Skip to Main content Skip to Navigation
New interface
Journal articles

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

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03418008
Contributor : Jakob Puchinger Connect in order to contact the contributor
Submitted on : Saturday, November 6, 2021 - 9:08:04 AM
Last modification on : Tuesday, October 18, 2022 - 8:34:05 AM

Links full text

Identifiers

Citation

Ulrike Ritzinger, Jakob Puchinger, Christian Rudloff, Richard F. Hartl. Comparison of anticipatory algorithms for a dial-a-ride problem. European Journal of Operational Research, 2022, 301 (2), pp.591-608. ⟨10.1016/j.ejor.2021.10.060⟩. ⟨hal-03418008⟩

Share

Metrics

Record views

65