Strategia, aby znaleźć najlepszą trasę tylko środkami transportu publicznego?

To, o czym mówisz, jest bardziej skomplikowane niż coś w rodzaju modeli matematycznych, które można opisać za pomocą prostych struktur danych, takich jak wykresy i "prostych" algorytmów, takich jak Djikstra ' s. to, o co prosisz, jest bardziej złożonym problemem, jak te spotykane w świecie zautomatyzowanego zarządzania logistycznego.

Jednym ze sposobów myślenia jest to, że zadajesz problem wielowymiarowy, musisz być w stanie obliczyć:

1. Odległość optymalizacja
2. optymalizacja czasu
3. optymalizacja trasy
4. optymalizacja"horyzontu czasowego "(jeśli jest 5:25, a autobus pojawia się dopiero o 7: 00, wybierz inną trasę.)

Biorąc pod uwagę wszystkie te okoliczności, można próbować deterministycznego modelowania przy użyciu złożonych wielowarstwowych struktur danych. Na przykład, nadal można użyć ważonej di-grafu do reprezentowania istniejących potencjalnych tras, w którym każdy węzeł zawierał również skończone automaty stanu, które dodały błąd wagi do trasy w zależności od wartości czasu (więc przekraczając węzeł o 5:25 otrzymujesz inną wartość niż w przypadku, gdy symulacja przekroczyła go o 7: 00.)

Myślę jednak, że w tym momencie znajdziesz się w coraz bardziej złożonej symulacji, która najprawdopodobniej nie zapewnia "Wielkiego" przybliżenia optymalnych tras, gdy porady zostaną przeniesione do świata rzeczywistego. Okazuje się, że oprogramowanie i modelowanie matematyczne i symulacja są co najwyżej słabym narzędziem, gdy spotkanie z rzeczywistymi chaotycznymi zachowaniami i dynamizmem.

Moja propozycja to użycie alternatywnej strategii. Chciałbym spróbować użyć algorytmu genetycznego, w którym DNA dla osoby obliczone potencjalną drogę, chciałbym następnie utworzyć funkcję fitness, który zakodowane koszty i wagi w bardziej "łatwy do utrzymania" sposób tabeli wyszukiwania. Wtedy pozwoliłbym algorytmowi genetycznemu na znalezienie optymalnego rozwiązania dla wyszukiwarki tras transportu publicznego. Na nowoczesnych komputerach a GA takie jak to prawdopodobnie będzie działać w miarę dobrze, i powinien być co najmniej stosunkowo solidne do realnego dynamizmu świata.

Myślę, że większość systemów, które robią tego typu rzeczy, wybierają "łatwe wyjście" i po prostu robią coś w rodzaju algorytmu wyszukiwania A*, lub coś podobnego do chciwego, kosztownego, ważonego spaceru digrafowego. Należy pamiętać, że użytkownicy transportu publicznego sami nie wiedzą, jaka byłaby optymalna trasa }, więc optymalne rozwiązanie w 90% jest nadal będzie świetnym rozwiązaniem dla przeciętnego przypadku.

Niektóre punkty danych, które należy pamiętać z transportu publicznego arena:

1. każdy transfer wiąże się z karą 10 minut (chyba że jest to transfer czasowy) w umyśle zawodników. To znaczy mentalnie podróż z udziałem jednego autobusu, który trwa 40 minut, jest w przybliżeniu równoznaczna z podróżą 30 minut, która wymaga transferu.
2. Maksymalna odległość, jaką większość ludzi jest skłonna przejść do przystanku autobusowego to 1/4 mili. Dworzec kolejowy / Kolej Lekka około 1/2 mili.
3. odległość jest nieistotna do kierowcy transportu publicznego. (Ważny jest tylko czas)
4. Częstotliwość ma znaczenie (jeśli połączenie zostanie pominięte, jak długo do następnej magistrali). Kierowcy będą preferować częstsze opcje serwisowe, jeśli alternatywa zostanie zablokowana na godzinę na następny ekspres.
Kolej ma większe preferencje niż autobus ( większa pewność, że pociąg przyjedzie i będzie jechał we właściwym kierunku)]} Opłacenie nowego biletu to wielki hit. (dodaj około 15-20min kary)
5. total trip liczy się również czas (z powyższymi karami)
6. Jak bezproblemowe jest połączenie? Czy jeździec musi istnieć Dworzec kolejowy przecinający ruchliwą ulicę? A może po prostu wysiąść z pociągu i przejść 4 kroki do autobusu?
Przejeżdżanie przez ruchliwe ulice-kolejna duża kara za transfery - może przegapić połączenie, bo nie może wystarczająco szybko przejść przez ulicę.

Znalezienie trasy dla samochodu jest dość easy: przechowujesz ważony Wykres wszystkie drogi i można użyć Algorytm dżikstry. Trasa autobusowa to mniej oczywiste.

