Penjelasan masalah pedagang keliling

Berikan daftar kota kepada seorang pedagang dan mintalah perjalanan terpendek yang mengunjungi setiap kota satu kali lalu kembali ke rumah. Siapa pun dapat memeriksa rute yang diusulkan, dan siapa pun dapat memperbaiki rute yang buruk hanya dengan melihatnya, tetapi tidak ada yang mengetahui metode cepat yang selalu menemukan rute terbaik. Masalah pedagang keliling telah menjadi contoh baku masalah sulit, dan metode yang diciptakan untuk menaklukkannya kini merencanakan pengiriman, mengebor papan sirkuit, dan merakit genom.

Peta kota-kota yang dihubungkan oleh sebuah rute tertutup, dengan kota awal ditandai dan rute lain yang lebih pendek tampak samar di bawahnya
Peta kota-kota yang dihubungkan oleh sebuah rute tertutup, dengan kota awal ditandai dan rute lain yang lebih pendek tampak samar di bawahnya

Masalahnya

Sebuah rute mengunjungi setiap kota tepat satu kali dan berakhir di tempat asalnya; panjangnya adalah jumlah jarak di sepanjang jalan. Tugasnya adalah menemukan rute terpendek. Dalam versi di sini, jaraknya berupa garis lurus di peta, sehingga perjalanan dari A ke C tidak pernah lebih panjang daripada melalui B: inilah masalah pedagang keliling metrik. Teka-teki ini dibahas oleh matematikawan Karl Menger sekitar tahun 1930, dan namanya menjadi umum pada dekade-dekade berikutnya, ketika para matematikawan di RAND Corporation menelitinya.

Karl Menger pada 1970. Ia membahas masalah salesman keliling sekitar 1930.
Karl Menger pada 1970. Ia membahas masalah salesman keliling sekitar 1930.

Ledakan jumlah rute

Tetapkan kota awal. Ada n − 1 pilihan untuk kota berikutnya, n − 2 untuk kota sesudahnya, dan seterusnya, dan setiap rute dapat dijalani ke dua arah, sehingga terdapat (n − 1)! / 2 rute. Untuk 10 kota jumlahnya 181.440, mudah bagi komputer. Untuk 20 kota sekitar 6 × 10¹⁶, dan untuk 70 kota jumlahnya melampaui banyaknya atom di alam semesta teramati. Komputer yang lebih cepat tidak banyak membantu: setiap kota tambahan melipatgandakan pekerjaan sekitar n kali.

NP-hard

Pada tahun 1972 Richard Karp menunjukkan bahwa pertanyaan apakah sebuah graf memiliki rute keliling yang melewati setiap simpul, yaitu siklus Hamilton, termasuk dalam keluarga masalah NP-complete yang semuanya sama sulitnya. Masalah pedagang keliling memuat pertanyaan itu, sehingga bersifat NP-hard. Metode cepat untuknya akan memberikan metode cepat bagi ribuan masalah lain dalam penjadwalan, logistik, dan kriptografi. Apakah metode semacam itu ada merupakan pertanyaan P versus NP, salah satu Masalah Hadiah Milenium.

Metode eksak: Held–Karp

Pada tahun 1962 Michael Held dan Richard Karp, dan secara terpisah Richard Bellman, menggunakan pemrograman dinamis. Untuk setiap himpunan kota S dan setiap kota j di S, hitung jalur terpendek yang berawal di kota asal, mengunjungi tepat kota-kota di S, dan berakhir di j. Setiap nilai diperoleh dari nilai untuk S tanpa j, sehingga tabel diisi dari himpunan kecil ke himpunan besar, dan rute terpendek muncul di akhir. Metode ini membutuhkan sekitar n² · 2ⁿ langkah alih-alih n!, yang untuk 30 kota berarti perbedaan antara hitungan menit dan umur alam semesta, tetapi tetap tumbuh secara eksponensial.

Richard Bellman pada tahun 1962, difoto oleh Alfred Eisenstaedt. Ia menamai pemrograman dinamis pada awal 1950-an ketika bekerja di RAND Corporation.
Richard Bellman pada tahun 1962, difoto oleh Alfred Eisenstaedt. Ia menamai pemrograman dinamis pada awal 1950-an ketika bekerja di RAND Corporation.

Aturan penyusunan cepat

