Properties of Link and Path Travel Times

Properties of link and path travel times

Malachy Carey

School of Management and Economics

Queen's University, Belfast, Northern Ireland BT7 1NN.

E-mail:

Web page:

15 September 2004

Many of the results in this talk are now available in:

Carey, M. "Link travel times I: desirable properties”, Networks and Spatial Economics 4(3), 257-268.

Carey, M. “Link travel times II: properties derived from traffic-flow models”, Networks and Spatial Economics 4(4), 379-402.

I would like to thank the UK Engineering and Physical Science Research Council (EPSRC) for supporting this research through their grant number GR/R/70101.

1. Properties of link/ path travel times

Travel times - key variables in predicting traffic behaviour on networks (e.g. for UE, SO, etc) when flows and travel times vary over time.

Many different models for DTA, hence important to consider:

-what are minimum accepted/ desirable properties of predicted time-varying travel times?

-are there relationships between these properties?

We here consider:

Existence, uniqueness & continuity

discuss here for travel times satisfying 4, denoted a(t).

FIFO, well known, caused most problems in literature.
Strict (or partial) causality.
Time-flow consistency.

3 & 4 mentioned in literature, but not by names given here.

1.1. Assumptions & conclusions

We assume

-conservation of flow is enforced, i.e. x(t) = U(t) V(t).

-& for simplicity, assume a single traffic of type.

Initially make no assumptions about how travel times are modelled / obtained,

-e.g. may be explicit travel-time function, a traffic flow model, a microsimulation model, etc.

-Stronger results can be obtained for particular classes of travel-time models.

We find:

-The DTA literature sometimes assumes/ implies that some of these properties are necessary or sufficient for others, when they are not.

-In general, no one of the various properties is necessary or sufficient for the others.

2. Obtaining travel times from cumulative inflows & outflows

For a link, or link segment, cell or path:

u(t) & v(s) =inflow & outflow (veh./unit time) at time t
U(t) & V(s) = cumulative inflows & outflows to time t
(t) = travel time for traffic entering at time t.

Computing (t), if U(t) & V(t) are everywhere increasing

(i.e. +u(t), v(t) >0).

Assume U(t) & V(s) obtained by any method.

If traffic flow is conserved & satisfies FIFO,

then inflows up to time t (i.e. U(t)) must all exit by exactly time t+(t), i.e.

U(t) = V(t+(t)) or (t) = (1)

Use this to compute (t) from U(t) & V(s) curves.

In Fig 1, (t) is horizontal distance between U(t) & V(s).

When FIFO & flow conservation hold,

eq. (1) ensures U(t), V(s) & (t) are consistent with each other.

Hence can call (1) a “time-flow consistency” condition.

In some models, (1) used to obtain (t) from U(t) & V(s),

in other models, (1) used to obtain V(s) from U(t) & (t).

Let a(t) denote travel times (t) computed from cumulative flows, as in (1) and Fig. 1..

