Text

A Bounded Formulation for The School Bus Scheduling Problem

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.

Ketersediaan

Informasi Detail

Judul Seri

TRANSPORTATION SCIENCE; Vol.56 No.5 September-October 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1148-1164

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

SCHOOL BUS SCHEDULING PROBLEM
TIME-INDEXED FORMULATION
RANDOMIZED ROUNDING ALGORITHM

Info Detail Spesifik

https://doi.org/10.1287/trsc.2022.1130

Pernyataan Tanggungjawab

Liwei Zeng, Sunil Chopra, Karen Smilowitz

Versi lain/terkait

Lampiran Berkas

Komentar