Snelle en realistische routeplanning voor GPS-toestellen

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.