Document [original]

Continuous-time Dynamic Shortest Paths

with Negative Transit Times

Ronald Koch ·Ebrahim Nasrabadi

Abstract We consider the dynamic shortest path problem in the continuous-time

model because of its importance. This problem has been extensively studied in the

literature. But so far, all contributions to this problem are based on the assumption

that all transit times are strictly positive. However, in order to study dynamic network

flows it is essential to support negative transit times since they occur quite naturally

in residual networks. In this paper we extend the work of Philpott [SIAM Control

Opt., 1994, pp. 538–552] to the case of arbitrary (also negative) transit times. In par-

ticular, we study a corresponding linear program in space of measures and characterize

its extreme points. We show a one-to-one correspondence between extreme points and

dynamic paths. Further, under certain assumptions, we prove the existence of an opti-

mal extreme point to the linear program and establish a strong duality result. We also

present counterexamples to show that strong duality only holds under these assump-

tions.

Keywords Shortest Path Problem ·Linear Programming in Measure Spaces ·

Extreme Points ·Duality Theory ·Measure Theory

Mathematics Subject Classification (2000) 05C38 ·49J27 ·90C46 ·46E27

1 Introduction

The shortest path problem is one of the most basic and important problems in opera-

tions research. An interesting extension of this problem is the dynamic shortest path

problem, whose goal is to find a shortest path between two specified nodes in a network

where

–each arc has a transit time determining the amount of time needed for traversing

that arc,

This work is supported by DFG project SK58/7-1.

The first author is supported by DFG Research Center Matheon in Berlin.

R. Koch, E. Nasrabadi

Technische Universit¨at Berlin, Institut f¨ur Mathematik, Straße des 17. Juni 136, 10623 Berlin,

Germany, E-mail: {koch,nasrabadi}@math.tu-berlin.de

–waiting at the nodes is allowed and causes cost,

–the cost for traversing an arc as well as the cost for waiting vary over time.

The aim of this paper is to study a general class of dynamic shortest path problems

and give a theoretical analysis of such problems. We concenterate on a continuous-time

setting where arcs can be entered and left at arbitrary points in time and assign also

negative values to transit times.

Related Literature The dynamic shortest path problem was first introduced by Cooke

and Halsey [7], who present an algorithm based on Bellman’s principle of optimality.

In the model proposed by Cooke and Halsey [7], arcs can be entered and leaved only

at integral points in time, leading to the so-called discrete-time model. Since then, a

number of authors (see, e.g., [2,5,6,13]) have studied different aspects of the discrete-

time dynamic shortest path problem.

Although discretization of time leads to problems that are considerably easier to

solve, this approach suffers from a serious drawback: the points in time at which de-

cisions are made are fixed in advance, before the problem is solved. For many appli-

cations, this is not a desired feature of the corresponding problem, since we get only

approximations on the optimum. In contrast, in the continuous-time model, decisions

can be made at arbitrary points in time.

The first work on dynamic network flows in the continuous-time model is due to

Philpott [14] and Anderson, Nash and Philpott [4], who study the dynamic maximum

flow problem in a network with zero transit times and time-varying transit and storage

capacities. Thereinafter, this topic has become an area of active research and many

authors have extensively studied different features of continuous-time dynamic network

flows (see, e.g., [8,10]).

Research on the continuous-time version of the dynamic shortest path problem is

conducted by, e.g., Orda and Rom [11,12], Philpott [15], and Philpott and Mees [16,17].

In particular, Philpott [15] formulates the problem as a linear program (LP for short)

in a space of measures and investigates the relationship between the problem and its

LP formulation. Especially, he introduces a dual problem and proves the absence of a

duality gap1. He also demonstrates the existence of an optimal extreme point for the LP

formulation and derives a correspondence between extreme points and dynamic paths.

Moreover, he establishes a strong duality result in the case where the cost functions

are Lipschitz-continuous.

In all of the work mentioned above, it is assumed that the transit times are

strictly positive. In particular, this assumption is critical to the arguments presented by

Philpott [15]. In this case, the feasible region of the LP formulation becomes bounded

with respect to a certain norm. This makes it possible to apply certain results from

the theory of linear programming in infinite-dimensional spaces (see, e.g., Anderson

and Nash [3]). This method no longer works for the case of nonpositive transit times

since the feasible region of the corresponding LP formulation may be unbounded.

Philpott [15] writes in the conclusion of his paper, “the assumption that all transit

times are strictly positive is central to the arguments presented”

1There is no duality gap between a linear program and its dual if they have the same

(finite) value. If this finite value is achieved by feasible solutions of the primal and of the dual

program, then strong duality holds. In finite-dimensional linear programming, strong duality

holds, whenever no duality gap exists and vice versa. In general, this is not the case in infinite-

dimensional linear programming (see, e.g., [3]).

In this paper we extend Philpott’s work [15] to the case where transit times can

be also negative. Notice that the assumption that all transit times are strictly positive

is not too restrictive in direct applications of the dynamic shortest path problem. For

instance, when some material (e.g., a vehicle or a message) has to be sent between

two specified points in a network as quickly or as cheaply as possible. However, like

classical shortest path problems, instances with negative transit times arise in solving

more complicated problems. For example, verifying whether a given dynamic flow has

minimum cost, we have to scan the residual network for negative cycles (see Chapter 6

in [10]). But, in general, the residual network contains arcs with negative transit times.

Hence, we cannot use the results in the literature and particularly not those derived by

Philpott [15]. This is our main motivation to study the dynamic shortest path problem

in the continuous-time setting, but – in contrast to Philpott’s work – with possibly

negative transit times.

Our Contribution We advance the state of the art for dynamic shortest path problems

by bridging the gap between them and linear programming. Our results generalize those

achieved by Philpott [15] for the case of positive transit times, but the ideas of the

underlying analysis and proofs do not follow those of Philpott. In the following we give

an overview of the paper and discuss the contribution in more detail.

In Section 2, a detailed definition of the continuous-time dynamic shortest path

problem is given. Like in the static case, the problem is formulated as the minimum

cost flow problem, but in contrast, the flow on each arc is modeled as a finite Borel

measure on the real line (time axis) indicating the amount of flow entering the arc over

time. This idea is due to Philpott [15], who gives an LP formulation of the problem

in space of measures. In Section 2, we also give an alternative LP formulation, which

differs slightly from that formulated by Philpott [15].

Section 3 deals with characterization of extreme points of the LP formulation. In

particular, we first prove that the continuous part of any extreme point solution is zero

and then derive a one-to-one correspondence between extreme points and dynamic

paths.

In Section 4, we consider a dual problem and derive some results between the LP

formulation and its dual. Specifically, a strong duality result under certain assumptions

is obtained. We also give examples to show that strong duality does not hold in general

if one of these assumptions is not fulfilled.

Our results are based on new techniques, which, among others, include a fair

amount of advanced measure theory. For the convenience of the reader, we give the

basic definitions and results in measure theory that are required for the purposes of

this paper in Appendix A. In Appendix B we provide the proofs of some technical

lemmas.

2 Problem description and formulation

In this section we give a precise description of the dynamic shortest path problem

in the continuous-time model. To motivate our treatment, we first describe the static

shortest path problem.

We consider a directed graph G:= (V, E) with finite node set Vand finite arc

set E⊆V×V. An arc efrom a node vto a node wis denoted by e:= (v, w) to

emphasize that eleaves vand enters w. In this case, we say that node vis the tail

of eand wis the head of eand write tail(e) := vand head(e) := w. Further, we

use δ+(v) := {e∈E|tail(e) = v}and δ−(v) := {e∈E|head(e) = v}to denote the

set of arcs leaving node vand entering node v, respectively.

Awalk Pfrom node vto node wis an alternating sequence of nodes and arcs

of the form P:= (v1, e1, v2, . . . , vn, en, vn+1) such that v1=v,ei= (vi, vi+1)

for i= 1, . . . , n, and vn+1 =w. Throughout the paper we denote the walk Pby

the arc sequence (e1,...,en), assuming that head(ei) = tail(ei+1) for i= 1,...,n.

Further, we denote by E(P) := {e1,...,en}and V(P) := {v1,...,vn+1}the set of

arcs and nodes, respectively, involved in P. The walk Pis said to be a path from vto w

(or simply v-w-path) if v1, v2, . . . , vn+1 are pairwise distinct, except v1and vn+1. If

in addition v1=vn+1, the path Pis called a cycle. A node wis said to be reachable

from node vif there exists a v-w-path.

Each arc e∈Ehas an associated cost ce. The cost of a path P= (e1,...,en)

is defined as the sum of the costs of all arcs in the path, that is, cP:= Pn

i=1 cei.

Let s∈Vbe a given source and t∈Vbe a given sink. We assume without loss of

generality that every node of Gis reachable from sand that tis reachable from every

node. The (static) shortest path problem is to determine a path from source sto sink t

with minimal cost. This problem can be seen as the problem of sending one unit of

flow from sto tat minimal cost and hence, can be formulated as follows:

min X

e∈E

cexe

s.t. X

e∈δ+(v)

xe−X

e∈δ−(v)

xe=8

1 if v=s

0 if v6=s, t

−1 if v=t∀v∈V ,

xe≥0∀e∈E .

(LP)

Here the decision variable xegives the amount of flow on arc e. It is well-known that the

underlying constraint matrix is total unimodular. This implies that any extreme point

of (LP) corresponds one-to-one to a path from sto twith the same cost. In particular,

in any extreme point, xeis either 1 or 0 for each e∈Ewhich indicates whether or

not the corresponding path involves the arc e, respectively. Thus, an optimal extreme

point of (LP) yields a shortest s-t-path.

The dual problem (LP∗) of (LP) can be written as follows:

max πs−πt

s.t. πv−πw≤ce∀e= (v, w)∈E . (LP∗)

If πis an optimal solution for (LP∗) then for every node v∈Vthe cost of a shortest s-v-

path is equal to πv−πs. Moreover, if the network contains a cycle Cwith negative cost,

then (LP) is unbounded because we can send an infinite amount of flow along Cand

therefore the objective function value goes to −∞. In this case, the dual problem (LP∗)

is infeasible. The shortest path problem where cycles with negative cost are allowed is

difficult to solve. In fact, it is NP-complete (see [1, page 95]), i.e., no polynomial-time

algorithm for this problem exist unless P=NP. For the case that the network contains

no negative cycle, strong duality holds between (LP) and (LP∗) and numerous efficient

algorithms for solving the shortest path problem exist. A comprehensive discussion and

comparison of these algorithms can be found in the textbook by Ahuja, Magnanti, and

Orlin [1].

So far we have considered the setting of the static shortest path problem in which

time does not enter the model. We now turn to the dynamic case in which each

arc e∈Ehas an associated transit time τe, specifying the required amount of time

to travel from the tail to the head of e. More precisely, if we leave node vat time θ

along an arc e= (v, w), we arrive at wat time θ+τe. Further, waiting is allowed at

the nodes of the network for later departure. In the following we extend the definition

of (static) walk, path, and cycle to the dynamic case.

Adynamic walk is a pair of a walk P= (e1,...,en) together with a family of

waiting times (λ1,...,λn+1). For i= 1,...,n+ 1 after arriving at node vi∈V(P)

we wait λitime units before we leave vi. Given a starting time θ, let αibe the

time when we arrive at node viand βibe the time when we departure from node vi.

For i= 1,...,n+ 1, the arrival time αiand the departure time βican be computed

recursively as follows:

