TSPTW
C++ code using ILOG Solver&Scheduler for TSP with time windows. The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a specific time window. We propose a hybrid approach for solving the TSPTW that merges Constraint Programming propagation algorithms for the feasibility viewpoint (find a path), and Operations Research techniques for coping with the optimization perspective (find the best path). We show with extensive computational results that the synergy between Operations Research optimization techniques embedded in global constraints, and Constraint Programming constraint solving techniques, makes the resulting framework effective in the TSPTW context also if these results are compared with state-of-the-art algorithms from the literature.
Keywords for this software
References in zbMATH (referenced in 31 articles , 1 standard article )
Showing results 1 to 20 of 31.
Sorted by year (- Boland, Natashia; Hewitt, Mike; Vu, Duc Minh; Savelsbergh, Martin: Solving the Traveling Salesman problem with time windows through dynamically generated time-expanded networks (2017)
- Fages, Jean-Guillaume; Lorca, Xavier; Rousseau, Louis-Martin: The salesman and the tree: the importance of search in CP (2016)
- Karabulut, Korhan; Fatih Tasgetiren, M.: A variable iterated greedy algorithm for the traveling salesman problem with time windows (2014)
- Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto: New state-space relaxations for solving the traveling salesman problem with time windows (2012)
- Benchimol, Pascal; van Hoeve, Willem-Jan; Régin, Jean-Charles; Rousseau, Louis-Martin; Rueher, Michel: Improved filtering for weighted circuit constraints (2012)
- Berbeglia, Gerardo; Cordeau, Jean-François; Laporte, Gilbert: A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem (2012)
- Dash, Sanjeeb; Günlük, Oktay; Lodi, Andrea; Tramontani, Andrea: A time bucket formulation for the traveling salesman problem with time windows (2012)
- Frederickson, Greg N.; Wittman, Barry: Approximation algorithms for the traveling repairman and speeding deliveryman problems (2012)
- Kiziltan, Zeynep; Lodi, Andrea; Milano, Michela; Parisini, Fabio: Bounding, filtering and diversification in CP-based local branching (2012)
- van Hoeve, Willem-Jan: Semidefinite programming and constraint programming (2012)
- Cattafi, Massimiliano; Gavanelli, Marco; Nonato, Maddalena; Alvisi, Stefano; Franchini, Marco: Optimal placement of valves in a water distribution network with $CLP(FD)$ (2011)
- Kovács, András; Beck, J. Christopher: A global constraint for total weighted completion time for unary resources (2011)
- Tramontani, Andrea: Enhanced mixed integer programming techniques and routing problems (2011)
- da Silva, Rodrigo Ferreira; Urrutia, Sebastián: A general VNS heuristic for the traveling salesman problem with time windows (2010)
- Heilporn, Géraldine; Cordeau, Jean-François; Laporte, Gilbert: The delivery man problem with time windows (2010)
- López-Ibáñez, Manuel; Blum, Christian: Beam-ACO for the travelling salesman problem with time windows (2010)
- Chang, Tsung-Sheng; Wan, Yat-Wah; Ooi, Wei Tsang: A stochastic dynamic traveling salesman problem with hard time windows (2009)
- Albiach, José; Sanchis, José María; Soler, David: An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation (2008)
- Artigues, Christian; Feillet, Dominique: A branch and bound method for the job-shop problem with sequence-dependent setup times (2008)
- Meyer, Bernd: Hybrids of constructive metaheuristics and constraint programming: A case study with ACO (2008) ioport