Modeling and estimation of combined route and activity location choice

Gunnar Fltterd* and Kai Nagel**

Abstract This work addresses a behavioral state estimation

problem using multi-agent traffic simulations. A model of
individual route and activity location choice is presented,
which can be simulated by a combination of a time variant
best path algorithm and dynamic programming, yielding a
behavioral pattern that minimizes a travelers perceived cost.
The estimation method then adjusts this individual behavior to
anonymous measurements of link-related traffic characteristics
using an algorithm for optimized microscopic traffic assignment
which itself is a novel tool with potentially broad applicability.

I. I NTRODUCTION

knowledge should be aggregated away during the formalizing

steps of setting up a mathematical estimation problem.
The remainder of this article is organized as follows. A
conceptual overview is given in the remainder of this section. The deterministic modeling and simulation problem is
discussed in section II, with a focus on behavioral issues and
some necessary background on the used traffic flow model.
The incorporation of uncertainty into the model then allows
to formulate the Bayesian estimation problem formulation
in section III, where a solution method is presented as well.
First experimental results are discussed in section IV and
finally the article is concluded in section V.

A. Problem statement
The problem of traffic monitoring and prediction has been
considered by many researchers. Various approaches are
data-driven [16], [17], [28], while others adjust structural
models to real world measurements. The latter group can
further be classified with respect to what quantities are
estimated: Some consider the problem of estimating physical
traffic flow properties such as densities, velocities, or flow
parameters [20], [27], while others (including this work)
concentrate on the underlying demand itself and consider the
physics of traffic flow as a dependent effect [2], [21], [26].
The second point of view is closer to the real problems
structure, since traffic demand is the cause of road usage.
Still, estimation of traffic demand and network link related
quantities are two aspects of the same problem and ultimately
should not be separated [1].
This article describes a method for traffic state estimation
that uses multi-agent simulations. We combine a flexible
but little formalized representation of individual mobility
behavior as implemented in the MATSim project [11] with
well understood methods of system engineering [19]. This
allows us to consider the problem of estimating agents
route and activity location choice in a Bayesian setting by
combining for every agent an a priori activity plan for a given
day with anonymous traffic measurements such as flows or
densities into a most likely a posteriori plan.
Our work appears to be the first in this field which estimates fully individualized behavior from anonymous traffic
measurements. The choice of this objective is justified by the
observation that traffic demand results from heterogeneous
individual mobility needs. Thus, no validated individualized
*Gunnar Fltterd is with the Group for Transport Systems Planning and Transport Telematics, Technische Universitt Berlin, D-10587
Berlin, Germany. Tel: +49-30-314-29520, fax: +49-30-314-26269, mail:
floetteroed@vsp.tu-berlin.de.
**Kai Nagel is head of the Group for Transport Systems Planning and
Transport Telematics, mail: nagel@vsp.tu-berlin.de.

B. Conceptual overview
The traffic model is decomposed into a microscopic representation of traveler behavior and a mixed micro/macro
mobility simulation.
Some aspects of the overall simulation setting are depicted
in Figure 1 (left). In an attempt to realize their individual
activity plans, travelers consider their long- and short-term
observations of the traffic system when performing actions
within their physical environment. Technically, an agent
modifies its current path by sending an object representing
its perceived cost of network link usage to a router, which
then returns the resulting best path. Note that this cost is
individually perceived and can contain perception errors as
well as incomplete knowledge.
The behavioral estimation procedure results from reasonable mathematical inference but can be conveniently illustrated as in Figure 1 (right). The simulation structure is not
changed at all. The estimation algorithm compares the output
of the mobility simulation and a traffic surveillance system.
Based on this comparison, it modifies the cost perception any
agent sends to the router in such a way that it corresponds to
the agents behavioral improbability. The resulting behavior
is different insofar as it is not optimal with respect to the
agents goals any more, but rather to a more general objective
function representing the state estimation quality.
Depending on the chosen setting, this estimation method
is applicable both for adjustment of a planning simulation to
historical data and to real time traffic monitoring by tracing
within-day traffic fluctuations.
The entire software system is single-threaded and was
written in the Java programming language.
II. M ODELING AND

SIMULATION

The estimation methodology proposed in subsequent section III requires a formal description of the traffic model.
Here, such a representation is given for both the physical

Fig. 1.

Schematic representation of the simulation procedure.

Simulation and Estimation

Schematic representation of the estimation procedure.

model of traffic flow and the mental representation of travel

behavior.

Fig. 2.

Screenshot of mobility simulation

