Traffic Optimization as a Networks Problem
As we saw in the first couple of lectures, networks are structures that can be used to model and solve a multitude of problems. One of the more interesting problems that utilizes graphs as an abstraction is that of road traffic optimization; that is, the optimization of traffic light patterns in a city to minimize the number of traffic jams.
How can this be modeled into a graph with nodes and edges?
Imagine every road as a directed edge, and every intersection as a node. Further, imagine a car positioned at any of these intersection nodes. It is free to travel to another adjacent node, as long as there is an edge connecting them in the direction of travel. In other words, an edge represents a road whose start node currently has a green light in the direction of the destination node.
Now, we can model the traffic optimization problem as follows:
- To represent a green light from one intersection to another, simply draw a directed edge between them
- To represent a red light from one intersection to another, take away the directed edge between them (if any)
- Assume that the nodes and edges are oriented in 2-D space, i.e. their positioning does carry meaning
- There is a counter on each node that represents the number of cars currently waiting at the corresponding intersection
- Suppose that every car in the city has an origin node and destination node
- Each car will traverse the graph towards its destination if an edge in the desired direction is currently available
- If there is no outgoing edge in the desired direction, the car will wait at the node, and add to the counter on that specific node
Given this model, we would intuitively like the minimize the maximum of the counters on all the nodes. In other words, we’d like to reduce the maximum traffic present on any given mode. To do this, we would have to control the flow of traffic between nodes by removing and adding edges either according to a pre-defined algorithm, or dynamically based on the counters on the nodes. Hence, this model is an abstraction for controlling traffic light patterns at intersections.
Note: At every instance, we must ensure that the configuration of edges does not result in potential collisions. Thus, no configuration can have intersecting edges.
Optimization Strategies
There are two main optimization strategies used to control the flow of traffic.
The first is the static strategy in which every traffic light has a pre-defined pattern to follow, which solely depends on the current day and current time. ‘Green wave’ is a common signal timing strategy used in cities in Europe, as well as in New York. It involves making a string of traffic signals green with appropriate delays in between. This results in vehicles travelling through the entire chain of intersections without stopping, hence effectively reducing fuel consumption and carbon emissions.
[“GreenWave” by Grüne_welle_2.PNG Original uploader was Honina at de.wikipedia
derivative work: JedNie – Grüne_welle_2.PNG. Licensed under CC BY-SA 3.0 via Commons.]
The second one is a dynamic strategy, which takes into account the current traffic situation to figure out the next best edge to add or remove. There are implementations of dynamic strategies — or ‘smart’ traffic lights — currently being developed to be deployed in several cities. These systems take into consideration several factors, including the traffic at neighboring intersections, to ‘smartly’ allocate green lights to traffic signals. If implemented well, these systems can even handle unexpected traffic jams due to accidents, rain or other events.