Permasalahan Penjual Keliling 📖 Wikipedia

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%.^[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 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.

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. 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]

Pada tahun 1959, Jillian Beardwood, J.H Halton, dan John Hammersley mempublikasikan sebuah artikel berjudul "The Shortest Path Through Many Points" (Jarak Terpendek Melalui Poin-poin Banyak) pada jurnal Cambridge Philosophical Society. ^[8] Teorema Beardwood-Halton-Hammersley memberikan solusi praktis pada permasalahan Penjual Keliling. Para penulis memberikan formula asimtotik untuk menentukan jarak dari rute terpendek untuk seorang penjual yang dimulai pada sebuah rumah atau kantor dan mengunjungi pada angka tetap dari lokasi-lokasi sebelum kembali ke awal.

Pada dekade yang sama, permasalahan tersebut dipelajari oleh banyak ilmuan dari matematika, ilmu komputer, kimia, fisika, dan cabang ilmu sains lainnya. Namun, pada tahun sekitar 1960, pendekatan baru telah dibuat bahwa, daripada mencari solusi optimal, yang dimana menghasilkan solusi dengan jarak yang diikat oleh jarak optimal, dan dengan melakukan itu menciptakan ikatan rendah untuk permasalahan tersebut; ikatan rendah ini kemudian akan digunakan untuk pendekatan bercabang dan mengikat. Salah satu metode untuk melakukan ini adalah dengan menciptakan rentang pohon minimum dari grafnya dan kemudian digandakan dari tiap tepiannya, dimana memproduksi ikatan jarak yang lebih optimal dalam berkeliling yang lebih berat dua kali lipat dari rentang pohon minimum.^[5]

Pada tahun 1976, [[Nicos Christofides}Christofides]] dan Sedyukov (Keduanya independen terhadap sesamanya) membuat kemajuan besar pada perkembangan permasalahan ini:^[9] Pada Algoritma Christofides-Serdyukov memberikan solusi, pada kasus terburuk pada kebanyakan 1.5 lebih panjang daripada solusi optimal. Sebagai algoritma termasuk simpel dan cepat, banyak berharap algoritma itu akan memberikan metode solusi mendekati optimal. Namun, harapan ini tidak begitu langsung terwujudkan, dan algoritma Christofides-Serdyukov tetap menjadi metode terbaik terhadap skenario terburuk hingga tahun 2011, saat terdapat ada algoritma aproksimasi yang (sedikit) membaik untuk dalam kelompok "grafik" TSP.^[10] In 2020, this tiny improvement was extended to the full (metric) TSP.^[11][12]

Richard M. Karp menampilkan pada tahun 1972 bahwa permasalahan Siklus Hamilton adalah NP-Complete, dimana menyiratkan bahwa permasalahan TSP itu adalah NP-Hard. Ini memberikan penjelasan matematis jelas untuk kesulitan komputasional untuk menemukan perjalanan yang optimal.

Progres besar terdapat pada tahun sekitar 1970 hingga 1980, saat Grötschel, Padberg, Rinaldi, dan yang lain berhasil dalam menyelesaikan instansial hingga setara 2.392 kota, menggunakan pemotongan bidang dan branch-and-bound.

Pada tahun 1990-an, Applegate, Bixby, Chvátal, dan Cook membuat sebuah program Concorde telah digunakan dalam banyak solusi. Gerhard Reinelt mempublikasikan TSPLIB pada tahun 1991, sebuah koleksi dari instansi dari kesulitan yang bervariasi, dimana telah digunakan dari banyak group riset untuk membandingkan hasilnya. Pada tahun 2006, Cook dan kawan-kawan mengkomputasi sebuah tur optimal melalui 85.900 kota diberikan oleh permasalahan mikro-chip, sekarang disebut sebagai instansi TSPLIB terbesar. Untuk banyak instansi dengan jutaan kota, solusi bisa ditemukan digaransikan diantara 2-3% dari tur optimalnya. ^[13]

TSP dapat dimodelkan sebagai grafik berbobot tak berarah, sedemikian rupa sehingga kota-kota adalah simpul grafik, jalur adalah sisi grafik, dan jarak jalur adalah bobot sisi. Ini adalah masalah minimisasi yang dimulai dan diakhiri pada simpul yang ditentukan setelah mengunjungi setiap simpul satu sama lain tepat sekali. Seringkali, modelnya adalah grafik lengkap (yaitu, setiap pasangan simpul dihubungkan oleh sebuah sisi). Jika tidak ada jalur antara dua kota, maka menambahkan sisi yang cukup panjang akan melengkapi grafik tanpa memengaruhi tur optimal.

Dalam TSP simetris, jarak antara dua kota sama di setiap arah yang berlawanan, membentuk grafik tak berarah. Simetri ini mengurangi separuh jumlah solusi yang mungkin. Dalam TSP asimetris, jalur mungkin tidak ada di kedua arah atau jaraknya mungkin berbeda, membentuk graf berarah. Kemacetan lalu lintas, jalan satu arah, dan tarif penerbangan untuk kota-kota dengan biaya keberangkatan dan kedatangan yang berbeda adalah pertimbangan dunia nyata yang dapat menghasilkan masalah TSP dalam bentuk asimetris.

• Formulasi yang setara dalam teori graf adalah: Diberikan graf berbobot lengkap (di mana simpul akan mewakili kota, sisi akan mewakili jalan, dan bobot akan menjadi biaya atau jarak jalan tersebut), temukan siklus Hamiltonian dengan bobot terkecil. Ini lebih umum daripada masalah jalur Hamiltonian, yang hanya menanyakan apakah jalur (atau siklus) Hamiltonian ada dalam graf tak berbobot yang tidak lengkap.

