An ant colony meta-heuristic algorithm for school bus routing problem

This paper deals with the school bus routing problem (SBRP). This problem is a variant of the vehicle routing problem where three simultaneous decisions that have to be made: determining the set of stops to visit, for each student which stop he should walk to and the latter case occurs when determining the routes visited with the chosen stops, so that the total traveled distance is minimized. In the standard VRP all stops to visit are given, but in school bus routing problem, is assumed that a set of potential stops is given, as well as a set of students that can walk to one or more of these potential stops. The school buses used to pick up the students and transport them to school have a finite capacity. Ant Colony Optimization (ACO) is a meta-heuristic for combinatorial optimization problems. In this paper, artificial ant colony is developed. its successful application to the SBRP and finds optimal or close-to- optimal solutions of large instances of the SBRP in very limited computing times is shown.