Verkeer versnellenAlgoritmen voor verkeerstoewijzingIn software voor verkeerstoewijzing, samengesteldezonering en acycliciteit in paden

Het algemene doel van dit proefschrift is om vooruitgang te boeken op het gebied/vlak van rekenuitdagingen/rekenefficiëntie in het domein van verkeersmodellering. Deze modellen worden tegenwoordig op grote schaal gebruikt om zowel operationele als strategische besluitvorming door beleidsmakers met betrekking tot autoverkeer te vergemakkelijken maar vragen nog altijd veel expertise en rekenkracht. Een veelvoorkomend voorbeeld/toepassing van verkeersmodellering is infrastructuurplanning, waarin deze modellen gebruikt worden om de maatschappelijke kosten en baten van voorgestelde veranderingen te beoordelen en waarin deze modellen ook een belangrijke rol spelen bij het voorspellen van luchtvervuiling. De grootste uitdaging in verkeersmodellering is het vinden van consistentie tussen de routekeuze (beslissingen) van reizigers en congestie (file) die ontstaat door die keuzes (van reizigers) in een werkbare tijdspanne. Modellen verschillen op basis van de onderliggende aannames over hoe zowel routekeuze als congestie worden berekend. Het argument voor het vinden van betere/snellere algoritmen is vanzelfsprekend. Het verlagen van de rekentijd die de onderliggende algoritmen met zich meebrengen(,) stelt modelleurs in staat om zowel dezelfde modelleringsvragen in een kortere tijd te beantwoorden, een realistischer model in te zetten als binnen een bepaald tijdsbudget meer verschillende scenario's te evalueren voor een betere besluitvorming.

In dit proefschrift worden drie verschillende bijdragen gepresenteerd. Ten eerste introduceren we een open-source pythonpakket genaamd dyntapy voor het oplossen van verkeerstoedelingsproblemen. Dyntapy biedt mogelijkheden voor het verwerken van gegevens over wegennetwerken en reisbehoeften, bevat een reeks algoritmen voor verschillende varianten van verkeersmodellering en heeft meerdere visualisatiefunctionaliteiten. Het doel van deze tool is tweeledig: het vergemakkelijkt open wetenschap door de drempel te verlagen voor het publiceren van algoritmen met betrekking tot verkeerstoedeling in open source en het biedt toegang tot state-of-the-art toedelingsalgoritmen, die gewoonlijk niet vrij beschikbaar/niet open-source beschikbaar zijn.

De tweede bijdrage van dit doctoraat is de ontwikkeling van een benaderingsschema voor het statische verkeerstoedelingsprobleem (probleem). De benadering bestaat eruit dat langeafstandsreizigers aanvankelijk eerst naar een surrogaatbestemming, die zich onderweg van hun werkelijke bestemming bevindt, reizen, vooraleer ze overgaan op het routering naar hun werkelijke bestemming eens ze dichterbij zijn. Op deze manier is het resulterende model beter schaalbaar met de grootte van het studiegebied. We formuleren het probleem als een uitbreiding op het evenwicht van Wardrop en laten zien hoe het/dit benaderingsschema kan worden gebruikt in Dial's algoritme B. Het concept (heeft echter een generieke aantrekkingskracht en) is in principe toepasbaar op alle andere statische algoritmen en kan ook helpen bij het verbeteren van de efficiëntie van dynamische verkeerstoedelingsalgoritmen. Er wordt aangetoond dat voor voldoende grote modellen, de rekentijden met meer dan een/één grootteorde/orde van grootte daalt met verwaarloosbare gevolgen voor de (oplossings)kwaliteit in vergelijking met het standaard verkeerstoedelingsalgoritmen.

Tot slot bespreken we een nieuwe manier om routes op transportnetwerken bij te houden: door ze te coderen in beperkte acyclische subgrafen. De uitdaging is dat een subgraaf gevormd uit verschillende acyclische routes over het algemeen zelf niet acyclisch is. Twee Integer Programmatiemodellen voor het (probleem van het) vinden van een acyclische subgraaf die de paddekking maximaliseert worden geïntroduceerd. De dekkingsgraden worden onderzocht in grootschalige casestudies. Geen van beide probleemformuleringen is in alle gevallen uitvoerbaar in een redelijke rekentijd. We stellen een greedy heuristiek om snel oplossingen te genereren en vergelijken de dekkingsgraden tussen de exacte en heuristische aanpak. In alle gevallen werd gemiddeld een dekkingsgraad van meer dan 90 procent waargenomen bij gebruik van de voorgestelde heuristiek. Dit resulteert in efficiënte acyclische netwerken waarin, aantoonbaar, bijna alle relevante paden zijn opgenomen.