• Persyaratan untuk kembali ke kota awal tidak mengubah kompleksitas komputasi dari masalah tersebut; lihat masalah jalur Hamiltonian.

• Masalah terkait lainnya adalah masalah pedagang keliling yang mengalami hambatan: Temukan siklus Hamiltonian dalam graf berbobot dengan bobot minimal dari edge terberat. Contoh nyata adalah menghindari jalan-jalan sempit dengan bus besar.^[14] Masalah ini memiliki kepentingan praktis yang cukup besar, terlepas dari bidang transportasi dan logistik yang jelas. Contoh klasik terdapat dalam pembuatan papan sirkuit tercetak (PCB): penjadwalan rute mesin bor untuk mengebor lubang pada PCB. Dalam aplikasi pemesinan atau pengeboran robotik, "kota" adalah bagian yang akan diproses atau lubang (dengan ukuran berbeda) yang akan dibor, dan "biaya perjalanan" mencakup waktu untuk mengganti peralatan robot (masalah pengurutan pekerjaan mesin tunggal).^[15]
• Masalah masalah pedagang keliling umum, juga dikenal sebagai "masalah politisi keliling", berkaitan dengan "negara bagian" yang memiliki (satu atau lebih) "kota", dan pedagang harus mengunjungi tepat satu kota dari setiap negara bagian. Salah satu aplikasinya ditemukan dalam mengurutkan solusi untuk masalah pemotongan stok untuk meminimalkan perubahan pisau. Aplikasi lain berkaitan dengan pengeboran dalam manufaktur semikonduktor; lihat misalnya, Templat:Paten AS. Noon dan Bean menunjukkan bahwa masalah pedagang keliling umum dapat diubah menjadi TSP standar dengan jumlah kota yang sama, tetapi matriks jarak yang dimodifikasi.
• Masalah pengurutan sekuensial berkaitan dengan masalah mengunjungi sekumpulan kota, di mana terdapat hubungan prioritas antar kota.
• Pertanyaan wawancara umum di Google adalah bagaimana cara mengarahkan data di antara node pemrosesan data; Rute bervariasi berdasarkan waktu transfer data, tetapi node juga berbeda berdasarkan daya komputasi dan penyimpanannya, yang memperumit masalah ke mana data harus dikirim.
• travelling purchaser problem berkaitan dengan seorang pembeli yang bertugas membeli sejumlah produk. Ia dapat membeli produk-produk ini di beberapa kota, tetapi dengan harga yang berbeda, dan tidak semua kota menawarkan produk yang sama. Tujuannya adalah untuk menemukan rute antara sebagian kota yang meminimalkan total biaya (biaya perjalanan + biaya pembelian) dan memungkinkan pembelian semua produk yang dibutuhkan.

TSP dapat dirumuskan sebagai program linear bilangan bulat.^[16][17][18] Beberapa formulasi telah diketahui. Dua formulasi yang terkenal adalah formulasi Miller–Tucker–Zemlin (MTZ) dan formulasi Dantzig–Fulkerson–Johnson (DFJ). Formulasi DFJ lebih kuat, meskipun formulasi MTZ masih berguna dalam pengaturan tertentu.^[19][20]

Kesamaan dari kedua formulasi ini adalah bahwa kota-kota diberi label dengan angka ${\displaystyle 1,\ldots ,n}$ dan ${\displaystyle c_{ij}>0}$ dianggap sebagai biaya (jarak) dari kota ${\displaystyle i}$ ke kota ${\displaystyle j}$. Variabel utama dalam formulasi tersebut adalah:

${\displaystyle x_{ij}={\begin{cases}1&{\text{jalur tersebut berangkat dari kota }}i{\text{ ke kota }}j\\0&{\text{sebaliknya.}}\end{cases}}}$

Karena variabel-variabel ini adalah variabel 0/1, maka formulasi tersebut menjadi program bilangan bulat; semua kendala lainnya murni linier. Secara khusus, tujuan dalam program ini adalah untuk meminimalkan panjang rute

${\displaystyle \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}.}$

Tanpa batasan lebih lanjut, ${\displaystyle \{x_{ij}\}{i,j}}$ akan secara efektif mencakup semua himpunan bagian dari himpunan sisi, yang sangat jauh dari himpunan sisi dalam sebuah tur, dan memungkinkan minimum trivial di mana semua ${\displaystyle x{ij}=0}$. Oleh karena itu, kedua formulasi tersebut juga memiliki batasan bahwa, di setiap simpul, terdapat tepat satu sisi masuk dan satu sisi keluar, yang dapat dinyatakan sebagai persamaan linear ${\displaystyle 2n}$:

${\displaystyle \sum _{i=1,i\neq j}^{n}x_{ij}=1}$ untuk ${\displaystyle j=1,\ldots ,n}$ dan ${\displaystyle \sum _{j=1,j\neq i}^{n}x_{ij}=1}$ untuk ${\displaystyle i=1,\ldots ,n.}$

Hal ini memastikan bahwa himpunan sisi yang dipilih secara lokal terlihat seperti sebuah tur, tetapi tetap memungkinkan solusi yang melanggar persyaratan global bahwa ada satu tur yang mengunjungi semua simpul, karena sisi yang dipilih dapat membentuk beberapa tur, masing-masing hanya mengunjungi sebagian dari simpul; Bisa dibilang, persyaratan global inilah yang membuat TSP menjadi masalah yang sulit. Rumusan MTZ dan DFJ berbeda dalam cara mereka mengekspresikan persyaratan akhir ini sebagai kendala linier.