OV-Routeplanner & Stoplinking

Voor OV-gerelateerde hobby's, computerspelletjes, gezelschapsspellen, etcetera
Gebruikersavatar
Skinkie
Berichten: 106
Lid geworden op: Di 05 Apr 2011, 17:43

OV-Routeplanner & Stoplinking

Berichtdoor Skinkie » Zo 10 Mar 2013, 16:34

Binnen een routeplanner zijn een aantal problemen die je kunt opdelen in een zoek-probleem en een filter-probleem. De meest eenvoudige routeplanner zal alle mogelijke routes zoeken en sorteren op basis van een criteria zoals kortste tijd, minste overstappen, laagste kosten. Hier uit volgt gegeven de vector {vertrek locatie, aankomst locatie, vertrektijd} een lijst met het meest optimale resultaat.

Een van de interne zoek-filter problemen heet 'stoplinking'. In het meest simpele geval zouden alle haltes tot een maximale loopafstand in het netwerk aan elkaar kunnen worden vastgemaakt. Dit is een proces wat normaal gesproken voor het bouwen van de graaf gebeurt. Dit geeft als resultaat dat de routeplanner tijdens het zoeken bij iedere halte "uitstapt" en zoekt of er een betere route binnen bijvoorbeeld 5 kilometer van de huidige halte ligt, waar een betere overstap te maken is. Een routeplanner kan enorm veel tijd besparen als het weet dat het bij een halte niet relevant is om uit te stappen. Omdat er gegeven een maximale loopafstand toch geen andere buslijn rijdt. Een stapje extra efficiëntie zou kunnen zijn om alleen de dichtstbijzijnde halte van een alternatieve route {lijnnummer, richting} te koppelen aan de te onderzoeken halte.

We zijn bij dit probleem dus nogsteeds een stap voor de daadwerkelijk planning, maar willen de planner natuurlijk niet hinderen door bepaalde relaties niet te leggen, terwijl ze in de praktijk relevant zijn. In het plaatje hieronder leg ik een van de boeiendere problemen neer. We hebben twee routes, de rode en de groene. Beide hebben ze een richting, de vraag is niet zo zeer waar gaat de planner aangegeven dat de overstap moet worden gemaakt, maar welke haltes moeten aan de rode halte meest links worden gekoppeld.

Afbeelding

Voor de mensen die natuurkunde al snel zijn vergeten; de s staat voor de (fictieve) lengte tussen de punten. Een van de belangrijkste vragen nu is: hoe evalueren we de volgordelijkheid van de parabool, waar heel duidelijk is dat de reiziger meer zou betalen of langer onderweg zou zijn als hij terug zou lopen naar de groene halte links, terwijl een halte dat later in het netwerk ligt, maar verder lopen is, mogelijk wel een betere kandidaat is voor het planner algoritme. We moeten bij dit probleem de componenten reistijd of aansluiting volledig buiten beschouwing laten, omdat deze pas later beschikbaar is.

Het probleem is: hoe voorkom je dat je alles moet toevoegen. Dus stel dat we minder moeilijk zouden doen over meerdere haltes van dezelfde buslijn die ongeveer allemaal op de zelfde afstand liggen, waarom zou het dan toch logisch zijn om de onderste groene halte niet toe te voegen.

De informatie die we in principe hebben per halte:
{haltenummer, lijn, richting, volgorde, x, y}

Voor mensen die de afstand tussen twee haltes als heuristiek onmisbaar beschouwen, kunnen we daar ook werkelijke segmentlengte (of zelfs: reistijd tussen haltes) beschikbaar maken.

De simpele vraag: welke haltes zou je koppelen aan de linker rode halte, en welke niet.
En welke generieke denkwijze gebruik je hierbij?


Resultaten

Code: Selecteer alles

Algoritme  | Radius | Obstructie | Links
-----------+--------+------------+--------
Baseline   |   400m |       x1.3 |  311519
Somoht     |   400m |       x1.3 |  103922
Somoht     |  2000m |       x1.3 | 1248838
Somoht     |  4000m |       x1.3 | 3960070
Skinkie-v1 |   400m |       x1.3 |   55978
Skinkie-v1 |  2000m |       x1.3 |  228955
Skinkie-v1 |  4000m |       x1.3 |  442083
Laatst gewijzigd door Skinkie op Ma 11 Mar 2013, 02:31, 8 keer totaal gewijzigd.

