×

A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. (English) Zbl 1058.90054

Summary: We study a generalization of the well-known Traveling Salesman Problem (TSP) where each customer provides or requires a given non-zero amount of product, and the vehicle in a depot has a given capacity. Each customer and the depot must be visited exactly once by the vehicle supplying the demand while minimizing the total travel distance. We assume that the product collected from pickup customers can be delivered to delivery customers. We introduce a \(0-1\) integer linear model for this problem and describe a branch-and-cut procedure for finding an optimal solution. The model and the algorithm are adapted to solve instances of TSP with pickup and delivery. Some computational results are presented to analyze the performance of our proposal.

MSC:

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C09 Boolean programming

Software:

Concorde; VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows, in: G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (Eds.), Optimization, Vol. I, North-Holland, Amsterdam, 1989.; R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows, in: G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (Eds.), Optimization, Vol. I, North-Holland, Amsterdam, 1989. · Zbl 1201.90001
[2] Anily, S.; Hassin, R., The swapping problem, Networks, 22, 419-433 (1992) · Zbl 0763.90080
[3] Anily, S.; Mosheiov, G., The traveling salesman problem with delivery and backhauls, Oper. Res. Lett, 16, 11-18 (1994) · Zbl 0814.90119
[4] D. Applegate, R. Bixby, V. Chvatal, W. Cook, Concorde: a code for solving traveling salesman problem, http://www.math.princeton.edu/tsp/concorde.html; D. Applegate, R. Bixby, V. Chvatal, W. Cook, Concorde: a code for solving traveling salesman problem, http://www.math.princeton.edu/tsp/concorde.html
[5] Balas, E.; Padberg, M. W., Set partitioninga survey, SIAM Rev, 18, 710-760 (1976) · Zbl 0347.90064
[6] Benders, J. F., Partitioning procedures for solving mixed variables programming problems, Numer. Math, 4, 238-252 (1962) · Zbl 0109.38302
[7] Gendreau, M.; Laporte, G.; Vigo, D., Heuristics for the traveling salesman problem with pickup and delivery, Comp. Oper. Res, 26, 699-714 (1999) · Zbl 0957.90069
[8] B.L. Golden, W.R. Stewart, Empirical analysis of heuristics, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985.; B.L. Golden, W.R. Stewart, Empirical analysis of heuristics, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985.
[9] M. Grötschel, M.W. Padberg, Polyhedral theory, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985.; M. Grötschel, M.W. Padberg, Polyhedral theory, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985.
[10] H. Hernández-Pérez, J.J. Salazar-González, The one-commodity pickup-and-delivery travelling salesman problem, Lecture Notes in Computer Science, Vol. 2570, Springer, Berlin, 2002, pp. 89-104.; H. Hernández-Pérez, J.J. Salazar-González, The one-commodity pickup-and-delivery travelling salesman problem, Lecture Notes in Computer Science, Vol. 2570, Springer, Berlin, 2002, pp. 89-104.
[11] M. Jünger, G. Reinelt, G. Rinaldi, The travelling salesman problem, in: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.), Handbook in Operations Research and Management Science: Network Models, Elsevier, Amsterdam, 1995.; M. Jünger, G. Reinelt, G. Rinaldi, The travelling salesman problem, in: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.), Handbook in Operations Research and Management Science: Network Models, Elsevier, Amsterdam, 1995.
[12] Khachian, L. G., A polynomial algorithm in linear programming, Soviet Math. Dokl, 20, 191-194 (1979) · Zbl 0409.90079
[13] Mosheiov, G., The travelling salesman problem with pick-up and delivery, Eur. J. Oper. Res, 79, 299-310 (1994) · Zbl 0815.90135
[14] D. Naddef, G. Rinaldi, Branch-and-cut algorithms for the capacitated vehicle routing problem, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA, 2001.; D. Naddef, G. Rinaldi, Branch-and-cut algorithms for the capacitated vehicle routing problem, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA, 2001.
[15] Padberg, M. W.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev, 33, 60-100 (1991) · Zbl 0734.90060
[16] Savelsbergh, M. W.P.; Sol, M., The general pickup and delivery problem, Transportation Sci, 29, 17-29 (1995) · Zbl 0826.90049
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.