Ant Colony Optimization algorithm for determining the shortest routes to reduce distribution costs

Yusraini Muharni, Evi Febianti, Febby Chandra Adipradana, Muhammad Adha Ilhami, Ade Irman Saeful Muttaqin, Kulsum Kulsum, Lely Herlina, Anting Wulandari, Hartono Hartono

Abstract


Distribution is an important activity that companies need to pay attention to. Improper planning for distribution activities can potentially waste both cost and time. Determining the shortest distribution route could help companies effectively reduce distribution costs. This research was conducted on a small and medium enterprise (SME) located in Rangkasbitung, Indonesia that sells various types of bread. Distribution activities carried out by Jaya Roti were found to be still conventional, while the distribution carried out to the city of Serang has many locations and complex route combinations. This research utilized the metaheuristic method of Ant Colony Optimization (ACO) with MATLAB software to determine the shortest route, which is included in the Travel Salesman Problem (TSP). The result of the shortest route determination was a total distance of 93,484 Km with an efficiency rate of 26.97% and a resulting cost of IDR 170,795.

Keywords


Ant Colony Optimization; Shortest route; Distribution; Travel Salesman Problem

Full Text:

PDF

References


B.-Y. Cheng, J. Y.-T. Leung, and K. Li, “Integrated scheduling of production and distribution to minimize total cost using an improved ant colony optimization method,” Comput. Ind. Eng., vol. 83, pp. 217–225, May 2015, doi: 10.1016/j.cie.2015.02.017.

A. Swarnkar, N. Gupta, and K. R. Niazi, “Adapted ant colony optimization for efficient reconfiguration of balanced and unbalanced distribution systems for loss minimization,” Swarm Evol. Comput., vol. 1, no. 3, pp. 129–137, Sep. 2011, doi: 10.1016/j.swevo.2011.05.004.

D. Liu, X. Hu, and Q. Jiang, “Design and optimization of logistics distribution route based on improved ant colony algorithm,” Optik, vol. 273, p. 170405, Feb. 2023, doi: 10.1016/j.ijleo.2022.170405.

D. Zhang, S. Cai, F. Ye, Y.-W. Si, and T. T. Nguyen, “A hybrid algorithm for a vehicle routing problem with realistic constraints,” Inf. Sci., vol. 394–395, pp. 167–182, Jul. 2017, doi: 10.1016/j.ins.2017.02.028.

Q. Zhang and S. Xiong, “Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm,” Appl. Soft Comput., vol. 71, pp. 917–925, Oct. 2018, doi: 10.1016/j.asoc.2018.07.050.

Y. meng Yue and X. Wang, “An Improved Ant Colony Optimization Algorithm for Solving TSP,” Int. J. Multimed. Ubiquitous Eng., vol. 10, no. 12, pp. 153–164, Dec. 2015, doi: 10.14257/ijmue.2015.10.12.16.

P. Stodola, P. Otřísal, and K. Hasilová, “Adaptive Ant Colony Optimization with node clustering applied to the Travelling Salesman Problem,” Swarm Evol. Comput., vol. 70, p. 101056, Apr. 2022, doi: 10.1016/j.swevo.2022.101056.

R. Skinderowicz, “Improving Ant Colony Optimization efficiency for solving large TSP instances,” Appl. Soft Comput., vol. 120, p. 108653, May 2022, doi: 10.1016/j.asoc.2022.108653.

J. B. Mach, K. K. Ronoh, and K. Langat, “Improved spectrum allocation scheme for TV white space networks using a hybrid of firefly, genetic, and ant colony optimization algorithms,” Heliyon, vol. 9, no. 3, p. e13752, Mar. 2023, doi: 10.1016/j.heliyon.2023.e13752.

L. Xu, K. Huang, J. Liu, D. Li, and Y. F. Chen, “Intelligent planning of fire evacuation routes using an improved ant colony optimization algorithm,” J. Build. Eng., vol. 61, p. 105208, Dec. 2022, doi: 10.1016/j.jobe.2022.105208.

X. Yang, H. Dong, and X. Yao, “Passenger distribution modelling at the subway platform based on ant colony optimization algorithm,” Simul. Model. Pract. Theory, vol. 77, pp. 228–244, Sep. 2017, doi: 10.1016/j.simpat.2017.03.005.

X. Du, C. Du, J. Chen, and Y. Liu, “An energy-aware resource allocation method for avionics systems based on improved ant colony optimization algorithm,” Comput. Electr. Eng., vol. 105, p. 108515, Jan. 2023, doi: 10.1016/j.compeleceng.2022.108515.

P. González, R. R. Osorio, X. C. Pardo, J. R. Banga, and R. Doallo, “An efficient ant colony optimization framework for HPC environments,” Appl. Soft Comput., vol. 114, p. 108058, Jan. 2022, doi: 10.1016/j.asoc.2021.108058.

M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst. Man Cybern. Part B Cybern., vol. 26, no. 1, pp. 29–41, Feb. 1996, doi: 10.1109/3477.484436.

Y. Wang and Z. Han, “Ant colony optimization for traveling salesman problem based on parameters optimization,” Appl. Soft Comput., vol. 107, p. 107439, Aug. 2021, doi: 10.1016/j.asoc.2021.107439.

M. Das, A. Roy, S. Maity, and S. Kar, “A Quantum-inspired Ant Colony Optimization for solving a sustainable four-dimensional traveling salesman problem under type-2 fuzzy variable,” Adv. Eng. Inform., vol. 55, p. 101816, Jan. 2023, doi: 10.1016/j.aei.2022.101816.

P. Balaprakash, M. Birattari, T. Stützle, and M. Dorigo, “Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers,” Comput. Optim. Appl., vol. 61, no. 2, pp. 463–487, Jun. 2015, doi: 10.1007/s10589-014-9719-z.

H. Zhao and C. Zhang, “An ant colony optimization algorithm with evolutionary experience-guided pheromone updating strategies for multi-objective optimization,” Expert Syst. Appl., vol. 201, p. 117151, Sep. 2022, doi: 10.1016/j.eswa.2022.117151.

Zhou, H. Ma, J. Gu, H. Chen, and W. Deng, “Parameter adaptation-based ant colony optimization with dynamic hybrid mechanism,” Eng. Appl. Artif. Intell., vol. 114, p. 105139, Sep. 2022, doi: 10.1016/j.engappai.2022.105139.

Q. Wang et al., “A Dual-Robot Cooperative Welding Path Planning Algorithm Based on Improved Ant Colony Optimization,” IFAC-Pap., vol. 55, no. 8, pp. 7–12, 2022, doi: 10.1016/j.ifacol.2022.08.002.




DOI: http://dx.doi.org/10.36055/jiss.v9i1.19022

Refbacks

  • There are currently no refbacks.


  is supported by