Journal of Transportation Technologies, 2012, 2, 230-240
http://dx.doi.org/10.4236/jtts.2012.23025 Published Online July 2012 (http://www.SciRP.org/journal/jtts)
A Cooperative Distributed System for Real-Time Route
Guidance
Yaser E. Hawas
Civil and Environmental Engineering Department, UAE University, Al Ain, UAE
Received March 22, 2012; revised April 25, 2012; accepted May 20, 2012
ABSTRACT
This paper describes a cooperative decentralized architecture for reactive real-time route guidance. The architecture is
cooperative in the sense that it allows adjacent local controllers to exchange information regarding the traffic conditions
in their territories. A set of local decision rules and associated heuristic functions to support the cooperative architecture
are specified. A protocol governing the knowledge exchange among local adjacent controllers is developed. A simula-
tion-assignment modeling framework is used for assessing the effectiveness of this cooperative architecture under vari-
ous levels of controller knowledge and network traffic congestion. The cooperative decentralized system is tested under
various scenarios of knowledge and cooperation and network traffic demand levels. The cooperative system is com-
pared against the shortest path algorithm as a benchmark.
Keywords: Decentralized System; Real-Time Route Guidance; Local Controllers; Cooperative Systems; Micro-Scopic
Simulation
1. Introduction
A common approach for route guidance envisions a cen-
tral controller with capability to predict driver origin-
destination (O-D) trip desires, to optimally assign a path
to each driver from origin to destination, as well as to
re-route as warranted [1,2]. The reported limitations of
centralized systems include the massive data processing
and communication needs between the TMC and thou-
sands of users at a time. Excessive computing, storage
and communication capacities are required at the TMC.
As a result, the TMC might be frequently overloaded [3].
Furthermore, such systems were reported to have high
system operating costs [4].
In contrast, hierarchical distributed architectures pro-
vide for locally oriented real-time reactive strategies for
vehicle routing that rely on limited available information
[5,6]. In large-scale networks, the need for fast control
action in response to local data inputs and perturbations
strongly suggests use of distributed information and con-
trol structures. While distributed systems have been ex-
tensively exploited in areas such as telecommunications
and computing network control, only recently have dis-
tributed systems been considered as a promising basis for
route guidance in vehicular traffic networks.
Hawas and Mahmassani [2] developed a non-coopera-
tive decentralized structure and a family of heuristic-based
rules for reactive real-time route guidance. The premise
of this decentralized structure is the ability to deal with
varying degrees of information, spatially and temporally.
In addition, unlike the centralized predictive approach, it
does not require a priori knowledge (or prediction) of the
time-dependent OD demand desires. This structure as-
sumes a set of local controllers distributed over the net-
work. Each local controller is responsible for providing
reactive route guidance for vehicles in its territory. The
controllers are non-cooperative in the sense that they do
not exchange knowledge of the traffic states in their re-
spective territories. Local decision rules that incorporate
heuristic evaluation functions are specified, reflecting
varying degrees of intelligence. The non-cooperative de-
centralized architecture has been shown to be computa-
tionally efficient, and fairly robust and effective under
recurrent as well as incident situations [2].
The use of distributed multi-agent systems to improve
dynamic route guidance and traffic management is re-
ported in Adler et al. [7]. Inter vehicular communication
(IVC) networks provide decentralized solutions for traf-
fic management problems [8-11]. IVC networks are in-
stantiations of mobile ad hoc networks, which have no
fixed infrastructure and instead rely on ordinary nodes to
perform network management functions.
There are several ITS projects based on IVC networks.
FleetNet [9] uses an IVC network to improve the drivers
and passengers’ safety and comfort. VGrid [8] proposes
solving vehicular traffic flow control problems autono-
C
opyright © 2012 SciRes. JTTs

