Ant Colony Optimization for Traveling Tourism Problem on Timor Island East Nusa Tenggara

Authors

  • Yampi R Kaesmetan Sekolah Tinggi Manajemen Informatika Uyelindo Kupang
  • Marlinda Vasty Overbeek

DOI:

https://doi.org/10.24014/ijaidm.v3i1.9274

Keywords:

Ant Colony Optimization Traveling Tourism Problem Optimization Shorthest Path

Abstract

Timor island consists of five districts and one city, namely Kupang District, South Central Timor District, North Central Timor, Belu District, Malaka District, and Kupang City. On the Timor island, it has natural tourist destinations, culinary tours, cultural and historical attractions most on the island of Timor. The Ant Colony Optimization (ACO) Algorithm is very unique compared to the other nearby search algorithm, this algorithm adopted because of Ant Colony who were looking for food from the nest to food sources by leaving a footprint called Pheromone. Mapping system algorithm using ant, tourist sites can show the shortest route between two points is desired. Ants algorithm proved to be applied in determining the optimum route, but still has the disadvantage of dependence on the parameter value is not maximized. From the test results based on parameters of the cycle and the number of ants affects the simulation time, for ant algorithm parameters. From the test results based on the parameters, α and β affects, number of node, the simulation time and the shortest distance varying toward the destination even if the starting location and ending on the same location.

Author Biography

Yampi R Kaesmetan, Sekolah Tinggi Manajemen Informatika Uyelindo Kupang

[1].              [BPS] Badan Pusat Statistik Provinsi NTT. 2019. Jumlah Wisatawan Domestik Menurut Kabupaten Kota di Provinsi NTT tahun 2010 – 2017. [internet][download : 2019 July 05]. Website : https://ntt.bps.go.id/dynamictable/2018/09/06/785/jumlah-wisatawan-domestikmenurut-kabupaten-kota-di-provinsi-nusa-tenggara-timur-2010-2017.html 

[2].              [BPS] Badan Pusat Statistik Provinsi NTT. 2019. Jumlah Wisatawan Mancanegara Menurut Kabupaten Kota di Provinsi NTT tahun 2006 – 2017. [internet][download : 2019 July 05]. Website : https://ntt.bps.go.id/dynamictable/2015/03/17/54/jumlah-wisatawan-mancanegara-menurut-kabupaten-kota-di-provinsi-nusa-tenggara-timur-2006-2017.html

[3].              Dorigo M, Maniezzo V and Colorni A. "Distributed optimization by ant colonies" Proceedings of the 1st European COnference on Artificial Life, pp.134-142, 1991.

[4].              M. Dorigo, V. Maniezzo and A. Colorni, "Ant System : Optimization by an colony cooperating Agents," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol.26, no.2, pp.29-41, 1996

[5].              X. Xue, X. Cheng, B. Xu, H. Wang and C. Jiang, "The basic principle and application of ant colony optimization algorithm," 2010 International Conference on Artificial Intelligence and Education (ICAIE), Hangzhou, 2010, pp. 358-360.

[6].              Y. Pei, W. Wang and S. Zhang, "Basic Ant Colony Optimization," 2012 International Conference on Computer Science and Electronics Engineering, Hangzhou, 2012, pp. 665-667.

[7].              M. Dorigo, M. Birattari and T. Stutzle, "Ant colony optimization," in IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, Nov. 2006.

[8].              M Dorigo and L.M. Gambardella. "Ant Colony System : A cooperative learning approach to the traveling salesman problem," IEEE Transaction on Evolutionary Computation, vol.1, no.1, pp.56-66,1997

[9].              M. Dorigo and L.M. Gambardella, "Ant colonies for the traveling salesman problem," BioSystems, vol.43, no.2, pp.77-81, 1997.

[10].          M. Dorigo, G. Di Caro and L.M. Gambardella, "Ant algorithms for discrete optimization," Artificial Life, vol.5, no.2, pp.137-172, 1999.

