An Improved Whale Optimization Algorithm for Vehicle Routing Problem with Time Windows
Abstract
The vehicle routing problem with time windows (VRPTW) is a pivotal problem in logistics operation management which attempts to establish routes for vehicles to deliver goods to customers. The objective of VRPTW is to find the optimal set of routes for a fleet of vehicles in order to serve a given set of customers within time window constraints. As the VRPTW is known to be NP-hard combinatorial problem, it is hard to be solved in reasonable computational time. Therefore, this paper proposes the modification of the whale optimization algorithm with local search to solve the VRPTW. The local search comprised 2-Operator and single insertion for solution improvement. Furthermore, the 2-Operator is used after the exploration phase and single insertion in the exploitation phase. The computational experiments were applied to Solomon’s instance that included small to large size problems. The experiment results show that the average gap of the total distance between the Best Known Solution (BKS) and the proposed solutions is within 5.82%. In addition, the best solution was found 29 out of 56 instances that is better than the PSO at 1.09%. This shows that this proposed provides a minimum value and outperforms other metaheuristics approaches.
Keywords: Whale Optimization Algorithm; Vehicle Routing Problem; Time Constraints
[1] G.B. Dantzig and J.H. Ramser, The Truck Dispatching Problem, Management Science, 1959, 6(1), 80-91.
[2] C. Liu and J. Yu, Multiple depots vehicle routing based on the ant colony with the genetic algorithm, Journal of Industrial Engineering and Management, 2013, 6(4), 1013-1026.
[3] P. Francis and K. Smilowitz, Modeling techniques for periodic vehicle routing problems, Transportation Research Part B: Methodological, 2006, 40(10), 872-884.
[4] J.M. Belenguer, M.C. Martinez, and E. Mota, A lower bound for the split delivery vehicle routing problem, Operations Research, 2000, 48(5), 801-810.
[5] S. Liu, A hybrid population heuristic for the heterogeneous vehicle routing problems, Transportation Research Part E: Logistics and Transportation Review, 2013, 54, 67-78.
[6] J.F. Bard, G. Kontoravdis, and G. Yu, A branch-and-cut procedure for the vehicle routing problem with time windows, Transportation Science, 2002, 36(2), 250-269.
[7] M. Desrochers, J. Desrosiers, and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations research, 1992, 40(2), 342-354.
[8] N. Azi, M. Gendreau, and J.Y. Potvin, An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, European Journal of Operational Research, 2010, 202(3), 756-763.
[9] É. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.Y. Potvin, A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation Science, 1997, 31(2), 170-186.
[10] S. Kirkpatrick, C.D. Gelatt Jr., and M.P. Vecchi, Optimization by simulated annealing, Science, 1983, 220, 671-680.
[11] R.A. Russell and W.C. Chiang, Scatter search for the vehicle routing problem with time windows, European Journal of Operational Research, 2006, 169(2), 606-622.
[12] Y.J. Gong, J. Zhang, O. Liu, R.Z. Huang, H.S.H. Chung, and Y.H. Shi, Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach, IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2011, 42(2), 254-267.
[13] K. Kantawong and S. Pravesjit, An enhanced ABC algorithm to solve the vehicle routing problem with time windows, ECTI Transactions on Computer and Information Technology, 2020, 14(1), 46-52.
[14] B. Yu, Z.Z. Yang, and B.Z. Yao, A hybrid algorithm for vehicle routing problem with time windows, Expert Systems with Applications, 2011, 38(1), 435-441.
[15] Y. Shen, M. Liu, J. Yang, Y. Shi, and M. Middendorf, A hybrid swarm intelligence algorithm for vehicle routing problem with time windows, IEEE Access, 2020, 8, 93882-93893.
[16] S. Mirjalili and A. Lewis, The whale optimization algorithm, Advances in Engineering Software, 2016, 95, 51-67.
[17] D. B. Prakash and C. Lakshminarayana, Optimal siting of capacitors in radial distribution network using whale optimization algorithm, Alexandria Engineering Journal, 2017, 56(4), 499-509.
[18] Z. Yan, J. Sha, B. Liu, W. Tian, and J. Lu, An ameliorative whale optimization algorithm for multi-objective optimal allocation of water resources in Handan, China, Water, 2018, 10(1), 87.
[19] M.A. Basset, G. Manogaran, D.E. Shahat, and S. Mirjalili, A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem, Future Generation Computer Systems, 2018, 85, 129-145.
[20] S. Khalilpourazari, S.H.R. Pasandideh, and A. Ghodratnama, Robust possibilistic programming for multi-item EOQ model with defective supply batches: Whale optimization and water cycle algorithms, Neural Computing and Applications, 2019, 31(10), 6587-6614.
[21] S.K. Dewi and D.M. Utama, A new hybrid whale optimization algorithm for green vehicle routing problem, Systems Science and Control Engineering, 2021, 9(1), 61-72.
[22] J.J. Asl, M.E.A.B. Seghier, S. Ohadi, and P. van Gelder, Efficient method using Whale Optimization Algorithm for reliability-based design optimization of labyrinth spillway, Applied Soft Computing, 2021, 101, 107036.
[23] J. Zhang, L. Hong, and Q. Liu, An improved whale optimization algorithm for the traveling salesman problem, Symmetry, 2021, 13(1), 48.
[24] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 1987, 35(2), 254-265.
[25] N. Kohl, J. Desrosiers, O.B. Madsen, M.M. Solomon, and F. Soumis, 2-Path cuts for the vehicle routing problem with time windows, Transportation Science, 1999, 33(1), 101-116.
[26] W. Cook and J.L. Rich, A parallel cutting-plane algorithm for the vehicle routing problem with time windows, Technical report TR99-04, Department of Computational and Applied Mathematics, Rice University, Houston, Texas, USA. 1999.
[27] B. Kallehauge, J. Larsen, and O.B. Madsen, Lagrangean duality applied on vehicle routing with time windows-experimental results, Internal report IMM-REP-2000-8 Technical University of Denmark, Lyngby, Denmark. 2001.
[28] S. Irnich and D. Villeneuve, The shortest-path problem with resource constraints and k-cycle elimination for k≥ 3, INFORMS Journal on Computing, 2006, 18(3), 391-406.
[29] A. Chabrier, Vehicle routing problem with elementary shortest path based column generation, Computers and Operations Research, 2006, 33(10), 2972-2990.
[30] J. Larsen, Parallelization of the vehicle routing problem with time windows, Thesis, Technical University of Denmark, Denmark. 1999.
[31] E. Danna and C.L. Pape, Accelerating branch-and-price with local search: A case study on the vehicle routing problem with time windows, Column Generation, 2003, 30-130.
[32] S. Jung and B.R. Moon, A hybrid genetic algorithm for the vehicle routing problem with time windows, Genetic and Evoluation Computation Conference (GECCO), Proceeding, 2002, 1309-1316.
[33] G.B. Alvarenga, G.R. Mateus, and G.D. Tomi, A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows, Computers and Operations Research, 2007, 34(6), 1561-1584.
[34] J. Berger, M. Salois, and R. Begin, A hybrid genetic algorithm for the vehicle routing problem with time windows, Conference of the canadian society for computational studies of intelligence, Proceeding, 1998, 114-127.
[35] H.C.B. de Oliveira and G.C. Vasconcelos, A hybrid search method for the vehicle routing problem with time windows, Annals of Operations Research, 2010, 180(1), 125-144.
[36] T. Vidal, T.G. Crainic, M. Gendreau, and C. Prins, Time-window relaxations in vehicle routing heuristics, Journal of Heuristics, 2015, 21(3), 329-358.
[37] Y. Rochat and É.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1995, 1(1), 147-167.
[38] P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, International conference on principles and practice of constraint programming, Proceeding, 1998, 417-431.
[39] J.F. Cordeau, G. Laporte, and A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 2001, 52(8), 928-936.
[40] K.C. Tan, Y.H. Chew, and L.H. Lee, A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows, Computational Optimization and Applications, 2006, 34(1), 115-151.
DOI: 10.14416/j.ind.tech.2022.04.001
Refbacks
- There are currently no refbacks.
