×

zbMATH — the first resource for mathematics

Solving the Traveling Salesman problem with time windows through dynamically generated time-expanded networks. (English) Zbl 06756591
Salvagnin, Domenico (ed.) et al., Integration of AI and OR techniques in constraint programming. 14th international conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-59775-1/pbk; 978-3-319-59776-8/ebook). Lecture Notes in Computer Science 10335, 254-262 (2017).
Summary: The Traveling Salesman problem with time windows is the problem of finding a minimum-cost path visiting each of a set of cities exactly once, where each city must be visited within a specified time window. It has received significant attention because it occurs as a subproblem in many real-life routing and scheduling problems. We explore an approach in which the strength of a time-expanded integer linear programming (IP) formulation is exploited without ever explicitly creating the complete formulation. The approach works with carefully designed partially time-expanded networks, which are used to produce upper as well as lower bounds, and which are iteratively refined until optimality is reached. Preliminary computational results illustrate the potential of the approach as, for almost all instances tested, optimal solutions can be identified in only a few iterations.
For the entire collection see [Zbl 1364.68017].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Software:
TSPTW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ascheuer, N., Fischetti, M., Grötschel, M.: A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36(2), 69–79 (2000) · Zbl 0972.90085 · doi:10.1002/1097-0037(200009)36:2<69::AID-NET1>3.0.CO;2-Q
[2] Baldacci, R., Mingozzi, A., Roberti, R.: New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3), 356–371 (2012) · Zbl 06599275 · doi:10.1287/ijoc.1110.0456
[3] Boland, N., Hewitt, M., Marshall, L., Savelsbergh, M.: The continuous time service network design problem. Optimization Online 2015–01-4729 (2015)
[4] Dash, S., Günlük, O., Lodi, A., Tramontani, A.: A time bucket formulation for the traveling salesman problem with time windows. INFORMS J. Comput. 24(1), 132–147 (2012) · Zbl 06599260 · doi:10.1287/ijoc.1100.0432
[5] Dumas, Y., Desrosiers, J., Gélinas, É., Solomon, M.M.: An optimal algorithm for the traveling salesman problem with time windows. Oper. Res. 43(2), 367–371 (1995) · Zbl 0837.90036 · doi:10.1287/opre.43.2.367
[6] Focacci, F., Lodi, A., Milano, M.: A hybrid exact algorithm for the TSPTW. INFORMS J. Comput. 14(4), 403–417 (2002) · Zbl 1238.90054 · doi:10.1287/ijoc.14.4.403.2827
[7] Pesant, G., Gendreau, M., Potvin, J., Rousseau, J.: An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transp. Sci. 32(1), 12–29 (1998) · Zbl 0987.90086 · doi:10.1287/trsc.32.1.12
[8] Savelsbergh, M.W.P.: Local search in routing problems with time windows. Ann. Oper. Res. 4(1), 285–305 (1985) · doi:10.1007/BF02022044
[9] Savelsbergh, M.W.P.: The vehicle routing problem with time windows: minimizing route duration. INFORMS J. Comput. 4(2), 146–154 (1992) · Zbl 0780.90105 · doi:10.1287/ijoc.4.2.146
[10] da Silva, R.F., Urrutia, S.: A general VNS heuristic for the traveling salesman problem with time windows. Discrete Optim. 7(4), 203–211 (2010) · Zbl 1241.90130 · doi:10.1016/j.disopt.2010.04.002
[11] Wang, X., Regan, A.: Local truckload pickup and delivery with hard time window constraints. Transp. Res. Part B 36, 97–112 (2002) · doi:10.1016/S0965-8564(00)00037-9
[12] Wang, X., Regan, A.: On the convergence of a new time window discretization method for the traveling salesman problem with time window constraints. Comput. Ind. Eng. 56, 161–164 (2009) · doi:10.1016/j.cie.2008.04.011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.