The time dependent traveling salesman problem: Polyhedra and algorithm

被引：66

作者：

Abeledo H. ^{[1
]}

Fukasawa R. ^{[2
]}

Pessoa A. ^{[3
]}

Uchoa E. ^{[3
]}

机构：

[1] Department of Engineering Management and Systems Engineering, The George Washington University, WA, DC

[2] Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON

[3] Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói, RJ

来源：

Mathematical Programming Computation | 2013年 / 5卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Branch-price-and-cut; Cutting planes; Integer programming; Polyhedral combinatorics; Time dependent traveling salesman;

D O I：

10.1007/s12532-012-0047-y

中图分类号：

学科分类号：

摘要：

The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP. We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts. We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices. © 2012 Springer and Mathematical Optimization Society.

引用

页码：27 / 55

页数：28

共 29 条

[1]

Applegate D., Bixby R., Chvatal V., Cook W., On the solution of traveling salesman problems, Documenta Mathematica. Extra Volume ICM, 3, pp. 645-646, (1998)

[2]

Balas E., Carr R., Fischetti M., Simonetti N., New facets of the STS polytope generated from known facets of the ATS polytope, Discrete Optim., 3, pp. 3-19, (2006)

[3]

Balas E., Fischetti M., Polyhedral theory for the ATSP, The Traveling Salesman Problem and Its Variations, pp. 117-168, (2002)

[4]

Bigras L.-P., Gamache M., Savard G., The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup time, Discrete Optim., 5, pp. 685-699, (2008)

[5]

Dantzig G.B., Fulkerson D.R., Johnson S.M., Solution of a large-scale traveling salesman problem, Oper. Res., 2, pp. 393-410, (1954)

[6]

Fischetti M., Laporte G., Martello S., The delivery man problem and cumulative matroids, Oper. Res., 41, pp. 1055-1064, (1993)

[7]

Fox K., Gavish B., Graves S., An n-constraint formulation of the (time dependent) traveling salesman problem, Oper. Res., 28, pp. 101-102, (1980)

[8]

Gale D., A theorem of flows in networks, Pacif. J. Math., 7, pp. 1073-1082, (1957)

[9]

Godinho M.T., Gouveia L., Pesneau P., Natural and extended formulations for the time- dependent travelling salesman problem, (2010)

[10]

Gouveia L., Voss S., A classification of formulations for the (time-dependent) traveling salesman problem, Eur. J. Oper. Res., 83, pp. 69-82, (1995)

← 1 2 3 →