Hybrid Artificial Bee Colony and Improved Simulated Annealing for the Capacitated Vehicle Routing Problem

Farhanna Mar'i; Hafidz Ubaidillah; Wayan Firdaus Mahmudy; Ahmad Afif Supianto

doi:10.17977/um018v5i22022p109-121

Hybrid Artificial Bee Colony and Improved Simulated Annealing for the Capacitated Vehicle Routing Problem

Farhanna Mar'i, Hafidz Ubaidillah, Wayan Firdaus Mahmudy, Ahmad Afif Supianto

Abstract

Capacitated Vehicle Routing Problem (CVRP) is a type of NP-Hard combinatorial problem that requires a high computational process. In the case of CVRP, there is an additional constraint in the form of a capacity limit owned by the vehicle, so the complexity of the problem from CVRP is to find the optimum route pattern for minimizing travel costs which are also adjusted to customer demand and vehicle capacity for distribution. One method of solving CVRP can be done by implementing a meta-heuristic algorithm. In this research, two meta-heuristic algorithms have been hybridized: Artificial Bee Colony (ABC) with Improved Simulated Annealing (SA). The motivation behind this idea is to complete the excess and the lack of two algorithms when exploring and exploiting the optimal solution. Hybridization is done by running the ABC algorithm, and then the output solution at this stage will be used as an initial solution for the Improved SA method. Parameter testing for both methods has been carried out to produce an optimal solution. In this study, the test was carried out using the CVRP benchmark dataset generated by Augerat (Dataset 1) and the recent CVRP dataset from Uchoa (Dataset 2). The result shows that hybridizing the ABC algorithm and Improved SA could provide a better solution than the basic ABC without hybridization.

Full Text:

PDF

References

A. Islam, Y. Gajpal, and T. Y. Elmekkawy, “Hybrid particle swarm optimization algorithm for solving the clustered vehicle routing problem,” Appl. Soft Comput., vol. 110, p. 107655, 2021.

B. Yao, Q. Yan, M. Zhang, and Y. Yang, “Improved artificial bee colony algorithm for vehicle routing problem with time windows,” PLoS ONE 12 e0181275, pp. 1–18, 2017.

D. G. Rossit, D. Vigo, and F. Tohm, “Visual Attractiveness in Routing Problems : a Review,” Comput. Oper. Res., vol. 103, pp. 13–34, 2019.

R. Y. Pratama and W. F. Mahmudy, “Optimization Of Vehicle Routing Problem With Time Window ( Vrptw ) For Food Product Distribution Using Genetics Algorithm,” J. Inf. Technol. Comput. Sci., vol. 2, no. 2, pp. 77–84, 2017.

K. Leungsubthawee and S. Saranwong, “Multiple Depot Vehicle Routing Problems on Clustering Algorithms,” J. Math., pp. 205–216, 2018.

C. Koc and G. Laporte, “Vehicle Routing with Backhauls : Review and Research Perspectives,” Comput. Oper. Res., vol. 91, pp. 79–91, 2018.

F. Mar’i, W. F. Mahmudy, and P. B. Santoso, “An Improved Simulated Annealing for The Capacitated Vehicle Routing Problem (CVRP),” J. Ilm. Kursor, vol. 9, no. 3, pp. 119–128, 2018.

H. Awad, R. Elshaer, A. Abdelmo, and G. Nawara, “An Effective Genetic Algorithm for Capacitated Vehicle Routing Problem,” in Proceedings of the International Conference on Industrial Engineering and Operations Management, 2018, pp. 374–384.

C. Pornsing, “a Particle Swarm Optimization for the vehicle routing problem,” University of Rhode Island, 2014.

A. Rahmi, W. F. Mahmudy, and S. Anam, “A Crossover in Simulated Annealing for Population Initialization of Genetic Algorithm to Optimize the Distribution Cost,” J. Telecommun. Electron. Comput. Eng., vol. 9, no. 2–8, pp. 177–182, 2017.