Y. E. HAWAS 231
mously. TrafficView [10] defines a framework to dis-
seminate and gather information about the vehicles based
on IVC.
Hawas, Napeñas and Hamdouch [12] developed two
algorithms for inter-vehicular communication (IVC)-based
route guidance in a traffic network. Although the per-
formance of such IVC-based algorithms is quite rea-
sonable as compared to the centralized systems, there are
still many challenges such as the rapid topology changes,
the frequent fragmentations and the small effective net-
work diameter. Because of the high relative speed of
vehicles, the IVC network experiences very rapid changes
in topology. Also, due to the low deployment of vehicles
having IVC, the IVC network is subject to frequent
fragmentation. Finally, because of the poor connectivity,
the effective network diameter is usually small. These
aspects impose restrictions if deployed via IVC tech-
nologies. For instance, one should compromise the extra
effectiveness of having wider ranges of communication
against the possible degradation in performance due to
poor communication.
Bearing in mind the massive data processing and high
operational cost associated with the centralized systems,
the instability and communication constraints associated
with the IVC-based systems, this paper seeks to provide
improvement to the earlier work of Hawas and Mah-
massni [2]. The improvement is intended to resolve the
reported cycling problems commonly encountered in the
typical pure distributed systems. The improvement is
sought through allowing for information exchange (or
cooperation) among the various decentralized controllers.
In a sense, we investigate the possibility of using inter-
controller communication for exchanging knowledge
regarding the traffic conditions in their respective territo-
ries. Such improvement is thought of as a way to over-
come the limitations of the rapid topology changes, the
frequent fragmentation and poor communication associ-
ated with the IVC-based systems, as well as the limita-
tions of the heavy processing and cost of the centralized
systems. The information exchange would enrich the
knowledge base of any individual controller, and poten-
tially improve the quality of control by providing the
opportunity to utilize higher degrees of intelligence to
improve the specification of the heuristic evaluation fun-
ctions underlying the local decision rules. This new sys-
tem shall be denoted in this paper by the cooperative
decentralized system.
The paper is organized in five sections. Section 2 re-
views the detail the decentralized system structure, as-
sumptions, and rule specifications. Then details of the
rationale, and the essential modifications to the rule
specifications and heuristics to support the cooperative
decentralized scheme are presented. Section 3 discusses
the off-line simulation experimental design for the de-
centralized schemes for vehicle routing. Section 4 pro-
vides comparative estimates of the performance of both
decentralized route guidance non-cooperative and coo-
perative algorithms, with particular emphasis on the im-
provement in performance obtained by allowing know-
ledge sharing among the local controllers. Section 5 pro-
vides some concluding comments.
2. Decentralized Route Guidance Strategies
Hawas and Mahmassani [2] presented a distributed ar-
chitecture that provides for locally oriented real-time
strategies for reactive route guidance. This decentralized
architecture has the ability to deal with situations where
only limited information is available to the controllers.
The decentralized architecture envisioned a set of local
controllers distributed over the network, where every
controller can extract only limited “raw” information
(speed, concentration, etc.) from detectors, and utilizes
this information in conjunction with local decision rules
to guide vehicles within its territory to their individual
destinations. The local controllers are specific hardware
units that may be located at the level of the network in-
tersection; the decentralization level could be coarser or
finer depending on the available hardware, the level of
investment and the desired accuracy. Figure 1 illustrates
the spatial extent of the area from which the controller at
node i extracts information. The size of information ex-
tracted by a single controller (denoted by the knowledge
level, K) refers to the number of downstream links, from
which traffic measurements can be measured and utilized
in making the routing decisions. Figure 1 shows an ex-
ample of a local controller with K equals 1, 2, 3 and 4,
respectively.
Local decision rules use available partial information
and heuristics to evaluate alternative subpaths emanating
from the decision node towards the destination, and as-
sign vehicles at that node to the link(s) immediately
downstream. The vehicle could be assigned to only one
link, or multiple successive links within the local area. At
the end node of the assigned portion, the vehicle reaches
K=4
K=3
K=2
K=1
i
j
Figure 1. Controller i with various knowledge levels.

Y. E. HAWAS 232
another local controller, where a new assignment is in-
structed. A subpath (i, j, m, K) denotes the first (K) links
of path (m) from the decision node (i) to destination (j).
Assignment decisions are reached after evaluating the
various alternative subpaths in the local area. The con-
troller uses the current state in the local area and the an-
ticipated state outside the local area to evaluate the alter-
native subpaths. The subpath evaluation is analogous to
that of the A* graph search algorithm, which uses heuris-
tic information to decide which node to scan first. The
distinctive feature of the A* algorithm is the definition of
the evaluation function, F, which has two components:
the cost of reaching the node from the start node, G, and
the cost of reaching the goal from the node, H. The node
to expand is the one for which F = G + H is minimum
[13].
Consider a vehicle v going from origin node O(v) to
destination node D(v), v = 1, ···, V. Let t denote the time
at which v is about to cross a given controller i in its way
to D(v). The problem is to assign vehicle v to an outgoing
link (or links) emanating from i. Upon reaching the
downstream end node of the assigned link(s), the vehicle
is similarly assigned to another outgoing link(s), and so
on until v reaches D(v).
The type of local assignment rule considered here se-
lects, at node i, a K-link subpath on the basis of current
knowledge of travel time, distance, and concentration
along all the possible K-link subpaths (emanating from
node i). A penalty function ,, is defined to evaluate
the K links on subpath , using their current state.
t
ij
G

The anticipated cost of non-local portion of the vehi-
cle’s trip (from the end of the subpath to the vehicle’s de-
stination) is estimated using a heuristic penalty function
,, . The total penalty, given by ,, ,,,,
,
provides the basis for evaluating the alternative subpaths.
The specification of the heuristic function may reflect
varying degrees of “knowledge”, with varying corre-
sponding effort in terms of computation, data acquisition,
data processing and/or prediction. Figure 2 shows an
example of a subpath of nodes from controller i to node j,
and illustrates the functions G and H.
t
ij
H
tt t
ij ij ij
FGH

