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

Ulrike Ritzinger, Jakob Puchinger, Christian Rudloff and Richard F. Hartl

European Journal of Operational Research, 2022, vol. 301, issue 2, 591-608

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.

Keywords: Transportation; Dial-a-Ride problem; Dynamic; Stochastic; Real-world application (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721009231
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:301:y:2022:i:2:p:591-608

DOI: 10.1016/j.ejor.2021.10.060

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().