Memetic Algorithm for the Heterogeneous Fleet School Bus Routing Problem

Abstract

The school bus routing problem is a hard, widely studied combinatorial optimization problem. However, little attention has been paid in the literature to the integration between the school bus routing problem and the design of the underlying network. This paper aims to present a new variant of the problem in which the following issues are taken into consideration: the determination of the set of stops to visit, the allocation of students to stops, the generation of routes, and the utilization of a heterogeneous fleet, with different fixed costs and capacities. It is presented as an integer programming formulation, a lower-bound technique, as well a greedy genetic and a memetic algorithm for the heterogenous fleet school bus routing problem (HFSBRP). The integer programming formulation has shown limited application to the solution of large size instances. Computational results on a set of 1 instances provide evidence of the quality of the solutions found by the memetic algorithm on large instances.