A Bounded Formulation for The School Bus Scheduling Problem

Liwei Zeng (), Sunil Chopra () and Karen Smilowitz ()
Additional contact information
Liwei Zeng: The Institute for Mathematics and Its Applications, University of Minnesota, Minneapolis, Minnesota 55455
Sunil Chopra: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208
Karen Smilowitz: Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208

Transportation Science, 2022, vol. 56, issue 5, 1148-1164

Abstract: This paper proposes a new formulation for the school bus scheduling problem (SBSP), which optimizes school start times and bus operation times to minimize transportation cost. The goal is to minimize the number of buses to serve all bus routes such that each route arrives in a time window before school starts. We show that introducing context-specific features, common in many school districts, can lead to a new time-indexed integer linear programming (ILP) formulation. Based on a strengthened version of the linear relaxation of the ILP, we develop a dependent randomized rounding algorithm that yields near-optimal solutions for large-scale problem instances. The efficient formulation and solution approach enable quick generation of multiple solutions to facilitate strategic planning, which we demonstrate with data from two public school districts in the United States. We also generalize our methodologies to solve a robust version of the SBSP.

Keywords: school bus scheduling problem; time-indexed formulation; randomized rounding algorithm (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1130 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:56:y:2022:i:5:p:1148-1164

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().