Time‐varying shortest path problems with constraints

Journal Article


We study a new version of the shortest path problem. Let G = (V, E) be a directed graph. Each are e ∈ E has two numbers attached to it: a transit time b(e, u) and a cost c(e, u), which are functions of the departure time u at the beginning vertex of the arc. Moreover, postponement of departure (i.e., waiting) at a vertex may be allowed. The problem is to find the shortest path, i.e., the path with the least possible cost, subject to the constraint that the total traverse time is at most some number T. Three variants of the problem are examined. In the first one, we assume arbitrary waiting times, where waiting at a vertex without any restriction is allowed. In the second variant, we assume zero waiting times, namely, waiting at any vertex is strictly prohibited. Finally, we consider the general case whre there is a vertex‐dependent upper bound on the waiting time at each vertex. Several algorithms with pseudopolynomial time complexity are proposed to optimally solve the problems. First, we assume that all transit times b(e, u) are positive integers. In the last section, we show how to include zero transit times. © 1997 John Wiley & Sons, Inc. Networks 29: 141–149, 1997

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.