Tetangga terdekat selalu menuju kota terdekat yang belum dikunjungi. Metode ini sederhana dan cepat, tetapi cenderung meninggalkan beberapa kota yang harus dijemput dengan jalan memutar yang panjang di akhir, sehingga rutenya biasanya sekitar 25% lebih panjang daripada yang terbaik. Metode penyisipan justru mempertahankan sebuah putaran tertutup dan menambahkan kota yang tersisa satu per satu di tempat yang paling murah. Pada tahun 1976 Nicos Christofides menemukan cara penyusunan yang dijamin paling banyak 1,5 kali nilai optimum pada peta metrik mana pun, batas yang hampir tak terkalahkan selama lebih dari empat puluh tahun.

Memperbaiki rute: 2-opt

Pencarian lokal dimulai dari rute apa saja dan terus melakukan perubahan kecil yang memperpendeknya. Gerakan klasiknya, 2-opt, menghapus dua sisi dan menyambungkan kembali kedua potongan dengan cara sebaliknya, sehingga bagian di antaranya terbalik. Setiap kali dua sisi bersilangan, gerakan ini mengurai persilangan itu dan menghemat panjang, sehingga rute yang tidak dapat diperbaiki lagi oleh 2-opt tidak pernah memotong dirinya sendiri. Pada peta acak, rute 2-opt biasanya sekitar 5% di atas optimum. Gerakan yang lebih kuat yang menukar tiga sisi, atau metode kedalaman variabel dari Lin dan Kernighan tahun 1973, mendekat lebih jauh lagi.

Simulated annealing

Pencarian lokal bisa terjebak pada rute yang setiap gerakan tunggalnya justru memperburuk, padahal ada rute yang jauh lebih baik. Simulated annealing, yang diterapkan pada masalah ini oleh Scott Kirkpatrick, Daniel Gelatt, dan Mario Vecchi pada tahun 1983, meminjam ide dari metalurgi: metode ini menerima gerakan yang memperburuk dengan peluang yang bergantung pada suhu, yang tinggi di awal lalu diturunkan perlahan. Di awal, rute berkelana dengan bebas; di akhir, hanya perbaikan yang diterima. Dengan pendinginan yang cukup lambat, metode ini dapat diandalkan untuk menemukan rute yang sangat baik.

Jelajahi sendiri

Buka demo pedagang keliling untuk menempatkan hingga 200 kota secara acak, pada lingkaran, dalam kelompok, pada kisi, atau di mana pun Anda mengklik. Saksikan tetangga terdekat meninggalkan kota-kota terakhirnya, lihat 2-opt mengurai setiap persilangan, ikuti suhu simulated annealing saat mendingin, dan biarkan Held–Karp membuktikan rute terpendek untuk hingga 12 kota. Bandingkan semua menjalankan setiap metode pada peta yang sama dan menunjukkan seberapa jauh setiap rute di atas rute terpendek yang ditemukan.

Pertanyaan yang sering diajukan

Di mana masalah pedagang keliling digunakan?

Di mana pun sesuatu harus mengunjungi banyak tempat dalam urutan yang efisien: rute pengiriman dan penjemputan, lintasan bor atau laser di atas papan sirkuit, urutan teleskop mengamati bintang, urutan pengambilan barang di gudang, dan, dengan jarak yang berbeda, urutan fragmen saat merakit sekuens DNA.

Berapa masalah terbesar yang pernah terpecahkan secara eksak?

Pada tahun 1954 George Dantzig, Ray Fulkerson, dan Selmer Johnson membuktikan rute terpendek melalui 49 kota di Amerika Serikat. Pada tahun 2006 pemecah Concorde karya David Applegate, Robert Bixby, Vašek Chvátal, dan William Cook membuktikan rute optimal melalui 85.900 titik dari sebuah desain chip, setelah bertahun-tahun waktu komputasi.

Apakah rute terpendek selalu bebas persilangan?

Ya, pada peta datar dengan jarak garis lurus. Jika dua sisi bersilangan, menukarnya dengan dua sisi dari segi empat yang dibentuknya akan memperpendek rute, sehingga rute yang bersilangan tidak mungkin menjadi yang terpendek.

Apakah heuristik selalu memberikan rute yang sama?

Tetangga terdekat, penyisipan termurah, dan 2-opt seperti yang digunakan di sini bersifat deterministik: pada kota-kota yang sama, ketiganya memberikan rute yang sama. Simulated annealing dimulai dari rute acak dan melakukan gerakan acak, sehingga dua kali menjalankannya bisa berakhir dengan rute berbeda, biasanya dengan panjang yang hampir sama.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka demo pedagang keliling