[11].          T. Stutzle and H. Hoos, "MAX-MIN Ant System and local search for the traveling salesman problem," Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), Indianapolis, IN, USA, 1997, pp. 309-314.

[12].          Zhaojun Zhang and Zuren Feng, "A novel Max-Min ant system algorithm for traveling salesman problem," 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems, Shanghai, 2009, pp. 508-511.

[13].          L. Li and J. Wang, "SAR image ship detection based on Ant Colony Optimization," 2012 5th International Congress on Image and Signal Processing, Chongqing, 2012, pp. 1100-1103.

[14].          X. Li, Z. Liu and Y. Zhang, "A Novel Improved Ant Colony Algorithm for Multi-Robot Task Allocation," 2018 IEEE 4th Information Technology and Mechatronics Engineering Conference (ITOEC), Chongqing, China, 2018, pp. 1629-1633.

[15].          S. Di, P. He and H. Li, "Agent Coalition Formation of Chinese Question Answering System Based on Improved Ant Colony Algorithm," 2010 International Conference on e-Education, e-Business, e-Management and e-Learning, Sanya, 2010, pp. 98-101.

[16].          Xian-Yi Ye, Xiao-Rong Cheng, Lu-Ming Liu and Qi-Yuan Feng, "Research of the Best Repair Path Based on an Improved Ant Colony Algorithm in Power Distribution Network," 2005 IEEE/PES Transmission & Distribution Conference & Exposition: Asia and Pacific, Dalian, 2005, pp. 1-5.

[17].          G. Weixin, L. Xianjue, T. Nan and M. Xiangyang, "Improved Ant Algorithm Combined with Ecological Theory for Urban Power System Planning," 2009 International Conference on Artificial Intelligence and Computational Intelligence, Shanghai, 2009, pp. 229-233.

[18].          L. Sheng and Y. Xiaoming, "The Design and Implementation of Urban Rail Transit Optimal Transfer System Based on Improved Ant Colony Algorithm," 2012 Second International Conference on Business Computing and Global Informatization, Shanghai, 2012, pp. 770-773.

[19].          Hiroaki Ono and Yasuchika Mori, "The optimal design of the vehicle routing problem with time windows by ant colony system," SICE Annual Conference 2007, Takamatsu, 2007, pp. 1325-1329.

[20].          G. Yancheng, H. Ronggui, Y. Xirui, S. Hongxing and L. Chang, "Improved ant colony algorithm for vehicle scheduling problems of military logistics distribution," 2010 International Conference on Logistics Systems and Intelligent Management (ICLSIM), Harbin, 2010, pp. 669-673.

[21].          X. Han and X. Zhang, "School Bus Route Optimization Based on Improved Ant Colony Algorithm," 2019 4th International Conference on Electromechanical Control Technology and Transportation (ICECTT), Guilin, China, 2019, pp. 312-316

References

. [BPS] Badan Pusat Statistik Provinsi NTT. 2019. Jumlah Wisatawan Domestik Menurut Kabupaten Kota di Provinsi NTT tahun 2010 – 2017. [internet][download : 2019 July 05]. Website : https://ntt.bps.go.id/dynamictable/2018/09/06/785/jumlah-wisatawan-domestikmenurut-kabupaten-kota-di-provinsi-nusa-tenggara-timur-2010-2017.html

. [BPS] Badan Pusat Statistik Provinsi NTT. 2019. Jumlah Wisatawan Mancanegara Menurut Kabupaten Kota di Provinsi NTT tahun 2006 – 2017. [internet][download : 2019 July 05]. Website : https://ntt.bps.go.id/dynamictable/2015/03/17/54/jumlah-wisatawan-mancanegara-menurut-kabupaten-kota-di-provinsi-nusa-tenggara-timur-2006-2017.html

. Dorigo M, Maniezzo V and Colorni A. "Distributed optimization by ant colonies" Proceedings of the 1st European COnference on Artificial Life, pp.134-142, 1991.

. M. Dorigo, V. Maniezzo and A. Colorni, "Ant System : Optimization by an colony cooperating Agents," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol.26, no.2, pp.29-41, 1996

