TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol. 12, No. 9, September
2014, pp. 66
9
9
~ 671
0
DOI: 10.115
9
1
/telkomni
ka.
v
12i9.603
6
6699
Re
cei
v
ed Ma
rch 3
0
, 2014;
Re
vised June
25, 2014; Accepte
d
Jul
y
2
0
, 2014
Bee Inspired Zonal Vehicle Routing Algorithm in Urban
Traffic
Lei Wu*
1
, Licai Yang
1
, Haiqing Liu
1
, Ya
o Zhang
1,2
1
School of Co
n
t
rol Scienc
e an
d Engi
ne
erin
g,
Shan
do
ng Un
i
v
ersit
y
, Jin
an 2
500
61, Ch
ina.
2
School of Mec
han
ial, Electric
al & Informatio
n
Engi
ne
erin
g, W
e
ihai
264
20
9
,
China
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
w
u
lei-
17
@16
3
.com
A
b
st
r
a
ct
Dyna
mic
Rout
e Guid
ance Sy
stem, w
h
ich ca
n provi
de
th
e d
r
ivers w
i
th the opti
m
a
l
routes,
is one
o
f
the
most effici
ent sol
u
tio
n
s t
o
the
traffic
ja
m. T
h
is
pa
per
prese
n
ts a
b
ee i
n
sp
ired
z
o
nal v
e
h
i
cle
rou
t
in
g
alg
o
rith
m to
pr
ovid
e a r
eas
on
abl
e a
nd
effective o
p
ti
mal
rou
t
e for the Dy
n
a
mic R
oute G
u
id
ance
Syste
m
.
F
i
rstly, the pr
o
pose
d
alg
o
rith
m
divi
de
d th
e
w
hole traffic
n
e
tw
ork into
diff
erent traffic
gu
i
danc
e
z
o
ne
b
a
s
ed
o
n
Sh
ap
l
e
y valu
e
g
a
m
e
. Th
en
, re
al
tim
e
traffi
c d
a
t
a
wa
s co
l
l
e
cte
d
i
n
e
a
c
h
tra
ffi
c gu
id
a
n
ce
z
one b
y
i
n
te
r-
vehicl
e a
nd v
e
hicle-t
o
-infrastr
u
cture co
mmu
nicati
ons.
Ulti
m
ate
l
y, the
pro
posa
l
si
mu
late
d the
bee f
o
ra
gin
g
phenom
e
non in the
biologic
a
l system
to synchronous
ly c
o
m
p
ute the
optim
al routes
in each traffic guidanc
e
z
o
n
e
. T
h
e si
mu
lati
on r
e
sul
t
s show
that
the a
l
gor
it
h
m
has hig
her
c
o
mp
utatio
n
effi
ciency un
der th
e
preco
nditi
on of
provid
ing th
e glo
bal o
p
ti
ma
l route.
Ke
y
w
ords
: be
e insp
ired, traffic gui
danc
e
z
o
ne, opti
m
a
l
rou
t
e, dyna
mic ro
ute gui
da
nce s
ystem
.
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
In recent years, the co
nsta
nt
ly accel
e
rating of urb
ani
zation and m
o
torization p
r
og
ress of
mode
rn
city lead
s to veh
i
cula
r num
be
r increa
sin
g
year by yea
r
. The u
r
ba
n
traffic faces
unprecede
nte
d
p
r
e
s
sure,
and th
e traffic ja
m o
c
curs
more
and
more
often,
whi
c
h i
n
curs the
traffic accide
nt, energy waste, and en
vironme
n
ta
l pollution that
has be
com
e
the most so
cial
focu
s. Intellig
ent Tran
spo
r
tation Syste
m
(ITS) i
s
a
n
effective a
ppro
a
ch to
solve urban t
r
affic
con
g
e
s
tion,
ensure
traffi
c
safety, an
d imp
r
ov
e t
r
an
spo
r
tation
efficien
cy.
Dynami
c
Ro
ute
Guida
n
ce System (DRGS
)
, as an im
portant pa
rt
in ITS, can provide
re
liable guid
a
n
c
e
informatio
n, p
l
an o
p
timal travel path,
avoid
con
g
e
s
tio
n
re
gion,
and
bala
n
ce n
e
twork t
r
affic l
o
ad
by real time t
r
affic d
a
ta a
c
quisitio
n
an
d
dynam
ic traffic info
rmation
pro
c
e
s
sing.
The
DRGS can
utilize the
n
e
twork
ca
pa
city adeq
uat
ely to real
i
z
e the o
p
timization
of urb
an road
net
work
manag
eme
n
t and control.
In the traditi
onal
static route g
u
ida
n
ce sy
stem th
e ind
e
x of
route
choi
ce
model
is
gene
rally di
stance, th
at i
s
cal
c
ulatin
g
the
sh
o
r
te
st path. T
he
most
com
m
o
n
ly method
s are
Dijkstra, A*,
Floyd, and
so on. Th
ese
algo
ri
thms
have adva
n
tage
s an
d di
sadvantag
es.
The
Dijkstra
algo
rithm can
cal
c
ulate the opti
m
al sol
u
tion
of the sho
r
te
st path, ho
wever its e
r
go
dic
node n
u
mbe
r
is exce
ssive
so as to re
d
u
ce its effici
e
n
cy. It is suitable for small
network, but
its
efficien
cy
dro
p
s whe
n
the netwo
rk be
co
mes l
a
rg
e. T
he Floyd
alg
o
rithm e
n
cod
e
s
simply, an
d it
can
cal
c
ul
ate
the sho
r
test
path b
e
twe
e
n
any two n
ode
s. Its efficien
cy is hig
her th
an
Dijkstra
algorith
m
in
den
se dia
g
ra
m, but the same a
s
Di
j
k
stra al
go
rith
m, it is not suitabl
e for l
a
rge
netwo
rk a
nd
huge d
a
ta co
mputation be
ca
u
s
e of its hi
gh time com
p
lexity.
Since the
ro
ad network b
e
com
e
s m
o
re and mo
re
compl
e
x, and
the traffic co
nge
stion
become
s
mo
re a
nd mo
re
comm
on, the
real time
va
riation
of co
n
gestio
n
info
rmation i
s
hig
h
ly
nonlin
ear a
n
d
mutability. The Tra
d
itional stat
i
c
route guid
a
n
c
e system h
a
s
not bee
n full
y
con
s
id
ere
d
th
e interfe
r
en
ce of traffic j
a
m to the g
u
id
ance sy
stem,
and th
e gui
d
ance efficie
n
c
y
decrea
s
e
s
a
s
the nonlin
ea
r and m
u
tabl
e con
g
e
s
ti
on
informatio
n can be
reflect
ed in the mo
del.
Hen
c
e, th
e d
y
namic
ro
ute
guida
nce
syst
em with
t
he i
ndex
su
ch
as time, cost, fu
el con
s
umpti
on,
become
s
mai
n
stre
am. The
route ch
oice
model gene
rally calcul
ate
s
the sho
r
te
st path with th
e
time index i
n
DRGS.
Well-kno
w
n m
e
thod
s a
r
e
D*, tabu
se
arch al
gorith
m
, ant colo
ny
optimizatio
n, and
sim
u
lat
ed a
nneali
n
g
algo
rith
m,
etc. Fo
r the
enla
r
gem
en
t of urb
an
road
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 9, September 20
14: 66
99 – 671
0
6700
netwo
rk a
nd
the increa
se
of node num
ber, the se
arch re
gion a
n
d
the calcula
t
ion quantity o
f
these
alg
o
rit
h
ms in
cre
a
se, re
sultin
g i
n
the
large
computation
ti
me a
nd l
o
w
efficien
cy, which
can
not meet the real time
requi
reme
nt in
DRGS. Rese
arche
r
s p
r
esented m
a
ny algorithm
s to
improve
the optimal route
se
ar
chin
g
p
e
rform
a
n
c
e
in complex
road
network with
de
crea
sing
sea
r
ching
scales, su
ch a
s
re
stri
cted search
area a
l
gorithm [1], and hie
r
archi
c
al se
arch a
r
ea
algorith
m
[2], etc. These algorit
h
m
s
can improve the v
ehicl
e routing efficie
n
cy to a ce
rtain
extent, but they are
ea
sily leadin
g
to a l
o
cal
opt
imal
route du
e to the limitation
of sea
r
ch a
r
e
a
.
Even the hierarchi
c
al
sea
r
ch a
r
e
a
alg
o
rithm o
ften lead
s the vehicle into the backb
one lay
e
r,
whi
c
h n
o
t o
n
ly misses the glo
bal o
p
t
imal rout
e,
but also re
sults in
con
g
estion, a
nd
even
con
g
e
s
tion transfe
r or
cau
s
ing n
e
w
con
gestio
n
.
For this
purp
o
se, this
pap
er presents
a
zonal
ve
hicl
e routin
g alg
o
rithm to de
crea
se the
spa
c
e
com
p
l
e
xity of route cal
c
ul
ating.
Mean
while,
this alg
o
rith
m employ
s the be
e in
spi
r
ed
strategy to im
prove the efficien
cy
of rout
e finding. Simulation in a
n
actual net
work i
s
given, and
the re
sults
show th
at on t
he ba
si
s of e
n
su
ring
th
e g
l
obal o
p
timal
route, the p
r
opo
sal p
e
rfo
r
ms
better efficien
cy in route
co
mputation.
2. Bee Natur
e
and Be
e Colon
y
Optimizatio
n
Social in
se
cts su
ch a
s
an
ts and be
es
have a
kin
d
of instinct cal
l
ed gro
up int
e
lligen
ce,
whi
c
h ca
n make the g
r
oup highly coordi
nated,
and complet
e
compli
cate
d and intelli
gent
behavio
r. Th
e wo
rke
r
be
es b
r
ing the
necta
r
ba
ck to their nets and ex
cha
nge the ne
ct
ar
informatio
n
with their
co
m
panio
n
throu
gh
spe
c
ific d
ance
called
“8 Dan
c
e” in
orde
r to
attra
c
t
other b
e
e
s
fol
l
ow them to
realize the opt
imizat
ion
of g
r
oup fo
ra
ging
behavio
r. Th
e dan
ce fo
rm
is
clo
s
ely rel
e
va
nt to the harv
e
st, su
ch a
s
duratio
n, angl
e, rhythm, wh
ich
can exp
r
e
ss th
e yield o
n
the visited flo
w
ers. Th
e yie
l
d ca
n be
re
g
a
rde
d
a
s
the function with the
inde
pen
d
ent
varia
b
le of
honey q
uality, quantity, and dista
n
ce. T
he othe
r b
e
e
s
ob
se
rved th
e “8
Da
nce”
and follo
we
d
with
a certain probability, that i
s
, to forage t
o
the
position that the dance indi
cated. The foll
owi
n
g
probability is positive correlation
to the intensity of the dance,
consequently to
the previous
foragin
g
yield
of the da
ncer. The be
e swarm
can
fo
rm
the optimi
z
at
ion of extra
c
ti
on of the
hon
ey
sou
r
ce thro
ug
h this self
-org
anization mo
de.
This process
can be introd
uce
d
to solve
t
he optimization pro
b
lem, whi
c
h is calle
d bee
colo
ny algorit
hm [3]. The bee col
ony is
a bioni
c algo
rithm based o
n
the self-org
anization mo
del
and
swarm in
telligen
ce
of
bee
swarm in
the n
a
ture.
A bee
po
pula
t
ion con
s
ist
s
of thre
e
kind
s of
bee
s: the em
ployed be
e, the onl
oo
kers,
and the
scou
ts. At the very beginnin
g
, half of the col
ony
is the
emplo
y
ed bee,
an
d the oth
e
r i
s
the
onlo
o
ker. The
swa
r
m intelligen
ce of fora
ging
is
achi
eved by
the comm
uni
cation
a
nd co
operation am
ong different
kind
s of
be
es.
The so
urce
is
introdu
ce
d in
the model to rep
r
e
s
ent all possibl
e
solutio
n
s. Th
e prog
re
ss of foraging is
the
pro
c
e
ss
of searchin
g for
the optimal
solutio
n
.
The
basi
c
b
eha
vior of bee i
s
to search,
to
evaluate, a
n
d
to ab
and
on t
he
sou
r
ce. T
he valu
e of
th
e source
is in
dicate
d by th
e yield fu
ncti
on.
The yield fun
c
tion i
s
a jud
g
ment, whi
c
h
determi
ne
s the optimi
z
ati
on directio
n. The p
r
o
c
e
ss
of
solving the o
p
timal solutio
n
is the proce
ss of se
a
r
chi
ng high yield
sou
r
ce. The
r
efore, the ov
erall
goal i
s
to solv
e the optimal
solutio
n
of the yield functio
n
. The em
plo
y
ed bee
s corresp
ond to the
i
r
sea
r
ching
so
urce, in
other wo
rd th
e so
urce i
s
the ta
rget of th
e e
m
ployed
bee
s. The
onl
oo
kers
obtain the
yield info
rmati
on fro
m
the
employed
be
es i
n
the
da
nce
re
gion.
The p
r
o
babili
ty of
sou
r
ce sele
ction is p
r
op
ort
i
onal to the
honey
qu
anti
t
y, namely the yield of so
urce. Wh
en t
h
e
yield of source is relatively
low, it will be aban
don
ed
. Meanwhil
e
, the co
rre
sp
o
nding em
ploy
ed
bee to thi
s
source
will be
come
a
sco
ut. The sco
u
ts
rand
omly sea
r
ch
the ne
w
sou
r
ce ne
ar t
h
e
old so
urce so
as to jump o
u
t of local opt
imal boun
dary.
Karab
oga
su
ccessfully ap
plied the a
r
tificial
be
e colony (ABC)
al
gorithm to n
u
meri
cal
optimizatio
n i
n
200
5 [4], and propo
se
d
a syste
m
atic
ABC algo
rith
m, whi
c
h i
s
si
mple an
d rob
u
st
with the sup
e
rio
r
ity in numeri
c
al optim
izati
on of un
restrai
n
t probl
em. In 2006, Karabog
a a
nd
Basturk utili
zed the ABC t
o
solve
re
strained
nume
r
i
c
al o
p
timizati
on [5], and o
b
tained
a go
od
effec
t.
In combinatorial optimi
z
ation, Chi
n
et
al.
ut
ilized bee
colony al
gorit
hm to
solve workshop
scheduling problem [6], and they
solved the travellin
g salesm
an
probl
em by
using bee
colony
optimizatio
n i
n
200
8 [7].
Alok et
al. succe
ssf
ully f
ound th
e mi
nimum
spa
n
n
ing tree
with leaf
con
s
trai
nt in a certai
n undi
recte
d
wei
ght
ed gra
ph by usin
g ABC algorithm [8]. Kou et al. applied
the ABC
alg
o
rithm to
sol
v
e the TSP
probl
em [9],
and
put forward th
e im
provements of
the
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Bee Inspi
r
ed
Zonal Vehi
cle
Routing Algo
rithm
in Urba
n Traffic (Lei
Wu
)
6701
para
m
eters,
whi
c
h
perfo
rmed g
ood
eff
e
ct. Hu et
al
. reali
z
ed
the a
pplication of ABC
alg
o
rith
m
in
the path plan
ning problem
in weldi
ng en
ginee
ring [10]
.
3. Traffic G
u
idance Zo
ne
Partition
3.1. Definitio
n
of Traffic
Guidanc
e
Zo
ne
A com
p
lete
road n
e
two
r
k
con
s
i
s
ts of va
st ro
ad
se
ctio
ns
and i
n
tersection
s. Th
e
obje
c
t of
traffic
c
o
ntrol
z
o
ne is
intersec
tion.
However t
he traffic guidan
ce
zo
ne prefers ro
ad sectio
n, with
the pa
ram
e
te
rs such a
s
t
r
affic flow,
o
c
cup
a
n
c
y, and
satu
ratio
n
et
c. Th
e u
r
ba
n
ro
ad
network i
s
abstracte
d a
s
a con
n
e
c
ted
dire
cted g
r
a
ph, whe
r
e th
e node
s in
dicate the intersection
s, and t
he
edge
s indi
cat
e
the ro
ad
se
ction
s
. The at
tachme
nts
fo
rm a network topolo
g
y stru
cture, whi
c
h
can
be expre
s
sed
as follows:
}
,
{
A
R
S
(1)
Whe
r
e
R
={
r
1
,
r
2
, …,
r
n
} i
n
d
i
cate
s the
set
of road
secti
ons,
and
n
is
the numb
e
r of
ro
ad
se
ct
ion
s
;
A
={
a
1
,
a
2
, …,
a
n
}
indicates
the set
of attribut
e
of
R
, that is
a
i
={
a
i1
,
a
i2
, …,
a
ip
} represe
n
ts
the set of all attributes of
road sectio
n
r
i
, s
u
ch as traffic
flow, tr
avel time, averag
e sp
e
ed,
saturation, an
d occup
a
n
c
y, and
p
is the
numbe
r of attribute
s
. Beca
use the di
me
nsio
ns of all t
he
attributes a
r
e
different, normalizatio
n m
u
st be do
ne b
e
fore data p
r
oce
s
sing.
Traffic gui
da
nce
zon
e
is defined a
s
a
large net
wo
rk, whi
c
h div
i
des the enti
r
e ro
ad
netwo
rk i
n
to
different re
gion
s a
c
cord
ing to the traffic ch
ara
c
t
e
risti
cs li
ke t
r
affic flow, fl
ow
dire
ction, saturation, a
nd
occup
a
n
c
y etc. Wh
en
the
traffic flow
guida
nce an
d vehicl
e ro
u
t
ing
occur,
optima
l
path
se
arch
is
parallelly i
m
pleme
n
ted i
n
ea
ch
traffic guid
a
n
c
e
zo
ne
sep
a
rately
.
These rel
a
tively indepe
nd
ent zon
e
s a
r
e
the traffic gui
dan
ce zone
s,
noted as
u
(
o
ik
,
G
i
), which a
r
e
the non-null subsets of
enti
r
e ro
ad net
wo
rk
S
={
R
,
A
}.
3.2. Optimization Goal
Analy
s
is
Traffic
zo
ne i
s
a
set
of adj
ace
n
t ro
ad
se
ction
se
rie
s
, i
n
whi
c
h
the
n
ode
s have
hi
gh traffic
simila
rity to each
othe
r. Mean
while, the
roa
d
se
ctio
n
quantitie
s of
different
traffic zone
s a
r
e
as
balan
ce
d as
possibl
e, and
each
roa
d
section o
n
ly
b
e
long
s to on
e traffic zone
. Therefo
r
e, the
optimizatio
n goal of traffic guid
a
n
c
e zone pa
rt
ition
and its con
s
traint
s can
be expresse
d as
follows
:
12
12
12
1
(,
,
,
)
(,
,
,
)
(,
)
m
a
x
(
(
,
)
,
(
,
)
,
,(
,
)
,
,
(
,
)
)
()
,
,1
i
t
ii
i
i
N
ik
i
i
k
i
k
ik
i
i
k
t
i
s
im
i
num
t
ij
k
j
GG
G
G
Go
o
o
uo
G
u
o
G
uo
G
uo
G
u
o
G
Sim
G
N
oG
x
(2)
Whe
r
e
G
in
di
cate
s the
set of zone
s
an
d
t
re
present
s the
zone
n
u
mbe
r
.
o
i1
,
o
i2
,…,
o
iN
t
are the road
se
ction
s
of Zone
i
, and
N
i
is the road
se
ction num
b
e
r in Zon
e
i
.
u
(
o
ik
,
G
i
) is t
h
e
correl
ation b
e
twee
n
o
ik
a
nd Z
one
i
,
wh
ic
h is de
te
rmin
e
d
b
y
bo
th
th
e d
i
s
t
a
n
ce
-
p
os
itio
n facto
r
s
and the traffic simil
a
rity.
sim
is the mini
mum simil
a
rit
y
thresh
old,
and
nu
m
is the minimum
road
se
ction n
u
mb
er threshold.
x
kj
is th
e attri
bution of
roa
d
se
ction
j
to
Zone
k
, that
is, when
roa
d
se
ction j belo
ngs to Zo
ne
k
,
x
kj
is equal to 1, otherwi
se is 0.
3.3. Model Establishment
Define th
e ga
me
G
a
s
the
pro
c
e
ss
of ro
ad sectio
n pa
rt
ition acco
rdi
ng to the traff
i
c zone
core. The three eleme
n
ts
of the game p
r
ocess a
r
e:
(1) The
ga
m
e
pa
rticip
ant
set:
i
N
, wh
ere
N
={1,
2,
…,
n
}
is
the r
o
ad
s
e
c
t
io
ns
in th
e
netwo
rk;
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 9, September 20
14: 66
99 – 671
0
6702
(2) Strate
gy
for ea
ch pa
rticipa
n
t:
i
={
i1
,
i2
,…,
it
}
∑
, is the finite mixed strat
egy.
∑
is
the spa
c
e
of
all pa
rticip
ant
s’ mixed
st
rat
egie
s
.
ij
=(1,
2,…,
t
) is the
probability
of road
section
i
to
join
t
traffic
zone
s. The
va
lue of
ij
i
s
re
lated to th
e d
i
stan
ce
between th
e
road
se
ction
and
the
gravity cente
r
of the traffic zon
e
, wh
i
c
h can be expressed in Equ
a
tion (3
):
1
1
1
,1
1
t
ij
ij
ij
t
j
j
ij
d
d
(3)
Whe
r
e
d
ij
is the Eu
clide
a
n
distan
ce
bet
wee
n
road
section
i
an
d
the gravity center
of
traffic
z
o
ne
j
.
The bi
gge
r th
e di
stan
ce
be
tween
the
roa
d
sectio
n a
n
d
the traffic zo
ne i
s
, the
sm
aller th
e
prob
ability of the road se
ction join
s the traffic
zone
core. The road se
ction j
o
ins the ne
arest
traffic zo
ne core to form th
e traffic zo
ne
with the maximum pro
babil
i
ty.
(3) The expe
cted
p
r
ofit
of partici
pant se
t:
u
ij
={
u
i1
,
u
i2
,
u
it
} is
com
p
o
s
ed by the p
r
o
f
it when
the pa
rticip
a
n
ts ta
ke
strat
egie
s
from
the st
ra
tegy
space. Each road
se
ction t
a
ke
s the
traf
fic
cha
r
a
c
teri
stic simila
rity wit
h
t
he traffic zone
whi
c
h it
might join i
n
as the
gam
e
profit, such
as
Equation (4)
sho
w
s:
1
1
[(
,
)
]
[m
a
x
(
,
)]
[m
a
x
(
,
)
]
ij
i
j
ij
ij
i
j
r
i
j
ik
ij
jk
jt
k
us
i
m
o
c
di
f
d
if
o
c
dif
o
c
p
p
(4)
Whe
r
e
jk
p
indicates the average attribute
value of
each
road se
ction
in the traffic zone
cor
e
j
.
3.4. Game Partition
Algorithm Realization
In a ro
und
o
f
the game,
each gam
e
partici
pant
(p
layer, he
re
refers to ro
ad
se
ction
)
pursuits its
o
w
n m
a
ximum
profit
releva
n
t
to divi
ded
zone
s a
c
cordi
ng to th
e
kno
w
led
ge
relate
d to
all the zone
s,
namely the traffic simila
rit
y
and
proba
b
l
y joined zon
e
strategy co
mbination. T
h
e
strategi
es of
all partici
pant
s co
nsi
s
t of a strategy
co
mbination. T
he Na
sh eq
u
ilibrium of tra
f
fi
c
z
o
ne partition refers
to suc
h
a s
t
rategy c
o
mbin
ation: After iterations, any p
l
ayer obtain
s
the
maximum profit under the
existing strategy, that
is, the player e
a
rns mo
re in th
e cu
rre
nt zon
e
than
oth
e
r zo
nes, and
the profit
of
the
whole netwo
rk won’t red
u
ce becau
se of
pl
ayer’s
see
k
in
g
for the maxim
u
m profit.
Shapley valu
e is a mathe
m
atical meth
od to so
lve the probl
em of prof
it distrib
u
t
i
on of n
-
player with
coo
perativ
e strategy [11]. When
n
in
dividual
s are
engage
d in an activity
with
eco
nomi
c
p
r
ofit, each
in
dividual
can
obtain
ce
rtai
n profit. But whe
n
n
indiv
i
dual
s con
s
titute
allian
c
e, the
alliance gro
ss p
r
ofit is
bigge
r than
the sum of
the indep
end
ent profits of
n
individual
s. Each coop
e
r
ative form
with diffe
rent combi
n
a
t
ions of se
veral individ
uals
corre
s
p
ond
s to a ce
rtain p
r
ofit. When th
e activity
with econ
omi
c
profit is
non-co
nfrontation
a
l, the
increa
se of player num
b
e
r in
the co
operation ca
nnot cau
s
e t
he profit red
u
ction. So, the
coo
peration
of all the
n
individual
s brings the ma
ximum
profit. The bigge
st advantage
of
Shapley valu
e is that its principl
e and re
sults a
r
e fair
and ea
sily acce
ssi
ble by e
a
ch pl
ayer. T
h
e
Shapley valu
e method i
s
a schem
e of
the maximu
m profit dist
ribution, whi
c
h is defin
ed
as
follows
[12]:
Set
I
={1,2,…,
n
}, and if any sub
s
et of
I
,
whi
c
h re
pre
s
ents any co
m
b
ination of
n
players,
corre
s
p
ond
s to a real value
d
function
v
(
s
),
sat
i
sf
ie
s:
0
v
(5)
2
1
2
1
2
1
,
s
s
s
v
s
v
s
s
v
(6)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Bee Inspi
r
ed
Zonal Vehi
cle
Routing Algo
rithm
in Urba
n Traffic (Lei
Wu
)
6703
[
I
,
v
] rep
r
e
s
e
n
ts the
n-pla
y
er coop
erati
on
strategy,
and
v
indicates
the
c
h
arac
teris
t
ic
function of th
e cou
n
term
ea
sure, whe
r
e
v
(
s
) is the p
r
ofi
t
of subset
S
.
x
i
re
presents
the prof
it that
player
i
obtains
from
v
(
I
). In
coo
peratio
n
I
, the c
o
operative
strategy
di
stribution i
s
re
pre
s
ente
d
b
y
x
=(
x
1
,
x
2
,…
,
x
n
).
T
he coo
peration must sati
sfy
the
conditions as
follows:
n
i
i
v
x
n
i
i
,
,
2
,
1
,
1
(7)
n
i
i
v
x
i
,
,
2
,
1
,
(8)
i
(
v
) represen
ts the profit
distributio
n of p
l
ayer
i
in coo
perative g
a
m
e
[
I
,
v
]. The Shapley
value of the profit distrib
u
tion
of each pl
ayer in co
ope
ration [
I
,
v
] ca
n be de
scribe
d as follo
ws:
v
v
v
v
n
,
,
,
2
1
，
(9)
n
i
i
s
v
s
v
s
w
v
i
S
s
i
,
,
2
,
1
,
\
(10)
!
!
1
!
n
s
s
n
s
w
(11)
Whe
r
e
s
i
indi
cate
s all
the
sub
s
et
s
whi
c
h contain
s
pl
ayer
i
in
set
I
,
and
|
s
| rep
r
e
s
ent
s
the
factor numb
e
r
in sub
s
et
s
.
w
(|
s
|) is the
weig
hted fa
ctor, while
v
(
s
)
is the p
r
ofit of
sub
s
et
s
. [
v
(
s
)-
v
(
s
\
i
)]
rep
r
e
s
ents th
e in
crement
al
profit after pl
aye
r
i
joi
n
s the
su
bset
s
.
n
! indicates the
combi
nation
of all sub
s
et
s. The
Shapl
ey val
ue d
o
e
s
not de
al
with all th
ese combin
atio
ns,
however it
o
n
ly deal
s
wit
h
all th
e pl
ayers when
pla
y
er
i
do
es
n
’
t jo
in
s
u
bs
e
t
S
and
have
joi
ned
sub
s
et
S
, namely the (
s
-1)
!
*(
n
-
s
)!
int
e
r
e
st
ing
seq
u
e
n
ce
s.
The
ab
ove two expression
s com
b
ine
the weighte
d
factor [(
s
-1)
!
*(
n
-
s
)!]/
n
!, which di
strib
u
tes a fair m
a
rgin
al co
ntri
bution to ea
ch
intere
sting al
liance. Cal
c
u
l
ate the accumulative su
m of sub
s
et
S
where p
l
ayer
i
exist
s
repe
atedly. The final re
sul
t
represe
n
ts
a
ll possibl
e a
lliance assig
ned value
of play
i
which is
equal to the e
x
pected ma
rg
inal co
ntributi
on or in
creme
n
tal value.
The Shapl
ey value method
pays more a
ttention
to the efficien
cy of road sectio
n profit
and the p
r
ofit of road
se
ction pa
rtit
ion, rather tha
n
on
ly the dist
ribu
tion prin
ciple
of road
se
ctio
n
occup
a
n
c
y in traffic zo
ne
s. The algo
rith
m not onl
y a
v
oids the
situ
ation that roa
d
se
ction
size
deci
d
e
s
the
zon
e
regio
n
,
and
also
p
r
o
m
pts the
inte
rnal
relatio
n
so
as to imp
r
ove thei
r in
n
e
r
resou
r
ce utilization
ratio
and the e
n
tire net
work
reso
urce
utili
zation ratio by
see
k
ing
f
o
r
coo
peration
with adj
acent
zon
e
s
activel
y
. Thes
e
adv
antage
s fully
embody the
fair, bala
n
ce,
and
global o
p
tima
l characte
ri
stic of Shapley
value,
which
is good fo
r the implem
en
tation of zon
a
l
route gui
dan
ce system.
The Sh
apley
value-b
a
sed t
r
affic g
u
ida
n
ce
zone pa
rtition
alg
o
rithm
can
be de
scri
bed
a
s
follows
:
Step 1
: Set the directio
n
of traffic flow based on th
e origi
nal
S
o
f
guidan
ce
ro
ute, and
cho
o
se the ro
ad se
ction att
r
ibute
s
wh
ere
S
is the cent
er of the diffraction to com
pute the gam
e;
Step 2
: A
c
co
rding
to the
simila
rity thre
shol
d an
d no
de nu
mbe
r
thre
shol
d, ch
o
o
se th
e
traffic
z
o
ne core;
Step 3
: Acco
rding to the
maximum ex
pecte
d prof
it
prin
ciple, ma
ke the road
se
ction
s
join the
corre
s
po
ndin
g
traff
i
c
zon
e
core
to form t
r
affic zo
ne
s. Let t
he
zon
e
cont
enting
S
be
the
Zone
k
, a
nd the adja
c
e
n
t zone be Zo
ne
k
+1, and so o
n
;
Step 4
: In the first rou
nd
of game, accordin
g to the
average
attribute value a
nd the
distan
ce to th
e gravity coo
r
dinate of ea
ch traffi
c guid
a
n
ce
zon
e
, cal
c
ulate the ex
pecte
d profit o
f
each node to
every traffic guidan
ce zo
ne
u
ij
, and le
t
u
ma
x
=max
{
u
ij
}. The comp
utation data of
Zone
k
i
s
the
real time data
,
while the da
ta of Zone
k
+1 is the pre
d
i
c
ted data at the mome
nt
k
+1,
and so on.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 9, September 20
14: 66
99 – 671
0
6704
Step 5
:
Whe
n
the expe
ct
ed profit of
the nod
e to the
locate
d zone
u
0
<
u
ma
x
, choose th
e
maximum ex
pecte
d profit zon
e
to join
in, and
re-calcul
a
te the
averag
e attri
bute value
a
nd
gravity coo
r
di
nates of the n
e
w traffic g
u
idan
ce zone a
nd the Shapl
ey value of each n
ode.
Step 6
: Ent
e
r the n
e
xt roun
d of ga
me, and re-clu
ster the
n
ode a
c
cordin
g to the
expecte
d pro
f
it of each node.
When
the Shaple
y
value is maximum, n
a
mely the g
a
me
equilib
rium, the traffic guid
ance zo
ne
s a
r
e divided;
Step 7
:
Whe
n
the n
e
xt pe
riod
of re
al time data
acq
u
iring
come
s, if
S
is still in
Zone
k
,
repe
at step 4
to step 6, otherwi
se
rep
eat
step 2 to ste
p
6.
4. Route Ch
oice Model
4.1. Optimization Index
Analy
s
is
Dynami
c
Rou
t
e Guid
an
ce
System realizes th
e vehi
cl
e ro
uting
by u
s
ing
rolli
ng
cy
cle
way
[13]. The ma
thematical
m
odel of the
shorte
st path
probl
em u
s
u
a
lly
adopt
s the graph th
e
o
ry
kno
w
le
dge to
de
scribe
urb
an traffic ro
ad
network top
o
l
ogy. The
sp
e
c
ific m
odel
ca
n be
de
scrib
e
d
as
follows
:
E
S
i
E
j
i
S
j
j
i
k
j
i
I
Z
,
,
min
(
1
2
)
s
.t.
.
,
,
,
1
,
,
,
,
0
,
E
S
R
j
i
E
S
R
j
i
I
j
i
(13)
Whe
r
e
i
and
j
indicate th
e vertex of the di
recte
d
grap
h, nam
el
y the interse
c
tion
s of
urba
n road n
e
twork, an
d (
i
,
j
) indicate the ed
ge of th
e dire
ct
ed
graph, that is, t
he ro
ad
se
ction
betwe
en inte
rse
c
tion
i
an
d intersectio
n
j
in the real road network.
Z
i
,
j
(
k
) rep
r
ese
n
ts the road
resi
st
an
ce
at
mome
nt
k
,
whi
c
h i
s
sum
of the t
r
avel
time in
ro
ad
se
ction
(
i
,
j
) and
interse
c
tion
delay (the
av
erag
e vehi
cle
delay in t
he
adja
c
ent e
n
trance lan
e
s
of interse
c
tion
i
and inte
rse
c
tion
j
) at moment
k
.
S
and
E
indicate th
e origin
al an
d destinatio
n
resp
ectively
, and
R
(
S
,
E
)
rep
r
e
s
ent
s the acycli
c path
set from
S
to
E
.
The optim
al route from
S
to
E
is t
h
e
solut
i
o
n
whi
c
h
sat
i
sf
ie
s t
he E
q
.
(
1
2
) a
nd it
s
con
s
trai
nts E
quation (13
)
.
4.2. Model Establishment
The
whole
ne
twork i
s
divid
ed into diffe
re
nt tr
affic zone
s, and
every t
r
affic
zon
e
co
ntains
two ki
nd
s of
node
s: inn
e
r
node
s a
nd b
o
rde
r
n
ode
s.
The
inn
e
r no
des maintain the
optimal route
table to th
e o
t
her n
ode
s i
n
the
same
zo
ne, while th
e
borde
r n
ode
s mai
n
tain th
e optimal
rou
t
e
table to the other bo
rd
er no
des in a
d
ja
ce
nt zone
s.
In se
ction
1,
bee
s a
r
e
disti
ngui
she
d
into
thre
e
ki
nd
s: the em
ployed
bee
s, the o
n
l
ookers,
and the scou
ts. The empl
oyed bee
s collect the info
rmatio
n, wh
ile the onloo
kers wait in the
beehive to
o
b
se
rve the fe
llow’
s da
nce, and th
e sc
o
u
ts
sea
r
ch fo
r food
so
urce
ran
domly. T
h
e
numbe
r
of th
e em
ployed
b
ees is eq
ual
t
o
that of
the
onloo
ke
rs,
no
ted a
s
BN
, a
nd the
same
as
that of the fo
od
sou
r
ce
(
SN
). T
h
e
r
efore
,
the solution
set
co
mpo
s
e
s
SN
D-di
me
nsio
nal
ve
cto
r
s,
and the ist solution ca
n b
e
expre
s
sed
as
x
i
=(
x
i1
,
x
i2
, …,
x
iD
), whe
r
e
i
=1, 2, …,
SN
. The pollen
quantity of food so
urce correspon
ds to the quality
of the sol
u
tion, n
a
mely the fitness value.
Initially, generate the initi
a
l solutio
n
set
P
(
G
=0
) randomly, an
d ev
aluate its fitness
value. After the initializatio
n, the emplo
y
ed bee
s, the onloo
ke
rs, and the
scou
ts are
circul
a
r
ly
sea
r
ching fo
r the optimal solutio
n
, here standi
ng for the optim
al route. The
employed b
e
e
s
amend
the p
o
sition
relyin
g
on the
lo
cal i
n
formatio
n
in
their me
mory,
and te
st the
fitness value
of
new po
sition.
If the fitness value is high
er t
han the previous on
e, the
employe
d
bee
s reme
m
ber
the new solut
i
on instea
d of the old one, otherwise
still
hold the old one. After a round of se
arch
pro
c
e
ss,
bee
s sha
r
e the fi
tness value
a
nd po
siti
on i
n
formation
wit
h
the o
n
loo
k
ers in the
da
nce
regio
n
. The o
n
loo
k
ers eval
uate all the fitness
value i
n
formatio
n from the empl
oyed bee
s, a
n
d
select the food source
according to the
probability of
the fit
ness value. Like t
he employed
bees,
the onl
oo
ke
rs also
amen
d t
he p
o
sitio
n
re
lying on
the
l
o
cal
info
rmati
on in
thei
r m
e
mory, a
nd
test
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Bee Inspi
r
ed
Zonal Vehi
cle
Routing Algo
rithm
in Urba
n Traffic (Lei
Wu
)
6705
the fitness va
lue of
ne
w p
o
s
ition. If the fi
tness
valu
e i
s
hi
ghe
r tha
n
the p
r
eviou
s
one, th
ey drop
the old
one.
An artificial
o
n
loo
k
er select the
food
so
urce a
c
cordi
ng to the
pro
bability of fo
od
source qualit
y as follows:
SN
n
n
i
i
fit
fit
p
1
(14)
Whe
r
e,
fit
i
indicate
s the fitness val
ue of food source p
o
sition.
The alg
o
rith
m use
s
the f
o
llowin
g
expression
to
cre
a
te a com
pet
ition positio
n
of an old
positio
n.
kj
ij
ij
ij
x
x
rand
x
v
)
1
,
1
(
(15)
Whe
r
e the in
dex
k
is ran
d
o
mly sele
cte
d
, and
k
∈
{1, 2,
…,
BN
},
j
∈
{1, 2, …,
D
}. Although
k
is ra
ndo
mly decid
ed, it must be differe
nt to
i
. rand(-1,1) is the ran
dom num
ber i
n
the regio
n
[-1,
1], which d
e
c
ide
s
the ad
jace
nt food sou
r
ce creati
on of
x
i
. Thi
s
co
rrectio
n
rep
r
e
s
ent
s the
comp
ari
s
o
n
o
f
adjace
n
t food sou
r
ce in b
ee visual, na
mely the neig
hborhoo
d se
a
r
ch p
r
o
c
e
s
s.
The food sou
r
ce
s ab
and
o
ned by the b
ees a
r
e repla
c
ed by ne
w food source
which the
scouts find. I
f
a position
can
not be a
m
ende
d by
a pre
s
et cy
cl
e numb
e
r
ca
lled “limit”, the
aban
done
d food so
urce
will be repl
aced by the new
food so
urce found by the sco
uts with
the
assumptio
n
t
hat this foo
d
sou
r
ce i
s
a
band
oned.
T
he op
eratio
n
is reali
z
ed
by the following
equatio
n:
j
j
j
j
rand
x
min
max
1
,
0
min
(16)
This up
date
equatio
n rep
r
ese
n
ts the gl
obal se
arch
strategy. The
maintenan
ce of th
e
scouts ma
ke
s the algo
rith
m a better global se
arch
ability so as to avoid the bee swarm falling
into local mini
ma.
After the establishment of
every comp
etitor’s po
siti
on
v
i
, evaluat
e them and comp
are
them with
x
i
. If the new food so
urce is
better, aban
d
on t
he old, otherwise ke
ep
the old, that
is,
sele
ct the foo
d
sou
r
ce bet
wee
n
the old
and the curre
n
t in greedy selectio
n mechani
sm.
4.3. Zonal Guidance Pro
cedure
Whe
n
travele
r
s h
a
ve a ro
ute guida
nce
dem
and,
ch
oose the ori
g
inal and d
e
st
ination,
divide the tra
ffic guida
nce
zon
e
ba
se
d
on Shapl
ey
value, an
d se
arch the o
p
timal ro
ute in
each
traffic zone
b
y
using
bee i
n
spi
r
ed
algo
ri
thm. The rout
e guid
a
n
c
e o
r
iginal l
o
cate
d Zon
e
k
ado
pts
the real-tim
e
data at the moment
k
to cal
c
ulate the optimal route in the zon
e
. Define
the
adja
c
ent zo
n
e
of
S
located Zone
k
a
s
Zone
k
+1, an
d cal
c
ulate th
e optimal rout
e in Zone
k
+1 by
usin
g predi
cted data at th
e mome
nt
k
+1, and so on
. All the marginal road
se
ction
s
of traffic
zon
e
s compo
s
e th
e inte
rval net
work to
provid
e the
con
n
e
c
tion
of se
gmente
d
optimal
route
in
traffic zo
ne
s. The implem
e
n
tation of the algorith
m
is a
s
follows:
Step 1
: Set the traffic di
re
ction b
a
sed o
n
route
guid
a
n
ce
origi
nal
S
as be
nchm
ark, a
nd
sele
ct the traf
fic attribute of
diffraction di
re
ction of the
origin
al to co
mpute the ga
me;
Step 2
: Adop
t Shapley value-b
a
sed ga
me theory to divide the traffic zon
e
;
Step 3
: Calculate the
opti
m
al route i
n
each tr
affic
zone
by u
s
ing
pa
rallel
co
m
puting.
Here only ca
lculate the
S
located Z
o
n
e
i
and the
adja
c
ent Zo
n
e
k
+1, Zone
k
+2, until the
E
locate
d Zone
k
+
i
;
Step 4
:
Cal
c
ulate the
opti
m
al route of t
he inte
rv
al ne
twork to
co
nn
ect the
optim
al ro
ute
in each traffic zone
so a
s
to form the op
timal route fro
m
S
to
E
;
Step 5
: If
S
enters
a Zo
ne
k
+1, rep
eat S
t
ep 2 to Step
4 to re
-divide
the traffic zo
ne an
d
update the o
p
t
imal route.
5. Simulation and Analy
s
is
Take
part of
an urb
an ro
ad network a
s
an exam
pl
e, which cov
e
rs
abo
ut 15
squa
re
kilomete
rs, a
nd
contain
s
184
roa
d
sections, in
cludi
ng 10
on
e-way se
ction
s
and 1
55 t
w
o-way
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 9, September 20
14: 66
99 – 671
0
6706
se
ction
s
. Tre
a
t the road
section
s
a
s
n
ode
s, so
that
the actual
road
net
wo
rk
and the a
b
stract
road
net
work are
sho
w
n i
n
Figu
re
1 a
nd Fig
u
re
2
respe
c
tively. Establish the
roa
d
n
e
two
r
k
topology in
VISSIM, and acquire the
traffic p
a
ra
meters of al
l the road
section
s
th
rou
g
h
simulatio
n
. T
he real
-time d
a
ta is colle
cte
d
ever
y
5min
utes, a
nd th
e
predi
cted
dat
a is obtai
ned
by
usin
g RBF ne
ural net
wo
rk [
14].
Figure 1. Actual Ro
ad Network an
d its Topolo
g
y Architecture
Divide the wh
ole netwo
rk into traffic zon
e
s by usin
g Shapley value
-
based gam
e theory.
After limited i
t
eration
s
, the
game
gets
converg
e
n
c
e
and e
quilib
riu
m
, thus the
traffic
zon
e
s
are
determi
ned a
s
sh
own in Figure 3.
Figure 2. Abstraction of
Ro
ad Section
s
o
f
Actual Ro
ad
Network
Figure 3. Traf
fic Zone Pa
rtition Based o
n
the
Shapley Valu
e
Cho
o
se p
a
rt
re
sult
s of
zonal
and
no
n-zonal
opti
m
al route
s
from a
ma
ss
of optimal
route
s
se
arch
re
sult
s
a
s
sh
own
in Tabl
e 1,
one
of
whi
c
h f
r
om
ori
g
i
nal 1
392
to d
e
stinatio
n 1
2
25
is sh
own in Figure 4
(in bol
d).
Figure 4 sh
o
w
s that the zonal
optimal
route an
d no
n-zonal o
p
timal route fro
m
Node
1392 to
Nod
e
.
Table 1 li
sts that the zo
na
l optimal
ro
utes a
r
e
con
s
i
s
tent with the
non-zo
nal o
n
e
s.
Therefore, th
e algo
rithm
can p
r
ovide
gl
obal o
p
ti
mal
route
after p
a
rtition of the
whol
e net
wo
rk
into different traffic zon
e
s,
and cannot
make the
o
p
timal route
se
arch into loca
l optimum du
e to
decentrali
ze t
he ro
ute
sea
r
ch
regio
n
into
each tra
ffic
zone. On th
e
basi
s
of gl
ob
al optimal
rou
t
e
guarantee, th
e optimal rou
t
e sea
r
ch pro
c
e
ss
afte
r zo
ne pa
rtition a
dopts
parallel
comp
uting f
o
r
optimal route
cal
c
ulatio
n i
n
ea
ch traffic
zon
e
sy
n
c
h
r
o
nou
sly. Furth
e
rmo
r
e, the
a
l
gorithm
doe
sn’t
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Bee Inspi
r
ed
Zonal Vehi
cle
Routing Algo
rithm
in Urba
n Traffic (Lei
Wu
)
6707
sea
r
ch
relati
vely far
zon
e
s f
r
om th
e
zo
ne
s that
origin
al a
nd
destin
a
tion l
o
cate
d
so
a
s
to
decrea
s
e
th
e ergo
dic nod
e quantity
and redu
ce
the co
mputing
com
p
lexity. Table 1 lists that th
e
cal
c
ulatio
n time of zon
a
l vehicl
e routin
g
algorithm
i
s
l
e
ss than 1
se
con
d
, whi
c
h i
s
five time less
than the
non
-zon
al alg
o
rith
m. Con
s
e
que
ntly, the
zon
a
l vehicl
e rou
t
ing algo
rithm
increa
se
s th
e
routing effici
e
n
cy, and short
ens the calculation time.
Figure 4. The
Optimal Rout
e of Zonal Ve
hicle
Routin
g Algorithm
Figure 5. The
Optimal Rout
e of Hiera
r
chi
c
al
Algorithm
Dividing the
entire n
e
two
r
k into differe
nt traffic zon
e
s
can
not o
n
ly redu
ce th
e erg
odi
c
node
qua
ntity, comp
uting
complexity, and cal
c
ul
ation
time so
as i
n
cre
a
se the
search
efficien
cy
and
real
-time
perfo
rma
n
ce
, but it al
so
can
prov
ide
a glo
bal o
p
timal route.
Consequ
ently, the
traffic
zon
e
partition
can
en
su
re th
e
premise
of
accuracy
an
d imp
r
ove
th
e efficie
n
cy
and
perfo
rman
ce
of DRGS.
Furthe
rmo
r
e,
the traffi
c zone pa
rtition
can al
so
o
p
timize the
data
colle
ction an
d pro
c
e
ssi
ng
in vehicle-i
n
frastructu
re
coope
rative re
al-time a
c
qui
sition so as
to
provide
conv
enient an
d effective data fo
r the DRGS to enha
nce its performan
ce
.
Table 1. Re
sults of Optim
a
l Route
s
Co
mpared with
Non
-
zonal Al
gorithm
Original Destination
Zonal
vehicle
routing
Non-zonal vehicle routing
S
E
Node No.
Cal. time
Node No.
Cal. time
1392
1225
73
832ms
202
4827ms
Route
1392
→
136
1
→
13
59
→
1360
→
1355
→
1354
→
1
318
→
1258
→
123
2
→
12
25
1420
1212
104 916ms 238
5383ms
Route
1420
→
141
5
→
13
60
→
1355
→
1354
→
1318
→
1
258
→
1232
→
122
5
→
12
12
1093
1353
115 985ms 259
5195ms
Route
1093
→
109
7
→
11
42
→
1140
→
1156
→
1155
→
1
182
→
1181
→
120
1
→
12
17
→
1223
→
1233
→
1234
→
1
240
→
1258
→
1232
→
1
253
→
1289
→
131
6
→
13
22
→
1356
→
1350
→
1353
1105
1314
101 875ms 239
4967ms
Route
1105
→
111
4
→
11
69
→
1212
→
1225
→
1232
→
1
258
→
1276
→
131
5
→
13
14
1304
1387
26
812ms
136
4662ms
Route
1304
→
134
6
→
13
59
→
1360
→
1355
→
1354
→
1
398
→
1397
→
136
9
→
13
56
→
1350
→
1367
→
1386
→
1
387
989 1407
43
907ms
236
5217ms
Route
989
→
1017
→
102
6
→
1041
→
1075
→
1108
→
1
127
→
1131
→
114
8
→
11
68
→
1213
→
1232
→
1253
→
1
289
→
1316
→
1322
→
1
356
→
1369
→
139
7
→
14
07
To co
mpa
r
e
with hie
r
archi
c
al vehi
cle
ro
uting
algo
rith
m, the urba
n
netwo
rk i
s
div
i
ded into
two laye
rs. T
he trun
k
road
s
com
p
o
s
e th
e ba
ckbo
ne l
a
yer
as sho
w
n in
Figu
re
1
(bold
line
s
), a
n
d
the
other ro
a
d
s surro
und
e
d
the
trun
k ro
ads co
nstitu
t
e
the bran
ch
layers. In hi
erarchical vehi
cle
routing
algo
rit
h
m, se
arch th
e optimal
rout
e from
the
ori
g
inal a
nd the
destin
a
tion to
the ba
ckbon
e
layer respe
c
tively, and the optimal
ro
ute on the
b
a
ckbo
ne to
con
n
e
c
t the
origin
al an
d
the
destin
a
tion to
gene
rate th
e
optimal
rout
e from
orig
i
n
al to de
stinati
on. The
opti
m
al ro
ute results
of the hierarchical an
d zo
n
a
l vehicle rou
t
ing al
gorithm
s are
sho
w
n
in Table 2, a
nd the optim
al
route fro
m
13
92 to 1225 of
hiera
r
chi
c
al a
l
gorithm i
s
sh
own in Fig
u
re
5 (in bold
)
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 9, September 20
14: 66
99 – 671
0
6708
Table 2. Re
sults of Optim
a
l Route
s
Co
mpared
with Hierarchi
c
al Algorithm
O
r
iginal
Desti
natio
n
Zonal vehicle routing
Hier
archical vehicle routing
S E
Node
No.
Cal. time
Trav
.
Node No.
Cal. time
Trav
.
1392
1225
73
832ms
18.2min
56
437ms
25.7min
RouteZ
1392
→
136
1
→
13
59
→
1360
→
1355
→
1354
→
1
318
→
1258
→
123
2
→
12
25
RouteH
1392
→
136
1
→
14
18
→
1419
→
1388
→
1345
→
1
319
→
1311
→
130
4
→
13
02
→
1299
→
1276
→
1258
→
1
232
→
1225(differ
ent fro
m
RouteZ
)
1420
1
2
1
2
104 916ms
19.4min
73 519ms
32.2min
RouteZ
1420
→
141
5
→
13
60
→
1355
→
1354
→
1318
→
1
258
→
1232
→
122
5
→
12
12
RouteH
1420
→
141
5
→
14
10
→
1411
→
1398
→
1354
→
1
318
→
1258
→
123
2
→
12
25
→
1212
（
differ
ent from
RouteZ
）
1105
1
3
1
4
101 875ms
13.7min
85 492ms
13.7min
RouteZ
1105
→
111
4
→
11
69
→
1212
→
1225
→
1232
→
1
258
→
1276
→
131
5
→
13
14
RouteH
The same
w
i
th
RouteZ
1304
1
3
8
7
26 812ms
22.5min
62 467ms
40.8min
RouteZ
1304
→
134
6
→
13
59
→
1360
→
1355
→
1354
→
1
398
→
1397
→
136
9
→
13
56
→
1350
→
1367
→
1386
→
1
387
RouteH
1304
→
130
2
→
12
99
→
1276
→
1258
→
1232
→
1
225
→
1212
→
128
6
→
13
08
→
1324
→
1334
→
1353
→
1
370
→
1387 (differ
ent fr
om RouteZ
)
1407
9
8
9
43 907ms
14.6min
76 485ms
35.9min
RouteZ
1407
→
139
7
→
13
69
→
1356
→
1322
→
1316
→
1
289
→
1253
→
123
2
→
12
13
→
1168
→
1148
→
1131
→
1
127
→
1108
→
107
5
→
10
41
→
1026
→
1017
→
989
RouteH
1407
→
140
9
→
14
11
→
1398
→
1354
→
1318
→
1
258
→
1240
→
123
4
→
12
19
→
1215
→
1188
→
1178
→
1
173
→
1151
→
113
6
→
11
16
→
1095
→
1089
→
1072
→
1
063
→
1048
→
103
1
→
10
17
→
989(
differen
t
from Rout
eZ)
Due to the ch
ara
c
teri
stic of
hierarchi
c
al
v
ehicle routin
g algorithm, it provide
s
an optimal
route
with le
ss
erg
odi
c n
ode qu
antity and
sho
r
ter
cal
c
ulatio
n time than
zon
a
l vehicle
ro
uting
algorith
m
. Ho
wever, m
o
st
optimal route
s
of hi
era
r
chi
c
al al
go
rithm
have lon
ger travel time th
an
that of the
zonal al
go
rith
m. The
rea
s
on is that th
e aim
of hie
r
archical
sea
r
ch i
s
to
sh
rin
k
the
sea
r
ch
regi
o
n
into
the t
r
u
n
k l
a
yer so
as to
o
p
timize the
calcula
t
ion time. Alt
houg
h the
traffic
cap
a
city of b
a
ckbo
ne laye
r is hig
her th
a
n
that of
the bran
ch laye
r, the travel time, occupa
ncy
,
or
saturation
of backb
one l
a
yer i
s
bette
r th
an that of
the
bra
n
ch layer.
Therefore, the optimal
rout
e
of hierarchi
c
al alg
o
rithm
is e
a
sy to
lo
st in
l
o
cal o
p
timum. On
the othe
r h
a
nd, du
e to t
h
e
backb
one l
a
yer o
n
ly co
nsi
s
ts
of the tru
n
k
roa
d
s,
if t
here
are ple
n
ty of routing
deman
ds at the
same
time, t
he b
a
ckb
one
layer will
be
come
con
gested, whi
c
h
ca
nnot
solve th
e traffic jam,
but
bring
furthe
r
new conge
sti
on in
co
ntra
ry. Therefo
r
e,
com
p
a
r
ed
with hierarchi
c
al algo
rithm,
the
zon
a
l algo
rith
m can p
r
ovid
e a global o
p
timal rout
e
with approp
riate
calculation ti
me sa
crifi
c
e.
Select cou
p
l
e
s of
ori
g
inal
s
a
nd de
stin
ations
,
and
verify the
sea
r
ch
efficie
n
cy
of be
e
inspi
r
ed
algo
rithm comp
ared with
ant
colo
ny al
go
rithm an
d D*
algorith
m
. Th
e optimal
ro
ute
results given
by the above algorith
m
s a
r
e sho
w
n in T
able 3 an
d Ta
ble 4.
Table 3. Re
sults of Optim
a
l Route
s
Co
mpared with
Ant Colony & D* Algorith
m
Org.
Dest.
Zonal vehicle routing
Ant colo
n
y
vehicle routing
D* vehicle routing
S E
Node
No.
Cal.
time
Trav
.
Node
No.
Cal.
time
Trav
.
Node
No.
Cal.
time
Trav
.
1392
1225
73
832ms
18.2min
85
1263ms
18.2min
137
3792ms
18.2min
1420
1212
104
916ms
19.4min
127 1419ms
27.1min
196 3942ms
19.4min
1105
1314
101
875ms
13.7min
132 1463ms
13.7min
217 4049ms
13.7min
1304
1387
26
812ms
22.5min
44 1184ms
32.5min
82 3563ms
22.5min
1407
989
43
907ms
14.6min
69
1231ms
14.6min
115
3631ms
14.6min
Evaluation Warning : The document was created with Spire.PDF for Python.