TELKOM
NIKA
, Vol. 11, No. 4, April 2013, pp. 1883
~18
8
8
ISSN: 2302-4
046
1883
Re
cei
v
ed
Jan
uary 7, 2013;
Re
vised Feb
r
uary
12, 201
3
;
Accepte
d
Febru
a
ry 24, 2
013
A Novel Discrete Differential Evolution Algorithm
Lingjuan HO
U*
1
, Zhijiang HOU
2
1
School of M
anag
ement, Tianjin Norm
al University, Tianjin 30
038
7, China
2
Libra
r
y, Tian
jin University of Tech
nolog
y, Tianjin 300
387, Chi
na
*Co
rre
sp
ondi
ng autho
r, e-mail: lingjuan
258
@16
3
.co
m
A
b
st
r
a
ct
Aiming
at the
stochastic ve
hi
cle ro
utin
g pro
b
le
ms w
i
th si
mu
ltan
eous
pi
ckups a
nd
de
li
veries,
a
nove
l
discr
ete
differenti
a
l
ev
oluti
on
alg
o
rith
m is
pr
o
pos
e
d
for rout
es o
p
timi
z
a
ti
on. T
h
e al
gorith
m
c
an
directly b
e
us
e
d
for the d
i
scr
ete do
main
by
spec
i
a
l d
e
sig
n
. Co
mp
utatio
nal si
mul
a
tions
and c
o
mpar
is
ons
base
d
o
n
tw
o k
i
nds
of pr
obl
e
m
s
of differ
ent
si
z
e
s of
S
V
RP
SPD ar
e pr
ovid
ed. R
e
sults
de
mo
nstrate th
at
the
prop
osed
al
gor
ithm obta
i
ns
b
e
tter results th
an th
e b
a
sic d
i
fferentia
l
ev
ol
ution
al
gorith
m
and
the
existi
n
g
gen
etic al
gorith
m
.
Ke
y
w
ords
: SVRPSPD, bitw
ise oper
ator, dis
c
rete differenti
a
l evo
l
utio
n al
g
o
rith
m
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
The SVRPSP
D is a va
riant
of the cla
ssi
cal VRP
whi
c
h is often e
n
countered in p
r
acti
ce.
After VRPSPD is
int
r
oduced into the literature
by Min [1], s
o
me sc
holars
contribute
on
the
mathemati
c
al
formulatio
n
and the
sol
u
tion metho
d
s.
In pro
b
lem
s
, su
ch a
s
cap
a
city co
nst
r
ai
nt
and time
windows being taken into
account.
On the other hand,
bec
ause V
R
PSPD has been
proved
to b
e
NP-h
ard, th
e
solutio
n
meth
ods mo
st
ly focu
s o
n
the
he
uristi
cs an
d
meta-h
euri
s
ti
cs.
With the dev
elopme
n
t of compute
r
tech
nology,
a few heuri
s
tics an
d meta-h
eu
ri
stics have b
e
en
us
ed to s
o
lve VRPSPD [2,
3, 4].
To date, most s
t
udies
on
VR
PSPD focus
on the level of det
erminis
t
ic
model.
However,
in many real-worl
d
ap
plica
t
ions,
one
or more
pa
ram
e
ters of VRP
SPD tend to
be sto
c
h
a
sti
c
.
Thus, it is necessary to st
udy the mode
l and the algorithm of stochastic V
R
PSPD.
The diffe
renti
a
l evolutio
n
(DE) alg
o
rith
m is
one
of
the late
st i
n
telligent
opt
imization
algorith
m
s p
r
opo
sed by St
orn a
nd Pri
c
e
[5]. As a
pop
ulation-ba
sed
evoluti
ona
ry algorith
m
, DE
is
origin
ally de
sign
ed for continuo
us op
timiza
tion problem
s whi
c
h use si
mpl
e
mutation and
cro
s
sove
r o
p
e
rato
rs to g
e
nerate
ne
w
candid
a
te
solu
tions, a
nd
ap
plies on
e-to
-one
com
petition
strategy to
select th
e ne
w individ
ual
s. Du
e to
its si
mplicity, effectivene
ss an
d ro
bu
stne
ss,
DE
has be
en
su
ccessfully a
p
p
lied in
solving
continu
o
u
s
p
r
obl
em
s i
n
a va
riety of
fields.
Ho
we
ver,
Owin
g to
con
t
inuou
s n
a
ture of
DE, the
resea
r
ch o
n
DE for
combi
natorial
o
p
timization
i
s
v
e
ry
limited. So, it is urgent to prop
ose a
discrete
differential evol
ution algo
rith
m for spe
c
ifi
c
probl
em
s.
Re
cently, so
me sch
o
lars have d
one
som
e
rese
arche
s
o
n
DE for
co
m
b
inatori
a
l
optimizatio
n probl
em
s [6, 7, 8]. Few stu
d
ies h
a
ve be
en don
e on VRP with DE.
In view of above analysi
s
,
this pape
r fo
cu
se
s on de
signing a n
o
ve
l discrete differential
evolution alg
o
rithm (DDE). In DDE, ind
i
viduals a
r
e repre
s
e
n
ted a
s
discrete cli
ent ordi
nal, a
nd
new m
u
tatio
n
ope
rator i
s
define
d
b
a
se
d on the
definition o
f
new alg
e
b
r
aic
structu
r
es.
Con
s
e
quently
, DDE
ca
n b
e
directly a
p
p
lied to
the
combi
nato
r
ial
optimization
pro
b
lem
wh
ere
chromo
som
e
s are n
a
tural numbe
rs.
The remaini
n
g pap
er i
s
o
r
gani
zed
as fo
llows. In se
cti
on 2 the
sto
c
hasti
c prog
ra
mming
model of SV
RPSPD is
presented. Th
e structure of
DE is given i
n
section
3. In section
4 DDE is
introdu
ce
d co
mpre
hen
sivel
y
. And in section 5, the
computational result
s over di
fferent sizes
of
SVRPSPD are disc
us
sed. Finally, c
o
nc
lus
i
ons
an
d
some s
ugges
tions
for future work
are
summ
ari
z
ed.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 1883 – 1
888
1884
2. Problem Formulation a
nd Preliminaries
SVRPSPD discussed in this
paper can be descri
bed as follows: Given a singl
e depot, a
set of cli
ents whe
r
e e
a
ch
client
simult
aneo
usly ha
s both a deliv
ery dem
and
and a pi
ck-u
p
deman
d and
must be
serv
ed on
ce by o
n
ly one vehi
cle, a homoge
neou
s fleet of vehicle
s
wh
e
r
e
each vehi
cle,
whi
c
h
d
e
livers the
goo
ds
from
the
dep
ot to clients as well a
s
picks up load
s ba
ck
to the dep
ot, has th
e same
cap
a
city an
d
maximum tr
a
v
el time, and
must return t
o
the de
pot if it
can n
o
t satisf
y the demand
s of client
s or
if the maximum travel time excee
d
s.
In detail, we
sup
p
o
s
e th
at:
n
denote
s
the n
u
mb
er of the
cli
ents;
m
den
otes the
maximum available nu
mb
er of vehi
cle
can be u
s
e
d
of the depot(0);
C
d
e
n
o
tes the vehi
cle
cap
a
city; the
delivery d
e
m
and
subj
ects to
the n
o
rmal dist
ributi
on, that is
i
d
)
,
(
2
i
i
N
; the
pick-u
p dem
a
nd is d
e
termi
nate, assumi
ng
i
i
r
p
. We also
assume th
e travel time su
bject
s
to
the norm
a
l di
stributio
n, tha
t
is
t
ijk
)
,
(
2
ij
ij
ij
v
d
N
, sup
pose that the
servi
c
e time
for every cli
e
n
t
is pro
p
o
r
tiona
l to delivery demand of it, that is
i
i
d
T
.
B
denotes the maxi
mum travel time. The
con
s
trai
nts of
capa
city and
maximum tra
v
el time
coul
d be un
sub
s
t
antiated, but the probability
of
con
s
trai
nts
satisfactio
n
is more than
the given
co
nfiden
ce lev
e
l. Mean
whil
e,
denote
s
th
e
percenta
g
e
s
allowed for o
v
erload;
)
1
(
and
)
1
(
denote the con
f
idence level.
The problem
formulatio
n is as follows:
Let:
otherwise
j
i
arc
uses
k
vehicle
if
x
ijk
)
,
(
0
1
and
otherwise
i
client
visits
k
vehicle
if
z
ik
0
1
m
k
n
i
n
j
ijk
ij
x
d
z
Minimize
10
0
(1)
n
i
z
to
Subject
m
k
ik
,
,
2
,
1
1
1
(2)
m
k
x
n
j
jk
,
,
2
,
1
1
1
0
(3)
m
k
x
n
i
k
i
,
,
2
,
1
1
1
0
(4)
m
k
n
l
x
x
n
j
ljk
n
i
ilk
,
,
2
,
1
;
,
,
2
,
1
0
0
0
(5)
m
k
n
C
z
d
z
p
P
ik
n
i
i
ik
i
i
,
,
2
,
1
;
,
,
1
,
0
0
))
1
(
(
1
0
(6)
m
k
n
C
z
d
z
p
C
P
ik
n
i
i
ik
i
i
,
,
2
,
1
;
,
,
1
,
0
))
1
(
(
1
0
(7)
m
k
B
z
T
x
t
P
n
i
n
j
n
i
ik
i
ijk
ijk
,
,
2
,
1
1
)
(
00
1
(8)
m
k
V
V
V
for
V
x
k
V
iV
j
k
k
ijk
kk
,
,
2
,
1
,
2
,
}
0
{
1
(9)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Novel
Discrete Differenti
a
l Evolution A
l
gorithm
(Ling
j
uan HOU)
1885
The
obje
c
tive functio
n
(1)
minimizes the
total di
stan
ce. Co
nst
r
aint
s
(2) en
su
re
that eve
r
y
client is
se
rve
d
by exactly o
ne
vehicl
e. Constraints
(3
-4) en
su
re tha
t
maximum a
v
ailable nu
m
ber
of vehicle i
s
not exce
ede
d. Con
s
trai
nts (5
) g
uarant
ee that a ve
hicl
e
exits th
e clie
nt it enters.
Constrai
nts (6-7)
represent that a
small
num
ber of
overload is all
o
wable,
but the probability of
overloa
d
i
s
le
ss than
. Con
s
traint
s
(8) h
andle
maxim
u
m allo
wa
ble
travel time,
whi
c
h all
o
w
a
certai
n amou
nt of overtime, but the
probability of overtime is less than
. Const
r
aints (9) a
r
e
sub
-
tou
r
elimi
nation con
s
traints.
Note that
wh
en
0
fixed in co
nstrai
nts
(6
-7
), this mo
del i
s
tra
n
sfo
r
me
d into the m
o
del
of
SVRP sub
j
ect
to
the same co
nstrai
nts. When
n
fixed in
con
s
tra
i
nts
(6-7), thi
s
m
odel
i
s
transfo
rme
d
i
n
to the mod
e
l
of SVRP wi
th only picku
p
s. When
0
fixed and
1
m
, that is the
depot have o
n
ly one vehicl
e, the model is
tran
sformed
into the model of TSP.
3. Diffe
ren
t
ia
l Ev
o
l
ution Algorithm
DE is an im
proved ve
rsi
on of GA which
b
e
lon
g
s to the evolutionary opti
m
ization
method, wh
e
r
e ch
rom
o
so
mes a
r
e floa
ting-poi
nt nu
mbers. The
prin
ciple for
DE is de
scri
be
d
briefly as
follows
.
(1) Population Initialization
DE is co
nsi
d
ered
NP
d
-di
m
ensi
onal ve
ctors a
s
the initial populati
on to sea
r
ch the best
solutio
n
.
We
can
denot
e
the
group
as
follows:
}
,
,
1
,
0
,
,
,
2
,
1
),
,
,
,
(
|
{
max
,
,
2
,
1
,
,
G
G
NP
i
x
x
x
X
X
G
di
G
i
G
i
G
i
G
i
, where
G
ma
x
denote
s
t
he maximu
m
evolution ge
n
e
ration.
Clea
rly
,
NP
i
X
i
,
,
2
,
1
,
0
,
denot
e the initial
popul
ation. G
ener
ally, the
initial pop
ulat
ion
can b
e
ch
ose
n
rand
omly from the ran
g
e
of variables.
(2) Mut
a
tion Operator
The purpo
se
of mutation is to generate t
he mutant vector i
n
orde
r to enha
nce
pertu
rbatio
n t
o
the ta
rg
et vector to
avoid
prem
atu
r
e
converg
e
n
c
e t
o
a
non
-glo
b
a
l lo
cal
optim
um.
For
ea
ch t
a
rget
vecto
r
NP
i
X
G
i
,
,
2
,
1
,
,
, the m
u
tant vecto
r
ca
n b
e
cre
a
ted
a
s
:
)
(
,
3
,
2
,
1
1
,
G
r
G
r
G
r
G
i
X
X
F
X
V
, whe
r
e th
e i
ndexe
s
r
1
, r
2
, r
3
represent
the rand
om
and m
u
tually
different integers
generated within [1,
NP
] and also di
fferent from
i
.
F
is a scalin
g factor, whi
c
h is
a real cons
tant within [0,2].
(3) Cro
s
sove
r
Operat
or
The pu
rpo
s
e
of cro
s
sover
is to increa
se
t
he potential diversity of the evolution
grou
p.
Based o
n
the
mutant vecto
r
, the trial vector
)
,
,
,
(
1
,
1
,
2
1
,
1
1
,
G
di
G
i
G
i
G
i
u
u
u
U
can b
e
co
nstru
c
ted
as
follows
:
otherwise
x
j
i
rand
or
CR
rand
v
u
G
ji
G
ji
G
ji
,
1
,
1
,
)
(
)
1
,
0
(
(10
)
In formula
(1
0),
ra
nd
(0,1)
is a rand
om
value within [
0
,1];
rand
(
i
) i
s
a rand
omly cho
s
e
n
index from
}
,
,
2
,
1
{
d
.
G
is th
e n
u
mbe
r
of
cu
rre
nt gen
eration, and
CR
is
the
cr
oss
o
ver
probability within [0,1].
(4)
Sele
ction Operator
Based
on
the
estimatio
n
of
the g
r
ou
p, th
e se
le
ction o
perato
r
executes
acco
rdin
g to the
fitness val
ue
of the target
vector a
nd it
s corr
e
s
po
ndi
ng trial ve
cto
r
. The p
opul
a
t
ion of the ne
xt
gene
ration i
s
obtaine
d by adopting the fo
llowing
gre
e
d
y
selectio
n cri
t
erion:
otherwise
X
X
f
U
f
U
X
G
i
G
i
G
i
G
i
G
i
,
,
1
,
1
,
1
,
)
(
)
(
(11
)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 1883 – 1
888
1886
It is obvious from the abov
e descri
p
tion that
the traditional DE algo
rithm is desig
ned for
the contin
uou
s optimi
z
atio
n pro
b
lem
s
, not suitabl
e
for ap
plication
to comb
inatorial optimization
probl
em
s.
4. Discre
t
e Differe
ntial Ev
olution Algo
rithm
This pa
per p
r
opo
se
s a
n
o
vel DDE fo
r SVRP. T
h
e e
s
sential
differen
c
e
is mutation
operator with
DE.
4.1. Repre
s
e
n
ta
tion and
Fitnes
s Fun
ction
In this pap
er,
we ad
opt the client
-ordin
al-ba
s
e
d
re
prese
n
tation which h
a
s
bee
n widely
use
d
in
the li
terature fo
r V
R
P. The
fea
s
ible routing
can b
e
d
e
cod
ed to th
e
ch
romosome
(
i
11
,
i
12
,..
.,
i
1s
; 0,
i
21
,
i
22
,
...
,
i
2
t
;..
.; 0,
i
m
1
,
i
m
2
,
...,
i
mw
) with the le
ngth
n+m
-
1.
In DE, the fi
tness functio
n
is used to
evaluate the adapta
b
ility to environment of
chromosom
e
.First of all, we will deal
with the
constraint
s (6-8), let them transform into thei
r
equivalent
re
pre
s
entatio
ns. We
can
hav
e the
re
sult
s
that co
nst
r
ain
t
s (6-8
)
are
e
quivalent to
the
following formula, res
p
ec
t
i
vely [9]:
m
k
n
C
z
z
p
z
ik
n
i
i
ik
i
i
n
i
ik
i
,
,
2
,
1
;
,
,
1
,
0
)
1
(
1
0
1
2
1
，
(12
)
m
k
n
C
z
z
p
z
ik
n
i
i
ik
i
i
n
i
ik
i
,
,
2
,
1
;
,
,
1
,
0
)
1
(
)
1
(
1
0
1
2
1
，
(13
)
B
1
00
1
n
1
2
2
2
00
1
ij
ij
n
i
n
j
ijk
n
i
ik
i
i
i
ik
ij
n
i
n
j
ijk
v
d
x
z
z
x
）
（
(14
)
In this pap
er,
we u
s
e fo
rm
ula
l
l
z
bz
f
'
as the fitness fun
c
tion
, where
f
l
is t
he fitness
value of th
e
chrom
o
some
l
,
b
is
a g
i
ve
n
c
o
ns
ta
n
t,
z'
i
s
the b
e
st
dist
ribution
co
sts
corre
s
p
ondin
g
to the chromo
some in initial
populatio
n,
z
l
is the distrib
u
tion co
sts of
the chromo
some
l
.
4.2. Mutation
Opera
t
or
In DDE, a
si
mple m
u
tatio
n
op
erato
r
i
s
de
sign
ed i
n
orde
r to
ge
n
e
rate
discret
e value
s
.
Before d
e
si
g
n
ing the
ne
w mutation o
p
e
rato
r, first of
all, we i
n
tro
duce two
bit
w
ise op
erato
r
s of
the comp
uter langua
ge to
define the new al
geb
ra
i
c
structu
r
e o
n
the set of vectors who
s
e
element
s are
natural n
u
m
bers. We u
s
e
N
d
for the
d
-dimen
sion ve
ctor
set and
define a bin
a
r
y
operator fro
m
d
d
N
N
to
d
N
.
Definition 1:
Assumi
ng
d
d
N
a
a
a
A
)
,
,
,
(
2
1
,
d
d
N
b
b
b
B
)
,
,
,
(
2
1
, and giving
nume
r
ical co
nstant
)
1
,
0
(
F
, we define operators
as
follows
:
)
&
,
,
&
,
&
(
)
,
&(
:
&
2
2
1
1
d
d
b
a
b
a
b
a
B
A
,
)
|
,
,
|
,
|
(
)
,
(
|
|:
2
2
1
1
d
d
b
a
b
a
b
a
B
A
otherwise
a
a
a
a
a
a
a
F
rand
a
a
a
a
a
a
a
A
F
j
d
j
d
j
d
d
j
j
j
)
,
,
,
,
,
,
,
,
(
)
1
,
0
(
)
,
,
,
,
,
,
,
(
1
1
1
2
1
1
1
1
1
2
whe
r
e
rand
(0,1) is
a random number wit
h
in [0,1],
j
is
a rand
om nat
ural nu
mbe
r
within (1,
d
).
Based o
n
the
above definit
ion, the mutation ope
rato
r can be present
ed as follo
ws:
1
,
,
1
,
0
,
,
,
2
,
1
,
&
|
max
,
3
,
2
,
1
1
,
G
G
NP
i
X
X
F
X
V
G
r
G
r
G
r
G
i
）
（
(15
)
In formula(15
),
G
i
X
,
is the targ
et vector,
G
r
X
,
1
,
G
r
X
,
2
and
G
r
X
,
3
are ve
ctors distin
ct an
d
different of the target vector cho
s
en
rand
omly fro
m
the group.
F
is a mutant scal
e
factor,
belon
ging to the interval [0,
1
]. The abov
e form
ula
co
nsi
s
ts of two
comp
one
nts
and an exa
m
ple
is given in Fig
u
re 1.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Novel
Discrete Differenti
a
l Evolution A
l
gorithm
(Ling
j
uan HOU)
1887
Figure 1. Mutation ope
rato
r: (
a
):
s
e
le
ct
t
he v
e
ct
or
s
X
r1
, X
r2
and X
r3
randomly
, the
n
cal
c
ulate
X
d
=
3
2
&
r
r
X
X
; (
b
): sele
ct u
n
iform num
be
r ran
d
(0,1
) b
e
twee
n (0,1
) and ra
ndo
m numbe
r
j
rando
mly
,
calcul
ate
d
t
X
F
X
for
F
=
0
.5; (
c
): cal
c
ulate
t
r
X
X
V
|
1
.
4.3. Cross
o
v
e
r Opera
t
or
and Selectio
n Opera
t
or
In this paper, acco
rdin
g to formula (1
0),
the trial individual
s are ge
nerate
d
one
by one.
The
sele
ction
is
executed
according
to f
o
rmul
a (11
)
t
hat the
pop
ul
ation of th
e n
e
xt gene
ratio
n
is
prod
uced indi
vidually by using t
he gre
e
d
y
selectio
n cri
t
erion.
4.4. Rev
i
se
Opera
t
or.
We see that the feasibl
e
chrom
o
some
gene
s of
VRP must be different with ea
ch othe
r.
As de
scrib
e
d
in the p
r
evi
ous, ille
gal i
ndividual
s m
a
y be p
r
odu
ced
duri
ng t
he evolutio
n
a
ry
pro
c
e
ss.
So,
an a
u
xiliary o
perato
r
ba
se
d on
inte
g
e
r
o
r
de
r crite
r
ion
(IOR)
i
s
appli
ed
to ame
nd
t
he
infeasi
b
le chromosome
s [1
0].
5. Computati
onal Res
u
lts
and Analy
s
is
To validate t
he effectiven
ess of the
propo
s
ed
DDE
algorith
m
, two kin
d
s
of problem
s of
different
size
s of SVRPSP
D a
r
e
sele
cte
d
, that is
sma
ll-scale
probl
em (3
0
client
s), a
nd m
ediu
m
-
sized proble
m
(50 cli
ents), which a
r
e
solved by
DDE, traditional DE and GA [
3
], resp
ective
ly in
the same
con
d
itions.
The
relative pa
ram
e
ters of
mode
ls a
nd
algo
rit
h
ms in th
e p
a
per are li
sted
in
Table 1.
Table 1. The
Relative Parameters by M
odel
s And Algorithm
s
N K
C
NP
Gm
ax
CR
F
Pc
Pm
r B
）
（
30
8
600
100
200
0.3 0.5 0.855
0.055
0.1
1.8
0.4
30400
0.05
50
15
600
100
200
0.3 0.5 0.855
0.055
0.1
1.8
0.4
30400
0.05
All the algo
rithms i
n
this
pape
r a
r
e im
plemente
d
wi
th C p
r
og
ra
mming la
ngu
age. F
o
r
each in
stan
ce, 1
0
ind
epen
dent
re
plicatio
ns
are condu
cted
to obtain
statisti
cs.
Th
e
comp
utationa
l results a
r
e
sho
w
n in T
a
ble 2, wh
ere
SD den
otes t
he stan
da
rd
deviation of the
distan
ce valu
e, T denote
s
the com
putati
onal time.
Table 2. Average
Re
sults
of
the DDE, DE and GA A
l
gorithm
s
N
DDE DE
GA
Distance
SD T(s)
Distance
SD T(s)
Distance
SD T(s)
30
388.673
44.795
14
424.118
34.330
13.5
462.746
20.701
6.8
50
964.637
95.072
38.7
1107.13
61.566
38.3
1163.115
48.487
18.5
From Ta
ble 2, it
follows
that DDE ca
n
obtain the
better results than DE a
nd GA.
Therefore,
we ca
n con
c
lu
de that DDE
outperfo
rm
s
DE and
GA o
n
the con
s
ide
r
ed
pro
b
lem.
But
the DDE com
putational tim
e
is much lon
ger. Th
i
s
hap
pen
s be
cau
s
e in the pro
c
ess of DDE, the
illegal ch
rom
o
som
e
s a
r
e revised d
u
rin
g
each g
ene
ra
t
i
on, and a
s
the probl
em si
ze increa
se
s, the
numbe
r of a
m
endm
ents i
n
crea
se
s.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 1883 – 1
888
1888
6. Conclusio
n
The aim
of this p
ape
r is t
o
provid
e a
more
reali
s
tic modelin
g ap
proa
ch to V
R
P and a
more a
ppli
c
a
b
le algo
rithm
for solving
it. Thus
, firstly, this p
aper p
r
o
p
o
s
es a sto
c
h
a
s
tic
program
m
ing model for SVRPSPD with uncertain
demand and travel time, and then presents a
novel DDE fo
r ro
uting opti
m
ization. In
DDE, a clie
nt-o
rdinal
-b
ase
d
repre
s
e
n
tation
is appli
ed, a
n
d
novel mutatio
n
ope
rato
r is develope
d for this
re
pre
s
entation. Fu
rtherm
o
re, the
perfo
rman
ce
of
DDE is di
scu
s
sed by num
erical
expe
ri
ments. Simul
a
tion re
sults
and compa
r
i
s
ons d
e
mon
s
t
r
ate
the supe
rio
r
ity of the p
r
op
ose
d
DDE
al
gorithm
in
te
rms of
soluti
on q
uality an
d effectiven
e
ss.
Particul
arly, the new mu
tation operator de
sign
ed
for dire
ct appli
c
ation to combi
nato
r
ial
optimizatio
n probl
em
s is satisfying.
Ackn
o
w
l
e
dg
ements
This work wa
s finan
cially suppo
rted by the Ti
anjin Phi
l
oso
phy Soci
al Scien
c
e Rese
arch
Proje
c
t (No.T
J
GL
12-079
0)
and the Doct
or Fou
ndat
io
n of Tianjin Normal
University Grant
(No.5
2
WW1
1
02).
Referen
ces
[1]
Min H. T
he
multipl
e
v
ehic
l
e ro
uting
pro
b
lem
w
i
th
s
i
multan
eous
d
e
liver
y a
nd p
i
ckup po
ints.
T
r
ansportati
on Rese
arch
A
. 1989; 23A(
5
): 3
77–
38
6.
[2]
F
e
rmín Alfred
o T
ang M
ont
ané. A
tab
u
search
al
gor
ithm for th
e v
ehicl
e r
outi
n
g
pro
b
lem
w
i
t
h
simulta
neo
us p
i
ck-up a
nd d
e
li
ver
y
serv
ice. C
o
m
puters & Op
eratio
ns Rese
a
r
ch. 2006; 3
3
: 595
–6
19.
[3]
CL P
eng,
CH
L
i
an
g. Improve
d
ge
netic
al
gorit
hm fo
r v
ehic
l
e
routin
g pr
ob
le
m
w
i
th s
i
mult
a
neo
us p
i
cku
ps
and d
e
liv
eri
e
s.
Journ
a
l of System Si
mul
a
tion
.
2008; 2
0
: 226
6-22
70.
[4]
K Ganes
h, T
T
Nare
ndra
n
. T
A
ST
E: a t
w
o-
ph
ase h
eur
istic
to
solve
a ro
utin
g pro
b
lem
w
i
th
simulta
neo
u
s
deliv
er
y an
d pi
ck-up.
Int J Adv Manuf T
e
chn
o
l
. 200
8; 37: 1
221
–1
231.
[5]
Storn
R.
Diffe
rentia
l ev
ol
utio
n d
e
sig
n
of a
n
IIR-filter.
Pr
ocee
din
g
s IEE
E
Co
nferenc
e
Evol
ution
a
r
y
Comp
utation, Nag
o
y
a,
Jap
a
n
,
1996: 26
8-27
3.
[6]
On
w
u
b
o
lu
G, Dave
ndra
D.
Sched
uli
ng fl
o
w
sho
p
s
usin
g
differe
ntial
ev
oluti
on
alg
o
rith
m. Europ
e
a
n
Journ
a
l of Ope
r
ation
a
l Res
ear
ch
. 2006; 1
71(
2): 674–
69
2.
[7]
Xi
ao
hui Yu
an,
Anju
n Su, Hao
Nie. Appl
icatio
n of
enha
nce
d
discrete d
i
ffere
ntial ev
oluti
on
appr
oach t
o
unit commitme
n
t probl
em.
Energy Co
nversi
o
n
and Ma
na
ge
me
nt.
2009; 5
0
:
2449–
24
56.
[8]
Quan Ke Pan,
Mehmet F
a
tih T
a
sgetiren. A discrete d
i
ffere
ntial ev
ol
uti
on
alg
o
rithm for the permutati
on
flo
w
s
h
o
p
sche
duli
ng pr
ob
lem
.
Comp
uters & Industria
l Engi
neer
ing
. 2
008;
55: 795
–8
16.
[9]
LJ H
ou, H
Z
h
ou.
Stoc
hastic
veh
i
cle
ro
utin
g pr
obl
e
m
w
i
t
h
u
n
certai
n
de
ma
nd
an
d tra
v
el ti
me a
n
d
simulta
neo
us picku
ps
a
nd deliv
eri
e
s
. T
he 3rd
Intern
ation
a
l J
o
int
Co
nferenc
e o
n
Comp
utation
a
l
Scienc
es an
d Optimizatio
n
, IEEE Press, 2010: 32–
35.
[10]
Cao Erb
ao La
i Ming
yo
ng. T
he open ve
hi
cl
e routin
g prob
lem
w
i
th fuzz
y
de
mands.
Expert System
s wit
h
Appl
icatio
ns
. 2
010; 37: 2
405
–
241
1.
Evaluation Warning : The document was created with Spire.PDF for Python.