TY - CPAPER
AB - 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.
T1 - The School Bus Problem on Trees
DA - 2011
AU - Bock, Adrian Aloysius
AU - Grant, Elyot
AU - Könemann, Jochen
AU - Sanità, Laura
JF - Algorithms And Computation
SP - 10-19
VL - 7074
EP - 10-19
PB - Springer-Verlag Berlin
PP - Berlin
ID - 170056
KW - Network design
KW - Vehicle Routing
KW - Approximation algorithms
SN - 978-3-642-25590-8
SN - 0302-9743
UR - http://infoscience.epfl.ch/record/170056/files/sbp-isaac-final.pdf
ER -