[en] The problem considered in this work stems from a non-profit organization in charge of door-to-door passenger transportation for medical appointments. Patients are picked up at home by a driver and are then dropped at their appointment location. They may also be driven back home at the end of their appointment. Some patients have specific requirements, e.g., they may require an accompanying person or a wheelchair. Planning such activities gives rise to a so-called dial-a-ride problem. In the present work, it is assumed that the requests assigned to the drivers have been selected, and the transportation plan has been established for the next day. However, in practice, appointment durations may vary due to unforeseen circumstances, and some transportation requests may be modified, delayed or canceled during the day. The aim of this work is to propose a reactive algorithm which can adapt the initial plan in order to manage the disruptions and to take care of as many patients as possible in real-time. The plan should be modified quickly when a perturbation is observed, without resorting to major changes which may confuse the drivers and the patients. Several recourse procedures are defined for this purpose. They allow the dispatcher to temporarily delete a request, to insert a previously deleted request, or to permanently cancel a request. Simulation techniques are used to test the approach on randomly generated scenarios. Several key performance indicators are introduced in order to measure the impact of the disruptions and the quality of the solutions.
Centre de recherche :
HEC - QuantOM
Disciplines :
Méthodes quantitatives en économie & gestion
Auteur, co-auteur :
Paquay, Célia ; Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Berbeglia, G., Cordeau, J.-F., & Laporte, G. (2010), Dynamic pickup and delivery problems. European Journal of Operational Research, 202(1), 8–15.
Berbeglia, G., Pesant, G., & Rousseau, L.-M. (2011), Checking the feasibility of dial-a-ride instances using constraint programming. Transportation Science, 45(3), 399–412.
Berbeglia, G., Pesant, G., & Rousseau, L.-M. (2012), Feasibility of the pickup and delivery problem with fixed partial routes: A complexity analysis. Transportation Science, 46(3), 359–373.
Cappart, Q., Thomas, C., Schaus, P., & Rousseau, L.-M. (2018), A constraint programming approach for solving patient transportation problems. In J. Hooker (Ed.), Principles and practice of constraint programming (pp. 490–506), Cham: Springer International Publishing.
Cordeau, J.-F. (2006), A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3), 573–586.
Cordeau, J.-F., & Laporte, G. (2003), A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 37(6), 579–594.
Cordeau, J.-F., & Laporte, G. (2007), The dial-a-ride problem: Models and algorithms. Annals of Operations Research, 153(1), 29–46.
Coslovich, L., Pesenti, R., & Ukovich, W. (2006), A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem. European Journal of Operational Research, 175(3), 1605–1615.
Häll, C. H., Högberg, M., & Lundgren, J. T. (2012), A modeling system for simulation of dial-a-ride services. Public Transport, 4(1), 17–37.
Ho, S. C., Szeto, W., Kuo, Y.-H., Leung, J. M., Petering, M., & Tou, T. W. (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. Transportation Research Part B: Methodological, 20(3), 243–257.
Liebchen, C., Lübbecke, M., Möhring, R., & Stiller, S. (2009), The concept of recoverable robustness, linear programming recovery, and railway applications. In R. K. Ahuja, R. Möhring, & C. D. Zaroliagis (Eds.), Proceedings of the robust and online large-scale optimization, LNCS 5868 (pp. 1–27). Berlin Heidelberg: Springer-Verlag.
Liu, C., Aleman, D. M., & Beck, J. C. (2018), Modelling and solving the senior transportation problem. In W.-J. van Hoeve (Ed.), Proceedings of the Integration of constraint programming, artificial intelligence, and operations research, CPAIOR 2018 (pp. 412–428), Lecture Notes in Computer Science, 10848 Springer, Cham.
Mitrović-Minić, S., Krishnamurti, R., & Laporte, G. (2004), Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 38(8), 669–685.
Mitrović-Minić, S., & Laporte, G. (2004), Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 38(7), 635–655.
Molenbruch, Y., Braekers, K., & Caris, A. (2017), Typology and literature review for dial-a-ride problems. Annals of Operations Research, 259(1), 295–325.
Paquette, J., Cordeau, J.-F., & Laporte, G. (2009), Quality of service in dial-a-ride operations. Computers & Industrial Engineering, 56(4), 1721–1734.
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. (2013), A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1–11.
Psaraftis, H. N. (1986), Scheduling large-scale advance-request dial-a-ride systems. American Journal of Mathematical and Management Sciences, 6(3-4), 327–367.
Psaraftis, H. N., Wen, M., & Kontovas, C. A. (2016), Dynamic vehicle routing problems: Three decades and counting. Networks, 67(1), 3–31.
Ropke, S., Cordeau, J.-F., & Laporte, G. (2007), Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks, 49(4), 258–272.
Savelsbergh, M. W. P. (1985), Local search in routing problems with time windows. Annals of Operations research, 4(1), 285–305.
Savelsbergh, M. W. P. (1992), The vehicle routing problem with time windows: Minimizing route duration. ORSA Journal on Computing, 4(2), 146–154.
Savelsbergh, M. W. P., & Sol, M. (1995), The general pickup and delivery problem. Transportation Science, 29(1), 17–29.
Schilde, M., Doerner, K. F., & Hartl, R. F. (2011), Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports. Computers & Operations Research, 38(12), 1719–1730.
