Perpustakaan Digital ITB

Travelling Salesman Problem (TSP) adalah permasalahan seorang salesman untuk menemukan rute dari satu kota melewati sekumpulan kota lainnya dan kembali ke kota awal dengan jarak atau biaya total paling minimum dan setiap kota hanya boleh dikunjungi sekali. TSP dapat diaplikasikan secara luas dalam kehidupan nyata. Salah satunya pada bidang telekomunikasi, sangat penting untuk menentukan rute terpendek dalam merancang sebuah topologi ring sehingga dapat mengurangi biaya pemasangan. TSP merupakan masalah klasik yang sederhana namun sulit dipecahkan secara konvensional. Sehingga membangkitkan minat para peneliti untuk mengeksplorasi dan mengembangkan algoritma untuk pemecahan masalah TSP. Beberapa algoritma yang telah ditemukan diantaranya adalah brute force algorithm, ant colony optimization algorithm (ACO), greedy algorithm dan Greedy Randomized Adaptive Search Procedure (GRASP). Algoritma brute force adalah algoritma yang paling mudah dan paling mahal untuk TSP. Algoritma ini mencoba setiap kemungkinan sehingga akan menghasilkan nilai minimum yang absolut, tetapi memerlukan waktu eksekusi yang sangat lama untuk jumlah node yang besar. Algoritma lainnya menggunakan metode heuristik sehingga tidak selalu memberikan solusi yang optimal meskipun dapat menghemat waktu eksekusi dibandingkan algoritma brute force. Penelitian untuk pengembangan algoritma heuristik masih sangat terbuka. Penelitian ini berfokus untuk mendapatkan solusi permasalah Travelling Salesman Problem dengan metode heuristik sehingga dapat menghasilkan algoritma dengan waktu eksekusi yang cepat serta hasil yang akurat mendekatai nilai absolut sehingga dapat diimplementasikan pada perencanaan jaringan. Algoritma pada penelitian ini merupakan pengembangan dari algoritma yang sudah ada. Algoritma ini berhasil memperbaiki kekurangan algoritma sebelumnya, yaitu waktu komputasi yang lama. Pada penelitian ini digunakan bahasa pemrograman python, dan untuk simulasi pada jaringan digunakan network simulator Net2Plan. Hasil penelitian menunjukkan bahwa algoritma ini pada beberapa data dapat mengungguli beberapa algoritma lain baik dari sisi waktu eksekusi maupun solusi nilai minimum yang dihasilkan.