Markovian Dynamic Traffic Assignment:
A new approach for stochastic DTA
R. de la Paz Gualaa,∗ , C.E. Cortésa,b , B. Heydeckerc and P.A. Reyda Civil Engineering Department, FCFM, Universidad de Chile, Santiago, Chilericardo.delapaz@uchile.cl, ccortes@ing.uchile.clb Instituto de Sistemas Complejos de Ingeniería (ISCI), Santiago, Chilec Centre for Transport Studies UCL, London, United Kingdom

b.heydecker@ucl.ac.uk
d Department of Industry, Universidad Tecnológica Metropolitana, Santiago, Chile

prey@utem.cl∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 15, 2022
Keywords: Stochastic DTA, Markovian, Probabilistic Route Choice, Traffic Assignment, Dynamic Programming

1INTRODUCTION

In dynamic traffic assignment (DTA) applications, it is relevant to consider the uncertainty
inherent to motorist route choices as part of the DTA formulations. In particular, motorists’choices made on realistic transport networks are mostly based on the perceived costs of allroutes from their origins to their destinations. In this work, we present an approach to address
stochasticity in a DTA context based on nested cost operators, where motorists construct theirroutes taking into account the perceived costs from their current node to their destinations.
We present the Markovian dynamic traffic assignment (MDTA) model, an integration of theMarkovian traffic equilibrium (MTE) by Baillon & Cominetti (2008) with the DTA modelling
framework by Addison & Heydecker (1996, 1998). It addresses stochasticity in a DTA context
where motorists choose their route according to their perceived costs of the remaining trip,resulting in an arc-based model instead of a route-based one. Our model allows working withoverlapping routes with no assumptions of independence of their costs. We comment on theMDTA algorithm, a method that solves our model in discrete time and that respects the FirstIn First Out (FIFO) rule and on preliminar results regarding its computational implementation.

2The Markovian dynamic traffic assingment approach

We first address two aspects that are key to our approach.

2.1

Reasonable arcs towards a destination

From a purely stochastic point of view, every option has a positive probability of being chosenby users. In reality, it is observed that not actually all options are even considered. To address
this, we adapt a reasonability concept.
TRISTAN XI Symposium

MDTA: A new approach for stochastic DTA

R. de la Paz Guala, C.E. Cortés, B. Heydecker and P.A. Rey

2Considering a destination node d, we say that (i, j) is a reasonable arc towards destination d
if the minimum cost of going from node i to d is greater or equal to the minimum cost of goingfrom node j to d. The set of reasonable arcs towards a destination node d is denoted as Rd . Our
proposed definition is an adaptation of the reasonable route concept from Dial (1971) (originallydefined over routes and origin-destination pairs instead of arcs and destinations).

2.2

Fulfilling the FIFO rule

To illustrate how FIFO rule is fulfilled, we provide a simplified description of how the approach
performs the queue unloading process in a basic case scenario.
Consider an arc with two flow of motorists queueing, going to go destinations A and B,
denoted as A1 and B1 , respectively. Now, consider two new flows joining the queue (one forevery destination), denoted as A2 and B2 . If the queue unloading capacity of the arc, Q, is not
overpassed by the aggregation of flows (Q ≥ A1 + B1 + A2 + b2 ), then all motorists can leave, andthere are outflow rates of A1 + A2 (going to A) and B1 + B2 (going to B). Otherwise, consider
that A1 + B1 ≤ Q < A1 + B1 + A2 + b2 , then priority is given to those motorists waiting the most(A1 and B1 ) and the residual unloading capacity is proportionally split between the motoriststhat arrived right after those that have priority (A2 and B2 ), then, there are outflow rates of2
2A1 + (Q − A1 − B1 ) A2A+B(going to A) and B1 + (Q − A1 − B1 ) A2B+B(going to B).
222.3

The Markovian dynamic traffic assignment model

