Optymalizacja trasy dla wielu pojazdów

12

Mam 100 miejsc docelowych i 5 pojazdów i muszę zakodować rozwiązanie, które skutecznie kieruje pojazdy do każdego miejsca docelowego, więc każde miejsce docelowe odwiedza 1 z tych pojazdów. Niektóre z tych miejsc docelowych mogą mieć także okna czasowe do odwiedzenia.

Korzystam z PostgreSQL i PostGIS, i chciałem zastosować pgrouting, ale nie jestem pewien, czy nadaje się do wielu pojazdów - z mojej ograniczonej wiedzy na temat Dijkstry itp. Myślę, że są one przeznaczone dla jednego pojazdu.

Wszelkie przemyślenia na temat tego, czy pgrouting może rozwiązać ten problem, a jeśli tak, jakieś przykłady kodu? Jeśli nie, czy istnieją jakieś alternatywne rozwiązania typu open source, które mogą to zrobić?

routing pgrouting

— RichW
źródło

Zdarza mi się mieć podobną potrzebę jak twoja. Prowadzę działalność NPO NEMT (Non-Emergency Medical Transportation). musimy przewozić pacjentów na spotkania z oknami czasowymi na odbiór lub dostawę. Większość wniosków jest przyjmowana z wyprzedzeniem, inne są na miejscu. DARP wydaje się być dobrym algorytmem. Czy potrzebujesz rozwiązania DARP z tego samego powodu? Nick

— Nick Bazzi

10

pgRouting ma funkcję o nazwie DARP (Problem Dial-a-Ride) :

Rozwiązanie problemu z połączeniem telefonicznym (DARP) stara się zminimalizować koszty transportu, jednocześnie spełniając ograniczenia poziomu obsługi klienta (przekroczenie okna czasowego, czasy oczekiwania i podróży) oraz ograniczenia floty (liczba samochodów i pojemności, a także lokalizacja zajezdni).

Więcej na temat DARP i pgRouting:

prezentacja z FOSS4G 2010: ROZWIĄZYWANIE PROBLEMU Z WYKRESEM WYKONYWANIA DIALY ZA POMOCĄ PGROUTINGU
Ogłoszenie: „Algorytm DARP w pgRouting”
Strona DARP Doc: „Rozwiązywanie problemów z wybieraniem numeru (DARP)”

Aby skorzystać z tej nowej funkcji, musisz zainstalować gałąź darp programu pgRouting .

Odpowiedzi na to pytanie dotyczące wymiany stosów mogą dostarczyć dodatkowych informacji: Algorytm wyznaczania trasy dla wielu pojazdów z wieloma spadkami .

— podmrok
źródło

Początkowo widziałem algorytm DARP, ale przesadziłem z nim, ponieważ nie zdawałem sobie sprawy, że można go użyć dla kurierów. Wygląda na to, że dobrze sobie poradzi! Szkoda, że strona z dokumentacją nie ma żadnych przykładów użycia, może to być przypadek przeszukania kodu źródłowego, aby zobaczyć, jak to działa.

— RichW

2

pgRouting ma nową funkcję do rozwiązywania DARP: http://www.pgrouting.org/docs/1.x/darp.html

— dkastl
źródło

Zobacz także niektóre ogłoszenia tutaj: openvrp.com/blog/darp-alameterm-in-pgrouting

— dkastl

Dzięki Daniel, to doskonała funkcja, którą tam zbudowałeś. Nie zdawałem sobie sprawy, że można go wykorzystać do celów dostawy, ale na pewno wygląda to wykonalnie. Dzięki!

— RichW

1

Podczas gdy ESRI ArcLogistics wyraźnie nie odpowiada twoim konkretnym potrzebom korzystania z PostGIS lub open source, dla innych, którzy mogą nie mieć umiejętności programowania lub czasu na wdrożenie własnych rozwiązań, jest to dobre, gotowe do użycia, płatne rozszerzenie do ArcGIS zaprojektowany do realizacji opisanych zadań.

Obecnie oferują również 30-dniowy bezpłatny okres próbny, jeśli chcesz go przetestować.

— RyanKDalton
źródło

Poszedłem do centrali ESRI w zeszłym tygodniu, aby omówić dla nich to oprogramowanie, ale wydaje się, że nie spełnia naszych potrzeb (musi działać na serwerze i jest również dość drogie). Doskonały zestaw!

— RichW

Nasz produkt FleetEngine działa jako serwer z interfejsem SOAP. 100 miejsc docelowych, 5 pojazdów i okien czasowych zdecydowanie mieści się w zakresie możliwości. Jest bardzo blisko gotowości do produkcji, skontaktuj się ze mną w celu uzyskania licencji testowej. Nie jest open source ani darmowy, ale z drugiej strony nie jest tak drogi jak ArcLogistics.

— Uffe Kousgaard

1

Cześć Uffe, czy może wziąć pod uwagę ograniczenia pojazdu (ciężar i wymiary) i odpowiednio posortować paczki na pojazdy? Czy działa również w Wielkiej Brytanii i wykorzystuje dane z historii drogi do obliczania prędkości itp.?

— RichW

Tak na wszystkie pytania. Wykorzystuje proste dodatki masy / objętości. Nie potrafi też pakować w 3D, to byłoby zbyt wiele na co liczyć. Pełne wsparcie dla sieci ulicznych w każdym kraju, ale musisz dostarczyć sieć uliczną. Niestety nie zobaczyłem odpowiedzi wcześniej, myślałem, że ta dyskusja się zakończyła. Zadzwoń do mnie na adres uffe@routeware.dk, jeśli chcesz to omówić dalej.

— Uffe Kousgaard