A Bounded Formulation for The School Bus Scheduling Problem
العنوان: | A Bounded Formulation for The School Bus Scheduling Problem |
---|---|
المؤلفون: | Liwei Zeng, Sunil Chopra, Karen Smilowitz |
المصدر: | Transportation Science. 56:1148-1164 |
بيانات النشر: | Institute for Operations Research and the Management Sciences (INFORMS), 2022. |
سنة النشر: | 2022 |
مصطلحات موضوعية: | FOS: Computer and information sciences, Computer Science::Hardware Architecture, Optimization and Control (math.OC), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Transportation, Mathematics - Optimization and Control, Civil and Structural Engineering |
الوصف: | 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. |
تدمد: | 1526-5447 0041-1655 |
URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2193c81645d00e695ac7dbd49eaf7a67 https://doi.org/10.1287/trsc.2022.1130 |
حقوق: | OPEN |
رقم الأكسشن: | edsair.doi.dedup.....2193c81645d00e695ac7dbd49eaf7a67 |
قاعدة البيانات: | OpenAIRE |
تدمد: | 15265447 00411655 |
---|