A. Mobility simulation
The physical model combines microscopic and macroscopic aspects. The representation of traffic flow dynamics is
a fully macroscopic 1st order traffic flow model which runs
in discrete time and space and only moves aggregated flows.
The model permits linearization as required by the algorithm
given in section III-A, but still works on a microscopic level
in order to allow for behavioral heterogeneity in the driver
population, which is difficult to deal with in a macroscopic
way.
At diverges, the macroscopic model splits flows according
to turning fractions that result from observations of individual
behavior in the following way: Massless vehicles passively
float in the macroscopic traffic stream. Only at diverges
they actively choose their next link. The macroscopic model
counts, filters, and normalizes these turning moves, which
yield the required splitting fractions. Formally,
x(0)

= x0

x(k + 1) = f [x(k), u(k), k],

(1)

where x(k) is the macroscopic models state vector at

discrete time k, f is the state transition function and u(k) is a
control vector expressing the influence of individual behavior
onto the macroscopic model: For every possible turning
move ij from link i to link j it contains one component
uij (k) that represents the number of vehicles having made
this turn at time k by
X
uij (k) =
uij (k)

uij (k)

1 if individual made turn ij at k;

(2)
0
otherwise.

Approximate Jacobians f /x and f /u are available

due to the macroscopic nature of this model. Thus, from

Vehicles move from left to the right. At the diverge they choose from one of
three routes, each one having a downstream bottleneck. The figure indicates
that the macroscopic density (white=none, green=light, red=jammed) is
smoothly synchronized with the vehicles route choice.

f [k + k]/uij (k) aggregated traffic dynamics can be linearized with respect to any individuals path choice being
expressed as a sequence of turning moves [12], [13].
Overall, the approach is similar to what is termed
smoothed particle hydrodynamics (SPH) in physics [15]
or mesoscopic modeling in transport science [3], [10], [8],
[24], the main difference being that the model described
here was designed with the explicit intention to obtain
first derivatives from the model. In this way, mathematical
feasibility (linearization of the macroscopic model) and expressive power (microsimulation of behavior) are combined.
See Figure 2 for a screenshot of the mobility simulation.
This approach is quite efficient in terms of computational
time: We use an optimized mesh size for every link to
simulate the macroscopic model, which takes up most of
the calculation time. As a result, many links as well as the
vehicles they currently carry are updated on a quite coarse
time scale of up to 64 seconds, while smaller links are
updated every second.

Fig. 3.

physically possible. This property will in the following only

be stated verbally (U is feasible), since a formalization
would only increase notational overhead.
For individual , the cost of traversing U (i, j, k0 ) is
XX
C [U (i, j, k0 )] =
(4)
urs (k)crs (k),

Example of a plan with location choice

kk0 rs

This
plan
comprises
a
three-stage
sequence
residenceworkleisureresidence, which could be typical for an
employed persons weekday. In this example, the residence stage is only
possible at home, while work can be performed either at the office or at
home, assuming that working at home is feasible for this agent. The leisure
activity is possible either at home or at a shopping mall. The agent values
the choice of each activity location within every stage according to (a)
the direct benefit a choice of this location provides and (b) the expected
benefit it can expect from the remainder of its daily plan if it is continued
at this location. For example, when finishing work at 16:00 and comparing
the mall and the home location for the leisure stage, a home-working agent
has to take into account the cost of traveling to the mall and back home
which does not arise if the agent stayed home.

B. Behavioral model
1) A model of daily plans: Every agent has an individual plan for a given day, which is comprised as follows:
The complete day is segmented into n + 1 temporal stages.
Every such stage 0 a n is provided with a set La
of one or more locations (network links) and a discrete start
time step ka with 0 = k0 < k1 < . . . < kn . Formally,

)
stage a is nothing but a fixed temporal interval [ka , ka+1
during which wants to be at one of the locations in La . It
can be interpreted as an activity such as work, leisure or
shopping, while its location set can be understood as the
activity locations where the individual expects facilities for
execution of the according activity, e.g. different malls for
a shopping activity. An example of such an activity plan is
given in Figure 3. Note that the underlying network in which
the example locations are situated is not not drawn, but only
the logical multi-stage structure.
Every plan is anchored at its individuals unique home

location l0 = lhome
, where it starts and ends: L0 = Ln =

{lhome }. Individual values the choice of location l La

for activity a by Ra (l); the cost of choosing this location is
Ca (l) = Ra (l).
A route of individual starting at link i and time step k0
to link j is denoted by U (i, j, k0 ). It will be convenient to
represent it by
U (i, j, k0 ) = {u (k)}kk0 = {(urs (k))}kk0

(3)

where urs (k) is defined as in (2). We only consider feasible

routes in the sense that turning decisions are only made if the
previous route led to a location where this turning move is

which is additive in the nonnegative turning movement costs

crs (k) as perceived by . Link traversal costs can easily be
incorporated by adding them to the turning move cost of
entering the according link. The minimal cost path for between i and j when starting at k0 is denoted by U opt (i, j, k0 )

and its cost by Copt

(i, j, k0 ) = C [U opt (i, j, k0 )].
During execution of their daily plans, individuals are aware
of future effects their current activity location choice might
have: Not the most attractive (least cost) activity location
is chosen, but rather that location, which minimizes the
expected cost for the entire remainder of the day. Since any
individuals sequence of possible activity locations is known
and finite, dynamic programming can be employed to solve
this decision problem, as it will be shown in the next section.
2) Simulation of daily round trips: In order to describe
the combined route and activity location choice problem as
a multi-stage decision process, a residual cost Va (j) is introduced. It is defined as the minimal cost to be experienced
when starting activity a at location j La and continuing
in an optimal manner:

