车辆路径规划中的Dial A Ride 问题简介

今天我们给大家带来的是Dial a ride问题(DAR)的介绍，文中所用资料多参考于文献。先上目录

本期内容

1.问题介绍

2.发展历史与应用

3.问题分类

4. 算法

1.问题介绍

如今我们对通过手机App等方式打车比较习以为常了，但在智能手机未普及之前，人们通常是通过打电话来订车的，也就是Dial a ride。如果我们开了一家出租车公司，在接到这些顾客的服务请求之后，我们自然需要考虑一下怎么用我们手上的出租车来满足顾客的需求，在这样的背景下我们就需要考虑一下这个问题啦。

Cordeau and Laporte曾经给这个问题下过定义：DAR问题即在满足顾客请求的前提下，在一个由所有节点和弧组成的完全图中组织车辆的行驶路线，使得这些行驶路线达到例如成本最低的规划目标。此外需要注意的是这种服务是共享的，即可能有多个不同的乘客同时在同一辆车上，跟我们说的顺风车有相似之处。

那么为什么要研究这样的问题呢？大家如果仔细地思考我们的公共交通系统就会发现，一种公共交通方式无法同时满足有成本效益的运作要求和高质量服务的要求。这里高质量服务并不是说司机给你开的什么车或者司机素质如何，而是说能不能在顾客期望的时间将顾客从指定的出发地运输到要求的目的地。而我们的公交车和火车、高铁等能够运输大量的乘客，是有成本效益的。

待发高铁(来源：凤凰网)

虽然高铁、公交这些工具能够运输大量的乘客，但是这些工具通常是固定路线和排班的。乘客需要根据这些路线和排班调整自己的行程。的士能够提供点到点的接送服务，但是这种服务不论是在金钱还是环境上的花费都是相对比较大的。也就是说我们会面临成本效益和服务质量的矛盾，但是还是会有人思考能不能全都要，在这两者之间平衡一下呢？平衡了之后的成果就是一种请求式的公共交通服务，先接收大家的请求，再派车进行服务，相对平衡一下成本效益和服务质量。这几种方式我们可以对比一下：

2.发展历史与应用

请求式的公共交通服务(也就是Dial a ride)首次尝试于1970年的美国俄亥俄州，1972年在英国的阿宾顿也有尝试。后来其可行性被证明以后相似的服务模式就开始在各地出现。

在早期，这种服务模式对哪些人群最有好处呢？答案是年长者和由于残疾行动不便的人，这一人群比较难正常地使用公共交通出行，因此这样的服务非常受这一人群的欢迎。美国在1990年的残疾人法案中，要求所有的公共交通代理公司为残疾人提供区别于普通的公共巴士服务的辅助客运系统（一般无固定路线或时间表），结果促进了DAR被广泛地引入、改进。

Dial a ride曾是一种为年长者和残疾人提供的非盈利性质的服务，通常在进行规划的时候以最小化花费为目标。在一些机场中，这种服务模式被用来运输老人、残疾人和伤者等，其服务时间窗非常短，规划目标是使得移动的距离最小。

还有一种主要的应用在医疗卫生领域，在这一领域的应用中，时间的紧迫性和设备或人员兼容性等特征非常重要以及如何完成工作人员和维修人员的日程安排也很复杂。例如对香港医院管理局(医管局)而言，需要派车辆进行病人的运输，每辆运送病人的救护车的内部必须在连续的行程之间进行消毒，以避免疾病扩散（Lim et al.,2017）。

后来在公共交通领域也有了相关的应用，在需求量比较低的时间段（例如大晚上）或者地点（例如比较偏僻的地方）无法使用固定的公共交通时（例如过了末班车时间或者没有对应的行驶线路），就可以使用这种服务模式。

而在近些年，随着技术的发展（网络和移动通信、云计算、数据分析等）使得DAR能够以新的方式运行。如果大量的人单独使用私家车通勤的话，不仅会导致中央商务区和城市道路的拥堵，还会增加很多碳排放，所以这种服务模式又开始有市场了。

但是这种服务系统的运营是非常复杂的，在不同的应用场景下会有不同的特征，例如在医护领域会对时间窗约束的要求比较高，而对于残疾人则需要尽可能减少移动距离，有的运营公司会使用多车型的车队进行服务等等。这意味着需要有相应的算法进行实时性比较好的规划和排班才能够提供比较高质量的服务，这也是这一领域研究的意义。

3.问题分类

正如上述所说，在不同运营环境下的DAR会考虑不同的特征，一些比较常见的需要考虑的问题特征通常有以下几点：

1. 对需求节点的访问：如果不允许拒绝请求，则需要规划各个请求节点的访问；如果允许拒绝请求，则需要根据情况考虑接受哪些请求并作进一步规划。

2. 时间窗：每个顾客都能指定从出发点出发的时间窗和到达目的地的时间窗。

3. 车辆场站：即车辆一趟服务中开始服务与结束服务的地点。

4. 旅程：当车辆回到场站的时候视为完成了一次旅程。

5. 车辆容量：即车辆核载人数。

6. 乘行时间：乘客乘车时花费的时间。

