The Travelling Salesman Problem (TSP) adalah masalah dalam optimasi kombinatorial belajar di riset operasi dan ilmu komputer teoritis. Diberikan daftar kota dan jarak berpasangan, tugas ini adalah untuk menemukan sesingkat mungkin tur yang dilihat setiap kota tepat satu kali.Masalahnya ini pertama kali dirumuskan sebagai masalah matematika pada tahun 1930 dan merupakan salah satu masalah yang paling intensif dipelajari di optimasi. Ini digunakan sebagai patokan bagi banyak metode optimasi. Meskipun masalahnya komputasi sulit, sejumlah besar heuristik dan metode yang tepat diketahui, sehingga beberapa hal dengan puluhan ribu kota dapat dipecahkan.
TSP memiliki beberapa aplikasi bahkan dalam rumusan yang paling murni, seperti perencanaan, logistik, dan pembuatan microchip. Sedikit dimodifikasi, itu muncul sebagai sub-masalah di banyak daerah, seperti DNA sequencing. Dalam aplikasi ini, konsep mewakili kota, misalnya, pelanggan, pematrian poin, atau fragmen DNA, dan konsep mewakili jarak perjalanan waktu atau biaya, atau ukuran kesamaan antara fragmen-fragmen DNA. Dalam banyak aplikasi, hambatan tambahan seperti sumber daya yang terbatas atau waktu jendela membuat masalah jauh lebih keras.
Dalam teori kompleksitas komputasi, versi keputusan TSP termasuk dalam kelas NP-lengkap masalah. Dengan demikian, diasumsikan bahwa tidak ada efisien algoritma untuk memecahkan TSPs. Dengan kata lain, kemungkinan bahwa kasus terburuk berjalan waktu untuk setiap algoritma untuk TSP meningkat secara eksponensial dengan jumlah kota, jadi bahkan beberapa kasus dengan hanya ratusan kota akan memakan waktu bertahun-tahun untuk memecahkan CPU tepat.
Sejarah
Asal-usul masalah salesman keliling tidak jelas. Sebuah buku panduan untuk perjalanan salesman dari 1832 menyebutkan contoh masalah dan termasuk tur melalui Jerman dan Swiss, tetapi tidak mengandung matematis. [2]William Rowan Hamilton
Matematis permasalahan yang terkait dengan masalah salesman keliling diperlakukan di tahun 1800-an oleh matematikawan Irlandia WR Hamilton dan oleh matematikawan Inggris Thomas Kirkman. Hamilton Icosian Game adalah sebuah teka-teki berdasarkan rekreasi menemukan siklus Hamiltonian. [3] Bentuk umum dari TSP tampaknya telah dipelajari oleh matematikawan pertama selama tahun 1930-an di Wina dan di Harvard, terutama oleh Karl Menger, yang mendefinisikan masalah, menganggap yang jelas algoritma brute force, dan mengamati non-optimal dari tetangga terdekat heuristic:
Kita menyatakan masalah kurir (karena dalam praktiknya pertanyaan ini harus dipecahkan oleh masing-masing pos, bagaimanapun juga oleh banyak wisatawan) tugas untuk menemukan, untuk finitely banyak poin yang berpasangan jarak diketahui, rute terpendek yang menghubungkan titik-titik. Tentu saja, masalah ini dipecahkan oleh finitely banyak cobaan. Aturan yang akan mendorong jumlah pengadilan di bawah jumlah permutasi dari titik yang diberikan, tidak diketahui. Aturan bahwa orang pertama harus pergi dari titik awal ke titik terdekat, lalu ke titik paling dekat dengan ini, dan sebagainya, pada umumnya tidak menghasilkan rute terpendek. [4]
Hassler Whitney di Universitas Princeton memperkenalkan nama masalah salesman keliling segera setelah. [5]
Tahun 1950-an dan 1960-an, masalah menjadi semakin populer di kalangan ilmiah di Eropa dan Amerika Serikat. Kontribusi penting dibuat oleh George Dantzig, Delbert Ray Fulkerson dan Selmer M. Johnson di RAND Corporation di Santa Monica, yang mengungkapkan masalah sebagai suatu program linier integer dan mengembangkan pesawat memotong metode untuk pemecahannya. Dengan metode baru ini mereka memecahkan sebuah contoh dengan 49 kota untuk optimalitas dengan membangun sebuah tur dan membuktikan bahwa tidak ada tur lainnya bisa lebih pendek. Dalam dekade berikutnya, masalah ini dipelajari oleh banyak peneliti dari matematika, ilmu komputer, kimia, fisika, dan ilmu-ilmu lainnya.
Richard M. Karp pada tahun 1972 menunjukkan bahwa siklus Hamiltonian masalah adalah NP-lengkap, yang menyiratkan kekerasan NP-TSP. Ini diberikan penjelasan ilmiah komputasi yang tampak kesulitan menemukan tur yang optimal.
Kemajuan besar dibuat pada akhir tahun 1970 dan 1980, ketika Grötschel, Padberg, Rinaldi dan berhasil menyelesaikan kasus dengan tepat sampai dengan 2392 kota-kota, dengan menggunakan pesawat dan memotong cabang-and-bound.
Pada 1990-an, Applegate, Bixby, Chvátal, dan Cook Concorde mengembangkan program yang telah digunakan dalam banyak rekor baru solusi. Gerhard Reinelt menerbitkan TSPLIB pada tahun 1991, kumpulan contoh benchmark dari berbagai kesulitan, yang telah digunakan oleh banyak kelompok-kelompok penelitian untuk membandingkan hasil. Pada tahun 2005, Cook dan lain-lain dihitung tur yang optimal melalui kota 33.810 contoh yang diberikan oleh masalah tata letak microchip, saat ini terpecahkan TSPLIB terbesar misalnya. Bagi banyak contoh lain dengan jutaan kota, dapat ditemukan solusi yang provably dalam waktu 1% dari tur yang optimal.
Deskripsi
Sebagai masalah grafik
TSP simetris dengan empat kota. TSP dapat dimodelkan sebagai grafik, seperti kota-kota yang grafik's vertices, jalan adalah grafik yang pinggiran, dan jarak jalan adalah tepi yang panjang. Sebuah tur TSP menjadi siklus Hamiltonian, dan TSP tur yang optimal adalah siklus Hamiltonian terpendek. Seringkali, model adalah grafik lengkap (yaitu keunggulan masing-masing pasangan menghubungkan simpul). Jika tidak ada jalan yang ada di antara dua kota, menambahkan secara sewenang-wenang tepi panjang akan menyelesaikan grafik tanpa mempengaruhi tur yang optimal.asimetrik dan simetrik
Dalam TSP simetris, jarak antara dua kota adalah sama di setiap arah, membentuk sebuah grafik diarahkan. Simetri ini akan membagi dua jumlah kemungkinan solusi. Dalam TSP asimetris, jalan mungkin tidak ada di kedua arah atau jarak mungkin berbeda, membentuk sebuah grafik diarahkan. Lalu Lintas tabrakan, jalan satu arah, dan tiket untuk kota-kota dengan berbagai biaya kedatangan dan keberangkatan adalah contoh bagaimana simetri ini bisa istirahat turun.
Dengan jarak metrik
Dalam TSP metrik jarak antar memuaskan ketidaksamaan segitiga. Hal ini dapat dipahami sebagai "ada jalan pintas", dalam arti bahwa hubungan langsung dari A ke B tidak pernah lebih panjang daripada jalan memutar melalui C.
Tepi ini menentukan panjang metrik pada himpunan simpul. Ketika kota-kota dipandang sebagai titik-titik di pesawat, banyak alam fungsi jarak adalah metrik.
- Dalam TSP Euclidian jarak antara dua kota adalah jarak Euclidean antara titik yang sesuai.
- Dalam TSP bujursangkar jarak antara dua kota adalah jumlah dari perbedaan-perbedaan koordinat x dan y. Metrik ini sering disebut jarak Manhattan atau kota-blok metrik.
- Dalam metrik maksimum, jarak antara dua titik adalah maksimum perbedaan koordinat x dan y.
Yang terakhir muncul dua metrik routing misalnya dalam sebuah mesin yang latihan himpunan lubang dalam sebuah printed circuit board. Metrik Manhattan berkaitan dengan suatu mesin yang pertama mengatur koordinasi, dan kemudian yang lain, sehingga waktu untuk pindah ke sebuah titik yang baru adalah jumlah dari kedua gerakan. Metrik maksimum sesuai dengan mesin yang baik menyesuaikan koordinat secara bersamaan, sehingga waktu untuk pindah ke sebuah titik yang baru adalah lebih lambat dari dua gerakan.
Non-metrik jarak
Jarak langkah-langkah yang tidak memenuhi ketidaksamaan segitiga muncul dalam banyak routing masalah. Sebagai contoh, salah satu moda transportasi, seperti bepergian dengan pesawat udara, mungkin akan lebih cepat, meskipun itu mencakup jarak yang lebih panjang.
Dalam definisinya, TSP tidak mengijinkan kota-kota untuk dikunjungi dua kali, tetapi banyak aplikasi yang tidak perlu kendala ini. Dalam kasus tersebut, yang simetris, non-metrik misalnya dapat dikurangi dengan satu metrik. Menggantikan yang asli ini grafik dengan grafik yang lengkap di mana jarak antar kota c i j digantikan oleh jalan terpendek antara i dan j dalam grafik asli.
terkait masalah
- Yang setara dalam hal perumusan teori grafik adalah: Diketahui sebuah grafik berbobot lengkap (di mana simpul akan mewakili kota-kota, ujung-ujungnya akan mewakili jalan, dan bobotnya akan menjadi biaya atau jarak dari jalan itu), menemukan siklus Hamiltonian dengan yang paling berat.
- Persyaratan kembali ke kota awal tidak mengubah kompleksitas komputasi dari masalah, lihat jalur Hamiltonian masalah.
- Masalah terkait lainnya adalah masalah salesman keliling bottleneck (bottleneck TSP): Menemukan siklus Hamiltonian dalam grafik berbobot dengan berat minimal weightiest tepi. Masalahnya adalah cukup praktis, selain transportasi dan logistik jelas daerah. Sebuah contoh klasik adalah sirkuit tercetak manufaktur: penjadwalan rute dari bor mesin bor lubang-lubang dalam PCB. Dalam pengeboran robot mesin atau aplikasi, "kota" adalah bagian untuk mesin atau lubang (dengan ukuran yang berbeda) untuk latihan, dan "biaya perjalanan" termasuk waktu untuk memperbarui peralatan robot (mesin satu masalah sequencing pekerjaan).
- Salesman keliling yang digeneralisasi masalah berkaitan dengan "negara" yang memiliki (satu atau lebih) "kota" dan si penjual telah untuk mengunjungi tepat satu "kota" dari masing-masing "negara". Juga dikenal sebagai "politikus bepergian masalah". Satu aplikasi ini ditemui dalam memesan solusi untuk masalah saham pemotongan untuk meminimalisasi perubahan pisau. Lain berkaitan dengan pengeboran di manufaktur semikonduktor, lihat misalnya US Patent 7.054.798. Anehnya, Behzad dan Modarres [6] menunjukkan bahwa masalah salesman keliling generalised dapat diubah menjadi standar salesman keliling masalah dengan jumlah yang sama dari kota, tetapi yang dimodifikasi matriks jarak.
Garis tradisional serangan untuk masalah NP-keras adalah sebagai berikut:
- Menyusun algoritma untuk mencari solusi yang tepat (mereka akan bekerja cukup cepat hanya untuk masalah ukuran relatif kecil).
- Merancang "optimal" atau heuristik algoritma, yaitu algoritma yang memberikan baik tampaknya atau mungkin solusi yang baik, tetapi yang tidak dapat dibuktikan untuk menjadi optimal.
- Menemukan kasus khusus untuk masalah ( "subproblems") yang lebih baik atau persis heuristik yang mungkin.
Masalahnya telah terbukti NP-keras (lebih tepatnya, hal ini sudah selesai untuk kelas kompleksitas NP FP; melihat masalah fungsi), dan masalah keputusan versi ( "diberi biaya dan sejumlah x, memutuskan apakah ada bundar rute perjalanan lebih murah dari x ") adalah NP-lengkap. Para salesman keliling masalah kemacetan juga NP-keras. Masalah tetap NP-keras bahkan untuk kasus ketika kota-kota berada di pesawat dengan jarak Euclidean, serta dalam sejumlah kasus restriktif lainnya. Menghapus kondisi masing-masing mengunjungi kota "hanya sekali" tidak menghapus NP-kekerasan, karena dengan mudah terlihat bahwa dalam kasus planar optimal ada tur yang dilihat masing-masing kota hanya sekali (jika tidak, oleh ketidaksamaan segitiga, jalan pintas yang melompat kunjungan berulang tidak akan meningkatkan tur panjang).
Kompleksitas aproksimasi
Pada kasus yang umum, menemukan terpendek salesman keliling tur NPO-selesai. [7] Jika mengukur jarak adalah metrik dan simetris, masalahnya menjadi apX-lengkap [8] dan algoritma Christofides mendekati dalam waktu 3 / 2. [9 ] Jika jarak dibatasi pada 1 dan 2 (tapi masih adalah metrik) pendekatan rasio menjadi 7 / 6. Dalam asimetris, metrik kasus, hanya menjamin kinerja logaritmik diketahui, algoritma yang terbaik saat ini rasio kinerja mencapai 0,814 log n; [10] itu adalah sebuah pertanyaan terbuka jika ada pendekatan faktor konstan.
Masalah maksimisasi yang sesuai untuk menemukan salesman keliling terpanjang tur approximable dalam 63/38. [11] Jika fungsi jarak simetris, tur terpanjang yang dapat diperkirakan dalam waktu 4 / 3 oleh algoritma deterministik [12] dan dalam (33 + ?) / 25 oleh algoritma acak. [13]
Sesuai algoritma
Solusi yang paling langsung akan mencoba semua permutasi (kombinasi memerintahkan) dan melihat mana yang termurah (menggunakan kekerasan pencarian). Yang sedang berjalan waktu untuk pendekatan ini terletak dalam faktor polinom O (n!), Yang faktorial dari beberapa kota, jadi solusi ini menjadi tidak praktis bahkan untuk hanya 20 kota. Salah satu aplikasi yang paling awal pemrograman dinamis adalah suatu algoritma yang memecahkan masalah dalam waktu O (n 2 2 n) [14]
Solusi pemrograman yang dinamis membutuhkan ruang eksponensial. Menggunakan inklusi-eksklusi, masalah dapat diselesaikan dalam waktu polinomial dalam faktor 2 n dan ruang polinomial. [15]
Sebagai contoh, ini adalah masalah terbuka jika ada algoritma yang tepat untuk TSP yang berjalan dalam waktu O (1,9999 n) [16]
Pendekatan-pendekatan lain termasuk:
- Berbagai cabang-and-bound algoritma, yang dapat digunakan untuk memproses TSPs mengandung 40-60 kota.
- Perbaikan progresif algoritma yang menggunakan teknik mengingatkan pada pemrograman linear. Works well for up to 200 cities. Bekerja dengan baik untuk 200 kota.
- Implementasi dari cabang-dan-terikat dan masalah-generasi memotong spesifik, ini adalah metode pilihan untuk menyelesaikan kasus-kasus besar. Pendekatan ini memegang rekor saat ini, penyelesaian sebuah contoh dengan 85.900 kota, lihat Applegate (2006)
Pada bulan Maret 2005, masalah salesman keliling mengunjungi seluruh 33.810 titik dalam sebuah papan sirkuit dipecahkan menggunakan TSP Concorde Solver: sebuah tur panjang unit 66.048.945 ditemukan dan sudah terbukti bahwa tidak ada tur pendek ada. Perhitungan CPU mengambil kira-kira 15,7 tahun (Cook et al. 2006). Pada bulan April 2006 sebuah contoh dengan poin 85.900 dipecahkan menggunakan TSP Concorde Solver, mengambil alih CPU 136 tahun, lihat Applegate (2006).
Tidak ada komentar:
Posting Komentar
Tinggalkan Komentar :