(j, l, ka+1
) + Va+1
(l)} (5)
Va (j) = Ra (j) + min
{Copt

lLa+1

for a < n , while R0 (lhome

) and Vn (lhome
) can be
arbitrarily set to 0 since they have no influence on the final
result.
For being located on any link i at time step k and
heading for activity a, the task of optimally completing its
round trip can now be stated as the problem of finding a next

activity location la La with minimal cost Copt

(i, la , k) +

Va (la ), being given by


(i, j; k) + Va (j) .
(6)
la = arg min Copt
jLa

This can be achieved by calculation of a single best path from

i to an imaginary destination d which directly succeeds all
locations j La by means of likewise imaginary connecting
links of cost Va (j). This simplification is possible since the
next activitys end time is known and fixed, and from there
on the traveler is back on his/her pre-computed path. This
yields the best next activity location (which is the last real
node on the obtained path) as well as the best path itself.
See Figure 4 for an example.
In the same manner, an optimal round trip can be obtained

is
by one sweep through all activity stages: ln = lhome

fix. Running backwards through stages a = n 1, . . . , 0

allows to calculate for every activity location j of current
stage a the optimal next activity location (6) and its residual
cost (5). Having reached a = 0, the optimal round trip
can then be obtained by moving forwards through all stages
and choosing the optimal next location as annotated during

Fig. 4.

Calculation of a single decision stage

As long as departure times are fixed at stage transitions,

duration dependent activity values could be incorporated by
making the costs of the aforementioned imaginary links
behind activity locations time variant. Realistic modeling
of departure time choice would require additional state
information representing the duration an agent has already
been conducting an activity [9]. Since we already have to
search an entire time variant traffic network in order to
model spontaneous route adjustment, we will avoid this
state space increase and keep departure time fixed until we
have computationally investigated our approach on larger
scenarios.
III. E STIMATION

Assume it is 16:00 oclock: Figure 3s agent is about to finish its work

stage and leave the office. The choice between going to the mall and
going home for leisure can technically be calculated as follows: Add an
imaginary destination node to the network and connect mall and home
node by likewise imaginary links to that destination. Attach the sum of
each activitys immediate cost plus its residual cost to the according link.
Then, calculate a time variant best path through the network, with link
weights according to the agents perception of the current traffic situation.
The obtained best path does not only yield the subjectively optimal route
through the network but also the chosen next activity, which is the last real
node in the path.

the previous backwards sweep. This procedure is standard

dynamic programming.
The calculation of residual costs for all activity locations
requires n best path tree calculations, each one connecting
all locations of a given stage to the single extra node behind
all locations of the next stage.
3) Within-day replanning: This calculation scheme can
efficiently be applied for simulation of within-day replanning: Consider an individual , which so far followed a
pre-calculated route towards its next activity location la .
Assume that now faces a significant deviation between
the observed traffic situation and its historically learned
one (on which its pre-computed route is based). It appears
reasonable that spontaneously replans its current decision
stage, while keeping its evaluation of subsequent activity
locations fixed. This is equivalent to direct application of
(6) in order to obtain a new route (and maybe a new
activity location) reflecting the current situation. The only
required computation for such a single-stage decision is the
calculation of one best path through one of the next temporal
stages locations towards the imaginary destination node
behind it, as previously explained.
Since we have shown that activity location choice can be
subsumed in a slightly modified route choice problem, the
following discussion will only treat the according best path
problem without explicitly mentioning location choice.
4) Discussion of model limitations: Economic theory
suggests that the marginal utility of conducting an activity
decreases over time. The model described above assumes
duration independent activity values implying zero marginal
utilities, which is realistic only for long activity durations.
Currently, we account for this by imposing a lower bound
on stage lengths when generating activity plans.