Na przykład oznaczasz autobusy, których czas minął, jako mające nieskończony koszt - wtedy nie są uwzględniane w obliczeniach.

Wtedy otrzymujesz aby zdecydować, jak ważyć każdy aspekt.

Czas Tranzytu może zostać ważony przez 1 Czas oczekiwania może być ważony o 1 Transfery mogą być ważone o 0,5 (ponieważ wolałbym dostać się tam wcześniej i mieć dodatkowy transfer)

Następnie obliczasz wszystkie trasy na wykresie za pomocą dowolnego zwykłego algorytmu kosztu z dodaniem nieskończonego kosztu:

Za każdym razem, gdy poruszasz się wzdłuż krawędzi, musisz śledzić "aktualny" czas (sumować czas przejazdu), a jeśli dojdziesz do wektora, musisz przypisuj nieskończony koszt do wszystkich autobusów, które są przed bieżącym czasem. Aktualny czas jest zwiększany o czas oczekiwania na wektor do następnego odjazdu autobusu, a następnie możesz swobodnie poruszać się wzdłuż innej krawędzi i znaleźć nowy koszt.

Innymi słowy, istnieje nowe ograniczenie, "obecny czas", który jest czasem pierwszego startu autobusu, podsumowany wszystkimi czasami TRANZYTU i oczekiwania autobusów i przystanków przejechanych.

Komplikuje algorytm tylko trochę, ale algorytm to wciąż to samo. Widać, że większość algorytmów można zastosować do tego, niektóre mogą wymagać wielu przejść, a kilka nie będzie działać, ponieważ nie można dodać czasu-- > nieskończona kalkulacja kosztów inline. Ale większość powinna działać dobrze.

Możesz to jeszcze uprościć, zakładając, że autobusy są zgodnie z harmonogramem i zawsze jest inny autobus, ale wydłuża to czas oczekiwania. Czy algorytm tylko sumując koszty transportu, a następnie przejść przez drzewo ponownie i dodać koszty oczekiwania w zależności od tego, kiedy przyjedzie następny autobus. Czasami skutkuje to mniej wydajnymi wersjami, ale całkowity Wykres nawet dużego miasta jest w rzeczywistości dość mały, więc tak naprawdę nie jest to problem. W większości przypadków jedną lub dwie trasy będą oczywistymi zwycięzcami.

Google ma to, ale zawiera również dodatkowe krawędzie do chodzenia z jednego przystanku autobusowego do drugiego, więc możesz znaleźć nieco bardziej optymalną trasę, jeśli chcesz chodzić w miastach z dużymi systemami autobusowymi.

- Adam

Jeśli koszt każdego etapu podróży jest mierzony w czasie, to jedynym powikłaniem jest faktoring w harmonogramie - który zmienia koszt na każdym węźle do funkcji bieżącego czasu t, gdzie t jest tylko całkowity czas podróży do tej pory (zakładając, że harmonogramy są znormalizowane, aby rozpocząć od t=0).

Więc zamiast węzła a, który ma koszt 10 minut, ma koszt f (t) zdefiniowany jako:

• t1 = nextScheduledStop (t); / / aby uzyskać następny czas zatrzymania w czasie lub po czasie t
• baseTime for leg = 10 / / na przykład 10-minutowa podróż
• return (t1-t)+baseTime

Czas oczekiwania jest zatem dynamicznie wliczany do kosztów każdej nogi, a spacery między przystankami autobusowymi są tylko łukami ze stałym kosztem czasowym

Z tą reprezentacją powinieneś być w stanie zastosować algorytm* lub Dijkstry bezpośrednio

Sposób, w jaki myślę o tym problemie jest to, że ostatecznie próbujesz zoptymalizować swoją średnią prędkość od punktu początkowego do punktu końcowego. W szczególności nie obchodzi Cię całkowity przebyty dystans, jeśli idziesz [dobrze] z drogi oszczędza czas. Tak więc podstawową częścią przestrzeni rozwiązania będzie musiała być identyfikacja wydajnych dostępnych tras, które obejmują nietrywialne części całkowitej odległości przy stosunkowo dużych prędkościach między startem a metą.

Do oryginału punkt, typowe algorytmy trasy samochodowej wykorzystywane przez jednostki nawigacji GPS, aby podróż samochodem jest dobry związany do celu optymalny czas całkowity i optymalne oceny trasy. Innymi słowy, twoja podróż autobusem byłaby naprawdę dobra, aby podejść do rozwiązania opartego na samochodzie. Oczywiście system oparty na trasie autobusowej będzie miał o wiele więcej ograniczeń niż rozwiązania oparte na samochodzie, ale posiadanie rozwiązania samochodowego jako punktu odniesienia (czas i odległość) daje algorytmowi magistrali ramy do optymalizacji przeciw*. Mówiąc luźno, chcesz przekształcić rozwiązanie samochodowe w zestaw możliwych rozwiązań autobusowych w sposób iteracyjny lub być może bardziej prawdopodobne, że podejmiesz możliwe rozwiązania autobusowe i zdobędziesz je w porównaniu z rozwiązaniem opartym na samochodzie, aby wiedzieć, czy robisz "dobrze", czy nie.

