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.
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.
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.
[1]Pieter Colpaert et al. Intermodal public transit routing using linked connections. 2015. https://linkedconnections.org/lc_demo_paper.pdf.
[2]Tim Berners-Lee. Tim berners-lee. https://www.w3.org/People/Berners-Lee/, 2018.[22 October 2018].
[3]Open Knowledge International. What is open data? http://opendatahandbook.org/guide/en/what-is-open-data/, . [22 October 2018].
[4]Open Knowledge International. The open definition. http://opendefinition.org/, . [22October 2018].
[5]Julian Dibbelt et al. Connection scan algorithm.CoRR, abs/1703.05997, 2017. http://arxiv.org/abs/1703.05997.
[6]Bert Marcelis. De door de gebruiker ervaren performantie van routeplanning-api’s. Master’sthesis, University of Ghent, 2018.
[7]Marek Obitko.Rdf graph and syntax. http://www.obitko.com/tutorials/ontologies-semantic-web/rdf-graph-and-s…, 2007. [5 October 2018].
[8]What is server-sent events? https://streamdata.io/blog/server-sent-events/,2017. [8 October 2018].
[9]Ilya Grigorik.Http caching. https://developers.google.com/web/fundamentals/performance/optimizing-c…, 2018.[14 October2018].
[10] Open Knowledge Belgium. irail. https://irail.be/. [22 October 2018].
[11]Open Knowledge International. Why open data? http://opendatahandbook.org/guide/en/why-open-data/, . [22 October 2018].
[12] Joost Vennekens and Herman Crauwels. Webtechnologie, 2016.
[13]Florian Bauer and Martin Kaltenb ̈ock.Linked Open Data: The Essentials.editionmono/monochrom, Vienna, Austria. ISBN 978-3-902796-05-9.9394.
[14]Michael Hausenblas. 5 star open data.https://5stardata.info/en/, 2012. [22 May2018].[15]Tim Berners-Lee. Linked data. https://www.w3.org/DesignIssues/LinkedData.html.[15 November 2018].
[16]The Linked Data Fragments collaborators.Linked data fragments. http://linkeddatafragments.org/. [15 November 2018].
[17]Ruben Verborgh et al. Querying datasets on the web with high availability. 2014. http://linkeddatafragments.org/publications/iswc2014.pdf.
[18]Google and GTFS contributers. Gtfs static specification. http://gtfs.org/, 2016. [8November 2018].
[19]Google and GTFS contributers. General transit feed specification. http://gtfsrt.com/. [6November 2018].
[20]EACOMM Corporation. General transit feed specification real time. http://gtfsrt.com/. [6November 2018].
[21]Transmodel Update Project Team. Transmodel cen standard. http://www.transmodel-cen.eu/. [7 November 2018].
[22] NeTEx working group. Netex cen standard.http://netex-cen.eu/. [8 November 2018].
[23]CEN group. Standard interface for real-time information. http://www.transmodel-cen.eu/standards/siri/, . [8 November 2018].
[24]CEN group. Cen ts 15531 service interface for real time information (siri). https://www.vdv.de/siri.aspx, . [8 November 2018].
[25]Pieter Colpaert et al. The impact of an extra feature on the scalability of linked connections.2016. URLhttp://ceur-ws.org/Vol-1666/paper-05.pdf.
[26]K. Maeda. Performance evaluation of object serialization libraries in xml, json and binaryformats. In2012 Second International Conference on Digital Information and CommunicationTechnology and it’s Applications (DICTAP), pages 177–182, May 2012. doi:10.1109/DICTAP.2012.6215346.
[27] Douglas Crockford. Introducing json. http://www.json.org/. [5 October 2018].
[28]Saurabh Zunke and Veronica D’Souza.Json vs xml: A comparative performanceanalysisofdataexchangeformats.http://ijcsn.org/IJCSN-2014/3-4/JSON-vs-XML-A-Comparative-Performance-A…. [10 December 2018].
[29]W3C JSON-LD Community Group. Json for linking data. http://www.json-ld.org, 2014.[5 October 2018].
[30] W3C.Extensible Markup Language (XML) 1.0 (Fifth Edition), 2008. [5 October 2018].
[31]Sadayuki Furuhashi. Messagepack. https://msgpack.org/index.html. [5 October 2018].
[32]Google. Protocol buffers. https://developers.google.com/protocol-buffers/. [5October 2018].
[33]Bruno Krebs.Beating json performance with protobuf. https://auth0.com/blog/beating-json-performance-with-protobuf/. [6 October 2018].
[34] Apache Software Foundation. Apache thrift. https://thrift.apache.org/. [4 May 2019].
[35]Mozilla contributors. Connection management in http/1.x. https://developer.mozilla.org/en-US/docs/Web/HTTP/Connection_management…, 2018. [13 October2018].
[36]Browserscope contributors. Browserscope. https://www.browserscope.org/?category=network&v=top, 2018. [13 October 2018].
[37]WHATWG community. Server-sent events. https://html.spec.whatwg.org/multipage/server-sent-events.html#server-s…, 2018. [6 October 2018].
[38]The gRPC Authors. Frequently asked questions. https://grpc.io/faq/. [5 October 2018].
[39]Aaron Krauss. How websockets work – with socket.io demo . https://thesocietea.org/2016/04/how-websockets-work-with-socket-io-demo/, 2016. [5 October 2018].
[40]Mozilla contributors. The websocket api (websockets). https://developer.mozilla.org/en-US/docs/Web/API/WebSockets_API, 2018. [5 October 2018].
[41] MQTT contributors. Mqtt. https://mqtt.org/. [8 October 2018].
[42]HTTPbis Working Group.Hypertext Transfer Protocol Version 2 (HTTP/2), 2015. [7 October2018].
[43]Mozilla contributors. Http caching.https://developer.mozilla.org/en-US/docs/Web/HTTP/Caching, 2018. [14 October 2018].
[44]Internet Engineering Task Force (IETF).Hypertext Transfer Protocol (HTTP/1.1): Caching,2014. [8 October 2018].
[45]Internet Engineering Task Force (IETF).HTTP Immutable Responses, 2017. [7 October 2018].
[46]Pieter Colpaert. Linked connections specification 1.0. https://linkedconnections.org/specification/1-0, 2018. [12 October 2018].
[47]Pieter Colpaert et al. Public transit route planning through lightweight linked data interfaces.2017. https://pietercolpaert.be/papers/icwe2017-lc/paper.pdf.
[48]Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.1994 Patterns: Elements ofReusable Object-Oriented Software. 2018. ISBN 0201633612.