This paper considers the shortest path problem with waiting costs (SPWC) as
an extension to the shortest path problem with time windows. The problem c
onsists of 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 impos
ed for each unit of time spent waiting along the path. Starting from a Know
n, nonlinear, integer programming formulation, we propose two alternative f
ormulations for which algorithms already exist. First, we indicate how to t
ransform the SPWC into a shortest path problem with time windows and linear
node costs. Second, we prove that the SPWC can also be formulated as a two
-resource generalized shortest path problem with resource constraints. Comp
utational results used to compare these alternative formulations are presen
ted.