Traffic Light Phasing Optimization

[zh3zh3]

Homework Statement

(a) Draw a graph with the vertices corresponding to the traffic flows and the arcs corresponding to flows that can occur at the same time. (Called a compatibility graph)
(b) Show that finding subgraphs of the compatibility graph which are the biggest possible complete graphs, determines the optimum traffic light phasing needed and hence determine that phasing.

Homework Equations

The Attempt at a Solution

The problem is, I don't even understand what the question wants from me. I'm not asking for the solutions for both the question, (in fact there is a third part of the question which I am sure I can answer if someone could help me with question (a) and (b)) instead, I really need help on understanding the question itself and a rough idea on how to solve the problem.

By the way, can anyone tell me what's actually a 'compatibility graph'?

 

[CompuChip]

Heh it took me a few seconds to realize what was so odd about your diagram: everyone is on the "wrong" side of the road

Anyway, if I understood the question correctly, this is what they want you to do.
As the question states, just draw 7 vertices a through g. I suppose what they want you to do is: connect every vertex to all the other ones, that can move simultaneously without causing collisions. For example, if the lights for traffic flows e and f a green simultaneously, there is no problem. Allowing d and f to go through at the same time, however, would cause chaos. So you would connect f with e, but not with d. Then the exercise claims that any connected subgraph gives a configuration of traffic flows that can be allowed to move at the same time, without causing problems. Obviously, finding the largest of these, gives an optimum configuration then: as many different lights as possible are green at the same time. But b) asks you to prove that.

 

[Nick89]

I don't know but it seems to me the diagram can be interpreted in different ways... For example, if you look at a and b. Are they in the same line? What I mean is, is there one traffic light for a and b together, or do a and b use the same traffic light?

This is a problem because, if a has it's own traffic light, then a and f could go together without causing collisions. However, if a and b use the same light, then a and f could not go together because there's a chance the cars could go straight as well (b) colliding with f...

Or maybe I'm just making the question harder than it is lol...

 

[HallsofIvy]

I don't think the question has anything to do with a traffic light. a represents a car coming from the west, turning north while b represents a car coming from the east and continuing straight east. By the way, zh3zh3, There is a car turning left from every direction except north so there are 7 cars rather than 8. Was that intentional or an error?

To draw a compatability graph, draw 7 dots labled a, b, c, d, e, f, g . (Add an eighth point, h, if the lack of a car turning from north to east was an error.) Now look at each pair of turns. If two extended paths cross one another, those two turns are not "compatible" (cannot be made at the same time). If two paths do NOT cross then they are compatible. Connect two dots if and only if the two paths are do NOT cross. That is your "compatibility graph".

The "graph" is, of course, the dots connected by lines. The "compatibility" part is just because it shows which paths are compatible (defined in this problem as "can be made at the same time without the cars running into each other).

 

[Nick89]

Question b asks him to find the optimum traffic light phasing so that's why I started about traffic lights :)

It is pretty important for the optimum light phasing since if a and b can go together you cannot have a and f at the same time for example...

 

[HallsofIvy]

Question b asks him to find the optimum traffic light phasing so that's why I started about traffic lights :)

It is pretty important for the optimum light phasing since if a and b can go together you cannot have a and f at the same time for example...

You are right. I didn't even notice that!

 

[zh3zh3]

First of all, I need to apologize for not giving you enough information. My lecturer is a British, so the traffic flows forward on the left hand side.

Second, like what HallsofIvy said, there is a 'h', but that was meant to be the third part of the question:
(c) Suppose an extra lane of traffic, h, is added. This is a right turn next to flow c. Draw the resulting compatibility graph and propose an optimal traffic light phasing.

I couldn't actually get what Nick89 is trying to tell me though.

This is a problem because, if a has it's own traffic light, then a and f could go together without causing collisions.

I think we're assuming that there is only two lanes in a road, back and forth. So can you please explain to me, how, if a has its own traffic light, a and f could go together?

From what I've understood from CompuChip's explanation, I plotted 7 dots for a to g. For example, a and b, c, g, d, or e can occur at the same time (not all at once of course.), so I connect a to all these dots. So from here, I need to figure out if a flows, then how many traffic flows are possible to happen all at once. Then, I remove all these dots from my graph, doing the same thing again to get the maximum traffic flow.

Is this what I'm suppose to do?

 

[Nick89]

Sorry, my bad! I meant a and g ofcourse.

If a and b are in the same lane, and have one set of traffic lights, that means that for example if there are three cars in the 'a and b' lane, two cars could take route a and one car could take route b.

If there are only cars taking route a, then it is no problem for route g to be taken by other cars, they won't collide.

However, if there is a chance that cars will take route b instead of route a, then you cannot have route g at the same time because b and g will collide.

If a has it's own lane and it's own set of traffic lights, and b has it's own lane and set of traffic lights, then you can safely say that a and g can go together, since there is no chance cars will take route b (because that traffic light is still red).

If they are both in the same lane with the same traffic light, you cannot have a and g together; so it does make a big difference.

 

[zh3zh3]

Ah I see what you mean. What I did was compare two at the same time, not three or more. So, a and b are compatible, a and g are compatible. In the 2nd question, I'm required to find the optimum traffic light phasing.

The first step that I did was, I let a, b, d, and e move at the same time (they won't collide). Because they are all connected to each other and so, this means that all the traffic can occur at the same time. That's the maximum traffic flow I could find.

2nd, I removed a, b, d, and e from the graph. (They are the subgraphs of the compatibilty graph from 1st question) So this leaves me with c, f, and g. I chose f and g so that e could also flow at the same time. ( The priority is for those that have not moved )

Then the third step, c and f or c and a.

Summing it up:
1. a,b,d,e
2. f,g,e
3. c, f (or c, a)

Could anyone suggest any better answer?