[A footnote:

Taking derivative of (1) and rearranging,

v(t+(t)) = u(t)/ (1+'(t)). ()

In the DTA, () is sometimes referred to as "flow propagation equation", since “propagates” outflow from given inflows and travel times.

Hence (1) could also be called a flow propagation eq.]

Fig. 1 (a). Computing a(t) if U(t) & V(t) are everywhere increasing.

Fig. 1(b). Computing a(t) if U(t) is constant (u(t) =0) over some range.

Fig. 1(c). Computing a(t) if V(s) is constant (v(s) =0) over some range.

2.1. Existence, uniqueness & continuity of travel times a(t)

In Fig 1 or Fig 1(a), can show:

if U(t) & V(s) are continuously increasing then a(t) is unique & continuous in t.

In Fig 1(b), no inflow over some time interval (t1, t2).

In that case, can say,

travel time a(t) everywhere unique & continuous in t. or
can say it is undefined in interval (t1, t2).

From Fig 1(c), can say,

travel time is unique & semi-continuous, or can say,
a(t) is continuous one-to-many mapping at t3

See Proposition 1 in Carey (2004).

[Above, took U(t) & V(s) as given & computed a(t) from Fig. 1

Alternatively, given any 2 of variables U(t), V(s) and a(t),

third can be obtained immediately from Fig 1.

Can extend the above results to these cases. ]

2.2. First-in-first-out (FIFO)

FIFO: users exit from link/path in same order as entered it

N.B. Passing/ overtaking occurs in practice, but would need to be explicitly modelled, otherwise FIFO violations can cause very unrealistic results.

Interpretation of FIFO violations:

outflow physically positive but mathematically neg.

Consider flows entering from time t1 to t2, t1 < t2,

& exiting from t1+(t1) to t2+(t2).

(and no other flows).

Outflow per unit time, between t1+(t1) & t2+(t2), is

(inflows between t1t2)

v = ------

[t2+(t2)]  [t1+(t1)]

If FIFO holds, [t2+(t2)]  [t1+(t1)] is positive, hence v > 0.

If FIFO violated, [t2+(t2)]  [t1+(t1)] is negative, hence v < 0

Physically, outflows are pos. throughout the exit interval,

but mathematically neg. because difference in exit times is negative (exit time is moving backwards w.r.t. entry time).

Can be shown that a necessary and sufficient condition for FIFO is: v(t) > 0 (or 0) for all t.

2.3. Time-flow consistency & relationship to FIFO.

Some papers have assumed v(t) > 0, and justified this by saying that v(t) < 0 would mean flow travelling the wrong direction on the link, hence can be assumed away.

However, v(t) < 0 does not mean traffic going wrong way on link.

Assumption “v(t) > 0” is equivalent to assuming FIFO.

V(t) < 0 may not have a physically useful meaning, but it is easy to construct a travel time model in which it occurs.

Sometimes assumed/ implied in DTA literature that consistency eq., U(t) =V(t+(t)), or eqs derived from it, are necessary or sufficient for FIFO.

They are not, unless v(t)  0 is also ensured by other properties of the model.

[Footnote:

Derivative of (1) gives well-known “flow propagation eq.”

u(t)

v(t+(t)) = ------(5)

(1+'(t))

hence this too is not necessary or sufficient for FIFO.

2.4. Strict causality, partial causality, & relationship to FIFO

Strict causality: speed (& travel time) of vehicle is

affected by vehicles ahead but not vehicles behind.

Partial causality: speed (& travel time) of vehicle is

affected by vehicles ahead and also by some vehicles behind.

Example of partial causality: exit-flow model v(t) = g(x(t)). x(t) is number of vehicles on link at time t.

Neither partial causality nor strict causality is necessary or sufficient for (t) to satisfy FIFO.

Necessity: e.g., exit-flow model v(t) = g(x(t))

can be shown to satisfy FIFO but does not satisfy strict causality

(since inflows at time t affect x(t) and hence v(t) ).

Sufficiency: e.g., Consider travel-time model

(t) = f(u(t)) where u(t) is link inflow.

Satisfies strict causality, but easy to see it can violate FIFO.

3. Stronger properties for particular classes of travel-time models

Two classes of link or path models:

Exit-flow models.

E.g.

Merchant and Nemhauser, and later variants.
Cell-transmission model; triangular flow-density, nonlinear flow-density.
Microsimulation models, car following, etc.

Exit-time models. E.g. (t) = f(x(t))

E.g. Friesz et al(1993). Montreal group (Xu, Zhu, Marcotte, Florian, etc), by Astarita and Adamo, & several papers from China, especially Hong Kong.

Table: Properties of various models for obtaining link/ path travel-times

Model. Travel times obtained from: / Time-flow
consis-
tency / FIFO / Partial
caus-
ality / Strict
caus-
ality
Exit-time model:
f’n of no. of vehicles on link at time of entry,
(t) = f(x(t)) / YES / Only if (max inflow)
< 1/f'(x(t)) / YES / YES
Exit flow models.
Exit-flow model:
obtained from exit-flow model
v(t) = g(x(t)) using Fig 1,
U(t) = V(t+a(t)) / YES / YES / YES / NO
Exit-flow model “adjusted” to satisfy strict causality. / NO / NO / YES / YES
Combined exit-flow model: b(x(t))
= x(t)/ g(x(t))
= (vehicles on link)/
(outflow rate) / NO / YES / YES / YES
“Desirable properties” model:
f’n of “average flow” experienced by vehicle

/ YES / YES / YES / YES

3.1. Exit-time models.

Most common is (t) = f(x(t))

x(t) is no. of vehicles on link.

A sufficient condition to satisfy FIFO, & other desirable properties, (Xu et al (1999)) is:

(maximum inflow rate) < 1/ f'(x(t)) (*)

f'(x(t)) is gradient of f(x(t))

Similar conditions in several papers.

[ None suggest an intuitive reason for (*), but can be given:

For a violation of (*) we need 1/ f'(x(t)) to be “small”, hence f'(x(t)) to be “large”, i.e., travel time function very “steep”.

If the travel time function is “steep”, and if link volume x(t) is declining rapidly then travel times (for new entrants) will be declining “fast”. If declining fast enough, current vehicle will traverse the link and exit before preceding vehicle exits, hence violating FIFO.

Can also explain why l.h.s. is (maximum inflow rate). ]

3.2. Exit-flow models

3.2(a). An exit-flow model in continuous time

Consists of an exit-flow function

v(t) = g(x(t)) , (2)

and a conservation equation

x(t) = U(t) V(t),` (3)

or the derivative of this

x'(t) = u(t) v(t) (4)

Usually assumed: g(x) continuous nondecreasing

g(0)=0 and 0 < g(x)xfor allx> 0.

3.2(b). An exit-flow model in discrete time

Discrete exit-flow equation

v(t) = g(x(t)) t = 0, , 2, …, I (6)

and conservation equation

x(t+) = x(t) +u(t) v(t) t = 0, , 2, …, I. (7)

Analogous to (4).

3.2(c). Special form of exit-flow model:

CTM & finite diff. approx. to LWR model.

Lighthill & Whitham (1955), Richards (1996), Daganzo (1994, 1995), Lo (1999), Lo and Szeto (2002).

Discretise time & distance into cells & apply a form of exit-flow model.

Converges to LWR model, as discretisation refined.

If step size ‘large’, model is comparable to ‘whole-link’ models.

Flow from cell i to i+1 at time step t is

v(i,t) = min{g+(x(i,t)), g(x(i+1,t)) } (8)

g+(x) = amount available to exit from a cell

[upward sloping part of g(x) from origin to peak & continued forward as horizontal line],

g(x) = amount that the next cell downstream can accept,

[downward sloping part of g(x), continued back from peak by horizontal line].

Conservation eq. for FDA model: same as for M-N exit-flow model.

3.2(d). Travel times (t) when flows defined by exit-flow model (in continuous-time)

Existence, uniqueness and continuity ofa(t)

In exit-flow model, outflow v(t) = g(x(t)) is  0 or > 0 by construction, hence V(s) is everywhere increasing. hence (t) unique & continuous over t (sec. 2 and Fig. 1)

First-in-first-out (FIFO)

Proposition: When flows are given by exit-flow model then (t) satisfies FIFO.

Proof. Basically because v(t) = g(x(t))  0 hence v(t)  0, and we saw earlier that v(t)  0 is necessary & sufficient for FIFO.

Contrary to above, it has been stated several times in the literature that exit-flow model violates FIFO.

Causality.

Satisfies only partial causality, not strict causality

Outline proof: Travel time (t) = st obtained from U(t) = V(s), is affected by outflows v(s’) up to time s, i.e. outflows after time t.

But outflow v(s’) = g(x(s’)) depend on x(s’) hence inflows up to time s’.

Hence, travel time (t) depends on inflows after time t, as well as before time t.

3.2(e). ‘Causality' bounds on (t).

As noted above, travel times a(t) are affected by inflows after time t (from t to t+(t)), which violates strict causality. It is of interest to find bounds on the possible value of (t), given only inflows up to time t.

We derived such bounds and find they are very weak,

i.e., even if we know the inflows up to time t, travel time for traffic entering at time t can take a very wide range of values.

3.2(f). Adapting travel-time model a(t) to preserve strict causality

Can 'adapt' model a(t) so that it preserves strict causality, but this can cause FIFO violation.

Take travel-time model a(t) & re-define it as travel time for vehicle entering at time t+a(t), instead of time t.

This preserves strict causality, but can show it

no longer satisfies time-flow consistency and

can violate FIFO.

Also, it determines travel time based entirely on traffic that has already exited

(i.e. causality can easily be achieved, but can be “nonsense” causality)

3.2(g). Extending results

For exit-flow models, we extended results to:

Exit-flow model in discrete time

Difference approximations to LWR, & other ‘spillback’ models

Letting the exit-flow function be inhomogeneous over time

I.e. v(t) = g(x(t),t) instead of v(t) = g(x(t)).

Not considered previously in DTA literature?

3.2(h). Can travel-times from exit-flow model satisfy

FIFO, causality & time-flow consistency?

Answer is no, unless discretisation of time and space is refined to continuous limit.

If travel times satisfy time-flow consistency they satisfy FIFO but not strict causality.
If adjust travel-time def. to ensure strict causality, then it no longer satisfies time-flow consistency & may violate FIFO.

All 3 properties are ensured by LWR model -- continuous in time & space.

Whole-link exit-flow models are approximations to (restricted forms of) LWR model.

& converge to LWR if time & space steps are reduced to continuous limit.

That exit-flow models do not exactly satisfy the above desired properties is a price we pay for using an approximation.

4. A “combined” exit-flow & travel-time (exit-time) model

Sometimes suggested that:

If travel times satisfy FIFO they satisfy time-flow consistency U(t) = V(t+a(t)) or derivatives of that, or vice versa.

Counterexample:

A few reports & papers used flows defined by exit-flow model,

BUT instead of using cum. curves U(t) = V(t+a(t)) to compute travel times, use

x(t) (vehicles on link)

b(x(t)) = ------= ------

g(x(t)) (outflow rate)

Does not satisfy time-flow consistency, U(t)  V(t+b(t)), i.e. not Fig 1.

but satisfies uniqueness, FIFO, and causality.

(First time properties of this model have been discussed.)

5. An alternative travel-time (exit-time) model

Let travel time be function of

w(t), a weighted average of inflow at time of entry & outflow at time of exit

i.e., an estimate of “average” flow in neighbourhood

of the vehicle as it traverses the link.

where

and outflow given by

Carey, Ge and McCartney (2003)

Of all “whole-link” models

(exit-flow models, exit-time models, or combined model)

above appears to be only “whole-link” model that satisfies all 3 properties:

FIFO, strict causality, time-flow consistency.

6. Summary table: Properties of various models for obtaining link/ path travel-times

1. Properties of link/ path travel times

1.1. Assumptions & conclusions

2. Obtaining travel times from cumulative inflows & outflows

2.1. Existence, uniqueness & continuity of travel times a(t)

2.2. First-in-first-out (FIFO)

2.3. Time-flow consistency & relationship to FIFO.

2.4. Strict causality, partial causality, & relationship to FIFO

3. Stronger properties for particular

classes of travel-time models

3.1. Exit-time models.

3.2. Exit-flow models

3.2(a). An exit-flow model in continuous time

3.2(b). An exit-flow model in discrete time

3.2(c). Special form of exit-flow model:

CTM & finite diff. approx. to LWR model.

3.2(d). Travel times (t) when flows defined by exit-flow

model (in continuous-time)

3.2(e). ‘Causality' bounds on (t).

3.2(f). Adapting travel-time model a(t) to preserve strict

causality

3.2(g). Extending results

3.2(h). Can travel-times from exit-flow model satisfy

FIFO, causality & time-flow consistency?

4. A “combined” exit-flow & travel-time (exit-time) model

5. An alternative travel-time (exit-time) model

6. Summary table: Properties of various models for

obtaining link/ path travel-times