TY - JOUR
T1 - A Bounded Formulation for The School Bus Scheduling Problem
AU - Zeng, Liwei
AU - Chopra, Sunil
AU - Smilowitz, Karen
N1 - Funding Information:
Funding: This work was supported by Division of Civil, Mechanical and Manufacturing Innovation, National Science Foundation [Grant CMMI-1727744]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/trsc.2022.1130.
Publisher Copyright:
Copyright: © 2022 INFORMS.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - randomized rounding algorithm
KW - school bus scheduling problem
KW - time-indexed formulation
UR - http://www.scopus.com/inward/record.url?scp=85140033500&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85140033500&partnerID=8YFLogxK
U2 - 10.1287/trsc.2022.1130
DO - 10.1287/trsc.2022.1130
M3 - Article
AN - SCOPUS:85140033500
SN - 0041-1655
VL - 56
SP - 1148
EP - 1164
JO - Transportation Science
JF - Transportation Science
IS - 5
ER -