Traveling Salesman Problem (TSP)

Traveling salesman Problem (TSP) merupakan permasalahan dalam menentukan titik persinggahan yang termurah biayanya dan terdekat dengan titik tujuan, ketika seorang salesman akan melakukan perjalanan dari titik asal ke titik tujuan yang mempunyai beberapa pilihan jalan yang dapat dilewati untuk sampai ketitik tujuan.

Algoritma Traveling Salesman Problem merupakan algoritma yang meniru perjalanan seorang penjaja keliling yang mengunjungi beberapa kota, kemudian kembali ke kota awal perjalanannya dimana tiap kota hanya dikunjungi sekali saja. Perjalanan tersebut harus menunjukkan perjalanan dengan jarak atau waktu minimum. Pada TSP ini kota dinyatakan sebagai vertek dan rute perjalanannya dinyatakan sebagai edge. Dengan kata lain masalah Algoritma Traveling Salesman Problem ini menyangkut suatu basis lokasi untuk mengunjungi n-1 buah lokasi lainnya dan kemudian kembali ke basisnya.

Didalam penerapan TSP ini graf yang dimaksud adalah graf yang berbobot. Graf berbobot adalah graf yang edgenya diberi nilai numeric, dimana nilai numerik ini merupakan jarak antara verteks atau dalam TSP merupakan jarak kota atau biaya dari kota satu dengan kota lainnya.

Travelling Salesman Problem sering dihubungkan dengan masalah mencari Hamiltonian cycle (untai Hamiltonian) didalam graf. Untai Hamilton didefinisikan sebagai sebuah graf yang memiliki untai tertutup yang melewati setiap vertek dalam graf tersebut atau dalam kata lain masing-masing node dikunjungi tepatnya sekali.

Untai tertutup sendiri adalah suatu jalan tertutup didalam graf dimana semua edge dan verteksnya berbeda sehingga tidak ada verteks yang muncul lebih dari sekali kecuali verteks awal dan akhir.