Paper:

# 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}

^{*1}Mori Seiki Co. Ltd.

^{*2}The University of Electro-Communications

^{*3}NS Solutions Corporation

^{*4}The 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.

*Int. J. Automation Technol.*, Vol.5, No.5, pp. 669-678, 2011.

- [1] E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, “The Traveling Salesman Problem,” John Wiley & Sons, 1985.
- [2] 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.
- [3] R. W. Calvo, “A New Heuristic for the Traveling Salesman Problem with Time Windows,” Transportation Science, Vol.34, No.1, pp. 113-124, 2000.
- [4] M. W. P. Savelsbergh, “Local Search in Routing Problems with Time Windows,” Annals of Operations Research, Vol.4, No.1, pp. 285-305, 1985.
- [5] 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.
- [6] 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.
- [7] 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.
- [8] 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.
- [9] 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.
- [10] 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.
- [11] S. Kirkpatrick, C. Gellat, and M. Vecchi, “Optimization by Simulated Annealing,” Science, Vol.220, No.4598, pp. 671-680, 1983.
- [12] R. Fletcher, “Practical Methods of Optimization,” John Wiley & Sons, 1987.
- [13] 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.
- [14] 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.
- [15] K. A. Dowsland, “Simulated Annealing,” in C. R. Reeves (Eds.) Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, Chapter 2, 1993.
- [16] 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.
- [17] 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.
- [18] 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.
- [19] 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.
- [20] 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.