Zastosowanie algorytmu przeszukiwania rozproszonego do problemu marszrutyzacji z ograniczeniem pojemności środków transportu

• Autorzy: Głuszek A. , Rudziński F.

Warianty tytułu

EN

Application of Scatter Search to Capacitated Vehicle Routing Problem

• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł prezentuje wyniki zastosowania algorytmu przeszukiwania rozproszonego do problemu marszrutyzacji z ograniczeniem pojemności pojazdów. Przeszukiwanie rozproszone zaliczane jest do obszaru algorytmów ewolucyjnych i znajduje wiele zastosowań w optymalizacji problemów o charakterze zarówno ciągłym jak i dyskretnym. Problem marszrutyzacji stanowi zagadnienie należące do zadań optymalizacji kombinatorycznej, a w szerszym zakresie – do badań operacyjnych. Ze względu na jego duże znaczenie praktyczne, zwłaszcza w obszarze zarządzania transportem, wciąż trwają intensywne badania w zakresie poszukiwania nowych i udoskonalania już istniejących algorytmów, umożliwiających jego efektywne rozwiązywanie. W rozdziale pierwszym niniejszego artykułu przedstawiono formalnie zadanie marszrutyzacji z ograniczeniem pojemności pojazdów. Rozdział drugi prezentuje zasadę działania algorytmu przeszukiwania rozproszonego. Rozdział trzeci przedstawia zestaw problemów testowych wykorzystywanych w niniejszej pracy oraz wyniki przeprowadzonych eksperymentów numerycznych. Rezultaty działania algorytmu przeszukiwania rozproszonego porównano z wynikami uzyskanymi przy zastosowaniu dwóch innych metod ewolucyjnych (algorytm genetyczny i strategia ewolucyjna) oraz zaawansowanego dwufazowego algorytmu heurystycznego, wykorzystującego zmodyfikowany algorytm wspinaczkowy.

EN

The paper presents application of scatter search to capacitated vehicle routing problem. Scatter search belongs to the area of evolutionary computations and it has numerous applications in continuous and discrete optimization problems. Vehicle routing problem is an important combinatorial optimization task that is related to operations research. It has great practical relevance, especially in the fields of transport management, distribution and logistics. Development of the algorithms for efficient solving of the vehicle routing problem is still very intensive. In the first section of the paper capacitated vehicle routing problem is formally presented. Next section describes in outline the scatter search algorithm. The third section presents a set of test examples, used in this study and the results of performed experiments. Proposed approach is also compared with two alternative evolutionary algorithms (genetic algorithm and evolutionary strategy) and advanced two-phase heuristic method, based on modified hill climbing algorithm.

Słowa kluczowe

PL

przeszukiwanie rozproszone; algorytm genetyczny; strategia ewolucyjna; problem marszrutyzacji

EN

scatter search; genetic algorithm; evolution strategy; vehicle routing problem

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2015
• Tom: nr 4
• Strony: 3417--3425, CD2
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Głuszek A.

• Politechnika Świętokrzyska, Wydział Elektrotechniki, Automatyki i Informatyki, Al. 1000-lecia P.P. 7, 25-314 Kielce. Tel: [phone]

autor

Rudziński F.

• Politechnika Świętokrzyska, Wydział Elektrotechniki, Automatyki i Informatyki, Al. 1000-lecia P.P. 7, 25-314 Kielce. Tel: [phone]

Bibliografia

• 1. Alba E., Dorronsoro B., Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms. Lecture Notes in Computer Science 3004, Springer, Berlin, Heidelberg, str. 11-20, 2004.
• 2. Augerat P., Belenguer J.M., Benavent E., Corberan A., Naddef D., Rinaldi G., Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem. Research Report 949-M, Universite Joseph Fourier, Grenoble, France.
• 3. Burke E.K., Bykov Y., The Late Acceptance Hill-Climbing Heuristic. Technical Report CSM-192, Department of Computing Science and Mathematics, University of Stirling, Stirling, Scotland, 2012.
• 4. Dantzig G.B., Ramser J. H., The Truck Dispatching Problem. Management Science, Vol. 6, str. 80-91, 1959.
• 5. Glover F., Laguna M., Fundamentals of Scatter Search and Path Relinking. Control and Cybernetics, Vol. 29, Nr 3, str. 653-684, 2000.
• 6. Glover F., A Template for Scatter Search and Path Relinking. Lecture Notes in Computer Science 1363, Springer, Berlin, Heidelberg, str. 1-51, 1998.
• 7. Gorzałczany M.B., On some idea of a neuro-fuzzy controller. Information Sciences, nr 120, str. 69-87, 1999.
• 8. Gorzałczany M.B., Piasta Z., Neuro-fuzzy approach versus rough-set inspired methodology for intelligent decision support. Information Sciences, nr 120, str. 45-68, 1999.
• 9. Marti R., Laguna M., Glover F., Principles of scatter search. European Journal of Operational Research, Tom 169, North-Holland, str. 359-372, 2006.
• 10. Talbi E., Metaheuristics: from design to implementation. John Wiley & Sons, Hoboken, NJ, 2009.
• 11. Wagner S. i in., Architecture and Design of the HeuristicLab Optimization Environment. W: Advanced Methods and Applications in Computational Intelligence, Topics in Intelligent Engineering and Informatics Series, Springer, str. 197-261, 2014.
• 12. http://dev.heuristiclab.com/
• 13. http://neo.lcc.uma.es/vrp/
• 14. http://www.optaplanner.org/

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę