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

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.

---

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.