1. SCSIT
  2. Всі випуски
  3. Випуск 650, 2009
  4. Дослідження ефективності існуючих алгоритмів для розв’язання задачі комівояжера

Дослідження ефективності існуючих алгоритмів для розв’язання задачі комівояжера

SCSIT.
2009;
Випуск 650
: cc. 235 - 244
Authors: 

Р. Базилевич, Р. Кутельмах

Національний університет «Львівська політехніка», кафедра програмного забезпечення

Досліджено ефективність існуючих точних та евристичних алгоритмів розв’язання задачі комівояжера. Зроблено висновки щодо доцільності їх застосування при розв’я- занні задач великих розмірностей, а також при декомпозиції.

Existing exact and heuristic algorithms’ efficiency for solving Traveling Salesman Problem has been investigated. The conclusions were made of their application for solving large-scale problems as well as for using with decomposition.

  1. Reinelt, Gerhard (1994), The Traveling Salesman: Computational Solutions for TSP Applications. Lecture Notes in Computer Science 840, Springer–Verlag, Berlin.
  2. Reinelt, Gerhard (1992), Fast heuristics for large geometric traveling salesman problems. ORSA Journal on computing, 4:206-217
  3. David S. Johnson and Lyle A. McGeoch. Experimental Analysis of Heuristics for the STSP. In Gutin and Punnen, editors, The Traveling Salesman Problem and its Variations. Kluwer Academic Publishers, 2002.
  4.  S. Lin and B. W. Kernighan. An effective heuristic algorithm for the Traveling salesman problern. Operations Research, 21:498–516. 1973.
  5. S. Lin. Computer solutions of the travelling salesman problem. Bell System Technical Journal 44, pages 2245–2269, 1965.
  6. K .Helsgaun, «An effective implementation of the Lin–Kernighan Traveling Salesman Heuristic», 2002.
  7. Reinelt, Gerhard (1991) TSPLIB — A traveling salesman problem library, ORSA Journal on Computing 3, 376–384.
  8. http://www.research.att.com/~dsj/chtsp/
  9. D. Applegate, R.E. Bixby, V. Chvátal, and W. Cook. On the solution of traveling salesman problems. Documenta Mathematica, Extra Volume ICM III: 645–656, 1998.
  10. D. Applegate, W. Cook, A. Rohe. Chained Lin–Kernighan for large traveling salesman problems. INFORMS J. Computing, to appear.
  11. D. Applegate, R.E. Bixby, V. Chvátal, and W. Cook. Findong tours in the TSP.1998.
  12. D. Applegate, R.E. Bixby, V. Chvátal, and W. Cook. Findong cuts in the TSP.1995
  13. http://www.tsp.gatech.edu/concorde.html
  14. D. Neto. Efficient cluster compensation for Lin–Kernighan Heuristics. PhD thesis, Department of Computer Science, University of Toronto, 1999.
  15. G. Laporte, J-Y. Potvin, F. Quilleret, «A Tabu Search using Genetic Diversification for the Clustered Traveling Salesman Problem», Journal of Heuristics, Vol 2 (3), p. 187-200, 1996.
  16. Held, M., and Karp, R. M. (1970), «The Traveling Salesman Problem and Minimum Spanning Trees», Operations Research. 18:1138–1162.
  17. Held, M., and Karp, R. M. (1971), «The Traveling Salesman Problem and Minimum Spanning Trees: part II», Mathematical Programming 1:6–25.
  18. C. L. Valenzuela and A. J. Jones, ‘‘Estimating the Held–Karp lower bound for the geometric TSP, ’’ Manuscript dated 8 June 1995.
  19. Balas, E., and Toth, P. (1985), «Branch and Bound Methods», in The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. E. L. Lawler, J. K Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys. Eds. John Wiley and Sons, New York.
  20. Held, M., Wolfe, P., and Crowder, H. P. (1974), «Validation of subgradient optimization», Mathematical Programming 6:62–88
  21. Wolsey, L. (1980), «Heuristic analysis, linear programming, and branch and bound», Mathematical Programming Study 13:121–134.
  22. Shmoys, D. B., and Williamson, D. P. (1990), «Analyzing the Held–Karp TSP Bound: A Monotonicity Property with Application», Information Processing Letters. 35:281–285.
  23. Christofides, N. (1979), «The Traveling Salesman Problem», in Combinatorial Optimization. N. Christophides, A. Mingozzi, P. Toth and C. Sandi. Eds. John Wiley and Sons, New York.
  24. Volgenant, T., and Jonker, R. (1982), «A branch and bound algorithm for the symmetric traveling salesman problem based on the 1–tree relaxation», European Journal of Operational Research. 9:83–89.
  25. Johnson, David S. (1990), «Local Optimization and the Traveling Salesman Problem», Automata Languages and Programming: 17th International Colloquium Proceedings.
  26. Johnson, D. S., McGeoch L. A., and Rothberg, E.E. (1996), «Asymptotic experimental analysis for the Held–Karp traveling salesman bound», Proceeding 1996 ACM–SIAM symposium on Discrete Algorithms.
  27. G. B. Dantzig, R. Fulkerson, and S. M. Johnson, Solution of a large–scale traveling salesman problem, Operations Research 2 (1954), pp. 393–410.
  28. Johnson, D. S., McGeoch L. A. The traveling salesman problem: A case study in local optimization. In E.H.L. Aaarts and J.K. Lenstra, editors, Local Search in Combinatorial Optimization, pp 215–310, John Wiley & Sons, New York, 1997.
  29. J. L. Bentley, ‘‘Multidimensional binary search trees used for associative search, ’’ Comm. ACM 18 (1975), 309–517.
  30. J. L. Bentley, ‘‘Experiments on traveling salesman heuristics, ’’ in Proc. 1st Ann. ACMSIAM Symp. on Discrete Algorithms, SIAM, Philadelphia, PA, 1990a, 91-99.
  31. J. L. Bentley, ‘‘K d trees for semidynamic point sets, ’’ in Proc. 6th Ann. Symp. on Computational Geometry, ACM, New York, 1990b, 187–197.
  32. J. L. Bentley, ‘‘Fast algorithms for geometric traveling salesman problems, ’’ ORSA J. Comput. 4 (1992), 387–411.
  33. D. S. Johnson. Local optimization and the traveling salesman problem. In ICALP '90. pages 446–461. Springer–Verlag, 1990. Proceedings of the lith Colloquium on Automata. Languages and Programming.
  34. B. Chandra. H. Karioff. and C. Tovey. 'New results on the old k–opt algorithm for The TSP. In Proceedings of the Fifth ACM–SIAM Symposium on Discrete Algorithms. Pages 150–159, 1994.
  35. L. Fredman, D. S. Johnson. L. A. McGeoch. and G. Ostheimer. Data Structures for Traveling salesmen. Journal of Algorithms. 18:432–479. 1995.