Bayesian network model for traffic flow estimation using prior link flows

Zhu Senlai Cheng Lin Chu Zhaoming

(School of Transportation, Southeast University, Nanjing 210096, China)

During the last decades, traffic flow estimation has become an important aspect of transportation planning. Two important problems in the traffic flow estimation field are: the origin-destination (OD) matrices estimation and the traffic assignment problems. The first one is to try to estimate the number of users traveling from each origin to each destination based on some link flow observations, while the second is to try to estimate how the OD flows disaggregate among different possible routes and links of the OD pairs.

The OD matrices estimation problem can be dealt with by many different methods, such as least squares[1]and generalized least squares[2]methods, entropy or information-based methods[3], and statistical-based methods. The statistical-based methods can be classified into classical methods[4]and Bayesian methods[5-10]. In statistical-based methods, the traffic flows are assumed to be multivariate random variables given some parametric families, such as Poisson, Gamma, multivariate normal, etc. And the parameters are considered as random variables themselves in Bayesian methods. The traffic assignment problem is primarily dealt with using two different methods: deterministic user equilibrium (DUE)[11-12]and stochastic user equilibrium (SUE)[13-14]. If the OD matrices estimation and traffic assignment are treated separately, some inconsistencies normally arise in the solutions of both problems. To remove these inconsistencies, several combined methods of the two problems have been proposed in Refs.[15-17].

More recently, Castillo et al.[6]proposed a Bayesian network (BN) model using prior OD flows for traffic flow estimation and then combined it with the multinomial logit(MNL) SUE model. In their Bayesian network, OD flows are assumed to be parents of link flows. Thus they need to give the relative weights of all OD flows with respect to the total traffic flow, as part of the inputs of the BN model. However, generally, for a real transportation network, the number of OD pairs can be very large. For example, in Chicago’s Regional Network, there are 12982 nodes, 39018 links and 2297945 OD pairs. It can be seen that the number of links is usually much smaller than the number of OD pairs and the relative weights of link flows are comparatively convenient to be obtained in a real traffic network. Based on these facts, we build a new Bayesian network using prior link flows, in which the link flows are parents of OD flows, and the relative weights of link flows with respect to the total traffic flow are part of the inputs of the BN model. Furthermore, to obtain an equilibrium solution, we combine the proposed BN model with a SUE model and give the procedures to solve it.

1 Proposed Bayesian Network Model

1.1 Model assumptions

Assumption1The vectorVof link flows is a multivariate normal random variable with meanμVand variance-covariance matrixΣV.

Assumption2The conditional distribution of each OD flowTigiven the link flows is a normal distribution:

To obtain the regression coefficientβia, we first consider the well-known conservation law equation:

(1)

Eq.(1) can be written as

(2)

V=DT

(3)

We do the following conversion of Eq.(3):

DTV=DTDT

(4)

Then, Eq.(4) can be written as

T=(DTD)-1DTV=(DTD)-1DTμV+

(DTD)-1DT(V-μV)

(5)

And it becomes clear that,

β=(DTD)-1DT,E(T)=μT=βμV

(6)

According to Eq.(5), we replace Assumption 2 by the following assumption.

Assumption3The OD flows are given by

T=βV+ε

(7)

whereε={ε1,ε2,…,εn} are the mutually independent normal random variables and represent the OD flows apart from those used in the links of the considered network.

Note that all the link flows are correlated. Their values vary randomly with the vacation time, commute time and special weather conditions, etc. In order to represent these correlations, we make the following assumption.

Assumption4The link flows are given by

Va=kaU+ηa

(8)

1.2 Complete model

According to all the assumptions, all the random variables involved in our model are related by the linear expression:

(9)

The meanE(U,η,ε,V,T) is

(10)

And the variance-covariance matrixΣ(U,η,ε,V,T)is

(11)

whereDεis the variance matrix ofε, andDηis the variance-covariance matrix ofη.

Then, we obtain the joint probability density (JPD):

f(V1,V2,…,Vm;T1,T2,…,Tn)=

(12)

The probability can be updated by using the joint distribution of OD and link flows conditioned on the available information. And we can solve the following planning to obtain point estimations, whose results are normally the conditional means:

(13)

whereV0is the subset ofVand represents the observed component ofV.

2 Combined BN and SUE model

