Permasalahan Penjual Keliling

Templat:Use Oxford spelling

Permasalahan Penjual Keliling atau Travelling Salesman Problem (TSP) menyatakan pertanyaan: "Diberikan daftar kota-kota dan jarak diantara tiap kota, tentukan rute terdekat yang mengunjungi tiap kota dan kembali ke kota asal?" Pertanyaan ini adalah permasalahan NP sulit di optimalisasi kombinatorial, penting dalam teori ilmu komputer dan riset operasi.

Permasalahan Pembeli Kelilingdan Permasalahan Rute Kendaraan adalah sama-sama generalisasi dari TSP.

Dalam Teori Kompleksitas Komputasional, versi pilihan dari TSP (dimana diberikan panjang L, tugas untuk memilih antara graf perjalanan dari kebanyakan L) berada pada kelas permasalahan NP-lengkap. Maka, memungkinkan bahwa Kasus Skenario Terburuk untuk kompleksitas waktu pada algoritma apapun pada TSP bertambah superpolinomial (tetapi, tidak lebih dari Hipotesis Waktu Eksponensial) dengan jumlah banyaknya kota.

Permasalahan ini awalnya diformulasikan pada tahun 1930 dan menjadi salah satu permasalahan yang intens dipelajari dalam bidang optimalisasi. Permasalahan ini digunakan sebagai Tolak Ukur dalam komputasi pada metode-metode optimalisasi. Meskipun permasalahan ini sangat susah secara komputasi, banyak heuristik dan Algoritma Eksak diketahui, hingga beberapa instansi dengan puluhan hingga ribuan kota bisa diselesaikan secara lengkap dan bahkan permasalahan dengan jutaan kota bisa diperkirakan didalam fraksi kecil yaitu 1%.^[1]

TSP memiliki beberapa aplikasi meskipun pada formulasi yang sangat murni, seperti perencanaan, logistik, dan manufaktur dari sirkuit terintegrasi. Sedikit modifikasi, terlihat sebagai sub-permasalahan di lingkup yang luas, seperti DNA sekuens. Pada aplikasi-aplikasi ini, konsep kota merepresentasi, contoh, pelanggan, poin solder, atau fragmen-fragmen DNA, dan konsep jarak merepresentasi waktu atau harga dari perjalanan atau tur, atau ukuran kemiripan diantara fragmen-fragmen DNA. TSP juga muncul pada astronomi, dimana para ahli astronomi mengobservasi banyak sumber yang ingin diminamilisir waktu yang dibuang menggerakkan teleskop antar sumber; pada permasalahan ini, TSP bisa ditanam dalam Kontrol Optimal. Pada banyak aplikasi, tambahan kendala seperti sumber daya terbatas atau jendela waktu yang diberikan.

Asal-usul dari permasalahan penjual keliling tidak jelas. Sebuah buku panduan untuk penjual keliling dari tahun 1832 menyebutkan permasalahan dan termasuk contoh tur melalui Jerman dan Swiss, tetapi tidak mengandung penyelesaian matematis.^[2]

TSP secara matematis diformulasikan pada abad ke-19 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Kirkman