Stochastic User Equilibrium with Full Route Set in Dynamic Traffic Assignment

Jeroen Verstraete Willem Himpe
Een volledige route set convergeert snel in een verkeers toedelings evenwicht en bevat zeker alle relevante alternatieven. Een volledige route set is hier geintroduceerd in een dynamische verkeerstoedeling.

Stochastisch gebruikersevenwicht met volledige route set in dynamische verkeerstoedeling

Om verkeer goed te kunnen modelleren is een route set heel belangrijk. Een route set bevat alle routes die in het model beschouwd worden. Tijdens het uitvoeren van het algoritme, kan de route set vast of flexibel zijn. Een vaste route set heeft als voordeel dat er enkel een evenwicht gezocht hoeft te worden onder de stromen. Een algoritme met een vaste route set convergeert dan ook sneller. Het grote nadeel aan een vaste route set stelt zich voor het uitvoeren van het algoritme. Hoe bepaal je nu welke routes er wel en niet inzitten? (En dit voor dat de evenwichtsbelasting op de linken bekend zijn!) Een manier om dit op te lossen is om een flexibele route set te gebruiken. Het algoritme bekijkt tijdens de uitvoering welke route set er gebruikt moet worden. Dit verhoogt uiteraard de complexiteit, niet enkel hoeft nu de stromen convergeren, ook de route set moet convergeren. Dat dit een groot probleem kan vormen, toont het volgende voorbeeld aan. Dials algoritme werkt (door invoering van een topologie) met een flexibele route set. Neem het volgende simpele netwerk, waar verkeer van knooppunt 1 naar knooppunt 2 wilt gaan. Hiervoor zijn 2 verschillende alternatieven beschikbaar. Tijdens het uitvoeren van het algoritme zien we dat het algoritme niet convergeert. Dit ligt aan het feit dat het algoritme steeds wisselt tussen twee route sets. Namelijk de punten die beide routes bevatten en de cirkels die enkel de kortste route bevat.

Example network

Dials convergence

Bell (1995) en Fosgerau (2013) hebben hiervoor een oplossing gemaakt. Om de goede convergentie te behouden van een vaste route set, is gekozen voor een volledige route set. Doordat deze route set alle mogelijke routes bevat, blijft deze constant tijdens de uitvoering van het algoritme. Uiteraard zijn er oneindig veel mogelijke routes, tenminste als het netwerk cirkels toelaat. Dit betekent dat de route set impliciet zal zijn. In tegenstelling tot expliciete route sets, waar alle beschouwde routes expliciet opgesomd worden, worden de routes hier impliciet beschouwd. Dit kan gedaan worden door alle mogelijke draai bewegingen te omschrijven. Bell en Fosgerau hebben zo het Recursive Logit omschreven. De recursive logit beschouwt de kans dat een bepaalde beweging wordt genomen, gegeven de eindbestemming (maar onafhankelijk van de begin plaats). Dit gebeurd door dezelfde utiliteiten definities als Dial (71), met het enige verschil dat er nu geen volgorde van de knooppunten is. Dit impliceert dat knooppunt utiliteiten van zich zelf kunnen afhangen. Dit levert een stelsel van vergelijkingen op. Met deze utiliteiten kan de kans op een bepaalde beweging (voor een bepaalde bestemming) berekend worden. Alleen is dit momenteel enkel gedaan in een statische toedeling. Meer en meer wordt gebruik gemaakt van dynamische toedelingen. (Bv. Het dynamisch model van Antwerpen en Brussel dat het Vlaams verkeercentrum samen met TML ontwikkelt) De bijdrage van deze thesis wordt dan ook het model zo aanpassen dat het toepasbaar wordt in een dynamische verkeerstoedeling. Om dit te doen, is het model eerst toegepast in een statische toedeling.

Hieruit bleek direct dat er wel degelijk potentieel in het model zit door de betere convergentie. Op een semi logaritmse schaal vertoont de convergentie een lineair verloop. Dit komt omdat een proportionele stap grootte gebruikt kan worden. Een klein vooronderzoek hieromtrent is gebeurd in de thesis die aantoont dat er wellicht nog betere stapgroottes genomen kunnen worden.

convergence