7. 路线持续时间：车辆在一次旅程中所花费的时间。

      通常在进行DAR的规划时需要在考虑上述特征的同时分配车辆，并为车辆作路径规划。我们知道，规划是需要一个规划目标的，规划目标可以从运营者视角出发（例如车辆行驶时间、总行驶距离、需要的车辆数量、司机的工作时间等）或者用户视角出发（例如乘行时间、等待时间、时间窗的满足情况等）。但是这两种视角对应的目标常常是冲突的。作为乘客，当然是希望能够尽可能地减少等待时间和乘行时间，但是这样就会造成运营成本的增加，比如需要增派车辆以达到这样的目标。

在很多情况下，规划目标的制定是多目标的，需要综合考虑多种情况。解决多目标DAR的研究大致可以分为三种：

1. 以多个目标的加权和为规划目标：目标的加权和适用于对不同目标的权重有明确和直接的评估的问题。

2. 按照重要性的顺序考虑：必须首先优化较高优先级的目标，然后在可能的情况下进一步优化较低优先级的目标。Garaix et al. (2010)首先考虑最小化运营成本然后才是最大化服务的质量。

3. 寻找问题的Pareto边界：Pareto边界由那些与其余的解相比不占劣势的解组成，Pareto边界为决策者提供了所有可能的最优解的全貌，当决策者对每个标准的相对重要性不确定时，这是特别有利的。它还有助于在战术层面上在不同的目标之间进行权衡。( Paquette et al., 2013 ).

而更加广泛的针对所有DAR的研究的分类则可以从两个方面来看：

1. 如果所有与决策制定相关的信息都在操作开始之前提供给决策制定者，则认为是规划的运作是静态的；如果在规划的运作过程中出现了新的信息，并且允许决策者对这些新信息做出响应，那么这个过程就是动态的。

2. 如果在做出决策时信息是确定的，那么这种问题就是一种确定性的DAR问题；如果决策时信息未知或者不确定，则可以看作是随机性的DAR问题。这两者也可以看作是完美信息和不完美信息的差别。

根据上述两个方面，我们可以得到四种分类如下图：

emmmm好像还是不太清楚的样子，那我们再说的详细点，完美信息需要考虑所有现在和未来运作有关的信息，例如(1)所有的潜在的用户有哪些；(2) 这些潜在的用户是否会变成真正的用户；(3)客户的具体需求量；(4) 未来每一次运作中可能出现的整个过程，比如车辆的行驶路线，每位顾客的接送等等。

上述这些信息如果与我们的预期相差不大，那么这样的问题就能够很好地逼近实际情况。上述表格中的Static and stochastic就是指决策者必须在开始之前在(2)-(4)中的一个或多个信息未知的情况下为所有事情做出决策，例如车辆的数量和行驶路线等等。剩下的相信大家就可以举一反三啦。

4.算法

好了，上面叨叨了这么多，相信大家对这个问题已经有了一些基本的认识。有了问题，就要解决问题，目前解决DAR问题及其变种问题的算法大致可以分成两种：精确算法和启发式算法。这个分类相信也在各位读者的意料之中。

精确算法

关注我们公众号的小伙伴肯定知道，精确算法能够求出问题的最优解，当问题的规模比较小的时候，精确算法能够在可接受的时间内找到最优解，但是问题的规模变大以后，求解所需要的计算量和存储空间都会急速增长。

而求解DAR问题的精确算法基本上都是基于Branch-and- Bound的，有Branch-and- cut、Branch-and-Price、Branch-and-price-and-cut几种。

其中Cordeau (2006)最早将Branch and cut算法应用到DAR问题上，Garaix et al. (2010, 2011) 则是应用了Branch and price算法，而在Branch and price and cut算法上，Qu and Bard (2015) and Gschwind and Irnich (2015) ,也给出了很好的应用。篇幅原因在这里就不对具体的内容做过多的介绍了，感兴趣的小伙伴可以找一找这些文献看看。

截至到2016年，一些用精确算法求解的结果大致如下：

注意算例那里的表示是车辆数目/请求数目。

2启发式算法

虽然精确性算法在小规模的算例上能够在可接受的时间内得到最优解，但是由于DAR问题是NP-Hard问题，所以研究的精力更多的是放在研究有效和高效的启发式算法上。而且我们在上文中也说过，从实际应用的角度出发，实际需求会需要能够更快响应的算法。下面列举几个在解DAR问题时常用的方法，其中很多方法是我们公众号的老伙伴了，经常关注的小伙伴应该也会比较熟悉。

1. Insertion Heuristics      这种方法比较简单，能够在较短的时间内找到可行解，但是解的质量不如元启发式算法。最早的应用由Jaw et al. (1986)完成。如今这种方法也被作为一种辅助用于找到可行解的方法在运用( Xiang et al., 2008; Wong et al., 2014; Markovi ´c et al., 2015 ),。

2. Tabu SearchCordeau and Laporte (2003)是最早提出在DAR问题中运用禁忌搜索算法的，他们使用了比较简单的邻域动作(将一个请求从一条路线转移到另一条路线)，有效果不错的多样化策略，例如对频繁移动这一行为进行惩罚，暂时接受不可行解。

