On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints

Abstract

The elementary shortest-path problem with time-windows and capac-ity constraints is a problem used for solving vehicle-routing and crew-scheduling applications. It occurs as a sub-problem used to implicitly generate the set of all feasible routes and schedules in the column-generation formulation of the vehicle routing problem with time windows and its variations. In the problem there is a directed graph with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements of a resource with a finite capacity. A minimum cost source–destination directed path is sought such that the total consumption of the resource does not exceed the capacity. The problem ins NP-hard in the strong sense. We review integer-linear formulation to the problem and compare them in order to study their computational efficiency.