A branch-and-bound algorithm for the time-dependent travelling salesman problem

被引：21

作者：

Arigliano, Anna ^{[1
]}

Calogiuri, Tobia ^{[1
]}

Ghiani, Gianpaolo ^{[1
]}

Guerriero, Emanuela ^{[1
]}

机构：

[1] Univ Salento, Dipartimento Ingn Innovaz, Lecce, Italy

来源：

NETWORKS | 2018年 / 72卷 / 03期

关键词：

branch-and-bound; lower bound; time-dependent; transportation; travelling salesman problem; vehicle routing; VEHICLE-ROUTING PROBLEMS; CUT ALGORITHM; SETUP TIMES; FORMULATIONS; COSTS;

D O I：

10.1002/net.21830

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a graph whose arc traversal times vary over time, the Time-Dependent Travelling Salesman Problem consists of finding a Hamiltonian tour of least total duration. In this paper we exploit some properties of the problem and develop a branch-and-bound algorithm which outperforms the state-of-the-art branch-and-cut procedure by Cordeau et al. [5].

引用

页码：382 / 392

页数：11

共 26 条

[1] An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation [J].

Albiach, Jose ;

Sanchis, Jose Maria ;

Soler, David .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 189 (03) :789-802

[2]

Applegate D.L., 2011, TRAVELING SALESMAN P

[3] The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times [J].

Bigras, Louis-Philippe ;

Gamache, Michel ;

Savard, Gilles .

DISCRETE OPTIMIZATION, 2008, 5 (04) :685-699

[4] SOME NEW BRANCHING AND BOUNDING CRITERIA FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].

CARPANETO, G ;

TOTH, P .

MANAGEMENT SCIENCE, 1980, 26 (07) :736-743

[5] Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem [J].

Cordeau, Jean-Francois ;

Ghiani, Gianpaolo ;

Guerriero, Emanuela .

TRANSPORTATION SCIENCE, 2014, 48 (01) :46-58

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

[7] Time-dependent routing problems: A review [J].

Gendreau, Michel ;

Ghiani, Gianpaolo ;

Guerriero, Emanuela .

COMPUTERS & OPERATIONS RESEARCH, 2015, 64 :189-197

[8] A Note on the Ichoua, Gendreau, and Potvin (2003) Travel Time Model [J].

Ghiani, Gianpaolo ;

Guerriero, Emanuela .

TRANSPORTATION SCIENCE, 2014, 48 (03) :458-462

[9] Natural and extended formulations for the Time-Dependent Traveling Salesman Problem [J].

Godinho, Maria Teresa ;

Gouveia, Luis ;

Pesneau, Pierre .

DISCRETE APPLIED MATHEMATICS, 2014, 164 :138-153

[10] A CLASSIFICATION OF FORMULATIONS FOR THE (TIME-DEPENDENT) TRAVELING SALESMAN PROBLEM [J].

GOUVEIA, L ;

VOSS, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 83 (01) :69-82

← 1 2 3 →