Random Nearest Neighbour Untuk Menyelesaikan Russian TSP Instances

Abstract

Travelling Salesman Problem (TSP) merupakan permasalahan penentuan rute terpendek yang diawali dari titik start untuk mengunjungi sekumpulan titik tepat sekali dan diakhiri dengan kembali ke titik start. Nearest Neighbour (NN) merupakan salah satu algoritma yang bekerja berdasarkan heuristic. Dalam menyelesaikan TSP, cara kerja dari NN adalah memilih titik terdekat dari titik terakhir yang dikunjungi dan belum termasuk ke dalam rute, untuk dimasukkan ke dalam rute. Penentuan titik yang akan dikunjungi berikutnya, akan menjadi masalah jika terdapat 2 atau lebih pilihan titik, dikarenakan kesamaan jarak dari titik terakhir. Untuk menyelesaikan masalah tersebut algoritma Random dapat menjadi sebuah solusi.Dengan demikian algoritma ini dapat disebut dengan Random Nearest Neighbour (RNN). Kemampuan RNN dalam menyelesaikan TSP perlu diuji, agar dapat diketahui kehandalannya. Dua kriteria penting yang dinilai dalam pengujian ini adalah rute solusi yang dihasilkan dan waktu perhitungan (CPU Time). Russian TSP Instances merupakan TSP Instances yang dapat digunakan untuk menguji RNN. Hasil pengujian menunjukkan bahwa RNN dapat memperbaiki panjang rute yang secara cepat.