TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.6, Jun
e
201
4, pp. 4543 ~ 4
5
4
9
DOI: 10.115
9
1
/telkomni
ka.
v
12i6.539
5
4543
Re
cei
v
ed
De
cem
ber 2
7
, 2013; Re
vi
sed
F
ebruary 25,
2014; Accept
ed March 1
0
, 2014
Study on VRPTW Based on Improved Particle Swarm
Optimization
Wang F
e
i
Schoo
l of Com
puter Scie
nce I
n
stitute, Gansu
Inst
itute of Political Sci
ence a
nd La
w
,
Lan Z
h
o
u
73
00
70, Chi
n
a
email: w
a
ngfe
i
612
8@1
26.co
m
A
b
st
r
a
ct
Vehic
l
e r
outi
n
g
pro
b
le
m w
i
th
time
w
i
nd
ow
s (VRPT
W
) is a
typica
l n
on-d
e
terministic
p
o
l
yno
m
i
a
l
hard (NP-
hard
)
optimi
z
a
t
i
o
n
probl
e
m
. In order to
ov
erco
me PSO
’s slow
astringe an
d pre
m
atu
r
e
conver
genc
e, an
i
m
prov
ed p
a
rticle
sw
ar
m
opti
m
i
z
at
ion
(IPSO) is put for
w
ard.
In the a
l
gorith
m
, it
use
s
the
pop
ulati
on e
n
tropy to makes
a qua
ntitative d
e
scripti
on
ab
ou
t the diversity o
f
t
he popul
atio
n, and ad
aptiv
el
y
adj
usts the cell
ular structure
accord
ing to th
e chan
ge
of p
opu
latio
n
entro
py to have a
n
effective bal
an
c
e
betw
een the lo
cal expl
oitati
on
and t
he gl
oba
l
explor
ation, th
us enh
anc
e
the perfor
m
a
n
ce
of the algorith
m
.
In the pap
er, the alg
o
rith
m w
a
s appl
ie
d to sol
v
e VRPT
W
,
th
e mathe
m
atic
al
mo
del w
a
s est
ablis
he
d an
d th
e
detai
led
i
m
p
l
e
m
e
n
tatio
n
pr
oc
ess of th
e
alg
o
rith
m w
a
s
int
r
oduc
ed. T
h
e
simulati
on
res
u
lts sh
ow
that th
e
alg
o
rith
m has
better opti
m
i
z
a
t
ion cap
a
b
ility than PSO.
Ke
y
w
ords
:
vehicl
e r
outin
g
prob
le
m w
i
th
times w
i
nd
ow
(VRPTW), particle swar
m
optimi
z
a
tion (P
SO),
pop
ulati
on e
n
tropy
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
Vehicle
ro
utin
g problem
wa
s p
r
op
ose
d
b
y
Dant
zi
g Z a
nd Ram
s
er
J
in 195
9 [1], it refers
to
the desi
g
n
of a set of
minimu
m-co
st
vehi
cle
ro
utes, orig
inating and
terminatin
g
a
t
a
distrib
u
tion
center, fo
r
a fl
eet of ve
hicle
s
that
service
s
a
set of
customers
with
certain
dem
an
ds.
Each
custom
er i
s
se
rvice
d
exa
c
tly on
ce, fu
rtherm
o
re, all cu
stomers mu
st be
a
s
sign
ed
to
vehicle
s
which satisfy ce
rt
ain co
nstraint
conditio
n
s.
In our life, ma
ny probl
ems i
n
logisti
cs ve
hicle
can
be
attributed to t
he VRPT
W. Although
the pro
b
lem
has b
een
wid
e
ly applied, it is not
still g
ood solution
s in the theory
field. VRP has
been
proved t
o
be
NP
probl
em, while V
R
PTW in
crea
se the tim
e
co
nstrai
nts on
the b
a
si
c ve
hi
cle
routing p
r
obl
em and its impleme
n
tatio
n
is mo
re
co
mplex than VRP. When
the scale of the
probl
em i
s
small, it is
po
ssible
to get
e
x
act soluti
on,
but it i
s
difficult to get th
e
optimal
soluti
on
for large di
mensi
on p
r
o
b
lems. In re
cent yea
r
s,
GA, ACA an
d other
heu
ristic o
p
timiza
tion
algorith
m
s h
a
ve been ap
plied to solve
the probl
em
s [2-5], but these algo
rith
ms all have long
sea
r
ch time
and e
a
sily fal
l
into local
o
p
timal. There
f
ore, ho
w to
con
s
tru
c
t opti
m
ized
algo
rithm
simple i
n
formation an
d h
i
gh in optimi
z
ing prec
i
s
io
n
enjoys
gre
a
t signifi
can
c
e i
n
solvin
g solve
VRPTW.
Particle
swarm optimizatio
n (PSO) i
s
a
set
of n
e
w i
n
telligent o
p
timization
algo
rithms
whi
c
h i
s
simp
le calculation,
fast
conve
r
g
ence a
nd
ea
sy to implem
e
n
t, etc [6]. Th
e alg
o
rithm
h
a
s
been a
pplied
to VRP [7-8] and a
c
hieve
d
very good re
su
lts, but it exist such pro
b
lems a
s
bei
ng
easy to stag
n
a
te and fall into local optim
um. Ther
efo
r
e, in this pap
er, an ada
ptive particl
e swa
r
m
optimizatio
n
based o
n
po
pulation
e
n
tropy is put fo
rwa
r
d
by ad
aptively adju
s
ting the
cell
ular
stru
cture accordin
g to the cha
nge of po
pulation
e
n
tro
p
y and applie
d to solve VRPTW. The re
sult
of experime
n
ts indi
cate
s that the algor
ith
m
can efficie
n
tly solve the probl
em.
2. Descrip
tio
n
about VRP
T
W and Ma
thematical M
odel
2.1. Descrip
tion about V
R
PTW
The VRPT
W can
be de
scrib
ed a
s
foll
owe
d
：
The
r
e are
a di
stri
bution
cente
r
and
N
cu
stome
r
s, d
i
stributio
n ce
nter ha
s
M
vehicle
s
of
ca
pa
city
Q
,
ij
d
is tran
spo
r
t di
stan
ce from
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4543 – 4
549
4544
cu
st
ome
r
i
t
o
cu
st
ome
r
j
,
v
is the spee
d of
the vehi
cle,
i
g
)
,...,
1
(
N
i
is d
e
man
d
go
ods for
cu
st
ome
r
i
an
d
i
g
is less than
Q
. Each ve
hicl
e ro
ute m
u
st
start a
nd fini
sh at the
sam
e
de
pot,
now find d
r
iving route
s
fro
m
the
cente
r
to ea
ch
c
u
s
t
omer
s
i
te
with the time is
not later than
i
l
)
,...,
1
(
N
i
and meetin
g the followi
ng requireme
nts:
1) Overl
oad i
s
forbid
den.
2) Delive
r
y must be finishe
d
as soon a
s
possibl
e.
3) Suppli
e
s required by ea
ch dem
andi
n
g
site mu
st be delivere
d
.
4) the total co
st must be at
minimum.
Supplem
enta
r
y conditio
n
s:
1) Adeq
uate
vehicle
s
are available in th
e
distrib
u
tion
cente
r
, and th
e cap
a
city of each
has b
een giv
en;
2) The
r
e is o
n
ly one distri
bution cent
er
and its lo
catio
n
has b
een gi
ven;
3) The
r
e is o
n
ly one type vehicle in the
cent
e
r
. Each
custo
m
er
site is se
rved b
y
only
one vehi
cle. Every site mu
st be
cove
red
by the driving route;
4) the gross d
e
mand of ea
ch deman
ding
si
te alon
g the
route cannot
surpa
ss the
cap
a
city of the vehicle;
5) In ord
e
r to
simplify the case, only the
time con
s
um
ed on ro
ad wi
ll be con
s
id
ered,
irres
p
ec
tive of the s
e
rvice time.
2.2. Mathem
atic Mode
Here is the m
a
thematic m
o
de built ac
co
rding to the de
scription a
b
o
v
e:
(1)---obj
ectiv
e
function (2
)-
(
9
)-
--
cons
traint c
o
nditions
f
=min
ijk
N
i
N
j
M
k
ij
x
d
00
0
(1)
M
y
M
k
k
1
0
(2)
Q
y
g
ik
N
i
i
1
，
}
,...,
1
{
M
k
(3)
M
k
ik
y
1
1
，
}
,...,
1
{
N
i
(4)
jk
N
i
ijk
y
x
0
，
}
,...,
1
{
N
j
，
}
,...,
1
{
M
k
(5)
ik
N
j
ijk
y
x
0
，
}
,...,
1
{
N
i
，
}
,...,
1
{
M
k
(6)
jik
t
=
v
d
ij
，
}
,...,
1
{
,
N
j
i
(7)
,
ijk
jik
jk
ik
x
t
t
t
}
,...,
1
{
,
N
j
i
，
}
,...,
1
{
M
k
(8)
i
ik
i
b
t
a
，
}
,...,
1
{
,
N
j
i
，
}
,...,
1
{
M
k
(9)
In the mo
del
, formulation
(1
) is the ta
rget fu
n
c
tion;
formulatio
n
(2) limit that
the total
numbe
r
of ve
hicle
s
dispatched f
r
om
dep
ot doe
s not
e
x
ceed
the
total nu
mbe
r
of
the di
strib
u
tio
n
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Study on VRPTW Based
on Im
prove
d
Part
icle Swarm
Optim
i
zation (Wang Fei
)
4545
cente
r
ha
s; formul
ation (3
) en
sure ea
ch vehi
cle l
o
a
d
doe
s not e
x
ceed it
s ca
rrying capa
cit
y
;
formulatio
n (4) sho
w
the
task
of cu
sto
m
er
can
o
n
ly be delivery
by a ca
r; formulation (5)
and
formulation (6) guarantee that each
customer
will
be visited ex
actly once; formul
ation (7) ,
formulatio
n
(8)an
d
fo
rmul
ation
(9) a
r
e
time con
s
trai
nt co
ndition
s of vehi
cle
.
ijk
x
and
k
y
0
ar
e
defined a
s
fol
l
ows in formul
a (10
)
and formula (1
1):
0
1
e
m
e
rge
n
cy
v
e
hi
cle k
i
s
i
n
us
e
0o
t
h
e
r
w
i
s
e
k
x
(10)
k
y
0
otherwise
0
use
in
is
k
vehicle
1
(11)
3. Impro
v
ed
Particle S
w
a
r
m Optimiz
a
tion
3.1. Particle S
w
arm Opti
miz
a
tion Algorithm
PSO is a ne
wly-em
erg
ed
bioni
c algo
rit
h
m imitating
bird
s to find f
ood d
e
velope
d by Dr.
Eberh
a
rt a
n
d
Dr. Ke
nne
dy in 19
95. In t
he PSO, ea
c
h
pa
rt
icle
ke
e
p
s t
r
ac
k
of
it
s
coo
r
din
a
t
e
s
in
the
problem
spa
c
e whi
c
h
are asso
ciate
d
with
th
e
be
st solution it
has
achieved
so fa
r, the v
a
lue
is called
pbest
. Wh
en a
p
a
rticl
e
take
s all
the
popul
ation
as its to
polo
g
ical nei
ghb
ors, the
be
st
value is called
gbest
. The parti
cl
e swarm o
p
timization
con
c
ept con
s
ist
s
of, at each time step,
cha
ngin
g
the
velocity of
each p
a
rticl
e
towa
rd
its
pbest
a
nd
gbest
locat
i
o
n
s.
A
c
cele
rat
i
on
is
weig
hted by a rand
om term, with sepa
rate ra
ndom
numbe
rs bei
ng gene
rate
d
for acceleration
toward
pbest
and
gbest
locat
i
o
n
s.
After finding the two best
values, the particl
e upd
a
t
es its velocit
y
and positio
ns with
fo
llo
w
i
ng
Eq
ua
tio
n
(
1
2)
a
n
d
(
1
3)
.
)
(
*
)
(
*
2
2
1
1
1
k
id
k
id
k
id
k
id
x
gbest
r
c
x
pbest
r
c
wv
v
(12)
1
1
k
id
k
id
k
id
v
x
x
(13)
In the formula:
k
id
x
is the position of
particle
i
,
k
id
v
is the velocity of particle
i
,
]
,
[
max
min
V
V
v
k
id
,
min
V
and
max
V
defined
by the u
s
er
are t
w
o
con
s
t
ants,
w
is inertia wei
ghting
factor,
c1 a
n
d
c2 a
r
e l
earn
i
ng facto
r
s,
，
usually c1
= c2 =
2,
1
r
and
2
r
are
two
ran
dom nu
mbe
r
betwe
en (0, 1
)
.
3.2. Population Entrop
y
Selecting p
r
o
per
A
and
B
to
meet parti
cle
fitness valu
es a
r
e interv
al
B
A
，
,
the
interval
B
A
，
is di
vided into
N
eq
ual pa
rts
，
t
h
e pa
rticle
nu
mbers
of
N
su
bi
ntervals a
r
e
1
S
，
2
S
,…,
N
S
,
the po
pulation e
n
tro
p
y are define
d
as sho
w
n in
Equation (1
4
)
.
N
S
N
S
E
i
N
i
i
lg
1
(14)
3.3. Impro
v
e
d
Particle Sw
arm Optimi
z
a
tion
In the pape
r, improve
d
particl
e swarm
optimi
z
ation is de
signed by u
s
ing two-
dimen
s
ion
a
l annul
ar cellul
a
r structu
r
e,
all particl
es a
r
e pla
c
ed in
side and e
a
ch
particle
ha
s 5
parts
whi
c
h i
s
the pa
rticle
itself and its f
our
n
e
ighb
ors. Whe
n
the
popul
ation en
tropy de
cre
a
ses
very quickly, the cell
ular stru
cture is narro
wed t
o
strengthe
n
the glob
al
sea
r
ch abilit
y of
algorithm; otherwi
s
e, the
cellular st
ructure i
s
wide
ned to st
rengthen the l
o
cal
searching ability
of
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4543 – 4
549
4546
algorith
m
. Becau
s
e
each
particl
e lea
r
n
s
the be
st
p
a
rticle i
n
form
ation of their neighb
ors, the
locatio
n
and
velocity of new algo
rithm is updated
with
the Equation
(15) a
nd the
Equation (16).
))
(
)
(
(
))
(
)
(
(
)
(
)
1
(
2
2
1
1
t
x
t
gbest
r
c
t
x
t
pbest
r
c
t
wv
t
v
id
id
id
id
id
id
(15)
)
1
(
)
(
)
1
(
t
v
t
x
t
x
id
id
id
(16)
In the paper,
only two-dim
ensi
onal cellu
lar st
ructu
r
e
s
are respectiv
e
ly written as
'
'
c
r
and
c
r
whi
c
h i
s
adopte
d
in
order to
facilitat
e the d
e
scrip
tion,
c
r
is
co
rre
s
po
ndin
g
to
wide
cellul
a
r st
ru
ct
ure,
while
'
'
c
r
is corre
s
p
ondin
g
to
na
rrow cellul
a
r stru
ct
ure and
c
r
=
'
'
c
r
,among of
which,
r
and
'
r
express th
e
line numbe
r
,
c
and
'
c
expre
s
s the
colu
mn n
u
m
ber,
so
the particl
e p
o
sition of con
v
ersin
g
cell
ul
ar
structu
r
e i
s
defined with
the Equation
(17
)
[9].
)
mod
]
[
,
]
([
)
,
(
'
'
c
j
c
i
divc
j
c
i
j
i
(17)
4. The Solution to VRPT
W Ba
sed on
the Algo
rith
m Proposed
in the Paper
4.1. Coding
Strateg
y
of
Particles
The positio
n of particle co
rrespon
ding with t
he answe
r to the question is the key
idea of
PSO. In the pape
r
,
a n
e
w parti
cle en
coding
of thre
e-dim
e
n
s
iona
l vectors
Z
on
the ba
sis
of
referen
c
e [10] is constru
c
t
ed to VRPTW
.
In the
vector
Z
, the first d
i
mensi
on
ix
Z
of
particl
es is
vehicle info
rmation; the s
e
c
o
n
d
d
i
m
e
n
s
i
o
n
iy
Z
of particle
s
is traveling di
stance of the ve
hicle.
4.2. Decodin
g
Stra
teg
y
of
Particles
To get to the
vehicle
ord
e
r
of the travel
path,
iy
Z
mu
st be
adju
s
ted. Adj
u
stment fu
nct
i
on
can b
e
got a
c
cording to the
size
seq
uen
ce of the vect
or
iy
Z
, that is
, fin
d
ing
iy
Z
of the vehicle fo
r
cu
st
ome
r
i
first, and then sorte
d
from
small to larg
e according t
o
the size of
iy
Z
, thus the
driving path
orde
r of vehi
cle
i
is obtai
ned. For
exa
m
ple, if
there are 1
0
cu
stome
r
s a
n
d
4
vehicle
s
. If the po
sition v
e
ctor
iy
Z
of a pa
rticle i
s
sho
w
n as Tabl
e 1
,
then vecto
r
iy
Z
of the
positio
n after adjustm
ent is shown a
s
Table 2.
So t
he co
rrespon
ding vehi
cle
routing
s
a
r
e
as
follows (0 rep
r
esents the di
stributio
n ce
n
t
er):
vehicle 1
，
0
→
2
→
6
→
0
；
vehicle 2
，
0
→
1
→
4
→
3
→
10
→
0
；
vehicle 3
，
0
→
7
→
9
→
5
→
0
；
vehicle 3
，
0
→
8
→
0
。
Table 1. The
Vector of Part
icle i before Deco
ding
customer
1 2 3 4 5
6
7 8 9 10
ix
Z
2 1 2 2 3
1
3 4 3 2
iy
Z
1.3 2.6 3.3 2.
4 4.
6 3.4 2.8 0.9
3.6
5.7
Table 2. The
Vector of Part
icle i after De
codi
ng
customer
1 2 3 4 5
6
7 8 9 10
ix
Z
2 1 2 2 3
1
3 4 3 2
iy
Z
1 1 3 2 3
2
1 1 2 4
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Study on VRPTW Based
on Im
prove
d
Part
icle Swarm
Optim
i
zation (Wang Fei
)
4547
4.3.
Process Des
c
ription of
Algorithm
Step 1: initialize: Set the
popul
ation si
ze
N
, inertia weight coeffici
ent
w
, ac
c
e
lerating
fac
t
or
1
c
and
2
c
, maximum n
u
m
ber of ite
r
ations
max
N
，
con
s
tant
. The
current ite
r
ati
o
n
numbe
r
t
is
set to 1
，
ran
dom g
ene
rat
i
on initial
po
sition
N
x
x
x
,...
,
2
1
and initial
velocit
y
N
v
v
v
,...,
,
2
1
of
N
particl
es; t
he
N
pa
rticle
s
are
pla
c
ed
in
the cellula
r of
c
r
ac
co
rd
in
g to th
e
orde
r of initial
i
zation.
Step 2: Calculate the fitness value
i
f
of the
i
parti
cle
,
and see
k
the be
st parti
cle
information
i
gbest
)
,...,
2
,
1
(
N
i
of their neighb
ors.
Step 3: For a
ll the particl
e
s
, if
i
f
>
i
pbest
, then
i
pbest
=
i
f
,
i
pbest
x
=
i
x
, update
i
gbest
according to the ne
w parti
cle fitness valu
e.
Step 4: Calculate pop
ulati
on entropy
t
E
of
t
iteration, update e
a
ch particl
e'
s po
si
tion
and spee
d wi
th the formula
(15) a
nd formula (1
6).
Step 5: Separately cal
c
ul
ate
1
t
t
t
E
E
E
and
1
t
E
2
1
t
t
E
E
, if s
a
tis
f
ying
1
)
2
(
t
t
E
E
,
the st
ru
cture
of cellul
a
r i
s
conve
r
ted to
'
'
c
r
, if s
a
tis
f
ying
t
E
1
)
1
(
t
E
,
the structu
r
e
of cellular i
s
conve
r
ted to
c
r
.
Step 6: Ju
dg
e wh
ether the
cu
rre
nt iterati
on num
be
r
t
is gre
a
ter tha
n
the iteration
n
u
mbe
r
max
N
, if not s
a
tis
f
ied,
1
t
t
return Step
2, otherwi
se,
the optimal solution
s is out
put.
5. Experimental Exampl
es
5.1. Example 1
To verify the viability of algorithm, rand
omly gene
rat
ed VRPT
W throu
gh the
compute
r
within the ra
nge of 100
×100(unit: km), the loca
tion
(unit: km) a
nd dema
nd (unit: t) and time
wind
ows
(unit
:
minute) of
custom
e
r
s i
s
shown a
s
T
abl
e 3.
Dist
ri
buti
on
cente
r
h
a
s
five vehi
cle
s
,
each vehicl
e’s sp
eed i
s
65
km/hou
r and
eac
h vehicl
e'
s maximum
capa
city is 25.
Table 3. Cu
st
omer Info
rma
t
ion
customers
X
coordinates Y
coordinat
es demand
times
w
i
ndo
w
s
0 50
50
1 39
4
7
（）
0,100
2 19
94
1
（）
0,90
3 97
42
2
（）
0,120
4 31
72
8
（）
0,60
5 37
26
2
（）
0,150
6 63
55
3
（）
0,240
7 95
82
2
（）
0,180
8 28
59
3
（）
0,30
9 54
28
5
（）
0,180
10 7
22
2
（）
0,60
11 16
2
4
（）
0,90
12 80
3
1
（）
0,60
13 39
98
5
（）
0,120
14 66
29
6
（）
0,30
15 86
60
1
（）
0,150
16 4
76
4
（）
0,60
17 96
8
5
（）
0,90
18 21
38
3
（）
0,60
19 74
73
4
（）
0,210
20 50
78
3
（）
0,150
The equ
ation
is cal
c
ulate
d
respe
c
tively by
PSO a
nd IPSO. Throug
h cal
c
ul
ation, the
optimal sche
duling
sch
e
m
e
s of
vehi
cle are
sh
own
a
s
Table
4, th
e
obje
c
tive fun
c
tion chan
ge
s
as
numbe
r of iteration
s
is sho
w
n a
s
Figu
re
1.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4543 – 4
549
4548
Table 4. The
Optimal Sch
e
duling Schem
e of Example
Vehicle
driving route
driving distance
driving time
Vehicle 1
0
→
8
→
4
→
16
→
2
→
13
→
20
→
0
159.1
146.8
Vehicle 2
0
→
18
→
10
→
11
→
1
→
5
→
9
→
0
159.2
147.0
Vehicle 3
0
→
14
→
12
→
17
→
3
→
15
→
7
→
19
→
6
→
0
209.4
193.3
Total
527.7
487.1
Figure 1. Performa
nce Co
mpari
s
o
n
of PSO and IPSO
5.2. Example 2
An area ha
s 25 demand
sites nee
din
g
resour
ce d
e
livered fro
m
distributio
n cente
r
.
There are en
ough ve
hicle
s
. The loadi
ng
cap
a
city is
3
0
ton for e
a
ch vehicl
e. Th
e avera
ge
sp
eed
is 25
km/hou
r.
The coo
r
di
na
te of distributi
on ce
nt
er is 0
point (6km, 4km), po
sition
coo
r
din
a
tes o
f
deman
d site
s (unit: km
), the dema
n
d
i
q
(uni
t: ton)and ti
me win
d
o
w
s
(unit: minute
)
are di
spl
a
ye
d
in Table 5 (0 rep
r
e
s
ent
s for the ce
nter, 1-25
rep
r
e
s
e
n
ts for the de
mand site
s).
The equ
ation
is cal
c
ulate
d
respe
c
tively by
PSO a
nd IPSO. Throug
h cal
c
ul
ation, the
optimal sche
duling
sch
e
m
e
s of
vehi
cle are
sh
own
a
s
Table
6, th
e
obje
c
tive fun
c
tion chan
ge
s
as
numbe
r of iteration
s
is sho
w
n a
s
Figu
re
2.
Table 5. Cu
st
omer Info
rma
t
ion
customers
X
coordinates Y
coordinat
es demand
times
w
i
ndo
w
s
0 6
4
1 5
8
2
（
0,20
）
2 9
7
9
（
0,20
）
3 5
3
6
（
30,60
）
4 7
7
8
（
0,10
）
5 0
2
2
（
10,30
）
6 10
8
4
（
10,30
）
7 2
9
3
（
10,30
）
8 4
1
3
（
10,30
）
9 4
5
3
（
30,60
）
10 9
7
2
（
10,30
）
11 7
1
8
（
20,50
）
12 4
4
4
（
0,10
）
13 3
6
1
（
30,60
）
14 9
10
5
（
10,20
）
15 1
1
3
（
10,40
）
16 10
1
5
（
10,30
）
17 0
6
9
（
20,50
）
18 2
3
8
（
0,20
）
19 8
5
6
（
30,60
）
20 3
0
1
（
20, 50
）
21 7
9
5
（
0,20
）
22 8
0
6
（
10,30
）
23 4
10
7
（
0,20
）
24 5
1
2
（
20,50
）
25 5
7
4
（）
0,10
0
10
0
20
0
300
40
0
50
0
60
0
70
0
800
90
0
1
000
500
600
700
800
900
1
000
1
100
1
200
1
300
1
400
it
e
r
a
t
io
n
n
u
m
b
e
r
：
t
o
ta
l d
i
s
t
a
n
c
e
k
m
PS
O
IP
S
O
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Study on VRPTW Based
on Im
prove
d
Part
icle Swarm
Optim
i
zation (Wang Fei
)
4549
Table 6. The
Optimal Sch
e
duling Schem
e of Example
Vehicle
driving route
driving distance
driving time
Vehicle 1
0
→
4
→
21
→
14
→
6
→
10
→
19
→
0
15.53
37.27
Vehicle 2
0
→
25
→
1
→
23
→
7
→
17
→
13
→
9
→
0 18.9
45.36
Vehicle 3
0
→
12
→
18
→
5
→
15
→
20
→
8
→
24
→
3
→
0
15.95
38.28
Vehicle 4
0
→
2
→
16
→
22
→
11
→
0
17.13
41.11
Total
67.51
162.02
Figure 2. Performa
nce Co
mpari
s
o
n
of PSO and IPSO
6. Conclusio
n
From
the
sim
u
lation
re
sult
of the t
w
o
e
x
perime
n
ts, it
co
uld
qui
ckl
y and
accu
ra
tely find
the optimal solution to VRPTW usi
ng IPSO,
which provides a n
e
w
idea for VRP
T
W.
Ackn
o
w
l
e
dg
ements
This
wo
rk
wa
s fina
nci
a
lly sup
porte
d
by the
Na
tional So
cial
Scien
c
e
fo
undatio
n
(12
C
GL
004
)
and the Yo
uth scientific
re
sea
r
ch p
r
oje
c
ts of Gan
s
u i
n
stitute of pol
itical scien
c
e
and
law (G
ZF2
01
2XQNL
W
1
2
).
Referen
ces
[1]
Dantzi
g G, Ramser J.
T
he truck dispatch
ing
prob
lem.
Mana
gment Scie
nce
.
1959; (6): 58-
102.
[2]
Azi N, Gendreau M, Potvin
JY. An exact
algori
thm for
a
sing
le-v
ehic
l
e
routi
ng
prob
le
m
w
i
th tim
e
w
i
nd
o
w
s a
nd
multipl
e
routes.
Europe
an Jo
u
r
nal of Operati
ona
l Rese
arch
.
2007; 1
78: 75
5-76
6.
[3]
Russell RA,
Chiang WC.
Scatter sear
ch
for the VRP
w
i
t
h
time
w
i
ndo
w
.
E
u
rop
e
an Jo
urna
l of
Operatio
nal R
e
search
. 20
06;
169: 60
6-6
22.
[4]
W
ang
L. Savi
ng
alg
o
rithm f
o
r VRP
of
w
i
th time
w
i
n
d
o
w
s
.
J
our
nal
o
f
Heil
on
gji
a
n
g
institute
of
techno
lo
gy
. 20
11; 25(3): 1
8
-2
0.
[5]
Che
n
MJ, Zha
ng ZS, C
h
e
n
CY et
al. Stu
d
y
on
A N
o
ve
l
Clusteri
n
g
Ant
Colo
n
y
A
l
gor
ithms for M
u
lti-
dep
ots Vehic
l
e
Routin
g Probl
em.
Manufactu
re Information
Engi
neer
in
g of Chin
a
. 20
08; 3
7
(11): 1-5.
[6]
Kenn
ed
y J
Eb
erhart R.
P
a
rticle Swar
m
Opt
i
mi
z
a
tion.
Proc
eed
ings
of IEE
E
Internati
ona
l
Confer
enc
e
on Ne
ural N
e
tw
o
r
ks. 199
5; 1942-
194
8.
[7]
Liu Z
X
. Ve
hicl
e sched
uli
ng o
p
timizati
on in l
ogistics d
i
strib
u
tion b
a
se
d on
particle s
w
ar
m optimizati
o
n
algorithm.
Jour
nal of W
uha
n
Univers
i
ty of Scienc
e an
d T
e
chno
logy
. 2
009;
32(6): 615-
61
8
．
[8]
ZHANG YB, LV GQ. Study
of Phy
s
ical Distributio
n Routing Optimization
Problem
Based on Hy
brid
PSO Algorithm
.
Packing en
gi
neer
ing.
2
007;
28(5): 10-
12
．
[9]
DUAN Xia
o
-d
ong,
GAO H
ong-
xia, LIU Xi
an
g-do
ng
et
c. Adaptiv
e P
a
rticle
S
w
arm
Optimizati
o
n
Algorit
hm Base
d on Pop
u
l
a
tio
n
Entrop
y.
C
o
m
p
u
t
e
r
En
gi
nee
ri
ng
. 200
7; 33
(18): 222-
22
4.
[10]
A
y
e
d
S, Imtiaz A, Sabah A. P
a
rticle
s
w
a
rm o
p
timizati
on for task assig
n
me
n
t
problem.
Micr
oproc
essors
and Micr
osyste
m
s
. 20
02; 26: 363-
371.
0
10
0
200
300
400
50
0
60
0
700
800
900
100
0
60
80
100
120
140
160
180
200
i
t
e
r
a
t
i
o
n
num
be
r
to
t
a
l d
i
s
t
a
n
c
e
:
km
PS
O
I
PSO
Evaluation Warning : The document was created with Spire.PDF for Python.