Optimalisasi rute untuk beberapa kendaraan

12

Saya memiliki 100 tujuan dan 5 kendaraan dan saya perlu membuat kode solusi yang secara efisien mengarahkan kendaraan ke setiap tujuan, sehingga setiap tujuan dikunjungi oleh 1 kendaraan. Beberapa tujuan ini dapat memiliki jendela waktu untuk dikunjungi juga.

Saya menggunakan PostgreSQL dan PostGIS, dan ingin menggunakan pgrouting tetapi saya tidak yakin ini cocok untuk banyak kendaraan - dari pengetahuan saya yang terbatas tentang Dijkstra dll. Saya pikir mereka dirancang untuk satu kendaraan.

Adakah pemikiran tentang apakah pgrouting dapat memecahkan masalah ini, dan jika demikian, ada contoh kode? Jika tidak, adakah alternatif sumber terbuka yang dapat melakukannya?

routing pgrouting RichW
sumber
Saya kebetulan memiliki kebutuhan yang sama seperti Anda. Saya menjalankan bisnis NPO NEMT (Transportasi Medis Non-Darurat). kita perlu membawa pasien ke janji mereka dengan jendela waktu untuk pengambilan atau pengiriman. Sebagian besar permintaan diterima di muka, yang lain ada di tempat. DARP tampaknya merupakan algoritma yang bagus. Apakah Anda membutuhkan pemecah DARP untuk alasan yang sama? Nick
Nick Bazzi

Jawaban:

10

pgRouting memiliki fungsi yang disebut pemecah DARP (Dial-a-Ride) :

Pemecah Masalah Dial-a-Ride (DARP) mencoba untuk meminimalkan biaya transportasi sambil memuaskan kendala tingkat layanan pelanggan (pelanggaran waktu jendela, waktu tunggu dan perjalanan) dan kendala armada (jumlah mobil dan kapasitas, serta lokasi depot).

Lebih lanjut tentang DARP dan pgRouting:

Untuk menggunakan fungsi baru ini, Anda harus menginstal cabang dg pgRouting .

Jawaban untuk pertanyaan ini pada stackexchange mungkin memberikan info tambahan: Algoritma perutean untuk beberapa kendaraan dengan beberapa tetes .

underdark
sumber
Saya awalnya melihat algoritma DARP tetapi menepisnya karena saya tidak menyadari itu bisa digunakan untuk kurir. Sepertinya itu akan melakukan pekerjaan dengan baik! Sangat disayangkan bahwa halaman dokumentasi tidak memiliki contoh penggunaan apa pun, mungkin merupakan kasus pencarian melalui kode sumber untuk melihat cara kerjanya.
RichW
1

Walaupun ESRI ArcLogistics jelas tidak sesuai dengan kebutuhan khusus Anda untuk menggunakan PostGIS atau open source, bagi orang lain yang mungkin tidak memiliki keterampilan pemrograman atau waktu untuk mengimplementasikan solusi mereka sendiri, itu adalah perpanjangan yang baik, ekstensi berbayar untuk ArcGIS yang dirancang untuk menyelesaikan tugas yang Anda jelaskan.

Mereka saat ini juga menawarkan uji coba gratis 30 hari jika Anda ingin mengujinya.

RyanKDalton
sumber
Saya pergi ke ESRI HQ minggu lalu untuk membahas perangkat lunak ini untuk mereka, tetapi tampaknya tidak memenuhi kebutuhan kita (perlu dijalankan di server dan juga cukup mahal). Sepotong kit yang sangat baik!
RichW
Produk FleetEngine kami berjalan sebagai server dengan antarmuka SOAP. 100 destinasi, 5 kendaraan, dan time-windows sangat sesuai dengan kemampuannya. Sangat dekat untuk siap produksi, hubungi saya untuk mendapatkan lisensi uji. Ini bukan open source atau gratis, tetapi di sisi lain tidak semahal ArcLogistics.
Uffe Kousgaard
1
Hai Uffe, dapatkah itu memperhitungkan pembatasan kendaraan (berat dan dimensi) dan menyortir paket ke kendaraan yang sesuai? Juga, apakah ini bekerja di Inggris dan menggunakan data riwayat jalan untuk menghitung kecepatan dll?
RichW
Ya untuk semua pertanyaan Anda. Ini menggunakan additons sederhana dari berat / volume. Itu tidak bisa melakukan pengepakan 3D juga, itu terlalu banyak untuk diharapkan. Dukungan penuh untuk jaringan jalan di negara mana pun juga, tetapi Anda harus menyediakan jaringan jalan. Sayangnya saya tidak melihat balasannya lebih cepat, saya pikir diskusi ini telah berakhir. Ping saya di [email protected] jika Anda ingin membahasnya lebih lanjut.
Uffe Kousgaard