Informatica 40 (2016) 393–398 393
OD-matrix Estimation Based on a Dual Formulation of Traffic Assignment
Problem∗
Alexander Yu. Krylatov, Anastasiia P. Shirokolobova and Victor V. Zakharov
Saint Petersburg State University
7/9 Universitetskaya nab., St. Petersburg, 199034 Russia
E-mail: a.krylatov@spbu.ru, a.shirokolobova@spbu.ru, v.zaharov@spbu.ru
Keywords: OD-matrix, Wardrop’s user equilibrium, duality
Received: December 1, 2016
Congestion, accidents, greenhouse gas emission and others seem to become unsolvable problems for all
levels of management in modern large cities worldwide. The increasing motorization dynamics requires
development of innovative methodological tools and technical devices to cope with problems emerging on
the road networks. First of all, control system for urban traffic area has to be created to support decision
makers by processing a big volume of transportation data. The input for such a system is a volume of travel
demand between origins and destinations — OD-matrix. The present work is devoted to the problem of
OD-matrix estimation. Original OD-matrix estimation technique is offered by virtue of plate scanning sen-
sors location. Mathematically developed technique is based on a dual formulation of the traffic assignment
problem (equal journey time by alternative routes between any OD-pair). Traffic demand between certain
OD-pair is estimated due to journey time obtained from plate scanning sensors. Moreover, the explicit
relationship between traffic demand and journey time is obtained for network of parallel routes with one
OD-pair. Eventually, the developed method was experimentally implemented to the Saint-Petersburg road
network.
Povzetek: OD-matrika povezuje izvore in cilje prometnih povezav. Prispevek se ukvarja z iskanjem prib-
ližkov OD-matrike z dvojno formulacijo.
1 Introduction
OD-matrix estimation and reconstruction are urgent and
complicated challenges, since road networks of modern
cities are extremely large and intricate. In general, OD-
matrix estimation and reconstruction are different prob-
lems: the first means to obtain approximate values, while
the second has a goal to obtain precise values of actual traf-
fic demands [1]. One of the first mathematical models for
OD-matrix estimation was formulated in a form of bi-level
program [2]. Despite numerous publications, this problem
still attracts researchers from all over the world [3–8]. A
detailed comparative analysis of methods for trip matrix es-
timation was made in [4]. From a practical perspective, the
most promising technique is combination of data obtained
both from plate scanning sensors and link-flow counts [5].
This paper is also devoted to OD-matrix estimation prob-
lem. We believe that a plate scanning sensor is highly ef-
ficient engineering equipment. Indeed, due to link-flow
counts one could obtain solely amount of vehicles on the
link, while plate scanning allows to estimate the average
travel time between origin and destination by identification
* This paper is based on Alexander Krylatov, Anastasiia Shi-
rokolobova and Victor Zakharov, A dual formulation of the traffic assign-
ment problem for OD-matrix estimation, published in the Proceedings of
the 2nd International Conference on Applications in Information Technol-
ogy (ICAIT-2016).
the vehicle in origin and destination points. Since travel
time between an origin-destination pair is a Lagrange mul-
tiplier for a primal traffic assignment problem (TAP), it is
the variable in a dual formulation of TAP. Therefore, we are
able to formulate a new bi-level optimization program for
OD-matrix estimation based on data obtained from link-
flow plate scanning sensors on congested networks.
The present article is organized as follows. In Section
2 the network of parallel routes with one OD-pair is in-
vestigated. The idea of OD-matrix estimation based on in-
formation about travel times between OD-pairs is clarified.
Section 3 provides a dual formulation of traffic assignment
problem in two subsections: for a simple network with one
OD-pair and parallel routes, and for the general topology
network. Section 4 describes bi-level optimization program
for OD-matrix estimation on a congested network by virtue
of plate scanning sensors. Section 5 is devoted to the ex-
perimental implementation of the developed approach to
the Saint-Petersburg road network. Conclusions are given
in Section 6.
2 The network of parallel routes
Let us ntroduce the following notation: F is traffic demand
between OD-pair; fi is traffic flow on the route i, i = 1, n,
f = (f1, . . . , fn),
∑n
i=1 fi = F ; ti(fi) = ai + bifi is
394 Informatica 40 (2016) 393–398 A. Krylatov et al.
travel time on congested arc i, i = 1, n. In the present
work we model travel time on a congested arc as the linear
function.
Let us formulate traffic assignment problem on network
of parallel routes as an optimization program [9, 10]:
z(f∗) = min
f
z(f) = min
f
n∑
i=1
∫ fi
0
ti(u)du, (1)
subject to
n∑
i=1
fi = F, (2)
fi ≥ 0 ∀i = 1, n. (3)
Wardrop’s first principle states that the journey times in
all routes actually used are equal and less than those that
would be experienced by a single vehicle on any unused
route [10, 11]. Traffic flows that satisfy this principle are
usually referred to as "user equilibrium" (UE) flows, since
each user chooses the route that is the best. On the network
of parallel routes UE is reached by such assignment f∗ =
(f∗1 , . . . , f
∗
n) as:
{
ti(f
∗
i ) = t
∗ > 0 when f∗i > 0,
ti(f
∗
i ) > t
∗ when f∗i = 0,
i = 1, n.
Thus, the mathematically formalized idea of UE (1)–
(3) can be used in reconstruction of traffic assignment on
the network between origin-destination pair. On the other
hand, if we know travel time t∗ between OD-pair, we are
able to reconstruct traffic demand F on the linear network
of parallel routes.
Without loss of generality we assume that routes are
numbered as follows:
a1 ≤ . . . ≤ an.
Theorem 1. Traffic demand F for a linear network of par-
allel routes can be obtained explicitly:
F = t∗
k∑
s=1
1
bs
−
k∑
s=1
as
bs
, (4)
where k satisfies
a1 ≤ . . . ak < t∗ ≤ ak+1 . . . ≤ an. (5)
Proof. Travel time t∗ on used routes is the Lagrangian mul-
tiplier that corresponds to the restriction (2) of optimization
program (1)–(3) [9, 12, 13].
Since goal function (1) is convex then the Kuhn-Tucker
conditions are both necessary and sufficient. Let us intro-
duce Lagrange multiplier µ for the flow conservation con-
straint (2) and multipliers ηi ≥ 0, i = 1, n for (3). The
Lagrangian for optimization problem (1)–(3) is
L =
n∑
i=1
∫ fi
0
ti(u)du+ µ
(
F −
n∑
i=1
fi
)
+
+
∑
i
ηi (−fi) . (6)
The derivative of Lagrangian (6) at variable fi has to be
equal to zero:
µ = ti(fi)− ηi.
Complementary slackness condition states that ηi · fi =
0. This equation holds when at least one of the variables is
zero. Thus, if fi > 0, then ηi = 0 and
µ = ti(fi) = ai + bifi. (7)
However, if fi = 0, then ηi ≥ 0 and
µ = ti(fi)− ηi = ai − ηi.
Hence, if ai ≥ µ then fi = 0. On the contrary, if we
express fi in terms of µ from (7) we get
fi =
µ− ai
bi
.
Therefore, if fi > 0 then
µ > ai.
Thus we are able to define the set of actually used routes
(routes with nonzero flows):
fi =
{ µ−ai
bi
when ai < µ,
0, when when ai ≥ µ,
i = 1, n. (8)
Without loss of generality, we could renumber routes in
such a way that a1 ≤ . . . ≤ ak < µ ≤ ak+1 ≤ . . . ≤ an.
Then, due to (2) and (8) we obtain
n∑
i=1
fi =
k∑
s=1
µ− as
bs
= F
and, consequently,
F =
k∑
s=1
µ− as
bs
.
Eventually, since µ is t∗ by definition, the theorem is
proved.
Therefore, if we know travel time of a vehicle on any
alternative route between OD-pair, appropriate traffic de-
mand can be uniquely reconstructed. Due to such re-
sults the developed approach seems to be promising. The
main idea of this method is based on the first principle of
Wardrop is as follows: if we define journey time of a ve-
hicle on any actually used route between certain OD-pair,
then we believe that journey time on all other used routes
is the same.
OD-matrix Estimation Based on a Dual Formulation of TAP Informatica 40 (2016) 393–398 395
Figure 1: The traffic in Saint-Petersburg city
3 Dual formulation of TAP
Generally, t∗ could be easily determined between any pair
of origin and destination on a real city road network. In-
deed, there are online services collecting information about
average travel speeds on all arcs of a city road network.
For instance, “Yandex.Traffic” based on “Yandex.Maps”
reflects the current road situation online (fig.1). Due to the
large scale databases this service is able to make statistical
predictions for different time periods and different days of
week. Average travel speed through any arc of road net-
work is in the public domain (fig.2).
Figure 2: Data from Yandex.Maps
Therefore, we can easily determine travel time through
the whole route between any pair of origin and destination,
using the information about average speed on the arcs. We
believe that road traffic is assigned according to the first
Wardrop principle. Thereby, if we estimate travel time
through the shortest route between OD-pair then we obtain
t∗ for this OD-pair. Note, that such information about road
network could also be useful for more efficient allocation
of resources by different companies [14].
Actually, due to information about equilibrium travel
time between OD-pairs we can estimate OD-matrix. In-
deed, let us refer to the duality theory of mathematical pro-
gramming.
3.1 Dual formulation of TAP for the
network of parallel routes
We introduce dual variables η = (η1, . . . , ηn) and define
dual traffic equilibrium problem for the network of parallel
routes:
max
η
n∑
i=1
θi(η),
with constraints
ηi ≥ 0, ∀i = 1, n,
where θi(η) for all i = 1, n satisfies the following opti-
mization program
θi(η) =
n∑
i=1
min
fi
(∫ fi
0
ti(u)du− ηifi
)
,
subject to
∑
fi = F.
It is proved that equilibrium assignment problem for a
network of parallel routes can be reduced to the fixed point
problem and is expressed explicitly [15]. Now let us prove
that the above mentioned bi-level program is really dual
TAP.
3.2 Dual formulation of TAP for a network
of general topology
Let us consider a network of general topology presented
by oriented graph G = (N,A). We introduce the follow-
ing notation: W is set of OD-pairs, w ∈ W , W ∈ N ;
Kw is the set of routes connecting OD-pair w; Fw is traf-
fic demand for OD-pair w, F =
(
F 1, . . . , F |W |
)T
; fwk
is traffic flow on the route k ∈ Kw, ∑k∈Kw fwk = Fw;
fw = {fwk }k∈Kw and f = {fw}w∈W ; xa is traffic flow on
the arc a ∈ A, x = (. . . , xa, . . .); ta(xa) is the link travel
cost on the arc a ∈ A; δwa,k is the indicator: 1 if acr a is
included in route k, 0 if otherwise.
User equilibrium on transportation networkG is reached
by such x∗ that
Z(x∗) = min
x
∑
a∈A
∫ xa
0
ta(u)du, (9)
subject to
∑
k∈Kw
fwk = F
w, ∀w ∈W, (10)
fwk ≥ 0, ∀w ∈W, (11)
396 Informatica 40 (2016) 393–398 A. Krylatov et al.
with definitional constraints
xa =
∑
w∈W
∑
k∈Kw
fwk δ
w
a,k, ∀a ∈ A. (12)
User equilibrium principle allows us to introduce t∗w, that
is equilibrium journey time for any OD-pair w.
Lemma. t∗w is the Lagrange multiplier in the optimization
program (9)–(12) corresponding to the constraint (11).
Proof. The Lagrangian of the problem (9)–(12) is
L =
∑
a∈A
∫ xa
0
ta(u)du+
∑
w
µw
(
Fw −
∑
k∈Kw
fwk
)
+
+
∑
w
∑
k∈Kw
ηwk (−fwk ) ,
where µw and ηwk ≥ 0 are Lagrangian multipliers, and dif-
ferentiation of the Lagrangian yields:
∂L
∂fwk
=
∑
a∈k
ta(xa)− µw − ηwk = 0.
Note, that according to complementary slackness
ηwk f
w
k = 0. Thus, for f
w
k > 0 the following expression
holds
∑
a∈k
ta(xa) = µw, ∀k ∈ Kw, w ∈W. (13)
Actually, left part of (13) is journey time on any used
route (fwk > 0) between OD-pair r. Therefore, proposition
is proved.
Eventually, according to the Lemma the following equal-
ity is true:
t∗w =
∑
a∈k
ta(xa) ∀k ∈ Kw, w ∈W.
Theorem 2. Dual mathemetical problem for a TAP, ex-
pressed by (9)–(12), is the following bi-level program:
max θ(T ) (14)
where θ(T ) is defined by
θ(T ) = min
f≥0
{∑
a∈A
∫ xa
0
ta(s)ds+
+
∑
w
tw
(
Fw −
∑
k∈Kw
fwk
)}
, (15)
subject to definitional constraints
xa =
∑
w∈W
∑
k∈Kw
fwk δ
w
a,k, ∀a ∈ A. (16)
Proof. We assume that x∗ is a solution of (9)–(12). We
introduce multipliers for the flow conservation constraints
(10) and (11). Indeed, according to Lemma, we can use
tw as Lagrangian multipliers for the constraints (10). The
Lagrangian for the problem (9)–(12) is
L(xa, tw) =
∑
a∈A
∫ xa
0
ta(s)ds+
+
∑
w
tw
(
Fw −
∑
k∈Kw
fwk
)
. (17)
If L(xa, tw) has a saddle point (x∗a, t
∗
w) in admissible
set, then x∗a is the solution of the problem (9)–(11), and t
∗
w
is the solution of the following optimization problem [16]:
max
T
L(x∗a, tw)
in case of
xa =
∑
w∈W
∑
k∈Kw
fwk δ
w
a,k, ∀a ∈ A,
where T = (t1, . . . , t|W |)T.
This duality relation holds when the theorem of equiva-
lence is satisfied [16].
4 OD-matrix estimation from plate
scanning sensors
Link-flow counts provide the amount of vehicles on the
links. Plate scanning sensors associated with the certain
links identify plates of vehicles from link-flow. Thus, when
any vehicle crosses a link with some sensor then sensor
records its plate number and fixation time. Eventually,
database consisting of {plate number, fixation time, num-
ber of sensor} is accumulated [3]. With the help of such
database the travel time between any origin-destination pair
can be evaluated directly. Indeed, one just has to know fix-
ation time of the vehicle in origin and fixation time in desti-
nation to define t∗w (as the difference between fixation time
in the destination and fixation time in the origin) for any
w ∈W .
Therefore, the following bi-level optimization program
can be formulated:
min
F
(
F − F
)T
U−1
(
F − F
)
+
+(T ∗ − T )T(T ∗ − T ), (18)
subject to
F ≥ 0, (19)
where T solves
max θ(T ), (20)
OD-matrix Estimation Based on a Dual Formulation of TAP Informatica 40 (2016) 393–398 397
when θ(T ) is defined by
θ(T ) = min
f≥0
{∑
a∈A
∫ xa
0
ta(s)ds+
+
∑
w
tw
(
Fw −
∑
k∈Kw
fwk
)}
, (21)
subject to definitional constraints
xa =
∑
w∈W
∑
k∈Kw
fwk δ
w
a,k, ∀a ∈ A. (22)
Here, (18) is the generalized least squares estimation and
F is the aprior volume of travel demand between all OD-
pairs, and U is the weighting matrix.
5 Computational experiment
Let us consider Saint-Petersburg road network (fig. 3). We
define seven origin-destination pairs with seven shortest
routes from seven periphery origins {1,2,3,4,5,6,7} to the
center destination {8}. According to STSI (State Traffic
Figure 3: Selected OD-pairs on the Saint-Petersburg road
network with the shortest routes
Safety Inspectorate), nowadays there are 253 plate scan-
ning sensors observing the Saint-Petersburg road network
(fig. 4). Due to these sensors, we are able to identify travel
time between chosen OD-pairs (table 1). The developed
approach is based on user equilibrium principle, which sug-
gests that value of travel time on the shortest route is travel
time on any actually used route. Moreover, we are able to
calculate aprior flows F using the gravity model [4].
Let us use these data as inputs for bi-level optimization
program (18)–(22). MATLAB was employed to carry out
the simulation. Results of simulation are presented in the
table 2. Moreover, these results are available in comparison
with aprior flows. Figure 5 gives a visualization of such
a comparison. One can see that rough aprior estimation
Figure 4: Sensors location on the Saint-Petersburg road
network
Table 1: Journey time obtained from plate scanning sensors
Route in OD-pair Travel time t∗/min
1–8 89
2–8 80
3–8 83
4–8 78
5–8 45
6–8 57
7–8 36
of trip flows, obtained by gravity model, was adjusted by
virtue of information about actual travel time between OD-
pairs. Therefore, approach introduced in this paper seems
to be quite useful.
Figure 5: Comparison of model and aprior flows
6 Conclusion
The present paper was devoted to the problem of OD-
matrix estimation. Original OD-matrix estimation tech-
nique based on a dual formulation of the traffic assign-
398 Informatica 40 (2016) 393–398 A. Krylatov et al.
Table 2: Comparison of model and aprior flows
OD-pair Aprior flow Model flow
1–8 5523 5910
2–8 12232 11253
3–8 6827 6295
4–8 6938 7631
5–8 5534 5080
6–8 4254 4650
7–8 3395 3202
ment problem was offered. Due to this technique traffic de-
mand estimation between certain OD-pair could be solely
based on the information about journey time. Since jour-
ney time is easily obtained from plate scanning sensors,
the developed technique has an obvious practical signifi-
cance. Moreover, explicit relationship between traffic de-
mand and journey time was obtained for the network of
parallel routes with one OD-pair. Such a result gives a
clear understanding of basis relationship between demand
and journey time. Eventually, the developed approach was
experimentally implemented to the Saint-Petersburg road
network, that demonstrates its effectiveness.
References
[1] Hazelton M. Inference for origin-destination ma-
trices: estimation, prediction and reconstruction //
Transportation Research Part B. 2001. No 35. P. 667–
676.
[2] Yang H., Sasaki T., Iida Y., Asakura Y. Estimation of
origin-destination matrices from link traffic counts on
congested networks // Transportation Research Part
B. 1992. No 26 (6). P. 417–434.
[3] Zakharov V., Krylatov A. OD-matrix estimation
based on plate scanning // 2014 International Con-
ference on Computer Technologies in Physical and
Engineering Applications (ICCTPEA). 2014. P. 209-
210.
[4] Medina A., Taft N., Salamatian K., Bhattacharyya S.,
Diot C. Traffic matrix estimation: existing techniques
and new directions // Computer Communication Re-
view – Proceedings of the 2002 SIGCOMM confer-
ence. 2002. No 32. P. 161–174.
[5] Castillo E., Menedez J. M., Jimenez P. Trip matrix
and path flow reconstruction and estimation based on
plate scanning and link observations // Transportation
Research Part B. 2008. No 42. P. 455–481.
[6] Bianco L., Cerrone C., Cerulli R., Gentili M. Locat-
ing sensors to observe network arc flows: exact and
heuristic approaches // Computers and Operation Re-
search. 2014. No 46. P. 12–22.
[7] Minguez R., Sanchez-Cambronero S., Castillo E.,
Jimenez P. Optimal traffic plate scanning location
for OD trip matrix and route estimation in road net-
works // Transportation Research Part B. 2010. No 44.
P. 282–298.
[8] Bierlaire M. The total demand scale: a new measure
of quality for static and dynamic origin–destination
trip tables // Transportation Research Part B. 2002.
No 36. P. 282–298.
[9] Krylatov A. Yu. Optimal strategies for traffic flow
management on the transportation network of paral-
lel links // Vestnik of St. Petersburg State University.
Series 10. Applied Mathematics. Computer Science.
Control Processes. 2014. No 2. P. 121–130.
[10] Patriksson M. The Traffic Assignment Problem:
Models and Methods. Utrecht, Netherlands: VSP,
1994. 223 p.
[11] Wardrop J. G. Some theoretical aspects of road traffic
research // Proc. Inst. Civil Eng. 1952. Vol. 1, No 3.
P. 325–362.
[12] Zakharov V. V., Krylatov A. Yu. Transit Network De-
sign for Green Vehicles Routing // Advances in In-
telligent Systems and Computing. 2015. Vol. 360.
P. 449–458.
[13] Zakharov V. V., Krylatov A. Yu. Competitive routing
of traffic flows by navigation providers // Automation
and Remote Control, 2016. Vol. 77, No 1. P. 179–189.
[14] Shavidze G. G., Balykina Y. E., Lejnina E. A.,
Svirkin M. V. Mathematical Model of Ambulance Re-
sources in Saint-Petersburg // Proceedings of the In-
ternational Conference on Numerical Analysis and
Applied Mathematics. 2015. Vol. 1738.
[15] Krylatov A. Yu. Network flow assignment as a fixed
point problem // Journal of Applied and Industrial
Mathematics. 2016. No 10 (2). P. 243-256.
[16] Belolipetskiy A.A., Gorelik V. A. Economic and
mathematical methods Moscow, Russia: Academiya,
2010. 368 p.