Voor het ontwerpen van starre verkeerslichtenregelingen gebruiken verkeersregelkundigen meestal óf de klassieke methode óf de kritieke-padmethode. Recent ontwikkelde DTV Consultants echter een heel nieuwe aanpak, die volgens het bedrijf beduidend sneller werkt. De crux van de nieuwe Graphium-methode, zo leggen de auteurs van deze bijdrage uit, is dat ze niet uitgaat van ‘conflictgroepen’ maar juist van niet-conflicterende richtingen.
In Nederland gebruiken verkeersregelkundigen vooral de in het Handboek Verkeerslichtenregelingen genoemde ‘klassieke methode’ om verkeerslichtenregelingen te ontwerpen. Deze methode gaat uit van conflictgroepen: richtingen die onderling conflicteren en dus na elkaar groen moeten krijgen. Voor alle conflictgroepen berekenen we de cyclustijd. De groep met de grootste cyclustijd is de maatgevende conflictgroep en die wordt automatisch in het fasediagram gezet – zie afbeelding 1 voor een voorbeeld. Daarna voeren we de overige richtingen met de hand toe.
In veel situaties volstaat deze methode prima, maar er kleven toch ook nadelen aan. In de eerste plaats is het handmatig aanvullen van het fasediagram tijdrovend en weinig consistent: in feite kan elke ontwerper op een verschillende oplossing uitkomen. De blokkenstructuur ten behoeve van verkeersafhankelijke regelingen moeten we ‘op het oog’ uit het fasediagram lezen. Bij het invullen van de overige richtingen in het fasediagram blijkt vaak dat deze niet passen onder het groen van de maatgevende conflictgroep. Het komt ook geregeld voor dat het aantal stappen (aantal richtingen) in de maatgevende conflictgroep niet voldoende is om alle richtingen minimaal één keer te realiseren. En last but not least: er wordt met de klassieke methode maar één oplossing voorgesteld en doorgerekend, terwijl er na invulling van de overige richtingen misschien wel betere oplossingen zijn.
In het Handboek Verkeerslichten wordt daarom ook de zogenoemde kritieke-padmethode genoemd. Het ‘kritieke pad’ is de opeenvolging van richtingen die de lengte van een cyclus bepalen. Dit pad blijkt niet altijd via de maatgevende conflictgroep te lopen, maar langs meerdere groepen. De kritieke-padmethode houdt hier rekening mee en lost daarmee de genoemde problemen van de klassieke methode op. Maar ook deze aanpak heeft weer zijn nadelen. In de praktijk blijken we lang niet alle kruispunten met de methode te kunnen doorrekenen. Ook vereist de (geautomatiseerde) berekening de nodige rekenkracht, wat er vooral bij complexe kruispunten op neerkomt dat de kritieke-padmethode niet snel genoeg is.
Op zoek naar een alternatief
In 2013 zijn we daarom op zoek gegaan naar een alternatieve methode voor het ontwerpen van verkeerslichtenregelingen. Om daadwerkelijk te kunnen spreken van een verbetering moest de methode aan een aantal voorwaarden voldoen:
- geschikt om van alle haalbare oplossingen zowel een ingevuld fasendiagram als de blokkenstructuur te verkrijgen (een haalbare oplossing is er één met een cyclustijd die kleiner is dan een instelbare waarde)
- met het juiste aantal benodigde blokken (ongeacht of dit gelijk is aan de lengte van een maatgevende conflictgroep)
- met zo min mogelijk uitzonderingen
- snel rekenend.
De eerste twee punten zijn bedoeld om de tekortkomingen van de klassieke methode op te lossen, de laatste twee om een verbetering ten opzichte van de kritieke-padmethode te bereiken.
Een meer praktische randvoorwaarde was dat de methodiek gemakkelijk inpasbaar zou moeten zijn in het softwarepakket COCON.
Niet-conflicterende richtingen
In november 2013 konden we de eerste resultaten van ons werk presenteren op het Nationaal Verkeerskundecongres. Een naam had de methode toen nog niet, maar inmiddels spreken we van de Graphium-methode: een verwijzing naar de grafentheorie waarop de methode gebaseerd is. De resultaten zijn vergelijkbaar met die van de kritieke-padmethode, maar er worden volledig andere algoritmes gebruikt om tot dat resultaat te komen.
Anders dan bij de klassieke methode en de kritieke-padmethode kijkt Graphium in eerste instantie niet naar de conflicterende richtingen, maar juist naar de richtingen die samen groen licht kunnen krijgen, de niet-conflicterende richtingen. De richtingen van een kruispunten kunnen in een schema worden weergegeven (een graaf), waarbij punten (of knopen) de richtingen voorstellen. Een verbinding tussen twee punten geeft aan dat die richtingen tegelijkertijd groen licht kunnen hebben – zie het voorbeeld in figuur 2. In zo’n graaf is het relatief eenvoudig om te bepalen uit welke blokken een verkeerslichtenregeling kan bestaan. Een blok is namelijk hetzelfde als een maximale ‘clique’ in deze graaf. Een clique is een verzameling van punten die met elkaar verbonden zijn en een clique is maximaal wanneer er geen ander punt aan kan worden toegevoegd die ook met alle punten in de clique verbonden is.
Wanneer Graphium alle blokken heeft gevonden, gaat het op zoek naar alle combinaties van blokken die een geldige regeling opleveren. Een regeling is geldig als het benodigde aantal blokken minimaal is, alle richtingen minimaal één keer in de regeling voorkomen en opgelegde koppelingen tussen richtingen, zoals synchroonstart en coördinaties in de regeling mogelijk zijn. Vervolgens berekent Graphium voor elke oplossing de cyclustijd en groentijden van de richtingen en vult daarmee het fasediagram in. Het fasediagram kan daarbij geoptimaliseerd worden naar minimale cyclustijd (waarbij de verzadigingsgraden van alle richtingen niet hoger zijn dan een opgegeven maximum) of naar minimale verliestijd volgens Akçeliks verliestijdformule.
Zoals we hierboven al opmerkten, was een van de doelstellingen bij de ontwikkeling van Graphium dat de rekentijd zo kort mogelijk moet zijn. Met een klein voorbeeld kunnen we laten zien, dat we daar inderdaad in geslaagd zijn. We hebben voor twee verkeersregelinstallaties (VRI’s) de rekentijd van Graphium vergeleken met die van VRIGen, een programma dat rekent met de kritieke-padmethode. De eerste VRI is voor een fictief viertakskruispunt met twaalf richtingen voor autoverkeer. De tweede VRI is voor een bestaand kruispunt, bestaande uit 27 richtingen met coördinaties tussen een aantal richtingen. Bijgaande tabel laat de rekentijden zien voor beide programma’s en beide VRI’s. De rekentijden zijn weliswaar gemeten met een stopwatch, maar de rekentijd van Graphium is duidelijk korter. Daarbij moet opgemerkt worden dat voor de tweede VRI VRIGen gestopt is bij 250 oplossingen, terwijl er meer oplossingen zijn. Het is daarom niet zeker dat VRIGen in dit geval ook de beste oplossing berekend heeft.
Discussie
Zowel de klassieke methode als de kritieke-padmethode geven een oplossing voor een starre regeling en Graphium is hierin niet anders. Het is gebruikelijk om eerst een starre regeling te ontwerpen en deze als basis te gebruiken voor een voertuigafhankelijke regeling. Echter, wat voor een starre regeling de beste oplossing is, is dat niet per se voor een voertuigafhankelijke regeling. Graphium heeft in dit opzicht dus ook nog verbetermogelijkheden.
Wat Graphium en de kritieke-padmethode op dit punt wel voor hebben op de klassieke methode, is dat ze met meerdere oplossingen komen. Simulaties kunnen dan uitsluitsel geven over welke oplossing het beste is als voertuigafhankelijke regeling. Omdat verkeersconforme simulaties over het algemeen duur zijn, onderzoeken we momenteel andere mogelijkheden om regelingen snel en goedkoop onder voertuigafhankelijke omstandigheden te simuleren.
De rekensnelheid van Graphium opent weer hele nieuwe mogelijkheden. Zo zou dynamische toepassing van (een deel van) de algoritmes mogelijk zijn. In de toekomst kan dat leiden tot regelingen die zichzelf ontwerpen en inregelen. Een deel van het ontwerpproces wordt dan overbodig en de verkeersregelkundige kan zich concentreren op een zo goed mogelijk kruispuntontwerp en op de beleidsdoelstellingen.
____
De auteurs
Carl Stolz en Bart Veroude Bsc. zijn respectievelijk senior adviseur en senior analist bij DTV Consultants.
