Groupe d’études et de recherche en analyse des décisions

G-97-21

The Shortest Path Problem with Time Windows and Linear Waiting Costs

et

This paper considers the shortest path problem with waiting costs (SPWC) as an extension of the shortest path problem with time windows. The problem consists in finding the minimum cost path in a network, where cost and time are two independent quantities associated with a path. Path feasibility is constrained by time windows at each node and a linear cost penalty is imposed for each unit of time spent waiting along the path. Starting from the nonlinear integer programming formulation of Desaulniers, Lavigne and Soumis (1998), we propose two alternate formulations for which algorithms already exist. First, we show how to transform the SPWC into a shortest path problem with time windows and linear node costs (SPNC). Secondly, we prove that the SPWC can be formulated as a 2-resource generalized shortest path problem with resource constraints (SPRC). Given these two possible formulations of the SPWC, computational experiments are conducted on instances derived from two vehicle scheduling problems described in the literature. The results show that the SPRC implementation solves SPWC instances consistently faster (by a constant factor) than the SPNC implementation.

, 24 pages

Ce cahier a été révisé en août 1998