3 February 2011 | Richard Eglese

Road congestion can make route planning a complicated issue. Professor Richard Eglese explains how schedules based on time-varying speeds can benefit drivers – and cut carbon.

Vehicle routing and scheduling has traditionally been worked out on the basis of road networks with average speeds for each road link. In practice, traffic flows are subject to congestion that leads to lower average speeds at particular times of the day or night, due to the regular fluctuations in volume of traffic. There is now much more traffic information and data available on past traffic patterns which makes it possible to plan vehicle journeys in a more informed and efficient way.

This approach will not be able to take account of unexpected events such as an accident, but regular congestion can be predicted. The resulting data can be used to create a road timetable that shows the shortest time and path between customers when the journey is started at different times.
Our research put the theory into practice, testing a routing and scheduling algorithm with real data from a vehicle fleet delivering electrical wholesale items in the south west, looking at total distances travelled, time required and carbon emissions. We looked at a nine-day period where vans made between 40 and 64 visits to customers each day.

Two road timetables were constructed using past data on speeds of vehicles on routes for each day’s set of customers, one (A) using uncongested speeds which did not vary by time of day and the other (B) taking into account the effects of congestion at different times of the day. The schedule prepared based on A was then tested under the actual time-varying speeds of B. As a result, over all the runs, the percentage of routes that went over time was 65 per cent and the total extra time required to finish those routes was an average of 57 minutes. In practice this may require the payment of overtime and could lead to problems if vehicles are delayed beyond the time when customers can accept delivery.

To overcome this problem, one strategy used by planners is to use slower constant speeds to make an allowance for congestion. This will not reflect the actual variations in speed at different times of the day, but might be expected to make sufficient allowance so actual route lengths do not exceed the 10 hours allowed. Even with this allowance, many of the routes planned still exceed the 600-minute time limit. The allowance is not enough to provide a set of routes that are likely to be satisfactory. It was not until speeds were reduced overall by 20 per cent that nearly all the routes were within the maximum.

In contrast with the previous results, using an algorithm based on time-varying speeds (C) produced results where all routes were completed within the 10-hour limit. These results demonstrate this is a more reliable basis for planning routes in terms of the time needed to complete each route, which also leads to the lowest distance travelled and lowest time required.

The study shows the effect that consideration of time-varying speeds can have on a real distribution operation. Being able to plan routes using traffic information that provides time-varying speeds for the roads in the network can improve conditions for drivers and also lead to some reduction in the levels of carbon emissions (in this case study, estimated at around 7 per cent).

Key points

• Past traffic patterns can predict regular congestion
• An algorithm based on time-varying speeds gives a more accurate timetable
• More accurate timetables benefit drivers

☛ Richard Eglese is professor of operational research in the Department of Management Science at Lancaster University Management School