Take Action

Home | Faculty & Research Overview | Research

Research Details

A bounded formulation for the school bus scheduling problem, Transportation Science

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.

Type

Article

Author(s)

Sunil Chopra, Liwei Zeng, Karen Smilowitz

Date Published

2022

Citations

Chopra, Sunil, Liwei Zeng, and Karen Smilowitz. 2022. A bounded formulation for the school bus scheduling problem. Transportation Science. 56(5): 1148-1164.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more