School-bus routing for program scheduling

The program scheduling problem involves a set of student pick-ups and drop-offs for which school-to-school routes must be developed. Each pick-up or drop-off has a scheduled time of occurrence, and these activities must be connected so as to minimize the number of deadhead or empty bus kilometers. We review the literature on routing with time windows and school-bus routing in general. We then formulate a mathematical programming model which has the structure of an assignment problem plus side constraints for time-feasibility and number of buses. Additional 0–1 variables are introduced which indicate those particular tasks that are connected to the depot, and which permit use of a pure assignment formulation and solution. Several actual problems from the Durham Board of Education are solved. Results, improvements and sensitivity questions are discussed, and suggestions are made for further research.