Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
| Autor: | Mourad Baïou, Rafael Colares, Hervé Kerivin |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Department of Mathematical Sciences [Clemson], Clemson University, COLARES, RAFAEL |
| Rok vydání: | 2023 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Combinatorial optimization computational complexity Information Systems and Management [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] General Computer Science polyhedral study [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Management Science and Operations Research Industrial and Manufacturing Engineering [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO] Computer Science::Robotics Modeling and Simulation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] autonomous vehicles dial-a-ride |
| Zdroj: | European Journal of Operational Research. 310:552-565 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2023.03.018 |
| Popis: | 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 pickup 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect