A monarch butterfly optimization for the dynamic vehicle routing problem. (English) Zbl 1461.90011
Summary: The dynamic vehicle routing problem (DVRP) is a variant of the Vehicle Routing Problem (VRP) in which customers appear dynamically. The objective is to determine a set of routes that minimizes the total travel distance. In this paper, we propose a monarch butterfly optimization (MBO) algorithm to solve DVRPs, utilizing a greedy strategy. Both migration operation and the butterfly adjusting operator only accept the offspring of butterfly individuals that have better fitness than their parents. To improve performance, a later perturbation procedure is implemented, to maintain a balance between global diversification and local intensification. The computational results indicate that the proposed technique outperforms the existing approaches in the literature for average performance by at least 9.38%. In addition, 12 new best solutions were found. This shows that this proposed technique consistently produces high-quality solutions and outperforms other published heuristics for the DVRP.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
monarch butterfly optimization; dynamic vehicle routing problem; greedy strategy; local searchReferences:
| [1] | Ismail, Z.; Solving the vehicle routing problem with stochastic demands via hybrid genetic algorithm-tabu search; J. Math. Stat.: 2008; Volume 4 ,161. · Zbl 1183.90057 |
| [2] | Oliveira, S.; de Souza, S.R.; Silva, M.A.L.; A solution of dynamic vehicle routing problem with time window via ant colony system metaheuristic; Proceedings of the 10th Brazilian Symposium on Neural Networks, (SBRN ‘08): ; ,21-26. |
| [3] | Belfiore, P.C.; Yoshizaki, H.T.Y.; Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in brazil; Eur. J. Oper. Res.: 2009; Volume 199 ,750-758. · Zbl 1176.90098 |
| [4] | Chen, Z.L.; Xu, H.; Dynamic column generation for dynamic vehicle routing with time windows; Transp. Sci.: 2006; Volume 40 ,74-88. |
| [5] | De Armas, J.; Melián-Batista, B.; Moreno-Pérez, J.A.; Restricted Dynamic Heterogeneous Fleet Vehicle Routing Problem with Time Windows; Advances in Computational Intelligence, Part II, Proceedings of the 12th International Work-Conference on Artificial Neural Networks (IWANN 2013), Puerto de la Cruz, Tenerife, Spain, 12-14 June 2013: Berlin/Heidelberg, Germany 2013; ,36-45. |
| [6] | Wang, G.G.; Zhao, X.; Deb, S.; A novel monarch butterfly optimization with greedy strategy and self-adaptive; Proceedings of the 2015 Second International Conference on Soft Computing and Machine Intelligence (ISCMI): ; ,45-50. |
| [7] | Ghetas, M.; Yong, C.H.; Sumari, P.; Harmony-based monarch butterfly optimization algorithm; Proceedings of the 2015 IEEE International Conference on Control System, Computing and Engineering (ICCSCE): ; ,156-161. |
| [8] | Feng, Y.; Yang, J.; Wu, C.; Lu, M.; Zhao, X.J.; Solving 0-1 knapsack problems by chaotic monarch butterfly optimization algorithm with gaussian mutation; Memet. Comput.: 2016; ,1-16. |
| [9] | Wang, G.G.; Hao, G.S.; Cheng, S.; Qin, Q.; A discrete monarch butterfly optimization for chinese TSP problem; Advances in Swarm Intelligence, Part I; Proceedings of the 7th International Conference (ICSI 2016), Bali, Indonesia, 25-30 June 2016: Cham, Switzerland 2016; ,165-173. |
| [10] | Wang, G.-G.; Deb, S.; Cui, Z.; Monarch butterfly optimization; Neural Comput. Appl.: 2015; ,1-20. |
| [11] | Dorigo, M.; Maniezzo, V.; Colorni, A.; Ant system: Optimization by a colony of cooperating agents; IEEE Trans. Syst. Man Cybern. Part B Cybern.: 1996; Volume 26 ,29-41. |
| [12] | Simon, D.; Biogeography-based optimization; IEEE Trans. Evol. Comput.: 2008; Volume 12 ,702-713. |
| [13] | Storn, R.; Price, K.; Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces; J. Glob. Optim.: 1997; Volume 11 ,341-359. · Zbl 0888.90135 |
| [14] | Kilby, P.; Prosser, P.; Shaw, P.; ; Dynamic VRPS: A Study of Scenarios: Glasgow, UK 1998; . |
| [15] | Montemanni, R.; Gambardella, L.M.; Rizzoli, A.E.; Donati, A.V.; Ant colony system for a dynamic vehicle routing problem; J. Comb. Optim.: 2005; Volume 10 ,327-343. · Zbl 1093.90094 |
| [16] | Khouadjia, M.R.; Sarasola, B.; Alba, E.; Jourdan, L.; Talbi, E.-G.; A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests; Appl. Soft Comput.: 2012; Volume 12 ,1426-1439. |
| [17] | Yang, D.; He, X.; Song, L.; Huang, H.; Du, H.; A hybrid large neighborhood search for dynamic vehicle routing problem with time deadline; Combinatorial Optimization and Applications, Proceedings of the 9th International Conference (COCOA 2015), Houston, TX, USA, 18-20 December 2015: Cham, Switzerland 2015; ,307-318. · Zbl 1478.90114 |
| [18] | Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A.L.; A review of dynamic vehicle routing problems; Eur. J. Oper. Res.: 2013; Volume 225 ,1-11. · Zbl 1292.90203 |
| [19] | Bekta¸S, T.; Repoussis, P.P.; Tarantilis, C.D.; Dynamic vehicle routing problems; Vehicle Routing: Problems, Methods, and Applications: Philadelphia, PA, USA 2014; ,299-347. |
| [20] | Psaraftis, H.N.; Wen, M.; Kontovas, C.A.; Dynamic vehicle routing problems: Three decades and counting; Networks: 2016; Volume 67 ,3-31. |
| [21] | Elhassania, M.; Jaouad, B.; Ahmed, E.A.; Solving the dynamic vehicle routing problem using genetic algorithms; Proceedings of the 2nd IEEE International Conference on Logistics Operations Management: ; ,62-69. |
| [22] | Euchi, J.; Yassine, A.; Chabchoub, H.; The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach; Swarm Evol. Comput.: 2015; Volume 21 ,41-53. |
| [23] | Mańdziuk, J.; Żychowski, A.; A memetic approach to vehicle routing problem with dynamic requests; Appl. Soft Comput.: 2016; Volume 48 ,522-534. |
| [24] | Gendreau, M.; Guertin, F.; Potvin, J.-Y.; Taillard, E.; Parallel tabu search for real-time vehicle routing and dispatching; Transp. Sci.: 1999; Volume 33 ,381-390. · Zbl 0958.90051 |
| [25] | Bent, R.W.; Van Hentenryck, P.; Scenario-based planning for partially dynamic vehicle routing with stochastic customers; Oper. Res.: 2004; Volume 52 ,977-987. · Zbl 1165.90600 |
| [26] | Taillard, É.; Parallel iterative search methods for vehicle routing problems; Networks: 1993; Volume 23 ,661-673. · Zbl 0804.90045 |
| [27] | Christofides, N.; Beasley, J.E.; The period routing problem; Networks: 1984; Volume 14 ,237-256. · Zbl 0541.90073 |
| [28] | Fisher, M.; Vehicle routing; Handbooks in Operations Research and Management Science: Amsterdam, The Netherlands 1995; Volume Volume 8 ,1-33. · Zbl 0870.90058 |
| [29] | Hanshar, F.T.; Ombuki-Berman, B.M.; Dynamic vehicle routing using genetic algorithms; Appl. Intell.: 2007; Volume 27 ,89-99. · Zbl 1189.90208 |
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.
