Solving a Bus Routing Problem Arising in Doha

Abstract

The generic variant of the school bus routing problem requires finding a set of routes that cover a predefined set of student pickup locations in order to minimize travel time while satisfying various constraints. In this paper, we study a new variant of the problem that was motivated by a real-world application in Doha, Qatar. In this variant, two objectives are considered: minimizing the number of buses and achieving a goal of not exceeding a predefined maximum travel time. We propose a compact mixed-integer programming problem and present how it can be solved heuristically to derive high-quality solutions for large-size instances.