Somoht
Berichten: 1190
Lid geworden op: Di 11 Sep 2012, 22:03

Re: OV-Routeplanner & Stoplinking

Berichtdoor Somoht » Zo 10 Mar 2013, 17:29

Mijn algoritme gaat uit van KISS dus niet kijken naar richting, liever wat nodeloze iteraties dan een hoop flexibiliteit inleveren. In een dynamische routeplanner heb je namelijk ook te maken met ingekorte ritten waardoor er misschien overstappen worden gebruikt die je anders meteen zou wegfilteren.
Daarom dus voor elke halte, in elk geval alle haltes binnen het station/stoparea linken. Daarnaast alle haltes binnen x aantal meter waar een andere lijn stopt. Immers het is onnodig een haltes te linken waar bijvoorbeeld alleen lijn 5 stopt.
Dus in pseudocode:

Code: Selecteer alles

for halteA in haltes:
    for halteB in haltes_rondom(halteA,hemelsbrede_grenswaarde):
        if halteA.vertrekkendelijnen != halteB.vertrekkendelijnen:
            werkelijkaantalmeters = routetussen(halteA,halteB)
                if werkelijkaantalmeters < werkelijke_grenswaarde:
                    link(halteA,halteB,werkelijkaantalmeters)

Wubbo
OVNL-beheerder
Berichten: 9570
Lid geworden op: Zo 09 Mar 2008, 16:44
Locatie: Den Haag

Re: OV-Routeplanner & Stoplinking

Berichtdoor Wubbo » Zo 10 Mar 2013, 22:45

Gaat dit om overstappen of om je startpunt? Op de een of andere manier (maar daar heb ik geen rationele onderbouwing voor) vind ik het namelijk bij een overstap erger om verder te lopen dan van of naar mijn begin- of eindpunt.

Ik krijg geen redenering opgebouwd waarom je bepaalde haltes niet mee zou nemen en andere wel, en dat heeft met name te maken met het feit dat de rijtijd van het voertuig niet te vertrouwen is doordat op allerlei rare punten extra of te weinig rijtijd wordt ingebouwd: een halte eerder of later instappen kan er dus voor zorgen dat je een bus eerder of later haalt. Doordat buffertijd op relatief willekeurige punten in een route zit, is dat niet makkelijk in een algoritme af te vangen.

Gebruikersavatar
Skinkie
Berichten: 106
Lid geworden op: Di 05 Apr 2011, 17:43

Re: OV-Routeplanner & Stoplinking

Berichtdoor Skinkie » Ma 11 Mar 2013, 01:41

Wubbo schreef:Gaat dit om overstappen of om je startpunt? Op de een of andere manier (maar daar heb ik geen rationele onderbouwing voor) vind ik het namelijk bij een overstap erger om verder te lopen dan van of naar mijn begin- of eindpunt.

Het gaat feitelijk om het venster wat over iedere halte heen wordt geschoven als het algoritme kandidaten aan het zoeken is. Dus het meest logische is om het als overstap te bekijken, maar het gebeurt in iedere stap van het proces, de evaluatie overstap of niet speelt pas een rol na de kandidaat selectie.

Gebruikersavatar
Skinkie
Berichten: 106
Lid geworden op: Di 05 Apr 2011, 17:43

Re: OV-Routeplanner & Stoplinking

Berichtdoor Skinkie » Ma 11 Mar 2013, 02:13

Skinkie-v1

Code: Selecteer alles

x voor alle haltes:
    alleroutes = routes van x
    y voor alle haltes rond x, gesorteerd op afstand van x, laag naar hoog:
        als routes van y niet in alleroutes zit:
            voeg overstap x, y toe
            voeg routes van y toe aan alleroutes

Gebruikersavatar
Skinkie
Berichten: 106
Lid geworden op: Di 05 Apr 2011, 17:43

