Hybrydowy system heurystyk przeszukiwania lokalnego dla symetrycznego TSP

• Autorzy: Szatkiewicz T. , Szafraniec F.

Warianty tytułu

EN

Hybrid system of two local search heuristics for TSP

• Języki publikacji: PL

Abstrakty

PL

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.

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.

Słowa kluczowe

PL

problem komiwojażera; heurystyki przeszukiwania lokalnego

EN

travelling salesperson problem; local search heurystics

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2015
• Tom: nr 4
• Strony: 5914--5923, CD 2
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Szatkiewicz T.

• Politechnika Koszalińska, Wydział Mechaniczny, 75-14 ul. Racławica 15-17 Koszalin

autor

Szafraniec F.

• Politechnika Koszalińska, Wydział Mechaniczny, 75-14 ul. Racławica 15-17 Koszalin

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.