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

Question

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.

---

The task

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.

Answer 1

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.

Answer 2

Level 1

I found that the best settings are, somewhat surprisingly:

S = |, V = 0, H = 0, and A = 2. This means that in each cycle, the light changes to green for only an instant, letting up to one car through before turning back to yellow.

This yields a total time of:

139,723 seconds, or 1.606 seconds of waiting per car.

My explanation for why this is optimal:

Basically, because we want cars to wait at the lights as little as possible, we want the light cycle to be as short as possible. And in this case, because the east- and westbound cars arrive in multiples of 4 seconds, having a cycle that is 4 seconds long means that they never have to wait at all! The starting state is opposite (vertical), because the first east- and westbound cars arrive at 30 seconds, which is halfway through the seventh cycle that starts at 28 seconds.

---

Assuming that all lights have the exact same settings, and that only integer settings are allowed, then according to my simulation the best settings for Levels 2 and 3 are:

Level 2:

S = -, H = 2, V = 4, A = 2; 152,036 seconds total, 2.792 seconds of waiting per car

Level 3:

S = |, V = 4, H = 7, A = 2; 211,692 seconds total, 5.857 seconds of waiting per car

Answer 3

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$

Answer 4

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?