A. Optimized assignment
Consider the discrete-time optimal control problem
K1
X

[x(k), u (k), k]

Minimize

J = [x(K)] +

subject to

x(0) = x0 ,
x(k + 1)X
= f [x(k), u(k), k],
u(k) =
u (k),

k=0 M

U = {u (k)}K1
k=0 are feasible.

(7)
The objective functional J is defined in terms of once
differentiable real-valued functions and . M denotes
the set of all travelers. The dynamic system constraints are
identical to (1) and (2), while the verbal route feasibility
constraint is elaborated in section II-B.1.
1) A single agent: Macroscopic traffic dynamics (1) are
linear in good approximation with respect to a single agents
behavior, since individual control variables uij {0, 1}
are small compared to actual turning counts in a congested
network. Thus, it is feasible to consider a linearization of J
with respect to u (k), k = 0 . . . K 1, which we denote
). While the difficulty to account for the dynamic
by J(U
constraints in (7) can be dealt with by well-known methods
from control theory [22] as it has already been elaborated
in a traffic-related context [18], we give a self-contained
explanation in the following.
Denote
J(k) = [x(K)] +

K1
X

[x(c), u (c), c]

c=k M

[x(k), u (k), k] + J(k + 1)

M

[x(K)]

Sensitivities with respect to states result from

X
[x(k), u (k), k] dJ(k + 1)

x(k)
dx(k)
dJ(k)
M
=
dx(k)
[x(K)]

x(K)

k<K
(8)
k = K.

k<K
k = K.
(9)

Since the interplay between variables at different k is fully

given by state equation (1),
f [x(k), u(k), k]T dJ(k + 1)
dJ(k + 1)
=
dx(k)
x(k)
dx(k + 1)

(10)

for k < K, where x(k + 1) = f [x(k), . . .] was used and

denotes the transpose. Sensitivities with respect to control
variables of a certain individual result from

dJ
du (k)

[x(k), u (k), k]
u (k)

f [x(k), u(k), k] dJ(k + 1)

,
u(k)
dx(k + 1)

(11)

where u(k)/u (k) yields an identity matrix and thus

disappears from the second addend.
Sensitivities dJ/du (k) can therefore be obtained in a
two-pass-procedure:
1) Using (10), solve (9) recursively for k = K . . . 0.
Moving backwards through time introduces a far
sightedness into the calculation, which is necessary
to predict a given time steps variations influence onto
future system states.
2) Determine the influence of controls by (11).
One obtains
K1
X  dJ T
) = J(U
) +
(k))
J(U
(u (k) u
du (k)
k=0

K1
XX
k=0

ij

dJ
u (k) + const.
duij (k) ij

(12)

where the constant addend contains all terms involving

= {
the control trajectory U
u (k)}k around which linearization took place, which is irrelevant to the considered
minimization problem.
) is a sum of time variant costs
J(U
dij (k) =

J
uij (k)

(13)

multiplied with the turn indicators uij (k). When all dij (k)
are positive, then minimization of the linearized problem
J is achieved by finding a balance, within the constraints,
between increasing as few indicators as possible and increasing only those with small dij (k). Since, in our case,
the constraint is given by the necessity of moving a traveler
from his/her origin to his/her destination, the application of
a time variant best path algorithm on a modified network
suggests itself as a solution procedure to this problem, where
the original networks links comprise the new nodes and
every possible turning movement in the original network
is represented by a new link ij with time variant cost
given by dij (k). If it cannot be guaranteed that all dij (k)
are nonnegative, loops of negative cost might occur in the
modified network, which somewhat complicate the best path
calculation [5].
Calculating one such best path for a single agent only
solves a linear problem approximation. The nonlinear prob-

lem for an entire population is discussed in the next section.

2) Many agents: We now consider the problem of minimizing (7) by synchronous modifications of many agents
trajectories. Clearly, the increased number of degrees of
freedom has the potential for a better overall solution, still
this setup results in certain problems also encountered in
dynamic route guidance: If many drivers are independently
of each other informed of a low travel time route, they might
all switch towards this route, causing a jam and very high
travel times times [6]. Similarly, the linearization (12) of
the overall functional does not allow for a coordination of
different vehicles path optimizations.
Our proposed algorithm resembles the fixed point solution
approaches to self consistent route guidance in the sense that
it iteratively updates only a subset of all particle trajectories.
One iteration of the algorithm is given below:
1) Load all vehicles onto the network;
2) evaluate target functional J and stop if desired;
3) differentiate target functional and obtain (12);
4) choose a subset M0 M;
5) calculate a new trajectory U for every M0 that
) as given in (12) by
approximately minimizes J(U
dynamic best path algorithm;
6) continue with 1.
This algorithm resembles a popular traffic assignment
method that solves the equilibrium problem in terms of a
fixed point iteration [7] and can also be interpreted as an
application of the method of Frank-Wolfe in a microsimulation setting [25]. Since traffic assignment based on these
methods has become common practice, we expect the method
to also work well for our purposes. The following section will
provide a concrete application of the proposed algorithm.
B. Bayesian problem formulation
1) Modeling of anonymous traffic measurements: The
macroscopic state equation (1) is supplemented with an
output equation
y(k) = g[x(k), (k), k],

