A Sample Average Approximation Approach for the Stochastic Dial-A-Ride Problem on a Multigraph with User Satisfaction

Chang Lu, Yuehui Wu and Shanchuan Yu

European Journal of Operational Research, 2022, vol. 302, issue 3, 1031-1044

Abstract: In this study, we investigate a practical routing problem faced by a demand-responsive transportation service provider. To model the problem, we extend the dial-a-ride problem by defining the problem on a multigraph under a stochastic environment. The problem descriptions are provided first, and then we formulate the problem via a two-stage recourse model. To solve the problem, we design a sample average approximation procedure embedded with an adaptive large neighbourhood search algorithm. The proposed model and algorithm are then tested on instances generated from benchmarks and real-world data. The experiment results prove that the proposed algorithm can deal with the target problem properly, and considering stochastic factors and alternative paths in the underlying road network can reduce the operation cost and improve user satisfaction efficiently.

Keywords: Routing; Demand responsive transit; User satisfaction; Stochastic dial-a-ride problem; Multigraph Routing Problem (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722000716
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:302:y:2022:i:3:p:1031-1044

DOI: 10.1016/j.ejor.2022.01.033

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 ().