Note that the proposed BN model needs to know the route choice proportions. If combining this model with traffic assignment models, such as SUE, we can easily obtain the proportion values from the SUE model and iterate until convergence. In this paper, we use the MNL model as a representative. The procedure of the combined method is given as follows:

Step1Initializing the model. FromE(U) and matrixK, we obtain the initial link flow vectorV={V1,V2,…,Vm}=KE(U). Then we can obtain the initial route choice proportionpikusing the formulas:

(14)

(15)

(16)

Step2Solving the BN model. After knowing the proportion matrixP, we can obtain the OD matrixTand the link flow vectorVusing the formulas:

β=[(Pδ)TPδ]-1(Pδ)T

(17)

E(V)=KE(U)

(18)

E(T)=βE(V)+E(ε)

(19)

Dη=Diag(vE(V))

(20)

(21)

ΣVT=ΣVVβT

(22)

ΣVT=ΣTV

(23)

ΣTT=βΣVVβT+Dε

(24)

(25)

(26)

E(Z|Z=z)=z

(27)

ΣZ|Z=z=0

(28)

T=E(Y|Z=z)|(Y,Z)=T

(29)

(30)

(31)

(32)

(33)

Step5Updating. We can update the route choice proportions and matrixKusing the following formulas:

(34)

(35)

and go to Step 2.

Eqs.(14) and (31) are the link cost functions. Eqs.(15) and (32) are the cost functions associated with routekof the OD pairi. Eqs.(16) and (33) are the Logit route choice proportion formulations. Eq.(17) defines the regression coefficient matrix. Eqs.(18) and (19) define the means ofVandT. Eq.(20) defines the diagonal variance matrix ofη;i.e.,varηa=(E(va)ν)2, wherevis the coefficient of variation. Eqs.(21) to (24) define the variance-covariance matrix in (14). Eqs.(25) and (26) are the updating equations for the means and variance-covariance matrix of the unobserved variables, whereYandZrefer to the unobserved and observed components of (T,V), respectively. Eqs.(27) and (28) state that the values of the observed variables are their observed values and their variances and covariances are null. Eq.(29) takes the means as point estimations for the OD and link flows. Eq.(30) is the conservation law equation. Eq.(34) is for updating route choice proportions, whereρ(0<ρ<1) is a relaxation factor. Eq.(35) is for updating matrixK.

3 Numerical Examples

Fig.1 The numerical traffic network

Fig.2 Bayesian network associated with the numerical traffic network

Using the data above to solve the combined BN and the SUE model, we can give the point estimations of traffic flows (including OD flows and link flows) after updating the evidences one by one. Tab.1 shows how the means (point estimations) of traffic flows change after updating the evidences one by one. It can be seen that onceV2becomes known andV3is also known (boldfaced in the table) due to the conservation laws. Similarly, after knowingV6,V7is also known.

Fig.3 illustrates how the marginal densities of OD flows evolve from their initial form to their final form with the increasing evidences. It can be seen that the variances normally decrease with the increasing evidences. By these marginal densities, we can easily obtain the probability intervals of the point estimations respectively. It can be seen that the proposed combined model provides the conditional distributions of all the variables given some evidences; i.e., it supplies complete statistical information about them, including point estimations and the corresponding probability intervals. Finally, in order to compare the results with those using the method of Castillo et al.[6], the OD flows of both methods are shown in Tab.2. Note that they are basically the same. This is to be expected, because of the same normal distribution assumptions for the traffic flows.

Tab．1 Point estimations of traffic flows

Fig.3 Conditional distribution of OD flows after updating evidences one by one. (a) T1; (b) T2; (c) T3;(d) T4;(e) T5; (f) T6

In the proposed method, link flows are parents of the OD flows, while the OD flows are parents of link flows in Castillo’s method. Therefore, the proposed method requires the knowledge of the relative weights of link flows with respect to the total traffic flow, while Castillo’s model requires the knowledge of the relative weights of OD flows. In fact, generally, for a network, the number of links is much smaller than the number of OD pairs. For example, in the numerical network, for the sake of illustrating, we only sample 6 OD pairs. But in fact, the numerical network is supposed to have totally 36 OD pairs due to its 9 nodes, while it has only 12 links. Another example, in Chicago’s Regional Network, there are 12982 nodes, 39018 links, while it has 2297945 OD pairs which is really a large number and much bigger than the number of links. So it is more convenient to obtain the relative weights of link flows with respect to the total traffic flow. In addition, the proposed model does not need to really assign traffic flows by solving the SUE model and we just use the well-known route choice proportion formulation instead. But Castillo’s method needs to make traffic assignment to obtain an initial solution. In other words, the proposed method is much easier to solve. Due to this advantage, the proposed model can almost use any existing SUE model easily, in which the only difference lies on the route choice proportion formulation. Moreover, if DUE models can be modified to get uniqueness and can provide route information, the proposed BN model can also be combined with them.

