TELKOM
NIKA
, Vol.13, No
.2, June 20
15
, pp. 632 ~ 6
4
3
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i2.1437
632
Re
cei
v
ed
Jan
uary 13, 201
5
;
Revi
sed Ma
rch 2
9
, 2015;
Acce
pted April 20, 2015
An Ant Colony-Based Heuristic Algorithm for Joint
Scheduling of Post-Earthquake Road Repair
and Relief Distribution
Bei Xu, Yuanbin Song*
Dep
a
rtment of T
r
ansport, Shippi
ng a
nd Lo
gi
stics, Shangh
ai
Jiao T
ong Uni
v
ersit
y
,
Shan
gh
ai 20
02
40, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
y
b
s
ong
@sjtu
.
edu.cn
Abs
t
rak
Emer
ge
ncy ro
ad rep
a
ir a
nd
distrib
u
tion
of relief
g
o
o
d
s are
crucial for p
o
s
t
-earthqu
ake r
e
spo
n
se.
How
e
ver, inte
rrelatio
n
sh
ips
betw
een th
os
e tw
o tasks are n
o
t ade
q
uately c
onsi
d
e
r
ed in t
heir
w
o
rk
sch
e
d
u
l
e
s
,
e
s
p
e
c
ia
l
l
y
i
n
ca
se
s wi
th
ve
ry l
i
m
i
ted
re
p
a
i
r
re
so
u
r
ce
s, l
e
a
d
i
n
g to
un
ne
cessa
ry de
l
a
y and
expe
ndit
u
re. A time-s
pac
e net
w
o
rk mod
e
l is
constructed
to
better descri
b
e
the constrai
nts arisin
g from t
h
e
interrel
a
tio
n
shi
p
s in joi
n
t schedu
lin
g of roa
d
repair
a
nd r
e
lief distri
buti
o
n w
o
rks. An a
n
t colony-
base
d
Heuristic
al
gori
t
hm is
dev
elo
p
ed to so
lve th
e NP-har
d mo
d
e
l
efficiently for
p
r
actical us
e, fol
l
ow
ed by
a cas
e
study of
Wenc
hua
n E
a
rthqu
a
k
e to v
a
li
date
t
he
pla
n
n
i
ng
to
ol
and
to
de
mo
nstrate its f
easi
b
ility
for res
o
lvi
n
g
real w
o
rld pr
ob
le
m.
Ke
y
w
ord:
Ant Colo
ny Alg
o
rith
m, Sche
dul
ing,
Post-earthqu
a
k
e Resp
ons
e, T
i
me-S
pac
e N
e
tw
ork
1. Introduc
tion
Earthqu
ake is con
s
ide
r
ed
as a
seri
ou
s thre
at to life safety. To redu
ce life lo
ss
an
d
injurie
s
, the
d
e
livery of living an
d me
di
cal
comm
odi
t
i
es to
ben
eficiarie
s
i
s
the
most u
r
ge
nt
and
importa
nt work in
the
sh
ort
-
term
po
st-e
a
r
thqua
ke
respon
se. T
he
di
stributio
n effi
cien
cy i
s
g
r
e
a
tly
depe
ndent o
n
the re
cove
ry of road
n
e
twork. Un
fo
rtunately, ca
se
s often o
c
cur th
at rep
a
ir
resou
r
ces are too limite
d
to rep
a
ir
all t
he d
a
mag
ed
road
s i
n
a
short time. T
h
us
a
sho
r
t-te
am
repai
r pla
n
fo
r pa
rt of the damag
ed roa
d
se
gment
s, as
well a
s
a
corre
s
p
ondin
g
delivery pl
a
n
,
has to be ma
de on pu
rpo
s
e of improvin
g the relief di
stributio
n efficien
cy.
However, great
challeng
es still exist to
optimize the
effici
ency. On the term
of
practice,
road
repai
r a
nd relief distri
bution wo
rk
a
r
e no
w
sched
uled
manu
all
y
and
se
pa
ra
tely by differe
nt
depa
rtment
s
according to
deci
s
io
n-m
a
kers’
expe
rien
ce in
Chi
na.
As for
re
sea
r
che
s
related,
up
to
now, whil
e
po
st-e
arthq
uake
road re
pair and reli
ef distri
butio
n are ex
ten
s
ively researched
respe
c
tively, the study of j
o
int sche
duli
ng of po
st-e
a
r
thqua
ke
ro
a
d
rep
a
ir a
nd
relief di
stribut
ion
remai
n
s
at a
low level. It i
s
also
re
co
gni
zed
by
Altay and
Gre
en [1
] that the la
ck of re
se
arch
on
inco
rpo
r
ate
o
peratio
ns wo
uld b
e
the
bo
ttleneck in
th
e field
of di
sa
ster re
sp
on
se
. To the
be
st
of
our
kn
owl
edg
e, there
a
r
e f
e
w
re
sea
r
che
s
o
n
joint
sch
edulin
g of p
o
s
t-ea
rthq
ua
ke
roa
d
rep
a
ir
a
nd
relief di
strib
u
tion. Yan an
d
Shih presen
t the first
si
g
n
ificant resea
r
ch
that directly targets thi
s
issue [2]. Th
ey establi
s
h
a multi-o
b
je
ctive mi
xed-i
n
teger
mod
e
l
of time-spa
ce n
e
two
r
k to
minimize the
time nece
s
sary for both
road
rep
a
ir a
nd relief di
stribution in 20
09. A heuri
s
tic
algorith
m
wit
h
Cplex i
s
d
e
velope
d for solving
su
ch model
s to
limit the sol
u
tion time in
a
rea
s
on
able
a
nd practi
cal range. L
a
ter i
n
201
2
and
2014, the
op
timal sched
ul
ing of logi
stical
sup
port fo
r e
m
erg
e
n
c
y ro
adway re
pair
work i
s
fu
rthe
r
stu
d
ied as a
su
ppl
e
m
ent
for the
previ
ous
research [3],[4]. However, serious limitations st
ill
exist in these models
due to
some ov
er
ideali
s
tic a
s
sumption
s. Th
e numb
e
r of
damag
ed p
o
ints on the
sa
me roa
d
seg
m
ent is limite
d
to
no more tha
n
two while t
h
ree o
r
more may occu
r in real ca
se
s, esp
e
ci
ally on a twist long
mountain
ro
ad. Th
e im
p
a
ct of
po
st-earthq
u
a
k
e
bad
we
ather on
re
pair
efficien
cy is not
con
s
id
ere
d
, whi
c
h may greatly influence road
rep
a
ir
and reli
ef dist
ribution
sche
dule
s
.
Therefore, thi
s
p
ape
r aim
s
to build
a m
o
del for joint
sche
duling
of
post-ea
rthqu
ake
ro
ad
repai
r and
rel
i
ef distributio
n to optimize
the effi
ciency of life-saving comm
odity delivery, taking
weath
e
r
relat
ed fa
ctors a
n
d
dem
and
urgent level
s
in
to co
nsid
eration. A Heuri
s
t
i
c alg
o
rithm
i
s
develop
ed to
solve the mo
del in a rea
s
o
nable
sho
r
t time for p
r
a
c
tical use.
Nume
rical te
sts
wit
h
a
ca
se of 200
8 Wen
c
h
uan E
a
rthqu
ake is
co
n
d
u
c
ted to validate its efficien
cy.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
An Ant Colony-Based Heuristic Algorithm
for
Joint Scheduli
ng of Post-Earthquake .... (Bei Xu)
633
2. Model and
Method
2.1. Time-sp
ace Net
w
o
r
k
Model
To model the
reali
s
tic p
r
obl
em, some a
s
sumptio
n
s a
r
e made a
s
be
low.
a) A short
-
te
rm re
pai
r an
d relief di
stri
bution pl
an i
s
con
s
ide
r
ed,
whi
c
h requi
res for
a
quick an
d reli
able pla
n
on the main pu
rp
ose of di
strib
u
ting relief m
a
terial
s to all benefi
c
iari
es.
b) Ba
d
weat
her re
du
ce
s
the repai
r
work e
ffici
en
cy of d
a
mag
e
d
point
s by
d
i
fferent
degree
s. Two types
of d
a
mage
d p
o
in
ts are
con
s
id
ered:
we
athe
r sen
s
itive (fl
oode
d by q
u
a
ke
lake, bu
ried b
y
landslid
es) and in
sen
s
itive (blo
ck
ed by
rocks, destro
y
ed by cru
s
ta
l deformatio
n
)
.
The efficien
cy decay rate
of either type is given a
c
cording to histo
r
i
c
al expe
rien
ce.
c) All the geo
grap
hic a
nd o
peratio
n information is kno
w
n.
d) Wo
rk team
s do not nee
d to return to
their work st
ations. The
rescue ma
chi
nery, fuel
and othe
r re
source
s will be
suppli
ed to the wo
rk tea
m
s by sup
port
units.
e) Only com
m
odity flows
are con
s
ide
r
e
d
in the relief distrib
u
tion n
e
twork.
f) Every damaged poi
nt can be rep
a
ired by
no more than on
e work team. All work
teams a
r
e a
s
sume
d to be equivalent in
terms of repai
r efficien
cy.
g)
M
u
ltiple d
a
mage
d
p
o
in
ts
(>2
)
a
r
e
allowed on
t
he sam
e
se
gment. Dam
age
s
at
intersectio
n
s
are al
so con
s
idere
d
.
h) To sim
p
lify the distributi
on model, rel
i
ef ma
terials l
i
ke cloth
e
s,
water, food,
medici
ne
and tents a
r
e
all packe
d an
d cal
c
ulate
d
as eq
uivalent
relief units.
i) A minim
u
m
perce
ntage
of ea
ch d
e
m
and p
o
int’s o
v
erall d
e
man
d
is
co
nsi
dered whe
n
allocating co
mmoditie
s
in the ca
se of supply sh
ortag
e
.
Firstly, two
simila
r net
works
are
e
s
tab
lished
fo
r road
re
pai
r and relief
di
stributio
n
respe
c
tively in Figure 1
and Fig
u
re
2. Ev
ery node in the time-spa
ce n
e
t
works
ha
s dual
attributes. Th
e hori
z
ontal
axis re
pre
s
e
n
ts its s
pace
attribute as a location li
ke work stati
on,
intersectio
n
, damag
ed poi
nt,
sup
p
ly
ce
nter or dem
a
nd p
o
int. Th
e
vertical
axis repre
s
e
n
ts it
s
time
attribute of th
e lo
cation’
s
state at a
sp
eci
f
ic mo
m
ent.
Every arc rep
r
esents a
wo
rk team
flow o
r
a
comm
odity flow. Coll
ectio
n
points a
r
e virtual point
s u
s
ed to en
su
re
the flow con
s
ervation.
Figure 1. Roa
d
repai
r time-spa
ce n
e
two
r
k (RRT
N)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 632 – 64
3
634
Figure 2. Reli
ef distributio
n
time-s
pace network
(RDTN)
In this model,
max out-flow of each work stat
ion equ
al
s to its origi
n
numbe
r of available
work tea
m
s.
Max out-flo
w
of each
suppl
y center equ
als to its
origi
n
amou
nt of
available
sup
p
ly.
Max out-flow
and max in-fl
o
w of ea
ch d
a
mage
d point
are both
set to be 1. Max in-flow of ea
ch
deman
d poi
n
t
equal
s to its total am
ou
nt of deman
d
.
Infinit out-flow a
nd in
-flo
w are allo
we
d for
each interse
c
tion and the passa
ble wo
rk teams a
nd
comm
odity are also infinite
on each roa
d
segm
ent. Different a
r
c type
s and thei
r flow ran
ge in bo
th networks a
r
e displayed i
n
Table1.
Table 1. Arc type and flow
rang
e in time-spa
ce n
e
two
r
ks.
Arc T
y
pe
Flow Range
Arc T
y
pe
Flow Range
In RRT
N
In RDT
N
(1) w
o
rk
station-intersection
[0
,
]
i
wt
(1) suppl
y
cent
er
-intersection
[0
,
]
i
(2)
w
o
rk station-
damaged point
[0
,
1
]
(2) suppl
y
cent
er
-demand p
o
int
[0
,
m
i
n
(
,
)
]
ij
(3) intersection-d
a
maged point
[0
,
1
]
(3) intersection-d
e
mand point
[0
,
]
j
(4) intersection-i
n
tersection
[0
,
]
(4)
intersection-i
n
tersection
[0
,
]
(5) dam
aged poi
nt- damage
d poi
nt
[0
,
1
]
(5) holding a
r
c: suppl
y
center
[0
,
]
i
(6) holding a
r
c:
work station
[0
,
]
i
wt
(6) holding a
r
c: intersection
[0
,
]
(7) holding a
r
c: intersection
[0
,
]
(7) holding a
r
c: demand point
[0
,
]
j
(8) holding a
r
c: damaged point
[0
,
1
]
(
8
)
collection ar
c
[0
,
]
(
9
)
collection ar
c
[0
,
]
*
i
wt
is the origin nu
mber of available w
o
rk teams at the
i
th w
o
rk station;
i
is the total
supply
of the
i
th suppl
y
center;
j
is the total demand of the
j
th demand point.
In post-ea
rth
qua
ke
sho
r
t-t
e
rm em
ergen
cy l
ogi
stics, life injury an
d
prop
erty dam
age a
r
e
much m
o
re i
m
porta
nt than the repai
r
and di
stri
buti
on co
st of money. Con
s
ide
r
ing diffe
rent
urge
nt levels of dema
nd
points, a
wei
ghted
su
m
o
f
the arrival
time asso
ciat
ed with
every
deman
d point
in relief distri
bution is
set as the mod
e
l obje
c
tive to minimize.
In modeling,
()
it
rep
r
e
s
ent
s a node in time
-spa
ce n
e
two
r
k whil
e
i
d
eno
te
s
its
sp
ace
attribute and
t
den
otes its time attrib
ute. Arc
()
(
'
)
it
jt
then
de
scribe
s a
wo
rk tea
m
/com
m
odity
movement from the
i
th loc
a
tion at the
t
th time to t
he
j
th loc
a
tion at the
'
t
th time. For
simpli
city, a single
i
repre
s
e
n
ts a location
node at any time in time-space networks.
We can then
fomulate the obje
c
tive function as eq
uati
on (1
).
11
mi
n
:
(
)
,
aT
D
ii
t
it
Zu
e
t
i
M
(1)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
An Ant Colony-Based Heuristic Algorithm
for
Joint Scheduli
ng of Post-Earthquake .... (Bei Xu)
635
whe
r
e
it
e
is a
bi
nary va
riable;
i
u
is the
urg
ent
level of th
e
i
th dem
and
poi
nt;
D
M
is
the
set of all de
mand p
o
ints;
a
is the num
b
e
r of dem
and
point;
T
is the
total time length of time-
s
p
ac
e
ne
tw
ork
.
There are five types of co
nstrai
nts ne
e
d
to be con
s
i
dere
d
in mod
e
ling.
a) Flo
w
Co
nservation
The time-spa
ce net
work
model share
s
the si
mila
r flow con
s
e
r
vation con
s
traints with
other net
wo
rk flow model
s as eq
uation (2) and e
quati
on (3
).
()
()
,
0,
i
RR
S
i
it
j
k
t
NN
V
P
tT
tT
jN
kN
wt
i
W
xx
iI
I
D
(2)
()
()
,
0,
i
DD
c
i
it
j
k
t
NN
V
D
tT
tT
jN
k
N
iS
yy
iI
I
M
(3)
whe
r
e
ij
x
is th
e
flow of
arc
ij
in RRTN
(unit
s
: work
teams
)
;
ij
y
is th
e flo
w
of
arc
ij
in
RDT
N
(units: comm
odity
equival
ents);
D
N
is the
set of all locati
ons in
RDTN;
S
W
is the set of
all work
st
at
ion
s
;
P
D
is th
e set
of all d
a
mage
d poi
nts;
C
S
is the set o
f
all su
pply centers;
N
I
is
the s
e
t of
all intersections;
NV
I
is the set of all virtual interse
c
tion
s.
b) Flo
w
Re
st
r
i
ct
ion
Wo
rk team a
r
c and
commo
dity arc are also
re
stri
cted
by the road n
e
twork a
c
cessablity
and flow u
p
p
e
r bo
und
s a
s
sume
d in Ta
ble 1, in addi
tion to their o
w
n p
r
ope
rtie
s as non
neg
ative
integer, a
s
formula Equatio
n (4)-(6).
0,
R
ij
i
j
ij
x
gm
i
j
A
(4)
0,
D
ij
ij
ij
ys
i
j
A
(5)
,
R
ij
x
Ii
j
A
(6)
whe
r
e
ij
m
is
a bi
nary va
riable
whi
c
h d
enote
s
the
acce
ssi
b
ility of arc
ij
in RRT
N
;
ij
is
a bina
ry
variable
whi
c
h denote
s
the
accessibility of arc
ij
in RDTN;
ij
g
is the flo
w
upp
er b
oun
d of arc
ij
in RRT
N
;
ij
s
is the flow up
per boun
d of
arc
ij
in RDT
N
;
R
A
is
the set of all
arcs i
n
RRT
N;
D
A
is
the set of all arcs in RDT
N
.
To mo
del t
h
e
problem
of
multi dam
age
d poi
nts on
o
ne
seg
m
ent,
a da
mage
d
p
o
int at
a
-way i
n
terse
c
tion i
s
extended
to
virtual dam
age
d
points with
the
same
wo
rklo
ad
and
damag
e type
on the adja
c
ent segm
en
ts and a vi
rt
ual interse
c
ti
on is in
se
rte
d
betwe
en t
w
o
adja
c
ent d
a
m
aged
point
s to cut the
ori
g
inal segme
n
t into seve
ral
sub
-
segm
ent
s with
only o
ne
damag
ed poi
nt.
Equation (7)
and eq
uation
(8) d
e
scribe
the
acce
ssibil
ity updating
method fo
r d
a
mage
d
points o
n
ro
a
d
seg
m
ent; e
quation
(9) a
nd equ
ati
on (10) d
e
scri
be
the acce
ssi
bil
i
ty synchroni
sm
of road seg
m
ents with v
i
rtual dam
ag
ed point
s extended fro
m
the same d
a
m
aged p
o
int
at
intersectio
n
;
equatio
n (11) avoids dam
aged
poi
nt
s
entend
ed fro
m
the
same
dama
ged
p
o
int
being repai
re
d more tha
n
once.
()
(
'
)
(
'
)
''
,,
,
PS
it
j
q
t
i
q
t
j
q
tt
t
t
mx
x
i
j
N
q
D
(7)
()
(
'
)
(
'
)
''
,,
,
PS
it
j
q
t
i
q
t
j
q
tt
tt
x
xi
j
N
q
D
(8)
()
(
'
)
'
(
'
)
'
1'
1'
,{
'
'
}
,
'
,
'
,
,
qq
kk
k
PV
PI
it
j
q
t
i
q
t
j
q
k
q
kt
t
k
t
t
mx
x
i
j
i
j
i
j
N
q
D
q
D
(9)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 632 – 64
3
636
(
)
('
)
'
('
)
'
1'
1'
,{
'
'
}
,
'
,
'
,
,
qq
kk
k
PV
P
I
it
j
q
t
i
q
t
j
q
k
q
kt
t
k
t
t
x
xi
j
i
j
i
j
N
q
D
q
D
(10)
()
1
1,
,
,
w
kk
PV
PI
qt
i
q
k
q
kt
T
x
iN
q
D
q
D
(11)
whe
r
e
q
N
is the set of all adjace
n
t locatio
n
s of the th
damage
d po
int;
PS
D
is the set of all
damag
ed poi
nts on se
gme
n
t;
PI
D
is the set of all damage
d points at intersectio
n
;
PV
q
D
is the set
of virtual damaged p
o
int
s
extended f
r
om the th
damag
ed poi
nt;
q
is the numbe
r of roa
d
segm
ents lin
ked to the interse
c
tion with t
he th damag
ed point.
c) Repai
r
W
o
rk Con
s
trai
nts
Equation
(1
2) en
sures rep
a
ir
wo
rk sta
r
ts o
n
ce a
work team
a
rrive
s at
a d
a
mag
ed p
o
int
and eq
uation
(13
)
req
u
ires
the work tea
m
to leave the damag
ed p
o
int once rep
a
ir wo
rk finish
es.
()
(
(
)
)
()
()
,,
,
q
PS
PV
qt
q
t
f
t
i
q
t
j
qt
q
x
xx
i
j
N
q
D
D
(12)
()
()
()
,,
,
PS
P
V
qt
i
q
t
j
q
q
t
q
x
xx
q
D
D
i
j
N
(13)
whe
r
e
()
q
ft
i
s
the r
e
pa
i
r
ti
me
of th
e
q
th
dama
ged point wh
en
its re
pair work sta
r
ts at
the
t
th
time;
PV
D
is the set of all virtual damage
d po
ints.
Rep
a
ir work
efficien
cy is assume
d to cha
nge
with different wea
t
her conditio
n
s ove
r
time, which
make
s it a time-d
epe
nde
nt factor. It i
s
linea
rly formulated a
s
equatio
n (14
)
for
simpli
city. And the
repai
r
time is
determined
by th
e time a
s
so
ciated with
th
e sta
r
t no
de
as
equatio
n (15
)
.
0,
(
)
(
)
,
(1
)
,
PW
tP
S
P
V
ts
s
q
qq
t
i
f
q
D
and
bw
bw
Eq
D
D
E
b
w
o
ther
w
i
se
(14)
()
1
(
)
()
m
i
n
(
)
|
,
,
tf
t
t
f
t
k
k
PS
PV
qq
q
q
kt
kt
ft
f
t
E
W
L
E
q
D
D
k
I
(15)
whe
r
e
s
q
E
is the repai
r efficie
n
cy of the th
damage
d po
int in good weather
con
d
ition;
t
q
E
is the
repai
r effici
en
cy of the
q
th d
a
mage
d p
o
int
at the
t
th time after earthquake;
PW
D
is th
e set of all
weath
e
r
sen
s
itive damage
d points;
t
bw
is the predi
cted
bad w
eathe
r i
ndex at the
t
t
h
time after
earthq
u
a
k
e;
s
bw
is the safe threshold
of ba
d weath
e
r in
dex;
q
is the repair
efficien
cy decay
para
m
eter of the
q
th dam
ag
ed poi
nt,
[0
,
1
]
q
;
q
WL
is the total wo
rkload of the
q
th damag
ed
point.
Equation
(16
)
en
su
re
s tha
t
a dama
ged
point
coul
d
be repai
red
by no mo
re t
han o
n
e
work team a
n
d
allows re
pai
ring only som
e
of the dama
ged poi
nts.
()
1,
iN
q
PS
P
V
qt
i
tT
xq
D
D
(16)
(d) Relief
Di
st
ribution Con
s
traints
To avoid
seri
ous in
suffi
cie
n
cy, the su
m
of all comm
o
d
ity arc flo
w
s
to each dem
a
nd point
sho
u
ld not be
less tha
n
the
minimum pe
rcenta
ge of its demand, a
s
formul
ated in
equatio
n (17
)
.
()
,
,
D
D
jj
i
t
j
tT
iN
i
j
yj
M
(17)
whe
r
e
j
is th
e total demand of the
j
th demand poi
nt;
j
is the mi
nimum pe
rce
n
tage of
deman
d re
qui
red for the
j
th deman
d point
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
An Ant Colony-Based Heuristic
Algorithm
for Joint Scheduli
ng of Post-Earthquake .... (Bei Xu)
637
Equation (18
)
ensures th
at positive collect
io
n arcs are allo
wed
only if the
minimum
requi
re
d dem
and of a dem
and poi
nt is met and equ
a
t
ion (19
)
re
co
rds the
dema
nd met time.
('
)
(
'
)
('
)
''
1
'
,,
,
()
,(
)
(
)
0,
,
ii
DD
D
k
i
t
k
ti
i
k
ti
i
tt
t
t
tt
k
N
ki
k
N
ki
k
N
ki
it
j
DD
C
P
yi
f
y
a
n
d
y
y
oth
e
r
w
i
s
e
iM
j
N
(18
)
()
,,
D
DCP
it
i
t
j
Me
y
i
M
j
N
(19)
whe
r
e
M
is a very larg
e po
si
tive number;
DCP
N
is the set of collectio
n point
in RDT
N.
Equation (20) ensu
r
e
s
that no more
co
mmodity
is d
e
livered to a
deman
d point
after its
minimum de
mand is m
e
t.
('
)
('
)
('
)
([
0
.
5
]
1
)
,
,
,
i
it
j
D
D
DCP
ktt
it
j
y
y
M
k
N
iM
jN
yh
(20)
whe
r
e
h
is a very small p
o
si
tive number.
(e)
Fini
shi
ng Con
s
trai
nts
Equation (21
)
clea
rs
all the
arc flo
w
s in
RRT
N a
nd
RDTN
after the
minimum d
e
m
and of
all deman
d p
o
ints are met, which mean
s the repai
r an
d the distrib
u
tion wo
rk a
r
e
all finishe
d
.
1
(m
a
x
{
}
)
(
m
a
x
{
}
)
'
'1
1
([
0
.
5
]
1
)
,
'
,/
,
kk
a
k
T
k
ij
t
t
ij
t
t
k
k
t
a
t
k
k
RD
D
t
x
yM
t
e
t
th
ij
N
N
k
M
(21)
2.2. Ant Colon
y
-based He
uristic Algor
ithm
The time
-sp
a
ce
net
work model
is formul
ated a
s
a mixed
-
int
eger multi-co
mmodity
netwo
rk
flow probl
em,
whi
c
h
i
s
cha
r
a
c
terized as NP
-ha
r
d. It is di
fficult to opti
m
ally solve i
n
a
limited time f
o
r la
rg
e p
r
obl
ems. T
h
e
r
efo
r
e,
we
devel
o
p
a hybrid
glo
bal sea
r
ch Heuri
s
tic algo
ri
thm
to efficiently solve th
e
probl
em by
applying
th
e
phe
romo
ne
idea
of an
t colony
system
algorith
m.The
algorithm fra
m
ewo
r
k is sh
own in Fig
u
re
3.
Initial and fea
s
ible
solution
m
e
thod
The pro
c
e
s
s to gene
rate a feasibl
e
soluti
on is frame
d
in Figure 4. Fi
rstly, a work team is
rand
omly ch
ose
n
to ma
ke an a
c
tion
deci
s
io
n at the be
ginnin
g
of a time u
n
it that whet
her it
woul
d
stay still, travel to
an a
d
ja
cent
inters
ectio
n
or
start
to
repair a
dam
aged
poi
nt. Th
e
deci
s
io
n ma
ki
ng p
r
o
c
e
s
s fo
llows a
pseu
do-ran
dom
proportio
nal
rul
e
dete
r
mine
d
by phe
rom
o
ne
[5-7], whi
c
h
is form
ulated
in equ
ation
(22
)
.To red
u
ce th
e com
puting
scale,
state
che
c
k is
con
d
u
c
ted in
advan
ce that
only wo
rk tea
m
s who fini
sh
their previou
s
travelin
g or
repai
rin
g
wo
rk
have to do the deci
s
io
n makin
g
pro
c
e
s
s.
()
(,
)
,(
)
(,
)
(,
)
0,
uJ
i
pi
j
j
Ji
pi
u
Pi
j
other
w
i
se
(22)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 632 – 64
3
638
whe
r
e
(,
)
Pi
j
is the proba
bility with which a work team
cho
o
se
s to move from node
i
to node
j
;
(,
)
p
ij
is the phe
romone val
ue
from no
de
i
to node
j
;
()
Ji
is the set of no
de
s that ca
n be
visited from n
ode
i
.
Figure 3. Fra
m
ewo
r
k of the hybrid glo
b
a
l sea
r
ch He
uristi
c algo
rit
h
m
After all the work team
states an
d
ac
tion are determi
ned,
the road n
e
twork is
dynamically u
pdated
a
c
cordingly [8] to
check th
e rea
c
ha
bility of e
a
ch
dem
and
point
whe
n
n
e
xt
time unit start
s
. The de
cid
e
-
ch
eck p
r
o
c
e
ss i
s
re
peate
d
until each d
e
mand
point i
s
re
achable f
o
r
at least one
supply ce
nter.
Then the e
a
rl
iest co
mmodi
ty arrival time from ea
ch supply ce
nter t
o
its re
achabl
e
dema
nd p
o
i
n
ts is obtai
ne
d with th
e Dij
kst
ra Algo
rith
m by cal
c
ul
ating an
d tra
c
i
ng
the sh
orte
st p
a
th ba
sed o
n
the cu
rrent ro
ad net
work [9
, 10]. The fina
l step to g
ene
rate a fea
s
ibl
e
solutio
n
for t
he o
r
igin
mo
del is to solve the
comm
o
d
ity allocatio
n
model fo
rmu
l
ated in Eq
ua
tion
(23
)
-(28
), whi
c
h can be
efficiently solve
d
with Cple
x.
Note that the
feasibl
e
sol
u
tion of allocation
model may b
e
absent be
cause of the p
oor rea
c
ha
b
ili
ty of some de
mand poi
nts.
In that case, th
e
deci
de-ch
eck pro
c
e
s
s of work team
cont
inue
s so a
s
t
o
ma
ke d
e
ma
nd poi
nts
rea
c
ha
ble fo
r mo
re
sup
p
ly cente
r
s until the all
o
catio
n
mod
e
l
yields fo
r a
feasibl
e
sol
u
tion (u
su
ally the optimal on
e)
with Cpl
e
x.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
An Ant Colony-Based Heuristic
Algorithm
for Joint Scheduli
ng of Post-Earthquake .... (Bei Xu)
639
Figure 4. Fra
m
ewo
r
k of the feasibl
e
sol
u
tion method
1
mi
n
:
a
ii
i
Zu
T
(23)
Subject to
1
a
b
aa
k
a
k
s
(24)
1
0
a
bk
b
k
s
(25)
12
m
a
x
,
,
...,
aa
a
b
a
Tt
t
t
(26)
[0
.
5
]
ba
ba
b
a
ba
s
te
t
sh
(27)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 632 – 64
3
640
0
ba
s
(28)
whe
r
e
a
T
is th
e
time wh
en th
e minimu
m d
e
mand
pe
rce
n
tage of
a
th d
e
mand
point i
s
met;
ba
t
is
the arrival tim
e
of comm
odi
ties from
b
th supply ce
nter t
o
a
th deman
d point;
ba
et
is the earliest
arrival time from
b
th supply
cente
r
to
a
th d
e
mand
point
cal
c
ulate
d
wit
h
Dij
kst
ra Alg
o
rithm;
ba
s
is the total a
m
ount of co
mmodity allo
cated to
a
th
demand point from
b
th su
ppl
y center;
a
u
is
the urgent lev
e
l of
a
th dem
a
nd poi
nt;
a
is th
e minimum
p
e
rcentag
e of
deman
d requ
ired fo
r the
a
th deman
d p
o
int;
a
is the to
tal deman
d o
f
a
th demand
point;
b
is the t
o
tal su
pply of
b
th
s
u
pp
ly c
e
n
t
er;
b
is the total numbe
r of sup
p
ly center.
Con
s
id
erin
g the case that
a later
rep
a
ired dam
age
d
point ne
ar to
a dema
nd p
o
i
nt may
improve
the
earlie
st a
rriva
l time fro
m
a
su
pply
cente
r
, a l
o
cal
sea
r
ch
meth
od i
s
a
pplie
d to f
i
n
d
possibl
e b
e
tter
sol
u
tions b
a
se
d o
n
the
o
b
tained
fea
s
i
b
le solutio
n
. The de
cide
-check process
and
earlie
st arrival time calcul
ation are rep
eated for an
other
l
time u
n
its. In this period, on
ce a
n
earlie
st arriva
l time is short
ened, the allo
cati
on mo
del update
s
its solution. The
optimal sol
u
tion
is repl
aced b
y
the new one whe
n
mo
del obje
c
tive gets improv
ed. The ran
g
e
of local se
arch
method is d
e
termin
ed by the value of
l
.
Combi
n
ing th
e work team
paths, comm
odity paths a
nd comm
odit
y
allocation, we finally
obtain
a fea
s
i
b
le
solution
for the
o
r
igina
l
sche
duling
probl
em. Spe
c
ifically, to im
prove th
e gl
o
bal
s
e
ar
ch
e
ffic
i
en
c
y
, in
itia
l p
h
e
r
o
m
o
n
e
s
a
n
d
s
o
lu
tio
n
u
p
p
e
r
bo
u
n
d
a
r
e
s
e
t b
y
g
ene
r
a
tin
g
a
g
ood
initial sol
u
tion. The initial
solution m
e
thod follows
th
e
feasibl
e
soluti
on meth
od e
x
cept that
wo
rk
teams a
r
e al
ways a
s
sign
e
d
to their ne
are
s
t
dama
g
ed point
whe
n
maki
ng a
c
tion de
cisi
on
s. Its
result p
r
ovid
es
a time l
e
ngth limit fo
r the
repai
r work
beyo
nd whi
c
h
th
e so
lution can
no
t
be
improve
d
a
n
d
a n
e
w iterati
on
sho
u
ld
be
sta
r
ted
to
fa
stern
the
sea
r
chi
ng
sp
eed.
And
of course,
the time length limit is upda
ted with
the improvem
ent of optimal sol
u
tions.
Pherom
one u
pdate rul
e
s
A local p
h
e
r
o
m
one u
pdate
rule i
s
ap
plie
d in the
work
team de
cisi
o
n
maki
ng p
r
o
c
e
ss
as
equatio
n (2
9
)
. It cuts
do
wn the
prob
ability
of pacing up
and
down bet
we
en two
point
s by
punitively red
u
cin
g
the phe
romo
ne of the turn ba
ck
way of a work team tempo
r
a
r
ily.
,,
,
[
0
,
1
]
pj
i
p
j
i
(29)
whe
r
e
(,
)
p
ji
is the
phe
romo
ne
value from
n
ode
j
to
n
o
de
i
at the de
ci
sion mom
ent
whe
n
a
work team fro
m
node
i
arrives at nod
e
j
;
is the phe
rom
one de
cay pa
ramete
r.
On the
oth
e
r
h
and,
phe
romone
s are
upd
ated
gl
obally eve
r
ytime
whe
n
a
feasi
b
le
solutio
n
is fo
und. Equ
a
tio
n
(3
0) i
s
to
gi
ve highe
r a
m
ounts
of ph
eromone
to a
r
cs bel
ongi
ng t
o
the
best solution
in every iterat
ion. Equation
(31) i
s
to de
cre
a
se the ph
erom
one leve
l for the arcs
in
inferio
r
sol
u
tions. Equatio
n
(32) i
s
used to set the initial pheromo
n
e
values.
1
,,
1
bes
t
pij
p
ij
Z
(30)
,,
1
0
pij
p
ij
p
(31)
0
0
1
p
nZ
(32)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
An Ant Colony-Based Heuristic
Algorithm
for Joint Scheduli
ng of Post-Earthquake .... (Bei Xu)
641
whe
r
e
and
are the
phe
ro
mone d
e
cay para
m
eters;
bes
t
Z
and
0
Z
is the o
b
jective valu
e of
the current b
e
st
solutio
n
a
nd the i
n
itial
solutio
n
, re
sp
ectively;
n
is th
e total nu
mb
er of
nod
es i
n
the RRTN;
0
p
is the initial pheromone level.
Stopping crite
r
ion
There a
r
e t
w
o sto
ppin
g
criteria to
re
du
ce
com
putati
on time.
TT
is t
o
tal computa
t
ion
time, whi
c
h
reflect
s
th
e
spe
ed
req
u
irement in
e
m
erg
e
n
c
y co
ndition;
TI
is th
e num
be
r of
iteration
s
sin
c
e the la
st o
b
jective valu
e is
upd
ated
without improvement, whi
c
h reflect
s
the
quality requi
rement of solu
tion.
Since
sol
u
tio
n
s m
u
st
be fo
und i
n
a li
mited time i
n
em
erge
nt situ
ations,
TT
is s
e
t
as
the
final stoppin
g
crite
r
ion. Sometimes
whe
n
the solution qualit
y is satisfying enou
gh,
the
comp
utation t
i
me may be far le
ss tha
n
TT
and the alg
o
rithm sho
u
ld stop to give early sol
u
tio
n
and
save m
o
re time. The
r
e
f
ore,
TI
is set a
s
an
ea
rly sto
pping
criterio
n after
whi
c
h
the algo
rithm
stop
s before meeting the fi
nal stop
ping
crite
r
ion.
3. Numberic
al Test
Due to so
me confid
ential issue
s
, the tested
ca
se
s are recon
s
tru
c
ted
based o
n
the fact
s
of Anxian
Co
unty in Sichu
an Province
durin
g the
20
08
Wen
c
h
u
a
n
Earth
qua
ke
. Thre
e
ca
se
s of
defferent
scal
es
are
con
s
id
ered
to te
st t
he al
gorith
m
perfo
rman
ce
again
s
t a
di
re
ct solution
wit
h
Cplex 1
2
.5.
Ca
se A
con
s
i
s
ts
of 14 inte
rse
c
tion
s, 1
6
dama
ged
po
ints, 1
work
station, 2
su
pply
cente
r
s
and
2 dema
nd p
o
i
nts. Ca
se B
con
s
i
s
ts of
2
0
interse
c
tion
s, 26 d
a
mag
ed point
s, 2
work
station, 2
su
pply cente
r
s and
4
de
m
and
point
s.
Ca
se
C con
s
ist
s
of
30
i
n
tersectio
n
s,
36
damag
ed
poi
nts, 3
wo
rk
station, 2
su
pply
centers and
6
dem
and
point
s.T
hese te
sts
a
r
e
perfo
rmed o
n
an Intel Pentium 4 CPU 3.
2GHz with 2
G
B RAM und
er Micro
s
oft Wind
ows 7.
As sh
own in
Table 2, it take
s 53
703.
44s
(ab
out 1
4
.9 hou
rs), 8
1997.0
3
s
(ab
out 22.8
hours) and 1
2966
3.58
s (a
bout 36.0 ho
urs), re
sp
ecti
ve
ly, to find the optimal
so
lutions fo
r tested
ca
se
s dire
ctl
y
with Cplex due to their l
a
rge p
r
o
b
lem
size di
spl
a
yed in Table
3. The He
uri
s
tic
algorith
m
onl
y took 93.68
s an
d 132.7
0
s
to re
ach
or get clo
s
e e
n
ough
(ga
p
wi
thin 5%) to the
optimal soluti
on in
Ca
se A
and
Ca
se B
.
This va
lid
ates the
effecti
v
eness a
nd
efficien
cy of the
Heu
r
isti
c algo
rithm in solving mod
e
ls of
middle/la
rge
scale. The
rel
a
tively larger
gap in Case
C
resulted from
the stopping
criteri
on sett
ings in
Ta
ble
4. The Heuri
s
tic algo
rithm
stoppe
d wh
en
the final stop
ping criterio
n
was met at 180s in
Case C with an
obje
c
tive that still could b
e
improve
d
. Th
erefo
r
e, if all
o
wed,
a bi
gge
r
l
can
be
u
s
ed
to imp
r
ove th
e solution
qu
ality whe
n
the
algorith
m
is a
pplied in very
large
-
scal
e case
s.
Table 2. Te
st result
Cplex 12.5
Heuristic Algorithm
Case A
Number of
Repai
red Dama
ged Po
ints
8
8
Objective 138
138
Gap (
%
)
0.00
0.00
Computation Tim
e
(s)
53703.44
93.68
Number of ite
r
ati
ons
-
81
Case B
Number of
Repai
red Dama
ged Po
ints
17
17
Objective 318
330
Gap (
%
)
0.00
3.77
Computation Tim
e
(s)
81997.03
132.70
Number of ite
r
ati
ons
-
96
Case C
Number of
Repai
red Dama
ged Po
ints
23
25
Objective 732
797
Gap (
%
)
0.00
8.88
Computation Tim
e
(s)
129663.58
180.00
Number of ite
r
ati
ons
-
144
Evaluation Warning : The document was created with Spire.PDF for Python.