J. Software Engineering & Applications, 2009, 2: 344-349
doi:10.4236/jsea.2009.25045 Published Online December 2009 (http://www.SciRP.org/journal/jsea)
Copyright © 2009 SciRes JSEA
Research on OD Matrix Calculation Based on
Quantum Behaved Particle Swarm
Optimization Algorithm
Lianyu WEI, Jianfu DU
Institute of Civil Engineering, Hebei University of Technology, Tianjin, China.
Email: {wly57, batdujianfu}@126.com
Received June 20th, 2009; revised August 25th, 2009; accepted September 2nd, 2009.
ABSTRACT
Traffic information is so far less than the number of OD variables, that it is difficult to obtain the satisfactory solution.
In this paper, a method based on Quantum behaved Particle Swarm Optimization (QPSO) algorithm is developed to
obtain the global optimal solution. It designs the method based on QPSO algorithm to solve the OD matrix prediction
model, lists the detailed steps and points out how to choose the PSO operator. Moreover, it uses MATLAB program-
ming language to carry out the simulation test. The simulation results show that the method has higher efficiency and
accuracy.
Keywords: OD Matrix Prediction Model, QPSO, Simulation Analysis, Optimal Design
1. Introduction
The traffic between import and export at the intersection
is an important data for urban traffic management and
control, and also impacts on the control of traffic lights at
the intersection directly. Therefore, how to obtain accu-
rate intersection OD and avoid the time-delay of control
and decision-making system are very important issues. As
the OD matrix calculation based on traffic has advantages,
such as convenience, rapidness, low-cost, effectiveness, it
has been more and more used in transport planning re-
cently. However, when the number of surveyed sections
is less than the number of OD variables, the solution of
OD matrix calculation will be non-unique and cannot
guarantee the accuracy [1]. Moreover, the objective func-
tion and fitness function of OD matrix calculation are
mostly nonlinear equations. In light of the above issues,
taking the reality situation that observation error and ran-
dom error exist into account, the relationship between OD
traffic and road traffic is not absolute linear. Although
through rigorous mathematical methods, it cannot get an
exact solution to the problem.
In pursuit of finding solution to these problems many
researchers have been drawing ideas from the field of
biology. A host of such biologically inspired evolutionary
techniques have been developed namely Genetic Algo-
rithm (GA) ([Baykasoğlu et al., 2008], [Costa et al., 2004],
[Grosset et al., 2001], [Gürdal Soremekun et al., 2001],
[Le Riche and Haftka, 1993], [Park et al., 2001], [Rajen-
dran and Vijayarangan, 2001] and [Walker and Smith,
2003]), Artificial Neural Networks (ANN) (Garg, Roy
Mahapatra, Suresh, Gopalakrishna & Omkar, 2007), Arti-
ficial Immune System (AIS) (Omkar, Khandelwal, San-
thosh Yathindra, Narayana Naik & Gopalakrishna, 2008)
and Particle Swarm Optimization (PSO) (Omkar, Mud-
igere, Narayana Naik & Gopalakrishna, 2008; Parsopou-
los, Tasoulis & Vrahatis, 2004) which are widely used for
solving such optimization problems. All of these algo-
rithms with their stochastic means are well equipped to
handle such problems [2].
Particle Swarm Optimization was introduced by Eber-
hart and Kennedy [3], inspired by the social behavior of
animals such as bird flocking, fish schooling, and the
swarm theory. Compared with GA and other similar evo-
lutionary techniques, PSO has some attractive characteris-
tics and in many cases proved to be more effective (Has-
san, Cohanim, Weck & Venter, 2005). Both GA and PSO
have been used extensively for a variety of optimization
problems and in most of these cases PSO has been proven
to have superior computational efficiency ([Hassan et al.,
2005] and [Sun, 2008]; Zhang et al., 2003 L. B. Zhang, C.
G. Zhou, X. H. Liu, Z. Q. Ma, M. Ma & Y. C. Liang
(2003) solved multi-objective optimization problems us-
ing particle swarm optimization in Proceedings of the
IEEE congress on evolutionary computation (CEC). Since
Research on OD Matrix Calculation Based on Quantum Behaved Particle Swarm Optimization Algorithm
Copyright © 2009 SciRes JSEA
345
1995, many attempts have been made to improve the per-
formance of the PSO (Clerc, 2004; Zheng, Ma, & Zhang,
2003). (Sun et al., 2004) and (Sun and Xu et al., 2004)
introduced quantum theory into PSO and proposed a
Quantum-behaved PSO (QPSO) algorithm, which are
guaranteed theoretically to find good optimal solutions in
search of space. The experiment results on some widely
used benchmark functions show that the QPSO works
better than standard PSO ([Sun et al., 2004] and [Sun and
Xu et al., 2004]) and is a promising algorithm. Hence in
the current work we propose to employ a multi objective
optimization method based on QPSO and compare it to its
predecessor PSO, which has been already implemented
by Omkar and Mudigere et al. (2008) [2].
This paper firstly establishes maximum entropy OD
matrix calculation model. It makes full use of the quan-
tum behaved particle swarm optimization algorithm
(QPSO algorithm) to solve the global optimization of the
objective function, lists the detailed steps of calculation
and shows how to choose the particle swarm operator,
and then calculates the OD matrix of road intersection.
Finally, compared to the results of conventional PSO al-
gorithm, it verifies the superiority of QPSO algorithm.
Therefore, this paper provides a more reliable method to
solve the OD matrix of road intersection.
2. OriginDestination Matrix Prediction
Model
2.1 Maximum Entropy Model
The maximum entropy approach is motivated by infor-
mation theory and the work of Shannon, 1948. C. E.
Shannon, A mathematical theory of communication. Bell
Syst. Tech. J. (1948), pp. 379423. Shannon (1948) who
defined a function to measure the uncertainty, or entropy,
of a collection of events, and Jaynes who proposed
maximizing that function subject to appropriate consis-
tency relations, such as moment conditions. The maxi-
mum entropy (ME) principle and its sister formulation,
minimum cross-entropy (CE), are now used in a wide
variety of fields to estimate and make inferences when
information is incomplete, highly scattered, and/or incon-
sistent (Kapur and Kesavan, 1992). In economics, the ME
principle has been successfully applied to a range of
econometric problems, including nonlinear problems,
where limited data and/or computational complexity hin-
der traditional estimation approaches. Theil (1967) pro-
vides an early investigation of information theory in eco-
nomics. Mittelhammer et al. (2000) provide a recent text
book treatment which is focused more tightly on the ME
principle and its relationships with more traditional esti-
mation criteria such as maximum likelihood [4].
In general, information in an estimation problem using
the entropy principle comes in two forms: 1) information
(theoretical or empirical) about the system that imposes
constraints on the values that the various parameters can
take; and 2) prior knowledge of likely parameter values.
In the first case, the information is applied by specifying
constraint equations in the estimation procedure. In the
second, the information is applied by specifying a discrete
prior distribution and estimating by minimizing the en-
tropy distance between the estimated and prior distribu-
tions the minimum Cross-Entropy (CE) approach. The
prior distribution does not have to be symmetric and
weights on each point in the prior distribution can vary. If
the weights in the prior distribution are equal (e.g. the
prior distribution is uniform), then the CE and ME ap-
proaches are equivalent.
The model is as follows:
(
)
maxlnln
11
nn
ETTT
ijij
ij
=−−
∑∑
== (1)
11
..1,,
nn
k
kijij
ij
stVTPkm
==
==
∑∑ L (2)
ij
Tij
≥∀ (3)
11
nn
ij
ij
TT
==
=
∑∑
(4)
Where n is the number of OD pairs;
ij
T
is the estimated
OD matrix;
k
V
is the detected traffic on section k;
k
ij
p
is
the distribution ratio of
ij
T
on section k, which is obtained
by the traffic distribution.
2.2 Hopfield Neural Network Model
The Hopfield Neural Network model [4] is
( )
1
,
,1,2,,.
N
ii
j
ii
duU
CITV
dtR
VguiN
=
=++
==
K
(5)
Here in Equation (5),
ij
T
is the connection weight value
between node
I
and node
J
, and
ijji
TT
=
;
(
)
g
. is a
function with
(
)
0
g
⋅>
;
i
U
is the input of node I;
i
V
is the output of node
I
;
i
I
is the constant value of node
I
;
C
is a positive constant; and R is a positive constant.
Equation (5) can be abbreviated to be
( )
1
,
,1,2,,.
N
iiijj
j
ii
du ITV
dt
VguiN
=
=+
==
K
(6)
It can be proved that when the energy function of sys-
tem (6) is
111
1
2
NNN
ijijii
iji
ETVVVI
===
=−−
∑∑
We can have
0
dE
dt
, and only when
0
i
dVdt
=
,
Research on OD Matrix Calculation Based on Quantum Behaved Particle Swarm Optimization Algorithm
Copyright © 2009 SciRes JSEA
346
0
dEdt
=
,
(
)
1,2,,
iN
=
K
.
The stable state of system (6) is the local minimum of
the above energy function. The computation processor
of system (6) is a process to find the local minimum in
fact, the goal function is the above energy function of
system (6).
Maximum entropy model is recognized by majority of
scholars among many OD matrix calculation models, be-
cause this models structure is simple and principle is
clear. It also suits the situation without a priori OD matrix
and which is a congested network [5].
2.3 Model Simplification
In light of above optimization problems, it is difficult to
solve the objective function directly. So Lagrange multi-
plier method is used to obtain the Lagrange function L:
11111
(lnln)()
nnmnn
k
ijijkkijij
ijkij
LTTTVTP
λ
=====
=+−
∑∑ (7)
The following Equation is the result of the first-Order
derivative of
ij
T
1
ln0
m
ij k
kij
k
ij
T
LP
TT
λ
=
=−=
(8)
So,
1
exp()
m
k
ijkij
k
TTP
λ
=
=−
(9)
T
is given as
0
exp()
T
λ
=−and take it into the Equa-
tions (7) and (9) respectively. The results are as follows:
111
0
111
exp()1
exp()
nnm
k
kij
ijk
nnm
kk
ijkijk
ijk
P
PPV
λ
λλ
===
===
−=
−=
∑∑
∑∑
1,,
km
=
L
(10)
Above equations are a set of nonlinear equations. The
number of variables is (m+1) which is equivalent to the
number of equations. Lagrange multipliers: 01
,
m
λλλ
LL
can be solved. And then the OD matrix can be obtained
according to Equation (9).
3. Design of the Quantum Behaved Particle
Swarm Optimization Algorithm
3.1 Particle Swarm Optimization Algorithm
Particle Swarm Optimization algorithm is a global opti-
mization algorithm that can reproduce swarm intelligence.
It is inspired from the foraging behavior of animal groups.
When groups search for the optimal target, each individ-
ual searches for its own goal. At the same time, individual
refers to other individuals who have achieved optimal
location and then adjusts the next search. The algorithm
uses the speed-location search model. The current loca-
tion of No.i particle is defined as
i
X
=12
(,,...)
iiid
xxx
,
experienced position is defined as i
P12
(,,...)
iiid
ppp
.
Fitness function determines the level of merits of the lo-
cation, while fitness function is determined by the opti-
mization goal. Where, the individual particle best position
is abbreviated as
pbest
, and the best location that all par-
ticles have experienced is regarded as global best location
(
gbest
). The speed of No. i particle is defined as
12
(,,...)
iiiid
Vvvv
=that is the distance each iterative parti-
cle moves. The Equations of conventional PSO algorithm
are described as follows:
11122
()()
iiii
vvrpbestxrgbestx
φφ
+
=++⋅− (11)
11
iii
xxv
++
=+ (12)
3.2 Quantum Behaved Particle Swarm
Optimization Algorithm
Particle Swarm Optimization algorithm is based on the
theory of swarm intelligence optimization algorithm. As
in the classical system, particles achieve convergence in
the form of orbit. Moreover, the speed of particles is lim-
ited, and the space of particles is also a limited region that
can not cover the entire feasible space. Therefore, with
the quantum mechanics point of view that particles have
quantum behavior, QPSO (Quantum Particle Swarm Op-
timization) algorithm is proposed [3,78]. Particle swarm
achieves iterative update through the following four
Equations:
1
12
111
/
/,/,,/
M
i
i
MMM
iiid
iii
mbsetpbestM
pbestMpbestMpbestM
=
===
=

