Perangkat lunak untuk merencanakan rute terpendek ke banyak alamat [ditutup]

8

Saya memiliki sekitar 300 alamat di sebuah kota dan saya mencoba mencari perangkat lunak yang dapat menyelesaikan masalah salesman keliling untuk itu. Saya sudah mencoba OptiMap solusi berbasis browser yang menggunakan Google API tapi itu dibatasi di 100 tujuan (Bahkan ketika Anda mengubah batas kode keras) dan browser yang saya coba akhirnya kehabisan memori. Saya tahu masalahnya NP sulit tetapi ini bukan masalah baru, pasti seseorang sudah menulis perangkat lunak. Satu-satunya solusi komersial yang saya lihat hanya berbasis di AS (ini adalah kota Australia) atau memiliki batas rendah.

Apakah ada perangkat lunak gratis atau komersial untuk menyelesaikan tugas ini dan ukurannya?

pengguna348998
sumber
2
Mungkin Anda dapat memecahkan masalah dalam potongan 100. Bisakah Anda memecah lokasi menjadi cluster dan memberi mereka makan ke OptiMap dalam potongan. Kemudian menangani transisi secara manual?
uSlackr
Saya selalu melihat masalah salesman keliling digunakan sebagai contoh, sesuatu seperti halo foobarbaz hal dunia. Sangat menyenangkan melihat bahwa ia memiliki potensi yang praktis. Omong-omong, NP keras atau tidak, algoritma genetika akan memberikan solusi yang sangat baik (tidak sempurna) dalam hitungan menit atau kurang. Juga, 300 alamat? Itu terlihat seperti situasi WTF yang tidak diperhitungkan oleh OptiMap. Ajukan bug?
Camilo Martin
Cari dengan kata kunci ini: optimasi pengiriman perangkat lunak logistik. Ada banyak perangkat lunak yang didedikasikan untuk masalah seperti ini. duckduckgo.com/…
climenole

Jawaban:

1

Tidak persis "gratis" - tetapi mungkin menerapkan algoritma perkiraan untuk TSP yang diuraikan dalam buku teks ini .

IIRC, ia memberikan solusi TSP untuk grafik planar faktor 2 dalam solusi optimal.

emptyset
sumber
1
Haha, +1 untuk jawaban "tulis algoritma ini"
Fopedush
Saya pikir itu lucu ketika orang berpikir mereka akan menemukan situs web dengan perangkat lunak tertulis khusus untuk menyelesaikan skenario spesifik mereka.
emptyset