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

被引：16

作者：

Sawik, T. ^{[1
]}

机构：

[1] AGH Univ Sci & Technol, Dept Operat Res & Informat Technol, 30 Mickiewicza Ave, PL-30059 Krakow, Poland

来源：

BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES | 2016年 / 64卷 / 03期

关键词：

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

D O I：

10.1515/bpasts-2016-0057

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

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.

引用

页码：517 / 520

页数：4

共 14 条

[1] Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
Bektas, Tolga
Gouveia, Luis
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 236 (03) : 820 - 832
[2] Cirasella J., 2001, The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, volume 2153 of Lecture Notes in Computer Science, V2153, P32, DOI DOI 10.1007/3-540-44808-X
[3] SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN PROBLEM
DANTZIG, G
FULKERSON, R
JOHNSON, S
[J]. JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1954, 2 (04): : 393 - 410
[4] IMPROVEMENTS AND EXTENSIONS TO THE MILLER-TUCKER-ZEMLIN SUBTOUR ELIMINATION CONSTRAINTS
DESROCHERS, M
LAPORTE, G
[J]. OPERATIONS RESEARCH LETTERS, 1991, 10 (01) : 27 - 36
[5] The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
Gouveia, L
Pires, JM
[J]. DISCRETE APPLIED MATHEMATICS, 2001, 112 (1-3) : 129 - 145
[6] Gouveia L., 1999, EUR J OPER RES, V112, P134146
[7] Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP
Gutin, G
Yeo, A
Zverovich, A
[J]. DISCRETE APPLIED MATHEMATICS, 2002, 117 (1-3) : 81 - 86
[8] LOCAL SEARCH FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM
KANELLAKIS, PC
PAPADIMITRIOU, CH
[J]. OPERATIONS RESEARCH, 1980, 28 (05) : 1086 - 1099
[9] INTEGER PROGRAMMING FORMULATION OF TRAVELING SALESMAN PROBLEMS
MILLER, CE
TUCKER, AW
ZEMLIN, RA
[J]. JOURNAL OF THE ACM, 1960, 7 (04) : 326 - 329
[10] A comparative analysis of several asymmetric traveling salesman problem formulations
Oncan, Temel
Altinel, I. Kuban
Laporte, Gilbert
[J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (03) : 637 - 654

← 1 2 →