Optimal trip assignment to depots in a large inter-city bus system

This paper examines the fleet-size problem in a multiple depot context for a large road transit system operating inter-city services. Each depot constructs its vehicle schedule for the trips assigned to it. The problem is to assign trips to depots such that vehicle scheduling if done optimally for each individual depot, would also result in being globally optimum for all depots put together. We develop a tree-search algorithm that systematically searches through potential trips for reassignments to achieve optimal decomposition while attempting to heuristically minimize deviations from initial (or preferred) trip assignments as required by the corporation. Test runs on real data indicate savings of around 4% in fleet-size from using the algorithm.