3. Simulated Annealing在DAR问题上，SA并没有像其它方法那样被广泛的应用，少数几位作者( Mauri et al., 2009; Zidi et al., 2012; Reinhardt et al., 2013 )实现了标准的利用SA解DAR问题并取得了一定成果。

4. Variable Neighborhood SearchParragh et al. (2009)提出了第一个用于解决DAR问题的VNS算法，解决的是一个双目标的DAR问题。

5. Large Neighborhood Search在这个算法的研究上Ropke and Pisinger (2006)为带时间窗的接送问题设计的自适应大领域搜索算法为该算法在DAR问题上的应用打下了基础( Lehuédéet al., 2014;  Masmoudi et al., 2016; Molenbruch et al., 2017a )等人都曾为DAR问题设计LNS算法。

参考文献

• Cordeau, J.-F. , Laporte, G. , 2003. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp. Res. Part B: Methodol. 37 (6), 579–594 .

• Garaix, T. , Artigues, C. , Feillet, D. , Josselin, D. , 2010. Vehicle routing problems with alternative paths: an application to on-demand transportation. Eur. J. Oper. Res. 204 (1), 62–75 .

• Garaix, T. , Artigues, C. , Feillet, D. , Josselin, D. , 2010. Vehicle routing problems with alternative paths: an application to on-demand transportation. Eur. J. Oper. Res. 204 (1), 62–75 .

• Garaix, T. , Artigues, C. , Feillet, D. , Josselin, D. , 2011. Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation. Comput. Oper. Res. 38 (10), 1435–1442 .

• Gschwind, T. , Irnich, S. , 2015. Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transp. Sci. 49 (2), 335–354 .

• Ho, S. C., Szeto, W. Y., Kuo, Y.-H., Leung, J. M. Y., Petering, M., & Tou, T. W. H. (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B-Methodological, 111, 395–421. 

• Jaw, J.-J. , Odoni, A.R. , Psaraftis, H.N. , Wilson, N.H. , 1986. A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transp. Res. Part B: Methodol. 20 (3), 243–257 .

• Lehuédé, F. , Masson, R. , Parragh, S.N. , Péton, O. , Tricoire, F. , 2014. A multi-criteria large neighbourhood search for the transportation of disabled people. J. Oper. Res. Soc. 65 (7), 983–10 0 0 .

• Lim, A. , Zhang, Z. , Qin, H. , 2017. Pickup and delivery service with manpower planning in Hong Kong public hospitals. Transp. Sci. 51 (2), 688–705 .

• Markovi ´c, N. , Nair, R. , Schonfeld, P. , Miller-Hooks, E. , Mohebbi, M. , 2015. Optimizing dial-a-ride services in maryland: benefits of computerized routing and scheduling. Transp. Res. Part C: Emerg. Technol. 55, 156–165 .

• Masmoudi, M.A. , Hosny, M. , Braekers, K. , Dammak, A. , 2016. Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem. Transp. Res. Part E: Logist. Transp. Rev. 96, 60–80 .

• Mauri, G. , Antonio, L. , Lorena, N. , 2009. Customers’ satisfaction in a dial-a-ride problem. IEEE Intell. Transp. Syst. Mag. 1 (3), 6–14 .

• Molenbruch, Y. , Braekers, K. , Caris, A. , 2017. Benefits of horizontal cooperation in dial-a-ride services. Transp. Res. Part E: Logist. Transp. Rev. 107, 97–119 .

• Parragh, S.N. , Doerner, K.F. , Hartl, R.F. , Gandibleux, X. , 2009. A heuristic two-phase solution approach for the multi-objective dial-a-ride problem. Networks 54 (4), 227–242 .

• Paquette, J. , Cordeau, J.-F. , Laporte, G. , Pascoal, M.M.B. , 2013. Combining multicriteria analysis and tabu search for dial-a-ride problems. Transp. Res. Part B: Methodol. 52, 1–16 .

• Qu, Y. , Bard, J.F. , 2015. A branch-and-price-and-cut algorithm for heterogeneous pickup and delivery problems with configurable vehicle capacity. Transp. Sci. 49 (2), 254–270 .

• Reinhardt, L.B. , Clausen, T. , Pisinger, D. , 2013. Synchronized dial-a-ride transportation of disabled passengers at airports. Eur. J. Oper. Res. 225 (1), 106–117 .

• Ropke, S. , Pisinger, D. , 2006. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40 (4), 455–472 .

• Wong, K.I. , Han, A.F. , Yuen, C.W. , 2014. On dynamic demand responsive transport services with degree of dynamism. Transp. A: Transp. Sci. 10 (1), 55–73 .

• Xiang, Z. , Chu, C. , Chen, H. , 2008. The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments. Eur. J. Oper. Res. 185 (2), 534–551 .

• Zidi, I. , Mesghouni, K. , Zidi, K. , Ghedira, K. , 2012. A multi-objective simulated annealing for the multi-criteria dial a ride problem. Eng. Appl. Artif. Intell. 25 (6), 1121–1131 .