P. Lu, L. Ye, Y. Zhao, B. Dai, M. Pei, and Y. Tang, “Review of meta-heuristic algorithms for wind power prediction : Methodologies , applications and challenges,” Appl. Energy, vol. 301, no. April, p. 117446, 2021.

V. Ganesan et al., “Quantum inspired meta-heuristic approach for optimization of genetic algorithm,” Comput. Electr. Eng., vol. 94, no. July, p. 107356, 2021.

D. Połap and M. Woźniak, “Meta-heuristic as manager in federated learning approaches for image processing purposes,” Appl. Soft Comput., vol. 113, p. 107872, 2021.

A. M. Altabeeb, A. M. Mohsen, and A. Ghallab, “An improved hybrid firefly algorithm for capacitated vehicle routing problem,” Appl. Soft Comput. J., vol. 84, p. 105728, 2019.

W. Y. Szeto, Y. Wu, and S. C. Ho, “An artificial bee colony algorithm for the capacitated vehicle routing problem,” Eur. J. Oper. Res., vol. 215, no. 1, pp. 126–135, 2011.

H. Ding, H. Cheng, and X. Shan, “Modified Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem,” in 2nd International Conference on Advances in Management Science and Engineering, 2018, pp. 197–201.

B. Akay, D. Karaboga, B. Gorkemli, and E. Kaya, “A survey on the Artificial Bee Colony algorithm variants for binary, integer and mixed integer programming problems,” Appl. Soft Comput., vol. 106, p. 107351, 2021.

A. A. Kondratenko, M. Bergström, M. Suominen, and P. Kujala, “An Artificial Bee Colony optimization-based approach for sizing and composition of Arctic offshore drilling support fleets considering cost- efficiency,” Sh. Technol. Res., pp. 1–24, 2022.

R. Szczepanski, K. Erwinski, M. Tejer, A. Bereit, and T. Tarczewski, “Optimal scheduling for palletizing task using robotic arm and artificial bee colony algorithm,” Eng. Appl. Artif. Intell., vol. 113, no. February, p. 104976, 2022.

L. Yang, A. Zhu, J. Shao, and T. Chi, “A knowledge-informed and pareto-based artificial bee colony optimization algorithm for multi-objective land-use allocation,” ISPRS Int. J. Geo-Information, vol. 7, no. 2, 2018.

B. K. Dedeturk and B. Akay, “Spam filtering using a logistic regression model trained by an artificial bee colony algorithm,” Appl. Soft Comput. J., vol. 91, p. 106229, 2020.

Y. Boudouaoui, H. Habbi, C. Ozturk, and D. Karaboga, “Solving differential equations with artificial bee colony programming,” Soft Comput., vol. 24, no. 23, pp. 17991–18007, 2020.

Y. Deng, H. Xu, and J. Wu, “Optimization of blockchain investment portfolio under artificial bee colony algorithm,” J. Comput. Appl. Math., vol. 385, p. 113199, 2021.

Ş. Öztürk, R. Ahmad, and N. Akhtar, “Variants of Artificial Bee Colony Algorithm and its application in Medical Image Processing,” Appl. Soft Comput., vol. 97, pp. 1–50, 2020.

L. Ge and E. Ji, “An improved artificial bee colony algorithm and its application in machine learning,” J. Phys. Conf. Ser., vol. 1650, no. 3, 2020.

F. Ye, D. Zhang, Y. Whar Si, X. Zeng, and T. T. Nguyen, “A hybrid algorithm for a Vehicle Routing Problem with Realistic Constraints,” Inf. Sci. (Ny)., vol. 394, no. 95, pp. 167–182, 2017.

X. Huang, X. Zeng, R. Han, and X. Wang, “An enhanced hybridized artificial bee colony algorithm for optimization problems,” IAES Int. J. Artif. Intell., vol. 8, no. 1, pp. 87–94, 2019.

Y. Wang, “Improving artificial bee colony and particle swarm optimization to solve TSP problem,” Proc. - 2018 Int. Conf. Virtual Real. Intell. Syst. ICVRIS 2018, pp. 179–182, 2018.

