A Genetic Algorithm for the Multi-Depot Vehicle Routing Problem

Abstract:

In this paper, we focus on the optimization of the system of the spare parts distribution for authorized garages in the Czech Republic. A spare parts market belongs to one of the key elements of the car industry. However, it has to adapt to still higher requirements on accuracy, speed and minimum error rate of the deliveries with keeping the costs at its minimum at the same time. The distribution of products from depots to customers is a practical and challenging problem in logistics that opens a significant space for application of software products.The design of optimal routes of vehicles from two depots can be formulated in combinatorial optimization as a multi-depot vehicle routing problem.The goal of a multi-depot vehicle routing problem is to design routes that start and end in one of the depots and visit a subset of customers in a specific sequence. Every customer has to be visited on one of the routes and the total costs for the delivery should be minimal.Vehicle routing problems belong to the class of NP-hard problems which means that there is no efficient algorithm for finding optimal solution available. To find a solution in an efficient way, we propose an approximate method based on a genetic algorithm.

• Periodical: Applied Mechanics and Materials (Volume 803)
• Pages: 69-75
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.803.69
• Online since: October 2015
• Authors: Alena Rybickova, Jakub Brodsky*, Adela Karaskova, Denisa Mockova
• Keywords: Genetic Algorithm, Logistics Systems, Multi-Depot Vehicle Routing Problem, Transport

References

[1] G.B. Dantzig, J.H. Ramser, The truck dispatching problem, In: Manage. Sci., Vol. 4 (1959) 80-91.

[2] G. Laporte, The vehicle routing problem: an overview of exact and approximate algorithms, In: Eur. J. Oper. Res., Vol. 59, No 3 (1992) 345-358.

DOI: 10.1016/0377-2217(92)90192-c

[3] J. Renaud, G. Laporte, F.F. Boctor, A Tabu search heuristic for the multidepot vehicle routing problem, In: Computers & Operations Research, Vol. 23, No. 3 (1996) 229-235.

DOI: 10.1016/0305-0548(95)o0026-p

[4] M. Filipec, D. Skrlec, S. Krajcar, Darwin meets computers: new approach to multiple depot capacitated vehicle routing problem. In: Proceedings of the 1997 IEEE international conference on systems, man, and cybernetics, Vol. 1 (1997) 421-426.

DOI: 10.1109/icsmc.1997.625786

[5] S.R. Thangiah, S. Salhi, Genetic clustering: An adaptive heuristic for the multidepot vehicle routing problem, In: Applied Artificial Intelligence, Vol. 15, No. 4 (2001) 361-383.

DOI: 10.1080/08839510151087293

[6] S.T. Bae, H. S. Hwang, G.S. Cho, M.J. Goan, Integrated GA-VRP solver for multi-depot system, In: Computers & Industrial Engineering, Vol. 53, No. 2 (2007) 233-240.

DOI: 10.1016/j.cie.2007.06.014

[7] T. Vidal, T.G. Crainic, M. Gendreau, N. Lahrichi, W. Rei, A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems In: CIRRELT, Vol. 34 (2010).

DOI: 10.1287/opre.1120.1048

[8] G. Jeon, H.R. Leep, J.Y. Shim, A vehicle routing problem solved by using hybrid genetic algorithm, In: Computers & Industrial Engineering, Vol. 53, No. 4 (2007) 680-692.

DOI: 10.1016/j.cie.2007.06.031

[9] C. Liu, J. Yu, Multiple depots vehicle routing based on the ant colony with the genetic algorithm, In: Journal of Industrial Engineering and Management, Vol. 6, No. 4 (2013) 1013-1026.

DOI: 10.3926/jiem.747

[10] C.Y. Liu, An improved adaptive genetic algorithm for the multi-depot vehicle routing problem with time windows, In: Journal of Networks, Vol. 8, No. 5 (2013) 1035-1042.

DOI: 10.4304/jnw.8.5.1035-1042

[11] A. Rybickova Analysis and optimization of supply of authorized garages of Peugeot and Citroen. Bachelor thesis, CTU in Prague, Faculty of Transportation Sciences, (2010).

[12] A. Rybickova, Use of genetic algorithms in discrete optimization problems. Master thesis, CTU in Prague, Faculty of Transportation Sciences, Prague, (2012).

[13] D. Mockova, A. Rybickova, Application of genetic algorithms to vehicle routing problem, In: Neural Network World, Vol. 1 (2014) 57-78.

[14] A. Rybickova, A. Karaskova, D. Mockova, Optimization of automotive spare parts distribution system using genetic algorithm. Paper presented at EngOpt 2014, Lisboa, Portugal, (2014).

DOI: 10.1109/scsp.2015.7181547

[15] F.B. Pereira, GVR: a New Genetic Representation for the Vehicle Routing Problem [online], Information on http: /fmachado. dei. uc. pt/wp-content/papercite-data/pdf/ptmc02a. pdf.