×

zbMATH — the first resource for mathematics

Decision diagrams for solving traveling salesman problems with pickup and delivery in real time. (English) Zbl 07165777
Summary: The Traveling Salesman Problem with Pickup and Delivery seeks a minimum cost path with pickups preceding deliveries. It is important in on-demand last-mile logistics, such as ride sharing and meal delivery. We examine the use of low-width decision diagrams in a branch-and-bound with and without assignment problem inference duals as a primal heuristic for finding good solutions within strict time budgets. We show these diagrams can be more effective than similarly structured hybrid constraint programming techniques for real-time decision making.
MSC:
90 Operations research, mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bergman, D.; Cire, A. A.; van Hoeve, W.-J., Lagrangian Bounds from decision diagrams, Constraints, 20, 3, 346-361 (2015) · Zbl 1327.90116
[2] Bergman, D.; Cire, A. A.; van Hoeve, W.-J.; Hooker, J., Decision Diagrams for Optimization (2016), Springer · Zbl 1338.90260
[3] Bergman, D.; Cire, A. A.; van Hoeve, W.-J.; Yunes, T., BDD-based heuristics for binary optimization, J. Heuristics, 20, 2, 211-234 (2014)
[4] Bertsimas, D.; Jaillet, P.; Martin, S., Online vehicle routing: the edge of optimization in large-scale applications, Operat. Res. (2019)
[5] Carpaneto, G.; Martello, S.; Toth, P., Algorithms and codes for the assignment problem, Ann. Oper. Res., 13, 1, 191-223 (1988)
[6] Caseau, Y.; Laburthe, F., Solving small tsps with constraints, (ICLP, Vol. 97 (1997)), 104
[7] Cire, A. A.; van Hoeve, W.-J., Multivalued decision diagrams for sequencing problems, Oper. Res., 61, 6, 1411-1428 (2013) · Zbl 1291.90091
[8] Dumitrescu, I.; Ropke, S.; Cordeau, J.-F.; Laporte, G., The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm, Math. Program., 121, 2, 269 (2010) · Zbl 1184.90108
[9] Focacci, F.; Lodi, A.; Milano, M., A hybrid exact algorithm for the TSPTW, INFORMS J. Comput., 14, 4, 403-417 (2002) · Zbl 1238.90054
[12] Kinable, J.; Cire, A. A.; van Hoeve, W.-J., Hybrid optimization methods for time-dependent sequencing problems, Eur. J. Operat. Res., 259, 3, 887-897 (2017) · Zbl 1402.90053
[16] Psaraftis, H. N., A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem, Transp. Sci., 14, 2, 130-154 (1980)
[18] Ruland, K.; Rodin, E., The pickup and delivery problem: faces and branch-and-cut algorithm, Comput. Math. Appl., 33, 12, 1-13 (1997) · Zbl 0894.90128
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.