The School Bus Problem on Trees

The School Bus Problem on Trees

0.00 Avg rating0 Votes
Article ID: iaor20133664
Volume: 67
Issue: 1
Start Page Number: 49
End Page Number: 64
Publication Date: Sep 2013
Journal: Algorithmica
Authors: , , ,
Keywords: combinatorial optimization, graphs
Abstract:

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 factor approximation for the variant where we have a fixed number of buses to use, and the goal is to minimize the maximum regret.

Reviews

Required fields are marked *. Your email address will not be published.