CONTINUOUS-TIME SHORTEST-PATH PROBLEMS AND LINEAR-PROGRAMMING

Shortest path problems are considered for a graph in which edge distances can vary with time, each edge has a transit time, and parking (with a corresponding penalty) is allowed at the vertices. The problem is formulated an a continuous-time linear program, and a dual problem is derived for which the absence of a duality gap is proved. The existence of an extreme-point solution to the continuous-time linear program is also demonstrated, and a correspondence is derived extreme points and continuous-time shortest paths. Strong duality is then derived in the case where the edge distances satisfy a Lipschitz condition.