# Calculate travel time on road map with semaphores

I have a road map with intersections. At intersections there are semaphores. For each semaphore I generate a red light time and green light time which are represented with syntax [R:T1, G:T2], for example:

``````    119                   185                 250
A ------- B: [R:6, G:4] ------ C: [R:5, G:5] ------ D
``````

I want to calculate a car travel time from A - D. Now I do this with this pseudo code:

``````function get_travel_time(semaphores_configuration)
{
time = 0;
for( i=1; i<path.length;i++)
{
prev_node = path[i-1];
next_node = path[i]);
cost = cost_between(prev_node, next_node)
time += (cost/movement_speed) // movement_speed = 50px per second
light_times = get_light_times(path[i], semaphore_configurations)
lights_cycle = get_lights_cycle(light_times) // Eg: [R,R,R,G,G,G,G], where [R:3, G:4]
lights_sum = light_times.green_time+light_times.red_light; // Lights cycle time
light = lights_cycle[cost%lights_sum];

if( light == "R" )
{
time += light_times.red_light;
}
}
return time;
}
``````

So for distance 119 between A and B travel time is, 119/50 = 2.38s ( exactly mesaured time is between 2.5s and 2.6s), then we add time if we came at a red light when at B. If we came at a red light is calculated with lines:

``````lights_cycle = get_lights_cycle(light_times) // Eg: [R,R,R,G,G,G,G], where [R:3, G:4]
lights_sum = light_times.green_time+light_times.red_light
light = lights_cycle[cost%lights_sum];
if( light == "R" )
{
time += light_times.red_light;
}
``````

This pseudo code doesn't calculate exactly the same times as they are mesaured, but the calculations are very close to them.

Any idea how I would calculate this?

-

You have three measurements here:

• Distance between lights (meters)
• Time between red and green (seconds)
• Speed of car (meters per second)

However, it looks like this problem is a lot more complex than what it appears to be at face value.

• Cars don't move at linear velocity. Even in a simplified model, they should speed up and slow down.
• Lights turn off and on at regular intervals. If a car travels faster or slower it will be stuck longer or shorter at red lights.

So what I would do in this case is to just pick a value for the car speed and calculate the outcome. Assume all lights start at the red position, the distances between the lights is in meters and that the car travels at a constant 10/ms (36 km/h or 22.3 mph).

The car will reach the first intersection in 119 / 10 = 11.9 seconds. 11.9 - 6 (seconds of red) = 5.9. 5.9 - 4 (seconds of green) = 1.9. The car will have to wait for (6 - 1.9) = 4.1 seconds. Our total so far is 11.9 + 4.1 = 16 seconds.

The next intersection is reached in 185 / 10 = 18.5 seconds. Our running total is 16 + 18.5 = 34.5 seconds. 34.5 - 5 - 5 - 5 - 5 - 5 - 5 = 4.5 seconds into the red state of the light, so the car has to wait 5.0 - 4.5 seconds. Our running total is now 35.0 seconds.

Finally, the last stretch of road is done in 185 / 10 = 18.5 seconds, which makes our total 53 seconds.

So, how do we put this into a formula? It seems to me that the best way to do this is to keep a running total of the car's time traveled. For every intersection, calculate the time the car will take to reach it (perhaps recursively up a tree?), modulo with the total light time, modulo with the red light time and add that to the running total. Do this for every light and you should get an accurate estimated arrival time. But only for this simple model.

EDIT:

Your car has a formula to calculate a position at time `t`. We can use this to see where the car will be in the future. We know that the distance between `A` and `B` is 119 meters, and we know that the car travels at 10 meters per second. In a formula:

``````next_intersection = start + speed * time;
``````

So if we solve that for time:

``````start + speed * time = next_intersection;
speed * time = next_intersection - start;
time = (next_intersection - start) / speed;
``````

So if we plug in our values:

``````time = (119 - 0) / 10;
time = 11.9 seconds
``````

However, the lights continue to blink on and off while the car is traveling. So how do we know whether the light is green or red when the car arrives? We divide by the interval, keep what's left over and see if it's greater than the red time:

``````light_time = (time % light_interval);
light_is_red = (light_time < light_interval_red) ? true : false;
``````

So if the light is red, we have to add a waiting time.

``````if (light_is_red)
{
time += (light_time - light_interval_red);
}
``````

And then we can travel to the next light, which is at `C`.

What you need most of all is a way to calculate the car's position at a time in the future, without animating it. Determine how you are moving the car and see if you can make a formula out of that that can calculate the car's position at any time in the future or past.

-
What if we arrive at intersection when there is a green light? Then car doesn't have to wait at that intersection. – Ivansek Jul 2 '12 at 7:13
That is correct, but you'll have to deal with that yourself. If the car arrives at a time when the light is green, no waiting time should be added. – knight666 Jul 2 '12 at 7:16
That's exactly what I want to calculate. Will at the intersection be a green light or red light when I arrive at that intersection without actually animating and measuring time. If i correctly understand your answer, you just provide me a formula for car travel time from A to D if car always have to wait at a red light? – Ivansek Jul 2 '12 at 7:21
I have expanded my answer to hopefully clear things up. – knight666 Jul 2 '12 at 7:40