=


∑∑
L
(13)
(
)
maxminmax
max
T
T
ββ
ββ −⋅
=− (14)
1212
()/()
prpbestrgbestrr
=+⋅+ (15)
()ln(1/)0.5
(1)
()ln(1/)0.5
pmbestxtuifu
xt pmbestxtuifu
β
β
+××<
+=
××≥
(16)
In order to avoid algorithm premature, Mean Best Posi-
tion (mbest) is regarded as the barycenter of all particles.
Where,
i
pbest
is the best position of the particle.
β
is
the contraction and expansion coefficient that impacts the
convergence speed and performance of algorithm. In this
paper, deal with
β
by adaptive changes in accordance
with Equation (14). T is the number of current iteration.
Tmax is the maximum number of iterations. 12
,
rr
Research on OD Matrix Calculation Based on Quantum Behaved Particle Swarm Optimization Algorithm
Copyright © 2009 SciRes JSEA
347
(0,1)
rand ,
gbest
is the global optimal solution,
u
(0,1)
rand .
3.3 Optimal Design of OriginDestination
Matrix Calculation Model Algorithm
Algorithm design, including as follows:
1) the determination of objective function
In order to obtain better accuracy, this problem will be
translated into the following optimization problem. The
optimizing goal is that minimizes the mean square devia-
tion of the calculated value of the left from the true value
of the right in Equation (13). That is
0
()()
min() 1
m
kkkk
k
vVvV
Jm
λ=
⋅−
=+
(17)
Where, 0111
exp()
nnm
kk
ijkij
ijk
vPP
λ
===
=−
∑∑
0
1
V
=
0
111
exp(),1,...
nnm
kk
kijkij
ijk
vPPkm
λλ
===
=−=
∑∑
Lagrange multipliers 01
,
m
λλλ
LL
are unknown. So-
lution space is the range of Lagrange multipliers. Because
the Lagrange multipliers are not given in this model ex-
plicitly, it is necessary to estimate conservatively accord-
ing to the specific issues and enlarge the range appropri-
ately.
2) detailed implementation steps are:
Step1: Initialize particle swarm.
Step2: Calculate the value of particle objective func-
tion.
Step3: Update
pbest
and
gbest
according to parti-
cles fitness.
Step4: Calculate mbest according to Equation (13).
Step5: Calculate random point p of each particle ac-
cording to Equation (15).
Step6: Calculate new location of each particle accord-
ing to Equation (16).
Step7: Double counting, until meet the number of itera-
tions.
3.4 Simulation of a Typical Function Optimization
Now, QPSO algorithm is illustrated that can be applied to
the circuit performance equation to solve the global
minimum feasibility and effectively, by solving the
Schaffers f6 function. The value of the global minimum
is 0. The Schaffers f6 function is:
222
2222
sin0.5
(,)0.5
(10.001())
xy
fxy xy
+−
=+
+×+ (18)
(10,10)
x∈− ;
(10,10)
y∈−
Use QPSO algorithm and PSO algorithm to solve the
above equation respectively.
The selected parameters are as follows: Particle number
is 10; the maximum number of iterations is 1000; the ac-
curacy is set to 1e-25. Figure 1 and Figure 2 show the
obtained convergence curves.
As can be seen from Figure 1, when the iteration num-
ber reached 210, the curve tends to converge. Whereas,
when the iteration number reached 310, the curve of Fig-
ure 2 tends to converge; the solution of QPSO algorithm
from Figure 1 is 0, while, the solution of PSO algorithm
from Figure 2 is 0.000114686. Therefore, this example
shows that the convergence speed and accuracy of QPSO
algorithm are far better than the PSO algorithm for opti-
mization problems.
4. Simulation Examples
4.1 Simulation Results
This paper uses MATLAB programming language to
carry out the simulation test. The intersection is shown in
Figure 3. The traffic of every import is regarded as x1, x2,
x3, x4 respectively. The traffic of every export is regarded
as y1, y2, y3, y4 respectively. The traffic at intersection can
be obtained by the detector. Count the total number of
observed vehicles from 8:00 a.m. to 8:00 p.m.
Figure 1. Convergence curve of QPSO algorithm
Figure 2. Convergence curve of PSO algorithm
Research on OD Matrix Calculation Based on Quantum Behaved Particle Swarm Optimization Algorithm
Copyright © 2009 SciRes JSEA
348
Figure 3. A intersection plot of Tianjin
( )
12341234
,,,,,,,
T
Vxxxxyyyy
=
( )
5321,5069,4986,5035,5109,5220,4823,5259
T
=
Traffic distribution matrix is as follows:
111000000000
000111000000
000000111000
000000000111
000100100100
100000010010
010010000001
001001001000
P






