Om de doorstroming in een netwerk te optimaliseren, moeten we verkeersmanagementmaatregelen in samenhang inzetten. Maar hoe bepaal je wat de optimale – meest samenhangende – inzet is? Lange tijd leek het ondoenlijk om zo’n regelprobleem met behulp van (microscopische) modelvoorspellingen op te lossen: het probleem was daarvoor te complex. Een slimme wiskundige techniek die gebruik maakt van verschillende modellen lijkt echter voor een doorbraak te zorgen. Volgens Osorio et al is de nieuwe modelgebaseerde optimaliserende aanpak zelfs geschikt voor het doorrekenen van complete netwerken.
Microscopische verkeersmodellen zijn gedetailleerde vraag- en aanbodmodellen die afzonderlijke voertuigen en individuele reizigers simuleren en beschrijven hoe elk van de reizigers beslissingen neemt over bijvoorbeeld de modaliteit, vertrektijd, route en zelfs de rijstrook die ze daarbij gebruiken. Ook details als verkeersregelingen (zoals groentijden) en prioriteiten van het openbaar vervoer worden gesimuleerd.
Deze modellen gebruiken we al tientallen jaren om via trial & error verkeerslichten in te regelen, wachtrijen en mogelijke terugslag te bestuderen enzovoort. We beschikten nog niet over geautomatiseerde methoden om regelingen te optimaliseren, maar daar kan dus snel verandering in komen. In het onderstaande bespreken we kort de kenmerken van het optimalisatieprobleem, we leggen uit waarin de modelaanpak tot nu toe tekortschoot – en laten zien hoe en waarom de nieuwe modelgebaseerde optimaliserende aanpak wél geschikt is voor het (geautomatiseerd) optimaliseren van netwerken.
Het optimalisatieprobleem
We gaan er in het navolgende vanuit dat we de beschikking hebben over een gekalibreerd microsimulatiemodel waarmee we het functioneren van een reeks verkeerslichten kunnen beoordelen. Het is een stochastisch model, wat betekent dat de uitkomst van een run elke keer verschilt en de facto een trekking is uit een stochastische verdeling. We gebruiken de notatie F=F(x,y;p) om dit uit te drukken. Hier staat de beslissingsvector x voor de variabelen van de verkeersregeling, zoals de groentijden. De functie F beschrijft een stochastische waarde van de te optimaliseren prestatiemaat, zoals totale verliestijd, totale reistijd of totale emissie. Deze waarde hangt natuurlijk af van de verkeersregeling x, maar ook van andere endogene variabelen van het simulatiemodel y. Denk dan aan de capaciteiten van de links, de routekeuzekansen enzovoort. Ook de (vaste) simulatieparameters p spelen een rol: de herkomst-bestemmingsmatrix, netwerktopologie, het openbaar-vervoernetwerk etc.
Stel dat we op zoek zijn naar de regeling x* die de gemiddelde prestatie van het netwerk optimaliseert. We kunnen het optimalisatieprobleem dan beschrijven als:
x* = arg min f(x)
waarin f(x)=E(F(x,y;p)) de verwachte waarde is die we krijgen als we oneindig veel simulaties zouden uitvoeren. Hierbij moeten we natuurlijk rekening houden met het feit dat x* netjes aan alle randvoorwaarden moet voldoen, met andere woorden: x* moet realiseerbaar zijn.
De grootste uitdaging bij het aanpakken van dit soort problemen is dat we f(x) niet zomaar kunnen uitschrijven in een paar wiskundige formules: we kunnen de te optimaliseren functie f(x) alleen schatten met behulp van een stochastische simulatie. Om dat goed te doen moeten we voldoende simulaties uitvoeren, totdat de juiste verkeersregeling is gevonden. We noemen deze aanpak Simulation-based Optimalisation (SO).
Netwerkniveau?
Voor simpele problemen (een kruispunt) werkt deze methode uitstekend: dankzij SO-algoritmes kunnen we inderdaad de optimale regelaanpak vinden. Onderzoekers gingen daarom al snel op zoek naar meer. Zouden we de SO-aanpak kunnen gebruiken om te bepalen hoe we meerdere verkeersmanagementmaatregelen in samenhang kunnen inzetten?
Het antwoord was nee. Het probleem is namelijk dat er met de gewone SO-aanpak niet gericht wordt gesimuleerd. Simpel gezegd: het model beschikt niet over kennis van het achterliggende probleem, maar ontdekt ‘simulerenderwijs’ wat de beste oplossing is. Daarbij wordt bijvoorbeeld gebruik gemaakt van principes uit de biologie, zoals evolutie in een genetisch algoritme. Dat is nog te doen als het om een enkele verkeersregeling gaat, maar het op deze wijze doorrekenen van een wat groter netwerk met meerdere maatregelen vereist zoveel simulaties, dat de benodigde rekentijd te lang is. Het toegepaste onderzoek verlegde de aandacht daarom naar alternatieve aanpakken, zoals HERO, de aanpak Gecoördineerd Netwerkbreed Verkeersmanagement (GNV, zoals ontwikkeld binnen de Praktijkproef Amsterdam) en de decentrale Backpressure-methode.
Nieuwe SO-aanpak
Maar zoals gezegd, er gloort hoop. In 2013 ontwikkelden Osorio en Bierlaire et al een nieuw, efficiënter algoritme dat ervoor zorgt dat we veel gerichter simuleren. [1] Het betreft in feite een SO-metamodel dat de output van de simulator slim combineert met de informatie van een simpel macroscopisch analytisch en differentieerbaar verkeersmodel als MARPLE, STAQ of nog iets veel eenvoudigers. In principe kunnen we gebruik maken van elk model, zolang we maar de afgeleide ∇m(x) van de beslisvector x naar de modeluitkomsten m(x) kunnen uitrekenen en we het model kunnen ‘fitten’ op de uitkomsten van het simulatiemodel.
In deze bijdrage gaan we uit van een eenvoudig analytisch wachtrijmodel, waarmee we op rudimentaire wijze de terugslag van wachtrijen beschrijven. Dit model maakt het mogelijk om de doelfunctie analytisch te benaderen.
We veronderstellen de volgende vorm:
Hierin is fA (x,z;q) de benadering van de prestatie van het netwerk, gegeven de beslisvector x en de endogene variabelen z, waaronder de verdeling van de lengte van de wachtrijen die we kunnen afleiden uit het toepassen van het simulatiemodel. De parameters α en β (schaalparameters) en het functionele deel van het metamodel ϕ(x;β) worden gebruikt om het model te ‘fitten’ op de uitkomsten van het simulatiemodel.
In Osario et al (2015) wordt het volgende metamodel afgeleid:
Hierin stellen i alle relevante wachtrijen voor en li de maximale lengte van deze wachtrijen (voordat ze terugslaan); ρi is de verhouding tussen de aankomstintensiteit en de service rate voor de wachtrij i. [2] Hierbij gaan we ervan uit dat we de totale reistijd in het netwerk proberen te minimaliseren.
We zullen nu de iteratieve methode toelichten aan de hand van figuur 1. In een gegeven iteratie k doorloopt het algoritme de volgende stappen:
- Fit het metamodel mk, uitgaande van de simulatieresultaten tot nu toe. Anders gezegd: bepaal α, β en z.
- Gebruik mk om een optimalisatie uit te voeren en leid een zogenaamd trial point xk af.
- Evalueer de prestaties op dit trial point met behulp van de simulator. Dit leidt tot nieuwe simulatieresultaten.
Elk nieuw simulatieresultaat verbetert de nauwkeurigheid van het metamodel. Dit leidt vervolgens tot een beter trial point met verbeterde prestaties. Deze stappen kunnen net zo lang worden herhaald totdat de rekencapaciteit (rekentijd) ‘op’ is.
De crux van deze metamodel-benadering is dus dat we de (inefficiënte) stochastische respons van de simulatie vervangen door een deterministische metamodel-responsfunctie m, en wel op zo’n manier dat we (efficiënte) deterministische optimalisatietechnieken kunnen gebruiken.
Om te illustreren dat de aanpak met een SO-metamodel inderdaad goed werkt, gaan we tot slot kort in op een interessante casestudie met betrekking tot Manhattan, New York. Voor deze studie hebben we een microscopisch verkeerssimulatiemodel van de New York City Department of Transportation (NYCDOT) ingezet, gebruikmakend van Aimsun-software. Het model is gekalibreerd voor de doordeweekse ochtendspits. Het beschouwde netwerk betreft oostelijk Manhattan – zie figuur 2.
We vergelijken de prestaties van de regelingen die het SO-algoritme van het metamodel voorstelt (aangeduid met m), met de regelingen die NYCDOT momenteel in dat gebied gebruikt. Het SO-algoritme wordt ingezet met een limiet (budget) van 150 simulaties. Dat wil zeggen: zodra er 150 simulatieruns zijn uitgevoerd, stoppen we het algoritme en wordt uit die set het beste regelplan voor upper east Manhattan gekozen.
Met behulp van een simulator evalueren we beide regelplannen – de bestaande en het plan dat met de SO-methode is ontwikkeld. We schatten daarbij de volgende prestaties: (a) de verwachte totale wachtrijlengte in het netwerk; (b) de verwachte reistijd (minuten); (c) de verwachte dichtheid gemeten over het gehele netwerk (voertuigen per km); (d) de totale kans op terugslag, oftewel de som van alle terugslagkansen van alle wachtrijen; en (e) de verwachte netwerkcapaciteit (voertuigen per uur).
Om deze prestatie-indicatoren goed te kunnen schatten voeren we per regelplan 50 simulaties uit. Vervolgens plotten we de empirische cumulatieve verdelingsfunctie (cumulative distribution function, CDF) van elke prestatie-indicator. Elke CDF-curve bestaat dus uit 50 simulatieschattingen van de betreffende indicator. De ‘plots’ in figuur 3 betreffen steeds één indicator van twee regelplannen, waarbij de doorlopende lijn staat voor het bestaande regelplan en de stippellijn voor de SO-variant.
Uit figuur 3-a blijkt dat het voorgestelde SO-plan tot een aanzienlijke vermindering van de totale wachtrijlengte leidt: de gemiddelde vermindering ligt rond 26%. De maximale wachtrijlengte blijft bij een op SO gebaseerd plan beperkt tot 400 voertuigen, wat lager is dan de kleinste waarde van het bestaande plan.
Figuur 3-b laat zien dat met het SO-plan de verwachte reistijd afneemt met gemiddeld 10%. Ook de verwachte dichtheid neemt af (3-c), terwijl de netwerkcapaciteit (3-e) juist toeneemt.
Interessant is ook figuur 3-d, die laat zien dat de kans op terugslag significant afneemt. Gemiddeld gaat het om een 25% kleinere kans. Dit toont aan dat het met het gebruikte algoritme goed mogelijk is om het terugslaan van wachtrijen netwerkbreed terug te dringen – en daarmee de kans op (extra) congestie te verminderen. Ook is de spreiding van de kans veel kleiner, wat duidt op extra stabiliteit.
Conclusies
Al met al is het SO-metamodel een zeer veelbelovende methode om verkeersregelingen in een netwerk te optimaliseren. Zoals de Manhattan-case laat zien, zijn er ronduit spectaculaire verbeterslagen mogelijk in de afhandeling van het verkeer.
Voor de komende tijd is het zaak om de theorie en de kennis opgedaan in de cases verder te beproeven en te vertalen naar geautomatiseerde toepassingen. Als dat lukt dan kunnen we met recht spreken van een regelrechte doorbraak in netwerkmanagement.
____
Noten
[1] C. Osorio, M. Bierlaire et al, A simulation-based optimization framework for urban transportation problems, Operations Research 61 (6) (2013) 1333–1345.
[2] Zie voor meer details: C. Osario et al, Reducing gridlock probabilities via simulation-based signal control, Transportation Research Procedia 6 ( 2015 ) 101 – 110.
____
De auteurs
Dr. Carolina Osorio is assistant professor aan de Massachusetts Institute of Technology.
Prof. dr. ir. Serge Hoogendoorn is hoogleraar Verkeersstromen aan de TU Delft.