Local Area
i j
b
G
H
Figure 2. The performance functions G and H; F = G + H.
Two different structures are discussed afterwards. The
first is a non-cooperative structure where controllers
work independently. This is denoted by the “pure” de-
centralized structure. Every controller is assumed to have
access to information and traffic measurements from its
own territory, and share no information with adjacent
controllers. The second is a cooperative structure, where
controllers are envisioned to share useful information
with adjacent controllers regarding the traffic states of
their own territories. This cooperative scheme provides
for the mechanism to enrich the knowledge base of indi-
vidual controllers.
2.1. Non-Cooperative Decentralized Route
Guidance
Hawas and Mahmassani (1996) presented the generalized
rules that can be used to distribute vehicles among seve-
ral subpaths using a logit splitting model. A generalized
subpath penalty function was developed. It comprised
local state variables (travel-time and concentration), and
non-local variables (anticipated travel time). A penalty
coefficient was introduced and associated with each state
variable to reflect the variable’s relative impact on the
subpath total penalty. The penalty function comprised
three sets of state variables: 1) local variables to measure
congestion (average weighted concentration); 2) local
and non-local variables to measure traveling distance;
and 3) local and non-local variables to measure travel
time.
The local portion of the penalty function was
specified as follows:
,,
t
ij
G
,,
,,,,,, ,,
tLLtLLtL
ijT ijKijSij
GTK    
 
L
S

(1)
where
L
T

,
L
K

, and
L
S

are the penalty coefficients of
the current local travel time along subpath at time t,

,
,,
L
t
ij
T, the current average concentration, ,
,,
L
t
ij
K
,
,,
, and the
local traveled distance, ,,ij, respectively.
L
S
L
t
ij

T

 is the
sum of the link travel times along subpath at time t;
,, is the sum of link distances along , and is given
by:
L
ij
S
,, ()
L
ij a
SS




a (2)
where is the length of link a.
()Sa
In Equation (1), ,
,,
L
t
ij
K denotes the average concen-
tration along the subpath, as an indicator of the local con-
gestion level. The current concentration also reflects the
average number of vehicles to be affected by the assign-
ment. If the coefficient
L
K

of this variable is inter-
preted as the average additional (marginal) cost imposed
on the subpath vehicles, then ,
,,
L
Lt
K
ij
K   would indicate
the additional delay (per unit distance) incurred by the
subpath vehicles. The effect on the subpath vehicles di-
minishes gradually as vehicles get further from the deci-

Y. E. HAWAS 233
sion node. Link concentrations are weighted inversely to
account for the spatially diminishing effect, as follows:
,ta
C
,
,,
()
1
()
a
Lt
ij
a
Da
K
Da







(3)
where is the current concentration (vehicles/unit
ortion of the eva-
lu
NL
,ta
C
distance) of link a at time t, and D(a) is the depth of link
a with respect to the decision node, i.
The specification of the non-local p
ation function, ,,
t
ij
H is given by:
,tNLNLtNL
,, ,,,,ij ijij
TS
H
T 
S

(4)
where,
  



N
L
T

 and
N
L
S

 are the penalty coefficients of
the non- anticipated travel-time, ,
,,
local
N
Lt
ij
T
, and the non-
local anticipated traveled distance, ,,
N
L
S
ij, respectively.
The state variable ,
,,
N
Lt
ij
T
 is an approxtion of the an- ima
ticipated non-local l time from the end of subpath
 to destination j; ,
,,
trave
N
Lt
ij
T
can be calculated by extrapo-
ing the local prevg travel time, from historical
information, or it may be replaced by corresponding in-
formation exchanged from the adjacent controllers under
the cooperative scheme as will be discussed later.
Because the actual path to be followed beyond
lat ailin
the lo-
cal area boundaries is not known a priori, heuristics are
used to obtain coarse estimates of ,,
N
L
ij
S
, and ,
,,
N
Lt
ij
T
.
While recognizing that the specification could rt
varying degrees of intelligence, and involve correspond-
ingly varying amount of computational processing; our
intent was to test very simple specifications that did not
require any network path computations for the non-local
portion.
A part,
eflec
icular specification of ,,
N
Lt
ij
T
 is given by:
,
,,
Lt
ij
,
,, ,,
,,
N
Lt NL
ij ij
ij
TS
S




  (5)
The non-local travel distance,
T
,,
N
L
ij
S

tes o
, is calculated by
su

(6)
(7)
The parameters WM and WE are selected a
th
among several feasible
su
bstituting the Cartesian coordinaf the subpath end
node bn at the boundary and those of the destination
node j into a weighted sum of both “Manhattan” (right-
angle) and “Euclidean” distances between the two points
(Equations (6) and (7)).


NL 





,,
0.5
22
jbn jbn
ij M
Ejbn jbn
xx yy
SW
Wxx yy








