期刊
COMPUTERS & INDUSTRIAL ENGINEERING
卷 151, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2020.106916
关键词
School bus routing; Multi-commodity network flow; Augmented Lagrangian relaxation; Cyclic block coordinate descent method
资金
- National Nature Science Foundation of China [71473259, 71734004, 72001020]
- Beijing Municipal Natural Science Foundation [L181007]
- China Postdoctoral Science Foundation [2020M670128]
This study examines practical requirements for the school bus routing problem and proposes a solution based on a time-discretized multi-commodity network flow model. By introducing an augmented Lagrangian relaxation approach, the optimization of student-bus assignment and bus routing is facilitated through linear multi-commodity network flow sub-problems.
The school bus routing problem (SBRP) is a challenging real-world problem that affects many citizens on a daily basis. This study considers several important classes of practical requirements for SBRP that include multiple schools, mixed-loads for students boarding the same bus but from different stops and commuting to different schools, heterogeneous fleets, various student-pickup time windows, and school-bell-ring constraints. Accordingly, a time-discretized multi-commodity network flow model is proposed based on a student-loading state-oriented space-time network. To enable optimization of both the student-bus assignment and bus routing, we introduce an extended-state dimension to represent the number of students commuting to different schools by buses. By implementing an augmented Lagrangian relaxation approach, the primal SBRP is reformulated as a quadratic 0-1 programming model with linear flow balance constraints. Furthermore, the augmented Lagrangian model can be decomposed and linearized as a series of linear multi-commodity network flow sub-problems that can be successively solved using dynamic programming algorithms in a cyclic block coordinate descent framework. The proposed model and approach to the solution are implemented on a nine-node test network, a Sioux Falls network under different scenarios, and a large-scale Chicago sketch network.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据