(14)

which maps system states x(k) by a once differentiable

function g onto macroscopic observables y(k) such as flows,
velocities or densities. The system output y(k) is generated
by sensors such as inductive loops, floating cars, or traffic
surveillance cameras. Since these sensors are prone to various sources of error, these influences are expressed by a
random disturbance vector (k) that turns y(k) itself into a
random variable.
Although our approach can handle the general formulation
(14), we will in the following adopt a more specific case,
that is more amenable to an intuitive understanding of
the formalism. Assume that only link-related outputs are
available and generated by
yi (k) = gi [xi (k)] + i (k)

(15)

with i (k) being normally distributed with expectation 0 and

known variance i2 . By output is conditional probability

Pr(yi (k)|xi (k)) we denote the probability that yi (k) lies

within a -environment around gi [xi (k)]:
Pr(yi (k)|xi (k)) = Pr( i (k) )

(16)

with sufficiently small to allow with reasonable precision

for the first-order approximation


2
(yi (k) gi [xi (k)])2
,
Pr(yi (k)|xi (k)) p
exp
2i2
2i2
(17)
which can be subsumed in terms of trajectories Y = {y(k)}k
and X = {x(k)}k as
Y
Pr(Y|X ) =
Pr(y(k)|x(k))
k

YY
k

Pr(yi (k)|xi (k)),

(18)

the same result as the cost minimization procedure given in

section II-B.2.
Now it is assumed that some measurements Y are available. The a posteriori probability Pr(U |Y) that an individual chose path U in consideration of Y is expressed via
Bayes theorem:
Pr(U | Y) =

Pr(Y|{U } ) = Pr(Y|X ({U } )),

(19)

which can be linearized because of all intermediate steps

differentiability.
2) Formulation of the estimation problem: It is assumed
that individual is currently moving through the network
towards one of the activity locations of its current plan stage.
Without consideration of measurements, the individuals a
priori path and location choice can be simulated as explained
in section II-B.2.
This choice mechanism is now probabilistically relaxed.
The a priori probability that the individual chooses a path
U is expressed in terms of a multinomial logit model [4]

exp( C (U ))
,
Pr(U ) = P

V exp( C (V))

(20)

where the normalizing denominator sums over all possible

paths V from the individuals current location to its destinations. Note that this choice set will never be explicitly
generated. is the individual specific logit dispersion
parameter. Since the path costs in (20) already incorporate
s perceptional error, the logit model only represents an
additional perceptional error that is not link related. Thus,
the problem of cost correlations among different alternatives
is taken care of by explicit simulation of cost perception,
while the logit model is employed in a context where the
assumption of independent identically distributed errors is
reasonable [23].
In the absence of further information (such as measurements) the minimum cost path would have maximum
probability of being chosen. Thus, a probability maximizing
estimator of the individuals a priori route choice would yield

(21)

where Pr(Y | U ) is equivalent to (19) with the route choice

of all individuals other than being fixed. After taking the
logarithm of this function, we substitute (18) and (20):
X
ln Pr(U | Y) =
ln Pr(yi (k)|xi (k)) C (U )
ik

X
exp( C (V))ln Pr(Y) (22)
V
{z
}
|
independent of U

ln

where stochastic independence between outputs on different

links or different time steps results from the simplified
assumption of univariate normal output errors (15).
From recursive eq. (1) one notes that x(k) is fully defined
k1
by control sequence {u(k)}k=0
, which directly results from
the entire populations individual path choice set {U } via
(2). This dependency implies the existence of a conditional
probability

Pr(Y | U ) Pr(U )
,
Pr(Y)

Here and in the following equations one should keep in mind

that the xi (k) depend on the uij (k), which in turn are defined
by the uij (k) (cf. equation 19 and 2). Substituting (4) as well
as (17) and dropping all terms independent of U , we obtain
X (yi (k) gi [xi (k)])2
ln Pr(U |Y)
=
2i2
ik
X
cij (k)uij (k).
(23)

ijk

Thus, the most likely a posteriori route U of any individual

