Performance Analysis of ACO and FA Algorithms on Parameter Variation Scenarios in Determining Alternative Routes for Cars as a Solution to Traffic Jams

Authors

  • Yuliant Sibaroni School of Computing, Telkom University, Indonesia http://orcid.org/0000-0002-9275-8972
  • Sri Suryani Prasetiyowati School of Computing, Telkom University, Indonesia
  • Mitha Putrianty Fairuz School of Computing, Telkom University, Indonesia
  • Muhammad Damar School of Computing, Telkom University, Indonesia
  • Rafika Salis School of Computing, Telkom University, Indonesia

DOI:

https://doi.org/10.15575/join.v7i1.797

Keywords:

Alternative Route, Ant Colony Optimization, Firefly Algorithm, Parameter Optimization, Travel Time

Abstract

This study proposes several alternative optimal routes on traffic-prone routes using Ant Colony Optimization (ACO) and Firefly Algorithm (FA). Two methods are classified as the metaheuristic method, which means that they can solve problems with complex optimization and will get the solution with the best results. Comparison of alternative routes generated by the two algorithms is measured based on several parameters, namely alpha and beta in determination of the best alternative route. The results obtained are that the alternative route produced by FA is superior to ACO, with an accuracy of 88%. This is also supported by the performance of the FA algorithm which is generally superior, where the resulting alternative route is shorter in distance, time, running time and  there is no influence on the alpha parameter value. But in each iteration, the number of alternative routes generated is less. The contribution of this research is to provide information about the best algorithm between ACO and FA in providing the most optimal alternative route based on the fastest travel time. The recommended alternative path is a path that is sufficient for cars to pass, because the selection takes into account the size of the road capacity.

Author Biography

Yuliant Sibaroni, School of Computing, Telkom University

Lecturer in Informatics Faculty , Telkom University, received the bachelor’s degree in Statistics from Gadjah Mada University (UGM), received master dan doctoral degree in Informatics from Bandung Institute of Technology (ITB)

References

A. Marsiela, “ADB: Kemacetan di Bandung Melebihi Jakarta.†https://www.beritasatu.com/nasional/578854-adb-kemacetan-di-bandung-melebihi -jakarta (accessed Jun. 23, 2021).

R. Refianti and A. Benny, “Solusi optimal travelling salesman problem dengan Ant Colony System ( ACS ),†no. February 2016, 2005, doi: 10.13140/RG.2.1.2089.7047.

