A note on the Miller-Tucker-Zemlin model for the asymmetric traveling salesman problem

• Autorzy: Sawik T.

Identyfikatory

DOI

10.1515/bpasts-2016-0057

• Języki publikacji: EN

Abstrakty

EN

An enhancement of the Miller-Tucker-Zemlin (MTZ) model for the asymmetric traveling salesman problem is presented by introducing additional constraints to the initial formulation. The constraints account for ordering of boundary nodes as well as all successive nodes in the salesman tour. The enhanced MTZ subtour elimination constraints are computationally compared with the basic MTZ constraints and the version of MTZ lifted by Desrochers and Laporte. The proposed enhancement shows improved performance on a number of asymmetric TSPLIB instances.

Słowa kluczowe

EN

asymmetric traveling salesman problem; Miller-Tucker-Zemlin constraints; subtour elimination constraints

PL

problem komiwojażera; SEC; metoda MTZ

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2016
• Tom: Vol. 64, nr 3
• Strony: 517--520
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Sawik T.

• AGH University of Science and Technology, Department of Operations Research and Information Technology, 30 Mickiewicza Av., 30-059 Kraków, Poland

Bibliografia

• [1] T. Öncan, I.K. Altinel and G. Laporte, “A comparative analysis of several asymmetric traveling salesman problem formulations”, Computers & Operations Research 36, 637–654 (2009).
• [2] G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, “Solution of a large-scale traveling salesman problem”, Operations Research 2, 393–410 (1954).
• [3] C.E. Miller, A.W. Tucker and R.A. Zemlin, “Integer programming formulations and traveling salesman problems”, Journal of Association for Computing Machinery 7, 326–329 (1960).
• [4] M. Desrochers and G. Laporte, “Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints”, Operations Research Letters 10, 27–36 (1991).
• [5] L. Gouveia and J.M. Pires, “The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints”, European Journal of Operational Research 112, 134146 (1999).
• [6] L. Gouveia and J.M. Pires, “The asymmetric travelling salesman problem: On generalizations of disaggregated Miller-Tucker-Zemlin constraints”, Discrete Applied Mathematics 112, 129–145 (2001).
• [7] H.D. Sherali and P.J. Driscoll, “On tightening the relaxations of Miller-Tucker-Zemlin formulations for asymmetric travelling salesman problems”, Operations Research 50(4), 656–669 (2002).
• [8] S.C. Sarin, H.D. Sherali and A. Bhootra, “New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints”, Operations Research Letters 33, 62–70 (2005).
• [9] T. Bektas and L. Gouveia, “Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?”, European Journal of Operational Research 236, 820–832 (2014).
• [10] TSPLIB, “A library of travelling salesman and related problem instances”, http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html (1997). Accessed 25.09.2015.
• [11] J. Cirasella, D.S. Johnson, L.A. McGeoch and W. Zhang, “The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests”, in A. L. Buchsbaum and J. Snoeyink (eds.), Algorithm Engineering and Experimentation, Lecture Notes in Computer Science, 2153, 32–59 (2001).
• [12] G. Gutin, A. Yeo and A. Zverovich, “Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP”, Discrete Applied Mathematics 117, 81–86 (2002).
• [13] P. C. Kanellakis and C. H. Papadimitriou, “Local search for the asymmetric traveling salesman problem”, Operations Research 28, 1086–1099 (1980).
• [14] W. Zhang, “Truncated branch-and-bound: A case study on the asymmetric TSP”, Proc. of AAAI 1993 Spring Symposium on AI and NP-Hard Problems, 160–166 (1993).