Issue

Vo. 6, No. 3, August 2021

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Application of Ant Colony Optimization for the Shortest Path Problem of Waste Collection Process

https://doi.org/10.22219/kinetik.v6i3.1307
Andhi Akhmad Ismail
Universitas Gadjah Mada
Radhian Krisnaputra
Universitas Gadjah Mada
Irfan Bahiuddin
Universitas Gadjah Mada

Corresponding Author(s) : Andhi Akhmad Ismail

andhi_akhmad@ugm.ac.id

Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, Vo. 6, No. 3, August 2021

Abstract

The search for the shortest path of the waste collection process is an interesting topic that can be applied to various cases, from a very practical basic problem to a complex automation system development. In a dense settlement, the waste collection system can be a challenging process, especially to determine the most optimized path. The obstacles can be circling streets, impassable roads, and dead-end roads. A wrong choice of method can result in wasteful consumption of energy. A possible method to solve the problem is the traveling salesman problem using ant colony search optimization, considering its relatively fast optimization process. Therefore, this paper proposes an application of ant colony and traveling salesperson problem in determining the shortest path of the waste collection process. The case study for the optimization algorithm application is the path UGM Sekip Lecturer Housing is considering. Firstly, the data was collected by measuring the distance between points. Then, the paths were modeled and then compared with the actual route used by waste transport vehicles. The last step is implementing the ant colony optimization and traveling salesman problem by determining the cost function and the parameters. The optimization process was conducted several times, considering the random generator within the algorithm. The simulation results show the probable shortest path with a value of about 752 meters so that the use of fossil fuels in waste transport vehicles can be more efficient. The results show that the algorithm can automatically recommend the minimized path length to collect waste.

Keywords

