SP atau Traveling Salesman Problem adalah salah satu masalah distribusi yang cukup lama dibahas dalam kajian optimasi. Masalahnya adalah bagaimana seorang salesman mengunjungi seluruh kota di suatu daerah dan kembali ke kota awal keberangkatan dengan aturan bahwa tidak boleh ada kota yang dikunjungi lebih dari satu kali.
Berikut adalah aturan-aturan yang mengidentifikasikan bahwa permasalahan tersebut adalah TSP:
Perjalanan dimulai dan diakhiri di kota yang sama sebagai kota asal sales.
Seluruh kota harus dikunjungi tanpa satupun kota yang terlewatkan.
Salesman tidak boleh kembali ke kota asal sebelum seluruh kota terkunjungi.
Tujuan penyelesaian permasalahan ini adalah mencari nilai optimum dengan meminimumkan jarak total rute yang dikunjungi dengan mengatur urutan kota.
Perhatikan contoh berikut:
Seorang salesman akan mengawali perjalanannya di kota asal(Kota A) untuk mengunjungi seluruh kota yakni kota A-F. Perhatikan gambar berikut.
Dari studi kasus tersebut didapatkan salah satu kemungkinan jalur yang paling optimum dengan jalur urutan kota A->E->F->C->D->B->A. tentunya hasil tersebut dengan mempertimbangkan jarak dari masing-masing kota hingga menghasilkan kombinasi urutan kota dengan jarak yang optimum. Perhatikan gambar berikut.
Sumber : icomit.wordpress.com
