Wednesday, March 18, 2009

New Mathematical System Helps To Cut Bus Journey Times

SOURCE

ScienceDaily (Mar. 17, 2009) — A research team from the University of Burgos (UBU) has designed a system to reduce the time spent waiting at bus stops in the city, as well as the length of bus journeys. The method, which could be applied to other locations, is based on a mathematical strategy known as “taboo search.”
The UBU’s Research Group on Metaheuristic Techniques, working with Mexican researchers, has come up with a system to reduce the time spent waiting at bus stops in Burgos from 20 to 17 minutes, and to cut average bus journey times from 16 to 13.5 minutes.
“This translates into a 13% performance improvement of this urban transport service,” Joaquín A. Pacheco, the research group’s coordinator and director of the UBU’s Applied Economics Department, tells SINC.
“When we face a problem of this kind, we can use an exact method, which gives us an optimal solution but takes a long time to calculate – or we can use an approximate or heuristic technique, which provides a good solution with less calculation time,” says Pacheco, who chose the second method.
Heuristic algorithms are more effective in certain situations, such as when the data for a problem to be solved are imprecise, or when fast and adaptable solutions are needed. The researchers used the “taboo search” method from the most highly perfected heuristic techniques, known as metaheuristics. This strategy uses learning methods, and classifies certain options as “forbidden” or “taboo”, to avoid developing solutions that have already been previously created.
“For example, when searching for solutions, if a bus has just left a particular stop, this stop is then marked as ‘taboo’ and it cannot be included as part of that route again for a certain number of iterations (repetitions),” explains Pacheco.
The results of the “taboo search” made it possible to design slight modifications to the current lines operating in the city, for example by making a bus route run along one street instead of another, or by eliminating some twists and turns, as well as to redistribute the bus fleet, especially in the eastern part of the city. These improvements will allow urban transport users in Burgos to save time during their trips.
In order to carry out this study, the researchers maintained a set number of bus routes, as well as their starting and finishing points. The work was commissioned by Burgos City Council, which requested that no abrupt changes be made to the service. The city has 382 bus stops served by 24 routes operating on working days.
This method can also be used in other towns, according to its developers. The metaheuristic techniques are already being applied in Castilla-La Mancha and the Balearic Islands in order to reduce the cost of school transport services, and the amount of time students have to wait at bus stops.
Journal reference:
Joaquín Pacheco, Ada Álvarez, Silvia Casado, José Luis González-Velarde. A tabu search approach to an urban transport problem in northern Spain. Computers & Operations Research, 2009; 36 (3): 967 DOI: 10.1016/j.cor.2007.12.002
Adapted from materials provided by Plataforma SINC, via AlphaGalileo.