0,0; and 1
ME ME
WW WW 
ccording to
e general network topology. For ideal grid networks the
distance between any two nodes is the Manhattan dis-
tance, and WM = 1 with WE = 0.
This rule distributes vehicles
bpaths using a splitting model, which allocates more
vehicles to least cost subpaths, and fewer vehicles to sub-
paths with worse performance, in an attempt to equalize
the performance on all emanating feasible subpaths. A
subpath  belongs to the subset of feasible subpaths,
() ()iFiS

 (where ()
F
Si is the set of all subpaths
m i if the ing condition applies:
(1), 0
tt
FF 
emanatirong ffollow
*
,, ,, ij ij



where is the minimum value of
*
,,
t
ij
F ,,
t
ij
F

()
F
Si

For .

equals 0, ()i includes only the
best subpath, * , and this rule opes as all-or-nothing
assignment. If
erat

, then () ()iFSi .
The fraction cles assof vehii feasigned to able subpath
, is inversely proportional to the penalty value, ,,
t
ij
F
.
veral functional forms could be used for the splitting
rule. A standard logit form was used as follows:
Se
,, *
,,
,, *
,,
,, ,(),(),,,
ij
tt
ij ij
t
ij FF
f
e
pfiiijt
e










 (8)
The model allocates vehicles to any subpath based on
th
tt
ij
FF 



e difference between the subpath performance, ,,
t
ij
F
,
and the performance of the best subpath, *
,,
t
ij
F.
parameter
 is the dispersion factor and its va typi-
cally negative.
The above ru
The
slue i
le specification required the calibration of
th
2.2. Cooperative Decentralized Route Guidance
,t

(9)
The term
e time-dependent penalty coefficients. A simulation-
based optimization procedure that employs a variant of
the well-known Hill Climbing Technique was used.
The penalty coefficients were calibrated so as to optimize
the overall network performance over the analysis period
T.
A mathematical optimal control formulation is developed
for the derivation of the optimal specification of the heu-
ristic function ,,
t
ij
G, in a simplified network. The pe-
nalty function iecified as the approximate current
marginal travel time along the subpath. This can be ex-
pressed as:
s sp
,,
,,,,,, ,,
..
tLt LtL
ijijij ij
GTMKS
 


,,
,, ,,
Lt Lt
ij ij
KS

g subpath 
expresses the
ve
total number of
hicles alon. The coefficient M is the av-
erage marginal effect of the added vehicle at i on any of
the


,,
,,
Lt
(10)
,,
Lt Lt
ij ij
KS

vehicles. The heuristic function can
be specified as:
,
,, ,,
tN
ij ij
HT



Y. E. HAWAS 234
Exchanging knowledge among l
te
2.3. Cooperative Decentralized System Structure
ocal controllers is in- same knowledge level K). Figure 4 shows a simplified
network (with K = 2) where controllers share information.
As shown, controller i receives information from con-
troller c and all other depth-K controllers to improve the
specification of the heuristic function ,, . Assume
that is a subpath from i to j, where c is the boundary
node of . Assume subpath f* (f* = [c, m, d]), as shown
in Figure 4, is the least travel time subpath from c to j at
time t.
t
ij
H


nded to reduce the influence of errors introduced by the
heuristic function ,,
t
ij
H in calculating the non-local
variables. One might utilize abstract or processed infor-
mation from neighboring controllers to improve the heu-
ristic function specification. While incorporating a higher
knowledge level might increase the computational bur-
den significantly, combining abstract information (from
adjacent controllers) increases the knowledge at negligi-
ble cost. The cooperative control scheme envisions a set
of controllers connected through a two-way communica-
tion system. The exchanged knowledge is incorporated in
the heuristic function specification ,,
t
ij
H to better anti-
cipate traffic conditions in the non-local portion. Figure
3 outlines a schematic representation of the cooperative
distributed system.
Different cooperative schemes may be defined de-
pe
Controller i receives the following information items
from controller c at time t:
1) Average concentration in the local area governed by
controller c.
2) Estimated travel time estimate from c to the destina-
tion node j along the least travel time subpath, f*. The
decision controller at i utilizes this information only if c
is closer to the destination node, j.
nding on the relative locations of the controllers that
may exchange knowledge, the information to be ex-
changed, and the specification of the heuristic function
,,
t
ij
H.
3) Distance from c to the destination node j along the
least travel time subpath, f*. The decision controller at i
utilizes this information only if c is closer to the destina-
tion node, j.
This information is used by controller i to improve the
specification of the heuristic function ,, . The heuris-
tic function ,, (Equation (4)) is modified by introduc-
ing a new variable as well as a penalty factor,
t
ij
H
t
ij
H
E
K

A two-way communication system is envisioned to allow
of the
exchanged concentration from c, as will be shown later.
Travel time information from c is used to replace the
term ,
,,
N
Lt
ij
T
 in ,,
