A New Formulation for the Dial-a-Ride Problem
A New Formulation for the Dial-a-Ride Problem
复制标题
电话预约问题的新表述
DOI：
10.1287/trsc.2021.1044
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
M. Forbes
中科院分区：
文献类型：
--
作者：
Yannik Rist;M. Forbes
提出了一种新的混合整数规划模型和分支切割算法来求解电话预约问题。DARP是一个路线规划问题，其中几辆车必须为一组客户提供服务，每个客户都有一个取货和送货地点，并包括时间窗口和乘车时间限制。我们开发了“限制片段”，这是选择的部分路线，可以代表任何DARP路由。我们将展示如何列举这些限制片段，并证明它们之间的统治结果。我们提出的配方是解决BC算法，其中包括新的有效的不平等具体到我们的限制片段配方。该算法对现有和新的实例进行了基准测试，首次解决了9个现有实例的最优性。与当前最先进的方法相比，在大型实例上，运行时间减少了一到两个数量级。
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.