Traffic Modelling: Is Beating Traffic Congestion a Zero-Sum Game?

Traffic congestion is a global problem. Last year, a study showed that Toronto is the 20th most congested city in the world with an average of 164 hours of driving time spent in congestion.

I’m not surprised.

Earlier in my career, I commuted twice a day for over an hour each way. In a year, that works out to roughly 21 days sitting in traffic. While my commute has improved since then, I still can’t help but wonder how much time commuters could save if we reduced traffic congestion. In my case, even a 10% improvement could have saved me a couple of days every year.

How Much Time Would We Save if Cars Drove Themselves?

It’s easy to imagine how self-driving cars could save us time. As our car drives us to work, we’d be able to at least read that book that we’ve been meaning to finish. With that benefit aside, let’s consider the actual time on the road. If we relinquished control to our artificially-intelligent automobiles, would we really end up spending less time in traffic? What if we relied on self-driving cars to keep us in a lane of traffic instead of trying to bypass congestion by changing lanes ourselves?

The goal of this two-part article is to answer this question quantitatively through the use of a simplified traffic model. In particular, the model aims to programmatically simulate traffic conditions and human behaviour. Before exploring how self-driving cars can manage traffic better than we can, there is a more fundamental question that we should answer.

Is Opportunistic Lane-Changing a Zero-Sum Game?

It’s a familiar struggle for regular commuters. The work meeting starts in half an hour, but the GPS is telling you that the ETA is in 36 minutes. Can you shave off those minutes with some clever, well-timed lane-changes?

If we haven’t done it ourselves, we’ve been a witness to (and victim of) other drivers “weaving” through traffic. Some may feel that these drivers are only taking time off their commute and adding it onto others. In other words, such opportunistic lane-changing behaviour seems like a “zero-sum game”. But is it?

A zero-sum game is defined as:

… a mathematical representation of a situation in which each participant’s gain or loss of utility is exactly balanced by the losses or gains of the utility of the other participants.

In our case, we say that opportunistic lane-changing is a zero-sum game when such behaviour over a given time period does not result in a better outcome for all commuters on the road. If we can conclude a zero-sum game, we can also conclude that self-driving cars can manage traffic better than humans simply by not changing lanes at all. In order to explore the “zero-sum game” hypothesis, I’ll clarify some terms and define what to measure.

Lane-Change Conditions

Let’s start with the notion of “opportunistic lane changing”. The term “opportunistic” is used to indicate that the driver acts opportunistically for their self-interest (i.e. they do not consider the effects of their actions on other drivers). In light of this, here are two-lane change conditions that seem reasonable:

“As a driver, I will change lanes if all of the following conditions are met:”

1. Changing to the other lane drops my remaining time in traffic by a certain percentage
2. I’ve spent a certain minimum length of time in my current lane

Traffic Performance Metrics

Second, we framed what a “better outcome” (or higher performance) means in our model by defining four quantitative metrics. Higher performance is indicated by lower values for the first three metrics (Average Time, Aggregate Time, and Cars Remaining), and a higher value for the fourth metric (Aggregate Throughput).

Average and Aggregate Time

The ideal length of time spent on the road is zero. Therefore, we defined two metrics:

• Average Time: The average time spent by drivers on the road
• Aggregate Time: A total of every driver’s time spent on the road

Cars Remaining

Given that both the number of cars entering the road as well as the simulation duration remain the same for all simulation runs, we can define an additional metric:

• Cars Remaining: The total number of cars remaining on the road at the end of the simulation

Aggregate Throughput

What if a simulation run results in a lower Aggregate Time, but a higher number of Cars Remaining? We defined the following metric to account for this:

• Aggregate Throughput = Cars Exited / Aggregate Time

Defining the Model

We modelled the total time on the road for a given car to be dependent on the number of other cars in its lane:

t[total] = f(n)

• t[total]: total time on road
• n: number of cars in the given lane

Subsequently, a given car’s remaining time on road t[remaining] is calculated as follows:

t[remaining] = t[total] – t[elapsed]

The elapsed time-on-road t[elapsed] is incremented as the simulation runs (more on this later). A car exits the road once t[remaining] reaches 0.

This approach avoids the need to track a car’s position on the road, thus simplifying the implementation of the model significantly.

Time on Road Function

t[total] = A * max(0, n – N) + M

The graph above portrays a simplified yet conceivable time-on-road function. The time M represents the minimum length of time-on-road, regardless of the number of cars in a given lane.

Similarly, N represents the “congestion-free” capacity of a lane of traffic. Once the number of cars grows beyond this number, the time-on-road increases proportionally to the number of cars in the lane. The number A represents the amount by which the time on the road increases in response to one additional car on the road.

Time Unit (Tick)

Due to this being a computer model, we introduce the notion of a tick. This serves two main purposes:

• An arbitrary unit of time used in the model
• The smallest progression step (or increment) in the simulation where a change can occur.

Simulation Overview

The diagram above represents the general design of the simulation. The key concepts are:

• Arrival Sequence: A pre-generated sequence of boolean values based on an arrival probability
• Lane Assigner (LA): If a Car arrives, it is assigned to a Lane at random
• Lanes (L1, L2, L3): Several Lanes that “contain” the Cars. While there is no limit to the number of Cars that can be placed in a Lane, the total time spent by each Car in it’s Lane is subject to the Time on Road function
• Car: Represents the vehicle in traffic. On every tick, a Car may or may not change lanes based on the Lane Change Conditions
• Lane Exit: Occurs for any Car in any Lane once t[elapsed]reaches t[total]
• Metrics Tracker: Tracks the Traffic Performance Metrics, as defined earlier

