Top > IJAT > A Compressed Annealing Approach with Pre-Process for the Asymm ...

single-au.php

IJAT Vol.5 No.5 pp. 669-678
doi: 10.20965/ijat.2011.p0669
(2011)

Paper:

Views over last 60 days: 546

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

Received:
March 26, 2011
Accepted:
June 21, 2011
Published:
September 5, 2011
Creative Commons License
Keywords:
Asymmetric Traveling Salesman Problem (ATSP), time window constraints, metaheuristics
Abstract
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.
Cite this article as:
T. Mizogaki, M. Sugi, M. Yamamoto, H. Nagai, Y. Shiomi, and J. Ota, “A Compressed Annealing Approach with Pre-Process for the Asymmetric Traveling Salesman Problem with Time Windows,” Int. J. Automation Technol., Vol.5 No.5, pp. 669-678, 2011.
Data files:
References
  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [11] S. Kirkpatrick, C. Gellat, and M. Vecchi, “Optimization by Simulated Annealing,” Science, Vol.220, No.4598, pp. 671-680, 1983.
  12. [12] R. Fletcher, “Practical Methods of Optimization,” John Wiley & Sons, 1987.
  13. [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. [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. [15] K. A. Dowsland, “Simulated Annealing,” in C. R. Reeves (Eds.) Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, Chapter 2, 1993.
  16. [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. [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. [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. [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. [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.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Oct. 11, 2024