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.
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.
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.
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:"
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).
The ideal length of time spent on the road is zero. Therefore, we defined two metrics:
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:
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:
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)
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.
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 road increases in response to one additional car on the road.
Due to this being a computer model, we introduce the notion of a tick. This serves two main purposes:
The diagram above represents the general design of the simulation. The key concepts are:
Here is what happens on every tick:
Here are the input conditions that are common to all simulation runs (i.e. controlled variables):
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):
Through trial and error, we determined an appropriate set of conditions. The ideal parameters should result in:
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.
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.
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.
The results yield three key conclusions:
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).
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!
The model is written in Node JS, available as open source via the following repository: