Algoritma Held-Karp Yang Terbatas Untuk Traveling Salesman Problem (TSP)

Ambarwati, Titin Junik (2019) Algoritma Held-Karp Yang Terbatas Untuk Traveling Salesman Problem (TSP). Other thesis, Institut Teknologi Sepuluh Nopember.

Text 06111540000065-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (3MB) | Request a copy

Abstract

Traveling Salesman Problem (TSP) dapat diilustrasikan sebagai permasalahan perjalanan seseorang yang berangkat dari satu kota (node) ke kota (node) lain dan kembali ke kota awal dengan rute perjalanan terpendek, dimana setiap kota (node) hanya dilewati tepat satu kali. Terdapat banyak metode yang telah diteliti untuk bisa menyelesaikan TSP, namun penggunaan algoritma Held–Karp masih belum memberikan hasil yang memuaskan. Hal ini dikarenakan algoritma Held–Karp memiliki waktu komputasi yang lama untuk TSP yang cukup besar (n>20). Berdasarkan hal tersebut, dirumuskan algoritma Held–Karp yang terbatas yang dapat menyelesaikan TSP yang cukup besar. Algoritma Held–Karp yang terbatas disusun secara runtut dan ditambahkan pada algoritma genetika untuk mengetahui performansinya. Algoritma genetika yang dilengkapi algoritma Held–Karp yang terbatas dibandingkan dengan algoritma genetika dan algoritma Held–Karp yang terbatas. Untuk membandingkan ketiga algoritma tersebut, dibuat 50 problem yang diambil dari TSPLIB dengan jumlah node dan tipe yang berbeda. Dari hasil perhitungan, didapat rata-rata nilai akurasi dari algoritma genetika yang dilengkapi algoritma Held–Karp yang terbatas yaitu 99.62%, untuk algoritma Held–Karp yang terbatas didapat rata-rata nilai akurasi yaitu 94.21%, dan untuk algoritma genetika didapat rata-rata nilai akurasi yaitu 45.32%. Waktu komputasi algoritma Held–Karp yang terbatas lebih cepat dari algoritma genetika dan algoritma genetika yang dilengkapi algoritma Held–Karp yang terbatas, sedangkan waktu komputasi untuk algoritma genetika yang dilengkapi algoritma Held–Karp yang terbatas lebih cepat dari algoritma genetika untuk jumlah node yang kurang dari 96, dan waktu komputasi algoritma genetika lebih cepat dari algoritma genetika yang dilengkapi algoritma Held–Karp yang terbatas untuk jumlah node yang lebih dari sama dengan 96.
===============================================================================================================================
Traveling Salesman Problem (TSP) can be illustrated as the problem of someone traveling departing from one city (node) to another city (node) and returning to the initial city with the shortest route, where each city (node) is only passed once. There are many methods that have been studied to be able to complete TSP, but the use of the Held-Karp algorithm still has not produced satisfactory results. This is because the Held-Karp algorithm has a long computational time for a large TSP (n> 20). Based on this, a restricted Held-Karp algorithm is formulated that can solve a large TSP. The restricted Held-Karp algorithm is arranged in a coherent manner and added to the genetic algorithm to determine its performance. Genetic algorithms that are equipped with a restricted Held-Karp algorithm are compared to genetic algorithms and a restricted Held-Karp algorithm. To compare the three algorithms, 50 problems were made from TSPLIB with different nodes and types. From the calculation results, it is obtained that the average accuracy value of the genetic algorithm which is equipped with a restricted Held-Karp algorithm is 99.62%, for a restricted Held-Karp algorithm the average value of accuracy is 94.21%, and for the average genetic algorithm obtained accuracy value is 45.32%. The computational time of the restricted Held-Karp algorithm is faster than genetic algorithms and genetic algorithms which are equipped with a restricted Held-Karp algorithm, while the computational time for genetic algorithms that are equipped with a restricted Held-Karp algorithm are faster than genetic algorithms for less than 96, and the computational time of the genetic algorithm is faster than the genetic algorithm which is equipped with the Held-Karp algorithm which is restricted to the number of nodes more than equal to 96.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Algoritma Genetika, Algoritma Held–Karp, Algoritma Held–Karp yang terbatas, Dynamic Programming, Traveling Salesman Problem (TSP)
Subjects:	Q Science > QA Mathematics > QA402.5 Genetic algorithms. Interior-point methods. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Mathematics, Computation, and Data Science > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	TITIN JUNIK AMBARWATI
Date Deposited:	06 Aug 2026 05:18
Last Modified:	06 Aug 2026 05:18
URI:	http://repository.its.ac.id/id/eprint/65655

Actions (login required)

View Item