Re: OV-Routeplanner & Stoplinking

Berichtdoor Skinkie » Ma 11 Mar 2013, 02:44

Skinkie-v2:

Code: Selecteer alles

gedaan = {}
x voor alle stopareas:
    y voor alle haltes in stoparea x:
        link alle haltes naar elkaar
        assert(afstand(halte a, halte b) < radius)
        gedaan.add(y)

z voor alle (stopareas + (allehaltes - gedaan)):
     link dichtsbijzijnde (stopareas + (allehaltes - gedaan)) tot radius

Gebruikersavatar
Chauf21
OVNL-beheerder
Berichten: 3128
Lid geworden op: Zo 09 Mar 2008, 22:27

Re: OV-Routeplanner & Stoplinking

Berichtdoor Chauf21 » Ma 11 Mar 2013, 14:54

De simpele vraag: welke haltes zou je koppelen aan de linker rode halte, en welke niet.
En welke generieke denkwijze gebruik je hierbij?

Bij de keuze voor een halte spelen er bij mij, naast afstand, twee belangrijke andere factoren mee:
  • de aanwezigheid van andere lijnen/vervoermiddelen. Stel dat bij de twee bovenste groene bolletjes alleen lijn x (met een frequentie 1x/uur) stopt en bij het onderste bolletje zowel lijn x als lijn y. Indien lijn y een lijn is die eveneens naar de door mij gewenste bestemming gaat, dan wordt de onderste halte een serieus alternatief omdat ik dan meer reismogelijkheden per uur heb.
  • de 'kwaliteit' van de halte. Wellicht wat lastiger te operationaliseren, maar wanneer de onderste halte voorzien is van een abri (en de andere twee niet) of er zijn voorzieningen zoals fietsenrekken of pinautomaat, dan ga ik het gebruik van de onderste halte wel in overweging nemen.

Gebruikersavatar
Skinkie
Berichten: 106
Lid geworden op: Di 05 Apr 2011, 17:43

Re: OV-Routeplanner & Stoplinking

Berichtdoor Skinkie » Ma 11 Mar 2013, 22:06

Chauf21 schreef:
De simpele vraag: welke haltes zou je koppelen aan de linker rode halte, en welke niet.
En welke generieke denkwijze gebruik je hierbij?

Bij de keuze voor een halte spelen er bij mij, naast afstand, twee belangrijke andere factoren mee:
  • de aanwezigheid van andere lijnen/vervoermiddelen. Stel dat bij de twee bovenste groene bolletjes alleen lijn x (met een frequentie 1x/uur) stopt en bij het onderste bolletje zowel lijn x als lijn y. Indien lijn y een lijn is die eveneens naar de door mij gewenste bestemming gaat, dan wordt de onderste halte een serieus alternatief omdat ik dan meer reismogelijkheden per uur heb.

In principe mag je de frequentie niet meenemen, omdat dat een planner eigenschap is. Daarmee is je eis hetzelfde als dat van Somoht.
  • de 'kwaliteit' van de halte. Wellicht wat lastiger te operationaliseren, maar wanneer de onderste halte voorzien is van een abri (en de andere twee niet) of er zijn voorzieningen zoals fietsenrekken of pinautomaat, dan ga ik het gebruik van de onderste halte wel in overweging nemen.

Ik vind dit een hele sterke, omdat het me deed denken aan haltetoegankelijkheid. Er zijn inderdaad eigen aan haltes waardoor je liever naar een bepaalde halte loopt door een voorziening. Sterke toevoeging, mits meetbaar te maken.

Karl
Berichten: 3644
Lid geworden op: Do 13 Mar 2008, 21:06

Re: OV-Routeplanner & Stoplinking

Berichtdoor Karl » Wo 13 Mar 2013, 22:34

Ik was iets aan het lezen over Janelle's tijd-plaats-convergentie-model* en eerder deze maand over de wet van Behoud van REistijd en VERplaatsing (BREVER)** en daarvoor van Van Hagen over NS' klantwensenpirmide en eigenlijk zou je in plaats van een routeplanner die gebaseerd is op tijd een routeplanner moeten maken die gebaseerd is op moeite. Hoeveel moeite kost het om via route 1 van A naar B te komen en hoeveel om dat via route 2 te doen? Maar dat is natuurlijk lastig te operationaliseren, want hoe maak je zoiets meetbaar?

