The knowledge of urban mobility patterns is important to maintain good public services as well as to improve city planning. These mobility patterns can be characterized by using expensive fieldwork or analyzing the huge amount of data available from services and environmental monitoring in smart cities. The origin-destination matrix estimation (ODME) aims to estimate the traffic of vehicles between origin and destination areas in the city of OPorto in Portugal from traffic observed from sensors installed at roads. This estimation is stated as an optimization problem and solved by linear programming. The results have shown that the number and location of sensors are important issues to be considered.
The origin-destination matrix (ODM) contains information about flow of vehicles
between two geographical areas in a city. Let assume that there are n origin-destination
(OD) pairs with a flow qw of vehicles in a particular pair w 2 W (the set of
all OD pairs). These OD pairs are usually located at the borders of a region
[
The origin-destination matrix estimation (ODME) can be considered as a dual
problem of the static traffic assignment (STA) [
The flow of vehicles va in a link a is given by (1). It is the sum of n flows qw multiplied by a given probability pwa of using link a by an OD pair w. Additionally, (2) is a non-negativity constraint of qw.
va = X
qw.pwa w2 W qw
0 8 z (vz ⇡ vz) 8 w (qw ⇡ qw)
By assuming that a link z is monitored by sensors, an estimate vz of the flow of vehicles in z should approximate the measured flow vz according to (3). Similarly, qw is approximated to qw according to (4).
According to [
The network sensor location problem (NSLP) concerns how to define the location and
number of sensors. In [
The article [
In our work, R1 is considered by default. The other rules R2, R4, R7 are tested
separately. Differently from [
The following metrics are used to evaluate ODME: mean absolute error (MAE), root mean square error (RMSE), total demand deviation (TDD), and determination coefficient (R2) according to (5), (6), (7), and (8), respectively. (5) (6) (7) (8) M AE =
P w2 W |qw n
qw| RM SE = T DD = | r 1 P n w2 W (qw Pw2 W qw
qw)2 P w2 W qw
Pw2 W qw
P w2 W qw| R2 = ( p(n Pw2 W qw2 n(Pw2 W qwqw) (Pw2 W qw)(Pw2 W qw) (Pw2 W qw)2)(n Pw2 W (qw)2 (Pw2 W qw)2) )2
Both MAE and RMSE are error metrics used to evaluate differences between observed and real flows of OD pairs. On other hand, TDD is an error related to the sum of observed and real OD flows. All these metrics should be minimized for good results.
The determination coefficient R2 evaluates the proportion of the variance in the dependent variable (estimated OD flows qw) that is predictable from the independent variable (real OD flows qw) variance, resulting in a output between 0 and 1. The dependence between observed and estimated values is greater as R2 ⇡ 1. in this case, R2 should be maximized.
The ODM is composed by n decision variables representing the traffic flows of n
OD pairs. The MILP model for ODME presented here is similar to the one of
[
Variables are shown in Table 1. There are (np + 3 · ns) variables. Decision variables are qw, estimated flows in links are vz, and Fz+ and Fz are variables used to quantify matching errors. The cost function is represented by (9).
Equation (10) requires that a probability pwz of flow qw should use link z. Each observable link has a restriction of this kind.
Equation (11) sets a matching between the observed and estimated traffic in link z. Fz is positive when the estimated values are larger than the observed ones and Fz+ is on the other way around. This restriction acts with (9) and (10) in order to find vz ⇡ vz by adjusting qw decision variables.
vz = (vz + Fz+
Fz )
Restriction (12) is based on the non-negativity constraint specified in (2). values.
Restrictions (13) and (14) indicate that Fz+ and Fz+ are bound to non-negative For every link sensor, there is a restriction as in (11), (13) and (14), and for every qw, there is a restriction as in (12).
min X(Fz+ + Fz ) qw z2 Z vz = X w2 W
pwz · qw qw
0 Fz+ Fz 0 0
Section 4.1 describes the data used to the ODME problem formulation. Section 4.2 shows results for ODME using MILP and different numbers of sensors.
In this work, data comes from the taxi trip database found in [
The [
The geographic database [
The experiments have been made from 200 to 2000 virtual sensors with locations defined by rules R2, R4, R7 or R4R7. The number of sensors was increased by 100 between 200 and 500 sensors, and by 250 for more than 500 sensors.
According to Fig. 1 (MAE), rule R7 yields better results for any number of sensors except 1500 sensors. Particularly, for less than 1500 sensors. The gap between R7 and R4R7 or R4 is reduced for a large number of sensors. R4R7 has the worst result for 200 sensors, but it is better than R4 until 1500 sensors, where R4 is better. R2 has the worst result for every number of sensors except for 200 sensors. The results for R2 are close to
R4 and R4R7 for small number of sensors but R4 and R4R7 are better for a larger number of sensors than R2.
In Fig. 2 (RMSE), R7 has better results for 200 sensors and between 400 and 1250 sensors. Results for R7 are worse for 300 sensors than for 200 sensors which is unexpected since the result was worse with more information added. R4R7 has better results for 300 sensors, and R4 has better results for 1500 sensors and above. R2 has the worst result for any number of sensors, showing a slightly decline in RMSE from above 400 to close to 330 for 200 and 2000 sensors, respectively.
Fig. 3 (R2) has a similar information of Fig. 2. R7 also has better results for 200 sensors and between 400 and 1250 sensors in this metric. Results for R7 are also worse for 300 sensors than for 200 sensors. R4R7 has better results for 300 sensors, and R4 has better results for 1500 sensors and above. R2 has the worst result except for 200 or 300 sensors.
Fig. 4 (TDD) shows different behavior when compared to the three previous analysis. R4R7 has better results most of the time. R4, R7, and R4R7 are close to zero between 400 and 800 sensors, while the minimum TDD value for R2 occurs with 1000 sensors, which is exactly the number of sensors used in Section 4.2.
R7 has the better results in RMSE and R2 metrics between 400 and 1250 sensors. It has the better results for any number of sensors except with 1500 sensors for MAE as well as the better results in TDD for 1500 sensors and above. R4 is better above 1250 sensors for RMSE and R2. R4R7 is only better for TDD between 300 and 750 sensors, and with 300 sensors for RMSE.
This work presented the effects of using different rules of distribution of sensors at roads of Oporto in Portugal in the quality of ODME. The quality of ODME was evaluated by four different metrics: MAE, RMSE, TDD and R2. The better set of rules may vary depending on the number of sensors and metrics used. For MAE, RMSE and R2 metrics, experiments with more sensors produced better results using any set of rules. TDD is better mainly between 400 and 800 sensors, but it presents poor results after 1000 sensors. Rule R7 is better for two metrics and any number of sensors except for 300 sensors. For 1500 sensors and above, R4 has better results for metrics RMSE and R2 but R7 has better results for the other two metrics, i.e., a tie occurs between R4 and R7. For 300 sensors, the best performing set of rules was R4R7 in three of four metrics.
For future work, the introduction of probe vehicles could add information to improve ODM and assignment matrix estimations. The influence of number and location of sensors can also be analyzed for other ODME techniques as for instance general least squares.