. X. Xue, X. Cheng, B. Xu, H. Wang and C. Jiang, "The basic principle and application of ant colony optimization algorithm," 2010 International Conference on Artificial Intelligence and Education (ICAIE), Hangzhou, 2010, pp. 358-360.

. Y. Pei, W. Wang and S. Zhang, "Basic Ant Colony Optimization," 2012 International Conference on Computer Science and Electronics Engineering, Hangzhou, 2012, pp. 665-667.

. M. Dorigo, M. Birattari and T. Stutzle, "Ant colony optimization," in IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, Nov. 2006.

. M Dorigo and L.M. Gambardella. "Ant Colony System : A cooperative learning approach to the traveling salesman problem," IEEE Transaction on Evolutionary Computation, vol.1, no.1, pp.56-66,1997

. M. Dorigo and L.M. Gambardella, "Ant colonies for the traveling salesman problem," BioSystems, vol.43, no.2, pp.77-81, 1997.

. M. Dorigo, G. Di Caro and L.M. Gambardella, "Ant algorithms for discrete optimization," Artificial Life, vol.5, no.2, pp.137-172, 1999.

. T. Stutzle and H. Hoos, "MAX-MIN Ant System and local search for the traveling salesman problem," Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), Indianapolis, IN, USA, 1997, pp. 309-314.

. Zhaojun Zhang and Zuren Feng, "A novel Max-Min ant system algorithm for traveling salesman problem," 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems, Shanghai, 2009, pp. 508-511.

. L. Li and J. Wang, "SAR image ship detection based on Ant Colony Optimization," 2012 5th International Congress on Image and Signal Processing, Chongqing, 2012, pp. 1100-1103.

. X. Li, Z. Liu and Y. Zhang, "A Novel Improved Ant Colony Algorithm for Multi-Robot Task Allocation," 2018 IEEE 4th Information Technology and Mechatronics Engineering Conference (ITOEC), Chongqing, China, 2018, pp. 1629-1633.

. S. Di, P. He and H. Li, "Agent Coalition Formation of Chinese Question Answering System Based on Improved Ant Colony Algorithm," 2010 International Conference on e-Education, e-Business, e-Management and e-Learning, Sanya, 2010, pp. 98-101.

. Xian-Yi Ye, Xiao-Rong Cheng, Lu-Ming Liu and Qi-Yuan Feng, "Research of the Best Repair Path Based on an Improved Ant Colony Algorithm in Power Distribution Network," 2005 IEEE/PES Transmission & Distribution Conference & Exposition: Asia and Pacific, Dalian, 2005, pp. 1-5.

. G. Weixin, L. Xianjue, T. Nan and M. Xiangyang, "Improved Ant Algorithm Combined with Ecological Theory for Urban Power System Planning," 2009 International Conference on Artificial Intelligence and Computational Intelligence, Shanghai, 2009, pp. 229-233.

. L. Sheng and Y. Xiaoming, "The Design and Implementation of Urban Rail Transit Optimal Transfer System Based on Improved Ant Colony Algorithm," 2012 Second International Conference on Business Computing and Global Informatization, Shanghai, 2012, pp. 770-773.

. Hiroaki Ono and Yasuchika Mori, "The optimal design of the vehicle routing problem with time windows by ant colony system," SICE Annual Conference 2007, Takamatsu, 2007, pp. 1325-1329.

. G. Yancheng, H. Ronggui, Y. Xirui, S. Hongxing and L. Chang, "Improved ant colony algorithm for vehicle scheduling problems of military logistics distribution," 2010 International Conference on Logistics Systems and Intelligent Management (ICLSIM), Harbin, 2010, pp. 669-673.

. X. Han and X. Zhang, "School Bus Route Optimization Based on Improved Ant Colony Algorithm," 2019 4th International Conference on Electromechanical Control Technology and Transportation (ICECTT), Guilin, China, 2019, pp. 312-316

Downloads

Published

2020-05-16

Issue

Section

Articles