Transporting students to and from schools is a complex problem for public and private schools. In most cases in the world, schools provide dedicated school buses for their own students. In this paper, we address a mixed-load school bus routing problem (MLSBRP), which school bus may carry students from more than one school at the same time. Reasonable planning of school bus route may reduce required number of school buses, the number of stops to pick up and drop off students, total mileage of all buses and operating cost of the system. The objective of our problem is to minimize the total cost of school bus system. Pick-up time windows, earliest time when school buses can pick up students at stops, and maximum duration of the trip are considered to meet the real-world instances. First, a mixed integer linear programming formulation is provided and solved by commercial operations research software CPLEX. We also present a case study for three schools in Suzhou, Jiangsu, China to show that mixed-load can effectively reduce the cost of the school bus system. For large-sized instances which cannot be solved by CPLEX in a reasonable amount of time, we develop a simulated annealing-based heuristic method. Results of our computational investigation reveal the efficacy in obtaining near-optimal solutions of our method.

CICTP