TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.4, April 201
4, pp. 2645 ~ 2
6
5
1
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i4.4306
2645
Re
cei
v
ed Se
ptem
ber 2, 2013; Re
vi
sed
Octob
e
r 15, 2
013; Accepte
d
No
vem
ber
5, 2013
Traffic Network Optimal Scheduling Paths Based on
Time Intervals Division
Hao Wei
1
*, Zhang Xing
2
Hen
an Un
ivers
i
t
y
of Urb
an Co
nstr
uction, Pin
gdi
ngsh
an 4
6
7
036, Ch
in
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: hao_
w
e
i
_
2
0
1
3
@1
63.com
A
b
st
r
a
ct
In order to ma
ke the netw
o
rk mod
e
l w
a
s more fitting
the a
c
tual con
d
itio
n of city traffic, this pa
pe
r
prese
n
ts a dy
n
a
mic trans
port
a
tion
netw
o
rk
mo
de
l bas
ed
o
n
the traffic ti
me div
i
sio
n
, an
d
desi
gns i
m
prov
ed
Dijkstra a
l
gor
ithm to so
lve th
e city traffic paths pl
a
n
n
i
ng
prob
le
m. Dijkst
ra alg
o
rith
m is
a typical si
ngl
e
-
source
short
e
s
t
path al
gorith
m
is used
to c
a
lculat
e a
n
o
d
e
t
o
a
ll
other
n
o
d
e
s i
n
th
e sh
ortest path.
T
he
ma
i
n
character
i
stic i
s
the starti
ng
poi
nt
as th
e c
e
nter o
u
tw
ard e
x
pans
ion
lay
e
r
s
until
the
exte
nsio
n to th
e
e
nd.
T
he Dijkstra a
l
gorith
m
is a ve
ry represe
n
tati
ve shorte
st pat
h alg
o
rith
m. T
h
is pap
er intro
d
uces new
patte
rns
to effectively c
o
mbi
ne the
mode
l an
d al
gor
ithm. T
he
s
i
mulati
on ex
peri
m
e
n
ts po
int to
ten time inter
v
al
s
w
h
ich il
lustrate
the i
m
prove
d
Dijkstra
al
gori
t
hm c
an
av
oi
d
drivi
ng to t
h
e
block
ed r
o
a
d
s
in
different ti
me
interva
l
s. T
he alg
o
rith
m has s
o
me feasi
b
il
ity
in path p
l
a
nni
n
g
and co
mputa
t
ion efficie
n
cy.
Ke
y
w
ords
: pat
h pla
nni
ng, roa
d
netw
o
rk mo
d
e
l, time
divis
i
o
n
, impr
ove
d
Dij
kstra algor
ith
m
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 yea
r
s, with th
e ra
pid growth of
car
ownershi
p
, traffic pro
b
l
e
ms h
a
ve be
come
a
very serio
u
s
so
cial proble
m
which ca
u
s
e
s
gre
a
t inconvenie
n
ce f
o
r peo
ple'
s d
a
ily life and work
and
also b
r
in
g envi
r
onm
en
tal pollutio
n
,
wa
ste of
ene
rgy, and t
r
affic jam
phe
nom
enon
[1]. As
an
importa
nt pa
rt of the natio
nal e
c
on
omi
c
and
so
cial
a
c
tivities, tran
sportation
ha
s be
come
on
e
of
the foundatio
ns of the su
rv
ival
and devel
opment of the
modern so
ci
et
y. With the
rapid e
c
o
nom
ic
developm
ent
in China'
s m
a
jor
cities in
re
cent ye
ars, e
x
pandin
g
po
p
u
lation,
car o
w
ne
rship i
n
t
h
e
rapid
growth
and traffic co
nge
stion p
r
ob
lems
ca
use
d
by a se
rie
s
of
traffic soci
al
probl
em
s . Due
to the lack of infrast
r
u
c
ture
con
s
tru
c
tion
over
the years, a lot of pl
anning ha
s go
ne wrong in t
he
impleme
n
tation pro
c
e
s
s, whi
c
h are redu
cing t
he
efficien
cy of urba
n tran
sp
ort, cau
s
ed
some
so
cial probl
ems. Thi
s
greatly affects t
he so
ci
al and e
c
o
nomic d
e
vel
opment an
d
the
improvem
ent
of pe
ople'
s living sta
nda
rd. The
path
planni
ng
poin
t
ing to the
u
r
ban t
r
affic
ca
n
solve the pro
b
lems of road
cong
estio
n
, trav
el inconve
n
ien
c
e in a certain extent [2].
In ord
e
r to i
m
prove
the
efficien
cy of
city
traffic p
a
t
h plan
ning,
dome
s
tic
an
d forei
gn
schola
r
s hav
e carried
on
re
sea
r
che
s
and p
r
o
p
o
s
e
d
lots
of pat
h plan
ning
a
l
gorithm
s
whi
c
h
contri
buted t
o
the traffic
system
con
s
t
r
uctio
n
is
theories
and prac
tice [3, 4]. At pres
ent, the
resea
r
ch di
rection
s
m
a
in
ly focu
s on
the a
s
pe
ct
s of
roa
d
n
e
twork
mod
e
l
s a
nd pl
an
ning
algorith
m
s which
have
a
c
hieve
d
ce
rtain
re
sult
s.
Among th
em
, Zografos p
r
opo
se
d
a traffic
deci
s
io
n-m
a
ki
ng supp
ort sy
stem which is for vehi
cl
e al
locatio
n
, sche
duling a
nd
ro
uting gui
dan
ce
[5]; Lu Fen
g
prop
osed th
e
optimal
path
algorith
m
ba
sed
o
n
spatial hiera
r
chi
c
al reasonin
g
whi
c
h
first cla
s
sified
the traffic ne
twork in the f
o
rm
s
of grad
es to differen
t
levels, and
then the leve
ls
were used fo
r the optimal
path plannin
g
algorith
m
[6-8]; referen
c
e prop
osed
a layered p
a
t
h
planni
ng al
go
rithm which can in
cre
a
se t
he sea
r
chi
n
g
efficien
cy by con
s
tr
aining
the searchi
n
g
area
s. The
ro
ad hie
r
archi
c
al app
roa
c
h i
s
u
s
ed to
im
prove the o
p
timal path pla
nning; refere
nce
pre
s
ente
d
a dynamic
sho
r
test path alg
o
rithm and
p
r
ovided the g
eneral sol
u
tio
n
s of the optimal
paths in
an a
c
ycli
c graph;
referen
c
e an
d discu
s
s
ed t
he sh
orte
st p
a
th pro
b
lem f
o
r arc
weight
s
cha
nge
s. Th
e previou
s
re
sea
r
che
s
m
a
i
n
ly are
for
p
a
th pla
nning
probl
em
s mo
st of
whi
c
h a
r
e
based on
sho
r
test path al
g
o
rithm. The
condition
s
a
r
e
too re
strictive
and t
he calculation meth
o
d
s
are to
o compl
i
cated [9]. Althoug
h the m
e
thods
ca
n
the
o
retically a
c
hi
eve the a
c
curate cal
c
ul
atio
n
results, it’s ha
rd to colle
ct the data an
d d
i
fficu
lt to fulfill in the actual
appli
c
ation [1
0, 11].
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2645 – 2
651
2646
Aiming at the above sh
ortco
m
ing
s
, this pa
per p
r
opo
se
s a dynamic o
p
tim
a
l path
planni
ng alg
o
r
ithm ba
sed
on traffic tim
e
division
co
mbining th
e curre
n
t urb
a
n
traffic dyna
mic
cha
ngin
g
feat
ure
s
. The
pa
per
build
s the
roa
d
net
work mo
del o
n
b
a
si
s of the
dynamic changi
ng
rule
s of the road traffic at
different time
. The
data collectio
n method
s in the model a
r
e si
mple
and the pat
hs pla
nning
algorithm h
a
s hig
h
co
mputation ef
ficien
cy. The model ca
n
well
coo
perate wit
h
the algorith
m
[12-14].
2.
The D
y
namic Road
Ne
t
w
ork Model
In the norm
a
l road n
e
two
r
k mo
del, th
ere a
r
e lot
s
of informatio
n, such a
s
delay at
cro
s
sroad, a
nd delay du
e
to traffic con
t
rol. It’s co
m
p
lex to colle
ct the time informatio
n and
it’s
hard to
fulfill. Therefore, th
e model
s
sho
u
ld be
simp
lifi
ed a
c
cordi
ng
to the sp
ecifi
c
feature
s
of th
e
urba
n traffic
whe
n
build th
e model
s.
2.1. Urban Tr
affic
D
y
namic Chan
ging Features
In the real traffic, there are blocked
conditi
ons in the
roads. The traffic conditions will be
different in
th
e same
roa
d
at differe
nt time inte
rvals.
For exampl
e
,
the
interval
of 8:00-9:00 i
s
norm
a
lly the
pea
k time to
go to
wo
rk,
so the bl
ock
e
d
situation
is seriou
s.
Ho
we
ver, the inte
rval
of 5:00-7:00
will be unblocked.
A
c
cordi
ng to the
above urban traf
f
i
c
changing f
eatures, it’
s
not
suitabl
e to
use the
unitary
time wei
ght t
p
ij to re
p
r
e
s
e
n
ts the
time f
i
nish
drivin
g t
he di
re
cted
a
r
c
<vi,vj>. The
r
efore, th
e d
r
i
v
ing time
wei
ghts
sh
ould
be
re
configu
r
ed a
c
co
rding
to the
dyna
mic
cha
ngin
g
rule
s of the traffic.
Bretti propo
sed to build m
odel
s that we
re clo
s
e to th
e urba
n actu
al traffic con
d
itions in
the research
es i
n
whi
c
h
traffic
dynami
c
info
rmat
io
n
nee
d to
be
fuse
d in
the
model. T
h
e
r
e
f
ore,
the area
s wit
h
varied traffic co
ndition
s should b
e
consi
dered. Only t
he static roa
d
network
model an
d shorte
st time can’t sim
p
ly be used to
pl
an path
s
be
cause it will make the
cho
s
en
paths
are
not
the sh
orte
st paths i
n
the
actual
situati
ons.
Due to t
he con
c
ern, whe
n
build t
he
dynamic
roa
d
netwo
rk m
o
d
e
l, not only the urb
an tr
affi
c varie
d
co
nd
itions shoul
d
be co
nsi
d
e
r
e
d
,
but also the traffic con
d
ition
s
at different ti
me intervals
s
h
ould be taken into acc
ount.
2.2. The D
y
n
a
mic Road
Net
w
o
r
k Mode
l
Dynami
c
rout
e guid
a
n
c
e a
nd traffic
co
n
t
ro
l
is ba
sed
on Urb
an Road Network
Traffic
Analysis in int
e
lligent tran
sportation
syst
ems.
Urb
an
Road
Network Traffic Analysi
s
is also
impo
rtant to travele
r
inform
ation
servi
c
e
system.
City road
net
work traffic state
analysi
s
met
hod i
s
the
b
a
si
s of
imp
o
rtant theoretical
probl
em
s of intelligent tra
n
sp
ortation
systems an
d traffic mana
g
e
ment evalu
a
tion of traffic
con
g
e
s
tion, a
nd
solve traffic
con
g
e
s
tion
, this meth
od
ca
n p
r
ovide
a referen
c
e
for road
traffic
planni
ng.
Curre
n
tly, re
sea
r
che
r
s
at home
and
abro
ad h
a
ve
done
so
me
re
sea
r
ch on
city and
high
way traffi
c
state. O
n
traffic state
of t
he u
r
ba
n
roa
d
net
wo
rk re
search, th
e ma
in d
r
aw relev
ant
con
c
lu
sio
n
s g
e
t from the te
sting d
a
ta. Fo
r exampl
e: Th
e appli
c
ation
of pattern
re
cognition the
o
ry
and m
e
thod
s, research
o
n
urban t
r
an
spo
r
t net
wo
rk an
d the
m
o
torway net
work mod
e
, draw
traffic state can be re
du
ce
d to repeate
d
,
a limited num
ber of the result
s of the different types of
pattern
s; Usi
ng pattern re
cog
n
ition met
hod
s feat
ure
vectors extracted inte
rse
c
tion traffic fl
ow
runni
ng
con
d
i
tion and
situ
ation a
s
sessment mod
e
l to esta
blish traffic thro
ugh
the interse
c
ti
on
data si
milarit
y
; Adopting a
global
app
ro
ach to
dat
a
manag
eme
n
t analysi
s
of
space-time t
r
a
ffic
data, to dra
w
traffic stat
e rep
r
esentat
ion. In
freeway traffic state res
earch, mainly
use
s
th
e
extended Kal
m
an filter. F
o
r exam
pl
e: the extend
ed
Kalman filter app
roa
c
h to
high
way traf
fic
den
sity pre
d
i
c
tion. Extend
ed Kalma
n
fi
lter meth
o
d
establi
s
h
e
s real-time high
way
traffic
st
ate
es
timator.
The city
traffic
webbe
d analysi
s
rela
ted
to
the
macro, Me
di
um an
d mi
cro traffic
para
m
eters. Macro
s
copi
c traffic
p
a
ra
m
e
ters
de
sc
ri
b
e
s th
e evol
ution of th
e
ch
ara
c
teri
stics
and
the overall st
ate of netwo
rk traffic net
work; medi
u
m
param
eters mainly refe
rs to roa
d
traffic
para
m
eters (flow rate, share,
et
c.); microsco
pic para
m
eters ma
inly refers to the vehic
l
e
operating sta
t
us
a
nd relati
onship
to ea
ch other.
T
h
erefo
r
e, the t
r
affic
state of
the u
r
ba
n ro
ad
netwo
rk
anal
ysis involve
s
a multi-scale,
multi-
varia
b
l
e
, highly ra
nd
om and tim
e
-varying comp
lex
system
s a
nal
ysis. O
n
ly te
mporal vari
ation
can
not d
r
aw traffic fro
m
the a
nalys
is
of the traffic flow
data, and
th
e nee
d to
establish
a rea
s
on
able
ro
ad
netwo
rk mo
del, define
conne
cted
micro-,
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Traffic Netwo
r
k O
p
tim
a
l Scheduli
ng Path
s Base
d on Ti
m
e
Intervals
Divi
sio
n
(Hao
Wei)
2647
medium
-an
d
macro-city ro
ad net
work t
r
affic statu
s
para
m
eters.
On this
ba
sis, the rig
h
t p
a
th
netwo
rk traffic statu
s
and i
t
s cha
nge
s a
nalyze.
Traffic vol
u
m
e
of g
ene
rati
on i
s
related
with th
e p
e
ople'
s p
r
o
d
u
c
tion
and
life
,
and
a
variety of social activities.
Different
path
at the
same
time, the sam
e
ro
ad at
a di
fferent time o
r
the same
roa
d
at the sam
e
time in the different
se
cti
ons of their traffic volume may be different,
and this diff
eren
ce a
nd
the cha
nge
have ce
rtain
regula
r
ity. This
chan
ge
is calle
d traffic
distrib
u
tion
chara
c
te
risti
c
s that the traf
fic o
c
cu
rs
with time a
nd
space differen
t. Studying the
variation of the traffic
will be able to
unde
rsta
nd
a
nd ma
ster th
e traffic characteri
stics. Roa
d
traffic plan
nin
g
, eco
nomi
c
analysi
s
of ro
ad traffi
c fa
cil
i
ties de
sig
n
, traffic ma
nag
e
m
ent and t
r
af
fic
safety are of
great si
gnificance.
In urba
n tra
ffic, different time intervals corre
s
po
nd to differe
nt traffic co
ndition
s.
Therefore, th
e driving time
weights of e
a
ch a
r
c
will chang
e with the time intervals. In dynamic
road
net
wo
rk
model, the
24
hou
rs in
one
day can
be
di
vided to
different time i
n
tervals a
c
cordin
g
to the traffic
condition
s. If the ro
ad
con
d
i
t
ions at
two time interval
s
are the
sa
me,
the wei
ghts
will
be the sam
e
. Table 1 is the
populatio
n st
atistical trip ti
me in one da
y in Liuzho
u city.
Table 1. Trip
Time Statistical Table
Trip
time
1 6:30-7:30
11:30-13:
00
2 7:10-8:30
17:00-18:
00
3 8:30-9:00
16:30-17:
00
Based
on th
e
con
d
ition
s
in
Table
1, one
day c
an b
e
d
i
vided to 10
time interval
s
(k0
~
k9),
as sho
w
n in
Table 2.
Table 2. Time
Division a
nd
Relate
d Traffi
c Co
ndition
s
km
Time
Traffic Condition
s
km
Time
Traffic Condition
s
k0 6:00-7:30
Sparse
k5
13:30-14:
30
Peak
k1 7:30-9:00
Peak
k6
14:30-16:
30
Sparse
k2 9:00-11:3
0
Sparse
k7
16:30-19:
30
Peak
k3 11:30-13:
00
Sparse
k8
19:30-22:
00
Sparse
k4 13:00-13:
30
Sparse
k9
22:00-6:0
0
Sparse
The blo
c
ked
con
d
ition
s
of the traffic can
be
cla
ssifie
d
to 5
levels- 1 e
x
tremely
unblo
c
ked; 2
unblo
c
ked; 3
slightly
blo
c
ked; 4 medi
all
y
blocked; 5
seriou
sly blo
cked. Throug
h the
traffic
conditi
ons at e
a
ch ti
me in ta
ble
2
as
well
as the
traffic bl
ock
evaluation
in
dexes, th
ere
are
some
co
ncl
u
sion
s-k1,
k7
belon
g to pe
ak time, the i
ndex is 5; k3, k5 are le
ss, t
he index i
s
4; k2,
k6 a
nd
k8
maybe have
slightly blo
c
ked
situati
o
n
,
the index i
s
3; k0, k4
are
com
para
b
ly
unblo
c
ked, th
e index is 2; k9 belon
gs to
extrem
ely un
blocke
d time intervals, the i
ndex is 1.
Thro
ugh
the
previou
s
anal
ysis, thi
s
pap
er
build
s th
e
dynamic road
network
mod
e
l ba
se
d
on traffic time
division. The
r
e are:
)
,
,
,
(
D
T
E
V
G
n
i
v
V
i
,
,
3
,
2
,
1
j
i
V
v
V
v
v
v
E
j
i
j
i
,
,
,
E
v
v
v
v
d
D
j
i
j
i
)
,
(
)
,
(
s
m
k
K
m
,
,
3
,
2
,
1
K
k
E
v
v
E
v
v
w
T
m
j
i
i
p
k
pij
,
,
,
,
(1)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2645 – 2
651
2648
In the
above
6 eq
uation
s
,
G is u
r
ba
n
ro
ad n
e
two
r
k
chart, a
nd
ea
ch a
r
c corre
s
p
ond
s to
one time
wei
ght. V is the i
n
formatio
n se
t of the nod
e
s
in G; E i
s
t
he directe
d
a
r
cs
set in G;
D is
the distan
ce
betwe
en the
two co
ntiguo
us no
de
s in E;
T is the time nee
d to finish d
r
iving a
ll of
the directe
d
arcs i
n
E; K i
s
time inte
rv
als
se
t. Figu
re 1 i
s
the
dynamic ro
ad
n
e
twork
ba
sed
on
time division.
Figure 1. Dyn
a
mic Road
Network Ba
sed
on Time Divi
sion
In Figu
re 1,
wkm
p
ij rep
r
e
s
ent
s the tim
e
finish
i
ng
dri
v
ing the di
re
cted arc
of <vi
,
vj> from
the precurso
r nod
e vp via t
he
start n
ode
vi in the
dire
cted arcs
of <vp,vi>
and
<v
i,vj> in the ti
me
interval of
km
. wkm
p
ij in
clu
des th
e d
e
lay of the p
r
e
c
u
r
so
r n
ode
vp
at node
of vi
处
and the
time
from vi to vj. The
r
efore,
althoug
h at t
he
same
time, the time f
i
nishi
ng d
r
ivi
ng
<vi,vj> from
different di
re
ction
s
i
s
diff
erent. T
hen,
at the
sam
e
time, an
a
r
c
will
co
rrespond
to diffe
rent
weig
hts. Thu
s
, whe
n
time interval is s, there
a
r
e s g
r
oup
s of time
weig
hts in the dynamic ro
ad
netwo
rk. F
r
o
m
the previo
u
s
analy
s
is, th
e differe
n
c
e
s
betwe
en the road net
wo
rk
model b
a
sed
on
time division
and othe
r mo
dels a
r
e a
s
follows.
(1) Th
e roa
d
con
d
ition
s
an
d feature
s
are compl
e
tely con
s
id
ere
d
which is in a
c
corda
n
ce
with the dyna
mic rul
e
s.
(2) T
he time informatio
n of the road n
e
twork
can b
e
ob
tained directl
y
by GPS.
(3) Ea
ch a
r
c
can
corre
s
p
o
nd to multiple
weight
s ba
se
d on pre
c
u
r
so
r node
s.
(4) The
a
c
tu
al condition
s of the
roa
d
s
a
r
e
di
re
ctly or i
ndirectly
co
nsi
dered,
su
ch
as
driving time a
nd delay at crossro
ad.
3.
Optimal Paths Solutions
in D
y
namic
Road
Ne
t
w
o
r
k Model
The improve
d
Dijkstra al
g
o
rithm is a
p
p
li
ed to solve
the dynamic
optimal path
probl
em
based on tim
e
division.
3.1. The Da
ta Struc
t
ure
of the Impro
v
ed Dijkstra Algorithm
In the propo
sed roa
d
network m
odel, th
e dire
cted a
r
cs at ea
ch ti
me co
rre
sp
o
nd to a
grou
p of time
weig
hts. The
array N
stores the
ar
cs
set of E, the adjacen
cy lists store th
e wei
ght
of each directed arcs in E. For mth
sin
g
l
e list, it
can
store
the tim
e
wei
ghts
wh
en it driven
the
whol
e dire
cte
d
arc at time km-1. The ad
jace
ncy
matri
x
stores the
pointer
s of the dire
cted arcs.
The pointe
r
s are u
s
ed to lo
cate the adj
a
c
en
cy lists in
the array as shown in Figu
re 2.
Figure 2. The
Adjacen
c
y Li
sts St
orin
g the Dire
cted Arcs
Weig
hts
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Traffic Netwo
r
k O
p
tim
a
l Scheduli
ng Path
s Base
d on Ti
m
e
Intervals
Divi
sio
n
(Hao
Wei)
2649
3.2. Computation Step
s of the Impro
v
ed Dijkstra Algorithm
In orde
r to we
ll combin
e the establi
s
h
e
d
dynamic roa
d
netwo
rk m
o
del and imp
r
o
v
ed
Dijkstra al
go
ri
thm, a new e
quation
co
st(i
,j,pre,k
m
)
is i
n
trodu
ce
d to rep
r
e
s
ent the
time weights
driving from v
p
to <
v
i,vj>
at time k
m
. Then,
1
!
]
][
[
and
if
].
[
.
]
][
[
j
i
Windex
pre
preNode
w
k
next
j
i
Windex
Road
m
k
t
m
，
1
!
]
][
[
and
-1
if
].
[
.
]
][
[
min
j
i
Windex
pre
w
k
next
j
i
Windex
Road
m
k
t
m
，
1
-
]
][
[
if
j
i
Windex
，
The Equatio
n (8) i
s
u
s
e
d
to initialize
the
algorith
m
. The funct
i
on first
com
putes th
e
minimum tim
e
weig
ht coll
ected by the
different
precursor n
ode
s i
n
dire
ct
ed a
r
c <vi,vj> at time
k
m
. Th
e
me
an
in
gs
o
f
th
e
c
h
ar
ac
te
r va
ria
b
l
es
in th
e
a
l
g
o
r
ithm ar
e a
s
fo
llows
.
S—
s
e
t var
i
ab
le
whi
c
h is th
e
set of the no
des i
n
optima
l
path;
s(vi)—
Boolean va
ri
able which id
entifies
whet
her
found th
e o
p
timal path
to th
e no
de
of vi; d(vi)—th
e tim
e
to fini
sh th
e
optimal
path;
p(vi)—poi
nte
r
,
the precurso
r nod
es cho
s
en by
node
vi; T—the ti
me a
rrived
a
t
the no
de. T
he d
e
tails of
the
algorith
m
are
as follo
ws.
(1) Initiali
zati
on. Assume t
he cars leave
the star
t point v0 at time t0, the time interval of
time t0 can b
e
obtaine
d as km, other no
des vi ca
n be
compute
d
by equation (8).
(2) Th
e node
s meeting
s(vi)=false are
sea
r
c
hed. Fa
lse re
pre
s
e
n
ts the optimal
path to
node vi d
o
e
s
n’t find. The
node
s
with m
i
nimum d
(
vi)
are
cou
n
ted t
o
set of S. B
y
computin
g t
h
e
time of T=T
+
d(vi) the
ca
rs a
rriving
at vi, t
he time intervals
km
belon
ged to
time T ca
n
be
obtaine
d.
(3)
R
e
v
i
sion.
I d(v
k
)
>
d
(v
j)
+
co
st(i,j,p(v
j),
k
m),
as
sum
e
d(v
k
)
= d
(
v
j
)+
co
st(i,j,p(v
j)
),
p(v
k
)
=
vj until the paths with short
e
st time are f
ound.
(4) Steps (2
)
and
(3) are re
peated
until
s(vt)=tr
ue. Tru
e
re
pre
s
e
n
ts
optimal p
a
th
of node
vi is found. vt
为
is the end p
o
int.
(5)
Re
call. B
a
se
d on
pre
c
ursor
pointe
r
p, the optima
l
path P0t fro
m
start v0 to
end vt
can b
e
obtain
ed, that’s:
1
)!
(
and
)
(
,
,
,
1
0
0
j
j
i
t
t
v
p
v
p
v
v
v
v
P
(2)
4. Experiment
and
An
aly
s
is
Aiming at the
dynami
c
opt
imal path
s
pl
annin
g
probl
em ba
sed
on
traffic time i
n
tervals
division, this paper
build
s a sim
u
latio
n
experim
ent
platform in whi
c
h the pl
atform uses
the
p
r
oc
es
so
r
o
f
In
te
l
Co
reT
M
2 Duo E7
5
00@2.93G
Hz, and memo
ry of 4.00GB.
The develo
p
ment
environ
ment use
s
Vi
sual
C++ and
MA
PX
widg
ets. T
he time
wei
ghts
of the
di
recte
d
a
r
cs i
n
th
e
road n
e
two
r
k model a
r
e co
mputed a
s
followin
g
rule
s.
(1) The
dyn
a
mic
ro
ad n
e
twork
situati
on b
a
s
ed o
n
traffic time
division i
s
si
mulated.
Assu
ming th
e time weigh
t
s of ea
ch
ro
ad at differen
t
time are
ro
ad len
g
th/sp
e
ed limit and
the
delay at cro
s
sro
ad is 0.
(2) The dyna
mic
road net
works when
the
road
s a
r
e
blocke
d a
r
e
simulate
d. Th
e traffic
blocks only si
mulate the bl
ocks at cro
ssroad
s an
d Ro
tary intersecti
on.
Ten time
s of
simulatio
n
ex
perim
ents
are
ca
rri
e
d
o
n
b
a
se
d on
the p
r
eviou
s
rule
s
and the
traffic conditi
ons
at ten ti
me interval
s.
Figure 3 i
s
at time k0
(6
:00-7:30
), the
traffic condit
i
on
belon
gs to ro
ads pla
nning
probl
em
at id
le time, Fig
u
re 4 i
s
at time
k7
(16:30
-19
:
30), the
traffic
con
d
ition bel
ong
s to the ro
ads pl
annin
g
probl
em at pe
ak time.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2645 – 2
651
2650
Figure 3. Optimal Paths Plannin
g
at Time k0
Figure 4. Optimal Paths Plannin
g
at Time k7
From Fig
u
re
3 and 4, the improved Di
jka
s
tr
a alg
o
rit
h
m can avoi
d driving to blocke
d
road
s at diff
erent time to
find other
p
a
ths. T
he
si
mulation exp
e
rime
ntal re
sults at ten ti
me
intervals a
r
e
as sho
w
n in
Table 3.
Table 3. Simulation Experi
m
ent Re
sults
at Different Ti
me
Time Overall
lengths
of the paths (m
)
Driving time (s)
Path planning
time (ms)
k0 1285.68
97.28
388
k1 1897.36
2246.83
259
k2 1285.68
132.09
311
k3 1285.68
266.98
311
k4 1285.68
96.33
297
k5 1897.36
1917.58
362
k6 1285.68
157.41
339
k7 1897.36
2107.53
283
k8 1285.68
161.76
341
k9 1285.68
74.20
335
Referrin
g th
e time inte
rvals an
d tra
ffic situation
s
in T
able
2 and
comp
aring
the
simulatio
n
re
sults in
Table
3, the traffic situation
at ti
me k1,
k5 an
d k7 i
s
at pe
ak
which is
more
cro
w
d th
an o
t
her time int
e
rvals
and th
e driving tim
e
is lon
ger.
By combinin
g the sim
u
lat
i
on
results in Fig
u
re 4, altho
u
gh traffic is
conge
sted at
time k7, the i
m
prove
d
Dij
k
stra al
gorithm
still
can
re-pl
an t
he p
a
ths a
n
d
the time
for
sea
r
ching
pat
hs i
s
me
rely
283m
s. G
ene
rally
spe
a
kin
g
,
the imp
r
oved
Dij
kst
ra
alg
o
rithm
ca
n e
ffectivel
y pla
n
the
optima
l
path
s
in
th
e dyna
mic road
netwo
rk m
o
d
e
l based on ti
me interval
s division.
5. Conclu
sion
This pa
pe
r ca
rrie
s
re
se
arch
on dynamic
optim
al path
s
plannin
g
pro
b
lem ba
sed o
n
traffic
time division,
builds
simul
a
ted dynami
c
ro
ad net
work m
odel, a
nd pre
s
e
n
ts
the com
putat
ion
step
s for im
p
r
oved
Dijkstra algo
rithm
whi
c
h fulf
ills t
he effective
combinatio
n of
the model
a
n
d
algorith
m
. Th
e roa
d
net
work
mod
e
l b
a
se
d on tim
e
division
ca
n truly refle
c
t the city traffic
feature
s
whi
c
h has
some
pra
c
tical valu
e. The
re
sult
s of the simu
lation experi
m
ents p
r
ove
the
prop
osed m
odel a
nd
co
mputation m
e
thod h
a
ve
some
fea
s
ibi
lity in paths planni
ng a
n
d
comp
utation efficien
cy.
Referen
ces
[1]
Shuq
iao Z
h
ou,
Peter Del
y
, R
u
i
x
i Yu
an, And
r
eas Kassl
er. Mitigati
ng Co
nt
rol Ch
ann
el Sa
turation i
n
th
e
D
y
namic C
h
a
n
nel Assi
gnme
n
t
Protocol.
JCIT.
2011; 6(6): 271-
281.
[2]
Guang
Li, Ya
d
ong W
a
ng. A
Ne
w
Meth
od f
o
r Privac
y-Pre
s
ervin
g
Data
Minin
g
Bas
ed
on W
e
i
ghte
d
Sing
ular Va
lu
e Decom
positi
o
n
.
JCIT
. 2011; 6
(
3): 28-34.
[3]
JIA An- chao, Z
H
OU Gang. Stud
y
on Se
le
ction
of Sup
p
li
ers Based o
n
Rou
gh Set an
d BP Neura
l
Net
w
ork.
Lo
gis
t
ics T
e
chnol
og
y.
2012; 31(
12)
: 229-23
2.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Traffic Netwo
r
k O
p
tim
a
l Scheduli
ng Path
s Base
d on Ti
m
e
Intervals
Divi
sio
n
(Hao
Wei)
2651
[4]
Che
ng-H
o
n
g
Y
ang, S
hen
g-W
e
i T
s
ai, Li-Ye
h
Chu
a
n
g
, Ch
e
ng-H
uei Y
a
n
g
. A Modifi
ed
P
a
rticle S
w
a
r
m
Optimizatio
n
for
Global Optimi
zation.
IJACT
. 201
1; 3(7): 169
-189.
[5]
Ying
CHEN,
Runto
ng Z
H
A
N
G, Hao
y
u
e
LI, Rui
x
i
a
LI, Yuho
ng GAO. CALIS-bas
ed
Clo
ud L
i
br
ar
y
Services Pl
atform Model.
AISS
. 2011; 3(6): 204-
212.
[6]
GUO Qiu-xia,
DENG
X
i
ang-
ming, OU Y
a
ng-
jiang.
Ev
aluation of
Value
Chain Risks Based on B
P
Artificial Neural Net
w
ork.
Log
i
s
tics T
e
chnol
o
g
y.
2011; 3
0
(7)
:
120-12
2.
[7]
Jirasak Gorn
mane
e, Kittima Mekha
bunc
hakij. T
r
anslati
on IT
IL Service Operatio
n to Ontologic
a
l
Artifacts.
JCIT
. 2011; 6(9): 2
7
1
-29
4
.
[8]
Josep
h
K Sir
o
r, Lia
ng Gu
a
ngu
n, Pan
g
K
a
if
an
g, She
n
g
Hua
n
y
e, W
a
ng D
ong. Imp
a
ct of RF
ID
T
e
chnolog
y
on
T
r
acking of Export Goods in
Ken
y
a.
JCIT
. 2010; 5(9): 1
90-
199.
[9]
Hua
ng R
u
i. Dif
fusion
of Mobi
l
e
Pho
nes i
n
C
h
in
a: Appl
icati
on of Bass
Dif
fusion M
ode
l.
JCIT
. 2012;
7(1): 54-6
1
.
[10]
QIU Shi-hui. A
nal
og Circ
u
it F
ault Di
agn
os
is
Based o
n
Artificial Ne
ura
l
Net
w
o
r
k.
Scienc
e T
e
chno
log
y
and En
gi
neer
in
g.
2012; 1
2
(30)
: 8042-8
0
4
6
.
[11]
Jieju
n
Hua
ng,
Yan
y
a
n
W
u
, Y
i
ng
xi
a W
u
, Y
u
n
j
un
Z
han,
Ha
o
W
u
. Anal
ys
is o
f
Spatio-tem
po
ral C
h
a
n
g
e
s
of Land Us
e in
W
uhan C
i
t
y
Us
ing R
e
mote Se
nsin
g an
d GIS.
IJACT
. 2012; 4(1): 215-
22
2.
[12]
Qiu Che
n
, Ko
ji Kota
ni, F
e
ifei Le
e, T
adahiro
Ohmi. F
a
ce Reco
gn
itio
n Usin
g VQ Histogr
am
i
n
Compress
ed DCT
Domain
. JCIT.
2012; 7(1)
: 395-40
4.
[13]
Z
hang
Li
hu
a.
A Ne
w
Q
u
a
n
tum Cl
on
e Ge
netic
A
l
gor
ith
m
Base
d Mu
lti-user
Detecti
o
n for C
D
MA
Sy
s
t
e
m
.
IJACT
. 2011; 3(1
1
): 17-25.
[14]
Vahi
d B
ehrav
e
s
h, Se
yye
d
M
ohamm
ad
Rez
a
F
a
rs
hc
hi. A
Novel
R
a
n
dom
ized
Se
arch T
e
chn
i
qu
e fo
r
Multipl
e
M
obi
le
Rob
o
t Paths
Plan
nin
g
In
Re
petitive
D
y
n
a
m
i
c Envir
onm
ent
.
IAES Internat
ional J
ournal
of Robotics a
n
d
Auto
matio
n
. 201
2; 1(4): 214
-222.
Evaluation Warning : The document was created with Spire.PDF for Python.