Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem and freight transport scheduling problem. The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.