Optimisation of vehicle routing problem with time windows using Harris Hawks optimiser
DOI:
https://doi.org/10.15282/jmes.16.3.2022.08.0717Keywords:
Vehicle Routing Problem, Time Windows, Harris Hawk OptimiserAbstract
Vehicle routing problem is one of the combinatorial optimisation problems that have gained attraction for studies because of its complexity and significant impact to service providers and passengers. Vehicle routing problem with time windows (VRPTW) is a variant where vehicles need to visit the predetermined stop points within the given time frame. This problem has been widely studied and optimised using different methods. Since the performance of algorithms in different problems is dissimilar, the study to optimise the VRPTW is ongoing. This paper presents a VRPTW study for a public transportation network in Kuantan and Pekan districts, located in East Pahang, Malaysia. There were 52 stop points to be visited within two hours. The main objective of the study is to minimise the number of vehicles to be assigned for the routing problem subjected to the given time windows. The problem was optimised using a new algorithm known as Harris Hawks Optimiser (HHO). To the best of authors’ knowledge, this is the first attempt to build HHO algorithm for VRPTW problem. Computational experiment indicated that the HHO came up with the best average fitness compared with other comparison algorithms in this study including Artificial Bee Colony (ABC), Particle Swarm Optimisation (PSO), Moth Flame Optimiser (MFO), and Whale Optimisation Algorithm (WOA). The optimisation results also indicated that all the stop points can be visited within the given time frames by using three vehicles.
References
R. Eshtehadi, E. Demir, and Y. Huang, “Solving the vehicle routing problem with multi-compartment vehicles for city logistics,” Comput. Oper. Res., vol. 115, p. 104859, 202, doi: https://doi.org/10.1016/j.cor.2019.104859.
Y. Li, H. Soleimani, and M. Zohal, “An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives,” J. Clean. Prod., vol. 227, pp. 1161–1172, 2019.
W. Cao and W. Yang, “A survey of vehicle routing problem,” MATEC Web Conf., vol. 100, pp. 1–6, 2017.
P. Sitek, J. Wikarek, K. Rutczyńska-Wdowiak, G. Bocewicz, and Z. Banaszak, “Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: A modified hybrid approach,” Neurocomputing, vol. 423, pp. 670–678, 2021.
L. C. Yeun, W. a N. R. Ismail, K. Omar, and M. Zirour, “Vehicle routing problem : Models and solutions,” J. Qual. Meas. Anal., vol. 4, no. 1, pp. 205–218, 2008.
S. P. Anbuudayasankar, K. Ganesh, and S. Mohapatra, Models for practical routing problems in logistics: Design and practices, vol. 9783319050. 2014.
F. Meng, Y. Ding, W. Li, and R. Guo, “Customer-oriented vehicle routing problem with environment consideration: Two-phase optimization approach and Heuristic solution,” Math. Probl. Eng., vol. 2019, 2019.
G. Laporte, P. Toth, and D. Vigo, “Vehicle routing: historical perspective and recent contributions,” EURO J. Transp. Logist., vol. 2, no. 1–2, pp. 1–4, 2013.
S. Zhang, W. Zhang, Y. Gajpal, and S. S. Appadoo, “Ant colony algorithm for routing alternate fuel vehicles in multi-depot vehicle routing problem,” in Decision Science in Action: Theory and Applications of Modern Decision Analytic Optimisation, K. Deep, M. Jain, and S. Salhi, Eds. Singapore: Springer Singapore, 2019, pp. 251–260.
A. Soeanu, S. Ray, J. Berger, A. Boukhtouta, and M. Debbabi, “Multi-depot vehicle routing problem with risk mitigation: Model and solution algorithm,” Expert Syst. Appl., vol. 145, p. 113099, 2020.
R. Eshtehadi, E. Demir, and Y. Huang, “Solving the vehicle routing problem with multi-compartment vehicles for city logistics,” Comput. Oper. Res., vol. 115, p. 104859, 2020.
Y. Li, H. Soleimani, and M. Zohal, “An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives,” J. Clean. Prod., vol. 227, pp. 1161–1172, 2019.
V. Leggieri and M. Haouari, “Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems,” Eur. J. Oper. Res., vol. 263, no. 3, pp. 755–767, 2017.
S. C. H. Leung, Z. Zhang, D. Zhang, X. Hua, and M. K. Lim, “A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints,” Eur. J. Oper. Res., vol. 225, no. 2, pp. 199–210, 2013.
Y. Shi, Y. Zhou, T. Boudouh, and O. Grunder, “A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup–delivery and time window,” Eng. Appl. Artif. Intell., vol. 95, p. 103901, 2020.
R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Comput. Ind. Eng., vol. 140, p. 106242, 2020.
A. Dixit, A. Mishra, and A. Shukla, “Vehicle Routing Problem with Time Windows Using Meta-Heuristic Algorithms: A Survey,” in Harmony Search and Nature Inspired Optimization Algorithms, 2019, pp. 539–546.
N. A. El-Sherbeny, “Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods,” J. King Saud Univ. - Sci., vol. 22, no. 3, pp. 123–131, 2010.
F. Massen, “Optimization approaches for vehicle routing problems with black box feasibility,” p. 310, 2013.
G. D. Konstantakopoulos, S. P. Gayialis, E. P. Kechagias, G. A. Papadopoulos, and I. P. Tatsiopoulos, “A Multiobjective Large Neighborhood Search Metaheuristic for the Vehicle Routing Problem with Time Windows,” Algorithms, vol. 13, no. 10, 2020.
R. Zhu and Y. Zhai, “Research on the application of VRP theory in logistics transportation,” MATEC Web Conf., vol. 100, 2017.
Darin Beigie, “Solving optimization problems with spreadsheets,” Math. Teach., vol. 111, no. 1, p. 26, 2017.
J. S. Arora, “Discrete variable optimum design concepts and methods,” Introd. to Optim. Des., pp. 619–641, 2012.
W. Roetzel, X. Luo, and D. Chen, Optimal design of heat exchanger networks, no. 3. Elsevier Inc., 2020.
M. S. Shunmugam and M. Kanthababu, Advances in Simulation, Product Design and Development. Springer Nature Singapore, 2018.
N. Azi, M. Gendreau, and J. Y. Potvin, “An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles,” Eur. J. Oper. Res., vol. 202, no. 3, pp. 756–763, 2010.
J. Yu, C. H. Kim, and S. B. Rhee, “The comparison of lately proposed Harris Hawks optimization and Jaya optimization in solving directional overcurrent relays coordination problem,” Complexity, vol. 2020, no. iii, 2020.
A. A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja, and H. Chen, “Harris hawks optimization: Algorithm and applications,” Futur. Gener. Comput. Syst., vol. 97, pp. 849–872, 2019.
A. Abbasi, B. Firouzi, and P. Sendur, “On the application of Harris hawks optimization (HHO) algorithm to the design of microchannel heat sinks,” Eng. Comput., no. mm, 2019.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Universiti Malaysia Pahang Publishing
This work is licensed under a Creative Commons Attribution 4.0 International License.