can be stated in terms of control problem (7) with
X (yi (k) gi [xi (k)])2
[x(k), u (k), k] =
2i2
i
X
+
cij (k)uij (k)
ij

[x(K)]

= 0

(24)

and can be calculated by means of the algorithm given in

section III-A.
3) Discussion of problem formulation: While application
of section III-As algorithm to problem (24) is possible
without further modifications, several remarks are given here
to clarify the algorithms working.
Target function (24) results from the simplifying assumption of univariate normal measurement errors (15).
More general distributions are possible.
The solution algorithm relies on repeated linearizations
of (24) with respect to any agent s path choice.
Specifically, eq. (12) turns into
XX


) =
J(U
ij (k) + cij (k) uij (k), (25)
k

ij

where real-valued coefficients ij (k) result from the

linearization steps as described in section III-A.1 applied to the quadratic measurement error term, while
the path cost perception term is already linear. These
coefficients represent the additive modifications to the

individual cost perception as described in section I-B.

Since the ij (k) are identical for all agents, they have
to be calculated only once per iteration.
In the absence of measurements, only the second addend
in (24) remains. While in this case the Bayesian problem
formulation still expresses an entire path choice distribution resulting from the logit assumption (20), the solution algorithm will always strive for this distributions
maximum, which in this case is a user equilibrium (UE).
Still, this discrepancy is only of theoretical concern:
In a practical application there are available measurements which incorporate real-world randomness and
its resulting path-spread into the estimated behavior.
Furthermore, a congested assignment distributes paths
across various alternatives as well.
Both, planning (offline) and telematics (online) applications can be dealt with by the proposed method. The
major difference is the information about the network
state that is repeatedly given to the agents during the
iterative estimation procedure. If every agent is provided
with global knowledge of the system state as it resulted
from the very last iteration, the algorithm converges
in the absence of measurements towards a UE, and
otherwise towards a statistically reasonable compromise
between a UE and the observed measurements. If, on the
other hand, the information updates given to the agents
are constrained to what is actually observable to the
agent in that moment, the algorithm does not converge
to a strict UE any more, but rather to a solution which
realistically regards for a randomly influenced withinday situation. In the latter case, historical information
contained in the drivers activity plans must be used to
complement the local observations.

Fig. 5.

Reduced Berlin network

Fig. 6.

Experiment (a)

IV. E XPERIMENTS
A. Setting of the test case
We have set up an extensive test case for the proposed
method. The geographical zone of investigation is the city
of Berlin. Its traffic network is represented by a graph of
approximately 2400 links. The MATSim system has been
used to generate activity plans for a complete microscopic
representation of the Berlin population. The experiments
described here use a 10% sample of this population (approx.
170.000 agents). The network is shown in Figure 5.
We gained first experiences with this test case in a realworld application during the soccer world championship
2006. Since we encountered severe problems with all kind
of data corruption (including errors in the network file,
unrealistic activity plans, unreliable measurements) during
this project, this article considers a setting in which most
uncertainties have been removed in order to study the method
itself rather than a specific scenario. Accordingly, the results
given here are to be understood as a preliminary study of
algorithmic feasibility. Increasing realism with respect to
various sources of disturbances is subject of our ongoing
research.

No incorporation of measurements. % = 0.785.

All experiments use synthetically generated measurements

as follows: Plans from an imperfect MATSim traffic assignment that did not reach a user equilibrium were loaded
onto the network using the same mobility simulation as
the estimator itself. For 10% of all links, we collected 5minute averages of the number of vehicles on these links as
measurement data. The experiments were run from 6am to
9am, which is the time of the strongest traffic variations in
the simulation because of the morning rush hour. Since the
imperfect MATSim result is not a user equilibrium, it can
be understood as a behavioral deviation from such, which is
exactly the type of situation our method has been designed
to handle.
B. Experiments
Four exemplary experiments are discussed. The resulting
scatterplots are depicted in Figures 6, 7, 8, and 9, where

Fig. 7.

Fig. 8.

Experiment (b)

No incorporation of behavioral model. % = 0.988.

Experiment (c)

Reasonable combination of measurements and behavioral model. % =

0.974.

% is the coefficient of correlation and point coordinates are

(measured value / simulated value).

In experiment (a), the estimator is run without the use

of any measurements. As a result, it generates a best
assumption of traveler behavior given the MATSim activity plans by iterating these plans until an approximate
user equilibrium is achieved. One observes significant
deviation between simulation and estimation. This can
be explained by the working of the estimation algorithm
in the absence of any measurements: In this case, only
the behavioral a priori information is available, which
results in a plain user equilibrium assignment as explained above. Since the measurements were generated
from a non-equilibrium situation, but are not available
to the estimation procedure, the scatterplots represent
nothing more but the measurements deviation from a
user equilibrium.
In experiment (b), parameters were set such that the
algorithm attempted to reproduce the measurements by
ignoring behavioral a priori assumptions as much as
possible: Only measurement-induced cost corrections
were visible to replanning agents, while the cost of
travel itself was completely ignored. The very good
measurement reproduction indicates that the method
works well. The not totally perfect fit is due to various
causes, some of which were deliberately accepted while
others are still under investigation. Unavoidable but to
some degree tunable causes of imprecision are: Incorporation of various mathematical simplifications in the
estimation algorithm in order to keep up tractability; use
of a random solution mechanism with finite resolution;
discretization of macroscopic quantities in time and
space on a quite large scale for reasons of computational

performance; use of a linearization based method that

might converge only towards a local optimum of the
problem.
Experiment (c) incorporates the behavioral model with a
reasonable weight. As a result, the estimation algorithm
abstains from calculating routes that are very unrealistic
given an agents activity plan, even if such behavior
yield a better measurement fit. The reproduction quality
of measurements involved in the estimation is now
slightly worse than in experiment (b). The reason for
this is the newly incorporated influence of the estimators behavioral model, which contradicts the unrealistic
behavioral nature of the measurements. Since in general
measurements are just as error-prone as simulation
results, such a compromise is desirable. When judging
the estimation quality, it is important to keep in mind
that the scatterplots only depict one half of the entire
estimation problem; the behavioral fit based on the a
priori generated activity plans is not visualized.
Given the general setting as described in experiment
(c), the methods real-time capabilities are investigated
in experiment (d). While the previous experiments were
run to convergence, here a rolling horizon approach
with a time window of 30 minutes was used. The
window moved forwards at 1-minute steps, which is
approximately the duration of one estimation iteration.
During every iteration, a new path was calculated for
3% of the entire population. The result is slightly
worse than that of experiment (c) but still indicates a
significant improvement over experiment (a).

The scatterplots for experiments (b) through (d) compare

simulation results only to measurements that also were

Fig. 9.

Experiment (d)

Calculated with rolling horizon in real time. % = 0.959.

made available to the estimation algorithm (in-sample results). The out-of-sample results we obtained so far show
greater qualitative variability than the depicted in-sample
results and require further investigations, since ultimately
the method should yield likewise consistent out-of-sample
improvements. One important aspect is the out-of-sample
results greater sensitivity to the chosen behavioral model,
which mainly guides the estimations interpolation between
available measurements.
Even if much more experiments will be necessary to fully
understand all implications of the method, these experiments
assert that the algorithm is computationally capable of generating significant estimation improvements even in real-time
scenarios of realistic size.
V. S UMMARY

AND OUTLOOK

We have presented a novel method for behavioral traffic

state estimation based on a priori generated activity plans and
anonymous traffic measurements. First experiments indicate
that the method works with good precision in a real-time
setting even for large problems. Still, since the experiments
conducted so far only used synthetically generated measurements, many aspects are yet to be explored.
One major simplification was the generation of measurements by the same mobility simulation the estimator
itself used. Since model-based assumptions about traffic flow
dynamics are currently incorporated as error-free information
in the estimation formulation, further investigations with real
world data might show that a relaxation of this assumption
will be necessary. Since methods for the adjustment of
physical traffic flow processes to measurements are available
from the systems engineering literature, an integration of
both estimation approaches appears reasonable as stated in
the introduction.

A similar statement holds for the occurrence of incidents,

which can be considered as structural deviations between
modeling assumptions about traffic dynamics and the real
situation. The implementation of an additional incident detection module definitely would greatly increase the systems
real-world applicability.
An improved a priori demand also implies a better estimation quality. As recent experiments have shown [14], a
brute force attempt to only reproduce measurements does not
provide a reasonable overall picture of the traffic situation,
which makes the incorporation of good behavioral a priori
assumptions necessary. This observation also suggests a natural operation scheme of the method in a traffic management
center: In continuous operations, the estimator could be
employed to track within-day fluctuations. If an additional
update of the agents activity plans on a daily basis was
realized, the overall system could incrementally improve a
transport planning simulation based on these plans as well.
R EFERENCES
[1] C. Antoniou. On-line Calibration for Dynamic Traffic Assignment.
PhD thesis, Massachusetts Institute of Technology, 2004.
[2] Kalidas Ashok. Estimation and Prediction of Time-Dependent OriginDestination Flows. PhD thesis, Massachusetts Institute of Technology,
1996.
[3] M. Ben-Akiva, M. Bierlaire, H. Koutsopoulos, and R. Mishalani.
Dynamit: A simulation-based system for traffic prediction. DACCORS
Short Term Forecasting Workshop, The Netherlands, February 1998.
See also its.mit.edu.
[4] Moshe E. Ben-Akiva and Steven R. Lerman. Discrete Choice Analysis.
MIT Press series in transportation studies. The MIT Press, Cambridge,
Massachusetts and London, England, 1985.
[5] Dimitri P. Bertsekas. Linear network optimization. The MIT Press,
Cambridge, Massachusetts and London, England, 1991.
[6] Jon Alan Bottom. Consistent Anticipatory Route Guidance. PhD
thesis, Massachusetts Institute of Technology, 2000.
[7] E. Cascetta. Transportation systems engineering: theory and methods.
Kluwer Academic Publishers, Dordrecht, 2001.
[8] G.L. Chang, H.S. Mahmassani, and R. Herman. A macroparticle
traffic simulation model to investigate peak-period commuter decision
dynamics. Transportation Research Record, 1005:107120, 1985.
[9] D. Charypar and K. Nagel. Q-learning for flexible learning of daily
activity plans. Transportation Research Record, 1935:163169, 2005.
[10] DYNAMIT/MITSIM, 1999. Massachusetts Institute of Technology,
Cambridge, Massachusetts. See its.mit.edu.
[11] Nagel et al. MATSim web site. http://www.matsim.org/, accessed
2006.
[12] Gunnar Fltterd and Kai Nagel. Some practical extensions to the cell
transmission model. Vienna, Austria, 2005. 8th International IEEE
Conference on Intelligent Transportation Systems.
[13] Gunnar Fltterd and Kai Nagel. Simulation and optimization of
trajectories in a congested network. Technical Report 06-02, Technical
University of Berlin, 2006.
[14] Gunnar Fltterd and Kai Nagel. State estimation for multi-agent
simulations of traffic. Berkley, California, June 2007 (submitted).
World Conference on Transport Research.
[15] R.A. Gingold and J.J. Monaghan. Smoothed particle hydrodynamics
- theory and application to non-spherical stars. Royal Astronomical
Society, Monthly Notices, 181:375389, 1977.
[16] G. Huisken and E. van Berkum. A comparative analysis of shortrange travel time prediction methods. Washington DC, USA, 2003.
TRB (82. Annual Meeting).
[17] Y. Kamarianakis and P. Prastacos. Forecasting traffic flow conditions
in an urban network: Comparison of multivariate and univariate
approaches. Washington DC, USA, 2003. TRB (82. Annual Meeting).
[18] A. Kotsialos et al. Traffic flow modeling of large-scale motorway
networks using the macroscopic modeling tool METANET. IEEE
Transactions on Intelligent Transportation Systems, 3(4), 2002.

[19] P.R. Kumar and Pravin Varaiya. Stochastic systems. Estimation,

identification and adaptive control. PrenticeHall information and
systems sciences series. PrenticeHall, 1986.
[20] S. Lorkowski and P. Wagner. Parameter calibration of traffic models
in microscopic online simulations. Washington DC, USA, 2005. TRB
(84. Annual Meeting).
[21] Hani S. Mahmassani, Xiao Quin, and Xuesong Zhou. DYNASMART
X evaluation for realtime TMC application: Irvine test bed. Technical
report, Maryland Transportation Initiative (University of Maryland and
College Park, Maryland), January 2004.
[22] J.B. Pearson and R. Sridhar. A discrete optimal control problem. IEEE
Transactions on automatic control, 11(2):171174, April 1966.
[23] Michael Scott Ramming. Network Knowledge and Route Choice. PhD
thesis, Massachusetts Institute of Technology, 2002.
[24] T. Schwerdtfeger. Makroskopisches Simulationsmodell fr Schnell-

[25]
[26]
[27]
[28]

straennetze mit Bercksichtigung von Einzelfahrzeugen (DYNEMO).

PhD thesis, University of Karsruhe, Germany, 1987.
Yosef Sheffi. Urban Transportation Networks: Equilibrium Analysis
with Mathematical Programming Methods. Prentice-Hall, Englewood
Cliffs, N.J. 07632, 1985.
C. Sun. Dynamic origin/destination estimation using true section
densitites. California path research report UCBITSPRR20005,
University of California, 2000.
Y. Wang and M. Papageorgiou. Real-time freeway traffic state
estimation based on extended kalman filter: a general approach.
Transportation Research B, 39:141167, 2005.
C. Zhou and P. Nelson. Predicting traffic congestion using recurrent
neural networks. In Proceedings of the 9th World Congress on
Intelligent Transport Systems, Chicago, USA, 2002.