t
ij
H (Equation (4)) by **
,1 ,1
,, ,,
L
tNLt
cjf
TT

,
the controller at i to receive knowledge from those con-
trollers that reside at its boundary nodes. The territories
of any two communicating controllers will overlap and
share an area of depth K (if both controllers have the cjf
Controller i
Goals
Local Rules
A
lternatives
Evaluation
Choice:
Sub-path
(selection &
Share)
A
bstract
Knowledge
Raw
Information
Controller
c
Goals Local Rules
A
lternatives
Evaluation
Choice:
Sub-path
(selection &
Share)
A
bstract
Knowledge
Raw
Information
Knowledge Transfer Protocol
Figure 3. Structure of the cooperative decentralized system.

Y. E. HAWAS 235
Figure 4. Information exchange with spatial propagation.
here ,1Lt
T is the prevailing travel time along subpath w*
,,cjf
e t −f* at tim 1, and *
,1
,,
N
Lt
T
 denotes the “anticipated”
non-local travel time fro boundary node of subpath
f* (node d as shown in Figure 4) to j, at time t − 1. Simi-
larly, the distance information is used to replace ,,
cjf
m the
N
L
S

(in Equation (4)) by **
LN L
SS, where, L
cj
S
ij
*
,,f is
2.4. Knowledge Exchange Protocol
ing knowledge
,,cjf ,,cjf
traveled alothe prevailing distanceng subpathnd f*, a
*
NL
S
 denotes the “anticipated” non-local distance from
,,cjf
the boundary node of subpath f* (node d) to j.
Figure 5 shows a controller i exchang
with all the boundary controllers [a, b, c, e, f, g, k]. In the
figure, concentration information is exchanged between i
and all depth-K controllers. Travel time and distance in-
formation are utilized from three boundary controllers
only [a, b, c]. Denote by, ,
,,
E
t
ij
K, the concentration re-
ceived by i (from the control the end node of , c)
at time interval t.
ler at
E
K

is the penalty coefficient of the
concentration term, ,
,,
E
t
ij. As indicated previously, this
information is procesy controller c, at interval t − 1.
The heuristic function ,,
t
ij
H (for subpath  from con-
troller i at time t) is now re-specified as:

,1
,Lt tNLNLt


 

K
sed b

**
**
,1
,,,, ,, ,,
,, ,, ,,
,
,,
NLt
ij ij
Tcjf cjf
LNL
NL NL
ij
Scjf cjf
EEt
Kij
TT
HxTy
SS
xS y
K






 








e, x and y are binary indicators. x = 0 and





(11)
wher y = 1 if
fication
derived using the optimal control theory. The exchanged
kn
**
,, ,, ,, ij cjf cjf 
(12)
where Mrginal cost of f.
Note that, is forced to
re individual controllers may have full access
to
rt of the
ad
ong controllers,
i.e
sign
nducted to assess the ef-
d reactive approach, with
the Manhattan distance from c to j is greater than the
Manhattan distance from i to j, otherwise, x = 1 and y =
0. In other words, the travel time and distance informa-
tion are utilized only if the relaying controller, c, is closer
to the destination node, j, than the receiving controller, i.
The above specification replaces the heuristic function
non-cooperative specification (Equation (4)).
The same protocol is also applied to the speci
owledge is utilized to enhance the heuristic function
(Equation (10)) by adding a term that captures the mar-
ginal cost along subpath, f*. The travel time information
is also utilized according to the binary values of x and y,
as indicated above. The specification of the heuristic
function becomes:

,1 ,1
,
,,
Lt NLt
tLt
ij TT
HxTy

 




*
,
,,
2,,
Et L
ij cjf
KS
M 
2 is the coefficient of the ma
if the concentration coefficient, M2
*
a value of 0, it will represent the case that concentration
information is not exchanged among controllers. Various
operational modes can be tested based on the values of x,
y, and M2:
1) FCD refers to the fully cooperative decentralized
system whe
knowledge processed by adjacent depth-K controllers,
i.e. x and y values are set according to the controllers
locations with respect to the destination node.
2) PCD refers to the partially cooperative distributed
system where controllers may only access pa
jacent controllers’ information (the concentration is
not shared among controllers), i.e. x and y values are set
according to the controllers locations with respect to the
destination node, but M2 is set to 0.
3) NCD which refers to the non-cooperative scheme
that permits no information exchange am
. x = 1, y = 0, M2 = 0.
3. Experimental De
Simulation experiments are co
fectiveness of the decentralize
particular emphasis on the cooperative scheme. The latter
is tested under various scenarios of network congestion,
and knowledge levels. The experiments address the fol-
lowing aspects:

Y. E. HAWAS 236
j
C
a
b
e
f
h
Depth = K
g
g
m
n
Controller m: shares only concent rat i on w it h i, x=0, y= 1
Controller n: shares Conce ntrat i on, T ravel Ti m e and D i st ance w i t h i, x=1 , y = 0
i
Figure 5. Type of Information utilized from depth-K controllers.
 The performance of the
