# Cross-road optimization - what is the proper way to solve this type of puzzle?

This puzzle has 3 levels of increasing complexity. Each "level" is separate and complete, so feel free to post partial solutions to the individual levels only.
I'm most interested in the principal questions asked in the text-boxes for level 3, but I think the 'simpler' levels are also worth considering.

You are in charge of defining traffic lights and traffic signs on crossroads in your district.

Your district is in a silent backwater area, so there is zero traffic, except during rush-hour when suddenly a lot of cars drive through.

You have been charged with the task to minimize the total time traffic spends in your district, so that exhaust fumes are reduced to a minimum. You do not care about individual drivers. From your perspective, it is okay to have one person wait for the whole hour at a traffic light while all other traffic passes by - as long as the total integrated time of all traffic is minimized.

As only rush-hour is important, this puzzle counts time in seconds starting with 0 at the beginning of the rush-hour. From time 0 onwards cars will continuously arrive at the border of your district and drive in a straight line until they leave the district at the other end. Every second a car is in your district, it adds +1 to the overall "fumes" regardless of its motion.

The overall "fumes" is the property which you want to minimize.

# The simplified traffic rules

For the purpose of this puzzle, traffic is described by the following, simplified rules:

• A car requires 30sec to pass through one section of your district. A section is the distance between border and crossing or between two crossings. The length of these sections is of no importance, and neither is traffic level on the road. The 'space' in front of a crossing is large enough to hold all traffic, so back-queuing does not affect anything except the 'crossing time' of the following crossing as specified below. (The 30sec will only add an offset to the fume-level, but it prevents 'speeding' through the whole puzzle on no-traffic.)

• Passing through a crossing does take 1 sec. (Only at green light of course!) There can only be 1 car in each direction in the crossing during this 1 sec.

• If a crossing is amber or red when a driver reaches it, he will stop and stand in queue. He will stand there until it is green.

• When a traffic light turns amber-to-green, starting takes each driver 1 sec per car in front to reach (and then pass) the crossing. So the first car goes immediately, the second needs 1 sec, the third 2 sec and so on. Any car which doesn't get across until the traffic light turns amber again, stops for the next green period in the new queuing position.

• No car can overtake another car, nor can two cars be in the same spot at the same time. (So in a queue, the front-car will delay all others.)

# Traffic light rules

Every crossing has a single, individual traffic light which will periodically go through the following cycles:

• state |: Green for North-South while red for East-West
• state X: Amber for all directions
• state -: Red for North-South while green for East-West
• state X: Amber for all directions

It is up to you to define:

• Variable S for starting state, which is the state the traffic light is in at begin of the rush-hour (0 sec). It can either be state | or state -.

• Variable V for vertical, which is the length of state | in seconds .

• Variable H for horizontal, which is the length of state - in seconds.

• Variable A for amber, which is the length of state X in seconds.
Note that there is only a single length for the amber phases.
Also, for security reasons, the amber phase must not be shorter than 2sec

# LEVEL 1 - district map and traffic Starting with rush-hour ( 0 sec ) and immediately stopping after rush-hour ( >3600 sec ) cars will enter at the district borders as follows:

N1: A car every 7 sec starting with 0. ( 0, 7, 14, 21, ... )
S1: A car every 9 sec starting with 0. ( 0, 9, 18, 27, ... )
W1: A car every 4 sec starting with 0. ( 0, 4, 8, 12, ... )
E1: A car every 8 sec starting with 0. ( 0, 8, 16, 24, ... )

What does the ideal (single) traffic-light setting look like?

# LEVEL 2 - district map and traffic Starting with rush-hour ( 0 sec ) and immediately stopping after rush-hour ( >3600 sec ) cars will enter at the district borders as follows:

N1: A car every 24 sec starting with 0. ( 0, 24, 48, ... )
S1: A car every 24 sec starting with 2. ( 2, 26, 50, ... )
N2: A car every 15 sec starting with 2. ( 2, 17, 32, ... )
S2: A car every 19 sec starting with 0. ( 0, 19, 38, ... )
N3: A car every 14 sec starting with 14. ( 14, 28, 42, ... )
S3: A car every 14 sec starting with 2. ( 2, 16, 26, ... )
W1: A car every 15 sec starting with 0. ( 0, 15, 30, ... )
E1: A car every 10 sec starting with 10. ( 10, 20, 30 ... )

What does the ideal traffic-light setting now look like?

# LEVEL 3 - district map and traffic Starting with rush-hour ( 0 sec ) and immediately stopping after rush-hour ( >3600 sec ) cars will enter at the district borders as follows:

N1: A car every 20 sec starting with 0. ( 0, 20, 40, ... )
S1: A car every 25 sec starting with 0. ( 0, 25, 50, ... )
N2: A car every 15 sec starting with 2. ( 2, 17, 32, ... )
S2: A car every 19 sec starting with 0. ( 0, 19, 38, ... )
N3: A car every 90 sec starting with 0. ( 0, 90, 180, ... )
S3: A car every 90 sec starting with 12. ( 12, 102, 192, ... )
W1: A car every 35 sec starting with 0. ( 0, 35, 70, ... )
E1: A car every 30 sec starting with 10. ( 10, 40, 70, ... )
W2: A car every 21 sec starting with 0. ( 0, 21, 42, 63, ... )
E2: A car every 21 sec starting with 0. ( 0, 21, 42, 63, ... )
W3: A car every 26 sec starting with 0. ( 0, 26, 52, ... )
E3: A car every 26 sec starting with 3. ( 3, 29, 55, ... )

And what is the solution now?

Can the above-posed puzzle still be solved analytically or does it require simulation, approximate models or other approaches?

Note: I do *not* know the answer to this puzzle.
In particular, this also means that some of the timings of cars might have been
very badly chosen (for level 2 & 3 at least).
The goal here (for me) is to **learn** how to make this into a better puzzle.
So if you discover a problem, please put it into the comments
and be aware that the puzzle might change due to edits.

• +1, but this question might feel more at home at Math SE as it requires a purely mathematical solution.
– dmg
Dec 8 '14 at 22:21
• I agree that this question would be a better fit on Mathematics.SE, but I believe it is also on topic here. Basically, do you think this question is entertaining and want to share it with others, or do you want a serious treatment of the problem and think that it might be dry for most other people to work on? Dec 9 '14 at 17:25
• Can you explain or give an example for the “Stopping takes 5 sec” provision? Suppose car P gets to an amber light at time t, and the light goes green at t+1. When does P leave the light? Or suppose car Q joins a queue at time t, and the car ahead of it goes thru the intersection at t+1. Does Q stop? When can Q go? Also, say the light cycles 10 times while car R is in a queue. Does R stop 10 times and get 50 seconds penalty? Does it go at the time its original car-count-delay times out? Does it get a new car-count-delay each time the light turns green? Dec 9 '14 at 23:46
• This seems like an extraordinarily complicated and arbitrary set of rules, and I kind of doubt (but it's just a gut feeling) that anytihng but the most trivial set-ups will be solvable without a computer. I would recommend removing the 30 second delay to cross reach "section" (as far as I can tell it contributes nothing to the problem, it just adds 60*(number of cars) to the overall fumes), and also removing the amber state of the lights, which just seem like an irritating distraction in an already very convoluted (and I don't mean that as a put-down) problem. Jan 11 '15 at 1:31
• As we evaluate each 'tick' can we assume a specific order of action? For example, a car is stopped at traffic lights which turn green at 7 seconds and the next car enters at 8 seconds. Does the car entering at 8 get delayed or not? If I have 3 traffic lights in a row, each of which has a single car stopped at them, and they all turn green at the same time, what happens? Nice puzzle, by the way. Jan 11 '15 at 11:44

For level 1:

Count total number of cars coming from each direction during the rush hour($3600/frequency + 1$), that gives:
N: 515
S: 401
W: 901
E: 451
Because | or - will let both N and S or W and E cars pass simultaneously, count total Vertical and Horizontal cars:
V: 916
H: 1352
And total cars: 2268
So now we can calculate ratio of V and H cars:
RV: $916/2268 * 100 = 40.39\%$
RH: $1352/2268 * 100 = 59.61\%$
So we have to let the light be | 40.39% of all time and - 59.61%. That sums up to about:
|: 1453.97 sec
-: 2146.03 sec
So the optimal strategy would be to first let the lights be - for 19 sec, then | for 13 sec and A for 2 sec in between(minimum time required, let's not make card wait longer and pollute air more). That sums up to $19+2+13+2=36$, which we can repeat 100 times

So the variable values for level 1 would be:

$S = -$
$V = 13$
$H = 19$
$A = 2$

• Is this really the optimum? Summing E and W cars if they are 'in sync'? I.e. In 8sec there will be 2w and 1e car going, but optimizing for the 2 W cars will allow the E car 'for free' +1 for picking up the challenge! Mar 6 '15 at 10:20
• Are spoilers necessary for this type of question? Nobody is going to accidentally scroll past your answer and absorb all of that information through the corner of their eye before they can help reading it. Mar 7 '15 at 1:07
• I don't think the MathJax is necessary either, it doesn't help the answer. Dec 18 '16 at 9:20

I tried to throw together a dynamical system to describe level two. This is my best attempt to set up an analytical solution; I don't have the time to try and model this right now, but maybe this will help point you in the right direction.

Also, in order to solve this discretely, using exactly the conditions you described, I'd recommend building a cellular automata model that would perfectly simulate your cross-roads. You could optimize that model's traffic light parameters with some error function (your pollution metric).

To do this continuously, you have to break your discretized conditions. The best way I could think of doing this is treating the system like a system of "buckets" that feed into and out of each other at certain rates. In this case, each of the vertical roads are their own buckets ($x_1, x_2, y_3$), and I break the horizontal road into 6 buckets (3 for eastward $y_i$, 3 for westward $z_i$). You'll notice that there are four sections of horizontal road, and in each case I treat the last leg of our "district" as "out of the bucket," in keeping with the metaphor. I do the same with the vertical sections, treating a car that passes the light as "exited the system." This is a simplification of mine, that I make chiefly because we are most interested in the ratio of the light switches. I don't know how to deal with the amber portion, to be honest. I'm kind of assuming that if we optimize for ratios of - vs. |, then the amber part is less crucial. If we wanted to be really thorough, we could penalize ratios that are close to 50:50, because those will have higher amounts of yellow-light time-wasting. I also do not account for the time-delay between a car entering and being able to leave. This is geared towards a steady-state solution, which will try to solve for optimal efficiency in the middle of rush hour.

To repeat, we have 9 total buckets, which cars will enter and leave at certain rates depending on the light ratios (| vs. -). The last leg of the road is considered out of the bucket already, because this problem will be solved in a steady-state manner for the ratio percentage, which really is not affected by cars on their way out.

$$\dot{x}_1 = \frac{1}{24} + \frac{1}{24} - 2*a_1, \hspace{1cm} x_1(0) = 2$$ $$\dot{x}_2 = \frac{1}{15} + \frac{1}{19} - 2*a_2, \hspace{1cm} x_2(0) = 2$$ $$\dot{x}_3 = \frac{1}{14} + \frac{1}{14} - 2*a_3, \hspace{1cm} x_3(0) = 16$$ , $$\dot{y}_1 = \frac{1}{15} -b_1, \hspace{1cm} y_1(0) = 0$$ $$\dot{y}_2 = b_1 -b_2, \hspace{1cm} y_2(0) = 0$$ $$\dot{y}_3 = b_2-b_3, \hspace{1cm} y_3(0) = 0$$ , $$\dot{z}_1 = \frac{1}{10} -b_3, \hspace{1cm} z_1(0) = 10$$ $$\dot{z}_2 = b_3 -b_2, \hspace{1cm} z_2(0) = 0$$ $$\dot{z}_3 = b_2-b_1, \hspace{1cm} z_3(0) = 0$$

These are time derivatives that describe the movements into and out of the buckets I mentioned before. The $a,b$ parameters are the ratios of light direction, so $a_i + b_i$ = 1. To once more clarify, $a_1$ will describe the portion of the time that 11 is open vertically (|). Therefore, $b_1$ will be the portion that 11 is horizontal (-), and so $a_1+b_1 = 1$ in our simplified example (ignoring amber).

To help clarify, for example, $\dot{y}_2$ describes the change in car population in the W1 between lights 11 and 12 ($y_2$). Cars enter $y_2$ from $y_1$ at a rate of 11 being open $b_1$ horizontally (-), and leave at the rate 12 is open ($b_2$) into $y_3$. The $z_i$'s are numbered from the eastward direction, which is why $z_1$ has cars entering at a rate of $\frac{1}{24}$ per second.

With the starting conditions and these equations, you should be able to figure out some optimums. I don't have time right now, but I would start with finding the steady state conditions (when $x_i = y_i = z_i = 0$) in terms of the $a_i,b_i$ parameters. Then I'd try to find the total bucket populations over your designated period as a function of those parameters $\left(\sum_i x_i + \sum_i y_i + \sum_i z_i \right)$. You could take the derivatives of those to find for which parameters the total car population is minimized. That should give you close to optimal light conditions in the middle of the hour, although not so well at the beginning.

Sorry I don't have the time to completely solve this, and also if I've made any theoretical/detail errors. I wrote this quickly, just wanted to throw in a continuous approach that would help out. I encourage anyone who sees an error in my approach/improvement to improve this. I'd also love to see the cellular automata model if anyone takes the time.

Lastly, this exact same approach would work for level 3, as long as my assumptions are ok for level 2. It would just take 36 equations instead of 9 (6 for each road, 3 for each direction).

EDIT

I fixed a couple detail errors.

Also, if the system is always flooded with cars, always vertical lights (|) minimizes the total number of cars (6 lanes flowing vs. 2). I'm starting to think you'll need Fourier analysis to get a more satisfying analytic answer; my general setup still works, you would just need to replace the rates above with delta/ square functions. Which you could do by hand, but switching between frequency and time domains is kind of a pain. The same thing goes for level 3; I think my continuous setup will give the predictable answer that isn't quite satisfying, and you'd need Fourier analysis to get frequencies for the lights firing on/off.

For level 1 the ratio of green time between N1S1/W1E1 is 4/7. The higher rate in each direction is the one that require to allow the cars to move through. If we could synchronize it with the fast cars (in each direction) coming into the crossing than we could refine it. Assuming a more general rule we need to allow 7 cars of the 4 seconds rate for every 4 cars of the 7 seconds rate, to cross. The slower rate will be automatically accommodated. Is this helping?