Modified Snow Avalanches Algorithm untuk Vehicle Routing Problem

Ayomi Sasmito, Jovanka Cathrynn, Michelle Tanaka, Maria Zefanya Sampe

Abstract


Metaheuristic algorithms are often used to tackle various optimization problems. In recent years, many new metaheuristic algorithms have been developed, such as the snow avalanches algorithm (SAA), which is inspired by natural snow avalanches. SAA consists of four avalanche phases: avalanches due to steep mountain slopes, human factors, local weather conditions, and it only has one control parameter. Like most metaheuristic algorithms, SAA has the potential to get trapped in local optima due to having only one control parameter. Therefore, this study presents a modification of SAA, called modified SAA (mSAA), which integrates the opposition-based learning (OBL) method with SAA to enhance the optimization process. To validate the performance of mSAA, tests were conducted on various OBL techniques to determine the best combination for solving complex and nonlinear problems, specifically the vehicle routing problem (VRP) on three types of VRP datasets (D01, D02, and D03 datasets). The results were then compared with the snow avalanches algorithm (SAA), hiking optimization algorithm (HOA), teaching learning-based optimization (TLBO), and grey wolf optimizer (GWO). Based on the average value, standard deviation, and best value, the mSAA method performed well and effectively in solving VRP using a combination of Quasi OBL and S_i=0.6+0.4 rand.


Keywords


Metaheuristic; Optimization; Opposition-based learning (OBL); Vehicle Routing Problem (VRP); Modified Snow Avalanches Algorithm (mSAA)

Full Text:

PDF

References


E. M. Toro O., A. H. Escobar Z., and M. Granada E., “Literature review on the vehicle routing problem in the green transportation context,” Luna Azul, no. 42, pp. 362–387, Dec. 2015, doi: 10.17151/luaz.2016.42.21.

G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Manage Sci, vol. 6, no. 1, pp. 80–91, 1959, doi: 10.1287/mnsc.6.1.80.

B. L. Golden, T. L. Magnanti, and H. Q. Nguyen, “Implementing vehicle routing algorithms,” Networks, vol. 7, no. 2, pp. 113–148, Jun. 1977, doi: https://doi.org/10.1002/net.3230070203.

G. Laporte and Y. Nobert, “Exact Algorithms for the Vehicle Routing Problem**The authors are grateful to the Canadian Natural Sciences and Engineering Research Council (grants A4747 and A5486) and to the Quebec Government (FCAC grant 80EQ04228) for their financial support.,” in North-Holland Mathematics Studies, vol. 132, S. Martello, G. Laporte, M. Minoux, and C. Ribeiro, Eds., North-Holland, 1987, pp. 147–184. doi: https://doi.org/10.1016/S0304-0208(08)73235-3.

J.-F. O. Cordeau, “A Branch-and-Cut Algorithm for the Dial-a-Ride Problem,” 2003.

A. Pessoa, M. P. de Aragão, and E. Uchoa, “Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems,” in The Vehicle Routing Problem: Latest Advances and New Challenges, B. Golden, S. Raghavan, and E. Wasil, Eds., Boston, MA: Springer US, 2008, pp. 297–325. doi: 10.1007/978-0-387-77778-8_14.

R. Baldacci, P. Toth, and D. Vigo, “Exact algorithms for routing problems under vehicle capacity constraints,” Ann Oper Res, vol. 175, no. 1, pp. 213–245, 2010, doi: 10.1007/s10479-009-0650-0.

M. Gendreau, A. Hertz, and G. Laporte, “New Insertion and Postoptimization Procedures for the Traveling Salesman Problem.” [Online]. Available: https://www.jstor.org/stable/171722

J. E. Beasley, “Route first—Cluster second methods for vehicle routing,” Omega (Westport), vol. 11, no. 4, pp. 403–408, 1983, doi: https://doi.org/10.1016/0305-0483(83)90033-6.

G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Oper Res, vol. 12, no. 4, pp. 568–581, Aug. 1964, doi: 10.1287/opre.12.4.568.

X.-S. Yang, “Chapter 1 - Introduction to Algorithms,” in Nature-Inspired Optimization Algorithms (Second Edition), X.-S. Yang, Ed., Academic Press, 2021, pp. 1–22. doi: https://doi.org/10.1016/B978-0-12-821986-7.00008-1.

N. Pholdee and S. Bureerat, “Comparative performance of meta-heuristic algorithms for mass minimisation of trusses with dynamic constraints,” Advances in Engineering Software, vol. 75, pp. 1–13, 2014, doi: https://doi.org/10.1016/j.advengsoft.2014.04.005.

S. Gupta and K. Deep, “A hybrid self-adaptive sine cosine algorithm with opposition based learning,” Expert Syst Appl, vol. 119, pp. 210–230, 2019, doi: https://doi.org/10.1016/j.eswa.2018.10.050.

M. Ventresca and H. R. Tizhoosh, “Simulated Annealing with Opposite Neighbors,” in 2007 IEEE Symposium on Foundations of Computational Intelligence, 2007, pp. 186–192. doi: 10.1109/FOCI.2007.372167.

M. Ventresca and H. R. Tizhoosh, “Opposite Transfer Functions and Backpropagation Through Time,” in 2007 IEEE Symposium on Foundations of Computational Intelligence, 2007, pp. 570–577. doi: 10.1109/FOCI.2007.371529.

H. R. Tizhoosh, “Opposition-Based Learning: A New Scheme for Machine Intelligence,” in International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06), 2005, pp. 695–701. doi: 10.1109/CIMCA.2005.1631345.

S. Mahdavi, S. Rahnamayan, and K. Deb, “Opposition based learning: A literature review,” Swarm Evol Comput, vol. 39, pp. 1–23, Apr. 2018, doi: 10.1016/j.swevo.2017.09.010.

K. Golalipour et al., “Snow avalanches algorithm (SAA): A new optimization algorithm for engineering applications,” Alexandria Engineering Journal, vol. 83, pp. 257–285, Nov. 2023, doi: 10.1016/j.aej.2023.10.029.

S. O. Oladejo, S. O. Ekwe, and S. Mirjalili, “The Hiking Optimization Algorithm: A novel human-based metaheuristic approach,” Knowl Based Syst, vol. 296, p. 111880, Jul. 2024, doi: 10.1016/j.knosys.2024.111880.

R. V Rao, V. J. Savsani, and D. P. Vakharia, “Teaching–learning-based optimization: A novel method for constrained mechanical design optimization problems,” Computer-Aided Design, vol. 43, no. 3, pp. 303–315, 2011, doi: https://doi.org/10.1016/j.cad.2010.12.015.

S. Mirjalili, S. M. Mirjalili, and A. Lewis, “Grey Wolf Optimizer,” Advances in Engineering Software, vol. 69, pp. 46–61, 2014, doi: https://doi.org/10.1016/j.advengsoft.2013.12.007.




DOI: http://dx.doi.org/10.12962/limits.v21i3.21862

Refbacks

  • »
  • »
  • »
  • »


Jumlah Kunjungan:

Creative Commons License
Limits: Journal Mathematics and its Aplications by Pusat Publikasi Ilmiah LPPM Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/limits.