The school bus problem on trees

Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

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

Original languageEnglish
Title of host publicationAlgorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Pages10-19
Number of pages10
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan
Duration: 5 Dec 20118 Dec 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7074 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Symposium on Algorithms and Computation, ISAAC 2011
CountryJapan
CityYokohama
Period5/12/118/12/11

Fingerprint

Dive into the research topics of 'The school bus problem on trees'. Together they form a unique fingerprint.

Cite this