αi:= (θfor i= 1

βi−1+τei−1otherwise and βi:= αi+λi.

A walk Pis called a dynamic path if Pdoes not revisit any node (except the endpoints)

at the same point in time, i.e., [αi, βi]∩[αj, βj] = ∅for each 1 ≤i < j ≤n+ 1

with vi=vjand (i, j)6= (1, n + 1). Note that the underlying (static) walk of a

dynamic path need not to be a (static) path since it is allowed that a node can be

revisited at different points in time. Moreover, Pis said to be a dynamic cycle if Pis

a dynamic path, and in addition v1=vn+1 and α1=βn+1. Further, we say that the

path Phas time horizon Θif βn+1 =Θ.

Each arc eand each node vhas a cost function ce:R→Rand cv:R→R,

respectively. For a certain point in time θ∈R, the cost for leaving the tail of eat time θ

and traveling along eis ce(θ) and the cost per time unit for the waiting at vat time θ

is cv(θ). The cost of a dynamic walk P= (e1,...,en) with arrival times α1,...,αn+1

and departure times β1,...,βn+1 is thus given by

cost(P) :=

i=1

cei(βi) +

n+1

i=1 Zβi

αi

cvi(θ)dθ .

Here the first sum gives the cost for traveling along arcs in the path and the second one

gives the cost for waiting at nodes of the path. A dynamic path Pfrom vto wis called

adynamic shortest path if it holds cost(P)≤cost(P′) for all dynamic v-w-paths P′

with the same starting time and the same time horizon as P.

Given a source s∈V, a sink t∈V, and a time horizon Θ, the continuous-time

dynamic shortest path problem is to determine a dynamic shortest path from sto t

with starting time 0 and time horizon Θ:

Continuous-time Dynamic Shortest Path Problem (CDSP)

Input: A network consisting of a directed graph G:= (V, E), cost func-

tions (ce)e∈Eand (cv)v∈V, a source s∈V, a sink t∈V, and a

time horizon Θ,

Task: Find a dynamic shortest s-t-path with starting time 0 and time

horizon Θ.

For the case that transit times as well as the time horizon are integral and further,

waiting times have to be integral, the problem is a discrete-time model. Actually, in

the discrete-time model, it is only allowed to leave each node at integral points in time.

Hence, the resulting problem can be solved by the time-expanded network technique

(see, e.g., [8]). In this paper we focus on the more challenging continuous-time model

in which we can leave each node at any point in time and further, transit times as well

as the time horizon can be any real value.

Throughout the paper, if not mentioned otherwise, the starting time and the time

horizon of a dynamic path from source sto sink tare assumed to be 0 and Θ, respec-

tively.

2.1 LP formulation in measure spaces

We observed that the static shortest path problem has an equivalent LP formula-

tion as (LP). More precisely, there is a one-to-one correspondence between static s-t-

paths and extreme points of (LP) which preserves costs. Hence, a natural question is

“Does CDSP have an equivalent LP formulation?” In order to answer this question

we go along the same lines as in the static case. In fact, CDSP can be seen as the prob-

lem of sending one unit of flow from source sat time 0 to sink tat time Θat minimal

cost which can be modeled as a minimum cost flow over time problem. Unlike the static

case the flow over time on each arc e∈Eis given by a measure xeon the real line R

(time axis) which assigns to each suitable subset Ba nonnegative real value xe(B).

Intuitively, xe(B) is interpreted as the amount of flow entering arc ewithin the times

in the subset B. This idea is due to Philpott [15], who formulates CDSP as a linear

program in space of measures. In what follows, we give a detailed description of the LP

formulation for CDSP, which differs slightly from that of Philpott [15] and is easier to

recognize as a generalization of (LP). But first we motivate the use of measures.

Let Bbe the collection of all intervals of R, whose elements can be seen as time

intervals. In order to distribute flow over time on an arc e∈Ewe assign a value xe(I)

to each time interval I, determining the amount of flow entering arc ewithin the time

interval I. Thus, intuitively, the function xe:B → Rhas to satisfy the following

properties:

(i) The flow assigned to the empty set is 0, i.e., xe(∅) = 0.

(ii) An amount of flow is always nonnegative, i.e., xe(I)≥0 for all I∈ B.

(iii) For a countable collection (Ii)i∈Nof pairwise disjoint intervals in B, it holds:

xe„[

i∈N

Ii«=X

i∈N

xe(Ii).

On closer inspection of property (iii) we observe that Bmust be closed under count-

able unions of its members. Otherwise property (iii) is not well-defined. In addition,

we require that Bis closed under complementation. Henceforth, we extend Bto the

smallest set containing all (open) intervals which is closed under countable union and

complementation. We call Bthe Borel σ-algebra on Rand a set B∈ B aBorel set

or a measurable set. In this manner properties (i)–(iii) make µto a Borel measure.

Thus, measures provide an appropriate tool for defining flow distributions over time.

Based on the above observations, we define a measure-based flow over time xby

Borel measures

xe:B → Re∈E .

For a Borel set B∈ B the value xe(B) gives the amount of flow entering arc ewithin

the times in B. For the purposes of the paper, we require xeto be a finite Borel measure

on R, i.e., |xe|:= xe(R)<∞for all e∈E. This means that the total amount of flow

traversing an arc is finite. Through the paper, we focus on measure-based flows over

time and therefore the term flow is used to refer to measure-based flow over time.

Recall that the problem we want to model is to send one unit of flow from sat

time 0 to tat time Θso that the cost is minimized. This means that there is a supply

of one flow unit at the source at time 0, and a demand of one flow unit at the sink at

time Θ. Hence, the supply or demand at a node vis given by a signed Borel measure bv

defined as

bv(B) := 8

1v=s, 0∈B

−1v=t, Θ ∈B

0 otherwise ∀B∈ B .

The value |bv(B)|is interpreted as the amount of supply or demand at node vover

the Borel set Bdepending on whether bv(B)>0 or bv(B)<0, respectively.

Flow has to be stored at a node v∈Vif more flow enters vthan leaves that node

at certain points in time. Given a flow x, the storage at node vis determined by a

signed measure yvdefined as

yv(B) := bv(B)−X

e∈δ+(v)

xe(B) + X

e∈δ−(v)

xe(B−τe)∀B∈ B ,(1)

where B−τe:= {θ−τe|θ∈B}. For a Borel set Bthe value yv(B) shows the

amount of flow which is in total additionally stored at vover Bif yv(B)≥0. Note

that flow can also leave v, even if yv(B)≥0. Further, if yv(B)≤0 the value −yv(B)

can be interpreted as the total amount of stored flow leaving vover B. Since the space

of signed measures is a vector space (see Appendix A), (1) can be rewritten as follows:

e∈δ+(v)

xe−X

e∈δ−(v)

(xe−τe) + yv=bv.

Here xe−τeis understood to be a Borel measure defined by (xe−τe)(B) := xe(B−τe)

for every Borel set B∈ B.

We know that every signed Borel measure can be uniquely decomposed into a sum

of a discrete and a continuous measure (see for more details Appendix A). This implies

that for each arc ethe flow xeis the sum of a continuous flow xc

eand a discrete flow xd

Similarly, for each node v∈Vthe storage yis the sum of a continuous storage ycand

a discrete storage yd. Since the supply or demand bvis a discrete measure for each

node v, we get the following equation for xc= (xc

e)e∈Eand yc= (yc

v)e∈E:

e∈δ+(v)

e−X

e∈δ−(v)

(xc

e−τe) + yc

v= 0 ∀v∈V . (2)

A flow xis called discrete (continuous) if xc

e= 0 (xd

e= 0) for all arcs e∈E. So it

follows from (2) that yc= 0 whenever xis discrete.

For a node v∈Vwe let Yvbe the distribution function of the storage yv, that is,

Yv(θ) := yv((−∞, θ]), for all θ∈R. So we have

Yv(θ) = bv((−∞, θ]) −X

e∈δ+(v)

xe((−∞, θ]) + X

e∈δ−(v)

xe((−∞, θ −τe]) ∀θ∈R.

Here the first sum denotes the total amount of flow arriving at node vup to time θ

and the second one represents the total amount of flow leaving node vup to time θ.

Further, |bv((−∞, θ])|gives the total amount of supply or demand at node vup to

time θ, depending on whether bv((−∞, θ]) is positive or negative, respectively. Thus,

the value Yv(θ) gives us the amount of flow stored at node vat the point in time θ∈R.

It is assumed that there is no initial storage at any node and flow must not remain

at any node. This means Yv(−∞) := limθ→−∞ Yv(θ) and Yv(∞) := limθ→∞ Yv(θ)

must be zero for each node v∈V. Notice that both limits exist since Yvis of bounded

variation.

A flow xwith corresponding storage yfulfills the flow conservation constraint at

node vif

Yv(θ)≥0∀θ∈R.

The flow xfulfills the strict flow conservation constraints at node vif the equality

holds in the above inequality. This implies that storage is not allowed at v.

We suppose that the cost functions (ce)e∈Eand (cv)v∈Vare measurable. The

value ce(θ) can be interpreted as the cost per flow unit for sending flow into arc eat

time θand cv(θ) as the cost per time unit for storing one unit of flow at node vat

time θ. The cost of a flow xwith corresponding storage yis thus given by

cost(x) := Z∞

−∞ X

e∈E

ce(θ)dxe+Z∞

−∞ X

v∈V

cv(θ)Yv(θ)dθ . (3)

Summarizing the above discussion, the problem of sending one unit of flow from

a source sat time 0 to a sink tat time Θat minimal cost can be expressed as the

following linear program in the space of signed Borel measures:

min Z∞

−∞ X

e∈E

ce(θ)dxe+Z∞

−∞ X

v∈V

cv(θ)Yv(θ)dθ

s.t. X

e∈δ+(v)

xe−X

e∈δ−(v)

(xe−τe) + yv=bv∀v∈V ,

xe≥0∀e∈E ,

Yv≥0∀v∈V .

(LPM)

This formulation is quite similar to the formulation of (LP) and can be seen as its

extension. In fact if waiting is not allowed and the transit times as well as the time

horizon are zero, then (LPM) reduces to (LP).

A flow xwith corresponding storage ysatisfying the constraints of (LPM) is called

a feasible solution or feasible flow. Similarly as in the finite-dimensional linear program-

ming, a feasible solution of (LPM) is called an extreme point if it cannot be derived

from a convex combination of any two other feasible solutions. In the next section we

want to show that extreme points of (LPM) correspond to dynamic s-t-paths with the

same cost and vice versa. Hence, we have to encode a dynamic path with measures,

whereas in the static case a path is identified with its incidence vector whose elements

are 0 or 1. Let P:= (e1,...,en) be a dynamic path with arrival times αiand depar-

ture times βifor i= 1,...,n+ 1. The incidence vector χPof Pis a family (χP

e)e∈E

of discrete measures defined by

χP

e:= (Pi|ei=eχP

eiif e∈E(P)

0 otherwise ∀e∈E , (4)

where

χP

ei(B) := (1 if αi∈B

0 otherwise ∀B∈ B i= 1,...,n .

The corresponding storage ψP:= (ψP

v)v∈Vis defined by:

ψP

v:= bv−X

e∈δ+(v)

χP

e+X

e∈δ−(v)

(χP

e−τe)∀v∈V . (5)

For each v∈Vlet ΨP

vdenote the distribution function of the measure ψP

v, i.e.,

ΨP

v(θ) := ψP

v((−∞, θ]) for all θ∈R. It is not hard to observe that

ΨP

v(θ) = (Pi|vi=vΨP

vi(θ) if v∈V(P)

0 otherwise ∀v∈V ,

where

ΨP

vi(θ) := (1 for θ∈[αi, βi)

0 otherwise ∀i= 1,...,n+ 1 .

Therefore, ΨP

v≥0 and the incidence vector χPis a feasible solution of (LPM). In the

following section we show that χPis not only a feasible solution, but also an extreme

point of (LPM).

3 Characterization of extreme points

The notion of extreme points plays an important role in the theory of linear pro-

gramming. This is because of the fact that they usually have a considerably simpler

structure than arbitrary feasible solutions and further, whenever a linear program has

an optimum solution, then one can be found among the extreme points. This becomes

even more important for the LP formulation of the shortest path problem because

an extreme point of (LP) corresponds to a (static) s-t-path with the same cost and

vice versa. In this and the next section we show that these results can be extended

to (LPM). In particular, in the first part of this section we show that the continuous

part of any extreme point is 0. Subsequently, in the second part we derive a one-to-one

correspondence between extreme points of (LPM) and dynamic s-t-paths. Further, in

the next section we prove, under some assumptions, the existence of an optimal extreme

point for (LPM).

We begin our discussion with an important result concerning the characterization

of extreme points. Roughly speaking, it deals with the following situation: whenever

there exists a walk Pcarrying a continuous measure of flow and in addition there is

waiting at the beginning and at the end but not at intermediate nodes of P, then the

corresponding feasible solution is not an extreme point. For the proof, we require the

following technical lemma, proven in Appendix B.

Lemma 1 Let µbe a finite signed measure on Rwith a nonnegative distribution

function F. Let S:= {θ∈R|F|(a,b)>0for some interval (a, b)∋θ}be the

set of points with a strictly positive neighborhood regarding F. Then R\Sis a

strict µc-null set, i.e., µc|R\S= 0.

For a signed measure µthe positive and negative part is denoted by µ+and µ−,

respectively (see Appendix A). This is used in the following lemma.

Lemma 2 Let xwith corresponding storage ybe a feasible solution for (LPM)

and P= (e1,...,en)be a walk from node vto node w. Further, assume that there

exists a positive measure fsuch that

f−(τe1+...+τen)≤yc−

v,(6)

i|ei=e

f−(τe1+...+τei)≤xc

e∀e∈E , (7)

f≤yc+

w.(8)

Then xis not an extreme point.

Proof We show that xcan be written as the convex combination of two feasible solu-

tions x1and x2. The basic idea is to increase and decrease xalong Pto construct x1

and x2. This will change the flow xon arcs e1,...,enand affect the storage yat end-

points vand w. To maintain the feasibility of x1and x2, we first find a closed interval

satisfying certain properties. We then send at the beginning of the interval less flow

and at the end more flow as compared with x. But in total we send the same amount

of flow as xover the interval along P. This gives us x1. The solution x2is constructed

the other way around, i.e., we send more flow at the beginning of the interval and less

flow at the end.

Let us first look for an interval which ensures that we are able to increase and

decrease the flow xslightly along Pwithout violating feasibility. Let τ:= Pn

k=1 τei

be the transit time of the walk P. Notice that Pcan be seen as a dynamic walk with

zero waiting times at nodes. We show that there exists a closed interval Isatisfying

the following properties:

1. f(I)>0 implying that the flow can be reduced along Pover I−τwith a nonzero

measure;

2. Yv|I−τ> ǫ and Yw|I> ǫ for some ǫ > 0 implying that the storage can be reduced

at vand w.

As in Lemma 1, we define

Sv:= {θ∈R|Yv|I′>0 for some open interval I′∋θ},

Sw:= {θ∈R|Yw|I′>0 for some open interval I′∋θ}.

Because of (8) we know that fis absolutely continuous with respect to yc+

wand, as a

consequence, with respect to |yc

w|:= yc+

w+yc−

w. On the other hand, it follows from

Lemma 1 that yc

w|R\Sw= 0. Hence, we can conclude that |yc

w|(R\Sw) = 0 and

further, f=f|Swsince fis absolutely continuous with respect to |yc

w|. Similarly, (6)

and Lemma 1 imply f= (f−τ)|Sv. Consequently, we get from the definitions of Sv

and Swthat there exists an θ∈supp(f) and an open interval I′containing θsuch

that Yv|I′−τ>0 and Yw|I′>0. Since θis contained in the support of f, every closed

interval I:= [α, β]⊆I′with θ∈(α, β) satisfies the properties above.

In the following let I= [α, β] be a closed interval and ǫ > 0 such that f(I)>0,

Yv|I−τ> ǫ, and Yw|I> ǫ. Without lost of generality, assume that f(R\I) = 0

(i.e., supp(f)⊆I). This can be done by letting f:= f|I. Further, let α1, β1∈I

with α1≤β1be chosen in such a way that f([α, α1]) = f([β1, β]) = min{ǫ, f(I)

2}.

Note that α1and β1exist since fis a continuous measure. Then we define

f1:= f|(α,α1)−f|[β1,β],

f2:= −f|(α,α1)+f|[β1,β]=−f1.

It is easy to see that f1+f2= 0 and that |f1(B)|< ǫ and |f2(B)|< ǫ for all

measurable set B. We now define xqfor q= 1,2 by

e=xq

e+X

i|ei=e`fq|[α,β]−(τ1+. . . +τi)´∀e∈E .

The equation f1+f2= 0 implies 1

2x1+1

2x2=x. Thus it remains to check the

feasibility of x1and x2. The flows x1and x2are nonnegative because of (7) and the

fact that |f1| ≤ fand |f2| ≤ f. Let y1and y2be the corresponding storage of x1

and x2, respectively. It is not hard to see that for q= 1,2yqis equal to yexcept for

nodes vand wwhere we have yq

v=yv−(fq−τ) and yq

v=yw−fq. It then follows

from the definition of f1and f2that the distribution functions Y1,Y2, and Ycoincide

everywhere except on I−τand Iat nodes vand w, respectively. Within the points

in time in I−τand Iat nodes vand w, respectively, we get

v|I−τ≥0, Y q

w|I≥0, q = 1,2,

due to the fact that |f1(B)|< ǫ,|f2(B)|< ǫ and the definition of I. This yields the

desired result. ⊓⊔

As already mentioned, our first goal in this section is to show that the continuous

part of an extreme point is 0. Thus, if we find a walk and a nonzero measure satisfying

the assumptions of Lemma 2 whenever the continuous part is positive, we are done.

The next example shows that an algorithm constructing such a path could cycle and,

hence, must be designed carefully.

Example 1 Consider the network depicted in Figure 1 where the transit times are

shown on the arcs and suppose that fis some continuous Borel measure such that

f([0,1]) = 1 and f(R\[0,1]) = 0. Let Θ:= 0 be the time horizon and consider the

following feasible solution of (LPM): The flow fcirculates on the cycle Cinduced by s

and v. Every time the flow reaches the node vhalf of the remaining flow is sent in the

arc (v, t). Thus we get the following solution

x(s,v)=

∞

i=0

2i(f+i), x(v,s)=1

2(x(s,v)+ 1), x(v,t)=1

2(x(s,v)+ 1).

s t

−1

Fig. 1 Network for Example 1. The transit times are shown on the arcs.

Every finite s-t-walk Psatisfies the assumptions of Lemma 2. The corresponding mea-

sure is f

2kassuming that the cycle Cis used k−1 times by P. On the other hand an

uncarefully designed algorithm could be caught within the cycle C.

If we want to apply Lemma 2 we have to ensure that there exists a node whose

continuous part of storage is nonzero. The next lemma shows that whenever we have

an extreme point xsuch that the continuous part of the corresponding storage is 0,

then the continuous part of xhas to be 0 as well.

Lemma 3 Let xbe an extreme point of (LPM) with corresponding storage y. If

yc= 0, then xc= 0.

Proof Since yc= 0, from (2) we get

e∈δ+(v)

e−X

e∈δ−(v)

(xc

e−τe) = 0 ∀v∈V.

Thus we can add and subtract this equation from equation (1) without changing its the

right hand side. This yields two feasible solutions x1:= x+xcand x2:= x−xcboth

with corresponding storage yif xc0. Since x=1

2(x1+x2) is a convex combination

of two feasible solutions, xis not an extreme point. ⊓⊔

Having established Lemma 3, we consider the case where yc

v6= 0 for some node v,

which requires a more complicated treatment. In this case, we prove the existence of

a walk and a nonzero measure satisfying the assumptions (6)-(8) of Lemma 2. The

approach is based on an algorithm, which is a kind of the well-known breadth-first

search (BFS). The node set and arc set of the BFS-tree are denoted by VTand ET,

respectively. Each node in VTcorresponds to one node in Vand each arc in ETto one

arc in E. Actually, the BFS-tree contains in general multiple copies of a node v∈V

and multiple copies of an arc e∈E. An arc in ETwhose head is a leaf is called a

leaf arc. The BFS-tree is an out-tree and constructed in a way that each path starting

at the root node corresponds to a walk satisfying the assumptions (6) and (7). The

termination condition ensures that also the assumption (8) is satisfied. An illustration

of the algorithm is shown in Figure 2.

Before giving a detailed description of the algorithm, we present the following

lemma that will help us to show correctness. For the proof, see Appendix B.

Lemma 4 Let µ,µ1,...,µnbe finite Borel measures on Rwith µ≤Pn

i=1 µi.

Then there exists Borel measures ¯

µ1,...,¯

µnsuch that ¯

µi≤µi, for i= 1,...,n

and µ=Pn

i=1 ¯

µi.

v∗

e∗

eT, feT

Fig. 2 Construction of the BFS-tree.

BFS Algorithm

Input: A feasible solution xof (LPM) with corresponding storage yand a

node v1with yc−

v1>0.

Output: A walk and a measure satisfying the assumptions of Lemma 2.

(1) Init ¯

xe:= xc

efor all e∈E,VT:= ∅, and ET:= ∅.

(2) Add an (artificial) arc e∗to ETand let the head of e∗be the copy v∗

1of v1. Assign

the flow fe∗:= yc−

v1to e∗.

(3) For each leaf arc eT∈ETwith head vTdo:

(a) Let v∈Vbe the original node of vTand τeTbe transit time of the original

arc of eT(In the case of eT=e∗we set τeT:= 0).

(b) If feT−τeTand yc+

vare not mutually singular, then go to (5).

for all e∈δ+(v) and feT−τeT=Pe∈δ+(v)fe.

(d) For each arc e∈δ+(v) with fe0 add a copy e′to ET, connect e′to eTvia

vTand set fe′:= feand ¯

xe:= ¯

xe−fe.

(4) Go to (3).

(5) Return the walk consisting of the original arcs of the unique path from v∗

1to vT

in the BFS-Tree and the measure f:= min{feT−τeT, yc+

v}.

In what follows, we analyse the correctness of the BFS Algorithm in details.

One complete execution of Step (3) is called phase. Thus, in each phase every leaf arc

is treated and the depth of the tree is increased by 1. Note that the first phase is not

interrupted since eT=e∗,v=v1,fe∗=yc−

v1, and we know that yc−

v1and yc+

v1are

mutually singular. Further, ¯

xedenotes the remaining continuous flow on arc esince ¯

is initialized with xc

eand after assigning the flow feto a tree arc e′in Step (3d) we

reduce ¯

xeby the same flow. The next two lemma shows that the BFS Algorithm

works properly.

Lemma 5 The BFS Algorithm is well-defined and correct. In particular, the

algorithm is able to execute Step (3c), terminates in a finite time, and produces

the desired output.

Proof Assume that we are at Step (3c) and let e∗,eTand vbe as defined by the

algorithm. With each arc e∈Ewe associate two measures geand gl

e, which denote

the total flow assigned to ewithin the BFS-tree and the total flow assigned to ewithin

the leaf arcs of the BFS-tree, respectively. More precisely, measures geand gl

eare

defined by

ge:= X

e′∈ET|e′=e

fe′, gl

e:= X

leaf arc e′|e′=e

fe′.

Note that the artificial arc e∗does not appear in any of the two sums above. Steps

(3a)-(3d) ensure that flow (ge)e∈ETfulfills the strict flow conservation constrains at

intermediate nodes of the BFS-tree. Hence, for each intermediate node v∈VTwe get:

e∈δ−(v)

(ge−τe)−X

e∈δ+(v)

ge=X

e∈δ−(v)

(gl

e−τe)−(fe∗if v=v1

0 otherwise

≥X

e∈δ−(v)

(gl

e−τe)−yc−

v.(9)

Further, because of Step (3d) we see that the sum ¯

xe+geremains constant during the

execution of the algorithm. In fact, we always have

e=¯

xe+ge∀e∈E . (10)

Therefore, by substituting ¯

xe+geinstead of xcin (2), we get

v=X

e∈δ−(v)

((¯

xe−τe) + (ge−τe))−X

e∈δ+(v)

(¯

xe+ge).

On the other hand, it holds ¯

xe≥0 for each arc ebecause of earlier executions of (3c).

Now it follows from the above equation and inequality (9) that

e∈δ−(v)

(gl

e−τe)≤yc+

v+X

e∈δ+(v)

xe.

Because of Step (3b), we know that feT−τeTand yc+

vare mutually singular. Hence,

from the above inequality we obtain

feT−τeT≤X

e∈δ+(v)

xe.

Now we can construct a decomposition of feT−τeTinto Pe∈δ+(v)feso that fe≤¯

for each arc e∈δ+(v) (see for more details Lemma 4). This establishes the validity of

Step (3c).

Next we prove the termination of the algorithm. We first observe that the number

of tackled leafs in one phase is finite. This can be seen by induction and the fact that

the number of outgoing arcs of an original node is finite. Thus it suffices to show that

the number of phases is finite. In each phase the flow in the leave arcs is completely

routed to the outgoing arcs of the corresponding head nodes. Thus, by induction the

total amount of flow in the leaf arcs is always equal to fe∗

1(R) =: ǫ. Hence, in each

phase the total amount of flow (Pe∈Ege)(R) is increased by ǫ. On the other hand,

because of (10) the total amount of flow is bounded by M:= (Pe∈Exc

e)(R) which is

finite since (xe)e∈Eare assumed to be finite measures. Thus, the number of iterations

is bounded by ˚M

ǫˇand the algorithm terminates in a finite time.

For the correctness of the algorithm we show that the output of the algorithm

satisfies the assumptions (6)-(8) of Lemma 2. Consider Step (3c). Since this step is

well-defined the flow which is assigned to the outgoing arcs of vis smaller than the

flow feT. Therefore we obtain the following invariance from Steps (2) and (10): For

each tree arc eT∈ETwith head node vTthe walk consisting of the original arcs

of the unique path from v∗

1to vTand the measure feTsatisfies (6) and (7). Hence,

the correctness of the algorithm follows directly from the termination condition in

Step (3b) and the definition of fin the final Step (5). Note that fis nonzero since feT

and yc+

vare not mutually singular when reaching Step (5). This completes the proof

of the lemma.

The following lemma concludes the first part of this section.

Lemma 6 Let xwith coresponding storage ybe an extreme point of (LPM). Then

xc= 0.

Proof We assume the opposite and derive a contradiction. Suppose that xc

eis nonzero

for some arc e. Then, it follows from Lemma 3 that yc

vis nonzero for some node v. On

the other hand, we can conclude from (2) that

v∈V

v(R) = X

v∈V0

e∈δ−(v)

e(R)−X

e∈δ+(v)

e(R)1

A= 0 .

since, for each edge e=vw ∈E, the term xc

e(R) occurs once with a positive sign

if wis considered in the sum above and once with a negative sign if vis considered in

the sum above. Hence, we assume without loss of generality that yc−

v0. Then, the

BFS Algorithm which gets as input the feasible solution xand the node v, gives as

output a walk and a nonzero measure satisfying the assumptions of Lemma 2. Then

Lemma 2 implies that xis not an extreme point, which is a contradition. This yields

the result.

Up to this point, we have shown that xcmust be zero whenever xis an extreme

point of (LPM). Hence, we restrict our attention to discrete feasible solutions, when

identifying extreme points. In what follows, we show that an extreme point of (LPM)

corresponds to a dynamic s-t-path. We first give some definitions.

Suppose that xis a discrete feasible solution of (LPM) with corresponding storage y

and that P= (e1,...,en) is a dynamic walk with arrival times α1,...,αn+1 and

departure times β1,...,βn+1. Let δbe a positive real number. The walk Pcarries a

flow of value δ(with respect to x) if

xek({βk})≥δ∀i= 1,...,n ,

Yvk(θ)≥δ∀θ∈[αi, βi), i = 1,...,n+ 1 .

The flow value of Pis defined as the maximum amount of flow that can be carried

by P. The walk Pis called flow-carrying walk if its flow value is positive. For the case

that Pis a dynamic path or dynamic cycle, it is called a flow-carrying path or cycle,

respectively.

For a dynamic s-t-path let χPbe the corresponding incidence vector and ψPbe

the corresponding storage, respectively, given by (4) and (5). Then it is not hard to

observe that Pcarries a flow of value δif and only if δ·χP

e≤xefor all e∈E

and δ·ΨP

v≤Yvfor all v∈V.

Next we show that an extreme point provides a flow-carrying s-t-path. We do

this along the same lines as showing that the continuous part of an extreme point

is 0. Here a BFS-tree is constructed in a way that each path starting at the root node

corresponds to a flow-carrying walk. To do so, we assign to each tree arc eT= (vT, wT)

a measure feTwhose support consists only of one point in time θ. This is interpreted

as follows: Let e= (v, w) be the original arc of eT. Then the arc eis entered at time θ

in the corresponding walk, i.e., the departure time from node vis θand consequently

the arrival time at node wis θ+τe. If we consider the unique path from the root

node to wT, then the corresponding s-w-walk carries a flow of value feT({θ}). The

termination condition ensures that in the end we obtain a flow carrying s-t-walk.

The construction of the BFS-tree follows the same lines as the Continuous BFS

Algorithm. But in contrast, we have to take care that the constructed BFS-Tree has

finite width since incoming flow could be splitted into an infinite but countable number

of different parts. Therefore in Step (3c) of the algorithm, we do not propagate the

entire flow of an arc. In particular, we use the following result, the proof of which can

be found in B.

Lemma 7 Let µ1and µ2be two finite discrete measures. Furthermore, let γbe

a signed measure with γ(R) = 0 and nonnegative distribution function Fγsuch

that µ2+γ≥µ1. Consider a point θ∈Rand let ν1≤µ1be a measure with

supp(ν1) = {θ}. Then for every ρ∈[0,1) there exists a (discrete) measure ν2≤µ2

with finite support and a signed (discrete) measure ηwith distribution function Fη

such that:

ρ·ν1=η+ν2,

0≤Fη≤Fγ,

η(R) = 0 .

We are now in a position to give a detailed description of the algorithm.

Discrete BFS Algorithm

Input: A discrete feasible solution xof (LPM) with corresponding storage

Output: An s-t-walk carrying a flow of value of f.

(1) Init ¯

xe:= xefor all e∈E,VT:= ∅,ET:= ∅,i:= 1, and ρ:= 3

(2) Add an (artificial) arc e∗to ETand let the head of e∗be the copy s∗of s. Assign

the measure fe∗:= bsto e∗.

(3) For each leaf arc eT∈ETwith head vTdo:

(a) Let v∈Vbe the original node of vTand τeTbe transit time of the original

arc of eT(In the case of eT=e∗we set τeT:= 0). Further, let θ∈Rbe such

that {θ−τeT}= supp(feT).

(b) If v=t,θ≤Tand ¯

yt|(θ,T ]> ǫ for a some positive ǫ∈Rthen go to (5).

with finite support such that fe≤¯

xe, 0 ≤YvT≤¯

Yv,yvT(R) = 0 and

ρ·(feT−τeT) = yvT+Pe∈δ+(v)fe

(d) For each arc e∈δ+(v) and each time ϑ∈supp(fe) add a copy e′to ET,

connect e′to eTvia vTand set fe′:= fe|{ϑ},¯

xe:= ¯

xe−fe′, and ¯

yv:=

yv−yvT.

(4) Set i:= i+ 1 and then ρ:= 2i+1

2i+2 . Go to (3).

(5) Return the dynamic walk corresponding to the unique path from s∗to vTin the

BFS-Tree and the positive real number δ:= min{feT({θ−τeT}), ǫ}.

It is worth to mention that the continuous and the discrete BFS algorithm are

quite similar. Regardless of the kinds of measures participating in these algorithms,

the discrete BFS algorithm can be seen as a generalization of the continuous version

as follows: We obtain the notion of the continuous BFS algorithm if we set ρalways

equal to 1 and assume that yvTcomputed in Step (3c) is always zero. As in the

continuous BFS algorithm, ¯

xeis the remaining flow on an arc e. In addition ¯

yvis the

remaining storage of a node v.

Lemma 8 The Discrete BFS Algorithm works correctly. That is, Step (3c)

is always valid executable, the algorithm terminates, and the output is a flow car-

rying s-t-path.

Proof Assume that we reach Step (3c) and let e∗,eTand vbe as defined by the

algorithm. We define for each arc e∈Etwo measures: The measure geis the total

flow assigned to ewithin the BFS-tree and gl

eis the total flow assigned to ewithin

the leaf arcs of the BFS-tree. In addition, we define a measure zvfor each node v∈V

determining the stored flow which is already propagated. Thus, we have:

ge:= X

e′∈ET|e′=e

fe′, gl

e:= X

leaf arc e′|e′=e

fe′, zv:= X

v′∈VT|v′=v

yv′.

Note that the artificial arc e∗does not appear in any of the first two sums above and

that vTdoes not appear in the last sum. Because of the above definitions and the flow

conservation equation in Step (3c) we get:

e∈δ−(v)

(ge−τe)−X

e∈δ+(v)

ge≥zv+X

e∈δ−(v)

(gl

e−τe)−(fe∗if v=v1

0 otherwise

=zv+X

e∈δ−(v)

(gl

e−τe)−b+

v.(11)

Further, because of Step (3d) we see that the two sums ¯

xe+geand ¯

yv+zvremain

constant during the execution of the algorithm. Thus we have

xe+ge=xe∀e∈Eand ¯

yv+zv=yvv∈V . (12)

Further, by induction it holds ¯

yv(R) = 0 and ¯

Yv≥0 for each v∈V. Inserting the

first equation of (12) in (1) we obtain:

yv=bv+X

e∈δ−(v)

((¯

xe−τe) + (ge−τe))−X

e∈δ+(v)

(¯

xe+ge).

On the other hand, we know that ¯

xe≥0 for each arc ebecause of (3c). Hence the

above equation and inequality (11) imply

e∈δ−(v)

(gl

e−τe)≤ −b−

v+ (yv−zv) + X

e∈δ+(v)

xe.

Further, Step (3b) implies that there exists a ¯

θ∈R∪{∞} with ¯

yv(−∞,¯

θ)) = 0 such

that the measures (feT−τeT)−¯

yv|(−∞,¯

θ)and b−

v(−∞,¯

θ)) + ¯

yv|[¯

θ,∞)are mutually

singular (note that in the case v=twe can choose ¯

θ∈[θ, Θ] and otherwise we

choose ¯

θ=∞). Then we can conclude:

feT−τeT≤¯

yv|(−∞,¯

θ)+X

e∈δ+(v)

xe.

By the application of Lemma 7 we obtain a discrete measure ν≤Pe∈δ+(v)¯

xeof finite

support and the signed measure yvTsatisfying ρ·(feT−τeT) = yvT+ν. Now we apply

Lemma 4 to νin order to find the measure fefor each e∈δ+(v). From the conclusions

of both Lemmas 4 and 7, we get the validity of Step (3c).

For proving the termination of the algorithm we first observe that the number

of tackled leafs in one phase is finite. This is seen by induction and the fact that in

Step (3d) only a finite number of (new) leafs is added to the tree. Thus it suffices to

show that the number of phases is finite. At the end of each phase the amount of flow

in the new leave arcs is ρtimes the amount of flow in the old leafs. Let ρi=2i+1

2i+2 be

the ρused in phase i. Then at the end of phase ithe amount of flow in the new leaves

is equal to

fe∗(R)·

j=1

ρj=bs(R)·

j=1

2j+ 1

2j+ 2 = 1 ·1

j=1

2j+ 1

2j−1+ 1 =2i+ 1

2i≥1

2.(13)

Hence, in each phase the total amount of flow (Pe∈Ege)(R) is increased by at least 1

Further, because of (10) the total amount of flow is bounded by M:= (Pe∈Ex)(R)

which is finite since we restrict to finite measures. Thus, the number of iteration is

bounded by 2Mand the algorithm terminates in finite time.

To prove the correctness of the algorithm it is enough to show that the output is a

walk-carrying flow of amount f. Consider Step (3c) and a point in time ϑ≥θ+τeT.

It holds:

e∈δ+(v)

fe((ϑ, ∞)) = X

e∈δ+(v)

fe(R)−X

e∈δ+(v)

fe((−∞, ϑ])

=ρ·(feT−τeT)((−∞, ϑ]) −X

e∈δ+(v)

fe((−∞, ϑ])

=yvT((−∞, ϑ]) .

For e∈δ+(v) and ϑ∈supp(fe) we know YvT|[θ+τeT,ϑ)≥fe(ϑ). Therefore we obtain

the following: For tree arc eT∈ETwith head node vTthe dynamic walk corresponding

to the unique path from s∗to vTin the BFS-Tree carries a flow of value feT(R).

Hence, the correctness of the algorithm follows directly from the termination condition

in Step (3b) and the definition of δin the final step (5).

As mentioned previously, the nonzero components of any extreme point of (LP)

are one which indicate a static s-t-path. The next lemma shows that this result can be

extended to CDSP.

Lemma 9 Suppose that xis an extreme point of (LPM). Then the network G

contains no flow-carrying cycle. Moreover, there is a unique flow-carrying s-t-path

Pof flow value 1. In fact, we have x=χPwhere χPis the incidence vector of P.

Proof Let us first assume by contradiction that there is a flow-carrying cycle Cand

let χCbe the incidence vector of C. If Ccarries a flow of value δthen x1:= x+δ·χC

and x2:= x−δ·χCare both feasible solutions. Obviously x=1

2(x1+x2) is the

convex combination of x1and x2. This implies that xis not an extreme point, which

is a contradiction. Hence, there exists no flow-carrying cycles with respect to x.

Now suppose that there are two s-t-paths P1and P2with incidence vectors χP1

and χP2carrying a flow of values δ1and δ2, respectively. Let δ:= min{δ1, δ2}. Then

x1:= x+δχP1−δχP2and x2:= x−δχP1+δχP2are both feasible solutions and we

have x=1

2(x1+x2). Hence, xis not an extreme point, which is again a contradiction.

This implies that there must be at most one flow-carrying s-t-path.

We are left to prove the existence of a flow-carrying s-t-path of flow value 1. Since x

is an extreme point, it follows from Lemma 6 that the continuous part of xis 0. This

means that xis discrete and thus applying Discrete BFS Algorithm yields a

flow-carrying s-t-path Pwith respect to x. Define x∗:= x−δ·χPwhere δand χP

are the flow value and incidence vector of P, respectively. We show that δmust be 1

and further, x∗must be zero. Note that δ≤1 because of the definition of bs. Now

suppose that δ < 1. Then it is not hard to see that x∗6= 0 and 1

1−δx∗is also a

discrete feasible solution of (LPM). Thus there exists a flow carrying s-t-path P∗with

respect to x∗and hence, also with respect to x. Because of the maximality of x∗we

have P∗6=Pcontradicting the uniqueness of P. Thus we must have δ= 1 imply-

ing x∗=x−χP. In this case x1:= x+x∗and x2:= x−x∗are both feasible solutions

and we have x=1

2(x1+x2). This implies that x∗= 0 since xis an extreme point.

Hence, x=χP, which completes the proof of the lemma. ⊓⊔

As a direct consequence of the above lemma we obtain the following:

Corollary 1 For an extreme point xof (LPM) the flow xeis concentrated on

a finite set (that is, xeis discrete and supp(xe)is finite) for each arc e∈E.

Further, xe({θ}) = 1 for each arc e∈Eand each point θ∈supp(xe).

We can now summarize the results of this section in the following theorem.

Theorem 1 Any extreme point of (LPM) corresponds one-to-one to a dynamic

s-t-path. If the cost functions are given, this one-to-one correspondence preserves

also costs.

Proof From Lemma 9 we know that for any extreme point xthere exists an s-t-path P

with x=χP. Thus, it remains two show that for any dynamic s-t-path Pthe incidence

vector χPis an extreme point of (LPM).

We assume the opposite, that is, x:= χPis not an extreme point for some dynamic

s-t-path P. Then there is a signed measure x∗such that x1:= x+x∗and x2:= x−x∗

are both feasible solutions. Further, assume that x∗is maximal in the following sense:

for any ρ > 1 at least one of x+ρ·x∗and x−ρ·x∗is not feasible. Obviously x∗

is a discrete measure and hence, x1and x2are. Then by Lemma 9, there are flow-

carrying s-t-paths P1and P2with respect to x1and x2respectively. Because of the

maximality of x∗at least one of P1and P2is not equal to P. Without loss of generality

let P1be this path. We have x2= 2x−x1≤2χP−δ·χP1for some δ > 0. But this

contradicts the feasibility of x2since 2χP−δ·χP10. Hence, xis an extreme point.

The definition of the incidence vector implies that the cost of a dynamic s-t-path

and its corresponding incidence vector are equal. This establishes the theorem. ⊓⊔

4 Duality theory

Thus far, we have confined ourselves to the feasible region of (LPM) and characterizing

its extreme points. Now we turn our attention to the objective function of (LPM) and

finding its value. The value of (LPM) is the infimum of its objective function over

all feasible solutions which will be denoted by V[LPM]. Like the static shortest path

problem, (LPM) is unbounded (i.e., its value tends to −∞) if the network Gcontains a

negative dynamic cycle (i.e., a dynamic cycle with negative cost). More precisely, let P

be a dynamic s-t-path with incidence vector χPand Cbe a negative dynamic cycle

with incidence vector χC. It is not difficult to see that χP+δ·χCis a feasible solution

of (LPM) for each δ≥0 whose objective function value is cost(χP) + δcost(χC).

Therefore if cost(χC)<0 then V[LPM] can be made arbitrary negative by making δ

sufficiently large. So we give the following assumption.

Assumption 1 The network contains no negative dynamic cycle.

This assumption can be satisfied by making all costs nonnegative or all transit

times strictly positive. For the latter case, the number of arcs in any dynamic s-t-

path is bounded by a constant independent of the path. Further, the feasible region

of (LPM) becomes bounded with respect to a certain norm which makes it possible

to apply certain results from the theory of linear programming in infinite-dimensional

vector spaces. Philpott [15] assumes all transit times are strictly positive and establishes

a duality theory for (LPM) based on the paired-space methodology as adapted by

Anderson and Nash [3]. In particular, he develops a dual problem for (LPM) and

proves the absence of a duality gap. Further, he shows that the values of (LPM) and

its dual are finite and attained in each problem in the case where cost functions satisfy

a Lipschitz condition. In what follows, we give some simple examples to show that

these results do not necessarily hold for the more general case with arbitrary transit

times. Further, we present some necessary and sufficient conditions under which the

strong duality result holds between (LPM) and its dual.

4.1 Dual formulation

Before formulating a dual problem for (LPM), we consider the following small example.

Example 2 Consider the network shown in Figure 1 on page 12 with the following arc

cost functions:

cs,v(θ) = cv,s(θ) = 0 , cv,t(θ) = θ , ∀θ∈R.

The node cost functions are supposed to be zero. It is clear that the network contains no

negative dynamic cycle. Now let fbe a discrete flow concentrated on the singleton {0}

with f({0}) = 1. For each k∈Nwe define a feasible solution xkfor (LPM) as follow:

The flow fcirculates ktimes around the cycle Cinduced by sand vand then it is

sent along arc (s, v) and (v, t). This yields the following feasible solution:

(s,v)=

i=0

(f+i), xk

(v,s)= (xk

(s,v)+ 1) −(f+ (k+ 1)) , xk

(v,t)=f+ (k+ 1) .

Obviously, we have cost(xk) = −k−1. Hence, (LPM) is unbounded since cost(xk)

tends to −∞ as kgoes to ∞.

The above example shows that the absence of negative dynamic cycles does not

alone guarantee the existence of optimal solutions for (LPM). However, the problem

given in Example 2 will have an optimal solution if we restrict the feasible region of

(LPM) by considering a time window for each node. This motivates the following

assumption.

Assumption 2 For each node v∈Vthere exists a time window [av, bv]with

av>−∞ and bv<∞, within node vis permitted to visit.

Subsequently, the definition of a dynamic path (or cycle) as well as definition of a

feasible solution for (LPM) are constrained by time windows at nodes. More precisely,

for a dynamic path (or cycle) P= (e1,...,en) with arrival time αiand departure

time βifor node vi, we assume that αi, βi∈[avi, bvi] for i= 1,...,n+ 1. Further,

for any feasible solution x, y of (LPM) the measures xand yare supposed to be zero

at any point out of the time windows. So we let

ue|R\[av,bv]= 0 ∀e= (v, w)∈E .

It is naturally assumed that 0 ∈[as, bs] and Θ∈[at, bt]. To simplify notation, we

suppose that for each node v∈Vand each point in time θ∈[av, bv], the net-

work Gcontains a dynamic s-v-path with starting time 0 and time horizon θ, and a

dynamic v-t-path with starting time θand time horizon Θ. This assumption imposes

no loss of generality because the nodes and times violating this assumption do not

appear in any dynamic s-t-path and can therefore be deleted.

Having made Assumption 2, we can formulate a dual problem. For the ease of

notation, we assume that the waiting costs are zero, i.e., cv(θ) = 0 for every v∈Vand

θ∈R. We note that this assumption imposes no restriction because the waiting costs

are omitted by substituting (1) into (3) and then by integration by parts (see, e.g., [15]).

Now by the theory of linear programming in infinite-dimensional spaces (see, e.g., [3]),

we can write down a dual problem of (LPM) as follows:

min ρs−ρt+Zbs

ηs(ϑ)dϑ −Zbt

ηs(ϑ)dϑ

s.t. ρv−ρw+Zbv

ηv(ϑ)dϑ

−Zbv

θ+τe

ηw(ϑ)dϑ ≤ce(θ)∀e= (v, w)∈Eθ ∈[av, bw−τe],

ηv(θ)≤0∀v∈V, θ ∈[av, bv],

(LPM∗′

)

θs= 0 Θ= 1

cs,t =(θsin(1/θ)θ∈(0,1],

0θ= 0

ct,s =(−θsin(1/θ)θ∈(0,1],

0θ= 0

Fig. 3 Network for Example 3. The transit times are zero.

where ρv∈Rand ηv∈L∞[av, bv] for each node v∈V. The reader is referred to [15]

for a detailed discussion of the above formulation. To derive a similar formulation

as (LP∗), we consider a more general dual problem. In particular, we shall focus on

the following dual problem:

max πs(0) −πt(Θ)

s.t. πv(θ)−πw(θ+λe)≤ce(θ)∀e= (v, w)∈E, θ ∈[av, bw−τe],

πvmonotonic increasing and

right continuous on [av, bv]∀v∈V .

(LPM∗)

It is clear that (LPM∗) is a generalization of (LPM∗′

) because any feasible solu-

tion ρ, η generates one for (LPM∗) of the same objective function value by setting

πv(θ) = ρv+Zbv

ηv(ϑ)dϑ ∀v∈V, θ ∈[av, bv].

Conversely, if πis feasible for (LPM∗) in which πvis absolutely continuous on [av, bv]

for every v∈V, then ρv:= πv(bv) and ηv(θ) := ˙

π(θ) for every θ∈[av, bv], is feasible

for (LPM∗′

) and again the two solutions have the same objective function value.

Any πthat satisfies the constraints of (LPM∗) is said to be (dual) feasible, and the

value of (LPM∗), denoted by V[LPM∗], is the supremum over all feasible solutions. The

following weak duality result is easily established by integration by parts (see, e.g., [15]

for more details).

Lemma 10 (Weak duality) V[LPM]≤V[LPM∗].

It is of great interest to conjecture whether a strong duality result can be estab-

lished whereby V[LPM] = V[LPM∗] and these values are attained in each problem. It

depends on being able to construct a feasible solution xfor (LPM) and a feasible solu-

tion πfor (LPM∗) for which V[LPM, x] = V[LPM∗, π]. The following three examples

show that in general strong duality may not hold between (LPM) and (LPM∗) if even

Assumptions 1 and 2 are fulfilled.

Example 3 We consider the network shown in Fig. 3. The arc cost functions are shown

on the arcs and the node cost functions are zero. Moreover, the transit times are zero

and a time window [0,1] is associated to each node. Let Θ:= 1 be the time horizon

and fbe a discrete flow concentrated on the singleton {0}with f({0}) = 1

For each k∈Nwe define a feasible solution xkfor (LPM) as follow:

(s,v)=

i=1 „f−2

(4i−1)π«, xk

(v,s)=

k−1

i=1 „f−2

(4i+ 1)π«.

Actually the feasible solution xkis the incidence vector of a dynamic s-t-path Pk

derived as follows: We start from node sat time 0 and go from sto tand back

from tto sfor ktimes. In addition, we wait for a certain time at nodes sand t

whenever we arrive at these nodes. At the end of kth circulation we wait at node t

until time 1. More precisely, we have the dynamic s-t-path Pk= (e1,...,e2k−1) with

arrival times α1,...,α2kand departure times β1,...,β2k, where

e2i−1= (v2i−1, v2i) = (s, t) for i= 1,...,k ,

e2i= (v2i, v2i+1) = (t, s) for i= 1,...,k−1,

α1= 0, α2i−1=2

(4k−(4i−5))πfor i= 2,...,k ,

α2i=2

(4k−(4i−3))πfor i= 1,...,k ,

β2i−1=2

(4k−(4i−3))πfor i= 1,...,k ,

β2k= 1, β2i=2

(4k−(4i−5))πfor i= 1,...,k−1.

We observe that cost(xk) = −Pk

i=1 2

(2i+3)π. So cost(xk) tends to −∞ as kgoes

to ∞, and hence V[LPM] = −∞.

The following two examples deal with the situation where the value of (LPM) is

finite, but no feasible solution attain this value. Notice that this is not the case for

static shortest path problem as it is well known that if the value of (LP) is finite, then

this value is attained by some feasible solution.

Example 4 We consider Example 3, but now with the following arc cost functions:

ct,s(θ) = (θ2sin(1/θ)θ∈(0,1] ,

0θ= 0 , ct,s(θ) = (−θ2sin(1/θ)θ∈(0,1] ,

0θ= 0 ,

Then, it holds that

V[LPM] = lim

k→∞ cost`xk´=−

∞

i=0 „2

(2i+ 3)π«2

<∞

where xkis a feasible solution of (LPM) as defined in Example 3. Here the value

of (LPM) is finite, but it is not attained by any feasible solution.

Example 5 We consider a simple network containing of only one arc e= (s, t) which

joins source sto sink t. Let Θ:= 1 be the time horizon and cebe the cost function

given by

ce(θ) = (1−θ θ < 1 ,

1θ≥1 ,

There is no waiting costs at the nodes and transit time of eis assumed to be zero. Here

we have V[LPM] = 1, but it is not attained by any feasible solution.

θs= 0 Θ= 1

√20

−10

Fig. 4 Network for Example 6. The transit times are shown on the arcs.

The previous two examples show that Assumptions 1 and 2 do not guarantee in

general the existence of an optimal solution for (LPM), even for the case that the cost

functions satisfy a Lipschitz condition or are piecewise analytic. Actually the problem

in Example 4 is because of the fact that the cost functions have a infinite number of

local optimum and in Example 5 due to the fact that the cost functions do not attain

its minimum. So it is natural to restrict the cost functions to those that have a finite

number of local minimum and attain their minimum on a closed interval.

Assumption 3 For each arc e= (v, w)∈E, the cost function ceis both piecewise

analytic and lower semi-continuous on [av, bv−τe].

Notice that a function f: [a, b]→Ris said to piecewise analytic if there exists a

partition {θ0, θ1,...,θm}of [a, b] (i.e., a=θ0< θ1< . . . < θm=b) , ǫ > 0, and gk

analytic on (θk1−ǫ, θk+ǫ) with gk(t) = f(t) for θ∈[θk1, θk), k= 1, . . . , m. Hence, a

piecewise analytic function can be discontinuous at a finite number of points and such

a function may not attaint its minimum over a closed interval. That is why we require

that the costs functions are both piecewise analytic and lower semi-continuous. It is

well known that a lower semi continuous function attains its minimum on a compact

set. We shall use this fact later on to prove the existence of dynamic shortest paths.

The following example shows that not only the structure of cost functions, but also

of transit times are important.

Example 6 Consider the network shown in 4 with cost functions as given below:

cs,t(θ) = 1 −θ cs,v(θ) = cs,w(θ) = cv,s(θ) = cw,s(θ) = 0 ∀θ∈R.

cs(θ) = cv(θ) = cw(θ) = ct(θ) = 1 ∀θ∈R.

We associate a time window [−1,1] with each node and let Θ:= 1 be the time

horizon. We observe that V[LPM] = 0, but no feasible solution attain this value. This

is because of the fact that

sup

−1<S<1{S=m√2−n|m, n ∈N∪{0}} = 0 ,

but this value is not reached by any finite nand m.

In Example 6 the value of (LPM) is finite, but the problem has no optimal solution.

The reason here is that greatest common factor of a set of numbers including irrational

numbers does not exist. This is not the case for rational numbers. Hence, we give the

following assumption.

Assumption 4 The transit times (τe)e∈Eas well as the time horizon Θare all

rational.

So far, we have observed that strong duality does not necessarily hold if at least

one of the Assumptions 1, 2, 3, and 4 is not fulfilled. Throughout the rest of the paper

we suppose that these assumptions hold and prove a strong duality result.

4.2 Strong Duality

The basic idea for establishing strong duality between (LPM) and (LPM∗) goes along

the same lines as in the static case. Therefore, we first show that the network Gcontains

a dynamic shortest s-v-path with starting time 0 for each node v∈Vand for each

time horizon θ∈[av, bv].

Let Pa dynamic s-t-path. By Theorem 1 the incidence vector χPof Pis an

extreme point of (LPM). Note that, for each e∈E, the set supp(χP

e) is finite and,

for each θ∈supp(χP

e), it holds that χP

e(θ) = 1. Note that in a dynamic path no

node is revisited at the same point in time. Hence, χP

eis uniquely defined by supp(χP

and is therefore interpretable as a (finite) vector χP

e∈R|supp(χP

e)|. The entries of

the vector χP

eare exactly the times when we leave the tail of ealong the path P.

In the following χP

edenotes also this vector and we assume that entries are ordered

monotonically increasing.

In order to define locally shortest paths we define, for all ǫ > 0, the ǫ-neighborhood

of an dynamic s-t-path Pas the set of all dynamic s-t-paths P′satisfying:

|supp(χP

e)|=|supp(χP′

e)|and ||χP

e−χP′

e||∞< ǫ ∀e∈E .

Then, Pis a locally shortest path if there exists an ǫ > 0 such that cost(P)≤cost(P′)

for all paths P′in the ǫ-neighborhood of P. In the following, we show that the set of

locally shortest paths are finite and hence a dynamic shortest always exists under the

assumptions 1–4. For this, we give an alternative characterization of locally shortest

paths and start with the definition of nonstop paths.

Let P= (e1,...,en) be a dynamic s-t-path with waiting times (λ1,...,λn+1). A

subsequence P′= (ek,...,eℓ) of consecutive arcs in Pis called a nonstop subpath

of Pif λi= 0 for i=k+ 1,...,ℓ. If, in addition, λk>0 and λℓ+1 >0 holds then the

nonstop subpath P′is called maximal. In particular, P′is not maximal if P′starts

at sat time 0 or ends at tat time Θ.

For any ǫ∈[−λk, λℓ+1] the arc sequence (e1,...,en) with starting time 0 and

waiting times

(λ1,...,λk−1, λk+ǫ, 0,...,0

|{z }

, λℓ+1 −ǫ, λℓ+2,...,λn+1)

ℓ−ktimes

is a dynamic s-t-path denoted by P|P′(ǫ). Let βkand αℓ+1 be the departure time

at vkand the arrival time at vℓ+1 in P, respectively, and τP′:= Pℓ

i=kτeibe the

transit time of P′. Then, P|P′(ǫ) is obtained by leaving node vkat time βk+ǫinstead

of time βkand arriving at node vℓ+1 at time βk+ǫ+τP′=αℓ+1 +ǫinstead of

time αℓ+1. Roughly speaking, P|P′(ǫ) is obtained by shifting P′within path Pby ǫ

time units.

We observe that for a given ǫ∈[−λk, λℓ+1], the dynamic s-t-path P|P′(ǫ) is con-

tained in the |ǫ|-neighborhood of P. We are now interested to compute the difference in

costs between Pand P|P′(ǫ). To do this, we define a cost function cP′: [avk, bvk]→R

where [avk, bvk] is the time window of vkby

cP′(θ) :=

ℓ

i=k

cei“θ+

i−1

j=k

τej”.(14)

Thus, for a point in time θthe value cP′(θ) determines the cost for traveling along P′

without waiting and with starting time θ. Hence, the cost for moving from Pto P|P′(θ)

is given by cP′(βk+ǫ)−cP′(βk). The following lemma gives a necessary condition for

locally shortest paths.

Lemma 11 Let P= (e1,...,en)be a locally dynamic shortest s-t-path with depar-

ture times β1,...,βn+1. Then for each maximal nonstop subpath P′= (ek,...,eℓ)

of Pthe cost function cP′is locally minimized at the point βk.

Proof Follows from the above discussion. ⊓⊔

Let ¯

Ploc be the set of dynamic s-t-paths Pwhere each maximal nonstop subpath P′

starting at θlocally minimizes cP′, i.e., cP′has a local minimum at θ. In addition,

we assume that cP′is not constant on any open neighborhood containing θ. Further,

we say that two s-t-paths P1and P2are equivalent if they differ only in the starting

time θ1and θ2, respectively, of one common nonstop subpath P′and cP′is constant

over [θ1, θ2]. Note that in this case P1and P2have cost. Then, for all locally shortest

paths, an equivalent path is contained in ¯

Ploc. Hence, the following lemma shows that

the set of locally shortest s-t-paths is in essence finite.

Lemma 12 The set ¯

Ploc is finite.

Proof Let P∈¯

Ploc be a dynamic s-t-path and P′be a nonstop subpath of P. Note

that P′contains no dynamic cycles. First we show that there are only finitely many

possible arc sequences for the nonstop subpath P′. Let Imax := maxv∈V{bv−av}be

the maximum length of time windows [av, bv] over all nodes v∈V(see Assumption 2)

and let ˆ

τbe the greatest common factor of transit times, i.e.,

τ:= min{S > 0|Sis a finite sum of elements of the form + τeor + τe}.

Note that ˆ

τexists and is greater than 0 because of Assumption 4. Since P′contains

no dynamic cycle it visits any node at most ⌈I

ˆτ⌉times. Consequently, the number of

possible arc sequences for P′is bounded by a constant. This implies that cP′is the

finite sum of piecewise analytic functions. Hence, cP′is also piecewise analytic.

In the the following let P′be a maximal nonstop subpath of P. Because of As-

sumption 3 and equation (14), cP′is piecewise analytic and lower semi-continuous.

Hence, cP′has only a finite number of local minima (at points where c′

Pis not con-

stant) and attains all of them by some real value. Therefore there are only finite number

of possible start times for P′. This implies that the number of maximal nonstop subpath

with the same arc sequence as P′is bounded by a constant. Otherwise Pcontains a

dynamic cycle. Therefore the length of the arc sequence of Pis bounded by a constant.

Since Pis chosen arbitrary at the beginning of this proof, any arc sequence of a

path in ¯

Ploc is bounded by the same constant. Hence, the cardinality of ¯

Ploc is finite.

⊓⊔

The next lemma shows that ¯

Ploc contains the dynamic shortest s-t-path.

Lemma 13 Let Pbe a dynamic s-t-path. Then there exists an s-t-path ¯

P∈¯

Ploc

with cost(¯

P)≤cost(P).

Proof If P∈¯

Ploc, then we are done. So we consider the case where Pis not in ¯

Ploc.

In this case we iteratively apply the following procedure to construct a dynamic s-t-

path ¯

P∈¯

Ploc:

(i) Let P′= (vk,...,vℓ) be a maximal nonstop subpath of Psuch that the cost

function cP′does not have a local minimum (or is constant) at βk. Notice that

such a path path exists because of the definition of ¯

Ploc and the fact that Pis

not in ¯

Ploc. Further, choose P′such that it contains a minimal number of arcs.

(ii) Since the functions ce,e∈E, are lower semi-continuous by Assumption 3, cP′is

also lower semi-continuous. Thus, cP′takes its minimum over [βk−λk, βk+λℓ]

at some point θ. If there are several local minima choose θmaximal.

(iii) Let P|P′(βk−θ) be the dynamic s-t-path obtained from Pby shifting the nonstop

subpath P′by βk−θtime units. Since P|P′(θ) may contain dynamic cycles, we

delete all dynamic cycles in P|P′(θ).

(iv) Set P:= P|P′(θ). If Pis not in ¯

Ploc, then go to (i).

Notice that the number of arcs in P′is bounded by |E(P)|and increases after at

most |E(P)|iterations. Hence, the above procedure terminates after a finite number of

iterations and the resulting dynamic s-t-path Pis contained in ¯

Ploc. Further, in each

iteration the cost of Pdoes not increase which proves this lemma. ⊓⊔

Lemmas 12 and 13 show that a dynamic shortest s-t-path exists. More precisely,

a dynamic shortest s-t-path is one in ¯

Ploc with minimal cost. Further, Lemma 12 as

well as Lemma 13 remain valid if the sink tis replaced by any node v∈Vand if the

time horizon Θis replaced by any point in time θ∈[av, bv]. Furthermore, we obtain

the following result.

Lemma 14 For each node v∈Vand each point in time θ∈[av, bv], let dv(θ)

be the cost of a dynamic shortest s-v-path with starting time 0and time horizon

θ. Then, for each node v∈V, the label dv(θ)exists for all θand the function

dv: [av, bv]→Ris piecewise analytic and monotonic decreasing.

Proof As discused above the existence of dv(θ) follows from 12 and 13. Furthermore,

since there are no waiting costs the function dvis monotonic decreasing. Hence, it thus

remains to show that dvis piecewise analytic on [av, bv] for each v∈V.

In the following we fix a node v∈V. Similar to the definition of ¯

Ploc before

Lemma 12 define ¯

Ploc(θ) as the set of dynamic s-v-paths Pwith starting time 0 and

with time horizon θwhere each maximal nonstop subpath P′of Pstarting at ϑlocally

minimizes cP′. In addition, we assume that cP′is not constant on any open neigh-

borhood containing ϑ. Then Pv:= ∪θ∈[av,bv]¯

Ploc(θ) contains (nearly) all dynamic

shortest s-v-paths for any feasible time horizon θ.

Next we define an equivalence relation ∼on the set of all dynamic s-v-paths.

Let P= (e1,...,enP) and ¯

P= (¯

e1,...,¯

en¯

P) be two dynamic s-v-paths with waiting

times (λ1,...λnP) and (¯

λ1,...¯

λn¯

P). Then ∼is defined by

P∼¯

P:⇐⇒ (e1,...,enP) = (¯

e1,...,¯

en¯

P),

∃k∈ {1,...,nP+ 1}:λi=¯

λi∀i < k ,

λi,¯

λi>0i=k ,

λi=¯

λi= 0 ∀i > k .

Hence, Pand ¯

Pare equivalent if they differ only in the last positive waiting time. For

an equivalence class [P] we denote by P1the path consisting of the first k−1 arcs of P

without waiting at the end and by P2the path consisting of the last np−k+ 1 arcs

of Pwithout waiting at the beginning. Note that P1and P2can be the empty path.

Further, P1and P2are well-defined in the sense that they are coincide for any member

of [P]. On the other hand, any dynamic path in [P] is obtained by concatenating P1

and P2and introducing some positive waiting between them. (If Pis a nonstop path

without waiting at all we put it in the equivalence class P1=∅and P2=P.)

Consider the quotient set Pv/∼and an equivalence class [P]∈ Pv/∼. Then

each maximal nonstop subpath P′and also the last nonstop subpath of Plocally

minimizes cP′. Further, P2is a nonstop subpath itself. Hence, along the same lines as

in the proof of Lemma 12 we obtain that there exists only a finite number of possibilities

for P1and P2. Hence, Pv/∼is a finite set. In order to get an expression for dvwe

define a cost function c[P]: [av, bv]→Rby

c[P](θ) := cost(P1) + (cP2(θ−τP2) if θ > τP1+τP2,

∞if θ≤τP1+τP2,

Then, for every P∈ Pvwe have cost(P) = c[P](θ) where θis the time horizon of P.

Thus we obtain dv= min{c[P]}. Therefore dvis piecewise analytic since it is the

minimum of a finite number of piecewise analytic functions. ⊓⊔

From the above discussion we obtain the main result of this section.

Theorem 2 (Strong duality) There exist an extreme point xfor (LPM) and a

piecewise analytic solution πfor (LPM∗)so that

V[LPM, x] = V[LPM∗, π].

Proof Following Lemma 14, we define for each v∈Vand each θ∈[av, bv] the shortest

label dv(θ) to be the cost of a dynamic shortest s-v-path with starting time 0 and

time horizon θ. Obviously, we have ds(0) = 0 since the network contains no negative

dynamic cycle due to Assumption 1. In the following we show that the shortest path

labels define a dual feasible solution whose value equals to the cost of some feasible

solution for (LPM).

Let πv(θ) = −dv(θ) for any v∈Vand every θ∈[av, bv]. It follows from Lemma 14

that πis a piecewise analytic solution for (LPM∗) Now let Pbe a dynamic shortest

s-t-path with starting time 0 and time horizon Θand χPdenote its corresponding

incidence vector. We know from Theorem 1 that χPis an extreme point of (LPM)

whose value is equal to the cost of P. Summarizing, we can conclude that

V[LPM, χP] = cost(P) = dt(Θ) = −ds(0) + dt(Θ) = πs(0) −πt(Θ) = V[LPM∗, π].

It now follows from Lemma 10 that xis optimal for (LPM) and πis optimal for (LPM∗).

This yields the desired result. ⊓⊔

References

1. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Theory, Algorithms, and

Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.

2. R. K. Ahuja, J. B. Orlin, S. Pallottino, and M. G. Scutell`a. Dynamic shortest paths

minimizing travel times and costs. Networks, 41:197–205, 2003.

3. E. J. Anderson and P. Nash. Linear Programming in Infinite-Dimensional Spaces. Wiley,

New York, 1987.

4. E. J. Anderson, P. Nash, and A. B. Philpott. A class of continuous network flow problems.

Mathematics of Operations Research, 7:501–514, 1982.

5. X. Cai, T. Kloks, and C. K. Wong. Time-varying shortest path problems with constraints.

Networks, 27:141–149, 1997.

6. L. Chabini. Discrete dynamic shortest path problems in transportation applications: Com-

plexity and algorithms with optimal run time. Transportation Research Record, 1998:170–

175, 1645.

7. L. Cooke and E. Halsey. The shortest route through a network with time-dependent

internodal transit times. Journal of Mathematical Analysis and Applications, 14:492–498,

1966.

8. L. K. Fleischer and ´

E. Tardos. Efficient continuous-time dynamic network flow algorithms.

Operations Research Letters, 23:71–80, 1998.

9. J. F. Kingman and S. J. Taylor. Introduction to Measure and Probability. Combrodge

University Press, 1966.

10. E. Nasrabadi. Dynamic Flows in Time-varying Networks. PhD thesis, Technische Uni-

versit¨at Berlin, Berlin, 2009.

11. A. Orda and R. Rom. Shortest-path and minimum-delay algorithms in networks with

time-dependent edge length. Journal of the ACM, 37:607–625, 1990.

12. A. Orda and R. Rom. Minimum weight paths in time-dependent networks. Networks,

21:295–320, 1991.

13. S. Pallottino and M. G. Scutell`a. Shortest path algorithms in transportation models:

Classical and innovative aspects. In P. Marcotte and S. Nguyen, editors, Equilibrium and

advanced transportation modelling, pages 245–281. Kluwer, Norwell, MA, 1998.

14. A. B. Philpott. Algorithms For Continuous Network Flow Problems. PhD thesis, Univer-

sity of Cambridge, UK, 1982.

15. A. B. Philpott. Continuous-time shortest path problems and linear programming. SIAM

Journal on Control and Optimization, 32:538–552, 1994.

16. A. B. Philpott and A. I. Mees. Continuous-time shortest path problems with stopping

and starting costs. Applied Mathematics Letters, 5:63–66, 1992.

17. A. B. Philpott and A. I. Mees. A finite-time algorithm for shortest path problems with

time-varying costs. Applied Mathematics Letters, 5:91–94, 1993.

A Preliminaries on measure theory

In this appendix we briefly present some basic definitions and notation that are used frequently

throughout the paper. For a detailed treatment we refer to, e.g., [9].

Aσ-algebra on the real line Ris a nonempty collection of subsets of Rthat is closed under

countable unions and complements. The smallest σ-algebra on Rcontaining all open sets (or,

equivalently, closed sets) is called the Borel σ-algebra. The elements of the Borel algebra are

called measurable sets or Borel sets. Let Bdenote the collection of all Borel sets on R. A

function µ:B → R≥0is called a Borel measure on Rif

1. µ(B)≥0 for any B∈ B and µ(∅) = 0;

2. if {Bi}i∈Nis a countable collection of pairwise disjoint sets in B, then

µ`∪i∈NBi´=X

i∈N

µ(Bi).

A Borel measure µon Ris called finite if µ(R)<∞. Measures are by definition nonnegative,

i.e., a nonnegative real number is assigned to each measurable set. However, it is sometimes

convenient that also negative values can be assigned to some measurable sets. A measure which

can take both positive and negative values is called a signed measure. The space of finite signed

Borel measures becomes a vector space under the standard addition and scalar multiplication

operations. In particular, for any two finite signed Borel measures µ1and µ2and any real

value λ, the addition µ1+µ2and scalar multiplication λ·µ1are defined as

(µ1+µ2)(B) = µ1(B) + µ2(B)∀B∈ B ,

(λ·µ1)(B) = λ·µ1(B)∀B∈ B .

Let µ1and µ2be two signed Borel measures. We write µ1=µ2(µ1≤µ2) if µ1(B) = µ2(B)

(µ1(B)≤µ2(B)) for each B∈ B. Moreover, we write µ1≥0 if µ1(B)≥0 for each Borel set B

and µ0 if µ(B)<0 for some Borel set B. For a measurable set Aand a Borel measure µ,

the restriction µ|Aof µto the set Ais a Borel measure defined by µ|A(B) := µ(B∩A) for

each B∈ B. If µ|A= 0, then Ais called a strict µ-null. This implies µ(B) = 0 for each Borel

set B⊆A. A Borel set Bfor which µ(B) = 0 is called a µ-null set. A (signed) measure µis

called zero if µ(B) = 0 for each Borel set B. Otherwise µis called nonzero.

A function F:R→Ris called measurable if the preimage of each measurable set is

measurable, that is, F−1(B) := {θ∈R|F(θ)∈B}is a measurable set for every Borel set B.

It is well known that if Fis measurable, then the integral of Fon a measurable set Bwith

respect to a Borel measure µexists and is denoted by RBF dµ. We refer to, e.g., [9] for more

details.

A function F:R→Ris called a distribution function if it is of bounded variation and

right-continuous, and moreover limθ→−∞ F(θ) = 0. Notice that the limit exists since Fis

of bounded variation. For every finite signed Borel measure µ, there is a unique distribution

function Fsatisfying F(b)−F(a) = µ((a, b]) for all a, b ∈Rwith a≤b. In fact Fis given by

the formula F(θ) = µ((−∞, θ]).

Given a measure µon R, the support of µis defined to be the set of all points in Rwith

a neighborhood of positive measure, that is,

supp(µ) := {θ∈R:µ(U)>0 for every open neighborhood Uof θ}.

A point θ∈Ris called an atom of µif µ({θ})>0. Obviously if µis finite, the set of atoms

of µis countable. We define the discrete part µdand continuous part µcof a finite measure µ

µd(B) := X

atoms θ∈B

µ`{θ}´and µc(B) := µ(B)−µd(B)

for every measurable set B. The measure µis called a discrete (continuous2) if its continuous

(discrete) part is zero. In fact, a finite Borel measure is continuous (discrete) if and only if

its corresponding distribution function is continuous (a jump function) (see, e.g., Section 9.3

in [9]). Moreover, the decomposition µ=µc+µdof a finite Borel measure µa into a sum of

a discrete and a continuous measure is unique.

Two Borel measures µ1and µ2are called singular if there exist two disjoint measurable

sets Aand Bwhose union is Rsuch that µ1is zero on all measurable subsets of Bwhile µ2

is zero on all measurable subsets of A, i.e., µ1(B) = 0 and µ2(A) = 0. Moreover, µ1is said to

be absolutely continuous with respect to µ2if µ1(A) = 0 for every measurable set Afor which

µ2(A) = 0.

The following theorem shows that any signed measure can be expresses as the difference

of two singular (positive) measures.

Theorem 3 (Jordan Decomposition) Every signed measure µcan be expressed as a dif-

ference of two nonnegative measures µ+and µ−such that µ+and µ−are singular and at least

one of which is finite. Moreover if µ=µ1−µ2, then µ+≤µ1and µ−≤µ2. The measures µ+

and µ−are called the positive and negative part of µ, respectively. The pair (µ+, µ−)is called

the Jordan decomposition (or sometimes Hahn–Jordan decomposition) of µ.

2A continuous measure is also called nonatomic in textbooks on measure theory.

Following this theorem, let µbe a signed measure with the Jordan decomposition (µ+, µ−).

The absolute value of µis then defined by |µ|:= µ1+µ2. Theorem 3 helps us to define the

minimum of two measures. Let µ1and µ2be two nonnegative measures on R. The minimum

of µ1and µ2is a nonnegative measure defined by min{µ1, µ2}:= µ1−µ+=µ2−µ−, where

(µ+, µ−) is the Jordan decomposition of the signed measure µ1−µ2. It is not hard to see that

min{µ1, µ2}is positive if µ1and µ2are positive and not singular.

B Proofs of technical lemmas

In this Appendix, we provide the proofs of Lemmas 1, 4 and, 7 that were omitted from the

main text. We start with the proof of Lemma 4.

Proof (Proof of Lemma 4) The following algorithm computes ¯µ1,...,¯µn:

1. Set ν1:= µ.

2. For i:= 1 to ndo the following:

(a) Let (z+

i, z−

i) be the Jordan decomposition of the signed measure µi−νi.

(b) Set ¯µi:= µi−z+

i=νi−z−

iand νi+1 := νi−¯µi=z−

In order to complete the prove we have to show that µis reduced to zero during the algorithm,

i.e., νn+1 = 0. We assume the opposite and seek a contradiction. Let B= supp(νn+1). It

follows from the computations of the algorithm that

i=1

µi=

i=1

(νi+z+

i−z−

i) = µ+z+

1−z−

i=2

(z−

i−1+z+

i−z−

=µ−νn+1 +

i=1

Since νn+1 is mutually singular to z+

ifor all i= 1,...,n, we get (Pn

i=1 µi)(B)< µ(B), which

is a contradiction. ⊓⊔

The proof of Lemma 7 is based on the following result.

Lemma 15 Let µbe a finite discrete measure on R,fbe a positive real number, and θbe

a real number such that: f≤µ([θ, ∞)). Then for every ρ∈[0,1) there exists a (discrete)

measure ν≤µwith finite support supp(ν)⊂[θ, ∞]such that:

ρ·f=ν(R),

f−µ([θ, ϑ]) ≥ν((ϑ, ∞)) ∀ϑ∈[θ, max(supp(ν)) ).

Proof Since f≤µ([θ, ∞)), there is some point in time θmax ∈R, such that:

√ρ·f≤µ([θ, θmax]) .

In the following let θmax be the infimum over all such times. Then, θmax is in fact a minimum,

because of the right continuity of distribution functions. Therefore:

0≤√ρ·f−µ([θ, θmax))

| {z }

=: a

≤µ({θmax}).

Since µis discrete there exist a finite set Ω⊂[θ, θmax) such that:

√ρ·µ([θ, θmax)) ≤µ(Ω).

We define the discrete measure νas follows:

ν({ϑ}) := 8

µ({ϑ}) for ϑ∈Ω

afor ϑ=θmax

0 otherwise

Thus by definition we know that supp(ν)⊂[θ, ∞]. Further, we have

ν(R) = a+µ(Ω)≥µ({θmax}) + √ρ·µ([θ, θmax)) ≥√ρ·µ([θ, θmax]) ≥ρ·f .

For proving the second property let ϑ∈[θ, θmax). We have:

f−µ([θ, ϑ]) = f−µ([θ, θmax)) + µ((ϑ, θmax))

≥a+µ((ϑ, θmax))

≥ν((ϑ, ∞)) .

Scaling of νsuch that equality is reached in the first property completes this proof. ⊓⊔

Proof (Proof of Lemma 7) The idea is to apply Lemma 15 to f:= ν1({θ}) and µ2. Therefore

we have to show f≤µ2([θ, ∞)). Since γ(R) = 0 and Fγ≥0 we know:

γ([θ, ∞)) = γ(R)−γ((−∞, θ)) ≤0

Thus, from µ2+γ≥µ1we obtain:

f≤µ1([θ, ∞)) ≤γ([θ, ∞)) + µ2([θ, ∞)) ≤µ2([θ, ∞))

Hence, Lemma 15 ensures the existence of a discrete measure ν2≤µ2with finite support

in [θ, ∞) such that:

ρ·f=ν2(R),

f−µ2([θ, ϑ]) ≥ν2((ϑ, ∞)) ,∀ϑ∈[θ, max(supp(ν2))) .

In order two satisfy the first statement we define η:= ρ·ν1−ν2. Then from the first equation

we get η(R) = ν2(R)−ρ·f= 0. Further, the distribution function Fηis equal to 0 outside

of [θ, max(supp(ν2)). For ϑ∈[θ, max(supp(ν2)) we obtain:

Fη(ϑ) = ρ·f−ν2((−∞, ϑ]) = ν2(R)−ν2((−∞, ϑ]) = ν2((ϑ, ∞))

≤f−µ2([θ, ϑ]) ≤µ1([θ, ϑ]) −µ2([θ, ϑ]) ≤γ([θ, ϑ]) ≤Fγ(ϑ).

This completes the proof.

It remains to prove Lemma 1. To this end, we first give some lemmas.

Lemma 16 Suppose that µ1, µ2≥0are two finite continuous Borel measures on Rwith

distribution functions F1and F2, respectively. Let F1≥F2on some interval I:= (−∞, θ],

θ∈R, and M:= {ϑ∈I|F1(ϑ) = F2(ϑ)}be the set of points in Iwhere the two distribution

functions are equal. Then µ1(M) = µ2(M).

Proof For a given ǫ > 0, we let M<ǫ := {ϑ∈(−∞, θ)|F1(ϑ)−F2(ϑ)< ǫ}be the set of points

in (−∞, θ) where two distribution functions differ by less than ǫ. It is clear that M<ǫ is an open

set, so we can express it as a countable union of pairwise disjoint open intervals, unique up to

order, as Mǫ=∪i∈J(ai, bi), where Jis a countable set of indices. Note that, for each i∈J,

(ai, bi) is maximal in the following sense: There exists no open interval (a′, b′)⊆Mǫstrictly

containing (ai, bi). We also know that the distribution functions F1and F2are continuous

since µ1and µ2are continuous measures. Hence we can conclude that F1(ai)−F2(ai) = ǫif

ai6=−∞, and F1(bi)−F2(bi) = ǫif bi6=θ. Then it follows that

µ1(Mǫ)−µ2(Mǫ) = X

i∈J

µ1((ai, bi)) −µ2((ai, bi)) ≤ǫ .

Now we let tend ǫto 0 and get µ1(M) = µ2(M). ⊓⊔

The next corollary generalizes Lemma 16 from µ1(M) = µ2(M) to µ1|M=µ2|M, even

for the more general case when the assumption of F1≥F2is not met.

Corollary 2 Let µ1, µ2≥0be two finite continuous Borel measures on Rwith distribution

functions F1and F2, respectively. Moreover, let M:= {θ∈R|F1(θ) = F2(θ)}be the set of

points where two distribution functions are equal. Then µ1|M=µ2|M.

Proof We first assume that F1≥F2. Then Lemma 16 implies

µ1|M((−∞, θ]) = µ1|(−∞,θ](M) = µ2|(−∞,θ](M) = µ2|M((−∞, θ]) ∀θ∈R.

It follows from this relation that the distribution functions with respect to µ1|Mand µ2|M

coincide on R. This implies µ1|M=µ2|M.

For the general case, we define Fmax :R→Rby Fmax(θ) := max{F1(θ), F2(θ)}. It is

clear that Fmax is monotonic increasing and continuous on the right. So it is the distribution

function of some measure µmax. Applying the previous result to Fmax and F1and also to Fmax

and F2, we get

µ1|M=µmax|M=µ2|M.

⊓⊔

Corollary 3 Let µbe a finite signed Borel measure on Rwith distribution function Fand

Q⊂Rbe a countable set of real numbers. If µis continuous, then M:= {θ|F(θ)∈Q}is a

strict µ-null set, i.e., µ|M= 0.

Proof For each q∈Qdefine Mq:= {θ|F(θ) = Q}. Then Mis the disjoint (countable)

union of the Mq’s. Hence, in order to establish the lemma it is enough to show µ|Mq= 0 for

each q∈Q.

Let q∈Qbe fixed and assume, without loss of generality, that q≥0. Further, let µ+

and µ−be the positive and negative part of µwith distribution functions F+and F−, re-

spectively. Since µis continuous, a:= min{θ|F+(θ)≥q}is well-defined and F+(a) = q. We

define ¯

F:R→R+by

θ7→ (0 if θ≤a ,

F+(θ)−qif θ > a .

Then ¯

Fis the distribution function of the restricted measure ¯µ:= µ+|[a,∞)and we have

Mq={θ|¯

F(θ) = F−(θ)}. From Corollary 2 and the fact that Mq∩(−∞, a) = ∅, it follows

µ+|Mq= ¯µ|Mq=µ−|Mq, and as a direct consequence µ|Mq= 0.

We are now in a position to prove Lemma 1.

Proof (Proof of Lemma 1) Let µdbe the discrete part of µ. Then there exists a countable

set Qof real numbers such that the distribution function of µdonly takes its values in Q.

Let Fcbe the distribution function of µcand define ¯

M:= {θ|Fc(θ)∈Q}. It now follows

from Corollary 3 that µc|¯

M= 0 since Qis countable. In order to prove the lemma, it suffices

to show R\M⊆¯

M∪supp(xd). Let θ∈R\Mbe fixed. Due to the definition of distribution

functions, we have

µ({θ}) = F(θ)−lim

ϑ→θ−F(ϑ).

Then exactly one of the following cases occurs:

1. µ({θ}) = 0 and F(θ) = 0,

2. µ({θ})>0.

In the first case we have θ∈¯

Sand in the second case θ∈suppxd. This completes the proof

of the lemma.