[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.
Research Center/Unit :
HEC - QuantOM
Disciplines :
Quantitative methods in economics & management
Author, co-author :
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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
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.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.