Bagaimana Anda membuat daftar jalan yang dioptimalkan mengingat koordinat bujur dan lintang?

Saya sedang mengerjakan kampanye politik di mana lusinan sukarelawan akan melakukan promosi mengetuk pintu selama beberapa minggu ke depan. Diberikan daftar dengan nama, alamat, dan koordinat panjang / lat, algoritma apa yang dapat digunakan untuk membuat daftar jalan yang dioptimalkan.

Seperti yang dikatakan Steve Kallestad, ini adalah masalah TSP, dan ada pemecah gratis yang hebat untuk menemukan solusi perkiraan.

Mungkin terlalu banyak pekerjaan untuk apa yang Anda cari, tetapi Anda dapat mencoba menggunakan salah satu pemecah tersebut dalam kombinasi dengan Google Maps API, untuk menemukan jarak berjalan nyata di antara koordinat Anda: https://developers.google.com/maps / dokumentasi / arah / # DirectionRequests

(Saya belum pernah menggunakan API ini, jadi saya tidak tahu seberapa mudah atau efektifnya itu)

Orang-orang melihat sesuatu yang berkaitan erat dengan Traveling Salesman Problem dan berpikir bahwa itu tidak dapat diselesaikan.

Banyak pekerjaan telah dilakukan pada topik ini dan tidak semuanya menunjukkan bahwa solusi tidak tersedia. Bergantung pada parameter dan solusi yang diinginkan, Anda mungkin dapat menemukan sesuatu yang akan berfungsi.

Anda mungkin ingin melihat pada OpenOpt python .

Sumber daya lain untuk dilihat adalah Solver dan Generator TSP .

Jika Anda menggunakan R, ada paket TSP yang tersedia .

Sebenarnya menerapkan solusi untuk masalah Anda agak terlalu banyak untuk dibahas di sini, tetapi ini harus memberikan titik awal yang baik. Di dalam paket-paket ini dan pada dokumentasi di dalam tautan yang saya berikan untuk Anda, Anda akan menemukan bahwa ada berbagai macam strategi algoritmik yang tersedia. Anda memiliki wilayah geografis yang kecil dan "tenaga penjualan" yang kecil, sehingga kekuatan komputasi yang diperlukan untuk menghitung strategi dalam kerangka waktu yang masuk akal harus tersedia di desktop Anda.

Secara praktis, Anda tidak perlu menemukan strategi yang paling optimal. Anda hanya perlu yang sangat bagus. Pilih paket TSP yang terlihat paling tidak biasa dan cobalah.

Seperti @SpacedMan telah mencatat dalam komentar , tata letak jalan akan memiliki pengaruh besar pada optimalisasi daftar jalan kaki. Anda hanya memasukkan "garis lintang dan bujur" dalam judul pertanyaan Anda; tetapi menyelesaikan masalah itu tidak mengarah pada "daftar jalan", tetapi ke "daftar as-the-crow-lalat".

Melihat tata jalan Anda sebagai grafik, dengan bobot tepi yang menggambarkan jarak, dan mencoba menemukan lintasan terpendek di antara semua alamat yang diperlukan, akan mengarahkan Anda untuk memikirkan masalah Anda sebagai " Masalah jalur terpendek ". Algoritma Dijkstra adalah solusi yang paling dikenal (ada yang lain); dalam implementasi naifnya konvergen dalam O (n ² ) , yang mungkin dapat diterima jika daftar alamat Anda berukuran sedang. Jika tidak, cari versi yang dioptimalkan di tautan di atas.

Mengenai perpustakaan dan sumber daya untuk mulai menangani masalah, karena Anda tidak menentukan bahasa atau platform, izinkan saya arahkan ke kompilasi perute perutean di wiki Peta Jalan Terbuka dan secara umum kerangka kerja dan halaman perpustakaan mereka .

Inilah ide gila: berbicara dengan sukarelawan yang mengetahui lingkungan sekitar dan yang telah melakukan pekerjaan dari rumah ke rumah sebelumnya. Dapatkan saran dan ide mereka. Mereka mungkin akan memiliki wawasan bahwa algoritma tidak akan menghasilkan, dan modifikasi itu akan berharga untuk daftar rute yang dihasilkan komputer. Salah satu contoh: Menghindari persimpangan jalan yang sering dilalui dengan lampu lambat atau tanpa lampu. Contoh lain: pasangan relawan yang bekerja di sisi berlawanan dari jalan yang sama akan merasa lebih aman daripada relawan yang bekerja di jalan itu sendirian.