amined under various network congestion and know-
r various network congestion levels,
decentralized scheme is ex-
ledge levels.
 The cooperative scheme is evaluated against the above
scenarios, fo
knowledge levels, and the three operational modes
discussed earlier (FCD, PCD and NCD). By compar-
ing the network performance under both non-coopera-
tive and cooperative decentralized schemes, the mar-
ginal effect of the knowledge exchange can be as-
sessed under the various knowledge and congestion
levels. Under the FCD mode, travel time, distance
and concentration information could be exchanged.
The PCD mode allows only travel time and distance
to be exchanged. Exchanged information replace the
heuristic estimates as warranted by the protocol pre-
sented earlier. The difference in performance between
the NCD, PCD, and FCD modes could be attributed
to the effect of exchanged information in the latter
modes. Similarly, the difference between the FCD
and PCD modes is attributed to the effect of the addi-
tional information (namely, ,
,,
E
t
ij
K, average concen-
tration).
Simulation Modeling
To test the overall network performance under the con-
decentralized architectures,
an analysis period of T (60 minutes) is defined. The solu-
pes of control is simulated over
i-sim-s simulator (Hawas 2007,
Ea
trol of both centralized and
tions obtained by both ty
the analysis period using
Hawas and Abdel Hameed, 2009), and estimates of the
overall network travel time are obtained for comparative
analysis of effectiveness.
One hypothetical network is coded for testing. The
hypothetical network links are bi-directional with same
posted (free-flow) speed. The use of hypothetical net-
works for the assessment of the algorithms is quite ade-
quate as it enables testing various scenarios of network
size, link lengths, speeds, etc. The hypothetical testing
network as shown in Figure 6 has 49 nodes, 14 origins
and 24 destinations. All intersections are operated with
pre-timed controllers. The network is tested under vari-
ous conditions of network congestions (demand levels)
as shown in Table 1.
The experimental setup accounts for the effect of the
operational modes (column one), variations in the know-
ledge levels (second column), and the variation in the
OD demand pattern (third column). The first (1st) column
shows the operational modes (FCD, PCD, and NCD).
ch mode is tested with three knowledge levels, K (1, 3,
5). Each operational mode (and knowledge levels) is
tested with three demand scenarios. As the table indicates

