Complexity, algorithmic, and computational aspects of a dial-a-ride type problem. (English) Zbl 07709834
Summary: 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.
MSC:
| 90Bxx | Operations research and management science |
Keywords:
combinatorial optimization; autonomous vehicles; dial-a-ride; computational complexity; polyhedral studyReferences:
| [1] | Baïou, M., Colares, R., & Kerivin, H. (2021). The complexity of the unit stop number problem and its implications to other related problems. Preprint, URL: https://hal.archives-ouvertes.fr/hal-03120087. · Zbl 1536.90011 |
| [2] | Braekers, K.; Caris, A.; Janssens, G. K., Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots, Transportation Research Part B: Methodological, 67, 166-186 (2014) |
| [3] | Bsaybes, S.; Quilliot, A.; Wagler, A. K., Fleet management for autonomous vehicles using multicommodity coupled flows in time-expanded networks, 17th International symposium on experimental algorithms (SEA 2018) (2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik |
| [4] | Carvajal, R.; Ahmed, S.; Nemhauser, G.; Furman, K.; Goel, V.; Shao, Y., Using diversification, communication and parallelism to solve mixed-integer linear programs, Operations Research Letters, 42, 2, 186-189 (2014) · Zbl 1408.90194 |
| [5] | Chvatal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Mathematics, 4, 4, 305-337 (1973) · Zbl 0253.05131 |
| [6] | Colares, R., Exploring combinatorial aspects of the stop number problem (2019), University Clermont Auvergne, France, Ph.D. thesis. |
| [7] | Cordeau, J.-F., A branch-and-cut algorithm for the dial-a-ride problem, Operations Research, 54, 3, 573-586 (2006) · Zbl 1167.90681 |
| [8] | Cordeau, J.-F.; Laporte, G., The dial-a-ride problem: Models and algorithms, Annals of operations research, 153, 1, 29-46 (2007) · Zbl 1157.90353 |
| [9] | Denton, B. T.; Miller, A. J.; Balasubramanian, H. J.; Huschka, T. R., Optimal allocation of surgery blocks to operating rooms under uncertainty, Operations Research, 58, 4-part-1, 802-816 (2010) · Zbl 1228.90065 |
| [10] | Dyer, M. E.; Frieze, A. M., Planar 3DM is NP-complete, Journal of Algorithms, 7, 2, 174-184 (1986) · Zbl 0606.68065 |
| [11] | EasyMile (2015). Ez10 passenger shuttle. www.easymile.com/vehicle-solutions/ez10-passenger-shuttle. |
| [12] | Fagnant, D. J.; Kockelman, K., Preparing a nation for autonomous vehicles: Opportunities, barriers and policy recommendations, Transportation Research Part A: Policy and Practice, 77, 167-181 (2015) |
| [13] | Fischetti, M.; Hamacher, H. W.; Jørnsten, K.; Maffioli, F., Weighted k-cardinality trees: Complexity and polyhedral structure, Networks, 24, 1, 11-21 (1994) · Zbl 0809.90124 |
| [14] | Fischetti, M.; Monaci, M., Exploiting erraticism in search, Operations Research, 62, 1, 114-122 (2014) · Zbl 1291.90148 |
| [15] | Garey, M. R.; Johnson, D. S., Computers and intractability, Vol. 29 (2002), W.H. Freeman and Company: W.H. Freeman and Company New York |
| [16] | Goldschmidt, O.; Hochbaum, D. S.; Levin, A.; Olinick, E. V., The SONET edge-partition problem, Networks: An International Journal, 41, 1, 13-23 (2003) · Zbl 1026.90076 |
| [17] | Gomory, R. E., Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical society, 64, 5, 275-278 (1958) · Zbl 0085.35807 |
| [18] | Ho, S. C.; Szeto, W. Y.; Kuo, Y.-H.; Leung, J. M.Y.; Petering, M.; Tou, T. W.H., A survey of dial-a-ride problems: Literature review and recent developments, Transportation Research Part B: Methodological, 111, 395-421 (2018) |
| [19] | Kaibel, V.; Peinhardt, M.; Pfetsch, M. E., Orbitopal fixing, Discrete Optimization, 8, 4, 595-610 (2011) · Zbl 1235.90091 |
| [20] | Kaibel, V.; Pfetsch, M. E., Packing and partitioning orbitopes, Mathematical Programming, 114, 1, 1-36 (2008) · Zbl 1171.90004 |
| [21] | Karp, R. M., Reducibility among combinatorial problems, Complexity of computer computations, 85-103 (1972), Springer · Zbl 1467.68065 |
| [22] | 26-26 |
| [23] | Liu, M.; Luo, Z.; Lim, A., A branch-and-cut algorithm for a realistic dial-a-ride problem, Transportation Research Part B: Methodological, 81, 267-288 (2015) |
| [24] | Margot, F., Symmetry in integer linear programming, 50 Years of integer programming 1958-2008, 647-686 (2010), Springer · Zbl 1187.90200 |
| [25] | Masuyama, S.; Ibaraki, T., Chain packing in graphs, Algorithmica, 6, 1-6, 826-839 (1991) · Zbl 0731.68088 |
| [26] | Ostrowski, J.; Anjos, M. F.; Vannelli, A., Symmetry in scheduling problems (2010), Citeseer |
| [27] | Parragh, S. N., Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem, Transportation Research Part C: Emerging Technologies, 19, 5, 912-930 (2011) |
| [28] | Parragh, S. N.; Doerner, K. F.; Hartl, R. F., A survey on pickup and delivery problems, Journal für Betriebswirtschaft, 58, 1, 21-51 (2008) |
| [29] | Pelletier, S.; Jabali, O.; Laporte, G., 50th Anniversary invited article-goods distribution with electric vehicles: Review and research perspectives, Transportation Science, 50, 1, 3-22 (2016) |
| [30] | Pimenta, V.; Quilliot, A.; Toussaint, H.; Vigo, D., Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles, European Journal of Operational Research, 257, 2, 601-613 (2017) · Zbl 1394.90121 |
| [31] | Ravi, R.; Sundaram, R.; Marathe, M. V.; Rosenkrantz, D. J.; Ravi, S. S., Spanning trees-short or small, SIAM Journal on Discrete Mathematics, 9, 2, 178-200 (1996) · Zbl 0855.05058 |
| [32] | Ropke, S.; Cordeau, J.-F.; Laporte, G., Models and branch-and-cut algorithms for pickup and delivery problems with time windows, Networks: An International Journal, 49, 4, 258-272 (2007) · Zbl 1141.90340 |
| [33] | Sabharwal, A.; Samulowitz, H.; Reddy, C., Guiding combinatorial optimization with UCT, International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming, 356-361 (2012), Springer |
| [34] | Sherali, H. D.; Smith, J. C., Improving discrete model representations via symmetry considerations, Management Science, 47, 10, 1396-1407 (2001) · Zbl 1232.90309 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
