Dial a ride曾是一种为年长者和残疾人提供的非盈利性质的服务,通常在进行规划的时候以最小化花费为目标。在一些机场中,这种服务模式被用来运输老人、残疾人和伤者等,其服务时间窗非常短,规划目标是使得移动的距离最小。
还有一种主要的应用在医疗卫生领域,在这一领域的应用中,时间的紧迫性和设备或人员兼容性等特征非常重要以及如何完成工作人员和维修人员的日程安排也很复杂。例如对中国香港医院管理局(医管局)而言,需要派车辆进行病人的运输,每辆运送病人的救护车的内部必须在连续的行程之间进行消毒,以避免疾病扩散(Lim et al.,2017)。
其中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) ,也给出了很好的应用。篇幅原因在这里就不对具体的内容做过多的介绍了,感兴趣的小伙伴可以找一找这些文献看看。
Insertion Heuristics 这种方法比较简单,能够在较短的时间内找到可行解,但是解的质量不如元启发式算法。最早的应用由Jaw et al. (1986)完成。如今这种方法也被作为一种辅助用于找到可行解的方法在运用( Xiang et al., 2008; Wong et al., 2014; Markovi ´c et al., 2015 ),。
Tabu Search Cordeau and Laporte (2003)是最早提出在DAR问题中运用禁忌搜索算法的,他们使用了比较简单的邻域动作(将一个请求从一条路线转移到另一条路线),有效果不错的多样化策略,例如对频繁移动这一行为进行惩罚,暂时接受不可行解。
Simulated Annealing 在DAR问题上,SA并没有像其它方法那样被广泛的应用,少数几位作者( Mauri et al., 2009; Zidi et al., 2012; Reinhardt et al., 2013 )实现了标准的利用SA解DAR问题并取得了一定成果。
Variable Neighborhood Search Parragh et al. (2009)提出了第一个用于解决DAR问题的VNS算法,解决的是一个双目标的DAR问题。
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 .