Permasalahan Penjual Keliling

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.

Sejarah

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

Referensi

^ Lihat tur dunia TSP yang dimana telah diselesaikan didalam 0.05% dari solusi optimal. [1]
^ "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (Penjual keliling - bagaimana dia harus dengan apa yang dilakukan untuk mendapatkan komisi dan meyakinkan kesukesan pada bisnisnya - oleh seorang Commis-voyageur)

[1] Lihat tur dunia TSP yang dimana telah diselesaikan didalam 0.05% dari solusi optimal. [1]

[2] "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (Penjual keliling - bagaimana dia harus dengan apa yang dilakukan untuk mendapatkan komisi dan meyakinkan kesukesan pada bisnisnya - oleh seorang Commis-voyageur)

[1]

[2]