×

Using metaheuristics on the multi-depot vehicle routing problem with modified optimization criterion. (English) Zbl 1461.90016

Summary: This article deals with the modified Multi-Depot Vehicle Routing Problem (MDVRP). The modification consists of altering the optimization criterion. The optimization criterion of the standard MDVRP is to minimize the total sum of routes of all vehicles, whereas the criterion of modified MDVRP (M-MDVRP) is to minimize the longest route of all vehicles, i.e., the time to conduct the routing operation is as short as possible. For this problem, a metaheuristic algorithm – based on the Ant Colony Optimization (ACO) theory and developed by the author for solving the classic MDVRP instances – has been modified and adapted for M-MDVRP. In this article, an additional deterministic optimization process which further enhances the original ACO algorithm has been proposed. For evaluation of results, Cordeau’s benchmark instances are used.

MSC:

90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming

Software:

METSlib; VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dantzig, G.B.; Ramser, J.H.; The truck dispatching problem; Manag. Sci.: 1959; Volume 6 ,80-91. · Zbl 0995.90560
[2] Carlsson, J.; Ge, D.; Subramaniam, A.; Wu, A.; Ye, Y.; Solving min-max multi-depot vehicle routing problem; Lect. Glob. Optim.: 2009; Volume 55 ,31-46. · Zbl 1177.90035
[3] Narasimha, K.V.; Kivelevitch, E.; Sharma, B.; Kumar, M.; An ant colony optimization technique for solving min-max multi-depot vehicle routing problem; Swarm Evolut. Comput.: 2013; Volume 13 ,63-73.
[4] Ho, W.; Ho, G.T.S.; Ji, P.; Lau, H.C.W.; A hybrid genetic algorithm for the multi-depot vehicle routing problem; Eng. Appl. Artif. Intell.: 2008; Volume 21 ,548-557.
[5] Sharma, N.; Monika, M.A.; Literature Survey on Multi-Depot Vehicle Routing Problem; Int. J. Res. Dev.: 2015; Volume 3 ,1752-1757.
[6] Montoya-Torres, J.R.; Franco, J.L.; Isaza, S.N.; Jiménez, H.F.; Herazo-Padilla, N.; A literature review of the vehicle routing problem with multiple depots; Comput. Ind. Eng.: 2015; Volume 79 ,115-129.
[7] Braekers, K.; Ramaekers, K.; Van Nieuwenhuyse, I.; The vehicle routing problem: State of the art classification and review; Comput. Ind. Eng.: 2016; Volume 99 ,300-313.
[8] Gillett, B.E.; Johnson, J.G.; Multi-terminal vehicle-dispatch algorithm; Omega: 1976; Volume 4 ,711-718.
[9] Chao, M.I.; Golden, B.L.; Wasil, E.; A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions; Am. J. Math. Manag. Sci.: 1993; Volume 13 ,371-406. · Zbl 0808.90061
[10] Renaud, J.; Laporte, G.; Boctor, F.F.; A tabu search heuristic for the multi-depot vehicle routing problem; Comput. Oper. Res.: 1996; Volume 23 ,229-235. · Zbl 0855.90055
[11] Escobar, J.W.; Linfati, R.; Toth, P.; Baldoquin, M.G.; A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem; J. Heuristics: 2014; Volume 20 ,483-509.
[12] Soto, M.; Sevaux, M.; Rossi, A.; Reinholzc, A.; Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem; Comput. Ind. Eng.: 2017; Volume 107 ,211-222.
[13] Wu, T.H.; Low, C.; Bai, J.W.; Heuristic solutions to multi-depot location routing problems; Comput. Oper. Res.: 2002; Volume 29 ,1393-1415. · Zbl 0994.90019
[14] Lim, A.; Zhu, W.; A fast and effective insertion algorithm for multi-depot vehicle routing problem and a new simulated annealing approach; Advances in Artificial Intelligence, Lecture Notes in Computer Science: Berlin/Heidelberg, Germany 2006; Volume Volume 4031 ,282-291.
[15] Ombuki-Berman, B.; Hanshar, F.T.; Using Genetic Algorithms for Multi-depot Vehicle Routing; Bio-Inspired Algorithms for the Vehicle Routing Problem: Berlin/Heidelberg, Germany 2009; Volume Volume 161 ,77-99. · Zbl 1189.90208
[16] Seidgar, H.; Abedi, M.; Tadayoni, S.; Rezaeian, J.; An efficient hybrid of genetic and simulated annealing algorithms for multi server vehicle routing problem with multi entry; Int. J. Ind. Syst. Eng.: 2016; Volume 24 ,333-360.
[17] Karakatic, S.; Podgorelec, V.; A survey of genetic algorithms for solving multi-depot vehicle routing problem; Appl. Soft Comput.: 2015; Volume 27 ,519-532.
[18] Yu, B.; Yang, Z.Z.; Xie, J.X.; A parallel improved ant colony optimization for multi-depot vehicle routing problem; J. Oper. Res. Soc.: 2010; Volume 62 ,183-188.
[19] Yao, B.; Hu, P.; Zhang, M.; Tian, X.; Improved Ant Colony Optimization for Seafood Product Delivery Routing Problem; Promet-Traffic Transp.: 2014; Volume 26 ,1-10.
[20] Tang, Y.; An Improved Ant Colony Optimization for Multi-Depot Vehicle Routing Problem. International; J. Eng. Technol.: 2016; Volume 8 ,385-388.
[21] Gao, J.; Automobile chain maintenance parts delivery problem using an improved ant colony algorithm; Adv. Mech. Eng.: 2016; Volume 8 ,1-13.
[22] Ma, Y.; Han, J.; Kang, K.; Yan, F.; An Improved ACO for the Multi-depot Vehicle Routing Problem with Time Windows; Proceedings of the Tenth International Conference on Management Science and Engineering Management: Singapore 2017; Volume Volume 502 .
[23] Ting, C.J.; Chen, C.H.; Combination of multiple ant colony system and simulated annealing for the multi-depot vehicle routing problem with time windows; Transp. Res. Rec. J. Transp. Res. Board: 2008; Volume 2089 ,85-92.
[24] Vidal, T.; Crainic, T.G.; Gendreau, M.; Lahrichi, N.; Rei, W.; A Hybrid Genetic Algorithm for Multi-Depot and Periodic Vehicle Routing Problems; Oper. Res.: 2012; Volume 60 ,611-624. · Zbl 1260.90058
[25] De Oliveira, F.B.; Enayatifar, R.; Sadaei, H.J.; Guimarães, F.G.; Potvin, J.Y.; A cooperative coevolutionary algorithm for the Multi-Depot Vehicle Routing Problem; Expert Syst. Appl.: 2016; Volume 43 ,117-130.
[26] Wang, X.; Golden, B.; Wasil, E.; The min-max multi-depot vehicle routing problem: Heuristics and computational results; J. Oper. Res. Soc.: 2015; Volume 66 ,1430-1441.
[27] Wang, X.; Golden, B.; Wasil, E.; Zhang, R.; The min-max split delivery multi-depot vehicle routing problem with minimum service time requirement; Comput. Oper. Res.: 2016; Volume 71 ,110-126. · Zbl 1349.90140
[28] Benning, L.; Why Is the Traveling Salesman Problem NP Complete? Quora.com; 2014; .
[29] Cordeau, J.F.; Gendreau, M.; Laporte, G.; A tabu search heuristic for periodic and multi-depot vehicle routing problems; Networks: 1997; Volume 30 ,105-119. · Zbl 0885.90037
[30] Cordeau, J.F.; Maischberger, M.; A parallel iterated tabu search heuristic for vehicle routing problems; Comput. Oper. Res.: 2012; Volume 39 ,2033-2050.
[31] University of Malaga, Spain; ; .
[32] Stodola, P.; Mazal, J.; Applying the Ant Colony Optimisation Algorithm to the Capacitated Multi-Depot Vehicle Routing Problem; Int. J. Bio-Inspir. Comput.: 2016; Volume 8 ,228-233.
[33] Stodola, P.; Mazal, J.; Tactical Decision Support System to Aid Commanders in their Decision-Making; Modelling and Simulation for Autonomous Systems: Cham, Switzerland 2016; ,396-406.
[34] Blaha, M.; Silinger, K.; Application support for topographical-geodetic issues for tactical and technical control of artillery fire; Int. J. Circuits Syst. Signal Proc.: 2018; Volume 12 ,48-57.
[35] Hodicky, J.; Standards to support military autonomous system life cycle; Advances in Intelligent Systems and Computing: Cham, Switzerland 2018; Volume Volume 644 ,671-678.
[36] Rybansky, M.; Trafficability analysis through vegetation; Proceedings of the International Conference on Military Technologies: ; ,207-210.
[37] Drozd, J.; Analysis Results of the Military Observer Training System; Econ. Manag.: 2016; Volume 2016 ,24-31.
[38] Farlik, J.; Casar, J.; Stary, V.; Simplification of missile effective coverage zone in air defence simulations; Proceedings of the International Conference on Military Technologies: ; ,733-737.
[39] Hasilova, K.; Vališ, D.; Non-parametric estimates of the first hitting time of Li-ion battery; Measurement: 2018; Volume 113 ,82-91.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.