Zastosowanie algorytmów ewolucyjnych w problemie marszrutyzacji z oknami czasowymi

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

Warianty tytułu

EN

Application of evolutionary algorithms in vehicle routing problem with time windows

• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł prezentuje wyniki zastosowania wybranych algorytmów ewolucyjnych do problemu marszrutyzacji z oknami czasowymi. 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 oknami czasowymi. Rozdział drugi prezentuje krótko algorytmy ewolucyjne zastosowane w rozważanym problemie planowania optymalnego zestawu tras dla zespołu pojazdów. Proponowane podejście obejmowało wykorzystanie klasycznego algorytmu genetycznego, strategii ewolucyjnej i algorytmu przeszukiwania rozproszonego. Rozdział trzeci przedstawia zestaw problemów testowych wykorzystywanych w niniejszej pracy oraz wyniki przeprowadzonych eksperymentów numerycznych. Rezultaty działania algorytmów ewolucyjnych porównano dodatkowo z wynikami uzyskanymi przy zastosowaniu zaawansowanego dwufazowego algorytmu heurystycznego, wykorzystującego zmodyfikowany algorytm wspinaczkowy.

EN

The paper presents application of evolutionary algorithms to capacitated vehicle routing problem with time windows. Vehicle routing problem is an important combinatorial optimization task and it 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 with time windows is formally presented. Next section describes in outline evolutionary algorithms applied to considered problem of designing the optimal set of routes for team of vehicles. In our approach we use genetic algorithm, evolution strategy and scatter search algorithm. The third section presents a set of test examples, used in this work and the results of performed numerical experiments. The comparison of results obtained by evolutionary algorithms and advanced two-phase heuristic method, based on modified hill climbing algorithm, is also provided.

Słowa kluczowe

PL

algorytm ewolucyjny; marszrutyzacja; okno czasowe; zarządzanie transportem

EN

evolutionary algorithm; vehicle routing; time window; transport management

• Wydawca: Instytut Naukowo-Wydawniczy "TTS" Sp. z o.o
• Czasopismo: TTS Technika Transportu Szynowego
• Rocznik: 2015
• Tom: R. 22, nr 12
• Strony: 557--563, CD
• Opis fizyczny: Bibliogr. 18 poz., tab., rys.

Twórcy

autor

Głuszek A.

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

autor

Rudziński F.

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

Bibliografia

• 1. Beyer H.-G., The Theory of Evolution Strategies. Springer, Berlin, 2001.
• 2. Burke E.K., Bykov Y., The Late Acceptance Hill-Climbing Heuristic. Technical Report CSM-192, Department of Computing Science and Mathematics, University of Stirling, 2012.
• 3. Cordeau J.-F., Desaulniers G., Desrosiers, J., Solomon, M.M., Soumis, F., VRP with Time Windows. W: Toth P. and Vigo D. (eds.), The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, vol. 9, Philadelphia, PA, str. 157-193, 2002.
• 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. Głuszek A., Rudziński F., Zastosowanie algorytmu przeszuki-wania rozproszonego do problemu marszrutyzacji z ograniczeniem pojemności środków transportu, Logistyka, str. 3417-3425, nr 4/2015.
• 7. Goldberg D.E., Algorytmy genetyczne i ich zastosowania. WNT, Warszawa, 1998.
• 8. Gorzałczany M.B., On some idea of a neuro-fuzzy controller. Information Sciences, nr 120, str. 69-87, 1999.
• 9. 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.
• 10. Marti R., Laguna M., Glover F., Principles of scatter search. European Journal of Operational Research, Tom 169, North-Holland, str. 359-372, 2006.
• 11. Talbi E., Metaheuristics: from design to implementation. John Wiley & Sons, Hoboken, NJ, 2009.
• 12. Potvin J.-Y. Bengio S., The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, Vol. 8, str.165-172, 1996.
• 13. Rutkowski L., Metody i techniki sztucznej inteligencji. PWN, Warszawa, 2005.
• 14. Schwefel H.-P.: Evolution and Optimum Seeking. J.Wiley&Sons, 1995.
• 15. Wagner S. i in., Architecture and Design of the HeuristicLab Optimization Environment. W: Advanced Methods and Applications in Computational Intelligence, Topics in Intelligent En-gineering and Informatics Series, Springer, str. 197-261, 2014.
• 16. http://dev.heuristiclab.com/
• 17. http://neo.lcc.uma.es/vrp/
• 18. http://www.optaplanner.org/