Selain lelucon, saya memiliki masalah routing yang hampir menjadi masalah salesman keliling (TSP):
- titik awal didefinisikan
- titik akhir bertepatan dengan titik awal
- setiap node harus dikunjungi
- total biaya harus diminimalkan
Dua tahun lalu saya pikir TSP akan menjadi pasangan yang sempurna, jadi saya menjalankan beberapa sampel data tsp_solvedan Concorde. Untungnya, dengan cepat jelas bahwa jalur terpendek TSP bukan jalan terpendek yang sebenarnya , karena masalahnya menjadi lebih mudah dengan secara tidak realistis mengharuskan node dikunjungi tepat sekali . Gambar ini hanyalah upaya manual satu langkah untuk mengoptimalkan solusi yang dihitung dan sudah menghemat jarak tepi terpanjang yang digunakan.
Masalahnya muncul kembali, karena saya mencoba mencari rute optimal ke subset dari situs pemetaan / pemantauan. Data lokasi dan jaringan jalan cukup akurat dan tepat, sehingga latihan seperti ini masuk akal.
Saya telah melihat generalisasi TSP, tetapi tidak menemukan algoritma yang sesuai. Pohon spanning minimum tidak memperhitungkan pengembalian dari cabang (solusi pertama di sini harganya 3 lebih). Dari apa yang saya pahami, masalah jalur terpendek akhirnya hanya peduli pada dua node dan mereka yang keluar dari jalur optimal akan ditinggalkan. Kasus khusus masalah perutean kendaraan tampaknya paling cocok, meskipun saya tidak tahu apakah ini menganggap jalur tidak langsung.
Pertanyaan saya: apakah ada nama tetap, definisi untuk masalah seperti ini (keluarga)? Algoritma dan alat apa yang akan Anda gunakan untuk menyelesaikannya?
Saya yakin ini akan berat secara komputasi, tetapi saya tertarik pada jawaban umum (sumber daya tak terbatas) dan praktis.
sumber
Jawaban:
Ini TSP . Anda hanya belum menetapkan metrik jarak yang valid karena tidak memenuhi ketimpangan segitiga: jika ada rute dari A ke C hingga B yang lebih pendek dari jarak yang dinyatakan dari A ke C, maka jarak yang dinyatakan dari A ke C cukup sederhana, salah. Solusinya adalah memperbarui matriks jarak dengan mengatur panjang dari A ke C menjadi panjang terpendek dari semua rute dari A ke C.
sumber