EUROPEAN JOURNAL OF OPERATIONAL RESEARCH ELSEVIER
European Journal of Operational Research 106 (1998) 108115
Theory and Methodology
Estimating the urban OD matrix: A neural network approach Zhejun Gong Department of Management, Shenzhen University, Shenzhen, Guangdong 518060, PR China
Received 2 July 1996; accepted 17 March 1997
Abstract
In this paper, the Hopfield Neural Network (HNN) model is used to estimate the urban OrientationDestination (OD) distribution matrix from the link volumes of the transportation network, so as to promote the solving speed and precision. © 1998 Elsevier Science B.V. Keywords: Hopfield Neural Network; Transportation
1. Introduction It is known that the urban transportation network is very important to the development of the city. If the transportation network is suitable to the city, it can provide a good condition for the city development, otherwise it will lead to a decrease in the economic and social efficiency in many aspects of the city. The OrientationDestination (OD) distribution is important data for the design and reconstruction of the city, and modem cities now put great energy on it. By traditional methods, the OD matrix can be obtained through collecting the data of every urban zone, but it needs great financial and technological support and the results may be not precise, so it may lead to wrong decisions for the development of the city [3]. It is easy to get the urban link volumes of the transportation network through traffic counts, and it is feasible for us to build mathematical models based on link volumes through which we can gain the OD matrix. The optimization mathematical model is relatively concise and useful, but with the increase of the urban zones' number, the number of variables that needs to be solved increase very quickly, so the model may consume a lot of computer resources and need a lot of running time. The running time of this mathematical model is so long that it is unendurable to run the model on the personal computer, so it confines the optimization mathematical model to be used in practical activities [46,8]. The Hopfield Neural Network (HNN) is used to solve TSP problem (Travelling Salesman Problem), and this creates a new area for the optimization: neural optimization. The Hopfield Neural Network can realize quick computation and parallel distribution processing, and it is estimated that the Hopfield Neural Network may become an important technique to solve NP difficulties [1,2]. In this paper, HNN model is used to estimate the urban OD distribution matrix. 03772217/98//$19.00 © 1998 Elsevier Science B.V. All rights reserved. PH S03772217(97)001628
Z. Gong/ EuropeanJournalof OperationalResearch106 (1998)108115
109
2. Mathematical model for estimating OD matrix from link volumes The basic idea of building mathematical optimization model to estimate the OD distribution from transportation from transportation network link volumes is that the transportation link volumes are formed by the OD distribution among the urban zones. After we know the network link volumes, we can obtain the urban OD distribution matrix through solving the mathematical optimization model. Some important points of the urban transportation network, such as bus stops or route intersections, and so on, can be defined as the network nodes. After the city has been divided into many small zones, it can be considered that the OD activities of the zone residents happen at the nearest node to that zone. Suppose that the route m from node i to node j passes through link r, that is to say that the route m is connected by link r~ . . . . r . . . . . r,. Because the link volume is formed by the OD distribution among urban zones, we can build the mathematical model (P1) as follows:
min
~r ( ~ j ~ s Xsj']ZsjmOr
subject to
X~j > O.
~s (j~s Xsj Os
(Pl)
Usj,,
In the (Pl) model, some nodes are given: O s is the total OD value of zone s; O r is the volume of link r; is the distribution coefficient of the OD value in route m from zone s to zone j which passes through link r; and X,j is the OD value from zone s to zone j. The above model is a constrained nonlinear optimization programming model. Sometimes in order to be convenient, the second part of optimization goal in model (P1) can be omitted. So we can have 2
min
~(~s j~X,~. •
subject to
Xsi > 0,
~sjrn  Or)
(P2)
X~j = Xjs.
The meaning of each variable and each constant in (P2) is the same as that in model (P1). Now we discuss how to value U,i,,. We define
Or.,.
=
/ 5 1 PSJmlm
(l)
and we define P~/,. = e x p ( 
U,j,,
=
Ate:..), so we can have
exp(  At,j,.)
/:
e x p (  At,ira, )
=1
1
=
(2)
M
1+
•
mr= 1 mP~m
e x p [  A ( t ~ j , , ,  t ~ j m ) ].
Here in formula (2), we have M is the total number of routes to be distributed from s to j; t~j,. is the travelling time of route m from s to j; A is a positive constant; and m is one of the route to be distributed from s to j. From formula (2), the value of Us;m can be calculated.
Z. Gong/European Journal of Operational Research 106 (1998) 108115
110
3. Using H N N model to estimate OD matrix The Hopfield Neural Network model is
du i
Ui
c dt =
R
(Vi=g(ui),
N
+ l i + E T/Yj, jffil
(3)
i = 1 , 2 . . . . . N.
Here in formula (3), T/j is the connection weight value between node 1 and node j, and T/j = Tji; g ( . ) is a function with g ' ( . ) > 0; Ui is the input of node 1; V; is the output of node I; I; is the constant value of node I; C is a positive constant; and R is a positive constant. Formula (3) can be abbreviated to be
=li+ Vi
T/yj,
g(ui) ,
=
(41
i = 1,2 . . . . . N.
It can be proved that when the energy function of system (4) is l
E=
__
2
N
U
N
~_~ ~_. T/jViVj y" Vii i i=1 j=l
i=1
we can have dE _<0 dt and only when d V i / d t = O, d E / d t = 0 (i = 1,2 . . . . . N). The stable state of system (4) is the local minimum of the above energy function. The computation processor of system (4) is a process to find the local minimum in fact, the goal function is the above energy function of system (4). In fact, in the following discussion, it is unnecessary that T/j is the same as Tji, and we define T= [T/j].x.,
l=[liL×,,
U=[Ui].x,,
V = [ V i ] . × ,.
Theorem 1. If T is unsingular and for arbitrary positive value ~, we have
~~ T,.jej < O,
i = 1,2 . . . . . n,
jffil
then V * =  T  II is the stable point of system (4). Proof. As for V * =  T  l I, we have TV *   I , so du* =TV* dt
+I=0.
And for arbitrary e i > 0 (i = 1,2 . . . . . n) d ( u ; ~ Ei) = ~ TiJg(u; + ooj) ~ I i. dt j=l
Z. Gong~EuropeanJournal of OperationalResearch 106 (1998) 108115
111
According to Talor's theorem, we know 1
g ( u ; + e j ) = g ( u ; ) + ~jg'(u; ) +~g"( h ) ~ f , where A ~ (u~, u; + ej). The last part can be omitted, so
g ( u ; + s ; ) = g ( u ; ) + e;g'(u; ). Because g ' ( . ) > 0, so
d(u;
= z1=1
dt
(6)
In the same way, it can be proved that
~:j)
d(ui*
> 0.
dt
(7)
j=l
So, according to formula (5), (6) and (7), we can know that V *
is the equilibrium state of system (4).
[]
T h e o r e m 2. If T is unsingular and for arbitrary positive value ~, L Toej<0,
i = 1 , 2 . . . . . n,
j=l the function g(.) has the lowest bound m, let Vi* = [  T  1 I ] i, and if Vi * < m, then system (4) is asymptotic stable. Proof. Because m < g(u i) and Vi = g(ui), so Vi _> m, i = 1,2 . . . . . n. If Vi* >_m, from Theorem l, we can know that Vi* = [  T  l I ] i is the stable state of system (4). If Vi* < m, let ~i = Vi  Vi * , then we have du i dt
= L rij(Vi* "["~i) + l i < O j=~
and dVi
,
dui
dt = g (u')Y/t < 0" So, system (4) is asymptotic stable, and V; converges to m
Kl.
T h e o r e m 3 [7]. lf Tq < O, g ' ( u i ) > 0, g ( u i) has bound, and
T. + ~ ITql<0,
I = 1,2 . . . . . n,
j~l j4=i
then system (4) is asymptotic stable. As for model (P1), we define the energy function of the computation processor to be
Z. Gong/European Journal of Operational Research 106 (1998) 108115
112 then we have ,
=
r
+
jC*s
r
~ j¢'s
Let
d Xs~j,
OE
dt
OXsd I '
because Xs,j, >_ 0, so we define g(x)=
x>O, x<0.
x, 0,
We can gain the necessary parameters to build the HNN model. These parameters are given below:
T(,.j.X,j ) =  ~_,2Usj m • usd 7
s 4: s~, j 4: s, Jl 4: sl;
r
Ttsd,×sj) = TtsjXs,j,), Tcs,j,×s0 =  2 ( ~ r
s 4: s l , j 4: s, Jt 4: sl;
U s , ' ' U s l , ? + l ),
j4:s, jt4:Sl;
T(s~j.XsO = T(sCXs,j~),
J4: SL, Jl 4: Sl;
l(sljl) = 2( ~ Or " Us,j~, l Osl ) ,
j, 4: S, .
AS for model (P2), there are
T(sd, ) =  ~_, 2usj ~ • us,jr,
j 4: s, jj 4: Sl'~
r
T(stjiXsj ) = T(sjXs,j,),
j 4 : s, Jl 4: st;
I(,lJl)= 2 E OF" ~'~sIj~, r
j[ 4: S 1•
After the above discussion, it is easy to build the HNN model to estimate the OD distribution matrix.
4. An example In order to illustrate how to estimate the OD matrix by the HNN model, we run a simulation experiment on the computer. Suppose that there is an urban transportation network having four small zones, they are A, B, C and D. This network has five nodes, which is shown in Fig. 1. The resident OD time distributions are given in Table 1. The link volumes are shown in Table 2.
ol/\l Fig. 1. An exampleof urban transportationnetwork.
Z. Gong~European Journal of Operational Research 106 (1998) 108115
113
Table 1 OD time distribution time
node
node
1
2
1
3
4
8
2 3 4 5
8
5
7
5
10
6 4 8
5 5
7 5
10 4
6
8
To be convenient, the OD distribution between small zones adopts the allornothing method (minimum travel time method), which the OD value between two zones is distributed in the shortest route connecting these zones. According to model (P2), there is min
( gAB + XBA
+ ( SAC + subject to X~j > 0,


10) 2 + ( XAD + XDA
XCA 


7) 2 + ( XDC + XCD  8) 2 + ( XBC + XCB  6) 2
7) 2 + ( SAC + XCA  5) 2 + ( XBD + XDB  3) 2 + ( XBD + XDB  4) 2
Xsj = Xjs,
s = A , B , C , D ; j v~ s.
So we can establish the H N N model to be
dUBA
dUAB dt
2XA~  2XBA + 2 0 ,
dt
dUAD dt
2XBA + 20;
dUDA = 2XAD  2XDA + 14,
dt
dutx:
dt
2XAB
= 2XDA  2XAD + 14;
duct)
2X°c2XcD+I6'
dt
2XDc
2 X c ° + 16;
duBc  =   2 X B c  2XcB + 12, dt
ducB  =   2 X B c  2 X c a + 12; dt
d uAc dt' =4XcA4XcA
d UcA dt =4XAc4XcA
+24'
dUBD dt
+24;
dUDB = 4XBD  4XDB + 14,
[ u~j, X ~ j = g ( u s i ) = i~o '
dt
= 4XDB  4XBD + 14.
u~j >_ 0 usJ< 0
xsj=xjs,
s=A,B,C,D;j=A,B,C,D;jv~s.
According to Theorem 3, we can know that the above system is asymptotic stable. W e use Euler's method to solve the above example in the computation processor, and the length of step is 10  a . Table 2 Link volume between nodes Node 12 21
23 32
34 43
14 41
15 51
25 52
35 53
45 54
Volume
6
8
7
7
3
5
4
10
114
Z. Gong/European Journal of Operational Research 106 (1998) 108115
Table 3 Experiment 1 Initial input: all are 10 E n e r g y function value: 2 . 5 0 0 0 0 4 Output
XDC = XCD = 4 . 0 0 0 5 9 6 SAC = XCA = 3 . 0 0 0 1 4 9
XAD = XDA = 3 . 5 0 0 2 9 8 XBC = XCB = 3 . 0 0 0 2 9 8 XBD = XDB = 1.750075
gAB = XBA = 4 . 9 9 9 4 0 4 XDC = XCD = 3 . 9 9 9 7 0 2 XAC = XCA = 2.999851
XAD = XDA = 3 . 4 9 9 7 0 2 XBC = XCB = 2 . 9 9 9 7 0 2 XBD = XDB = 1.749925
XAB = XBA = 5 . 0 0 0 0 0 0
X^D = XDA = 3 . 5 0 0 2 9 8 XBC = XCB = 3 . 0 0 0 2 9 8 XBD = XDB = 1.750075
gAB = XBA = 5 . 0 0 0 5 9 6
Table 4 Experiment 2 Initial input: all are 0 E n e r g y function value: 2 . 5 0 0 0 0 3 Output
Table 5 Experiment 3 Initial input: all are 5 E n e r g y function value: 2 . 5 0 0 0 0 2 Output
XDC = XCD = 4 . 0 0 0 5 9 6 S A C = XC A = 3 . 0 0 0 1 4 9
Table 6 Experiment 4 Input
XAB = XBA = 1 . 0 0 ( 0 ) ~ XDC = XCD = 3 . 0 0 0 0 0 0
XAC = XCA = 5 . 0 0 0 0 0 0 E n e r g y function value: 2 . 5 0 0 0 0 3 Output
XAe = XBA = 4 . 9 9 9 4 0 4
Xt~c = Xco = 3 . 9 9 9 7 0 2 XAC = XCA = 3 . 0 0 0 1 4 9
XAD = XDA = 2 . 0 0 0 0 0 0 XBC = XCB ~ 4 . 0 0 0 0 0 0 XBD = XDB ~ 6 . 0 0 0 0 0 0
XAD = XDA = 3 . 4 9 9 7 0 2 XBC = XCB = 3 . 0 0 0 2 9 8 XBD = gOB = 1.750075
Table 7 Experiment 5 Input
XAB
SAC = XCA = 2 . 0 0 0 0 0 0
XAD = XDA ~ 5 . 0 0 0 0 0 0 XBC = XCB = 3 . 0 0 0 0 0 0 XBD = XDB = 1.000000
gAB = XBA = 5 . 0 0 0 5 9 6 XDC = XCD = 4 . 0 0 0 0 0 0 XAC = XCA = 2.999851
XAD = XDA = 3 . 5 0 0 2 9 8 XBC = XCB = 3 . 0 0 0 0 0 0 XBD = XDB ~ 1.749925
= XBA = 6.000000
XIDC = XCD = 4 . 0 0 0 0 0 0
E n e r g y function value: 2 . 5 0 0 0 0 2 output
115
Z. Gong/European Journal of Operational Research 106 (1998) 108115
Table 8 Comparison of the running time (step length: 0.0001; time unit: s) Experiment
1
2
3
4
5
HNN model Euler's model
2.4 330
2.3 310
2.2 285
2.2 285
2.1 270
The outputs of the HNN model are given in Tables 3  7 , the comparison of the HNN model to Euler's method is given in Table 8. In order to check the accuracy of the results, the OD values in Tables 3  7 are distributed to the transportation network in Fig. 1 by the allornothing method. It shows that using the H N N model to estimate the OD distribution matrix is feasible. On the other hand, the parameters needed to build the electrical circuit solving system of the HNN model are given out, so it is easy to build electrical circuit solving system, and then the OD matrix can be gained quickly and accurately. Thus the difficulties in the traditional optimization mathematical model can be overcome.
5. Conclusion The optimization mathematical model to estimate the OD distribution from link volumes is difficult to be applied because of its slow solving speed on the computer. But the neural network has the ability of quick computation, parallel distributed processing and electrical realization, so it is expected to overcome the difficulties in the traditional optimization model. The HNN model has the ability of quick computation and finding the global optimal solution to the problems to be solved, and the simulation experiment of using it to estimate the OD distribution is satisfactory.
References [1] Y.H. Pao, Adaptive Pattern Recognitionand Neural Networks, AddisonWesley,Reading, MA, 1989. [2] S.V.B. Aryer et al., A theoretical investigationinto the performance of the Hopfield model, IEEE Transactionon Neural Network 1 (2) (1990). [3] W.W. Hay, An Introductionto TransportationEngineering,John Wiley and Sons, New York, 1977. [4] H.J. Vanzuylen,L.G. Willumsen,The mos! likely trip matrix estimated from traffic counts, TransportationResearch 14 (1980) 281293. [5] S. Nguyen, Estimatingan OD matrix from network data: A network equilibriumapproach, PublicationNo. 87, Centre de Recherche sur les Transports, Universityof Montreal, Montreal. [6] L.G. Willumsen, OD matrices from network data: A comparison of alternativemethods for their estimation,in: Proceedingsof PTRC Summer Annul Meeting, 1978 Seminar in Transport Models, PTRC EducationResearch Services Ltd, London. [7] X. Liao, The stability of Hopfield neural network, Science in China A (Scientia Sinica) 23 (10) (1993). [8] Y. Iida, J. Takayama, Comparative study of model formulationon OD matrix estimationfrom observed link flows, in: Proceedingsof 4th World Conference on TransportationResearch, vol. 2, 1986.