Warianty tytułu
Application of Scatter Search to Capacitated Vehicle Routing Problem
Języki publikacji
Abstrakty
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.(abstrakt oryginalny)
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 taskthat 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 problemis 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 climbingalgorithm.(original abstract)
Twórcy
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 IntelligentEngineering 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/
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171567781