Tab．2 OD flow estimation

4 Conclusion

A comparison in the example shows that the estimates of the proposed method and Castillo’s method are basically the same. The proposed method needs the relative weights of link flows with respect to the total traffic flow, while Castillo’s method needs the relative weights of OD flows. Due to the fact that generally the number of links is much smaller than the number of OD pairs, the proposed method is more convenient. Meanwhile, the proposed model does not need to really assign traffic flows by solving the SUE model and just uses the route choice proportion formulation instead. But Castillo’s method needs to make traffic assignment to obtain an initial solution. So the proposed method is easier to solve. Similar to Castillo’s method, the proposed method can provide not only point estimations but also the corresponding probability intervals.

[1]Doblas J, Benitez F G. An approach to estimating and updating origin-destination matrices based upon traffic counts preserving the prior structure of a survey matrix [J].TransportationResearchPartB,2005,39(7): 565-591.

[2]Parry M, Hazelton M L. Estimation of origin-destination matrices from link counts and sporadic routing data [J].TransportationResearchPartB, 2012,46(1): 175-188.

[3]Xie C, Kockelman K M, Waller S T. A maximum entropy-least squares estimator for elastic origin-destination trip matrix estimation [J].TransportationResearchPartB, 2011,45(9): 1465-1482.

[4]Lo H P, Zhang N. Estimation of an origin-destination matrix with random link choice proportions: a statistical approach [J].TransportationResearchPartB, 1996,30(4): 309-324.

[5]Sun S L, Zhang C S, Yu G Q. A Bayesian network approach to traffic flow forecasting [J].IEEETransactionsonIntelligentTransportationSystems, 2006,7(1): 124-132.

[6]Castillo E, Menéndez J M, Snchez-Cambronero S. Predicting traffic flow using Bayesian networks [J].TransportationResearchPartB, 2008,42(5): 482-509.

[7]Perrakis K, Karlis D, Cools M, et al. A Bayesian approach for modeling origin-destination matrices [J].TransportationResearchPartB, 2012,46(1): 200-212.

[8]Wang Jian, Deng Wei, Zhao Jinbao. Short-term freeway traffic flow prediction based on improved Bayesian combined model [J].JournalofSoutheastUniversity:NaturalScienceEdition, 2012,42(1):162-167. (in Chinese)

[9]Wang Jian, Deng Wei, Zhao Jinbao. Short-term freeway traffic flow prediction based on multiple methods with Bayesian network [J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2011,11(4):147-153.

[10]Xianyu Jianchuan, Juan Zhicai, Zhu Taiying. Travel choice analysis by Bayesian networks [J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2011,11(5):167-172.

[11]Xu M, Qu Y, Gao Z. Implementing Frank-Wolfe algorithm under different flow update strategies and line search technologies [J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2008,8(3): 14-22.

[12]Bar-Gera H. Origin-based algorithm for the traffic assignment problem [J].TransportationScience, 2002,36(4): 398-417.

[13]Zhou Z, Chen A, Behkor S. C-logit stochastic user equilibrium model: formulations and solution algorithm [J].Transportmetrica, 2012,8(1): 17-41.

[14]Abbe E, Bierlaire M, Toledo T. Normalization and correlation of cross-nested logit models [J].TransportationResearchPartB, 2007,41(7): 795-808.

[15]Fisk C. On combining maximum trip estimation with user optimal assignment [J].TransportationResearchPartB, 1988,22(1): 69-79.

[16]Yang H. Heuristic algorithm for the bi-level origin destination matrix estimation problem [J].TransportationResearchPartB, 1995,29(1): 1-12.

[17]Maher M, Zang X, Van Vliet D. A bi-level programming approach for trip matrix estimation and traffic control problems with stochastic user equilibrium link flows [J].TransportationResearchPartB, 2001,35(1): 23-40.