Integer linear programming formulations of multiple salesman problems and its variations. (English) Zbl 1103.90065

Summary: We extend the classical multiple traveling salesman problem (mTSP) by imposing a minimal number of nodes that a traveler must visit as a side condition. We consider single and multidepot cases and propose integer linear programming formulations for both, with new bounding and subtour elimination constraints. We show that several variations of the multiple salesman problem can be modeled in a similar manner. Computational analysis shows that the solution of the multidepot mTSP with the proposed formulation is significantly superior to previous approaches.


90C10 Integer programming
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
Full Text: DOI


[2] Desrochers, M.; Laporte, G., Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints, Operations Research Letters, 10, 27-36 (1991) · Zbl 0723.90081
[3] Gavish, B., A note on the formulation of the \(m\)-salesman traveling salesman problem, Management Science, 22, 6, 704-705 (1976) · Zbl 0321.90034
[4] Gavish, B.; Srikanth, K., An optimal solution method for large-scale multiple traveling salesman problems, Operations Research, 34, 5, 698-717 (1986) · Zbl 0612.90099
[5] Gilbert, K. C.; Hofstra, R. B., A new multiperiod multiple traveling salesman problem with heuristic and application to a scheduling problem, Decision Sciences, 23, 250-259 (1992)
[6] Golden, B. L.; Magnanti, T. L.; Nguyen, H. O., Implementing vehicle routing algorithms, Networks, 7, 113-148 (1977) · Zbl 0359.90054
[7] Gorenstein, S., Printing press scheduling for multi-edition periodicals, Management Science, 16, 6, B373-B383 (1970)
[8] Kulkarni, R. V.; Bhave, P. R., Integer programming formulations of vehicle routing problems, European Journal of Operational Research, 20, 58-67 (1985)
[9] Laporte, G.; Nobert, Y., A cutting planes algorithm for the \(m\)-salesmen problem, Journal of the Operational Research Society, 31, 1017-1023 (1980) · Zbl 0441.90067
[10] Laporte, G., Integer programming formulations for the multi-depot vehicle routing problem, European Journal of Operational Research, 38, 227 (1989) · Zbl 0709.90610
[11] Laporte, G.; Nobert, Y.; Taillefer, S., Solving a family of multi-depot vehicle routing and location-routing problems, Transportation Science, 22, 3, 161-172 (1988) · Zbl 0662.90039
[12] Lenstra, J. K.; Rinnooy Kan, A. H.G., Some simple applications of the traveling salesman problem, Operations Research Quarterly, 26, 717-733 (1975) · Zbl 0308.90044
[13] Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulation of traveling salesman problems, Journal of the Association for Computing Machinery, 7, 326-329 (1960) · Zbl 0100.15101
[15] Svestka, J. A.; Huckfeldt, V. E., Computational experience with an \(m\)-salesman traveling salesman algorithm, Management Science, 19, 7, 790-799 (1973) · Zbl 0255.90033
[16] Tang, L.; Liu, J.; Rong, A.; Yang, Z., A multiple traveling salesman problem model for hot rolling scheduling in Shangai Baoshan Iron & Steel Complex, European Journal of Operational Research, 124, 267-282 (2000) · Zbl 1025.90523
[17] GuoXing, Y., Transformation of multidepot multisalesmen problem to the standard traveling salesman problem, European Journal of Operational Research, 81, 557-560 (1995) · Zbl 0912.90278
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.