Bock, Adrian Aloysius
Grant, Elyot
Könemann, Jochen
Sanità, Laura
The School Bus Problem on Trees
Algorithms And Computation
Algorithms And Computation
Algorithms And Computation
Algorithms And Computation
10
7074
Network design
Vehicle Routing
Approximation algorithms
2011
2011
The School Bus Problem is an NP-hard vehicle routing problem in which the goal is to route buses that transport children to a school such that for each child, the distance travelled on the bus does not exceed the shortest distance from the child's home to the school by more than a given regret threshold. Subject to this constraint and bus capacity limit, the goal is to minimize the number of buses required. In this paper, we give a polynomial time 4-approximation algorithm when the children and school are located at vertices of a fixed tree. As a byproduct of our analysis, we show that the integrality gap of the natural set-cover formulation for this problem is also bounded by 4. We also present a constant approximation for the variant where we have a fixed number of buses to use, and the goal is to minimize the maximum regret.
Springer-Verlag Berlin
0302-9743
978-3-642-25590-8
Algorithms And Computation
Conference Papers
000308788400003