SCHOOL BUS ROUTING PROBLEM (LAGRANGEAN, HEURISTIC, NETWORK, RELAXATION)

In this paper a new heuristic algorithm is developed for large scale School Bus Routing Problems with a single school, M buses with equal capacity, and n pickup points. The distances between the pickup points are symmetrical, and it is assumed that all buses begin their tours at the school.;The new School Bus Routing Algorithm was tested against the savings and 3-optimal vehicle routing algorithms to measure its accuracy. In a majority of cases it produced substantially better results both in terms of lower mileage and fewer number of vehicles. Also several experiments were conducted to measure the computational efficiency of the new algorithm.;Given these assumptions, the new School Bus Routing Algorithm iteratively produces a wide range of solutions most of which are feasible. At each iteration, a Lagrangean relaxation which requires the computation of a degree constrained minimum spanning tree is utilized. Later this tree is used to generate individual tours which satisfy both the capacity and time constraints for the problem. A modified r-optimal Traveling Salesman Algorithm is then used to improve the total length of each tour. At the end of each iteration, the Lagrangean vector is updated by the subgradient optimization algorithm. After the final iteration, the most desirable solution can be chosen from several feasible solutions.