Solving the Traveling Salesman Problem on a Directed Graph Using Greedy Algorithm (Case Study: Locations of BRI Bank in Bandar Lampung City)
Article Sidebar
Main Article Content
Abstract
The traveling salesman problem is the idea that a salesman must discover the shortest path between an origin point and many destination points, returning to the origin point after visiting the destination point once. In this study, the Greedy Algorithm will be used to solve the Traveling Salesman Problem on a directed graph which represented BRI Banks in Bandar Lampung city. The locations of the banks are represented by points, while the journey time between BRI Banks is represented by lines. According to the results, 130 minutes was the same amount of time spent manually and with the Python software.
Article Details
References
[1] Saiful Rohman, La Zakaria, Asmiati Asmiati, and Aang Nuryaman. Optimisasi travelling salesman problem dengan algoritma genetika pada kasus pendistribusian barang pt. pos indonesia di kota bandar lampung. Jurnal Matematika Integratif, 16(1):61–73, 2020 (in Indonesia).
[2] Admi Syarif,Wamiliana Wamiliana, and Yasir Wijaya. Evaluasi kinerja metode-metode heuristik untuk penyelesaian travelling salesman problem. Jurnal Sains MIPA Universitas Lampung, 2(2), 2012 (in Indonesia).
[3] Norman Biggs. The traveling salesman problem a guided tour of combinatorial optimization. Bulletin of the London Mathematical Society, 18(5):514–515, 1986.
[4] Gerhard Reinelt. The Traveling Salesman: Computational Solutions for Tsp Applications, volume 840. Springer, 2003.
[5] Mohammad Asim, Ritika Gopalia, and Shivalika Swar. Traveling salesman problem using genetic algorithm. International Journal of Latest Trends in Engineering and Technology, 3(3):183–190, 2014.
[6] David B Fogel. An evolutionary approach to the traveling salesman problem. Biological Cybernetics, 60(2):139–144, 1988.
[7] Alvendo Wahyu Aranski. Optimization of the smallest road using the traveling salesman problem (tsp) method. IJISTECH (International Journal of Information System and Technology), 6(1):159–166, 2022.
[8] Andrew Wilson, Yuliant Sibaroni, and Izzatul Ummah. Analisis penyelesaian traveling salesman problem dengan metode brute force menggunakan graphic processing unit. eProceedings of Engineering, 2(1):1874–1883, 2015 (in Indonesia).
[9] Muchamad Kurniawan, Farida Farida, and Siti Agustini. Rute terpendek algoritma particle swarm optimization dan brute force untuk optimasi travelling salesman problem. Jurnal Teknik Informatika, 14(2):191–200, 2021 (in Indonesia).
[10] Sriyani Violina. Analysis of brute force and branch & bound algorithms to solve the traveling salesperson problem (tsp). Turkish Journal of Computer and Mathematics Education, 12(8):1226–1229, 2021.
[11] Sitti Rosnafi’an Sumardi, Nur Nilam Sari, and Justin Eduardo Simarmata. Product distribution route using nearest neighbor algorithm. MALCOM: Indonesian Journal of Machine Learning and Computer Science, 4(3):894–900, 2024.
[12] Imam Sutoyo. Penerapan algoritma nearest neighbour untuk menyelesaikan travelling salesman problem. Paradigma, 20(1):101–106, 2018 (in Indonesia).
[13] Anie Lusiani, Siti Samsiyah Purwaningsih, and Euis Sartika. Tsp method using nearest neighbor algorithm at pt. j&t express in bandung. Jurnal Lebesgue: Jurnal Ilmiah Pendidikan Matematika, Matematika dan Statistika, 4(3):1560–1568, 2023.
[14] Stefan Hougardy and Mirko Wilde. On the nearest neighbor rule for the metric traveling salesman problem. Discrete Applied Mathematics, 195:101–103, 2015.
[15] AB Doumi, BA Mahafzah, and H Hiary. Solving traveling salesman problem using genetic algorithm based on efficient mutation operator. Journal of Theoretical and Applied Information Technology, 99(15):3768–3781, 2021.
[16] Erjon Duka. Traveling sales problem solved by branch and bound algorithm in lindo programming. Available at SSRN 3152830, 2018.
[17] L Virginayoga Hignasari and Eka Diana Mahira. Optimization of goods distribution route assisted by google map with cheapest insertion heuristic algorithm (cih). Sinergi, 22(2):132–138, 2018.
[18] Kadek Meliantari, D Putra Githa, and NK Ayu Wirdiani. Optimasi distribusi produk menggunakan metode cheapest insertion heuristic berbasis web. Merpati, 6(3):204, 2018 (in Indonesia).
[19] Rio Guntur Utomo, Dian Sa’adillah Maylawati, and Cecep Nurul Alam. Implementasi algoritma cheapest insertion heuristic (cih) dalam penyelesaian travelling salesman problem (tsp). Jurnal Online Informatika, 3(1):61–67, 2018 (in Indonesia).
[20] Omar Cheikhrouhou and Ines Khoufi. A comprehensive survey on the multiple traveling salesman problem: Applications, approaches and taxonomy. Computer Science Review, 40:100369, 2021.