Industrieel ingenieur informatica

Universiteit Gent campus Schoonmeersen

Snelle en realistische routeplanning voor GPS-toestellen

Gerealiseerd door: 
Jeroen Verbrugghe
Interne promotor: 
Jan Cnops
Externe promotor: 
Mario Pickavet
Externe promotor: 
Didier Colle
Academiejaar: 
20142015

GPS-toestellen berekenen de kortste weg en reistijd tussen twee punten in een wegennetwerk. Hiervoor wordt standaard het algoritme van Dijkstra gebruikt. Het wordt iets ingewikkelder als er ook rekening moet gehouden worden met spitsuren en structurele files, met andere woorden: met het tijdstip van de dag. Een mogelijke oplossing bewaart voor elk moment van de dag de werkelijke rijtijden van alle straten van het netwerk, en gebruikt een tijdsafhankelijke variant van het algoritme van Dijkstra. Het probleem bij deze oplossing: de geheugenvereisten zijn te groot om al de werkelijke rijtijden op te slaan. In deze scriptie wordt een benadering voorgesteld die dit probleem omzeilt. In plaats van per tijdstip en per straatdeel één tijdsduur bij te houden, wordt er gewerkt met compactere informatie. Enerzijds is er de tijdsinformatie, die per tijdstip bijhoudt hoeveel straatdelen er op het volledige netwerk zijn met vertragingen. Anderzijds is er de locatie-informatie, die per straatdeel bijhoudt hoeveel tijdstippen er doorheen de dag zijn waarop er vertragingen genoteerd worden. Deze twee stukken informatie worden gecombineerd om voor elk straatdeel op elk moment tot een benaderende rijtijd te komen.

Waar zijn ze nu?

Binnen de opleiding wordt vaak samengewerkt met bedrijven en andere instellingen. Zo stroomden onze alumni al door naar …

Onderzoek in de kijker

Pieter-Jan Maenhaut tracht in zijn onderzoek efficiënte algoritmen te ontwikkelen, die gebruikt kunnen worden voor statische en dynamische plaatsing van componenten in de publieke cloud. Daarnaast besteedt hij ook extra aandacht aan multi-tenancy, en de bijhorende uitdagingen zoals beveiliging en eenvoudig beheer in de cloud.