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]

William Rowan Hamilton, tahun 1850

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. ^[3] 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.

Kita menyatakan dengan "masalah kurir" (karena dalam praktiknya, pertanyaan ini harus diselesaikan oleh setiap tukan pos, juga oleh banyaknya pelancong) tugas untuk menemukan, untuk banyak titik terhingga yang jarak berpasangannya diketahui, rute terpendek yang menghubungkan titik-titik tersebut. Tentu saja, masalah ini dapat dieselesaikan dengan banyak percobaan. Aturan yang akan mendorong jumlah percobaan di bawah jumlah permutasi dari poin yang diberikan tidak diketahui. Aturan bahwa seseorang harus berangkat dari titik awal ke titik terdekat, lalu ke titik terdekat dengan titik tersebut, dan seterusnya, secara umum tidak menghasilkan rute terpendek. ^[4]

Masalah ini pertama kali dipertimbangkan secara matematis pada tahun 1930-an oleh Merrill M. Flood yang berupaya memecahkan masalah rute bus sekolah ^[5] 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)". ^[6]^[7]

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 ^[5] 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.^[5] Selain metode bidang pemotongan, Dantzig, Fulkerson, dan Johnson menggunakan algoritma cabang dan batas mungkin untuk pertama kalinya.^[5]

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)
^ Pembahasan mengenai karya awal Hamilton dan Kirkman dapat ditemukan dalam "Teori Graf, 1736-1936" karya Biggs, Lloyd, dan Wilson (Clarendon Press, 1986).
^ Dikutip dan diterjemahkan dari bahasa Inggris dalam Schrijver (2005). Bahasa Jerman Asli: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."
^ ^a ^b ^c ^d Lawler, E. L. (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization (edisi ke-Dengan pembetulan). John Wiley & sons. ISBN 978-0-471-90413-7.
^ Robinson, Julia (5 December 1949). On the Hamiltonian game (a traveling salesman problem) (PDF) (Laporan teknis) (dalam bahasa Inggris). Santa Monica, CA: The RAND Corporation. RM-303. Diakses tanggal 2 May 2020 – via Defense Technical Information Center.
^ Penanganan terperinci tentang hubungan antara Menger dan Whitney serta pertumbuhan dalam studi TSP dapat ditemukan di Schrijver (2005).

[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)

[3] Pembahasan mengenai karya awal Hamilton dan Kirkman dapat ditemukan dalam "Teori Graf, 1736-1936" karya Biggs, Lloyd, dan Wilson (Clarendon Press, 1986).

[4] Dikutip dan diterjemahkan dari bahasa Inggris dalam Schrijver (2005). Bahasa Jerman Asli: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."

[Wiley-5] Lawler, E. L. (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization (edisi ke-Dengan pembetulan). John Wiley & sons. ISBN 978-0-471-90413-7.

[Robinson1949-6] Robinson, Julia (5 December 1949). On the Hamiltonian game (a traveling salesman problem) (PDF) (Laporan teknis) (dalam bahasa Inggris). Santa Monica, CA: The RAND Corporation. RM-303. Diakses tanggal 2 May 2020 – via Defense Technical Information Center.

[Schrijver2005-7] Penanganan terperinci tentang hubungan antara Menger dan Whitney serta pertumbuhan dalam studi TSP dapat ditemukan di Schrijver (2005).

[1]

[2]

[3]

[4]

[5]

[6]

[7]