A comparative analysis of several asymmetric traveling salesman problem formulations

被引：149

作者：

Oncan, Temel ^{[2
]}

Altinel, I. Kuban ^{[3
]}

Laporte, Gilbert ^{[1
]}

机构：

[1] HEC Montreal, Canada Res Chair Distribut Management, Montreal, PQ H3T 2A7, Canada

[2] Galatasaray Univ, Dept Ind Engn, TR-34357 Istanbul, Turkey

[3] Bogazici Univ, Dept Ind Engn, TR-34342 Istanbul, Turkey

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 03期

关键词：

Integer linear programming; Asymmetric traveling salesman problem; Formulations; Projections; CLASSIFICATION;

D O I：

10.1016/j.cor.2007.11.008

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this Survey. a classification of 24 asymmetric traveling salesman problem (ATSP) formulations is presented. The strength of their LP relaxations is discussed and known relationships from the literature are reviewed. Some new relationships are also introduced, and computational results are reported. (C) 2007 Elsevier Ltd. All rights reserved.

引用

页码：637 / 654

页数：18

共 28 条

[1]

ALTINEL IK, 2005, RES PAPER SERIES BOG

[2] THE PERFECTLY MATCHABLE SUBGRAPH POLYTOPE OF A BIPARTITE GRAPH [J].

BALAS, E ;

PULLEYBLANK, W .

NETWORKS, 1983, 13 (04) :495-516

[3] A NEW FORMULATION FOR THE TRAVELING SALESMAN PROBLEM [J].

CLAUS, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (01) :21-25

[4]

Dantzig G.B., 1954, OPER RES, V2, P363

[5] IMPROVEMENTS AND EXTENSIONS TO THE MILLER-TUCKER-ZEMLIN SUBTOUR ELIMINATION CONSTRAINTS [J].

DESROCHERS, M ;

LAPORTE, G .

OPERATIONS RESEARCH LETTERS, 1991, 10 (01) :27-36

[6]

DRISCOLL PJ, 1995, THESIS VIRGINIA POLY

[7]

FINKE G, 1984, CONGRESSUS NUMERANTI, V1, P167

[8] AN N-CONSTRAINT FORMULATION OF THE (TIME-DEPENDENT) TRAVELING SALESMAN PROBLEM [J].

FOX, KR ;

GAVISH, B ;

GRAVES, SC .

OPERATIONS RESEARCH, 1980, 28 (04) :1018-1021

[9]

Gavish B., 1978, GR07878 OP RES CTR M

[10] The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints [J].

Gouveia, L ;

Pires, JM .

DISCRETE APPLIED MATHEMATICS, 2001, 112 (1-3) :129-145

← 1 2 3 →