Solving school bus routing problem with mixed-load allowance for multiple schools. (January 2021)

• Record Type: Journal Article
• Authors: Shang, Pan; Yang, Liya; Zeng, Ziling; (Carol) Tong, Lu
• Is Part Of: Computers & industrial engineering. Volume 151(2021)
• Publication Date: 2021-01
• Subjects: School bus routing -- Multi-commodity network flow -- Augmented Lagrangian relaxation -- Cyclic block coordinate descent method; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106916
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A time-discretized multi-commodity network flow model is proposed. Extended-state dimension is introduced to represent students commuting to different schools. A dynamic programming based cyclic block coordinate descent framework is proposed. Abstract: 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.