Een nadeel aan Recursive Logit en aan het feit dan echt alle routes beschouwd worden, is dat ook routes met een loop goede alternatieven worden. Dit is echter niet realistisch. Om dit beter te maken, kunnen penalty’s toegevoegd worden. Een voorbeeld is een hogere kost rekenen voor u-turns. Op deze manier worden minder loops gemaakt. Een klein voorbeeldje illustreert dit. Neem het onderstaand netwerk waar verkeer van onder naar boven wilt. Links is een toedeling zonder u-turn penalty, terwijl rechts die wel heeft. (In de thesis wordt verder gegaan op het verschil in de kansen.)

zonder penalty

met penalty

De grootste bijdrage is dus de methode te gebruiken in een dynamische verkeerstoedeling. Het idee is een statische toedeling te doen in de laatste tijdstap. Vanaf daar wordt er geïtereerd over de verschillende tijdslagen om de knooppunt utiliteiten te bepalen. (Met deze utiliteiten wordt dan de kans berekend.) Een beperking hierbij is dat de tijdstapgrootte kleiner moet zijn dan de kortste tijd van een link.

iteraties

Bij een dynamische toedeling worden dezelfde negatieve effecten ervaren van alle routes mee te nemen. Maar opnieuw kunnen deze opgelost worden door het introduceren van verschillende soorten penalty’s.  Doordat het probleem complexer geworden is, kan de stapgrootte niet meer gelijk zijn aan 1. Hieronder tonen een paar verschillende stap groottes hun invloed op de convergentie. Verder onderzoek kan zeker nog een betere stap grootte vinden, die de convergentie ten goede komt.

convergence

De conclusie luidt dus dat het mogelijk is deze formuleringen van Bell en Fosgerau toe te passen in een dynamische context. Omdat echter alle routes meegenomen worden, blijken sommige alternatieven die niet logisch zijn toch gekozen te zijn. Door het introduceren van verschillende soorten penalty’s kan die opgelost worden. Dit onderzoek opent de deuren voor verder onderzoek, zowel voor een grotere stap grootte als voor welke soort penalty’s er moeten worden geselecteerd.

Bibliografie

M. G. H. Bell. Alternatives to Dial’s logit assignment algorithm. Transportation Research
Part B, 29(4):287–295, 1995. ISSN 01912615. doi: 10.1016/0191-2615(95)00005-X.
M. E. Ben-akiva, S. Gao, Z.Wei, and Y.Wen. A dynamic traffic assignment model for highly
congested urban networks. Transportation Research Part C: Emerging Technologies, 24:
62–82, 2012. ISSN 0968090X. doi: 10.1016/j.trc.2012.02.006.
R. B. Dial and A. M. Voorhees. PROBABILISTIC MULTIPATH TRAFFIC ASSIGNMENT
WHICH OBVIATES PATH ENUMERATION The problem. Transpn Res, 5:83–111,
1971.
M. Fosgerau, E. Frejinger, and A. Karlstrom. A link based network route choice model with
unrestricted choice set. Transportation Research Part B: Methodological, 56:70–80, 2013.
ISSN 01912615. doi: 10.1016/j.trb.2013.07.012.
E. Frejinger, M. Bierlaire, and M. Ben-Akiva. Sampling of alternatives for route choice
modeling. Transportation Research Part B: Methodological, 43(10):984–994, 2009. ISSN
01912615. doi: 10.1016/j.trb.2009.03.001.
W. Himpe, R. Corthout, and M. J. C. Tampère. An efficient iterative link transmission model.
Transportation Research Part B: Methodological, 92:170–190, oct 2016. ISSN 01912615.
doi: 10.1016/j.trb.2015.12.013.
P. H. L Bovy. On Modelling Route Choice Sets in Transportation Networks: A
Synthesis. Transport Reviews, 29(1):43–68, 2009. ISSN 0144-1647. doi:
10.1080/01441640802078673.
H. Robbins and S. Monro. A Stochastic Approximation Method. The Annals of Mathematical
Statistics, 22(3):400–407, 1951. ISSN 0003-4851. doi: 10.1214/aoms/1177729586.
J. G.WARDROP. ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC
RESEARCH. Proceedings of the Institution of Civil Engineers, 1(3):325–362, may 1952.
ISSN 1753-7789. doi: 10.1680/ipeds.1952.11259.
F. V. Webster. TRAFFIC SIGNAL SETTINGS. Road Research Lab Tech Papers /UK/, 1958.

Universiteit of Hogeschool
Master in de ingenieurswetenschappen: verkeer, logistiek en intelligente transportsystemen
Publicatiejaar
2017
Promotor(en)
Prof. Dr. Ir. C. M.J. Tampère
Kernwoorden
Share this on: