PENENTUAN APPROXIMATION RATIO ALGORITMA 4-OPT PADA (1,2)-TRAVELING SALESMAN PROBLEM

GALIH PRADIPTO WISNUJATI, Prof. Dr.-Ing. Mhd. Reza MI Pulungan, S.Si., M.Sc.

2024 | Tesis | S2 Ilmu Komputer

Traveling Salesman Problem (TSP) adalah salah satu masalah yang paling terkenal di bidang optimalisasi diskrit. Untuk menemukan rute terpendek (optimal tour) pada TSP tidaklah mudah karena TSP dan beberapa variannya merupakan NP-Hard problem.

Salah satu variasi dari Metric TSP adalah (1,2)-TSP, dimana jarak antara dua buah titik bernilai 1 atau 2.

Berbagai algoritma dan pendekatan telah dibuat untuk menyelesaikan TSP, salah satunya adalah algoritma k-opt. Pada algoritma k-opt, untuk menemukan optimal tour, dilakukan dengan cara menukar maksimum sebanyak k buah edge dengan edge yang lain hingga didapatkan nilai tour yang lebih pendek pada setiap iterasi. Approximation ratio merupakan salah satu cara yang dapat digunakan untuk membandingkan antara algoritma yang satu dengan yang lain pada TSP. Suatu algoritma memiliki approximation ratio alpha(n), jika perbandingan antara nilai tour terpendek yang bisa diperoleh dari algoritma tersebut dengan nilai tour terpendek sebenarnya, maksimum sebesar alpha(n), untuk setiap persoalan TSP dengan n buah titik.

Beberapa penelitian telah dilakukan untuk mendapatkan approximation ratio dari algoritma k-opt pada (1,2)-TSP, untuk k = 2 dan k = 3. Namun untuk k > 3, masih perlu dilakukan penelitian. Oleh karena itu, dilakukan penelitian untuk mengetahui nilai

approximation ratio algoritma 4-opt pada (1,2)-TSP. Hasil penelitian menunjukkan bahwa nilai approximation ratio algoritma 4-opt pada (1,2)-TSP adalah 5/4 . Eksperimen telah dilakukan pada 12 sampel konstruksi (1,2)-TSP menggunakan program bahasa C++. Hasil eksperimen menunjukkan nilai yang sesuai dengan approximation ratio yang telah didapatkan dari perhitungan sebelumnya.

Traveling Salesman Problem (TSP) is one of the most famous problem in discrete optimization. To find the shortest route (optimal tour) in TSP is not easy, because TSP and its variant is NP-Hard problem. One of the variant of Metric TSP is (1,2)-TSP, where the distance between two of its vertices is 1 or 2.

Some algorithm and approaches have already been developed to solve TSP, one of them is k-opt algorithm. On k-opt algorithm, to find optimal tour, some exchange with at most k edges are conducted, until we find the shorter tour on each iteration.

Approximation ratio is one of the method to compare an algorithm to another one on TSP. An algorithm has approximation ratio alpha(n), if the comparison between the shortest tour obtained from these algorithm and the real shortest tour is at most alpha(n), on every TSP instance with n vertices.

Some research has been conducted to find the value of approximation ratio of k-opt algorithm for (1,2)-TSP, for k = 2 and k = 3. But for k > 3, a research is needed. Therefore, this research is conducted to find the value of approximation ratio of 4-opt algorithm for (1,2)-TSP.

The results show that the value of the approximation ratio of 4-opt algorithm for (1,2)-TSP is 5/4 . An experiment have been conducted on 12 samples of construction of (1,2)-TSP using a program which is uses C++ language. The result of the experiment

shows a value which is match with the approximation ratio which is obtained from previous calculation.

Kata Kunci : traveling salesman problem, approximation ratio, algoritma k-opt