Traveling Salesman Problem
Traveling Salesman Problem (TSP), menanyakan pertanyaan berikut: “Mengingat daftar kota dan jarak antara setiap pasangan kota, rute terpendek manakah yang dapat mengunjungi setiap kota tepat satu kali?” dan untuk kembali? Dia? Kampung halaman?” Ini adalah masalah NP-hard dalam optimasi kombinatorial, penting dalam ilmu komputer teoretis dan riset operasi. Masalah pembelanja yang bepergian dan masalah rute kendaraan merupakan generalisasi dari TSP.
Dalam teori kompleksitas komputasi, versi keputusan TSP (dengan panjang L, tugasnya adalah memutuskan apakah grafik memiliki paling banyak satu jalur dengan panjang L) termasuk dalam kelas masalah NP-lengkap.Oleh karena itu, ada kemungkinan bahwa waktu eksekusi kasus terburuk untuk algoritma TSP meningkat secara superpolinomik (tetapi tidak lebih dari eksponensial) dengan jumlah kota.
Masalah ini pertama kali dirumuskan pada tahun 1930 dan merupakan salah satu masalah optimasi yang paling banyak dipelajari. Ini digunakan sebagai titik referensi untuk banyak metode optimasi. Meskipun permasalahannya sulit secara komputasi, banyak heuristik dan algoritma yang sesuai telah diketahui, sehingga beberapa kejadian dengan puluhan ribu kota dapat diselesaikan sepenuhnya, dan bahkan permasalahan dengan jutaan kota dapat didekati dengan sepersekian 1%.
Sejarah
Asal usul masalah pekerja lapangan tidak jelas. Panduan perjalanan tahun 1832 menyebutkan masalah tersebut dan menyertakan contoh perjalanan di Jerman dan Swiss, tetapi tidak memuat penjelasan matematis.
TSP dirumuskan secara matematis pada abad ke-19 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Kirkman. Permainan Icosian Hamiltonian adalah teka-teki rekreasional yang didasarkan pada penemuan siklus Hamiltonian. Bentuk umum TSP tampaknya pertama kali dipelajari pada tahun 1930-an oleh ahli matematika di Wina dan Harvard, terutama Karl Menger, yang mendefinisikan masalahnya, mempertimbangkan algoritma brute force yang terdefinisi dengan baik, dan mengamati ketidakoptimalan.
Traveling Salesman Problem (TSP) awalnya muncul pada tahun 1930an ketika Merrill M. Flood mencoba memecahkan tantangan perencanaan rute bus sekolah secara matematis. Menariknya, Hassler Whitney dari Universitas Princeton memberikan sentuhan pribadi pada masalah ini dengan menyebutnya sebagai “masalah 48 negara bagian,” sehingga memicu minat awal terhadap topik tersebut. Pada tahun 1950an dan 1960an, popularitas TSP meningkat setelah RAND Corporation menawarkan hadiah kepada mereka yang dapat menyelesaikannya.
Namun, titik kritis dalam pengembangan TSP terjadi pada tahun 1950an dan 1960an, ketika George Dantzig, Delbert Ray Fulkerson, dan Selmer M.Johnson dari RAND Corporation mengembangkan metode bidang potong untuk mengatasi masalah ini. Meskipun kontribusi ini tidak memberikan solusi algoritmik langsung, kontribusi ini memberikan dasar yang sangat penting untuk pengembangan metode solusi yang lebih akurat di masa depan.
Akhirnya, pada tahun 1959, Jillian Beardwood, JH Halton, dan John Hammersley memberikan solusi praktis dengan teorema Beardwood-Halton-Hammersley, menandai perkembangan lebih lanjut dalam pengobatan PST. Pada tahun 1960-an, ada pendekatan baru yang berfokus pada pembuatan batas bawah dengan mengalikan pohon rentang minimum suatu grafik.
Hal ini membuka jalan bagi metode cabang-dan-gabung, yang menjadi pendekatan penting untuk mengatasi TSP.Selama dekade berikutnya, kemajuan signifikan dicapai pada akhir tahun 1970an dan 1980an, ketika Grötschel, Padberg, Rinaldi, dan peneliti lain memecahkan kasus TSP di 2.392 kota. Pada tahun 1990-an, muncul program Concorde dan TSPLIB yang berperan penting dalam pengembangan dan benchmarking algoritma TSP. Sebuah tonggak sejarah dicapai pada tahun 2006 dengan perhitungan rute optimal untuk 85.900 contoh masalah distribusi microchip perkotaan.Semua ini mencerminkan kemajuan luar biasa dalam pengobatan TSP selama beberapa dekade terakhir.
Deskrpsi
Sebagai Masalah Grafik
TSP dapat dimodelkan sebagai graf tak berarah berbobot, sehingga kota adalah simpul dari graf tersebut, jalan adalah sisinya, dan jarak suatu lintasan adalah bobot sisinya. Ini adalah masalah minimalisasi yang dimulai pada titik tertentu dan berakhir setelah mengunjungi titik lain tepat satu kali. Seringkali modelnya berupa graf lengkap (yaitu setiap pasangan simpul dihubungkan oleh sebuah sisi). Jika tidak ada jalur antara dua kota, menambahkan sisi yang cukup panjang akan melengkapi grafik tanpa mempengaruhi jalur optimal.
Asimetris dan simetris
Pada TSP simetris, jarak antara dua kota sama besar pada setiap arah yang berlawanan sehingga membentuk grafik tidak berarah. Simetri ini mengurangi separuh jumlah solusi yang mungkin. Dalam TSP asimetris, jalur di kedua arah mungkin tidak ada atau jaraknya mungkin berbeda, sehingga menghasilkan grafik berarah. Kemacetan lalu lintas, jalan satu arah, dan tarif penerbangan kota dengan biaya keberangkatan dan kedatangan yang berbeda menjadi pertimbangan nyata yang secara asimetris dapat menimbulkan masalah TSP.
Disadur dari: en.wikipedia.org