IMPROVEMENTS AND EXTENSIONS TO THE MILLER-TUCKER-ZEMLIN SUBTOUR ELIMINATION CONSTRAINTS

被引：363

作者：

DESROCHERS, M

LAPORTE, G

机构：

[1] ECOLE POLYTECH,MONTREAL H3T 1V6,QUEBEC,CANADA

[2] CTR RECH TRANSPORTS,MONTREAL H3C 3J7,QUEBEC,CANADA

来源：

OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 01期

关键词：

TRAVELING SALESMAN PROBLEM; VEHICLE ROUTING PROBLEM; SUBTOUR ELIMINATION CONSTRAINTS; LIFTING; FACETS;

D O I：

10.1016/0167-6377(91)90083-2

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper shows how the subtour elimination constraints developed by Miller, Tucker and Zemlin for the traveling salesman problem can be improved and extended to various types of vehicle routing problems.

引用

页码：27 / 36

页数：10

共 13 条

[1]

[Anonymous], 1954, OPERATIONS RES, DOI DOI 10.1287/OPRE.2.4.393

[2]

Desrochers M., 1988, VEHICLE ROUTING METH, V16, P65

[3]

Golden B., 1988, STUDIES MANAGEMENT S, V16

[4] PARTIAL LINEAR CHARACTERIZATIONS OF ASYMMETRIC TRAVELING SALESMAN POLYTOPE [J].

GROTSCHEL, M ;

PADBERG, MW .

MATHEMATICAL PROGRAMMING, 1975, 8 (03) :378-381

[5] INTEGER PROGRAMMING FORMULATIONS OF VEHICLE-ROUTING PROBLEMS [J].

KULKARNI, RV ;

BHAVE, PR .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 20 (01) :58-67

[6] CLASSIFICATION OF TRAVELING SALESMAN PROBLEM FORMULATIONS [J].

LANGEVIN, A ;

SOUMIS, F ;

DESROSIERS, J .

OPERATIONS RESEARCH LETTERS, 1990, 9 (02) :127-132

[7] OPTIMAL ROUTING UNDER CAPACITY AND DISTANCE RESTRICTIONS [J].

LAPORTE, G ;

NOBERT, Y ;

DESROCHERS, M .

OPERATIONS RESEARCH, 1985, 33 (05) :1050-1073

[8]

Laporte G., 1987, SURVEYS COMBINATORIA, V132, P147, DOI DOI 10.1016/s0304-0208(08)73235-3

[9]

Lawler E. L., 1985, TRAVELING SALESMAN P

[10] INTEGER PROGRAMMING FORMULATION OF TRAVELING SALESMAN PROBLEMS [J].

MILLER, CE ;

TUCKER, AW ;

ZEMLIN, RA .

JOURNAL OF THE ACM, 1960, 7 (04) :326-329

← 1 2 →