 Complexity, algorithmic, and computational aspects of a dial-a-ride type problemMourad Baïou, Rafael Colares and Hervé Kerivin European Journal of Operational Research, 2023, vol. 310, issue 2, 552-565 Abstract: In dial-a-ride systems involving autonomous vehicles circulating along a circuit, a fleet of vehicles must serve clients who request rides between stations of the circuit such that the total number of pick-up and drop-off operations is minimized. In this paper, we focus on a unitary variant where each client requests a single place in the vehicles and all the clients must be served within a single tour of the circuit. Such unitary variant induces a combinatorial optimization problem for which we introduce a nontrivial special case that is polynomially solvable when the capacity of each vehicle is at most 2 but it is NP-Hard otherwise. We also study the polytope associated with the solutions to this problem. We introduce new families of valid inequalities and give necessary and sufficient conditions under which they are facet-defining. Based on these inequalities, we devise an efficient branch-and-cut algorithm that outperforms the state-of-the-art commercial solvers. Keywords: Combinatorial optimization; Autonomous vehicles; Dial-a-ride; Computational complexity; Polyhedral study (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:310:y:2023:i:2:p:552-565 DOI: 10.1016/j.ejor.2023.03.018 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 |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.