Journal of Intelligent Learning Systems and Applications, 2011, 3, 11-16
doi:10.4236/jilsa.2011.31002 Published Online February 2011 (http://www.SciRP.org/journal/jilsa)
11
Dynamic Shortest Path Algorithm in Stochastic
Traffic Networks Using PSO Based on Fluid
Neural Network
Yanfang Deng, Hengqing Tong
School of Science, Wuhan University of Technology, Wuhan, China
Received March 23rd, 2010; revised June 23rd, 2010; accepted September 10th, 2010
ABSTRACT
The shortest path planning issure is critica l for dynamic traffic assignment and route guida n ce in in telligen t tran sp orta-
tion systems. In this paper, a Particle S warm Optimization (PSO) algorithm with priority-based encoding scheme based
on fluid neural network (FNN) to search for the shortest path in stochastic traffic ne tworks is introduced. The proposed
algorithm overcomes the weight coefficient symmetry restrictions of the traditional FNN and disadvantage of easily
getting into a local optimum for PSO. Simulation exp eriments have b een carried out o n differen t tra ffic networ k topo lo-
gies consisting of 15-65 nodes and the results showed that the proposed approach can find the optimal path and closer
sub-optimal path s with good success ra tio. At the same time, th e algorithms grea tly improve the converg ence efficiency
of fluid neuron network.
Keywords: Particle Swarm Optimization, Fluid Neuron Network, Shor test Path, Traffic Networks
1. Introduction
In recent years there has been a resurgence of interest in
the shortest path problem in various transportation engi-
neering applications [1]. In a distributed route guidance
system, an in-vehicle computer is commonly used to
calculate the optimal route in a large traffic network.
Typically the recommended routes must be found within
a very short time period (e.g., a few seconds). In a
real-time automated vehicle dispatching system, new
routes and schedules must be identified within a reasona-
ble time after a customer requesting a service. Because
the travel times are the basic input to the real-time
routing and scheduling process and are dynamic in most
urban traffic environments, there is an implicit require-
ment to use a minimum path algorithm repeatedly during
the optimization procedure.
In the above applications, the shortest path problem,
which is one of key technologies of distributed route
guidance system, concerns with finding the shortest path
from a specific origin to a specified destination in a given
network while mini mizing the total d istance, time or cost
associated with the path. This problem has been studied
extensively in the fields of computer science, operation
research, and transportation engineering [2] and so on.
The well-known algorithms including the Bellman’s dy-
namic programming algorithm [3], the Dijkstra algorithm
[4] and Bellman-Ford successive algorithm [5], are re-
ferred to as the standard shortest path algorithms. How-
ever, these traditional algorithms have major shortcom-
ings: firstly, they are no t suitab le for n etwo rks with nega -
tive weights of the edges; secondly, the algorithms search
only for the shortest route, but they cannot determine any
other similar or non-similar short routes; thirdly, they
exhibit high computational complexity. Therefore, the
optimal shortest path algorithms tend to be too computa-
tionally intensive for real-time one-to-one application s in
realistic traffic networks. Artificial neural networks
(ANNs) have been examined to solve the shortest path
problem relying on their parallel architecture to provide a
fast solution [6,7], However, ANN approach has several
limitations such that they are less adaptable to topologi-
cal changes in the network graph including the cost of
the arcs. Moreover, the ANNs do not consider sub-
optimal paths. Among other approaches for this problem,
the powerful evolutionary programming techniques such
as genetic algorithm (GA) [8] and tabu Search [9,10],
which shows better performance compared to those of
ANN approach and overcome the limitations mentioned

Dynamic Shortest Path Algorithm in Stochastic Traffic Networks Using PSO Based on Fluid Neural Network 12
above, have considerable potential to be investigated in
the pursuit for more efficient algorithms. PSO is such an
evolutionary optimization technique, which can solve
most of the problems solved by GA with less computa-
tion cost [11,12]. The most attractive feature of PSO is
that it requires less computational bookkeeping and,
generally, a few lines of implementation codes. Because
of the specific algorithmic structure, PSO has been
mainly applied to many continuous optimization prob-
lems with few attempts for combinatorial optimization
problems [13-15]. Unlike the GA, the PSO algorithm has
no complicated evolutionary operators such as crossover
and mutation. In the PSO algorithm, the potential solu-
tions, called as particles, are obtained by “flowing”
through the problem space by following the current op-
timum particles. Generally speaking, the PSO algorithm
has a strong ability to find the most optimistic resu lt, but
it has a disadvantage of easily getting into a local opti-
mum. After suitably modulating the parameters for PSO
algorithm, the rate of convergence can be speeded up and
the ability to find the global optimistic result can be en-
hanced. The PSO algorithm’s search is based on the
orientation by tracing Pb that is each particle’s best posi-
tion in its history, and tracing Pg that is all particles’ best
position in their history; therefore, it can rapidly arrive
around the global optimum. However, because the PSO
algorithm has several parameters to be adjusted by em-
pirical approach, if these parameters are not appropriate-
ly set, the search will become very slow near the global
optimum.
In this paper, the PSO algorithm based on the FNN
model to search for the shortest path in stochastic traffic
networks is proposed for the first time to our best know-
ledge. The technique makes full use of their advantages
and uses the PSO algorithm to do global search in the
beginning of stage, and then uses the FNN algorithm to
do local search around the global optimum Pg. In partic-
ular, this hybrid algorithm will be used to train the FNN
weights for function approximation and classification
problems in convergent speed and generalization per-
formance. Due to the fast global search feature of PSO, it
improves greatly the efficiency of the convergence of the
fluid neuron network, and decreases greatly the computa-
tion time of optimization path.
The paper is organized as follows. In Section 2, FNN
model is introduced and briefly discussed. PSO algo-
rithm and the particle encoding mechanism to solve
shortest path problem in the traffic networks is presented
in Section 3. The results from computer simulation expe-
riments are discussed in Section 4. Section 5 concludes
the paper.
2. FNN Model in the Traffic Networks
FNN [16], which based on continuous Hopfield neural
network, has some merits, for example, its convergent
process is as clear as the equilibrium process of fluid; its
stable state is unique, which is determined by both the
flow rate and the invariability in volume that the poten-
tial inside neurons must satisfy, corresponding to the
Kirchoff’s node law in electrical circuits and the conser-
vation properties of liquid in volume respectively.
Moreover, it is unnecessary for FNN to solve the optimal
problem by minimizing the energy function. Since the
traffic network is very similar to FNN, it is reasonable to
utilize FNN to handle the shortest p ath problem in traffic
networks.
FNN has audio-visual properties of fluid as shown in
Figure 1. The model is expressed as follows [17]:


2| |
,1,2,,
0 ij
1
s1i
iij jiii ii
ji
ii ij
ji
ij ji
ii bu c
du TssTu I
dt
TTij N
TT
gu ae







 
 
 



 (1)
where each neuron is viewed as a vessel containing
u-fluid, i
u,i
s
, 2| |
ii i
Tuand i Iis the volume , the lev-
el ,the leakage and the external flow rate poured into
(i I>0) or out (i I<0) of u-fluid in vessel i ,respectively.
The nonlinear function g characterizes the shape of the
vessel. ij Trepresents the capacity of the flow between
both the vessels i and j, as a pipe connected between both
the vessels and its diameter is controlled by the value of
ij
T.


ij ji
Ts sis the actual flow rate of u-fluid from
vessel j to vessel i, whose sign indicates the directions.
When the system is closed, the system will reach a stable
state, and then the total volume of the u-fluid in the sys-
tem will be constant. Evidently FNN is quite similar to
the traffic network. Certain amount of traffic flow going
through the traffic network can be viewed as the same
amount of fluid flowing through the vessels, that is, the
neurons. Fluid naturally flows from a higher level to a
Figure 1. The fluid neural ne twor k system[16].

Dynamic Shortest Path Algorithm in Stochastic Traffic Networks Using PSO Based on Fluid Neural Network 13
lower level, which is also the fundamental property of
u-fluid. When iterations are enough, the height of every
vessel is unchangeable and the system reaches a stable
state. Of all links connected with a neuron the link hav-
ing the largest volume of flow is the most probable route
chosen by the fluid. By this way, from the Original node
to the Destination nod e, the rou te with the largest vo lume
of flow is the shortest path. A traffic network consists of
nodes and links. Every node is represented by a neuron.
The link cost corresponds to the weight between nodes.
Specifically, the link cost could be the link travel time,
congestion degree, synthesis index from information
center, and the link length or road condition stored in
database of in-vehicle computer. The computer produces
a cost matrix, and then transfer it to T, in which ij T is
the connection degree between i and j. Using travel time
as an example:

0 cannot reach directly
can reach through
ij
lm
ij
Ttijm
KT h
 




 (2)
where 0

,

lm
tKTh


 is the prediction of travel
time of link m at time
K
Th


.In traffic networks,
because of the road condition, traffic volume and traffic
management and control, the costs of one link of two
directions are not always equal, that is ij ji TT, thus the
weight matrix is not symmetrical. ii ij
ji
TT


cannot be
satisfied for one node too. Since there are no cost data
from node i to i and there is no point in finding the
shortest path from i to i, ignoring the leakage of (1),
we obtain the following FNN for traffic networks:
1() ,1,2,,
N
iij jii
j
du Ts sIijN
dt 

 (3)
As far as traffic networks are concerned, the conver-
gence of FNN is somehow deteriorated in the global
search. However, the local search has a good conver-
gence. Therefore, the PSO algorithm is used to do global
search in the beginning of stage, and then uses the FNN
algorithm to do local search around the global optimum
Pg, which decrease greatly computational time to find the
optimal shortest path.
3. PSO Algorithm and Particle Encoding for
Shortest Path Problem
From the beginning of 90’s, new optimization technique
researches using analogy of swarm behavior of natural
creatures have been started, Eberhart and Kennedy de-
veloped PSO based on the analogy of swarm of bird and
fish school [18]. PSO is initialized with a group of ran-
dom particles and th en searches for optimum solution by
updating generations. In each iteration, each particle is
updated by following two “best” values. The first one is
the best solution it has achieved so far and is called pb
and the second one is tracked by the particle swarm op-
timizer is the best value, obtained so far by any particle
in the population and is called gb. Finally, each particle
updates its velocity and positions using following equa-
tions:
(1)()1* ()
(())2(())
(1) ()(1)
bb
velocity kwvelocity kcrand
ppk c gpk
p kp kvelocity k

 

 
(4)
where velocity is the particle’s velocity, p is the current
particle’s position, rand () is a random number between
(0, 1), c1 and c2 are learning factors. The inertia weight
w is employed to control the impact of the previous his-
tory of velocities on the current velocity, thus to influ-
ence the trade-off between global and local exploration
abilities of the flying points. The performance of each
particle is measured according to a predefined fitness
function, which is related to the problem being solv ed. In
stochastic traffic networks, each particle is defined as a
sequence of vertexes that represent a valid path and the
fitness function is the cost of the path according to the
cost of the edges.
The common PSO is either global version or local ver-
sion of PSO. In global version, all other particles influ-
ence the velocity of a particle, while in the local version
of PSO, selected number of neighbor particles affect the
particle’s velocity. In this paper, the global version of
PSO is chosen to search the shortest path in traffic net-
works. At the same time, a constriction factor [19] is
used, which can achieve the best performance while us-
ing velocity clamping. Thus, it is readily observed that
the PSO is very simple to be i mplemented. However, the
thorniest problem in applying PSO to the shortest path
problem is how to encode a path in a traffic network into
a particle in PSO. This encoding in turn affects th e effec-
tiveness of search process. The proposed path encoding
algorithm for PSO is essentially based on indirect priori-
ty based encoding. The direct encoding scheme is not
preferred since a random sequence of nodes is definitely
not a good choice for path construction. But the priori-
ty-based encoding scheme is suitably modified to address
the concerns raised earlier during path construction.
Therefore, the pseudo-codes for implementation of prior-
ity-based encoding algorithm is presented.
Let max
N
be the maximum number of nodes in the
traffic networks. Let k
p
Vbe a partial path (corresponding
to the position/priority vector of a particle) under growth,
which contains 1k

nodes with the terminal node k t
(0k

corresponds to the partial path with source node
only), and (1k

)th node is to be selected. Let k
x
be the
dynamic priority vector, which initially contains the

Dynamic Shortest Path Algorithm in Stochastic Traffic Networks Using PSO Based on Fluid Neural Network 14
priority values (position vector of the particle), referred
to by x. Every time a node is added to the partial path,
the corresponding position in k
x
is given a large nega-
tive value (
N

). Without loss of generality, node num-
ber 1 is taken as source node and destination node ID
is max
N
.The implementations of the modified priori-
ty-based encoding along with gradual path construction
process are summarized in the following steps:
Step 1:( Initialization) Let 0k， 1
k
p
V

and
k
x
x; 1
k
t and ()
kk
x
tN


.
Step 2: (Termination test) If ma x
k
tN, or max kN,
go to Step 4; else 1kk and go to Step 3.
Step 3: (Path extension) Select node k tas the node
with highest pr i ori t y from among the no des having direct
links with node 1k tif (

1kk
tt M

, where
M
is a
positive integer. Set

1, kkk
pp
VVt

 and

kk
x
tN

 .
Step 4: (Complete path) Return complete valid path
k
p
Vor return invalid path k
p
Vif the terminal node is not
the destination node.
In Step 2, if the number of iteration exceedsmax
N
, it
would mean either a va lid path has no t been found du e to
loops or the path does not terminate at the destination
node in max
N
steps. In that case, the objective function
evaluation of the corresponding particle is made to return
a very low value as penalty. In Step 3, the nodes having
direct links with the terminal node of the already grown
partial path can be found from the network topology. The
value of M should be judiciously decided based on net-
work topology.
The quality of a particle (solution) is measured by a
fitness function. Here, the fitness function is obvious as
the goal is to find the minimal cost path. Thus, th e fitness
of ith particle is defined as:
 
1
1
1
,PP and PP1
i
Nii
iyz
j
fCyjzj







 (5)
where PPi is the set of sequential node IDs for ith par-
ticle, i
N
equal to number of nodes that constitute the
path represented by ith particle, and
y
z
Cis the cost of the
link connecting node y and node z. Thus, the fitness
function takes maximum value when the shortest path is
obtained. If the path represented by a particle happens to
be an invalid path, then its fitness is assigned a penalty
value (= 0) so that the particle’s attributes will not be
considered by o thers for future search.
After the PSO algorithm is used for global search in
the beginning of stage, the FNN algorithm is used for
local search around the global optimum Pg, therefore, the
convergence of traffic networks improve greatly.
4. The Simulation Results and Discussions
The proposed algorithm for the shortest path search is
tested on random traffic networks as are shown Figure 2
through computer simulations using Matlab on an Intel
processor (T2050@1.60G). Population size is 30 and the
particle’s position vector which represents the node
priorities is initialized with random integer values in the
range [-90,90] and the velocities in the range [-10,10].
Both learning factors (c1 and c2) are chosen to be 2.05,
thus, constriction factor is 0.729 [19]. During the path
construction process, th e value of M is set to 4. The algo-
rithm is set to run for a maximum of 600 iterations unless
stated otherwise. The average CPU time required to
achieve the results shown in Figure 3. From Figure 3, it
can be found that average CPU time is less than 1 second
for more than 60 nodes, which can achieve real-time
search for the best dynamic path in the stochastic traffic
networks. In add ition to seekin g so lu tion for op ti mal path,
it is also equally importan t to look for closer sub-optimal
paths, especially, when the optimal path search is con-
gesting. Figure 4 shows the route failure ratio to achieve
the optimal path in the Figure 2 traffic networks. For
95% (and 90%) of the optimal path corresponding to
95% (and 90%) of the optimal path cost, the route failure
Figure 2. A typical 20-node random network where the
weights of the connecting edges are also shown adjacent to
the corresponding edges.
Figure 3. Convergence time with different nodes (popula-
tion size = 30).

Dynamic Shortest Path Algorithm in Stochastic Traffic Networks Using PSO Based on Fluid Neural Network 15
Figure 4. Route failure ratio to achieve optimal, 95% and
90% of optimal path (population size = 30).
ratio is more than 99%.When the nodes are more than 60,
the failure ratio is less than 5%.This feature is highly
beneficial in real-time automated vehicle dispatching
system.
5. Conclusions
In this paper, a new method is proposed for solving the
shortest path problem in stochastic traffic networks. The
approach based on combining FNN model with PSO.
The PSO search uses a modified indirect path-encoding
scheme. This algorithm is simple and easy and can find
quickly the shortest path without falling into local mini-
mums, which will occur if energy function is used to
solve the same problem. Since PSO and FNN are all pa-
rallel algorithms, it is very easy to run the new algorithm
on parallel computer or even on neural computer, which
will reduce the computational time drastically. As a fur-
ther study,the parameter of PSO algorithm will further be
optimized by chaotic operator for diversity of particle in
order to further enhance the convergence time of the al-
gorithm.
6. Acknowledgments
I would like to thank the experts who take their time to
check the paper and give me valuable suggestions. At the
same time, the project was supported by the National
Natural Science Foundation of China (30570611, 60773
210).
REFERENCES
[1] L. Fu, D. Sun and L. R. Rilett, “Heuristic Shortest Path
Algorithms for Transportation Applications: State of the
Art,” Computers & Operations Research, Vol. 33, No. 11,
2006, pp. 3324-3343. doi:10.1016/j.cor.2005.03.027
[2] D. Wang, B. Zhang, N. Jiang, Y. W. Jing and S. Y. Zhang,
“Traffic Dynamics Based on the Shortest Path Routing
Strategy,” Proceedings of the 21st Annual International
Conference on Chinese Control and Decision Conference,
Guilin, 17-19 June 2009, pp. 1106-1109.
[3] R. Bellman, “On a Routing Problem,” Quarterly of
Applied Mathematics, Vol. 16, 1958, pp. 87-90.
[4] E. Dijkstra, “A Note on Two Problems in Connexion with
Graphs,” Numerische Mathematik, Vol. 1, No. 1, 1959,
pp. 269-271. doi:10.1007/BF01386390
[5] A. Goldberg and T. Radzik, “A Heuristic Improvement of
the Bellman-Ford Algorithm,” Applied Mathematics
Letters, Vol. 6, No. 3, 1993, pp. 3-6. doi:10.1016/0893-
9659(93)90022-F
[6] M. Ali and F. Kamoun, “Neural Networks for Shortest
Path Computation and Routing Incomputer Networks,”
IEEE Transactions on Neural Networks, Vol. 4, No. 6,
1993, pp. 941-954. doi:10.1109/72.286889
[7] R. Wang, S. Guo and K. Okazaki, “A Hill-Jump
Algorithm of Hopfield Neural Network for Shortest Path
Problem in Communication Network,” Soft Computing-A
Fusion of Foundations, Methodologies and Applications,
Vol. 13, No. 6, 2009, pp. 551-558.
[8] C. Ahn and R. Ramakrishna, “A Genetic Algorithm for
Shortest Path Routing Problem and the Sizing of
Populations,” IEEE Transactions on Evolutionary Com-
putation, Vol. 6, No. 6, 2002, pp. 566-579. doi:10.1109/
TEVC.2002.804323
[9] J. Kuri, N. Puech, M. Gagnaire and E. Dotaro, “Routing
Foreseeable Lightpath Demands Using a Tabu Search
Meta-Heuristic,” Proceedings of Global Telecommunica-
tions Conference, New York, 17-21 November 2002, pp.
2803-2807.
[10] N. R. Raidl and B. A. Julstrom, “A Weighted Coding in a
Genetic Algorithm for the Degree-Constrained Minimum
Spanning Tree Problem,” Proceedings of the 2000 ACM
Symposium on Applied Computing, Como, 2000. doi:10.
1145/335603.335888
[11] E. Elbeltagi, T. Hegazy and D. Grierson, “Comparison
among Five Evolutionary-Based Opt i miz at io n Al gor it hm s, ”
Advanced Engineering Informatics, Vol. 19, No. 1, 2005,
pp. 43-53. doi:10.1016/j.aei.2005.01.004
[12] C. Mouser and S. Dunn, “Comparing Genetic Algorithms
and Particle Swarm Optimisation for an Inverse Problem
Exercise,” ANZIAM Journal, Vol. 46, 2004, pp. 174-181.
[13] A. Salman, I. Ahmad and S. Al-Madani, “Particle Swarm
Optimization for Task Assignment Problem,” Micro-
processors and Microsystems, Vol. 26, No. 10, 2002, pp.
363-371. doi:10.1016/S0141-9331(02)00053-4
[14] X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu and Q. X. Wang,
“Particle Swarm Optimization-Based Algorithms for Tsp
and Generalized Tsp,” Information Processing Letters,
Vol. 103, No. 5, 2007, pp. 169-176. doi:10.1016/j.ipl.
2007.03.010
[15] M. F. Tasgetiren, Y.-C. Liang, M. Sevkli and G.
Gencyilmaz, “A Particle Swarm Optimization Algorithm
for Makespan and Total Flowtime Minimization in the
Permutation Flowshop Sequencing Problem,” European
Journal of Operational Research, Vol. 177, No. 3, 2007,
pp. 1930-1947. doi:10.1016/j.ejor.2005.12.024
[16] G. Lei, “A Neuron Model with Fluid Properties for
Solving Labyrinthian Puzzle,” Biological Cybernetics,

Dynamic Shortest Path Algorithm in Stochastic Traffic Networks Using PSO Based on Fluid Neural Network 16
Vol. 64, No. 1, 1990, pp. 61-67. doi:10.1007/BF0020
3631
[17] H. Wen and Z. Yang, “Study on the Shortest Path
Algorithm Based on Fluid Neural Network of in-Vehicle
Traffic Flow Guidance System,” Proceedings of the IEEE
International Vehicle Electronics Conference, Changchun,
6-9 September 1999, pp. 110-113.
[18] J. Kennedy and R. Eberhart, “Particle Swarm Optimi-
zation,” IEEE International Conference on Neural Net-
works, Vol. 4, 1995, pp. 1942-1948.
[19] M. Clerc, “The Swarm and the Queen: Towards a
Deterministic and Adaptive Particle Swarm Optimi-
zation,” Proceedings of the IEEE Congress on Evolu-
tionary Computation, Washington, 1999, pp. 1951-1957.