A New Formulation for the Dial-a-Ride Problem
提出一种新的混合整数规划形式化方法和分支切割算法，用于解决拨号乘车问题，通过“受限片段”表示路径，显著缩短大规模实例的计算时间。
This paper proposes a new mixed integer programming formulation and branch and cut (BC) algorithm to solve the dial-a-ride problem (DARP). The DARP is a route-planning problem where several vehicles must serve a set of customers, each of which has a pickup and delivery location, and includes time window and ride time constraints. We develop “restricted fragments,” which are select segments of routes that can represent any DARP route. We show how to enumerate these restricted fragments and prove results on domination between them. The formulation we propose is solved with a BC algorithm, which includes new valid inequalities specific to our restricted fragment formulation. The algorithm is benchmarked on existing and new instances, solving nine existing instances to optimality for the first time. In comparison with current state-of-the-art methods, run times are reduced between one and two orders of magnitude on large instances.