The time dependent traveling salesman problem: polyhedra and algorithm
Tóm tắt
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.
Tài liệu tham khảo
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: On the solution of traveling salesman problems. Documenta Mathematica. Extra Volume ICM 3, 645–646 (1998)
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, 3–19 (2006)
Balas, E., Fischetti, M.: Polyhedral theory for the ATSP. In: Gutin, G., Punnen, A. (eds.) The Traveling Salesman Problem and Its Variations, pp. 117–168. Kluwer, Dordrecht (2002)
Bigras, L.-Ph., Gamache, M., Savard, G.: The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup time. Discrete Optim. 5, 685–699 (2008)
Dantzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solution of a large-scale traveling salesman problem. Oper. Res. 2, 393–410 (1954)
Fischetti, M., Laporte, G., Martello, S.: The delivery man problem and cumulative matroids. Oper. Res. 41, 1055–1064 (1993)
Fox, K., Gavish, B., Graves, S.: An n-constraint formulation of the (time dependent) traveling salesman problem. Oper. Res. 28, 101–102 (1980)
Gale, D.: A theorem of flows in networks. Pacif. J. Math. 7, 1073–1082 (1957)
Godinho, M.T., Gouveia, L., Pesneau, P.: Natural and extended formulations for the time- dependent travelling salesman problem, CIO Report8/2010, Lisbon (2010)
Gouveia, L., Voss, S.: A classification of formulations for the (time-dependent) traveling salesman problem. Eur. J. Oper. Res. 83, 69–82 (1995)
Gouveia, L., Simonetti, L., Uchoa, E.: Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Math. Program. Online first (2009)
Groetschel, M., Padberg, M.: On the symmetric traveling salesman problem II: lifing theorems and facets. Math. Program. 16, 281–302 (1979)
Groetschel, M., Padberg, M.: Polyhedral theory. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds.) The Traveling Salesman Problem, pp. 251–305. Wiley, New York (1985)
Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10, 26–30 (1935)
Hoffman, A.: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Proc. Symp. Appl. Math. 10, 113–128 (1960)
Irnich, S., Villeneuve, D.: The shortest path problem with resource constraints and \(k\)-cycle elimination for \(k\ge 3\). INFORMS J. Comput. 18, 391–406 (2006)
Lucena, A.: Time-dependent traveling salesman problem—the deliveryman case. Networks 20, 753–763 (1990)
Méndez-Díaz, I., Zabala, P., Lucena, A.: A new formulation for the traveling deliveryman problem. Discrete Appl. Math. 156, 3233–3237 (2008)
Melo, M., Subramanian, A.: Personal communication (2010)
Miranda Bront, J.J., Méndez-Díaz, I., Zabala, P.: An integer programming approach for the time dependent traveling saleman problem. Electron. Notes Discrete Math. 36, 351–358 (2010)
Niskanen, S., Ostergard, P.R.J.: Cliquer users guide. Helsinki University of Technology. Communications Laboratory, Technical report 48 (2003)
Padberg, M.: On the facial structure of set packing polyhedra. Math. Program. 5, 199–215 (1973)
Picard, J., Queyranne, M.: The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper. Res. 26, 86–110 (1978)
Pessoa, A., Poggi de Aragão, M.: Robust branch-cut-and-price algorithms for vehicle routing problems. In: Golden, B., Raghavan, S., Wasil, E. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 297–326. Springer, New York (2008)
Pessoa, A., Uchoa, E., Poggi de Aragão, M.: A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54, 167–177 (2009)
Pessoa, A., Uchoa, E., Freitas, R.: Exact algorithm over an arc-time indexed formulations for parallel machine scheduling problems. Math. Program. Comput. 2, 259–290 (2010)
Ralphs, T.K., Ladányi, L.: COIN/BCP User’s Manual. http://www.coin-or.org/Presentations/bcp-man.pdf (2001)
Vajda, S.: Mathematical Programming. Addison-Wesley, New York (1961)
Vander Wiel, R.J., Sahinidis, N.V.: An exact solution approach for the time-dependent traveling salesman problem. Naval Res. Logist. 43, 797–820 (1996)