The MDTA model has: a demand profile, a traffic model and an arc-choice model. For eachO-D pair (o, d) ∈ OD, the time-dependent demand rate function from the origin node o to thedestination node d, Dod (·), is exogenous. The other two parts are next further addressed.
2.3.1

The traffic model

We adapt the deterministic punctual queueing model to represent the traffic behaviour withineach arc, considering its features referenced in Addison & Heydecker (1998).
For each destination d ∈ D, for each arc a ∈ A and at each time t ∈ [0, T ], the inflow rate
and outflow rate of arc a going to destination d at time t are denoted as Ead (t) and Gad (t),respectively. The number of motorists with destination d in a queue on arc a at time t is denoted
as Lad (t), which we refer at as the queue length going to d of a at t.Then, the relationships
between inflow rates, outflow rates and queue lengths, for each destination node d ∈ D for eacharc a ∈ A at each time t ∈ [ϕa , T + ϕa ] can be analytically expressed as:XX
′E(t−ϕ),ifE(t−ϕ)≤Q∧Lad′ (t) = 0,
aaaadadd′ ∈Dd′ ∈D
Gad (t) = XLad (t) Q , otherwise,(1)a′ (t)Ladd′ ∈D0,ifXEad′ (t − ϕa ) ≤ Qa ∧dLad=d′ ∈Ddt
Ead (t − ϕa ) − Gad (t), otherwise.

Xd′ ∈DLad′ (t) = 0,(2)

Now, for each arc a ∈ A and at each time t ∈ [0, T ], the cost of the arc a, having entered it
at t, denoted as Ca (t), is given by the free flow travel time of a plus the delay due to the waitingtime in the queue. Analytically, this can be expressed as:
X
Lad′ (t + ϕa )Ca (t) = ϕa +TRISTAN XI Symposiumd′ ∈DQa.

(3)

MDTA: A new approach for stochastic DTA

R. de la Paz Guala, C.E. Cortés, B. Heydecker and P.A. Rey

3

As FIFO rule must be satisfied, for each d ∈ D, for each arc a ∈ A, and at each time t ∈ [0, T ],as in Heydecker & Addison (2005), we set the following condition:
Gad (τa (t)) =Ead (t)dτa (t)dt,(4)

where τa (t) is the exit time of a motorist that entered arc a at instant t, given by τa (t) = t+Ca (t).
Note that, given the arc-based construction of the model and, particularly, the arc costs, ourapproach is able to address overlapping routes without independence of route costs.
2.3.2

The arc-choice model

Our model is a dynamic adaptation of the static traffic assignment model embedded in the MTE(Baillon & Cominetti, 2008), which considers that motorists choose following a logit model thatconsiders the expected minimum costs from the current node to their respective destinations.
We also use a logit model, considering a constant and known dispersion parameter θ.
For each destination node d ∈ D, for each arc a = (i, j) ∈ A and at each time t ∈ [0, T ], theexpected minimum cost of going from i to d using arc a, entering at t, Zad (t), is given by:
1 XZad (t) = Ca (t) − ln exp (−θZbd (t + Ca (t))) .
(5)
θ+b∈AjNow,Tlet us recall that only outgoing arcs a from a node i that are reasonable towards d(a ∈ A+Rd ) are assigned positive inflow rates. Additionally, at a given instant, the flow rate
ito be assigned from node i can come from two sources: the aggregate outflow rate of incoming
arcs to i and/or demand rate being generated at i (if it is an origin).
For each destination node d ∈ D, there are two cases: (1) for each node i ∈ N such that(i, d) ∈/ OD (nodes that are not origins for destination d), for each arc a = (i, j) ∈ A+i and ateach time t ∈ [0, T ], the inflow rate of a going to d at t is given by:X
X exp(−θZad (t))
Gbd (t), if a ∈ Rd ,
exp (−θZbd (t))
b∈A−iEad (t) = b∈A+ T Rd(6)i0,otherwise;and (2), for each o ∈ O such that (o, d) ∈ OD (nodes that are origins for destination d), for eacharc a = (o, j) ∈ A+o and at each time t ∈ [0, T ], the inflow rate of a going to d at t is given by:


X


exp(−θZad (t))

Gbd (t) + D(o,d) (t) , if a ∈ Rd , X
exp (−θZbd (t))
Ead (t) =(7)b∈A−o
+T db∈AoR
0,otherwise.

2.4

The MDTA algorithm

To solve a discrete version of the problem, we present the MDTA algorithm. At each timeincrement resulting from the discretization, it runs an adaptation of Dial’s algorithm (Dial,1971), where the backward step is run first to compute the expected minimum costs from each
destinations, and then the forward step is run to compute the inflow rate assignments.
The MDTa algorithm has been computationally implemented and some comments on one of
the tested instances are presented in section 3.
TRISTAN XI Symposium

MDTA: A new approach for stochastic DTA

R. de la Paz Guala, C.E. Cortés, B. Heydecker and P.A. Rey

34Results and final remarks

We first briefly comment on some graphic results obtained from applying the MDTA algorithm
on an artificial instance for the Sioux Falls network (Yang & Qiang, 2016), where, for each arca, its free flow travel time ϕa and its queue unloading capacity, Qa are known and constant.
Figure 1 depicts the demand rates for each O-D pair and the evolution of the outputs (inflowrates, outflow rates, and queue lenghts) of arc 22, where ϕ22 = 2 [sec] and Q22 = 3 [veh/sec].
Some important aspects regarding the behavior of the outputs are: (1) as arc 22 is only reasonable
towards node 13 and 20 (not towards 2), then there are two types of motorists traveling throughthe arc; (2) when the total inflow rate (sum of inflow rates going to both destinations) becomes
greater than Q22 , then a queue forms; (3) when there is a queue, then the queue unloading
happens at capacity, then the total outflow rate is equal to Q22 (while fulfilling FIFO rule).

Figure 1 – Demand rates [veh/sec] for each O-D pair, and arc 22’s inflow rates [veh/sec], outflow
rates [veh/sec], and queue lengths [veh] going to destinations 13 and 20
We have provided the highlights of our Markovian approach to deal with DTA in an stochastic
context. The main contribution presented in this extended abstract is the Markovian dynamic
traffic assignment model, where motorists construct their route based on recursive arc choices
based on the expected costs to their respective destinations while choosing only arcs that they
consider to be reasonable. This model, given its arc-based formulation, allows working withoverlapping routes with no asumptions on independence of route costs, avoiding the usuallynecesary route enumeration process that is found in literature when applying route-based formulations. We also present some results of the MDTA algorithm, a deeply elaborated method thatallows to obtain a solution for the model, respecting FIFO rule, that, given its detailed dynamic
programming nature, its a determinant contribution by itslef.

References
Addison, J. D., & Heydecker, B. G. 1996. An exact expression of dynamic traffic equilibrium. Transportation And Traffic Theory, 359–383.
Addison, J. D., & Heydecker, B. G. 1998. Analysis of traffic models for dynamic equilibrium trafficassignment. Transportation Networks: Recent Methodological Advances, 35–49.
Baillon, J.-B., & Cominetti, R. 2008. Markovian traffic equilibrium. Mathematical Programming, 111(1),33–56.
Dial, Robert B. 1971. A probabilistic multipath traffic assignment model which obviates path enumeration. Transportation Research, 5(2), 83 – 111.
Heydecker, B.G., & Addison, J.D. 2005. Analysis of Dynamic Traffic Equilibrium with Departure Time
Choice. Transportation Science, 39(02), 39–57.
Yang, H., & Qiang, M. 2016. Sioux Falls Network. ://github.com/bstabler/TransportationNetworks/blob/master/SiouxFalls/Sioux-Falls-Network.pdf.

TRISTAN XI Symposium

MDTA: A new approach for stochastic DTA