B. Rambabu, A. V. Reddy, and S. Janakiraman, “Hybrid Artificial Bee Colony and Monarchy Butterfly Optimization Algorithm ( HABC-MBOA ) -based cluster head selection for WSNs,” J. King Saud Univ. - Comput. Inf. Sci., 2019.

F. Barani and H. Nezamabadi-Pour, “BQIABC: A new Quantum-Inspired Artificial Bee Colony Algorithm for Binary Optimization Problems,” J. AI Data Min., vol. 6, no. 1, pp. 133–143, 2018.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecch, “Optimization by Simulated Annealing,” Science (80-. )., vol. 220, no. 4598, pp. 671–680, 2007.

E. J. Kusuma, I. Pantiawati, and S. Handayani, “Melanoma Classification based on Simulated Annealing Optimization Neural Network,” Knowl. Eng. Data Sci., vol. 4, no. 2, pp. 97–104, 2021.

H. Lv, X. Chen, and X. Zeng, “Optimization of micromixer with Cantor fractal baffle based on simulated annealing algorithm,” Chaos, Solitons and Fractals, vol. 148, p. 111048, 2021.

J. Adler and E. N. Ribak, “Simulated annealing in application to telescope phasing,” Phys. A Stat. Mech. its Appl., vol. 572, p. 125900, 2021.

X. Liu et al., “Simulated annealing for optimization of graphs and sequences,” Neurocomputing, vol. 465, pp. 310–324, 2021.

S. Dhagat and S. E. Jujjavarapu, “Simulated annealing and artificial neural network as optimization tools to enhance yields of bioemulsifier and exopolysaccharides by thermophilic Brevibacillus borstelensis,” J. Environ. Chem. Eng., vol. 9, no. 4, p. 105499, 2021.

S. Peng, D. Rippel, M. Becker, and H. Szczerbicka, “Scheduling of offshore wind farm installation using simulated annealing,” IFAC-PapersOnLine, vol. 54, no. 1, pp. 325–330, 2021.

G. Çetin and A. Keçebaş, “Optimization of thermodynamic performance with simulated annealing algorithm: A geothermal power plant,” Renew. Energy, vol. 172, pp. 968–982, 2021.

F. Mar’i, W. F. Mahmudy, and P. B. Santoso, “Hybrid Particle Swarm Optimization and Simulated Annealing for Capacitated Vehicle Routing Problem,” Proc. 2019 4th Int. Conf. Sustain. Inf. Eng. Technol. SIET 2019, pp. 66–71, 2019.

İ. İlhan, “An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem,” Swarm Evol. Comput., vol. 64, no. March, p. 100911, 2021.

B. Morales-Castañeda, D. Zaldívar, E. Cuevas, O. Maciel-Castillo, I. Aranguren, and F. Fausto, “An improved Simulated Annealing algorithm based on ancient metallurgy techniques,” Appl. Soft Comput. J., vol. 84, p. 105761, 2019.

T. Yuxin, Y. Hairong, G. Hang, S. Yuying, and L. Gang, “Application of SVR optimized by Modified Simulated Annealing (MSA-SVR) air conditioning load prediction model,” J. Ind. Inf. Integr., vol. 15, no. January, pp. 247–251, 2018.

P. Augerat et al., “Computational Results With a Branch-and-Cut Code for the Capacitated Vehicle Routing Problem,” no. May 2014, pp. 1–24, 1995.

E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, and A. Subramanian, “New benchmark instances for the Capacitated Vehicle Routing Problem,” Eur. J. Oper. Res., vol. 257, no. 3, pp. 845–858, 2017.

F. Wang, H. Zhang, K. Li, Z. Lin, J. Yang, and X. L. Shen, “A hybrid particle swarm optimization algorithm using adaptive learning strategy,” Inf. Sci. (Ny)., vol. 436–437, pp. 162–177, 2018.

DOI: http://dx.doi.org/10.17977/um018v5i22022p109-121