Volgens de klantwensenpiramide delen reizigers de factoren op in satisfiers en dissatisfiers, waarbij betrouwbaarheid en veiligheid (basisvoorwaarde) de meest belangrijke zijn, gevolgd door gemak en snelheid (satisfier, voor iedereen belangrijk) en daarna comfort en beleving (dissatisfier). Misschien kan je naar aanleiding daarvan een aantal criteria opstellen en in een soort rangorde plaatsen om de 'moeite' te bepalen van een reis per OV.

Bijvoorbeeld: toen ik werkte in een dorp en een reis vanuit het werk naar huis moest maken door een bus te nemen en daarna een trein, had ik twee mogelijkheden.

Mogelijkheid 1: twee minuten lopen naar de bushalte, waar een trage, door alle dorpen rijdende bus komt en dan na 45 minuten ofzo op het station aankomen, om de trein te nemen. Waarbij vermeld moet worden dat de bus in het dorp waar ik opstapte al een uur aan het rijden was, waarbij er gemakkelijk vertraging op gelopen kan worden.

Mogelijkheid 2: vijftien minuten lopen naar de bushalte aan de provinciale weg, om daar een bus te nemen die via de snelweg naar het station reed. Dat duurde ongeveer 25 minuten. Deze bus had deze halte als derde halte en was dus vrijwel altijd op tijd (of hooguit +2 die aankomst -2 was).

Ik nam vaak mogelijkheid 2, maar die gaf 9292 nooit aan, maar hier zie je dat betrouwbaarheid ontzettend belangrijk is en dat daarbij een kwartiertje lopen na een kantoordag best goed uitkwam (afhankelijk van het weer). Soms kwam de vertraagde 'langzame' bus van een half uur eerder nog langs en nam ik die naar de gemeenschappelijke provinciale halte om dan over de snelweg naar het station te reizen.

Wat je hierbij mee zou kunnen nemen: hoe betrouwbaar is de dienstregeling icm de werkelijkheid? Wat is het weer, in verband met invloed op de loopafstanden. Wat zijn de voorzieningen bij de bushalte? Volgens mij neemt TomTom dit in nieuwste versies ook mee bij het berekenen van routes.

*, http://www.csiss.org/janelle/docs/Janel ... zation.pdf
**, ik heb niet iets digitaal gezocht, maar Googlelen levert vast iets op
Sowieso en sinaasappelsap.
Stop de ver-s-bahn-isering van Nederland.

Klaasje
Berichten: 5993
Lid geworden op: Do 30 Jul 2009, 23:01
Locatie: Groningen

Re: OV-Routeplanner & Stoplinking

Berichtdoor Klaasje » Do 14 Mar 2013, 11:02

Karl schreef:Volgens de klantwensenpiramide delen reizigers de factoren op in satisfiers en dissatisfiers, waarbij betrouwbaarheid en veiligheid (basisvoorwaarde) de meest belangrijke zijn, gevolgd door gemak en snelheid (satisfier, voor iedereen belangrijk) en daarna comfort en beleving (dissatisfier). Misschien kan je naar aanleiding daarvan een aantal criteria opstellen en in een soort rangorde plaatsen om de 'moeite' te bepalen van een reis per OV.

Bijna goed! Het is voor de duidelijkheid alleen wel zo handig als je satisfier en dissatisfier qua omschrijving omdraait. :pos:

Karl
Berichten: 3644
Lid geworden op: Do 13 Mar 2008, 21:06

Re: OV-Routeplanner & Stoplinking

Berichtdoor Karl » Do 14 Mar 2013, 11:44

Eh, Ja, natuurlijk.
Sowieso en sinaasappelsap.
Stop de ver-s-bahn-isering van Nederland.


Terug naar “OV als Hobby”

Wie is er online

Gebruikers op dit forum: Geen geregistreerde gebruikers en 1 gast