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

Szczepański, Emilian

doi:10.5604/01.3001.0012.5879

Artykuł - szczegóły

Tytuł artykułu

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

Autorzy

Szczepański Emilian

Wybrane pełne teksty z tego czasopisma

http://slw.wat.edu.pl

Identyfikatory

DOI

10.5604/01.3001.0012.5879

Warianty tytułu

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

Języki publikacji

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.

The aim of the article is to present themethodfordetermining routes of distribution vehicles and to assess the impact of the method used to determine the pathbetween 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 forpathfindingwere presented. The articles compare the vehicle routing problem solution from the point of view of the approach used to determine paths.

Słowa kluczowe

system dystrybucji ładunków algorytmy genetyczne gwiazda modelowanie matematyczne problem trasowania pojazdów

cargo distribution system genetic algorithms A-Star mathematical modeling vehicle routing problem

Wydawca

Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego

Czasopismo

Systemy Logistyczne Wojsk

Rocznik

2018

Tom

Vol. 48, no. 1

Strony

300--312

Opis fizyczny

Bibliogr. 23 poz., rys., tab., wz.

Twórcy

autor

Szczepański Emilian

eszczepanski@wt.pw.edu.pl

Politechnika Warszawska, Wydział Transportu

Bibliografia

1. 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.
2. 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.
3. Chabrier, A. (2006). Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research, 33(10), 2972-2990.
4. 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.
5. 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.
6. Fridell, E., Belhaj, M., Wolf, C., & Jerksjö, M. (2011). Calculation of external costs for freight transport. Transportation planning and technology, 34(5), 413-432.
7. 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.
8. Glover, F. (1995). Tabu search fundamentals and uses. Boulder: Graduate School of Business, University of Colorado.
9. 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.
10. 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.
11. Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints. Column generation, 6730, 33-65.
12. Jacyna, M., & Merkisz, J. (2014). Proecological approach to modelling traffic organization in national transport system. Archives of Transport, 30(2), 31-41.
13. 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.
14. 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.
15. Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416.
16. 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).
17. Michalewicz, Z. (2003). Algorytmy genetyczne+ struktury danych=programy ewolucyjne. Warszawa: Wydawnictwa Naukowo-Techniczne.
18. Pichpibul, T., & Kawtummachai, R. (2013). A heuristic approach based on clarke-wright algorithm for open vehicle routing problem. The Scientific World Journal, 2013.
19. 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.
20. Sysło, M. M., Deo, N., & Kowalik, J. S. (1999). Algorytmy optymalizacji dyskretnej: z programami w języku Pascal. Warszawa:Wydawnictwo Naukowe PWN.
21. 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.
22. Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1), 487-512.
23. 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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).

Artykuł jest efektem pracw ramach grantu dziekańskiego dla młodych naukowców (2018/2019 )oraz pracy statutowej realizowanych na Wydziale Transportu Politechniki Warszawskiej

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-6a3bd36d-e449-4f7f-829c-997455086561