An Optimized Solution to Multi-Constraint Vehicle Routing Problem

Asif Nawaz; Muhammad Rizwan  Rashid Rana; Ghulam  Mustafa

doi:10.32350/icr.0202.04

Asif Nawaz University Institute of Information Technology, PMAS Arid Agriculture University Rawalpindi
Muhammad Rizwan Rashid Rana University Institute of Information Technology, PMAS Arid Agriculture University Rawalpindi
Ghulam Mustafa University Institute of Information Technology, PMAS Arid Agriculture University Rawalpindi

DOI: https://doi.org/10.32350/icr.0202.04

Keywords: Cuckoo Search (CS), customer, Particle Swarm Optimization (PSO), Vehicle Routing Problem (VRP)

Abstract

Abstract Views: 46

A Vehicle Routing Problem (VRP) is a Non-Polynomial Hard Category (NP-hard) problem in which the best set of routes for a convoy of vehicles is traversed to deliver goods or services to a known set of customers. In VRP, some constraints are added to improve performance. Some variations of VRP are Capacitated Vehicle Routing Problem (CVRP), Vehicle Routing Problem with Stochastic Demands (VRPSD), Vehicle Routing Problem with Time Window (VRPTW), Dynamic Vehicle Routing Problem (DVRP), and Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) where vehicle and routes have multiple constraints. Swarm intelligence is a well-used approach to solve VRPs. Moreover, different hybrid combinations of global and local optimization techniques are also used to optimize the said problem. In this research, an attempt is made to solve CVRP with VRPSD by using two different hybridized population-based approaches, that is, the Cuckoo Search Algorithm (CSA) and Particle Swarm Optimization (PSO). The experiments showed the accuracy of the improved CVRP that is superior to one obtained by using other classical versions and better than the results achieved by comparable algorithms. Besides, this improved algorithm can also improve search efficiency.

Downloads

Download data is not yet available.

References

H. Qin, X. Su, T. Ren, and Z. Luo, “A review on the electric vehicle routing problems: Variants and algorithms,” Front. Eng. Manag., vol. 8, pp. 3, pp. 370-389, May 2021, doi: https://doi.org/10.1007/s42524-021-0157-1

G. D. Konstantakopoulos, S. P. Gayialis, and E. P. Kechagias, “Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification,” Operat. Res., vol. 22, no. 3, pp. 2033-2062, Sep. 2022, doi: https://doi.org/10.1007/s12351-020-00600-7

F. Yin and Y. Zhao, “Distributionally robust equilibrious hybrid vehicle routing problem under twofold uncertainty,” Info. Sci., vol. 609, pp. 1239-1255, Sep. 2022, doi: https://doi.org/10.1016/j.ins.2022.07.140

A. M. Altabeeb, A. M. Mohsen, L. Abualigah, and A. Ghallab, “Solving capacitated vehicle routing problem using cooperative firefly algorithm,” Appl. Soft Comput., vol. 108, pp. 107403, Sep. 2021, doi:https://doi.org/10.1016/j.asoc.2 021.107403

F. Pace, A. Santilano, and A. Godio, “A review of geophysical modeling based on particle swarm optimization,” Surv. Geophy., vol. 42, no. 3, pp. 505-549, Apr. 2021, doi: https://doi.org/10.1007/s10712- 021-09638-4

H. Peng, Z. Zeng, C. Deng, and Z. Wu, “Multi-strategy serial cuckoo search algorithm for global optimization,” Knowledge-Based Syst., vol. 214, pp. 106729, Feb. 2021, doi: https://doi.org/10.1016/j.knosys .2020.106729

J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proc. ICNN'95 – Int. Conf. Neural Networks, 1995, pp. 1942-1948, doi: https://doi.org/10.1109/ICNN.1 995.488968

H. A. Alterazi, P. R. Kshirsagar, H. Manoharan, S. Selvarajan, and N. Alhebaishi, “Prevention of cyber security with the internet of things using particle swarm optimization,” Sensors, vol. 22, no. 16, pp. e6117, 2022, doi: https://doi.org/10.3390/s221661 17

F. P. Goksal, I. Karaoglan, and F. Altiparmak, “A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery,” Comput. Indust. Eng. vol. 65, no. 1, pp. 39-53, May 2013, doi: https://doi.org/10.1016/j.cie.201 2.01.005

A. M. Florio, D. Feillet, M. Poggi, and T. Vidal, “Vehicle routing with stochastic demands and partial reoptimization,” Transport. Sci., vol. 56, no. 5, pp. 1393- 1408, Feb. 2022, doi: https://doi.org/10.1287/trsc.2 022.1129

Y. Marinakis., G. Iordanidou, and M. Marinaki, “Particle swarm optimization for the vehicle routing problem with stochastic demands,” Appl Soft Comput., vol. 13, no. 4, pp. 1693-1704, Apr. 2013, doi: https://doi.org/10.1016/j.asoc .2013.01.007

P. Bertolazzi, G. Felici, P. Festa, G. Fiscon, and E. Weitschek, “Integer programming models for feature selection: New extensions and a randomized solution algorithm,” Eur. J. Operat. Res., vol. 250, no. 2, pp. 389-399, Apr. 2016, doi: https://doi.org/10.1016/j.ejor .2015.09.051

C. Liu, J. Wang, L. Zhou, and A. Rezaeipanah, “Solving the multi-objective problem of IoT service placement in fog computing using cuckoo search algorithm,” Neural Proc. Letters, vol. 54, no. 3, pp. 1823-1854, Jan. 2022, doi:

https://doi.org/10.1007/s11063-021-10708-2

V. Pillac, M. Gendreau, C. Guéret, and A. L. Medaglia, “A review of dynamic vehicle routing problems,” J.

Operat. Res., vol. 225, no. 1, pp.1-11, Feb. 2013, doi: https://doi.org/10.1016/j.ejor.2012.08.015

S. H. Huang, Y. H. Huang, C. A. Blazquez, and C. Y. Chen, “Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm,” Advanc. Eng. Informat., vol. 51, pp. e101536, Jan. 2022, doi: https://doi.org/10.1016/j.aei.2022.101536