Permasalahan Penjual Keliling

Permasalahan Penjual Keliling atau Travelling Salesman Problem (TSP) menyatakan pertanyaan: "Diberikan daftar kota-kota dan jarak di antara 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 tolok 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 di dalam fraksi kecil yaitu 1%.Lihat tur dunia TSP yang dimana telah diselesaikan didalam 0.05% dari solusi optimal. 

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 di antara 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."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)


TSP secara matematis diformulasikan pada abad ke-19 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Kirkman. Permainan icosian Hamilton adalah teka-teki buatan yang didasarkan pada pencarian siklus Hamilton. Pembahasan mengenai karya awal Hamilton dan Kirkman dapat ditemukan dalam "Teori Graf, 1736-1936" karya Biggs, Lloyd, dan Wilson (Clarendon Press, 1986). Bentuk umum TSP tampaknya pertama kali dipelajari oleh matematikawan pada tahun 1930-an di Wina dan di Harvard, khususnya oleh Karl Menger, yang mendefinisikan masalah tersebut, mempertimbangkan algoritma gaya kasar yang jelas, dan mengamati ketidakoptimalan heuristik dari tetangga terdekat.

Masalah ini pertama kali dipertimbangkan secara matematis pada tahun 1930-an oleh Merrill M. Flood yang berupaya memecahkan masalah rute bus sekolah  Hassler Whitney di Universitas Princeton membangkitkan minat terhadap masalah tersebut, yang disebutnya sebagai "permasalahan 48 bagian". Publikasi paling awal yang menggunakan kata "travelling salesman problem" atau "permasalahan penjual keliling" pada tahun 1949 oleh Julia Robinson dalam RAND Corporation, "Pada permainan Hamiltonian (permasalahan penjual keliling)". Penanganan terperinci tentang hubungan antara Menger dan Whitney serta pertumbuhan dalam studi TSP dapat ditemukan di  .

Pada tahun 1950-an dan 1960-an, masalah ini menjadi semakin populer di kalangan ilmiah di Eropa dan Amerika Serikat setelah RAND Corporation di Santa Monica menawarkan hadiah untuk langkah-langkah dalam memecahkan masalah tersebut  Kontribusi penting diberikan oleh George Dantzig, Delbert Ray Fulkerson, dan Selmer M. Johnson dari RAND Corporation, yang menyatakan masalah tersebut sebagai program linear integer dan mengembangkan metode bidang potong untuk solusinya. Mereka menulis apa yang dianggap sebagai makalah penting tentang subjek tersebut di mana, dengan metode-metode baru ini, mereka memecahkan contoh dengan 49 kota hingga optimal dengan membuat sebuah tur dan membuktikan bahwa tidak ada tur lain yang lebih pendek. Namun, Dantzig, Fulkerson, dan Johnson berspekulasi bahwa, dengan solusi yang mendekati optimal, seseorang mungkin dapat menemukan keoptimalan atau membuktikan keoptimalan dengan menambahkan sejumlah kecil pertidaksamaan tambahan (pemotongan). Mereka menggunakan ide ini untuk memecahkan masalah 49 kota awal mereka menggunakan model string. Mereka menemukan bahwa mereka hanya memerlukan 26 pemotongan untuk mencapai solusi bagi masalah 49 kota mereka. Meskipun makalah ini tidak memberikan pendekatan algoritmik untuk masalah TSP, ide-ide yang terkandung di dalamnya sangat diperlukan untuk kemudian menciptakan metode solusi eksak untuk TSP, meskipun akan memakan waktu 15 tahun untuk menemukan pendekatan algoritmik dalam menciptakan pemotongan ini. Selain metode bidang pemotongan, Dantzig, Fulkerson, dan Johnson menggunakan algoritma cabang dan batas mungkin untuk pertama kalinya.

Referensi