New version of the BBS method and its usage for determining and scheduling vehicle routes

Andrzej Wolfenburg

doi:10.5604/08669546.1146991

Authors

Andrzej Wolfenburg Institute of Logistics and Warehousing, Poznan, Poland Author

DOI:

https://doi.org/10.5604/08669546.1146991

Keywords:

vehicle routing, scheduling vehicle routes, BBS method

Abstract

The work presents a method of the vehicle routing and scheduling using the modified Branch and Bound Simulation method for vehicles simultaneously carrying loads from multiple orders. Limitations concerning vehicle loads and time windows in pickup and delivery points are taken into consideration. The developed algorithm appoints the shortest, the fastest and the cheapest routes with a certain known accuracy. A modification of the BBS method is described A sample of result using Google API is shown.

References

Cordeau J.F. A branch-and-cut algorithm for the dial-a-ride problem, Oper Res 54, str 573–586, Informs, 2006.

Cudziło M., Zarządzanie zleceniami dostaw w rozproszonej strukturze magazynowej, Gospodarka Materiałowa i Logistyka, 2011 nr 2, pp. 12-17, 2011.

Fabri A,, Recht P, On dynamic pickup and delivery vehicle routing with several time windows and waiting times. Transport Res B-Meth 40, pp. 335–350, 2006.

Fagerholt K,, Christiansen M, A travelling salesman problem with allocation, time window and precedence constraints – an application to ship scheduling. Int Trans Oper Res 7, pp. 231–244, 2006.

Ghiani G, Guerriero F., Laporte G., Musmanno R., Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. Eur J Oper Res 151, pp. 1–11, 2003.

Hajdul M., Komodalność, czyli efektywna organizacja procesów transportowych, Logistyka, 2009 nr 2, pp. 26- 27, 2009.

Hajdul M., Cudziło M., Metody i narzędzia wspierające wielkoobszarową integrację procesów logistycznych z wykorzystaniem nowoczesnych technologii, Nowoczesne rozwiązania technologiczne w logistyce, pod red.: Golińska P., Stajniak M., Wydawnictwo Politechniki Poznańskiej, pp. 69-81, 2010.

Hernandez-Perez H., Salazar-Gonzalez J.J., A branch-and cut algorithm for the traveling salesman problem with pickup and delivery. Discrete Appl Math 145, pp.126–139, 2004.

Lau H,C,, Liang Z, Pickup and delivery with time windows : Algorithms and test case generation. Int J Artif Intell Tools 11, pp. 455–472, 2004.

Lu Q., Dessouky M.M., An exact algorithm for the multiple vehicle pickup and delivery problem. Transport Sci 38, pp. 503–514, 2004.

Parragh, S.N., Doermer, K.F., Hartl, R.F., A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations. Journal fuer Betiebswirtchaft 58, pp. 81-117, 2008, Wien.

Ropke S., Cordeau J.F., Laporte G. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49, pp. 258–272, 2007.

Szyszka G., Innowacyjna logistyka, Fakty Magazyn Gospodarczy, 2(68), str. 12-13, 2014.

Wolfenburg, A., Zastosowanie Symulacji Dyskretnej do Rozwiązania Zadań Optymalizacyjnych, Prace Naukowe Instytutu Organizacji i Zarządzania Politechniki Wrocławskiej, Nr 83, Seria Studia i Materiały 25, pp. 201-213, 2007, Wrocław.

Wolfenburg, A, Metoda BBS i jej wykorzystanie do optymalnego harmonogramowania prac na maszynach, monografia: Modele symulacyjne i gry menedżerskie we wspomaganiu decyzji w dydaktyce, Oficyna Wydawnicza Politechniki Wrocławskiej, pp. 111-118, 2010, Wrocław.

Wolfenburg, A, Optymalne kierowanie ruchem pociągów w obszarze sieci kolejowej, Wydawnictwa PWSZ w Gorzowie Wlkp., 2011, Gorzów Wlkp.

Xu H., Chen Z.L., Rajagopal S., Arunapuram S., Solving a practical pickup and delivery problem. Transport Science 37, pp. 347-364, 2004.

Wolfenburg A., Wyznaczanie i harmonogramowanie tras pojazdów przy wykorzystaniu metody BBS, Logistyka 4/2014, CD nr 2, Poznań 2014.