The School Bus Problem on Trees

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.


Publié dans:
Algorithms And Computation, 7074, 10-19
Présenté à:
22nd International Symposium on Algorithms and Computation (ISAAC 2011), Yokohama, Japan, December 5-8, 2011
Année
2011
Publisher:
Berlin, Springer-Verlag Berlin
ISSN:
0302-9743
ISBN:
978-3-642-25590-8
Mots-clefs:
Laboratoires:


Note: Le statut de ce fichier est: Seulement EPFL


 Notice créée le 2011-11-10, modifiée le 2019-08-12

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)