Exact algorithms for the traveling salesman problem with draft limits

被引：26

作者：

Battarra, Maria ^{[1
]}

Pessoa, Artur Alves ^{[2
]}

Subramanian, Anand ^{[3
]}

Uchoa, Eduardo ^{[2
]}

机构：

[1] Univ Southampton, Sch Math, Southampton SO17 1BJ, Hants, England

[2] Univ Fed Fluminense, Dept Prod Engn, BR-24210240 Niteroi, RJ, Brazil

[3] Univ Fed Paraiba, Dept Prod Engn, Ctr Tecnol, BR-58051970 Joao Pessoa, Paraiba, Brazil

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2014年 / 235卷 / 01期

关键词：

Draft limits; Traveling salesman; Cutting planes; Column generation; Extended formulation; FORMULATION;

D O I：

10.1016/j.ejor.2013.10.042

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：115 / 128

页数：14

共 14 条

[1] The time dependent traveling salesman problem: Polyhedra and algorithm [J].

Abeledo H. ;

Fukasawa R. ;

Pessoa A. ;

Uchoa E. .

Mathematical Programming Computation, 2013, 5 (01) :27-55

[2]

Balas E., 2004, TRAVELING SALESMAN P, P117

[3] New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem [J].

Baldacci, Roberto ;

Mingozzi, Aristide ;

Roberti, Roberto .

OPERATIONS RESEARCH, 2011, 59 (05) :1269-1283

[4] SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN PROBLEM [J].

DANTZIG, G ;

FULKERSON, R ;

JOHNSON, S .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1954, 2 (04) :393-410

[5] 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

[6] The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3 [J].

Irnich, Stefan ;

Villeneuve, Daniel .

INFORMS JOURNAL ON COMPUTING, 2006, 18 (03) :391-406

[7] Mixed integer programming formulations for single machine scheduling problems [J].

Keha, Ahmet B. ;

Khowala, Ketan ;

Fowler, John W. .

COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 56 (01) :357-367

[8]

Lysgaard J., 2003, WORKING PAPER

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

MILLER, CE ;

TUCKER, AW ;

ZEMLIN, RA .

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

[10] Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems [J].

Pessoa A. ;

Uchoa E. ;

de Aragão M.P. ;

Rodrigues R. .

Mathematical Programming Computation, 2010, 2 (3-4) :259-290

← 1 2 →