Marszrutyzacja pojazdów dystrybucyjnych: metoda optymalizacji i ocena wpływu zastosowanego sposobu wyznaczania ścieżek w sieci transportowej

• Autorzy: Emilian Szczepański

Warianty tytułu

Vehicle Routing Problem: Optimization Method and Impact Assesment of Used Type of Pathfinding in the Transport Network

• Języki publikacji: PL

Abstrakty

Celem artykułu jest prezentacja metody wyznaczania tras pojazdów dystrybucyjnych i ocena wpływu zastosowanego sposobu wyznaczania ścieżek między węzłami w sieci transportowej. Realizacja celu wymagała sformułowania modelu matematycznego odwzorowującego system dystrybucji ładunków i zadania optymalizacyjnego. Przedstawiono metodę optymalizacyjną opartą o algorytmy genetyczne i modyfikację algorytmu A-star do wyznaczania ścieżek. W artykule porównano wyznaczanie marszrut dla pojazdów dystrybucyjnych z punktu widzenia zastosowanego podejścia do wyznaczania ścieżek. (abstrakt oryginalny)

EN

The aim of the article is to present the method for determining routes of distribution vehicles and to assess the impact of the method used to determine the path between nodes in the transport network. The implementation of the goal required the formulation of a mathematical model of the cargo distribution system and the optimization task. An optimization method based on genetic algorithms as well as modification of A-star for pathfinding were presented. The articles compare the vehicle routing problem solution from the point of view of the approach used to determine paths. (original abstract)

Słowa kluczowe

PL

Transport; Dystrybucja towarów; Algorytmy genetyczne; Modelowanie matematyczne; Optymalizacja; Zarządzanie flotą pojazdów

EN

Transport; Commodity distribution; Genetic algorithms; Mathematical modeling; Optimalization; Fleet management

• Czasopismo: Systemy Logistyczne Wojsk
• Rocznik: 2018
• Numer: z. 48
• Strony: 300--312

Twórcy

autor

Emilian Szczepański

• Politechnika Warszawska

Bibliografia

• Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations research, 52(5), 723-738.
• Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., & Juan, A. A. (2014). Rich Vehicle Routing Problem: Survey. ACM Computing Surveys (CSUR), 47(2), 32.
• Chabrier, A. (2006). Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research, 33(10), 2972-2990.
• Clarke, G. U., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.
• Corominas, A., García-Villoria, A., & Pastor, R. (2014). Improving parametric Clarke and Wright algorithms by means of iterative empirically adjusted greedy heuristics. SORT-Statistics and Operations Research Transactions, 38(1), 3-12.
• Fridell, E., Belhaj, M., Wolf, C., & Jerksjö, M. (2011). Calculation of external costs for freight transport. Transportation planning and technology, 34(5), 413-432.
• Fukasawa, R., Longo, H., Lysgaard, J., de Aragão, M. P., Reis, M., Uchoa, E., & Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming, 106(3), 491-511.
• Glover, F. (1995). Tabu search fundamentals and uses. Boulder: Graduate School of Business, University of Colorado.
• Goldberg, A. V., & Harrelson, C. (2005). Computing the shortest path: A search meets graph theory. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 156-165). Society for Industrial and Applied Mathematics.
• Gromicho, J., van Hoorn, J. J., Kok, A. L., & Schutten, J. M. J. (2012). Restricted dynamic programming: a flexible framework for solving realistic VRPs. Computers & Operations Research, 39(5), 902-909.
• Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints. Column generation, 6730, 33-65.
• Jacyna, M., & Merkisz, J. (2014). Proecological approach to modelling traffic organization in national transport system. Archives of Transport, 30(2), 31-41.
• Jacyna-Gołda, I, Izdebski, M., Szczepański, E., Gołda, P. (2018). The assessment of supply chain effectiveness. Archives of Transport, 45(1), 43-52.
• Jacyna-Gołda, I., Gołębiowski, P., Izdebski, M., Kłodawski, M., Jachimowski, R., & Szczepański, E. (2017). The evaluation of the sustainable transport system development with the scenario analyses procedure. Journal of Vibroengineering, 19(7), 5627-5638.
• Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416.
• Likhachev, M., Ferguson, D. I., Gordon, G. J., Stentz, A., & Thrun, S. (2005). Anytime Dynamic A: An Anytime, Replanning Algorithm. In ICAPS (pp. 262-271).
• Michalewicz, Z. (2003). Algorytmy genetyczne+ struktury danych=programy ewolucyjne. Warszawa: Wydawnictwa Naukowo-Techniczne.
• Pichpibul, T., & Kawtummachai, R. (2013). A heuristic approach based on clarke-wright algorithm for open vehicle routing problem. The Scientific World Journal, 2013.
• Prins, C., & Bouchenoua, S. (2005). A memetic algorithm solving the VRP, the CARP and general routing problems with nodes, edges and arcs. In Recent advances in memetic algorithms (pp. 65-85). New York: Springer Berlin Heidelberg.
• Sysło, M. M., Deo, N., & Kowalik, J. S. (1999). Algorytmy optymalizacji dyskretnej: z programami w języku Pascal. Warszawa:Wydawnictwo Naukowe PWN.
• Toth, P., & Vigo, D. (2001). Branch-and-bound algorithms for the capacitated VRP. In The vehicle routing problem (pp. 29-51). Society for Industrial and Applied Mathematics.
• Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1), 487-512.
• Wasiak, M., Jacyna, M., Lewczuk, K., & Szczepański, E. (2017). The method for evaluation of efficiency of the concept of centrally managed distribution in cities. Transport, 32(4), 348-357.

Identyfikatory

DOI

10.5604/01.3001.0012.5879