Saturday, September 13, 2008

Optimal Lane Merging - Part 1

I spend a lot of time thinking about traffic; I spend a lot of time driving. Frequently, on multi-lane highway the following situation occurs. There are three driving lanes and the left lane is closed ahead. Cars in the left lane stay in the left lane until the last minue, then attempt to merge right. A driver in the middle lane then uses their horn, and may flip off the car in the left lane.

Why is the middle lane driver upset? They expect the left lane traffic to merge behind them. Often when you talk to a middle lane driver they say something like "Left lane people knew the road was closed up here, they should have merged "back there". Where "back there" is inevitably anyplace *behind* the middle lane driver. There is no specific place in mind (one mile back? 1/2 a mile back?), no just behind me.

Unfortunatly, when this happens, the optomal merger is infact right where the left lane ends, and the question should be, why didn't everyone stay in their lane until one lane ended? If they did the traffic would flow as smooth as possible. This is the optomal merger point.

In this blog I would like to try to prove that.

First, lets define some things:

An optimal merge occurs when all cars make it through the choke point in their minimal time. Obviously, if everyone in the left lane just parked their cars, the people in the middle lane could just go at normal highway speeds and they would be happy. The people in the left lane would be disadvantaged. That's not optimal. In an optimal merge the delay is evenly distributed to every vehicle. Evenly is the key, some vehicles can't get 2 units of delay while some get 1 or 0 units of delay.

To start, we need to define what decides how fast cars go on a highway. This is key.

Average Speed on a highway can be defined like this:

V = min{ Ds, L } where
  • V = Average Speed of cars on highway. This is the actual average speed of cars on the highway.
  • L = Law imposed speed. This is the speed a car would go if there were no other cars in its way. Its a function of the speed limit, weather, and other social conditions (how likely people are to get a ticket etc...) Typicaly, lets say its 75 for a 65mph zone.
  • Ds = Density imposed speed.

Lets also make some assumptions:
  1. Traffic is evenly distributed.
  2. These formulas are really geared towards a two lane highway, as opposed to a three, but with more math they apply to three as well.
  3. V[Left Lane] = V[Right lane] = V[all lanes]

Ds is important to understand. Ds is a function of the density [Ds(density) ] of the vehicles on the road.

So, lets think about the Average Speed formula above. When there is just one car on the road, it goes L, Traffic will continue to move at L speed until cars feel they need to slow down because they might hit someone in front of them. Then Ds takes over the equation.

Given this understanding of average speed, if Ds is higher than L, and more formally Ds(2 * lane_density) > L then there is no optimal place to merge lanes. Cars from the left lane can enter the middle lane and not effect road speed.

However, once Ds(2 * lane_density) < L, the optimal merger occurs at the end of the left lane.

This still needs some explanation, but from now on we will assume we are in the state where Ds(2 * lane_density) < L. I should also say I am assuming at some point before the merge all lanes have the same density, called lane_density.

So, the optimal merge occures when each left lane car merges between a right lane car. Such that through the choke point your procession of cars goes L M L M L M. Where L means a car formerly from the left lane, and M means a car formerly from the middle lane. Understand that any other ordering is not optimal.

For example, L M L M L L M L makes the last cars velocity through the system slightly greater than the seconds. Therefore we violate our rule for optomal velocity from above.

Simmilary, L M L M M L M violates our rule for optomal velocity. However, note that L L M M L L M M etc does not. If the cars through the choak point are evenly mixed then Optimal flow is acheived. There are several more complex ways to acheive an optimal mix, but I will leave that for your imagination.

Now, to get that mix you either need a traffic cop, or you need everyone to behave in a predictable way. Note that its only possible to behave in a predictable way if everyone can see what everyone else is doing. That only occures at the end of the lane. While it could occure before the end of the lane, all vehicles involved would need to agree that it must occure at exactly one point. Of course, that one point would then behave as the end of the lane. There would be no cars beyond that point, the lane would be de-facto closed, but unused by highway crews. Though the traffic flow would be optimal, the actual choice of the point would be ephemeral and may travel. Why not make it a little bit further back, how about 2 miles, how about 10? The only reasonable point is right when the lane ends.

This is where the argument becomes complex, and this is what I will finish later...

To Be continued.


A Fuss said...

Welcome back! Diahretic Expostulation readers have missed you (no offense to Net Ghost, whose postings have been truly fantastic). The blog world has truly missed mathematical (Physics?) equations.

Net Ghost said...

I think drivers in the left lane should switch lanes when they are given notice that their lane will end.

Also, the reason people stay in the left lane until the very last minute is because the density in that lane is LESS (because some people are polite and actually move over when they're supposed to). So it's not a matter of being efficient. The people in the left lane are trying to beat out all the people in the other lanes who have patiently waited their turn to get ahead.

The next question, of course, is if the left lane is less dense than the center lane, then shouldn't people from the middle lane cut into the left lane, and then back into the middle lane, for prime efficiency? But then what's the use of the sign warning people that the lane ends? Why have any warning sign at all?

sqroot(JK^2) said...

Net Ghost,

Right, People will try to merge into the less dense lane. The less dense lane always goes faster. However, the left lane is only the less dense lane because people started to move out of i at some point well before the end. This causes the right lane to become more dense and slow down. If you can get everyone from the left lane to move to the right lane at the exact same point, you would have an optimal merge. However, any point but the last point is an unstable point. All merge points that aren't at the end of the closed lane have a tendancy to shift and therefore create uneven density. When there is uneven density, you can't have an optimal merge.