Summary
On School Bus Routing and Scheduling
Michela Spada EPFL-SB-IMA
The purpose of school bus services is to carry children from their
homes to school and back. Scheduling and routing such services
manually can be a long and tedious task, as it gives rise to complex
combinatorial problems. To tackle those, we propose various heuristics
in order to build good quality schedules of school bus routes for small
and large size problems.
The school bus routing and scheduling problem is modeled by introducing a performance measure corresponding to the service level
provided to the children. This quality measure focusing on the
children differs from previous approaches to the subject, in which the
solution evaluation generally depends on the number of buses used or
the lengths of the routes of the vehicles. In addition, our schedules
allow the vehicles simultaneously to carry children going to different
schools, which to our knowledge has only been treated once in the
literature.
Two problems are considered: one consisting in maximizing the average
quality of children service level and another to maximize the quality
of the worst service level provided to a child. These problems can be
formulated as binary integer programs, but their size is too large to
consider an exact resolution with current software and computers. A
constructive method is proposed to obtain a feasible schedule which is
optimized thereafter with various heuristics: simulated annealing, tabu
search and variable neighborhood search. Let us note that, during
optimization, the use of schedules violating the vehicle capacity is
authorized. The heuristics employed, in their variant exploring
infeasible solution set, are more effective than those that are
confined to the feasible solution set. These methods also yield
much higher quality schedules for real data sets than those actually
used by the schools in question.
An ideal schedule should allow to simultaneously optimize both objective functions mentioned above. In order to approach such a
solution, a two phase method is proposed. The first phase consists in
maximizing the minimum service level and the second in maximizing the
average service level without reducing the minimum obtained during the
first phase.
We also developed an extension of our methods based on decomposition
adapted to large scale problems. The proposed decomposition approach
allows to considerably reduce computing time without giving up quality
and is essential in order to solve problems with a large number of
children.
Let us finally note that a graphical user interface was developed,
allowing to visualize, analyze and modify schedules generated by the
heuristics. It is thus possible to integrate additional constraints
that have not been modeled, or to adapt a solution in case of a small
modification to the problem data.
For more information, please contact
michela.spada@epfl.ch
[Top]
RETURN to previous
page.