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.
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