Application of Graph Theory for Traffic Management

Importance of Traffic Management

Traffic management is critical in controlling the flow of traffic while also mitigating collisions. There are various systems of traffic control that are used around the world. The dominant traffic system used in Canada is traffic lights. Figure 1 displays a positive trend of the total population of Canada from 1999 to 2019. Figure 2 displays a similar trend to Figure 1 such that the total number of vehicles registered since 1999 has also increased.

We can conclude that the population size is proportional to the volume of vehicles on the road. With a population size growing, the volume on vehicles and pedestrians will continue to increase. Therefore, is it important that the traffic arrangements for the traffics light are optimal to maximize efficiently of traffic flow, but also reduce the risk of accidents.

How do we figure out what the most optimal settings for each traffic light at every intersection? This is where graph theory can be used to answer our question.

Using Graph Theory for Traffic Management

In this paper, the crossroad analyzed is the most common type of intersection that encountered. The blue arrows are depicting the various flows of traffic (Figure 3).

The corresponding graph for this crossroad is as follows (Figure 4). This is referred to as the compatible graph.

The compatible graph was formed following these guidelines:

• Each direction of flow will exist as vertices
• An edge exists between two vertices if and only if both directions can exist simultaneously without any collisions. If true, we can say those two vertices have compatible flows.
  • For example, a has an edge to every vertex except for d because there would be a collision between two vehicles if a and d run simultaneously. Thus, a is compatible with every vertex except d.

Using the compatible graph, various mathematical models can be derived. The mathematical models can also include other important parameters that need to be considered such as volume of traffic flow, density of traffic flow, and wait times.

Sources

Setiawan, Ekky & Budayasa, I Ketut. (2017). Application of graph theory concept for traffic light control at crossroad. AIP Conference Proceedings. 1867. 020054. 10.1063/1.4994457.

Statistics Canada. (2020, September 10). Chart 1 Vehicle registrations. Statistics Canada. Retrieved October 20, 2022, from https://www150.statcan.gc.ca/n1/daily-quotidien/200910/cg-d001-eng.htm