Brute Force Algorithm Application For Solving Traveling Salesman Problem (TSP) In Semarang City Tourist Destinations

Dika Setyo Nugroho(1*), Ahmad Ilham(2)


(1) Universitas Muhammadiyah Semarang
(2) 
(*) Corresponding Author

Abstract


This research applies the brute force algorithm to address the Traveling Salesman Problem (TSP) in the city of Semarang. It involves location and distance data from Google Maps, and a Python program is implemented to find the shortest and longest routes among Dusun Semilir, Cimory on The Valley, Rawa Pening, Gedong Songo Temple, Marina Beach, Semarang Old Town, Sam Poo Kong Temple, Lawang Sewu, Rainbow Village, Ranggawarsita Museum, and Simpang Lima. The results show that the shortest route from Marina Beach to Gedong Songo Temple is 72.1 km, while the longest route from Sam Poo Kong Temple to Rainbow Village reaches 300 km. The analysis strengthens the effectiveness of the brute force algorithm, although time complexity remains a major consideration. This research provides a foundation for further development and tackling more complex scenarios on larger datasets.


Full Text:

PDF

References


W. R. Hamilton and T. P. Kirkman, Mathematical Exploration of the Traveling Salesman Problem, in Biggs, N., Lloyd, E. K., & Wilson, R. J. Graph Theory 1736–1936, Clarendon Press, Oxford, 1800s.

S. Atmojo, "Teori Permutasi dan Penggunaan API Mapbox untuk Implementasi TSP," Jurnal Ilmiah Edutic, vol. 4, no. 2, pp. 122-130, May 2018.

A. Wilson, "Analysis of the Brute Force Method for the Traveling Salesman Problem," Journal of Computational Optimization, vol. 45, no. 2, pp. 123-130, 2020, doi:10.1016/j.jcomp.2020.02.003.

R. Munir, Algoritma dan Pemrograman Komputer, Institut Teknologi Bandung, Bandung, 2014.

J. Johnson and D. Smith, "Optimization Methods for Traveling Salesman Problems," Journal of Operations Research, vol. 35, pp. 50-59, 2019.

D. Applegate, R. Bixby, V. Chvatal, and W. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2007.

G. Gutin and A. P. Punnen, The Traveling Salesman Problem and Its Variations, Springer, 2006.

H. S. Hwang, "Exact Algorithms for Solving the TSP: Review and Application," Algorithms, vol. 12, no. 5, pp. 82-90, 2019.

R. Karp, "Reducibility among Combinatorial Problems," in Complexity of Computer Computations, Springer, pp. 85-103, 1972.

E. Lawler, J. Lenstra, A. Kan, and D. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley-Interscience, 1985.

P. Moscato and M. G. Norman, "A Memetic Algorithm for Traveling Salesman Problem," Optimization Techniques, vol. 3, no. 6, pp. 269-279, 1991.

R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, 1994.

R. Bellman, "Dynamic Programming Treatment of Traveling Salesman Problem," Journal of ACM, vol. 9, no. 1, pp. 61-63, 1962.

J. M. Rosenkrantz, D. J. Stearns, and P. M. Lewis, "Approximate Algorithms for the Traveling Salesman Problem," SIAM Journal on Computing, vol. 6, pp. 563-581, 1977.

M. Held and R. M. Karp, "A Dynamic Programming Approach to Sequencing Problems," Journal of the Society for Industrial and Applied Mathematics, vol. 10, no. 2, pp. 196-210, 1962.

C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover, 1998.

G. Reinelt, The Traveling Salesman Problem: Computational Solutions, Springer-Verlag, 1994.

N. Christofides, "Worst-case Analysis of a New Heuristic for the Traveling Salesman Problem," Mathematical Programming, vol. 20, pp. 30-35, 1976.

B. L. Golden and E. A. Wasil, "Metaheuristics in Combinatorial Optimization," Annals of Operations Research, vol. 63, pp. 209-216, 1996.

T. M. Cavalcante, "Performance Comparison of Different Approaches to Solving TSP," IEEE Access, vol. 5, pp. 18753-18762, 2017.

Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1996.

S. Lin and B. W. Kernighan, "An Effective Heuristic Algorithm for the Traveling Salesman Problem," Operations Research, vol. 21, no. 2, pp. 498-516, 1973.

H. Hoos and T. Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann, 2004.

A. Blum and M. R. Furst, "Fast Planning through Planning Graph Analysis," in Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, pp. 1636-1642, 1995.

R. Sedgewick and K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.


Article Metrics

Abstract view : 41 times
PDF - 11 times

DOI: https://doi.org/10.26714/jkti.v3i1.16196

Refbacks

  • There are currently no refbacks.


=======================================================================================

Penerbit:

  • JKTI | Jurnal Komputer dan Teknologi Informasi
  • Program Studi S1 Informatika,  Unimus| Universitas Muhammadiyah Semarang
  • Sekretariat: Gedung Kuliah Bersama II (GKB II) Lantai 7,  Jl. Kedungmundu Raya No 18 Semarang
  • email: informatika@unimus.ac.id, Phone: + +62 813 2504 3677
  • e-ISSN: 2986-7592

Paper Template: Download

View My Stats

------------------------------------------------------------------------------------------------------------------------------------------------------