Y. Siyamtining Tyas and W. Prijodiprodjo, “Aplikasi Pencarian Rute Terbaik dengan Metode Ant Colony Optimazation (ACO),†IJCCS (Indonesian J. Comput. Cybern. Syst., vol. 7, no. 1, p. 55, 2013, doi: 10.22146/ijccs.3052.

V. Danchuk, O. Bakulich, and V. Svatko, “An Improvement in ant Algorithm Method for Optimizing a Transport Route with Regard to Traffic Flow,†Procedia Eng., vol. 187, pp. 425–434, 2017, doi: 10.1016/j.proeng.2017.04.396.

R. Claes and T. Holvoet, “Ant Colony Optimization applied to route planning using link travel time predictions,†IEEE Int. Symp. Parallel Distrib. Process. Work. Phd Forum, no. April 2014, pp. 358–365, 2011, doi: 10.1109/IPDPS.2011.173.

A. Bolufé-Röhler, J. M. O. Pereira, and S. Fiol-González, “Traffic flow estimation using ant colony optimization algorithms,†Comput. y Sist., vol. 18, no. 1, pp. 37–50, 2014, doi: 10.13053/CyS-17-4-2013-017.

L. Groleaz et al., “ACO with automatic parameter selection for a scheduling problem with a group cumulative constraint To cite this version : HAL Id : hal-02531062 ACO with automatic parameter selection for a scheduling problem with a group cumulative constraint,†2020.

H. Fahmi, M. Zarlis, E. B. Nababan, and P. Sihombing, “Ant Colony Optimization (ACO) Algorithm for Determining the Nearest Route Search in Distribution of Light Food Production,†J. Phys. Conf. Ser., vol. 1566, no. 1, 2020, doi: 10.1088/1742-6596/1566/1/012045.

L. Groleaz, S. N. Ndiaye, and C. Solnon, “ACO with automatic parameter selection for a scheduling problem with a group cumulative constraint,†GECCO 2020 - Proc. 2020 Genet. Evol. Comput. Conf., pp. 13–21, 2020, doi: 10.1145/3377930.3389818.

P. N. Ky Phuc and N. Le Phuong Thao, “Ant Colony Optimization for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window and Heterogeneous Fleets,†Logistics, vol. 5, no. 2, p. 28, 2021, doi: 10.3390/logistics5020028.

N. Ali, M. A. Othman, M. N. Husain, and M. H. Misran, “A review of firefly algorithm,†ARPN J. Eng. Appl. Sci., vol. 9, no. 10, pp. 1732–1736, 2014.

M. A. Tawhid and A. F. Ali, “Direct search firefly algorithm for solving global optimization problems,†Appl. Math. Inf. Sci., vol. 10, no. 3, pp. 841–860, 2016, doi: 10.18576/amis/100304.

X. Wang, M. He, and H. Jiang, “A Discrete Firefly Algorithm for Routing Optimization of Milk-Run,†no. Icadme, pp. 1538–1543, 2015, doi: 10.2991/icadme-15.2015.285.

J. Sudirwan, S. N. Fadlilah, and T. Teguh, “Aplikasi Hybrid Firefly Algorithm untuk Pemecahan Masalah Traveling Salesman: Studi Kasus pada PT Anugerah Mandiri Success,†ComTech Comput. Math. Eng. Appl., vol. 5, no. 2, p. 828, 2014, doi: 10.21512/comtech.v5i2.2281.

R. Micale, G. Marannano, A. Giallanza, P. P. Miglietta, G. P. Agnusdei, and G. La Scalia, “Sustainable vehicle routing based on firefly algorithm and TOPSIS methodology,†Sustain. Futur., vol. 1, no. September, p. 100001, 2019, doi: 10.1016/j.sftr.2019.100001.

J. Kwiecień and B. Filipowicz, “Firefly algorithm in optimization of queueing systems,†Bull. Polish Acad. Sci. Tech. Sci., vol. 60, no. 2, pp. 363–368, 2012, doi: 10.2478/v10175-012-0049-y.

A. Khadwilard, S. Chansombat, T. Thepphakorn, and P. Thapatsuwan, “Application of Firefly Algorithm and Its Parameter Setting for Job Shop Scheduling,†no. January, 2012.

M. M. Gangadharan and A. Salgaonkar, “Ant colony optimization and firefly algorithms for robotic motion planning in dynamic environments,†Eng. Reports, vol. 2, no. 3, pp. 1–23, 2020, doi: 10.1002/eng2.12132.

W. Windarto and E. Eridani, “Comparison of particle swarm optimization and firefly algorithm in parameter estimation of lotka-volterra,†AIP Conf. Proc., vol. 2268, no. September, 2020, doi: 10.1063/5.0017245.

D. Kurniawan and A. A. A. Colony, “93603-ID-none,†vol. 4, no. 3, 2016.

S. Sawyer, “Analysis of Variance : The Fundamental Concepts,†no. December, 2017, doi: 10.1179/jmt.2009.17.2.27E.

W. Wang and Y. Lu, “Analysis of the Mean Absolute Error (MAE) and the Root Mean Square Error (RMSE) in Assessing Rounding Model,†IOP Conf. Ser. Mater. Sci. Eng., vol. 324, no. 1, 2018, doi: 10.1088/1757-899X/324/1/012049.

A. J. Umbarkar, U. T. Balande, and P. D. Seth, “Performance evaluation of firefly algorithm with variation in sorting for non-linear benchmark problems,†AIP Conf. Proc., vol. 1836, no. June 2017, 2017, doi: 10.1063/1.4981972.

Lestari Himmawati Puji dan Eminugroho Ratna Sari, “Penerapan algoritma koloni semut untuk optimisasi rute distribusi pengangkutan sampah di kota Yogyakarta,†J. Sains Dasar, vol. 2, no. 1, pp. 13–19, 2014, doi: 10.21831/jsd.v2i1.2373.

S. Katiyar, Ibraheem, and A. Q. Ansari, “Ant Colony Optimization : A Tutorial Review Ant Colony Optimization : A Tutorial Review Department of Electrical Engineering Corresponding Author : ( Email : aqansari@ieee.org ),†no. August, 2015.

J. E. Bell and P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,†Adv. Eng. Informatics, vol. 18, no. 1, pp. 41–48, 2004, doi: 10.1016/j.aei.2004.07.001.

Downloads

Published

2022-06-30

Issue

Vol. 7 No. 1 (2022)

Section

Article

Citation Check

License

You are free to:

 

Under the following terms:

  • Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.

  • NoDerivatives — If you remix, transform, or build upon the material, you may not distribute the modified material.

  • No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

 

Notices:

  • You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation.
  • No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License

Most read articles by the same author(s)

Similar Articles

1 2 3 4 5 6 7 8 9 10 > >> 

You may also start an advanced similarity search for this article.