Y. E. HAWAS 237
500 500
500
500
500
500
500
500
500
500
500
500
500
500
(a)
1000 1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
(b)
2000 2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
(c)
Figure 6. Demand patterns of the test network: (a) Low; (b)
Medium and (c) High intensities.
Table 1. Testing scenarios.
Operational
Mode
Knowledge
Level (K)
Source Volume
(veh/hr)
500
1000 1
2000
500
1000 3
2000
500
1000
FCD
(Fully Cooperative)
5
2000
500
1000
1
500
1000
1000
PCD
(Partially Cooperative)
5
1
3
NCD
(Not-Cooperative)
5
Benchmark: SPA
(Shortest Path Algorithm)
2000
3
2000
500
2000
500
1000
2000
500
1000
2000
500
1000
2000
500
1000
2000
the FCD is tested twenty seven (27) times.
The “network demand” scenarios are aime
ing the effect of the operational mode, and ow-
ledge level under various network demand vos. As
such, all the network demand experiments are carried out
for the same network topograp (link leng kept
fixed; 500 m) and same link speed (80 km/hr).
The traffic loading intensity varies from loource
volume of eh/hr), mediumource volum1000
veh/hrce volume of 2000 veh/n all
tested scenarios, the source volumes are equally distri-
buted among all possible destinations.
The Shortest Path AlgorithmSPA) is us the
benchmark in all the above set of experimentat is,
d at study-
the kn
elum
hyth is
w (s
500 v (se of
r) and high (souhr). I
(sed a
s. Th

Y. E. HAWAS 238
the resulting network performance (the overatwork
tra thorrespondilue if
a ryed.
Ex
dation in
pe
of 500, 1000 and
mark SPA
Travel Time
with Respect to
NCD
ll ne
vel
eal-time SPA is deplo
time) is compared withe cng va
4. Experimental Results
periments with the various operational modes were
conducted using various network demand levels (500,
1000 and 2000 veh/hr) and knowledge levels (1, 3 and 5),
and results are summarized in Table 2 and Figure 7.
At very low knowledge levels, vehicles may cycle in
the network, and this may lead to high degra
rformance compared to the benchmark. The results in-
dicate that the marginal improvement in performance is
higher for low knowledge levels.
The decentralized scheme is tested under three know-
ledge levels (1, 3 and 5), demand levels
Table 2. Cooperative decentralized system performance.
Demand
Level
Knowledge
Level
Operational
Mode
Total Travel
Time as % of the
Bench
Difference in
Performance
NCD 131 -
PCD 126 5 1
FCD 124 7
NCD 122 -
PCD 120 2 3 500
FCD 117 5
NCD 118 -
PCD 117 1 5
FCD 116 2
NCD 137 -
PCD 130 7 1
FCD 122 15
NCD 122
5
1
3 2000
NCD 123 -
PCD
FCD
120
118
3
5
-
3
PCD 119 3
1000
FCD 118 4
NCD 142 -
PCD 135 7
FCD 128 14
NCD 131 -
PCD 127 4
FCD 124 7
NCD 129 -
PCD 128 1 5
FCD 126 3
N
CD
PCD
FCD
K=1
3
K=5
K=
105
110
115
0
125
0
135
% Relative Trave
Time 12
l
13
O
p
eratio na
l
Mode
Knowledge
Soume = 500 v
(a)
Level
urce Voleh/ h r
N
CD
PCD
FCD
K=1
K=3
K=5
105
110
115
120
125
130
140
% Relative Travel
Time
Operational
Mode
Knowledge Level
Soume = 1000 veh
(b)
135
rce Volu/hr
N
CD
PCD
FCD
K=1
K=3
K=5
11 5
120
125
130
135
% Relative Travel
Tim e
O
140
145
p
erationa
l
Mode
Knowledge Level
(c)
Figure 7. Performance of various cooperative schemes un-
der various knowledge levels and (a) Low; (b) Medium and
(c) High traffic intensities.
Source Volume = 2000 veh/hr
2000 veh/hr, and the three operational modes (FCD,
PCD, and NCD). Table 2 shows the performance of the
various operational modes in relative terms of the corre-
sponding benchmark performance.
The results indicate that under low congestion levels
(500 veh/hr), the relative performance of the FCD mode
ranges from 116% to 124%, and that makes this coopera-
tive mode even more competitive with the centralized

Y. E. HAWAS 239
SPA scheme.
Under the 500 veh/hr scenario, the FCD mode resulted
in about 7% reduction in overall travel time with know-
ledge level of 1, 5% with knowledge level of 3, and only
2% with knowledge level of 5 when compared to the
non-cooperative scheme NCD. Under highly congested
situations (2000 veh/hr), the reductions in overall travel
time are 14%, 7% and 3% for knowledge levels of 1, 3
and 5, respectively. The relative performance of the FCD
mode ranges from 126% to 128%.
The effect of adding ,
,,
L
t
ij
K to the heuristic function
(between the FCD and PCD schemes) is notable at low
knowledge and/or low congestion levels. At high know-
ledge levels, the concentration information, ,
,,
L
t
ij
K, ap-
pears to have a limited im on performance, and the
local concentration variable,
pact
, ,,
L
t, becomes adequate to
) achieved with the partial
sess the effectiveness of the
pr
nal cost associated with the centralized systems,
th
territo-
ries. Such improvement is thought of as a way to over-
opology changes, the
ij
capture the marginal cost.
The higher the knowledge level, the lesser the im-
provement (compared to NCD
K
information scheme, PCD. Under limited knowledge le-
vels, system performance can be enhanced by exchanged
information. At high knowledge levels, the time lag as-
sumed in transferring knowledge affects the accuracy of
heuristic function estimates as compared to actually ex-
perienced values, and situations where the PCD mode, or
even the FCD mode, are worse than NCD could be ob-
served.
To conclude, it is evident that the fully cooperative
mode, FCD, exhibited a highly competitive performance
compared to the centralized SPA scheme. The gain in
performance achieved by the cooperative scheme de-
clines with higher knowledge levels. The enhancement in
performance under low knowledge levels, at which the
non-cooperative scheme seems less effective, is quite
significant. By achieving significant enhancement in per-
formance under low knowledge levels, with negligible
computational cost, the decentralized cooperative system
becomes a very appealing route guidance system.
5. Concluding Comments
This paper presented a decentralized architecture that can
be employed as a cooperative scheme for real-time route
guidance in urban traffic nes. Simulation experi-
ments were performed to as
twork
oposed architecture. Under the cooperative scheme, the
performance under low knowledge levels, at which the
non-cooperative scheme seems less effective, is highly
competitive with the SPA. By achieving significant en-
hancement in performance under low knowledge levels,
with negligible computational cost, the decentralized co-
operative system becomes a very appealing route gui-
dance system with good potential for early deployment.
Bearing in mind the massive data processing and high
operatio
e instability and communication constraints associated
with the IVC-based systems, this paper seeks to provide
improvement to the pure non-cooperative decentralized
systems. The improvement is intended to resolve the re-
ported cycling problems commonly encountered in the
typical pure distributed systems. The improvement is
sought through allowing for information exchange (or
cooperation) among the various decentralized controllers.
In a sense, we investigate the possibility of using inter-
controller communication for exchanging knowledge
regarding the traffic conditions in their respective
come the limitations of the rapid t
frequent fragmentation and poor communication associ-
ated with the IVC-based systems, as well as the limita-
tions of the heavy processing and cost of the centralized
systems.
Further work will include the comparison of the pre-
sented system against the IVC-based route guidance sys-
tems reported in Hawas et al. (2009). It is expected that
the two systems may exhibit similar performance as
compared to the centralized system. Nonetheless, the
cooperative decentralized system is expected to add no
significant burden on the communication network. That
is, in this case the IVC-based system, each vehicle com-
municates with many other vehicles, and this implies
heavy communication and inter-vehicle processing re-
quirements. In the case of the cooperative decentralized
system the communication requirements are heavily re-
duced as each vehicle communicates only with one con-
troller at a time. The fact that this communication is local
with short distances allows for cheap communication
media to be utilized.
REFERENCES
[1] J. L. Adler, et al., “A Multi Agent Approach to Coopera-
tive Traffic Management and Route Guidance,” Trans-
portation Research Part B, Vol. 39, No. 4, 2005, pp. 297-
318. doi:10.1016/j.trb.2004.03.005
[2] J. Anda, et al., “VGrid: Vehicular ad Hoc Networking
and Computing Grid for Intelligent Traffic Control,”
Proceedings of the IEEE 61st Vehicular Technology Con-
ference, vol. Vol. 61, No. 5, 2005, pp. 2905-2909.
[3] L. Chen, et al., “VGITS: ITS Based on Intervehicle
Communication Networks and Grid Technology,” Jour-
nal of Network and Computer Applications, Vol. 31, No.
3, 2007, pp. 285-302. doi:10.1016/j.jnca.2006.11.002
[4] Y .E. Hawas, “A Microscopic Simulation Model for In-
cident Modeling in Urban Networks,” Transportation
Planning and Technology, Vol. 30, No. 2, 2007, pp. 289-
309. doi:10.1080/03081060701398117
[5] Y. E. Hawas and M. Abdel Hameed, “A Multi-Stage
Procedure for Validating Microscopic Traffic Simulation
Models,” Journal of Transportation Planning and Tech-
nology, Vol. 32, No. 1, 2009, pp. 71-91.

Y. E. HAWAS 240
doi:10.1080/03081060902750686
[6] Y. E. Hawas and H. S. Mahmassani, “Comparative
Analysis of Robustness of Centralized and Distributed
Network Route Control Systems in Incident Situations,”
Transportation Research Record, Vol. 1537, 1996, pp.
83-90. doi:10.3141/1537-12
[7] Y. E. Hawas, et al., “Comparative Assessment of In-
ter-Vehicular Cofor Real-
Time Traffic rnal of Intelligent
mmunication (IVC) Algorithms
Route Guidance,” Jou
Transportation Systems: Technology, Planning and Ope r a -
tions, Vol. 13, No. 4, 2009, pp. 199-217.
doi:10.1080/15472450903323107
[8] J. Jeremy, et al., “Challenges of Intervehicle ad Hoc
Networks,” IEEE Transaction on Intelligent Transporta-
tion System, Vol. 5, No. 4, 2004, pp. 347-351.
doi:10.1109/TITS.2004.838218
[9] C. J. Jiang, et al., “Research on Traffic Information
Grid,” Journal of Computer Search and Development,
Vol. 40, No. 12, 2003, pp. 1676-1681.
[10] H. S. Mahmassani and S. Peeta, “System Optimal Dy-
namic Assignment for Electronic Route Guidance in a
Congested Traffic Network,” Springer-Verlag, Heidel-
berg, 1995.
[11] H. S. Mahmassani and Y. E. Hawas, “Expe
Rolling Horizon Dynamic Route
riments with a
Guidance Algorithm:
le Traffic
s of the 2004 IEEE In-
, Assignment and
oblem Solving,” Addison-Wesley Publishing
ol. 27, No. 6, 1982, pp.
Robustness under Stochastic Demands,” Paper Presented
at the INFORMS, Atlanta, 1996.
[12] T. Nadeem, et al., “Traffic View: A Scalab
Monitoring System,” Proceeding
ternational Conference on Mobile Data Management,
Berkeley, 19-22 January 2004, pp. 13-26.
[13] M. Papageorgiou, “Dynamic Modeling
Route Guidance in Traffic Networks,” Transportation
Research, Vol. 24, No. 6, 1990, pp. 471-495.
[14] J. Pearl, “HEURISTICS: Intelligent Search Strategies for
Computer Pr
Co. Inc., Boston, 1984.
[15] P. E .Sarachick and U. Ozguner, “On Decentralized Dy-
namic Routing for Congested Traffic Networks,” Trans-
actions on Automatic Control, V
1233-1238.
[16] L. Wischhof, et al., “Information Dissemination in Self
Organizing Intervehicle Networks,” IEEE Transactions
on ITS, Vol. 6, No. 1, 2005, pp. 90-101.