Wat met real-time updates als je telefoon zelf jouw routes berekent?

Elke reiziger is anders en heeft een andere routeplanner nodig. De ene gebruikt graag een plooifiets in combinatie met het openbaar verdoer, terwijl de andere vooral een routeplanner wilt die de files vermijdt. Met de opkomst van Mobility as a Service (MaaS) worden de mogelijkheden nog meer divers. Daarom lijkt het opzetten van één routeplanner die iedereen tevreden stelt slechts een utopie. Met deze thesis maken we het simpeler om een nieuwe routeplanner op te zetten die updates zoals vertragingen snel in rekening kan brengen.

Laat je telefoon zelf routes berekenen

Klassieke routeplanners vereisen een serverinfrastructuur die de routes berekent. De applicatie stuurt een vraag naar de server om een route te berekenen tussen 2 punten via een web-API (Application Program Interface). De server antwoordt dan met een aantal mogelijke routes. Iedere aanvraag, door de hoge complexiteit, is uniek en moet opnieuw worden berekend, wat de cachebaarheid van de web-API niet ten goede komt. Verder wordt een app-ontwikkelaar beperkt door de vragen die de server kan oplossen.

Zou het dan niet mogelijk zijn om de routes lokaal te berekenen op je telefoon? Hiermee kan je je eigen route bepalen die aan jouw noden voldoet. Daarnaast wordt jouw route informatie niet gedeeld met anderen, wat jouw privacy ten goede komt.

Hiervoor wordt het Connection Scan Algoritme (CSA) gebruikt om routes te plannen door een openbaarvervoersnetwerk. Dit algoritme scant de mogelijke connecties om je te verplaatsen van punt A naar B, die in volgerde van vertrektijd worden aangeleverd.

Om effectief routes te berekenen, hebben we data nodig. Dankzij de openbaarheid van bestuur moeten overheidsbedrijven publieke data open stellen. Zo kan je o.a. de data van de Belgische openbaarvervoersmaatschappijen downloaden. Deze data worden aangeboden in de vorm van een datadump. Het verwerken van zo’n ruwe dump op je telefoon vereist te veel rekenkracht om werkbaar te zijn. Bovendien hebben we enkel de data nodig om onze routes te berekenen op een bepaald moment.

Dit probleem lossen we op met Linked Connections. Linked Connections fragmenteert de datadump in kleinere stukken. De applicatie kan dan slechts een deel van de data downloaden. Dit vermindert niet alleen de hoeveelheid data die moeten worden gedownload, maar ook de verwerkingstijd. Met deze betere verdeling tussen wat de server doet en wat er op de telefoon gebeurt, is het mogelijk om lokaal op je telefoon routes te berekenen. De server biedt aan alle apps dezelfde stukken informatie aan, wat interessant is voor de cachebaarheid en de privacy van de reiziger.

Snelle en automatische updates

Maar wat als een trein vertraagd is? Oorspronkelijk moesten we dan de data fragmenten opnieuw downloaden. Dankzij caching konden we de fragmenten overslaan die niet gewijzigd waren. Maar de vraag moest wel opnieuw worden verstuurd. Pas als alle fragmenten gecontroleerd waren, konden we de route helemaal herberekenen.

In deze thesis heb ik bestudeerd wat de invloed is op zowel de server als applicatie als we enkel de updates opvraagbaar maken. Door zo iets meer werk op de server te doen sparen we mogelijks heel wat bandbreedte uit. Verder bekeek ik ook of het algoritme in de app zelf slechts gedeeltelijk opnieuw uitgevoerd kon worden.

Hiervoor hebben we mobiele applicatie ontwikkeld die de Linked Connections data van de NMBS gebruikt om routes te genereren met behulp van CSA. Met onze applicatie kunnen reizigers hun route plannen maar ook het vertrekoverzicht van een bepaald station bekijken. Zo’n vertrekoverzicht bevat alle vertrekkende treinen in een bepaald station.

We hebben het CSA en het vertreksoverzicht uitgebreid om rekening te houden met de real-time data. Tijdens de routering, worden er snapshots gemaakt van de route. Indien een incident optreedt, voeren we een rollback uit naar net voor het incident (Een incident kan een vertragende of afgelaste trein zijn). Bij een vertreksoverzicht vervangen we enkel de aangepaste trein. Zodra de herberekening is uitgevoerd, krijgt de gebruiker meteen alternatieve route voor zijn of haar reis, zonder dat de gebruiker enige actie moet ondernemen. Om de gebruiker beter te informeren, worden er ook notificaties aangemaakt om duidelijk te maken welke trein of route bijgewerkt is.

Om de real-time data te publiceren hebben we het algoritme om de NMBS-datadump te verwerken aangepast. Met onze aanpassingen, worden de real-time incidenten in de Linked Connections ook apart als updates gepubliceerd. Nadat de verwerking is voltooid, kan de applicatie verder luisteren naar de updates. Daarvoor hebben we een polling (pull) aanpak vergeleken met een publisher subscribe (push) aanpak. Bij polling vraagt de applicatie de server om de 30 seconden of er nieuwe informatie beschikbaar is. Bij een push-aanpak zal de server de nieuwe informatie zelf naar de applicatie sturen.

Uit onze resultaten blijkt dat de push-aanpak efficiënter is, doordat er enkel data verstuurd wordt indien er effectief nieuwe informatie is. Zo konden we de hoeveelheid verzonden data verminderen met 90 % voor het CSA en met 92 % voor het vertrekoverzicht. Bij het gebruik van een push-aanpak, werden er 15 % minder data ontvangen voor het CSA en 21 % bij het vertreksoverzicht. Door het gebruik van updates, konden we een vertreksoverzicht 10 keer sneller bijwerken in vergelijking met de originele aanpak. De routeberekening met het CSA verliep op deze manier ook 2 keer sneller dan de originele aanpak. Doordat we enkel de updates verwerken, daalde het CPU verbruik met 50 – 55 % voor het vertreksoverzicht en 34 – 50 % voor het CSA. Deze besparing hangt af van het toestel dat gebruikt werd in de testomgeving.