Comparison of anticipatory algorithms for a dial-a-ride problem

• Published in: European journal of operational research 2022-09, Vol.301 (2), p.591-608
• Main Authors: Ritzinger, Ulrike, Puchinger, Jakob, Rudloff, Christian, Hartl, Richard F.
• Format: Article
• Language: English
• Subjects: Computer Science; Dial-a-Ride problem; Dynamic; Operations Research; Real-world application; Stochastic; Transportation
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2021.10.060

•Anticipatory algorithms for a real-world dial-a-ride problem in a highly dynamic environment.•Digital twin-based framework that enables extensive performance analysis of the algorithms.•Introducing a background optimization considerably improves the solution quality.•Experiments show that waiting strategies outperform the sample-scenario approach. Progress in digitalization opens opportunities to capture accurate transportation logistics data and provide advanced decision support, which leads into the question of how to efficiently exploit this progress in order to improve solution quality in transportation services. Here we address this issue in the context of a dynamic and stochastic patient transportation problem, where besides considering new events, we also incorporate stochastic information about future events. We propose different anticipatory algorithms and investigate which algorithm performs best according to the given settings in a real-world application. We therefore address different types of dynamic events, appropriate response times, and the synchronization of real-world data with the plan. In order to test and analyze how the algorithms behave and perform, we apply the concept of a digital twin. The implemented anticipatory algorithms compared here are a sample scenario planning approach and two waiting strategies. The question of the value of more sophisticated algorithms compared to algorithms with less computational effort is investigated. The experimental results show that solution quality benefits from incorporating information about future requests, and that simple waiting strategies prove most suitable for such a highly dynamic environment. We find that in highly stochastic environments, a rescheduling should be done whenever a new event occurs, whereas in less stochastic environments it is better to let the optimization engine run a bit longer and not start reoptimization after every new event.