The week's pick
Random Articles
Reseach Article
Traveling Salesman Problem Multi-destination Route Recommendation System Using Genetic Algorithm and Google Maps API
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 185 - Number 18 |
| Year of Publication: 2023 |
| Authors: Catharina Adinda Mega Cahyani, Trianggoro Wiradinata |
10.5120/ijca2023922907
|
Catharina Adinda Mega Cahyani, Trianggoro Wiradinata . Traveling Salesman Problem Multi-destination Route Recommendation System Using Genetic Algorithm and Google Maps API. International Journal of Computer Applications. 185, 18 ( Jun 2023), 35-43. DOI=10.5120/ijca2023922907
Abstract
Google Maps does not provide route recommendations if users want to find the shortest route from multiple destinations or stop destinations, or more than two destinations. Departing from the shortcomings of Google Maps which cannot sort the sequence of multi-destination routes with the shortest distance, the researcher created an innovation with a genetic algorithm in solving the problem of the Traveling Salesman Problem category. The processes in the genetic algorithm of solving the Traveling Salesman Problem include data collection from primary document sources, ETL implementation, genetic algorithm implementation, and genetic algorithm testing with comparison algorithms. The data to be used in this study is primary data from the day tour package "Banyuwangi City Tour" from PT. LINTASNUSA TOURISM PRIMARY. This research produces recommendations for destination routes with the shortest real-time travel distance with short computational time. The genetic algorithm that has been programmed will be compared with other Traveling Salesman Problem solving algorithms, namely Nearest Neighbor and Brute Force. Based on the results of testing with primary data, the genetic algorithm is proven to be able to solve the Traveling Salesman Problem with the shortest average distance and the same as the solution of the Brute Force algorithm, which is 42.759 kilometres. The genetic algorithm also successfully recommended destination routes with shorter real-time travel distances or more optimal solutions compared to the Nearest Neighbor algorithm, but the genetic algorithm took 0.9 seconds slower computational time than the Nearest Neighbor algorithm.
References
- R. Panko, “The Popularity of Google Maps: Trends in Navigation Apps in 2018,” Jul. 10, 2018. https://themanifest.com/app-development/trends-navigation-apps (accessed Feb. 25, 2023).
- E. Wulan and N. Apriani, “The Application of Genetic Algorithm in Solving Traveling Salesman Problem,” 2020, doi: 10.4108/eai.11-7-2019.2297522.
- S. Rohman, L. Zakaria, A. Asmiati, and A. Nuryaman, “Optimisasi Travelling Salesman Problem dengan Algoritma Genetika pada Kasus Pendistribusian Barang PT. Pos Indonesia di Kota Bandar Lampung,” Jurnal Matematika Integratif, vol. 16, no. 1, p. 61, 2020, doi: 10.24198/jmi.v16.n1.27804.61-73.
- S. Sharma and V. Jain, “A Novel Approach for Solving TSP Problem Using Genetic Algorithm Problem,” IOP Conf Ser Mater Sci Eng, vol. 1116, no. 1, p. 012194, 2021, doi: 10.1088/1757-899x/1116/1/012194.
- P. Mudjihartono, T. Tanprasert, and R. Setthawong, “A Comparative Study of Modified PSO Algorithm and Traditional PSO and GA in Solving University Course Timetable Problem,” 2018.
- M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization (Engineering Design and Automation), 1st ed. Wiley-Interscience, 1999.
- C. Pramartha and H. Suputra, “Rekomendasi Rute Perjalanan Wisata Berbasis Web Menggunakan Algoritma Genetika,” Jurnal Ilmu Komputer, vol. 13, pp. 21–27, Apr. 2020, doi: 10.24843/JIK.2020.v13.i01.p03.
- D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, 1st ed. Addison-Wesley Professional, 1989. [Online]. Available: http://gen.lib.rus.ec/book/index.php?md5=8ac0783ba24b71236b695cbdfab2ca67
- W. F. Mahmudy, “Algoritma Evolusi,” Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya, Malang, pp. 1–101, 2013.
- J. Juwairiah, D. Pratama, H. Rustamaji, H. Sofyan, and D. Prasetyo, “Genetic Algorithm for Optimizing Traveling Salesman Problems with Time Windows (TSP-TW),” International Journal of Artificial Intelligence & Robotics (IJAIR), vol. 1, p. 1, Oct. 2019, doi: 10.25139/ijair.v1i1.2024.
- S. A. Nene and S. K. Nayar, “A simple algorithm for nearest neighbor search in high dimensions,” IEEE Trans Pattern Anal Mach Intell, vol. 19, no. 9, pp. 989–1003, 1997, doi 10.1109/34.615448.
- I. Sutoyo, “Penerapan Algoritma Nearest Neighbour untuk Menyelesaikan Travelling Salesman Problem,” Jurnal Khatulistiwa Informatika, vol. 20, no. 1, pp. 101–106, 2018, doi: 10.31294/p.v20i1.3155.
- G. Kizilateş and F. Nuriyeva, “On the Nearest Neighbor Algorithms for the Traveling Salesman Problem,” in Advances in Computational Science, Engineering and Information Technology, D. Nagamalai, A. Kumar, and A. Annamalai, Eds., Heidelberg: Springer International Publishing, 2013, pp. 111–118.
- A. Rahman Saiyed, “The Traveling Salesman Problem,” 2012.
- R. H. Warren, “Solving the traveling salesman problem on a quantum annealer,” SN Appl Sci, vol. 2, no. 1, p. 75, 2019, doi: 10.1007/s42452-019-1829-x.
- S. Juneja, P. Saraswat, K. Singh, J. Sharma, D. Majumdar, and S. Chowdhary, Travelling Salesman Problem Optimization Using Genetic Algorithm. 2019. doi: 10.1109/AICAI.2019.8701246.
- F. Mahdia and F. Noviyanto, “211271-Pemanfaatan-Google-Maps-Api-Untuk-Pemban,” vol. 1, pp. 162–171, 2013.
- H. Santoso and R. Sanuri, “Implementasi Algoritma Genetika dan Google Maps API Dalam Penyelesaian Traveling Salesman Problem with Time Window (TSP-TW) Pada Penjadwalan Rute Perjalanan Divisi Pemasaran STMIK El Rahma,” Teknika, vol. 8, no. 2, pp. 110–118, 2019, doi: 10.34148/teknika.v8i2.187.
Index Terms
Keywords