An Application of Whale Optimization Algorithm for Heterogeneous Vehicle Routing Problem with Soft Time Windows

Authors

  • Kittipong Malampong College of Industrial Technology, King Mongkut’s University of Technology North Bangkok
  • Kanokporn Sripathomswat College of Industrial Technology, King Mongkut’s University of Technology North Bangkok

Keywords:

vehicle routing problem, time windows, whale optimization algorithm, appropriate parameters, design of experiment

Abstract

The Whale Optimization Algorithm (WOA) is a metaheuristic algorithm inspired by the hunting behavior of whales, which involves searching for search for prey, encircling prey, and bubble-net attacking. The WOA consists of exploration phase and exploitation phase, aimed at achieving high-quality solutions. This study proposes the application of the WOA method, combined with Local Search (LS) method, named WOA-LS, to solve the Heterogeneous Vehicle Routing Problem with Time Windows (HVRPTW) under soft time window constraints. The problem-solving process includes adjusting the appropriate parameters of the WOA-LS method, such as the number of populations and the number of iterations, using Taguchi orthogonal arrays and analysis of variance (ANOVA). The parameter results are then used to solve the problem and compare the solutions with those obtained by the Tabu Search (TS) method for 56 benchmark problems with different customer locations. The results show that the WOA-LS method outperforms the TS method for 9 of the 56 problems and achieves the same results for 4 problems. The average solution quality of the WOA-LS method is 3.29% higher than that of the TS method, indicating that the proposed method is effective in solving the problem.

References

G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science., vol. 6, no. 1, pp. 80-91, 1959.

É. D. Taillard, “A heuristic column generation method for the heterogeneous fleet VRP,” RAIRO - Operations Research., vol. 33, pp. 1-14, 1999.

B. Golden, A. Assad, L. Levy and F. Gheysens, “The fleet size and mix vehicle routing problem,” Computers and Operations Research., vol. 11, pp. 49-66, 1984.

J. Ferland and P. Michelon, “The Vehicle Scheduling Problem with Multiple Vehicle Types,” Journal of the Operational Research Society., vol. 39, pp. 577-583, 1988.

F. Li, B. Golden and E. Wasil, “A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem,” Computers and Operations Research., vol. 34, no. 9, pp. 2734-2742, 2007.

J. Jiang, K. M. Ng, K. L. Poh, and K. M. Teo, “Vehicle routing problem with a heterogeneous fleet and time windows,” Expert Systems with Applications., vol. 41, no. 8, pp. 3748-3760, 2014.

M. M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problems With Time Window Constraints,” Operations Research., vol. 35, no. 2, pp. 254-265, 1987.

D. C. Paraskevopoulos, P. P. Repoussis, C. D. Tarantilis, G. Ioannou, and G. P. Prastacos, “A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows,” Journal of Heuristics., vol. 14, no. 5, pp. 425-455, 2008.

J. C. Molina, J. L. Salmeron and I. Eguia, “An ACS-based memetic algorithm for the heterogeneous vehicle routing problem with time windows,” Expert Systems with Applications., vol. 157, p. 113379, 2020.

J. J. De La Cruz, C. D. Paternina-Arboleda, V. Cantillo, and J. R. Montoya-Torres, “A two-pheromone trail ant colony system - Tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products,” Journal of Heuristics.,

vol. 19, no. 2, pp. 233-252, 2013.

S. Mirjalili and A. Lewis, “The Whale Optimization Algorithm,” Advances in Engineering Software., vol. 95, pp. 51-67, 2016.

S. K. Dewi and D. M. Utama, “A New Hybrid Whale Optimization Algorithm for Green Vehicle Routing Problem,” Systems Science and Control Engineering., vol. 9, pp. 61-72, 2021.

A. S. Elmousel, O. M. Khairy, O. M. Shehata, and E. I. Morgan, “A Novel Discrete Whale Optimization Algorithm for Solving the Capacitated Vehicle Routing Problem,” in 2021 7th International Conference on Mechatronics and Robotics Engineering (ICMRE), pp. 169-173, 2021.

J. Zhang, L. Hong, and Q. Liu, “An improved whale optimization algorithm for the traveling salesman problem,” Symmetry., vol. 13, no. 1, pp. 1-13, 2021.

S. Yodwangjai and K. Malampong, “An Improved Whale Optimization Algorithm for Vehicle Routing Problem with Time Windows,” The Journal of Industrial Technology., vol. 18, no. 1, pp. 104-122, 2022.

Downloads

Published

2023-06-19

How to Cite

[1]
K. Malampong and K. . Sripathomswat, “An Application of Whale Optimization Algorithm for Heterogeneous Vehicle Routing Problem with Soft Time Windows”, TJOR, vol. 11, no. 1, pp. 32–43, Jun. 2023.