A set partitioning reformulation of a school bus scheduling problem

A set partitioning reformulation of a school bus scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20116941
Volume: 14
Issue: 4
Start Page Number: 307
End Page Number: 318
Publication Date: Aug 2011
Journal: Journal of Scheduling
Authors:
Keywords: programming: integer, heuristics
Abstract:

We present an integer programming model for the integrated optimization of bus schedules and school starting times, which is a single‐depot vehicle scheduling problem with additional coupling constraints among the time windows. For instances with wide time windows the linear relaxation is weak and feasible solutions found by an ILP solver are of poor quality. We apply a set partitioning relaxation to compute better lower bounds and, in combination with a primal construction heuristic, also better primal feasible solutions. Integer programs with at most two non‐zero coefficient per constraint play a prominent role in our approach. Computational results for several random and a real‐world instance are given and compared with results from a standard branch‐and‐cut approach.

Reviews

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