The Vehicle Scheduling Problem: Models, Complexity and Algorithms

Abstract

The Vehicle Scheduling Problem with time windows (VSP) is concerned with finding a minimum-cost set of vehicle schedules which processes a set of jobs with specified earliest and latest start times, durations and trip times between jobs. This problem is well known to be very difficult to solve. A proof that the VSP decision problem is NP-complete is developed in order to gain a deeper understanding of the reasons for the problem's complexity. The ideas are extended to measuring the difficulty of integer instances of the problem. A graph-theoretic representation of the VSP is combined with ideas related to problem difficulty and this leads to theorems on reducing the difficulty of problem instances. The techniques are aimed at reducing the number and sizes of the time windows, therefore greatly reducing the size of the feasible region. The window reduction methods are shown to be both theoretically and empirically valid.

The VSP is formulated as a constrained assignment problem, and the start times of jobs are replaced by time window variables. This new formulation leads to theorems on bounds for the VSP, and to a class of approximation algorithms with strong convergence properties. The algorithms prove to be effective in solving both easy and hard problems. The ideas are extended to produce exact algorithms for the VSP.

Extensions of the VSP model to include earliness, waiting time and return trips are formulated. The optimal solutions to some special cases of these problems are developed. The approximation algorithms for the VSP are easily adapted to these extended models.

An interactive system is developed to build and test new algorithms. This facility allows fundamental algorithms to be combined to produce new results. The user interfaces allow multiple solution views and manipulations to gain insight into the solution structures.