Behaviour on Tick

Here is what happens on every tick:

1. A value is popped off the Arrival Sequence
2. If there is an arrival, the Lane Assigner assigns it to a Lane
3. Cars who have met their Lane Change Conditions change Lanes
4. The time remaining is re-calculated for all Cars in all Lanes
5. Cars who have reached Zero Time Remaining exit the road
6. Steps 4 and 5 are repeated until no more Cars exit the road

Input Conditions

Here are the input conditions that are common to all simulation runs (i.e. controlled variables):

• Arrival Probability: For every tick, the likelihood of a car arriving. This value is close to 100% to simulate heavy traffic.
• Duration: Length of time to run the simulation for.
• Lane Change Delay: The amount of time added to their total time in lane (in ticks) if a car changes lanes. In other words, this is the time penalty for changing lanes.
• Time on Road Function: Defined as an input condition so that we can improve it in the future.
• Lanes: The number of lanes that the road is comprised of.
• Iterations: The number of iterations to run the simulation for.

Note that all times are in ticks (as covered earlier).

Here are the input conditions that are varied for every simulation run (i.e. independent variables):

• Lane Change Conditions: if this is undefined, then no lane changes occur. If it is defined, the following values are set (as introduced earlier):

• Minimum Time in Lane: The minimum time spent in the lane before a lane change is considered
• Minimum Time Saved Percentage: The minimum time saved by changing lanes (as a percentage)

Running the Simulations

Through trial and error, we determined an appropriate set of conditions. The ideal parameters should result in:

1. The number of Cars in Lane exceeding the congestion-free capacity most of the time
2. Most of the Cars exiting the Road by the end of the simulation

As we are interested in observing the effects of traffic congestion, point 1 is necessary. On the other hand, point 2 ensures we’re modelling a functional road (i.e. not in gridlock) that serves its purpose of “carrying” traffic through it.

Based on the above, here are the Input Conditions that we settled on:

Results: Effect of Varying Lane Change Conditions

We changed the two Lane Change Conditions independently, starting with Minimum Time in Lane.

Part A: Effect of changing Minimum Time in Lane

Keeping the Time Saved Percentage constant, we varied the Minimum Time in Lane.

Given that the Time Saved Percentage lane change condition remains constant at 60%, the model yields an optimum result at a Minimum Time in Lane of around 25 ticks. Also note that at lower values, it performs worse than the no-lane-changes case.

Part B: Effect of changing Time Saved Percentage

Next, we varied the Time Saved Percentage, while keeping Minimum Time in Lane constant at 2 ticks.

Similar to Part A, the simulation performs worse than the no-lane-changes case for results having lower values for Time Saved Percentage. Also, the simulation yields a better outcome as the Time Saved Percentage lane change condition is increased. The gains begin to taper off at around 200% with an Aggregate Throughput of approximately 4.15 cars / 100 ticks. (*)

(*) Lane changes occur even at very high values for Time Saved Percentage because a lane change will always occur when the time remaining in the new lane is zero.

Conclusion

The results yield three key conclusions:

1. Depending on input or lane change conditions, opportunistic lane changing can yield either a better or worse outcome than no lane changing.
2. There is an optimal combination of opportunistic lane change conditions that yield the best outcome possible.
3. Opportunistic lane changing can yield a significantly better outcome than no lane changing (~10%). Further simulation runs can determine a combined optimum for both lane change conditions that potentially yields an even better improvement than identified here.

If opportunistic lane changes in congested traffic were a zero-sum game, we would observe the same performance (Aggregate Throughput) for all simulation runs. Instead, we have discovered that opportunistic lane changing can be either less performant or more performant than no lane changing. Furthermore, a net-positive result for all drivers seems reasonably achievable, even while the drivers pursue an opportunistic lane-changing approach.

Therefore, we can conclude that opportunistic lane changing is not a zero-sum gain and can benefit all drivers on the road if exercised judiciously. This means not changing lanes too frequently (i.e. adhering to a reasonable minimum time in lane), and only changing lanes if it saves a significant amount of time (i.e. the time saved in the new lane is 90% or higher).

Next Steps

What do the results tell us about how to be a better driver? To state it simply: Be patient. Change lanes, but not frivolously. Everybody wins. Experienced drivers will likely not find this conclusion surprising.

The model could unlock more benefit by having actual traffic data mapped to it, doing so could yield a more concrete optimum range given varying conditions that we had held constant in our investigation. For example, we can model various traffic conditions by defining a different Time on Road Function.

Moreover, we have only begun to explore the potential of self-driving cars, in the context of the model. A random lane assignment with no lane changes will inevitably lead to imbalanced lanes. This strongly suggests that a lane-levelling algorithm can be a significant performance improvement over the no-lane-changes case.

Therefore, investigating how such an algorithm compares to an opportunistic lane changing strategy could be valuable. This is what we aim to pursue in the second part of this article. Stay tuned!

Source Code

The model is written in Node JS, available as open-source via the following repository:

https://github.com/psobocinski/traffic-modelling