A Compressed Annealing Approach with Pre-Process for the Asymmetric Traveling Salesman Problem with Time Windows
Tadanobu Mizogaki*1, Masao Sugi*2, Masashi Yamamoto*3, Hidetoshi Nagai*3, Yusuke Shiomi*3, and Jun Ota*4
*1Mori Seiki Co. Ltd.
*2The University of Electro-Communications
*3NS Solutions Corporation
*4The University of Tokyo
This paper proposes a method of rapidly finding a feasible solution to the asymmetric traveling salesman problem with time windows (ATSP-TW). ATSP-TW is a problem that involves determining the route with the minimum travel cost for visiting n cities one time each with time window constraints (the period of time in which the city must be visited is constrained). “Asymmetrical” denotes a difference between the cost of outbound and return trips. For such a combinatorial optimization problem with constraints, we propose a method that combines a pre-process based on the insertion method with metaheuristics called “the compressed annealing approach.” In an experiment using a 3-GHz computer, our method derives a feasible solution that satisfies the time window constraints for all of up to about 300 cities at an average of about 1/7 the computing time of existing methods, an average computing time of 0.57 seconds, and a maximum computing time of 9.40 seconds.
-  E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, “The Traveling Salesman Problem,” John Wiley & Sons, 1985.
-  D. S. Johnson and L. A. McGeoch, “The Travelling Salesman Problem: A Case Study in Local Optimization,” in E. H. L. Aarts and J. K. Lenstra (Eds.) Local Search in Combinatorial Optimization, John Wiley & Sons, pp. 215-310, 1997.
-  R. W. Calvo, “A New Heuristic for the Traveling Salesman Problem with Time Windows,” Transportation Science, Vol.34, No.1, pp. 113-124, 2000.
-  M. W. P. Savelsbergh, “Local Search in Routing Problems with Time Windows,” Annals of Operations Research, Vol.4, No.1, pp. 285-305, 1985.
-  N. Ascheuer, M. Fischetti, andM. Grötschel, “Solving the Asymmetric Traveling Salesman Problem with Time Windows by Branch-and-Cut,” Mathematical Programming, Vol.90, No.3, pp. 475-506, 2001.
-  E. Balas and N. Simonetti, “Linear Time Dynamic Programming Algorithms for New Classes of Restricted TSPs: A Computational Study,” INFORMS J. on Computing, Vol.13, No.1, pp. 56-75, 2001.
-  F. Focacci, A. Lodi, and M.Milano, “A Hybrid Exact Algorithm for the TSPTW,” INFORMS J. on Computing, Vol.14, No.4, pp. 403-417, 2002.
-  A. Mingozzi, L. Bianco, and S. Ricciardelli, “Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints,” Operations Research, Vol.45, No.3, pp. 365-377, 1997.
-  A. Nikolakopoulos and H. Sarimveis, “A Threshold Accepting Heuristic with Intense Local Search of Special Instances of the Travelling Salesman Problem,” European J. of Operational Research, Vol.177, No.3, pp. 1911-1929, 2007.
-  J. W. Ohlmann and B. W. Thomas, “A Compressed Annealing Approach to the Travelling Salesman Problem with Time Windows,” INFORMS J. on Computing, Vol.19, No.1, pp. 80-90, 2007.
-  S. Kirkpatrick, C. Gellat, and M. Vecchi, “Optimization by Simulated Annealing,” Science, Vol.220, No.4598, pp. 671-680, 1983.
-  R. Fletcher, “Practical Methods of Optimization,” John Wiley & Sons, 1987.
-  M. López-Ibáñez and C. Blum, “Beam-ACO for the Travelling Salesman Problem with Time Windows,” Computers and Operations Research, Vol.37, No.8, pp. 1570-1583, 2010.
-  W. B. Carlton and J. W. Barnes, “Solving the Traveling-Salesman Problem with Time Windows using Tabu Search,” IIE Trans., Vol.28, No.8, pp. 617-629, 1996.
-  K. A. Dowsland, “Simulated Annealing,” in C. R. Reeves (Eds.) Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, Chapter 2, 1993.
-  M. Gendreau, A. Hertz, and G. Laporte, “New Insertion and Postoptimization Procedures for the Traveling Salesman Problem,” Operations Research, Vol.40, No.6, pp. 1086-1094, 1992.
-  J.-Y. Potvin and S. Bengio, “The Vehicle Routing Problem with Time Windows Part II: Genetic Search,” INFORMS J. on Computing, Vol.8, No.2, pp. 165-172, 1996.
-  A. Langevin, M. Desrochers, J. Desrosiers, S. Gelinas, and F. Soumis, “A Two-Commodity Flow Formulation for the Traveling Salesman and the Makespan Problems with Time Windows,” Networks, Vol.23, No.7, pp. 631-640, 1993.
-  Y. Dumas, J. Desrosiers, E. Gelinas, and M. M. Solomon, “An Optimal Algorithm for the Traveling Salesman Problem with TimeWindows,” Operations Research, Vol.43, No.2, pp. 367-371, 1995.
-  G. Pesant, M. Gendreau, J.-Y. Potvin, and J.-M. Rousseau, “An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows,” Transportation Science, Vol.32, No.1, pp. 12-29, 1998.