Czyniąc to nieco bardziej konkretnymi, dla określonego czasu odjazdu będzie dostępna tylko ograniczona liczba autobusów w rozsądnym terminie, który może pokryć znaczny procent całkowitej liczby pasażerów odległość. Na podstawie prostej analizy motoryzacyjnej rozsądny okres czasu i znaczący procent odległości stają się wymierne przy użyciu pewnych lekko subiektywnych wskaźników. Z pewnością łatwiej jest ocenić każdą możliwość w stosunku do drugiej w bardziej absolutnym sensie.

Gdy masz zestaw możliwych segmentów głównych dostępnych jako możliwe odpowiedzi w rozwiązaniu, musisz je połączyć z innymi możliwymi ścieżkami chodzenia i oczekiwania....lub jeśli wystarczająco daleko od siebie rekurencyjny wybór dodatkowych krótkich przejazdów autobusowych. Intuicyjnie nie wydaje się, aby rzeczywiście miał miejsce zaporowy zestaw wyborów ze względu na paradoks ograniczeń (patrz przypis poniżej). Nawet jeśli nie można brutalnie wymusić wszystkich możliwych kombinacji stamtąd, to, co pozostaje, powinno być w stanie zoptymalizować za pomocą algorytmu typu symulowanego wyżarzania (SA). Inną opcją byłaby Metoda Monte Carlo .

The way We ' ve złamany problem do tego punktu pozostawia nam coś, co jest dość analogiczne do tego, jak algorytmy SA są stosowane do automatycznego układania i routingu układów ASIC, FPGA, a także umieszczania i routingu płytek drukowanych, z których jest sporo opublikowanej pracy na optymalizacji tego typu formy problemu.

* Uwaga: zwykle nazywam to "paradoksem ograniczeń" - moim terminem. Podczas gdy ludzie mogą naturalnie myśleć o bardziej ograniczonych problemach jako trudniejszych do rozwiązać, ograniczenia zmniejszyć wybory i mniej wyborów oznacza łatwiej brutalnej siły. Kiedy można brute force, wtedy nawet optymalne rozwiązanie jest dostępne.

Zasadniczo węzeł na wykresie powinien reprezentować nie tylko lokalizację, ale także najwcześniejszy czas, w którym można się tam dostać. Można o tym myśleć jako o eksploracji grafu w przestrzeni (miejscu, czasie). Dodatkowo, jeśli masz (place,t1) i (place, t2) gdzie t1

Teoretycznie, będzie to najwcześniejszy czas przyjazdu dla wszystkich możliwych miejsc z węzła startowego. W praktyce, trzeba trochę heurystyczne przycinać drogi, które zabierają cię zbyt daleko od swojego miejsce.

Potrzebujesz również heurystyki, aby rozważyć obiecujące trasy przed mniej obiecującymi-jeśli trasa prowadzi z dala od miejsca docelowego, jest mniej prawdopodobne (ale nie całkowicie mało prawdopodobne), aby być dobrym.

Myślę, że twój problem jest bardziej skomplikowany niż się spodziewasz. Ostatnie działania związane z kosztami koncentrują się na rozwiązaniu tego problemu: http://www.cost.esf.org/domains_actions/tud/Actions/TU1004 : "Modelowanie przepływów pasażerów w transporcie publicznym w dobie Inteligentnych Systemów Transportowych".

Z mojego punktu widzenia zwykłe algorytmy SPS nie nadają się do tego. Masz dynamiczny stan sieci, w którym niektóre opcje jazdy do przodu są niewyraźne (trasa jest zawsze "otwarta" dla samochodu, roweru, pieszych, natomiast połączenie tranzytowe jest dostępne tylko w określonym czasie).

Myślę, że pożądane jest tu nowe podejście polikryterialne (czas, niezawodność, koszt, komfort i inne kryteria). Musi być obliczany w czasie rzeczywistym, aby 1) publikować informacje użytkownikowi końcowemu w krótkim czasie 2) BYĆ w stanie dostosować ścieżkę w czasie rzeczywistym (w oparciu o warunki ruchu w czasie rzeczywistym-z ITS).

Mam zamiar myśleć o tym problemie przez najbliższe kilka miesięcy (może nawet w trakcie pracy doktorskiej).

Pozdrawiam Rafal

