А HYBRID APPROACH FOR SOLVING THE VEHICLE ROUTING PROBLEM WITH ADDITIONAL CONSTRAINTS
DOI:
https://doi.org/10.26906/SUNZ.2023.1.031Keywords:
graph, route, vehicle routing problem, time windows, carrying capacity, greedy algorithm, branch-and-bound algorithm, conservation algorithm, genetic algorithm, crossover, mutationAbstract
Topicality. In the modern world, there is a need to use automated systems in the transport logistics, in order to saving resources. When constructing a vehicle route, there are problems of searching the optimal route, taking into account additional constraints, such as the carrying capacity of vehicles or time windows of customers. In this regard, there is a need to improve the existing means of solving the vehicle routing problem. The goal of this work is to create a hybrid method of solving the vehicle routing problem with additional constraints. The object of research is the process of searching optimal routes with load capacity limitation and taking into account time windows. The subject of research is algorithms of solving vehicle routing problems with additional constraints. Results. In this paper, the features of the application of a hybrid approach based on the use of genetic and classical algorithms to solve the vehicle routing problem with additional constraints, are considered. The results of experimental studies demonstrating the advantages and disadvantages of each of the considered algorithms for solving the given problem are presented. Conclusions. The proposed hybrid approach based on the genetic algorithm and the modified greedy algorithm provides the highest accuracy and speed.Downloads
References
Aksen D., Zyurt Z., Aras N. (2006), “Open vehicle routing problem with driver nodes and time deadlines”, Journal of the Operational Research Society, Vol. 58(9), pp. 106-114, doi: https://doi.org/10.1057/palgrave.jors.2602249
Braekers K., Ramaekers K., Nieuwenhuese I. (2016), “The vehicle routing problem: State of the art classification and review”, Computers & Industrial Engineering, Vol. 99, pp. 300-313, doi: https://doi.org/10.1016/j.cie.2015.12.007
Caramia M., Guerriero F. (2010), “A heuristic approach for the truck and trailer routing problem”, Journal of the Operational Research Society, Vol. 61(7), pp. 1168-1180, doi: https://doi.org/10.1057/jors.2009.59
Clarke G., Wright J.W. (1964), “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, Vol. 12, No. 4, pp. 568-581, doi: https://doi.org/10.1287/opre.12.4.568
Theurich F., Fischer A., Scheithauer G. (2021), “A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs”, EURO Journal on Computational Optimization, Vol. 9, pp. 29-40, doi: https://doi.org/10.1016/j.ejco.2020.100003
Кораблев Н.М., Иващенко Г.С., Кушнарев М.В. (2012) “Агентно-ориентированный подход на основе искусственных имунных систем для решения задачи коммивояжера”, Біоніка інтелекту, №2(79), С. 33-37, available at: http://openarchive.nure.ua/handle/document/572
Alvarez A., Munari P. (2017), “An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen”, Computers & Operations Research, Vol. 83, pp. 1-12, doi: https://doi.org/10.1016/j.cor.2017.02.001
Vidal T., Crainic T.G., Gendreau M., Prins C. (2013), “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows”, Computers & Operations Research, Vol. 40(1), pp. 475-489, doi: https://doi.org/10.1016/j.cor.2012.07.018
Mohammed M.A., Ghani M.K., Hamed R.I., Mostafa S.A., Ahmad M.S., Ibrahim D.A. (2017), “Solving vehicle routing problem by using improved genetic algorithm for optimal solution”, Journal of Computational Science, Vol. 21, pp. 255-262, doi: https://doi.org/10.1016/j.jocs.2017.04.003
Bean J. C. (1994), “Genetic algorithms and random keys for sequencing and optimization”, ORSA Journal on Computing, Vol. 6, No. 2, pp. 154-160, doi: https://doi.org/10.1287/ijoc.6.2.154
Caceres-Cruz J., Arias P., Guimarans D., Riera D., Juin A. (2015), “Rich vehicle routing problem: Survey”, ACM Computing Surveys (CSUR), Vol. 47(2), No. 32, pp. 1-28, doi: https://doi.org/10.1145/2666003
Alba E., Dorronsoro B. (2004), “Solving the vehicle routing problem by using cellular genetic algorithms”, European Conference on Evolutionary Computation in Combinatorial Optimization, Vol. 3004, pp. 11-20, doi: https://doi.org/10.1007/978-3-540-24652-7_2
Cheng C., Wang K. (2009), “Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm”, Expert Systems Applications, Vol. 36(4), pp. 7758-7763, doi: https://doi.org/10.1016/j.eswa.2008.09.001