travel salesperson problem ant colony optimization waste collection process optimization
Ismail, A. A., Krisnaputra, R., & Bahiuddin, I. (2021). Application of Ant Colony Optimization for the Shortest Path Problem of Waste Collection Process. Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, 6(3). https://doi.org/10.22219/kinetik.v6i3.1307
Download Citation
Endnote/Zotero/Mendeley (RIS)
BibTeX
References
  1. E. B. Tirkolaee, M. Alinaghian, A. A. R. Hosseinabadi, M. B. Sasi, and A. K. Sangaiah, "An improved ant colony optimization for the multi-trip Capacitated Arc Routing Problem," Comput. Electr. Eng., vol. 77, pp. 457–470, 2019. https://doi.org/10.1016/j.compeleceng.2018.01.040
  2. A. Alwabli, I. Kostanic, and S. Malk, "Static Route Optimization For Waste Collection In Mecca City," in 2020 IEEE 6th International Conference on Optimization and Applications (ICOA), 2020, pp. 1–7. https://doi.org/10.1109/ICOA49421.2020.9094473
  3. F. Akkerman, M. Mes, and W. Heijnen, "Distance Approximation for Dynamic Waste Collection Planning," Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 12433 LNCS, pp. 356–370, 2020. https://doi.org/10.1007/978-3-030-59747-4_23
  4. X. Liu, F. Yang, J. Chu, C. Zhu, M. He, and Y. Zhang, "General Model Based on Artificial Neural Networks for Estimating the Viscosities of Oxygenated Fuels," ACS Omega, vol. 4, no. 15, pp. 16564–16571, 2019. https://doi.org/10.1021/acsomega.9b02337
  5. I. Bahiuddin, S. A. Mazlan, F. Imaduddin, and Ubaidillah, "A new control-oriented transient model of variable geometry turbocharger," Energy, vol. 125, no. May, pp. 297–312, Apr. 2017. https://doi.org/10.1016/j.energy.2017.02.123
  6. I. Bahiuddin, S. A. Mazlan, F. Imaduddin, N. Yamasaki, and Ubaidillah, "A Transient Model of a Variable Geometry Turbocharger Turbine Using a Passive Actuator," Arab. J. Sci. Eng., vol. 46, no. 3, pp. 2565–2577, Mar. 2021. https://doi.org/10.1007/s13369-020-05158-2
  7. I. Khan, M. K. Maiti, and M. Maiti, "Coordinating particle swarm optimization, ant colony optimization and k-opt algorithm for traveling salesman problem," Commun. Comput. Inf. Sci., vol. 655, pp. 103–119, 2017. https://doi.org/10.1007/978-981-10-4642-1_10
  8. Y. Zhong, J. Lin, L. Wang, and H. Zhang, "Discrete comprehensive learning particle swarm optimization algorithm with Metropolis acceptance criterion for traveling salesman problem," Swarm Evol. Comput., vol. 42, no. March, pp. 77–88, 2018. https://doi.org/10.1016/j.swevo.2018.02.017
  9. M. Mosayebi, M. Sodhi, and T. A. Wettergren, "The Traveling Salesman Problem with Job-times (TSPJ)," Comput. Oper. Res., vol. 129, p. 105226, 2021. https://doi.org/10.1016/j.cor.2021.105226
  10. P. Baniasadi, M. Foumani, K. Smith-Miles, and V. Ejov, "A transformation technique for the clustered generalized traveling salesman problem with applications to logistics," Eur. J. Oper. Res., vol. 285, no. 2, pp. 444–457, 2020. https://doi.org/10.1016/j.ejor.2020.01.053
  11. M. A. H. Akhand, S. I. Ayon, S. A. Shahriyar, N. Siddique, and H. Adeli, "Discrete Spider Monkey Optimization for Travelling Salesman Problem," Appl. Soft Comput. J., vol. 86, p. 105887, 2020. https://doi.org/10.1016/j.asoc.2019.105887
  12. I. Bahiuddin, S. A. Mazlan, M. I. Shapiai, F. Imaduddin, Ubaidillah, and S.-B. Choi, "A new platform for the prediction of field-dependent yield stress and plastic viscosity of magnetorheological fluids using particle swarm optimization," Appl. Soft Comput., vol. 76, pp. 615–628, Mar. 2019. https://doi.org/10.1016/j.asoc.2018.12.038
  13. R. K. Mohammadi and S. Najarzade, "Semi-Active Control of Structures Equipped With MR Dampers Based on Uniform Deformation Theory," Int. J. Civ. Eng., vol. 16, no. 8, pp. 871–885, 2017. https://doi.org/10.1007/s40999-017-0213-8
  14. Z. Ding, F. Zhao, Y. Qin, and C. Tan, "Adaptive neural network control for semi-active vehicle suspensions," J. Vibroengineering, vol. 19, no. 4, pp. 2654–2669, 2017. https://doi.org/10.21595/jve.2017.18045
  15. A. Hemmati-Sarapardeh, A. Varamesh, M. M. Husein, and K. Karan, "On the evaluation of the viscosity of nanofluid systems: Modeling and data assessment," Renew. Sustain. Energy Rev., vol. 81, no. March 2017, pp. 313–329, Jan. 2018. https://doi.org/10.1016/j.rser.2017.07.049
  16. S. Gad, H. Metered, A. Bassuiny, and A. Abdel Ghany, "Multi-objective genetic algorithm fractional-order PID controller for semi-active magnetorheologically damped seat suspension," J. Vib. Control, vol. 23, no. 8, pp. 1248–1266, 2017. https://doi.org/10.1177%2F1077546315591620
  17. V. Mohammadi, S. Ghaemi, and H. Kharrati, "PSO tuned FLC for full autopilot control of quadrotor to tackle wind disturbance using bond graph approach," Appl. Soft Comput. J., vol. 65, pp. 184–195, 2018. https://doi.org/10.1016/j.asoc.2018.01.015
  18. A. Aminian and B. ZareNezhad, "Accurate predicting the viscosity of biodiesels and blends using soft computing models," Renew. Energy, vol. 120, pp. 488–500, May 2018. https://doi.org/10.1016/j.renene.2017.12.038
  19. E. A. Mancera-Galván, B. A. Garro, and K. Rodr’iguez-Vázquez, “Optimization of Solid Waste Collection: Two ACO Approaches,” Proc. Genet. Evol. Comput. Conf. Companion, no. 5, pp. 43–44, 2017. https://doi.org/10.1145/3067695.3082043
  20. S. P. Raflesia and A. K. Pamosoaji, "A novel ant colony optimization algorithm for waste collection problem," 2019 4th Int. Conf. Inf. Technol. Inf. Syst. Electr. Eng. ICITISEE 2019, vol. 6, pp. 413–416, 2019. https://doi.org/10.1109/ICITISEE48480.2019.9003896
  21. Z. Oralhan, B. Oralhan, and Y. Yiğit, "Smart city application: Internet of Things (IoT) technologies based smart waste collection using data mining approach and ant colony optimization," Int. Arab J. Inf. Technol., vol. 14, no. 4, pp. 423–427, 2017.
  22. C. Bayliss, "Machine learning based simulation optimisation for urban routing problems," Appl. Soft Comput., vol. 105, p. 107269, 2021. https://doi.org/10.1016/j.asoc.2021.107269
  23. G. Laporte and S. Martello, "The selective travelling salesman problem," Discret. Appl. Math., vol. 26, no. 2–3, pp. 193–207, 1990. https://doi.org/10.1016/0166-218X(90)90100-Q
  24. Y. Yu, Y. Li, and J. Li, "Nonparametric modeling of magnetorheological elastomer base isolator based on artificial neural network optimized by ant colony algorithm," J. Intell. Mater. Syst. Struct., vol. 26, no. 14, pp. 1789–1798, 2015. https://doi.org/10.1177%2F1045389X15577649
  25. P. M. Daigavane and P. R. Bajaj, "Road Lane Detection with Improved Canny Edges Using Ant Colony Optimization," 2010 3rd Int. Conf. Emerg. Trends Eng. Technol., pp. 76–80, 2010. https://doi.org/10.1109/ICETET.2010.128
  26. 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, 1996. https://doi.org/10.1109/3477.484436
  27. M. Dorigo, V. Maniezzo, A. Colorni, and M. Dorigo, “Positive Feedback as a Search Strategy,” Tech. Rep. 91-016, no. June, pp. 1–20, 1991.
Read More
Author biographies is not available.
Download this PDF file
PDF
Statistic
Read Counter : 184 Download : 143

Downloads

Download data is not yet available.