# A Bounded Formulation for The School Bus Scheduling Problem

**Authors:** Liwei Zeng, Sunil Chopra, Karen Smilowitz  
**arXiv:** [1803.09040](https://arxiv.org/abs/1803.09040)  
**Date:** 2018-03-24  
**Summary page:** https://www.summarizepaper.com/en/paper/1803.09040v2/

## Key points

- The School Bus Scheduling Problem (SBSP) involves minimizing transportation costs while ensuring all bus routes arrive at school within a specified time window.
- Liwei Zeng, Sunil Chopra, and Karen Smilowitz propose a new formulation for the SBSP that optimizes both school start times and bus operation times to achieve these goals.
- They present a new time-indexed integer linear programming (ILP) formulation and develop a dependent randomized rounding algorithm based on a strengthened version of the ILP's linear relaxation.
- This algorithm yields near-optimal solutions for large-scale problem instances.
- The goal is to minimize the number of buses required while ensuring each route arrives at school before classes begin, thus reducing transportation costs significantly.
- The authors also generalize their methodologies to solve a robust version of the SBSP which takes into account uncertainties in travel times and other factors that can impact scheduling decisions.
- Overall, this paper presents an innovative approach to solving an important real-world optimization problem with significant practical applications in transportation planning and logistics management.

## Summary

The School Bus Scheduling Problem (SBSP) is a complex optimization challenge that involves minimizing transportation costs while ensuring all bus routes arrive at school within a specified time window. Liwei Zeng, Sunil Chopra, and Karen Smilowitz propose a new formulation for the SBSP that optimizes both school start times and bus operation times to achieve these goals. To solve this problem, they present a new time-indexed integer linear programming (ILP) formulation and develop a dependent randomized rounding algorithm based on a strengthened version of the ILP's linear relaxation. This algorithm yields near-optimal solutions for large-scale problem instances. The goal of the proposed approach is to minimize the number of buses required while ensuring each route arrives at school before classes begin. By optimizing both school start times and bus operation times, the authors are able to reduce transportation costs significantly. They also generalize their methodologies to solve a robust version of the SBSP which takes into account uncertainties in travel times and other factors that can impact scheduling decisions. Overall, this paper presents an innovative approach to solving an important real-world optimization problem with significant practical applications in transportation planning and logistics management.