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 27 articles , 1 standard article )
Showing results 1 to 20 of 27.
Sorted by year (- Fages, Jean-Guillaume; Lorca, Xavier; Rousseau, Louis-Martin: The salesman and the tree: the importance of search in CP (2016)
- 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)
- 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)
- Beck, J.C.; Wilson, N.: Proactive algorithms for job shop scheduling with probabilistic durations (2007)
- Frederickson, Greg N.; Wittman, Barry: Approximation algorithms for the traveling repairman and speeding deliveryman problems with unit-time windows (2007)
- Laporte, Gilbert; Rodríguez Martín, Inmaculada: Locating a cycle in a transportation or a telecommunications network (2007)
- Mak, Vicky; Ernst, Andreas T.: New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP (2007)