SOLVING MULTI-SCHOOL BUS ROUTING AND SCHEDULING PROBLEM

Abstract

School bus routing and scheduling is of huge importance in school transportation system operations. It is usually treated as two separated problems and is solved sequentially. But it is shown that such separation will lead to a worse solution than solving them together with respect to the number of buses and travel time. The rationale behind it and the key point connecting routing and scheduling problem – trip compatibility – is thus deeply studied. A Mixed Integer Programming model is proposed along with a School Decomposition Algorithm. The model and algorithm are tested on eight sets of randomly-generated mid-size problems in comparison to the existing models. The results show that the proposed model and algorithm can find a better solution using up to 30% fewer buses than the best traditional models in a reasonable amount of time.