  School bus planning problem (SBPP) has drawn much research attention due to
the huge costs of school transportation. In the literature, the SBPP is usually
decomposed into the routing and scheduling subproblems due to its complexity.
Because of the nature of the decomposition, even if all the subproblems are
solved to optimality, the final solution may not be as good as the solution
from the integrated model. In this paper, we present a new approach that
incorporates the scheduling information (namely the trip compatibility) into
the routing stage such that the interrelationship between the subproblems is
still considered even in the decomposed problems. A novel two-step heuristic
adopting the trip compatibility idea is presented to solve the school bus
routing problem. The first step finds an initial solution using an iterative
minimum cost matching-based insertion heuristic. Then, the initial trips are
improved using a Simulated Annealing and Tabu Search hybrid method. Experiments
were conducted on randomly generated problems and benchmark problems in the
literature. The result shows that our two-step heuristic improves existing
solutions up to 25% on the benchmark problems.
