Copy igh © IFAC T anspona ion Sys ems
Chania, G eece, 1997
AN
HEURISTIC ALGORITHM FOR DYNAMIC NETWORK LOADING
E.
Codina,
J.
Ba ce16
Poly hecnic Uni e si y
o
Ca alonia. Spain. Dep .
o
S a is ics and
O.R
.
e-mail:[email p o ec ed].es
Abs ac
: This pape desc ibes an heu is ic p ocedu e o
he
p oblem
o
de e mining
he
ime e olu ion o a ic
lows
and ou es on a oad ne wo k
wi h
he
key equi emen
ha
i s compu a ional cos s mus be appealing so
as
o
include i as
pa
o a eal ime T a ic Managemen Sys em.
Keywo ds: Road T a ic, Dynamic Models, Heu is ics,
Pa h
Planning, Delay
Es ima ion
.
1.
INTRODUCTION
In
he
las
yea s se e al esea ch and de el-
opemen p og ammes ha e included p ojec s
aiming
o
he
de elopemen
o
T a ic Man-
agemen
and
In o ma ion Sys ems
o
help in
he
eal
ime
es ima ion and p edic ion o a -
ic
condi ions in oad ne wo ks,
o
assis in
eal- ime a ic managemen
and
o
p o ide
he
basic in o ma ion
o
be b oadcas ed
o
oad use s
o
displayed
a
he
a iable mes-
sage signals. To achie e
he
goal o ha ing a
sys em wi h a eal
ime
esponse
he
appli-
ca ion equi es
he
use
o
p o en op imiza-
ion
and
simula ion algo i hms
ha
p esen
p ope cha ac e is ics
o
nume ically handle
he
a ic models as enough. In p inciple
he
mig a ion
o
a pa allel compu ing en i-
onmen has appea ed as
he
unique p ac ical
al e na i e
o
achie e his goal and some e-
sea ch e o s ha e been done in his di ec ion
(Chabini e
al.
, 1992) as
well
as p ojec s as
pa
o
R & D p og ammes such as
PETRI
(PETRI
P ojec
1993, 1995) IVHS and AM-
TICS. A key componen o a eal- ime T a ic
Managemen Sys em consis s, amongs o h-
e s, o a Dynamic T a ic Assignmen module.
531
The
Dynamic T a ic Assignmen p oblem has
been posed unde de e minis ic
and
s ochas-
ic app oaches
and
o mula ed in a a ie y
o ways using con inuous
o
disc e ized op-
imal con ol models
and
a ia ional inequal-
i y models (F iesz e al., 1989; Me chan
and
Nemhause , 1978; Be ns ein
and
F iesz, 1993
and o he s) o by means
o
heu is ic models
(Janson, 1991; de Romph
and
Hamme slag,
1992). Also, ques ions ela ed
o
he
ex ension
o
he
Wa d op p inciples
o
he dynamic case
and
o
he
concep
o
a dynamic equilib ium
ha e been examined in Smi h (1993) and
he
consis ency o some models has been exam-
ined
in
Codina and Ba cel6 (1995). Al hough
se e al algo i hmic p oposals o
he
op imal
con ol o mula ions ha e eme ged
(Codina
and Ba cel6, 1992,1995),only om
he
heu is-
ic and simula ion app oaches (Ba cel6
and
Ma in, 1994) compu a ional esul s on ull
size ne wo ks ha e been p esen ed up
o
now.
This
pape
desc ibes an heu is ic p ocedu e
whose compu a ional equi emen s ely basi-
cally on
he
compu a ion
o
sho es
pa hs
on a
anspo a ion
ne wo k
and
on app oxi-
ma ely sol ing he simple con inuum model in
o de
o
model
he
a ic
low
dynamics. Also
a ema cable aspec o
he
heu is ic
is
ha
he
e alua ion
o
a el imes elies on p edic ions
o he a ic densi ies on
he
links o
he
ne -
wo k.
2.
DESCRIPTION
OF
THE
HEURISTIC
PROCEDURE
Le us deno e by 9 =
(N,
A)
a g aph model-
ing an
u ban
ne wo k wi h N
he
se o nodes
and A
he
se
o
links. Le us deno e by
p~( )
he
numbe
o
ips
pe uni
o
ime
ha
en-
e
he
ne wo k
a
node 0 E
()
in
he
se
o
o igins,
a
ime
ins an
wi h des ina ion
node q E D in
he
se o des ina ions D
o
he
ne wo k. In
o de
o
desc ibe a ic lows
we
shall use wo magni udes: a ic
lows
and
a ic densi ies
a
a gi en link segmen . We
shall deno e
he
o al
low
on a link by
ja
and
he
o al
densi y on a link by
Xa
and
we
shall
supose
ha
hey
a e unc ions
o
he
link posi-
ion
Za
and
he
ime
ins an
,
Xa
= xa(za, ),
ja
= ja(za, ). Also
we
shall decompose a ic
lows and densi ies in o
lows
and
densi ies
pe
des ina ion: x a =
Lq
ED
x~
,
ja
=
Lq
ED
jg
and
ha
he e
exis s a speed- low ela ionship
o each
o
he
links
o
he ne wo k
o
he
ype
speed = wa(xa).
In Codina
and
Ba cel6 (1995), i has been
shown
ha
many
o
he
exis ing dynamic a -
ic
assignmen models desc ibe
he
e olu ion
o
a ic lows on a mul ides ina ion ne wo k
wi h
ma hema ical
models
ha
app oxima e
he
ollowing hype bolic
PDE
sys em:
aX~
+
aJ~
= 0,
Va
E A
a
aZa
B+l(O-
, ) -
B-l
(Z+,
) +
+ eqsq( ) = pq( ) V q E D
Jq(Za
, )
~
0
( xa(za, ) = LqED xHza, ) )
(Known
ini ial
(1)
Ano he se
o
cons ain s, exp essing a lim-
i ed
h oughpu
o
links like LqED
J~(Za+
,
)
~
Va,
and
a
maximum
admi ance
o inpu lows
like LqED JHO-, )
~
Ua,
Va
E. A , could b.e
added
o
he
equa ions ep esen mg
he
easI-
ble se o lows. Nonnega i i y cons ain s on
he
densi ies xq(
Za,
)
~
0
a e
edundan
i
532
he
speed densi y ela ionships
Wa
( . )
a e
de-
c easing in
[0
,
xal
and e i y
wa(O)
> 0 and
wa(xa) =
O.
I
can be easily shown
ha
o-
al
lows
on links obey
o
he
classical hype -
bolic
PDE
ha
desc ibes he simple con in-
uum model:
X
+
<p(x
)xz = 0 ,
<p(x)
=
d(
x~(x))
.
The
condi ions
ha
de e mine a
unique solu ion
o
X
+
<p(
x)x
z = 0 on a
link a e
he
ini ial densi y on
he
link
a
ime
=
o,
he
inpu
low
a
he
beginning
o
he
link
j(O-,
) = u( )
and
he
exi low
a
he
end o
he
link, j(za+, ) = ( ).
The
app oxima ion
o
he
sys em (1)
is
usu-
ally ull o dange s, specially in
he
case
o
noncons an
p opaga
ion speed
Wa
and
, addi-
ionally,
he
compu a ion
o
he
solu ions
o
he
app oxima ing schemes
is
ime consum-
ing.
I
he
solu ion x*(za, )
o
he p e ious
PDE
is
known hen i
is
possible o calcula e ime-
space ajec o ies o
o al
lows as solu ions
o
ia = w(x(za, )). In his con inuum model i
can be shown
ha
a gi en
ajec o y
is
only
in luenced by p e ious
and
neighbo
ajec o-
ies. Howe e , i
is
known
ha
he
o mula-
ion o dynamic a ic assignemn models
is
based on
he
knowledge o
he
e olu ion o
he
demands along a gi en ime ho izon. To
e e come his p oblem
he
heu is ic assumes
ha
p edic ions on
he
a ic densi ies on
he
links o
he
ne wo k a e a ailable
and
hey
a e
used when a ic lows each an in e sec ion.
Le b be a ime leng h simila in
magni ude
o
he
sho es a el
ime
o a link in
he
ne -
wo k
(b
=
10
o
30 seconds).
We
shall e e
o
b as
JL- ime
slice. I each
he
O-D olumes
bp~
o a gi en o igin 0 E
()
is
conside ed
as a uni
o
"pseudo-pla oon" when loaded
on
he
se
o
ime-dependen sho es
pa hs
oo ed on 0 a packe
o
ajec o ies will be
o igina ed on
he
links con ained in
he
ee
.
When pe o ming his ope a ion o each o i-
gin 0 each link will con ain a se
o
packe s
o
ajec o ies. Some o hese packe s will join
making up a
g ea e
one and o he s will e-
main isola ed. Fo a gi en o igin 0 in
he
se
o
o igins
()
o
he
ne wo k and packe
l- h
. d
b;
l
Tl
-l
l
on link
a,
le us eno e y
a,
a, a'
Ta
'
Ta'
X~
,
j!
he
ollowing magni udes:
-
i~,
;
.
The
en y
ins an
a
link a E A o
he
i s and las ca o packe i . -
T~.
The
depa u e
ime om
he
head
o
link a E A
o
he i s ca in packe
i.
-
~
,
T~.
The
ins an s
a
which
he
head
o
he
link a E A is eached by he i s and las ca
o packe
- h
.
-
x~
,
j~.
Densi y
and
low
a
he
ail o link
a E A o ca s
in
packe
l- h
a
he
ime
ha
he packe passes h ough link a E
A.
The
densi y
x~
a
ime
::::::
~
is
e alua ed ha -
ing in o accoun p edic ions based on coun s
o simila a ic condi ions and
j~
is
aken as
·l _ l ( l ) A
d·
I l
hl
d
Ja -
xa·w
xa·
cco
mgy,
Ya
' a a e en-
si y and low
a
he
head o
he
link.
Le us also assume
ha
o each link a E A
in
he ne wo k
he
ime-space e olu ion
o
he
packe s
o
ca s
ha
en e ed in
he
ne wo k
du ing
i- h
I-l- ime slice coming om each o i-
gin 0 E 0
is
app oxima ely known, i.
e:
~
,
~
a e known o packe s
ha
o igina ed
a
link a due
o
ca s en e ed
a
ime i- h. These
wo
ins an s
o ime can be de e mined using
a ime dependen sho es
pa h
algo i hm as
poin ed
ou
in Kau man and Smi h (1993),
as ime-dependen link a el ime unc ions
can be app oxima ed by ca( ) = la/wa(xa( ))
and le us supose
ha
unc ions ca( ) e i y
he
consis ency assump ion also ou lined in
Kau man
and
Smi h (1993), i.e: sup {
(ca(s)-
Ca ( )) -( -
s)}
~
0 o 0
~
s
~
.
Le us
deno e
now by
7 ~
he
numbe o ca s
in o one
o
hese packe s
on
link a E A
ha
en e ed du ing
i- h
I-l- ime slice
o
he
ne -
wo k. We shall call o he p ocess o de e -
mining
he
magni udes depic ed in igu e 1
o he i + 1- h I-l- ime slice o
he
incom-
ing and ou going links o a node
" o
sol e
he
node
".
We shall nex desc ibe an heu is ic
o
sol e a
node
on which no a p io i p ecedence
ules
o
signal iming exis
and
o which wo
lows
only mix i hey a i e simul aneously
o
he node. Le us deno e by 7
he
numbe
o ca s in a packe
£'
o
link b incoming
o
link
a
ha
in e ac s
wi h packe
7 ;
. Also, i
is
as-
sumed
ha
i a ic olume
7 b
is
composed
o
olumes di e ing
o
he
allowed mo emen s,
hen all ca s in
7
a e delayed by he slowes
u ning low.
"Sol ing
a
node"
. Le now be
kEN
and
le
us
deno e
by:
-
[(k)
,
I(k)
he
se
o
eme ging and incoming
links om node k.
-
I
b E
I(k)
, hen E(b)
~
[(k)
is
he
se
o links ou going om link b, i.e. he mo e-
men
(b
--+
a)
is
allowed.
I
a E
[(k)
hen
lea)
~
I(k)
is
he
se o links incoming
o
link b, (i.e.
he
mo emen
(b
--+
a)
is
allowed).
533
(a)
o
<_
£i1!~
!e_n~ _h_
-=
_Z,:>
,
Za
· ,
,
· ,
Fig. 1. (a) A ypical
ajec o
y when
he e
a e
no discon inui ies in
he
o al
densi y. (b)
Magni udes used by
he
heu is ic ne wo k
loading.
-I a ic olume
7 b
is
decomposed
in o
i s
allowed mo emen s ,
7 b
=
LaEE(b)
7 ba
,
hen
by E+(b) = { a E E(b) I
7 ba
> 0 } i
is
deno ed
he
se o all ou going links
ha
will ecei e a nonull
low
om link b
and
by
l+(a)
=
{b
E
lea)
I
7 ba
> O} i
is
deno ed
he
se
o
all links
ha
send nonull
low
o
link a.
Fo links a E E(k) and b E
l(k)
i
is
ea-
sonable
o
assume
ha
~+
1
and
T:
a e
de-
e mined by
he
ime
ins an s
~,
acco dingly
o:
~+l
Max{ ~/la/E
n
E+(b)}
bEI+ (a) (2)
T;+I
=
Max{[~ Ilal
E
E+(b)}
Also i
is
possible o calcula e
he
amoun
o ime
O~+I
needed by
he
7 ~
ca s
o
en e
he
link as OHI =
7
HI
/J
·
1.
i
[HI
=
l.
a a a a a
(j~+I
=
j~
)
and
by
O~+I
=
7 ~+I
/}~+I
i
~+I
>
~
(}a
being he maximum
low
ad-
mi ed
by link a).
So
he las ca en e s
he
link
a
ime
~+I
=
~+I
+
(}~+1.
An "easy
o
compu e
" app oxima ion
o
he
ajec o
y
Z~+l( )
using an in eg a ion me hod based on
he
cha ac e is ics
o
X
+
<p(x)xz
= 0
de-
e mines
~
and
T~.
Finally o links en e ing
a
node
k:
T~+l
=
Max{
~+l
I a E
E+(b)}
(3)
As
an e alua ion o
THl
Hl
THl
l"o
he
b , b ' b I'
incoming links
a
node k has been made, hen
" +
1 I (
T~+
1 -
T~+
1 ) app oxima es
he
exi
low
and i
is
necessa y
o
examine i he e exis s
spillback on link b.
The
Heu is ic
Ne wo k
Loading.
The
al-
go i hm ollowed by
he
heu is ics
is
p esen ed
below. Fo simplici y
he
spillbak phenomenon
on a link b incoming
o
a node k has been ex-
cluded. In case o spillback
he
ail node
k'
o link b
mus
be sol ed again as well as
he
nodes
in
he
" o wa d
s a
" o k'.
(i) Fo
he
i- h
J.L- ime
slice calcula e
he
ime-dependen
sho es
pa h
ees
(sp
's)
on
he
ne wo k o each 0 E
O.
(ii) Load
he
ne wo k wi h O-D lows
b·(p~)'
on
he
sp 's
calcula ed in 1). De e mine
he
en y
and exi imes
~
,
~
o
he
new packe s
1l"~.
De e mine
he
se s
E+
(b)
and
1+
(a) o incoming links b and eme g-
ing links a
o
each
node
.
(iii) De e mine
~,
T~
o
he
newly gene a ed
packe s.
Ini ialize
he
se s A
0,
N+
:
AO={aEAla~
U£(n)}
,
nEN
N+
= { n E
NI
I(n)
::
0 }, (4)
NO=
{n
E
NII(n)nA°::
0}
(i )
While
no
(N+
= 0)
-Take
kENO
n
N+
;
- "Sol e node" k ha ing in o accoun
p edic ions o a ic densi ies
x~+l
,
a E
£(k) (De e mine
~+l,T~+l,
"la
E £(k),
Vb
E
T~+l
E
I(
k)
and
he
es o p e i-
ous magni udes);
-Fo a E £(k), se
AO
=
AO
u
{a};
-Se N+
=
N+-{k}
.
( )
Compu a ion
o
bes
and
wo s O-D a el
imes
(~)i,
(u~)i
o
J.L- ime
slice
i- h
ac-
co dingly
o
a,
a
and
a
,
Ta·
( i) i
~
i +
1.
GOTO
s ep
1)
534
The
ou pu s
o
he
heu is ic
a e
hus e ined
bounds on
he
O-D a el imes o ca s en e -
ing
he
ne wo k
and
a i al imes
o
he
ne -
wo k nodes
a
each
J.L- ime
slice.
3.
REFERENCES
Ba cel6
J.
,R.
Ma in
(1994a). Assesmen
o
ehicle guidance sys ems
and
s a egies
by simula ion.
P ep in s
o
he
TRISTAN
II
Con e ence,
Cap i
199.4-
I aly.
I.
pp.
239-255.
Be ns ein D., T.
L.
F iesz (1993). A a ia-
ional con ol o mula ion o
he
simul-
aneous
ou e
and
depa u e- ime choice
equilib ium p oblem. In: T anspo a ion
and
T a ic Theo y. (C.F. Daganzo, Ed.)
Else ie Science.
Chabini
1.
, O. D isi Kai" ouni
and
M.
Flo ian
(1992). Sol ing
he
ne wo k equilib ium
p oblem on a ne wo k
o
anspu e s
. In:
Publica ion du
CRT
876.
Codina E.,
J.
Ba cel6 (1995a). An algo i hm
o ex emals calcula ions in op imal con-
ol
p oblems wi h applica ions
o
he
dy-
namic a ic assignmen p oblem. In:
U -
ban T a ic
Ne wo ks
(N.H.
Ga ne
, G.
Imp o a,
Eds.),
Chap
.
12
,
pp
. 311-331.
Sp inge Ve lag, Be lin.
Codina E., J. Ba cel6 (1995). A sys em op-
imal dynamic a ic assignmen model
wi h dis ibu ed
pa ame e s
. In:
Ad-
anced Me hods
in
T anspo a ion
Anal-
ysis
(L. Bianco,
P.
To h,
Eds.), Chap. 13,
pp. 299-320. Sp inge Ve lag, Be lin.
Codina E.,
J.
Ba cel6 (1995b). Dynamic a -
ic
assignmen : conside a ions on some
de e minis ic modelling app oaches.
An-
nals
o
Ope a ions Resea ch,
60
, pp. 1-58
F iesz T.L., F.J.Luque, R.L.Tobin
and
B.W.Wie (1989). Dynamic ne wo k
a ic assignmen conside ed as a con in-
uous ime op imal con ol p oblem. Op.
Res.,
37-6
, pp.58-69.
Janson B.N. (1991). Dynamic a ic assign-
men
o
u ban
oad ne wo ks. T ansp.
Res.,
25B
pp
. 143-161.
Kau man D.E., R.L. Smi h (1993). Fas es
pa hs
in ime-dependen ne wo ks o
in elligen highway sys ems applica ion.
IVHS
Jou nal.
1(1) pp. 1-11.
Me chan D.
K.
, G.L.Nemhause (1978). A
model
and
an algo i hm o
he
dynamic
a ic assignmen p oblem. T ansp.
Sci.
,
12,
No 3.
Technical annex guidelines o
PETRI
p ojec
(1993). Pa allel
Compu ing
o Spain
(PACOS).
PCI
P ojec
(EP-9602).
PETRI
P ojec (1995). Pa allel Compu ing
o Spain (PACOS)
PCI
P ojec (EP-
9602). Municipali y o Ba celona, UPC,
UITESA. Deli e able 1 - De ailed Sys em
Design.
de Romph E
.,
H.J.M. an G ol,R. Hame -
slag (1992). 3DAS -3-Dimensional Assi-
gnmen - A
dynamic
assignmen model o
sho p edic ions. P ep in s
o
he 89 h
Mee ing
o
he
RSA!,
Chicago, USA.
Smi h M.J. (1993). A new dynamic a -
ic
model
and
he
exis ence
and
cal-
cula ion o dynamic use equilib ia on
conges ed capaci y-cons ained oad ne -
wo ks. T ansp. Res.,
27B
,
No
1. pp.
49-
63.
535