A NEW FORMULATION TO THE SHORTEST PATH PROBLEM WITH TIME WINDOWS AND CAPACITY CONSTRAINTS

DONDO, RODOLFO

LATIN AMERICAN APPLIED RESEARCH

PLAPIQUI(UNS-CONICET)

Lugar: Bahia Blanca; Año: 2012 vol. 42 p. 252 - 265

0327-0793

The Shortest-path problem with time-windows and capacity constraints (SPPTWCC) is a problem used for solving vehicle-routing and crew-scheduling applications. The SPPTWCC 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 (VRPTW) and its variations. The problem is NP-hard in the strong sense. Classical solution approaches are based on a non-elementary shortest-path problem with resource constraints using dynamic-programming labeling algorithms. In this way, numerous label-setting algorithms have been developed. Contrarily to this approach and with the aim to obtain elemental and optimal solutions, we propose a new mixed integer-linear formulation to the SPPTWCC. Some valid inequalities that can be used to strengthen the linear relaxation of the SPPTWCC are also proposed. Numerical experiments on some VRPTW instances taken from Solomon´s benchmark problems show that (near) optimal solutions are easily obtained in spite of the considerable problem size. Also the number of generated columns is kept at a very low level