Nie wydaje mi się, że istnieje jakaś inna specjalna struktura danych, która zaspokoiłaby te specyficzne potrzeby, ale nadal możesz używać normalnych struktur danych, takich jak powiązana lista, a następnie wykonywać obliczenia trasy według danego czynnika-będziesz potrzebował pewnego rodzaju wprowadzania do aplikacji zmiennych, które wpływają na wynik, a następnie dokonywać obliczeń odpowiednio tj. w zależności od wprowadzanych danych.

Jeśli chodzi o czekanie i takie tam, to są to czynniki, które są związane z konkretnym węzłem, prawda? Ty może przełożyć ten czynnik na węzeł trasy dla każdej z gałęzi dołączonych do węzła. Na przykład możesz powiedzieć dla każdej gałęzi z węzła X, jeśli na węźle X jest oczekiwanie na m minut, skaluj wagę gałęzi przez [m / jakaś wartość bazowa*100]% (tylko przykład). W ten sposób uwzględniłeś inne czynniki równomiernie, ale jednocześnie zachowując prostą reprezentację problemu, który chcesz rozwiązać.

Gdybym rozwiązywał ten problem, prawdopodobnie zacząłbym od przypisanego grafu. Każdy węzeł na wykresie reprezentowałby każde skrzyżowanie w mieście, niezależnie od tego, czy system transportu publicznego tam się zatrzymuje, czy nie - pomaga to uwzględnić potrzebę chodzenia itp. Na skrzyżowaniach z usługą transit można dodać adnotacje za pomocą etykiet stop - etykiet umożliwiających wyszukiwanie harmonogramu usług dla przystanku.

Więc musisz dokonać wyboru. Czy potrzebujesz najlepszej możliwej trasy, czy tylko trasa? Czy trasy są wyświetlane w czasie rzeczywistym, czy rozwiązania mogą być obliczane i buforowane?

Jeśli potrzebujesz obliczeń "w czasie rzeczywistym", prawdopodobnie będziesz chciał skorzystać z chciwego algorytmu, myślę, że a * algorytm prawdopodobnie pasowałby do tej domeny problemu dość ładnie.

Jeśli potrzebujesz optymalnych rozwiązań, powinieneś przyjrzeć się rozwiązaniom dynamicznego programowania do wykresu... optymalne rozwiązania będą prawdopodobnie trwać znacznie dłużej, aby obliczyć, ale trzeba tylko znaleźć je raz, a następnie mogą być buforowane. Być może twój algorytm A* mógłby wykorzystać wstępnie obliczone optymalne ścieżki do informowania o swoich decyzjach o" podobnych " trasach.

Strasznie nieefektywnym sposobem, który mógłby zadziałać, byłoby przechowywanie kopii każdego skrzyżowania w mieście dla każdej minuty dnia. W latach 1975-1998 miejscowość administracyjnie należała do województwa siedleckiego.]}

elm_st_and_2nd[12][30].edges :
 elm_st_and_1st[12][35] # 5 minute walk to the next intersection
   time = 5 minutes
   transport = foot
 main_st_and_25th[1][15] # 40 minute bus ride
   time = 40 minutes
   transport = bus
 elm_st_and_1st[12][36] # stay in one place for one minute
   time = 1 minute
   transport = stand still

Uruchom swój ulubiony algorytm wyszukiwania ścieżek na tym wykresie i módl się o dobrą implementację pamięci wirtualnej.

Sam odpowiadasz na pytanie. Korzystając z algorytmu * lub Dijkstry, wszystko, co musisz zrobić, to zdecydować się na dobry koszt na Część każdej trasy.

Dla trasy autobusowej sugerujesz, że nie chcesz najkrótszej, ale najszybszej trasy. Koszt każdej części trasy musi zatem obejmować średnią prędkość przejazdu autobusu w tej części oraz wszelkie postoje na przystankach autobusowych.

Algorytm znajdowania najbardziej odpowiedniej trasy jest więc nadal taki sam jak poprzednio. Z*, wszystkie magia dzieje się w funkcji kosztów...

Musisz inaczej obciążać nogi. Na przykład-w deszczowy dzień myślę, że ktoś wolałby podróżować dłużej pojazdem niż chodzić w deszczu. Dodatkowo, ktoś, kto nie lubi chodzić lub nie jest w stanie chodzić, może zrobić inną / dłuższą podróż niż ktoś, kto nie miałby nic przeciwko chodzeniu.

Te krawędzie to koszty, ale myślę, że można rozszerzyć pojęcie / pojęcie kosztów i mogą mieć różne wartości względne.

Algorytm pozostaje ten sam, po prostu zwiększasz wagę każdej krawędzi wykresu według różnych scenariuszy(rozkład jazdy autobusów itp.).

Jakiś czas temu stworzyłem wyszukiwarkę tras metra jako ćwiczenie w wyszukiwaniu ścieżek Wykresów:

Http://gfilter.net/code/pathfinderDemo.aspx