Hybrydowy system heurystyk przeszukiwania lokalnego dla symetrycznego TSP

• Autorzy: Tomasz Szatkiewicz , Filip Szafraniec

Warianty tytułu

Hybrid System of Two Local Search Heuristics for TSP

• Języki publikacji: PL

Abstrakty

W artykule dokonano szczegółowej analizy mocnych i słabych stron heurystyk przeszukiwania lokalnego dla problemu komiwojażera. Analiza ta pozwoliła na opracowanie dwóch nowych heurystyk przeszukiwania lokalnego - LLS i CLS, które szczegółowo opisano.(abstrakt oryginalny)

EN

We described twno brand new local search heuristics for travelling salesman problem. We show that the LLS and CLS local search heuristics joint in one hybrid system can solve TSP better than known 2-opt, 3-opt standar heuristics.(original abstract)

Słowa kluczowe

PL

Instrumenty hybrydowe; Inteligentne Systemy Transportowe; Metody heurystyczne

EN

Hybrid instruments; Intelligent Transport Systems (ITS); Heuristics methods

• Czasopismo: Logistyka
• Rocznik: 2015
• Numer: nr 4, CD 2
• Strony: 5914-5923

Twórcy

autor

Tomasz Szatkiewicz

• Polityka Koszalińska

autor

Filip Szafraniec

• Polityka Koszalińska

Bibliografia

• 1. Aarts E., Lenstra J.K. Local search in combinatorial optimization. John Wiley & Sons, Inc, 1997.
• 2. Johnson, D.S. (1990). "Local Optimization and the Traveling Salesman Problem." Proceedings of the 17th Colloquium on Automate Languages and Programming, Lecture Notes in Computer Science 443, Berlin: Springer, 446-461.
• 3. WEIQI LI, Dynamics of Local Search Trajectory in Traveling Salesman Problem, Journal of Heuristics, 11: 507-524, 2005
• 4. D.S. Johnson., L.A. McGeoch., E.E. Rothberg. AsymptoticExperimental Analysis for the Held-Karp Traveling Salesman Bound, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 341-350
• 5. Bonomi, E., J.L. Lutton. (1984). The N-city Traveling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm. SIAM 1984 Review 26, 551-568.
• 6. Gutin G., Punen A. P. The Traveling Salesman Problem and Its Variations, Kluwer, 2002
• 7. Helsgaun K. An effective implementation of the Lin-Kernighan travelling salesman heuristic. European Joural of Operational Research, 2000, vol. 126, 106-130
• 8. Punnen, A.P., Margot, F., Kabadi, S.N.: TSP heuristics: domination analysis and complexity. Algorithmica 35(2003), 111-127 (2003)
• 9. Lin S., Kernighan B. An effective heuristic algoithm or the travelling -salesman problem. Operations Research, 1973, vol. 21, 498-516.
• 10. Reinelt G. TSPLIB - A travelling salesman problem library. ORSA Journal of Computing, 1991, vol. 3-4, 376-385.