Self-organising traffic control algorithms at signalised intersections
Date
2015-04
Authors
Einhorn, Mark David
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: The debilitating social, economic and environmental ramifications of traffic congestion are experienced
in large cities the world over. The optimisation of traffic signal timings at signalised
road intersections attempts to mitigate the extent of these adverse effects of traffic congestion
by reducing the delay time experienced by vehicles in a transport network. Today, traffic signal
control schemes may be classiffied into one of two main classes, namely fixed-time traffic signal
control strategies, which are typically cyclic in nature, and vehicle-actuated traffic signal control
strategies, which are typically acyclic in nature. Generally, cyclic control strategies tend to lack
exibility, and are unable to adapt to short-term uctuations in traffic ow rates, resulting in green times that are either too long or too short. On the other hand, acyclic control strategies
tend to lack coordination between intersections, resulting in vehicles being required to stop at
the majority of signalised intersections they encounter.
Self-organising traffic signal control has been proposed as an attractive alternative form of control
which both exhibits exibility and facilitates a global coordination between intersections as a
result of localised signal switching policies. Two examples of existing self-organising traffic signal
control algorithms from the literature include an algorithm proposed by Lammer and Helbing
in 2008 and an algorithm proposed by Gershenson and Rosenblueth in 2012. These algorithms
have been shown to outperform both optimised fixed-time traffc signal control techniques as well
as state-of-the-art vehicle actuated trffic signal control techniques, in terms of reducing vehicle
delay time in a transport network. A draw-back of both of these self-organising approaches,
however, is that their effective operation relies on carefully selected parameter values; poorly
selected parameter values may render these algorithms very ineffectual.
In this dissertation, three novel self-organising traffic signal traffic control algorithms are proposed.
These three algorithms assume the use of existing radar detection sensors mounted at
the intersection to provide the necessary input data. The radar detection sensors are capable
of detecting and tracking individual vehicles approaching an intersection, providing real-time
information pertaining to their physical dimensions, velocities, and ranges from the intersection
in terms of both time and distance. The three traffic signal control algorithms are free of any
user-specialised parameters, and instead rely solely on the data provided by the radar detection
sensors to inform their signal switching policies.
The first of these traffic signal control algorithms is inspired by inventory control theory, and
draws parallels between the monetary costs typically considered in inventory control models
and the delay time costs associated with traffic control at signalised intersections, which the
algorithm attempts to minimise.
The second novel traffic control algorithm is inspired by the chemical process of osmosis in
which solvent molecules move unaided from a region where they are highly concentrated, across
a semi-permeable membrane, into a region of high solute molecule concentration. The algorithm
models vehicles approaching an intersection as solvent molecules and the physical space available
for the vehicles to occupy once they have passed through the intersection as solute molecules.
Following this analogy, the intersection is considered to be the semi-permeable membrane.
The third traffic control algorithm is a hybrid of the inventory and osmosis-inspired algorithms
together with an intersection utilisation maximisation technique, which prevents unnecessary or
prolonged underutilisation of an intersection.
The three novel trafficc control algorithms, together with the algorithms of Lammer and Helbing,
and of Gershenson and Rosenblueth, as well as a fixed-time control algorithm, are implemented
in a purpose-built microscopic traffic simulation modelling framework. Several measures are
employed to evaluate the relative performances of the algorithms. These measures include
the usual mean and maximum resulting delay times incurred by vehicles and the saturation
level of the roadways in the transport network, as well as three novel performance measure
indicators which include the mean number of stops made by vehicles, their mean normalised
delay time and the mean normalised number of stops made. The algorithms are compared in
the context of a linear corridor road network topology as well as a grid road network topology
under various traffic
ow conditions. The overall performance of the novel hybrid traffic signal
control algorithm is found to be superior for the corridor road network topology, while the
performance of the osmosis-inspired algorithm is found to be superior for the grid road network
topology.
AFRIKAANSE OPSOMMING:Die negatiewe sosiale, ekonomiese en omgewingsimpak van verkeersopeenhoping word in groot stede regoor die w^ereld ervaar. Die doel met die optimering van verkeersligwerkverrigting by straatkruisings is om die omvang van hierdie negatiewe impak tee te werk deur die vertraging van voertuie in 'n vervoernetwerk te verminder. Hedendaagse verkeersbeheeralgoritmes kom in een van twee hoofklasse voor, naamlik vaste-tyd beheerstrategiee, wat gewoonlik siklies van aard is, en beheerstrategiee gebaseer op voertuigopsporing, wat tipies asiklies van aard is. Oor die algemeen beskik sikliese beheerstrategiee nie oor genoegsame buigsaambeid om aan te pas by kort-termyn fluktuasies in verkeersvloei nie, wat tipies daartoe lei dat hul groentye spesifiseer wat of te lank of te kort is. Aan die ander kant is asikliese beheerstrategiee nie daartoe in staat om koordinasie tussen naasliggende straatkruisings te bewerkstellig nie, wat weer daartoe lei dat voertuie genoodsaak word om by die oorgrote meerderheid straatkruisings op hul pad te stop. Die self-organiserende beheer van verkeersligte is as 'n aantrektlike, buigsame alternatief voorgestel wat in staat is om globale koordinasie tussen naasliggende straatkruisings as gevolg van gelokaliseerde seinstrategiee te bewerkstellig. Twee voorbeelde van bestaande self-organiserende verkeersbeheeralgoritmes in die literatuur is die algoritmes wat in 2008 deur Lammer and Helbing en in 2012 deur Gershenson en Rosenblueth voorgestel is. Daar is aangetoon dat hierdie algoritmes daartoe in staat is om ge-optimeerde vaste-tyd beheerstrategiee sowel as gevorderde strategiee gebaseer op voertuigopsporing uit te stof in terme van 'n vermindering van die vertraging van voertuie in 'n vervoernetwerk. 'n Nadeel van beide hierdie self-organiserende benaderings is egter dat hul doeltreffende werkverrigting berus op versigtig-gekose parameterwaardes; willekeurige parameterwaardes mag lei na hoogs ondoeltreffende werkverrigitng van die algoritmes. Drie nuwe self-organiserende verkeersbeheeralgoritmes word in hierdie proefskrif voorgestel. Hierdie drie algoritmes maak vir hul toevoerdata staat op die beskikbaarhed van bestaande radar opsporingsensors wat by straatkruisings geinstalleer is. Die sensors is daartoe in staat om individuele voertuie wat 'n straatkruising nader, op te spoor, te volg en intydse data oor hul fisiese dimensies, snelhede, en afstande na die kruising (in terme van beide tyd en afstand) te lewer. Die drie algoritmes bevat geen gebruikers-gespesifiseerde parameters nie, en maak in plaas daarvan slegs gebruik van die sensortoevoerdata om hul beheerstrategiee te bepaal. Die eerste van hierdie verkeersbeheeralgoritmes is deur die teorie van voorraadbeheer geinspireer en maak gebruik van parallelle tussen die monet^ere kostes wat tipies in voorraadbeheermodelle voorkom en die kostes in terme van vertragingstyd wat met verkeersbeheer by straatkruisings aangegaan word, en wat deur die algoritme geminimeer word. Die tweede verkeersbeheeralgoritme is deur die chemiese proses van osmose geinspireer, waar molekules van 'n oplossingsmiddel sonder eksterne hulp vanaf 'n gebied waar hul in hoe konsentrasie voorkom, deur 'n gedeeltelik-deurlaatbare membraan beweeg na 'n gebied waarin hul ook in hoe konsentrasie, maar in opgeloste vorm voorkom. Die algoritme modelleer voertuie wat 'n straatkruising nader as die molekules van die oplossingsmiddel en die fisiese ruimte wat aan die ander kant van die kruising beskikbaar is om deur voertuie beset te word, as molekules in opgeloste vorm. In hierdie analogie word die kruising self as die gedeeltelik-deurlaatbare membraan beskou. Die derde algoritme is 'n hibriede strategie waarin elemente van die eerste twee algoritmes in samewerking met 'n tegniek vir die maksimering van straatkruisingsbenutting gekombineer word, en wat wat ten doel het om onnodige of verlengte onderbenutting van die kruising te vermy. Hierdie drie nuwe verkeersbeheeralgoritmes word, tesame met die bestaande algoritmes van Lammer en Helbing, en van Gershenson en Rosenblueth, asook 'n vaste-tyd beheeralgoritme, in 'n mikroskopiese verkeersimulasiemodelleringsraamwerk wat spesifiek vir die doel ontwerp is, geimplementeer. Verskeie maatstawwe word ingespan om die relatiewe werkverrigting van die algoritmes te evalueer. Hierdie maatstawwe sluit in die gebruiklike gemiddelde en maksimum vertragingstye van voertuie en die versadigingsvlak van strate in die vervoernetwerk, sowel as drie nuwe maatstawwe, naamlik die gemiddelde aantal stoppe deur voertuie, hul genormaliseerde vertragingstye en die gemiddelde, genormaliseerde aantal stoppe. Die algoritmes word in die kontekste van 'n line^ere topologie van opeenvolgende straatkruisings en 'n netwerktopologie van reghoekige straatblokke onder verskeie verkeersdigthede met mekaar vergelyk. Daar word bevind dat die nuwe hibriede algoritme die beste vaar in die line^ere topologie, terwyl die osmose-ge inspireerde algoritme die ander algoritmes uitstof in die straatblok-netwerktopologie.
AFRIKAANSE OPSOMMING:Die negatiewe sosiale, ekonomiese en omgewingsimpak van verkeersopeenhoping word in groot stede regoor die w^ereld ervaar. Die doel met die optimering van verkeersligwerkverrigting by straatkruisings is om die omvang van hierdie negatiewe impak tee te werk deur die vertraging van voertuie in 'n vervoernetwerk te verminder. Hedendaagse verkeersbeheeralgoritmes kom in een van twee hoofklasse voor, naamlik vaste-tyd beheerstrategiee, wat gewoonlik siklies van aard is, en beheerstrategiee gebaseer op voertuigopsporing, wat tipies asiklies van aard is. Oor die algemeen beskik sikliese beheerstrategiee nie oor genoegsame buigsaambeid om aan te pas by kort-termyn fluktuasies in verkeersvloei nie, wat tipies daartoe lei dat hul groentye spesifiseer wat of te lank of te kort is. Aan die ander kant is asikliese beheerstrategiee nie daartoe in staat om koordinasie tussen naasliggende straatkruisings te bewerkstellig nie, wat weer daartoe lei dat voertuie genoodsaak word om by die oorgrote meerderheid straatkruisings op hul pad te stop. Die self-organiserende beheer van verkeersligte is as 'n aantrektlike, buigsame alternatief voorgestel wat in staat is om globale koordinasie tussen naasliggende straatkruisings as gevolg van gelokaliseerde seinstrategiee te bewerkstellig. Twee voorbeelde van bestaande self-organiserende verkeersbeheeralgoritmes in die literatuur is die algoritmes wat in 2008 deur Lammer and Helbing en in 2012 deur Gershenson en Rosenblueth voorgestel is. Daar is aangetoon dat hierdie algoritmes daartoe in staat is om ge-optimeerde vaste-tyd beheerstrategiee sowel as gevorderde strategiee gebaseer op voertuigopsporing uit te stof in terme van 'n vermindering van die vertraging van voertuie in 'n vervoernetwerk. 'n Nadeel van beide hierdie self-organiserende benaderings is egter dat hul doeltreffende werkverrigting berus op versigtig-gekose parameterwaardes; willekeurige parameterwaardes mag lei na hoogs ondoeltreffende werkverrigitng van die algoritmes. Drie nuwe self-organiserende verkeersbeheeralgoritmes word in hierdie proefskrif voorgestel. Hierdie drie algoritmes maak vir hul toevoerdata staat op die beskikbaarhed van bestaande radar opsporingsensors wat by straatkruisings geinstalleer is. Die sensors is daartoe in staat om individuele voertuie wat 'n straatkruising nader, op te spoor, te volg en intydse data oor hul fisiese dimensies, snelhede, en afstande na die kruising (in terme van beide tyd en afstand) te lewer. Die drie algoritmes bevat geen gebruikers-gespesifiseerde parameters nie, en maak in plaas daarvan slegs gebruik van die sensortoevoerdata om hul beheerstrategiee te bepaal. Die eerste van hierdie verkeersbeheeralgoritmes is deur die teorie van voorraadbeheer geinspireer en maak gebruik van parallelle tussen die monet^ere kostes wat tipies in voorraadbeheermodelle voorkom en die kostes in terme van vertragingstyd wat met verkeersbeheer by straatkruisings aangegaan word, en wat deur die algoritme geminimeer word. Die tweede verkeersbeheeralgoritme is deur die chemiese proses van osmose geinspireer, waar molekules van 'n oplossingsmiddel sonder eksterne hulp vanaf 'n gebied waar hul in hoe konsentrasie voorkom, deur 'n gedeeltelik-deurlaatbare membraan beweeg na 'n gebied waarin hul ook in hoe konsentrasie, maar in opgeloste vorm voorkom. Die algoritme modelleer voertuie wat 'n straatkruising nader as die molekules van die oplossingsmiddel en die fisiese ruimte wat aan die ander kant van die kruising beskikbaar is om deur voertuie beset te word, as molekules in opgeloste vorm. In hierdie analogie word die kruising self as die gedeeltelik-deurlaatbare membraan beskou. Die derde algoritme is 'n hibriede strategie waarin elemente van die eerste twee algoritmes in samewerking met 'n tegniek vir die maksimering van straatkruisingsbenutting gekombineer word, en wat wat ten doel het om onnodige of verlengte onderbenutting van die kruising te vermy. Hierdie drie nuwe verkeersbeheeralgoritmes word, tesame met die bestaande algoritmes van Lammer en Helbing, en van Gershenson en Rosenblueth, asook 'n vaste-tyd beheeralgoritme, in 'n mikroskopiese verkeersimulasiemodelleringsraamwerk wat spesifiek vir die doel ontwerp is, geimplementeer. Verskeie maatstawwe word ingespan om die relatiewe werkverrigting van die algoritmes te evalueer. Hierdie maatstawwe sluit in die gebruiklike gemiddelde en maksimum vertragingstye van voertuie en die versadigingsvlak van strate in die vervoernetwerk, sowel as drie nuwe maatstawwe, naamlik die gemiddelde aantal stoppe deur voertuie, hul genormaliseerde vertragingstye en die gemiddelde, genormaliseerde aantal stoppe. Die algoritmes word in die kontekste van 'n line^ere topologie van opeenvolgende straatkruisings en 'n netwerktopologie van reghoekige straatblokke onder verskeie verkeersdigthede met mekaar vergelyk. Daar word bevind dat die nuwe hibriede algoritme die beste vaar in die line^ere topologie, terwyl die osmose-ge inspireerde algoritme die ander algoritmes uitstof in die straatblok-netwerktopologie.
Description
Thesis (PhD)--Stellenbosch University, 2015.
Keywords
UCTD, Traffic signs and signals, Electronic traffic controls, Self-organizing systems, Traffic signs and signals -- Automation