=







4.2 Simulation Steps
1) Determine the solution space
The value of the OD matrix T can be calculated. It is
equivalent to the total of all the exports (or imports):
44
11
20411exp(9.92)
ij
ij
Txy
==
====
∑∑ . We can obtain
that
0
λ
= -9.92, according to
0
exp()
T
λ
=−.
In addition, various components of the OD matrix
should meet 1ij
TT
≤≤
, so we can obtain
00
1
0mk
kij
k
P
λλλ
=
−−
pp. Or 0
1
010
mk
kij
k
Pλλ
=
ppp.
According to
1
exp()
m
k
ijkij
k
TTP
λ
=
=−
, the element of P
matrix is 0 or 1, so
(1,)
k
km
λ=
L
can not be all nega-
tive. There are two situations: The whole elements are
nonnegative; one part of elements is positive, and the
other parts are zero or negative. For the situation that the
whole elements are nonnegative, the value of
k
λ
should
be within the range [0,10]. For the second situation, the
range can not be defined easily. As result of mutual in-
fluence between several unknown quantities, its value
may be very large or may be very small. Therefore, we
can obtain that there is a solution set and the values are
within the range [0,10].
2) Determine the conditions of termination
Set the maximum number of iterations as 300. When
the average mean square error (MSE) of the objective
function
()
J
λ
is less than 0.1, we regard the obtained
k
λ
(k=0,1 8) as the approximate optimal solution of
Equations (10) and terminate iterations.
3) Determine the number of particles
The optimal goal is that the objective function (mean
square error MSE) close to zero as possible. Selected pa-
rameters are as follows: The initial velocity of particles is
generated randomly; the number of particles is 20.
The simulation results are as follows:
4.3 Analysis the Simulation Results
Compared to the results of conventional PSO algorithm,
we can see that the results of the conventional PSO algo-
rithm and QPSO algorithm all meet the accuracy re-
quirements (MSE<0.1). However, when the conventional
PSO algorithm is used to solve individual variables, a
local optimal solution is obtained that led to a larger ab-
solute error of individual variables. As can be seen from
Table 1, the absolute error between actual traffic and cal-
culated traffic by QPSO algorithm is too small (0.103) to
meet the accurate requirements fully. Compared to Table
3, from Table 4 we can see the effect of the OD matrix
calculation is ideal.
Table 1. Absolute error of calculating road traffic
Absolute
Error V0-v0 V1-v1 V2-v2 V3-v3 V4-v4 V5-v5 V6-v6 V7-v7 V8-v8
QPSO 0.0002 -0.026 0.038 -0.103 0.063 0.025 -0.054 0.019 -0.0237
PSO 0.0003 -0.042 0.056 -0.120 0.084 0.023 -0.076 0.032 -0.0438
Table 2. Comparison of MSE
MSE QPSO PSO
MSE= Jλ
0.0485 0.0630
Table 3. Factual OD matrix of intersection
O D 1 2 3 4
1 0 1936 2351 1034
2 1241 0 1392 2436
3 1808 1389 0 1789
4 2060 1895 1080 0
Research on OD Matrix Calculation Based on Quantum Behaved Particle Swarm Optimization Algorithm
Copyright © 2009 SciRes JSEA
349
Table 4. Calculated OD matrix with QPSO
O D
1 2 3 4
1 0 1936.01 2351.02 1034
2 1240.99 0 1391.98 2435.99
3 1808.04 1389.03 0 1789.03
4 2059.95 1895.01 1079.98 0
5. Conclusions
This paper calculates the OD matrix calculation model
using QPSO algorithm, and determines the fitness func-
tion, according to the maximum entropy model. We use
this model to simplify the linear constraints between the
traffic and the OD matrix, and solve the optimal solution
of nonlinear equation using QPSO algorithm. It can be
seen from the above simulation that OD matrix calcula-
tion proposed in this paper is effective. It proves that ap-
plication QPSO algorithm in the field of OD matrix cal-
culation is feasible. It can considerably reduce the itera-
tive number that objective function can reach conver-
gence. Moreover, QPSO algorithm can improve the accu-
racy of the calculation and solve the problem of no con-
vergent and insufficient accuracy. We will further study
on how to apply QPSO algorithm in OD matrix calcula-
tion of a large and complex network.
6. Acknowledgments
The paper is supported by Tianjin Science and Technol-
ogy Project Fund.
REFERENCES
[1] W. Wang and J. Q. Xu, Urban transportation planning
theories and methods, China Communications Press,
1992.
[2] S. N. Omkar, R. Khandelwal, T. V. S. Ananth, G. N. Naik,
and S. Gopalakrishnan, Quantum behaved Particle
Swarm Optimization (QPSO) for multi-objective design
optimization of composite structures, Expert Systems
with Applications, Vol. 36, No. 8, pp. 1131211322, Oc-
tober 2009.
[3] J. Kennedy and R. C. Eberhart, Particle swarm optimiza-
tion, Proceedings IEEE International Conference Neu-
ralNetworks [C]. Piscataway, NJ: IEEE Press, pp. 1942
1948, 1995.
[4] C. Arndt, S. Robinson, and F. Tarp, Parameter estimation
for a computable general equilibrium model: a maximum
entropy approach, Economic Modelling, Vol. 19, No. 3,
pp. 375398, May 2002.
[5] Z. J. Gong, Estimating the urban OD matrix: A neural
network approach, European Journal of Operational Re-
search, Vol. 106, No. 1, pp. 108115, April 1998.
[6] M. Brenninger-Göthe, K. O. Jörnsten, and J. T. Lundgren,
Estimation of origin-destination matrices from traffic
counts using multiobjective programming formulations,
Transportation Research Part B: Methodological, Vol. 23,
No. 4, pp. 257269, August 1989.
[7] G. R. Widom, Data guides enabling query formulation
and optimization in semistructured databases, The 23rd
VLDB[C], Athens, Greece, pp. 436445, 1997.
[8] T. Milo and D. Suciu, Index Structures for path expres-
sions, The 7th ICDT[C], pp. 277295, 1999.