Intern
ati
o
n
a
l
Jo
urn
a
l
o
f
Ad
va
nces
in Applied Sciences (IJ
A
AS)
Vol.
2, No. 4, Decem
ber
2013, pp. 193~
200
I
S
SN
: 225
2-8
8
1
4
1
93
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJAAS
The P
r
eprocessi
ng and P
r
obing T
echnique of
Open
Cap
a
ci
t
a
t
e
d
Vehicl
e Routing Probl
e
m
with
Split and Time Deadline
(OCVRP-St) Model In Rubbish
Transportation Problem
Irmei
l
yan
a,
Fi
tri
M
a
ya
Pus
p
i
t
a,
Indr
aw
a
t
i
,
Fi
tra
N
u
r
Az
iz
ah
Departm
e
nt o
f
M
a
them
ati
c
s
,
F
a
cult
y
of M
a
them
ati
c
s
and
Natura
l
S
c
ien
ces
,
S
r
iwij
a
y
a Univ
ers
i
t
y
,
I
nderal
a
ya
, S
outh
Sumatera, Indon
esia
Article Info
A
B
STRAC
T
Article histo
r
y:
Received
May 12, 2013
Rev
i
sed
Ju
l 7
,
2
013
Accepte
d
J
u
l 26, 2013
The activ
ity
of r
ubbish transportation in
Palembang is one of the
applications
of
Vehi
cl
e Ro
u
ting Problem
(VRP) in transporting rubbish in Sako
Palembang b
y
apply
i
ng pr
epro
cessi
ng and pr
obing techn
i
ques to obtain
simplest OCVR
P model. The solu
tion is conducted b
y
using LINDO
software.
The
re
sults show that
the op
timal routes
in
Sukar
a
mi before and
after app
l
ying th
e tehniqu
es
are
the s
a
m
e
routes. In addition, we obtain the
reduction of con
s
traints and v
a
riables,
the r
e
duction of iteration n
u
mbers and
the op
tim
al
valu
e did
not
chang
e
.
Keyword:
Ope
n
Ca
pacitated Ve
hicle
R
out
i
n
g Pr
obl
e
m
(OC
V
R
P
)
Optim
al routes
Pre
p
r
o
cessi
n
g
t
echni
que
Pro
b
i
n
g
t
ech
ni
que
Copyright ©
201
3 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Fitri Maya Pu
sp
ita,
Depa
rt
m
e
nt
of
M
a
t
h
em
at
i
c
s,
Facu
lty of Math
em
at
ics an
d
Natural
Scien
c
es, Sriwij
aya
Un
iv
ersity,
In
deral
a
y
a
, So
ut
h Sum
a
t
e
ra,
I
n
d
o
n
esi
a
.
Em
a
il: p
i
p
it1
40
201
@yah
oo
.co
m
.au
1.
INTRODUCTION
R
u
b
b
i
s
h
pr
o
b
l
e
m
i
s
a
m
a
jor
pr
o
b
l
e
m
i
n
a ci
t
y
t
h
at
shoul
d
be ha
n
d
l
e
d
by
t
h
e g
ove
rnm
e
nt
especi
al
l
y
by
Di
nas
Ke
b
e
rsi
h
a
n
da
n Pe
m
a
kam
a
n (
D
K
P
).
The
r
u
bbi
s
h
di
sp
osal
i
n
Pal
e
m
b
ang
i
s
con
d
u
ct
ed
i
n
t
o
st
ep
s
.
The r
u
bbi
s
h
were c
o
l
l
ect
ed
fr
om
hom
es
t
o
t
h
e nea
r
est
Tem
pora
r
y
R
u
b
b
i
s
h Di
s
pos
al
(TR
D
)
.
Th
en, t
h
e
rubb
ish
will b
e
tran
sp
orted
b
y
th
e o
f
ficers
fro
m
Pale
m
b
an
g
Hyg
i
en
e Serv
ice Un
it b
y
u
s
i
n
g
v
e
h
i
cles such
as
dum
p t
r
uck
s
or
am
rol
l
t
o
Fi
nal
R
ubbi
s
h
Di
sp
osal
(FR
D
) o
r
dep
o
t
i
n
Su
ka
wi
nat
a
n
or Ka
r
y
a Jay
a
. The rub
b
i
s
h
tran
sp
ortatio
n is group
ed in
to
Work
in
g Area fo
r
eac
h dri
v
er of
ve
hi
cl
e.
The r
u
bbi
s
h
t
r
ans
p
ort
a
t
i
o
n i
s
one
of t
h
e exam
pl
e of
Veh
i
cle Rou
tin
g Prob
lem
(
V
RP) to fi
n
d
min
i
m
u
m
ro
u
t
es. IF it is fo
cu
ssed
on
on
e
d
e
po
t an
d
g
e
neral v
e
h
i
cle cap
acity, th
en
it
is called
Ca
pacita
ted
Vehi
cl
e Ro
ut
i
n
g Pr
obl
e
m
(C
VR
P)
. I
f
t
h
e c
u
st
om
ers can
be vi
si
t
e
d cl
oc
kwi
s
e
or a
n
t
i
cl
ock
w
i
s
e r
out
e
s
al
on
g
th
e arcs, th
en
t
h
e
p
r
ob
lem
is c
a
lled
Sy
mmet
r
i
c
C
a
paci
t
a
t
e
d
Vehi
cl
e R
out
i
n
g Pr
o
b
l
e
m
(SC
V
RP)
.
In the clas
sic
VRP, the
ve
hic
l
es sh
oul
d g
o
b
ack
t
o
t
h
e
dep
o
t
aft
e
r fi
ni
s
h
i
n
g
t
h
e jo
u
r
ney
.
Ho
we
ver
,
i
n
m
o
re i
m
p
r
o
v
e
d case, after fi
n
i
sh
ing
th
e
j
o
u
r
ney, th
e v
e
h
i
cles n
eed
n
o
t
to
go
b
a
ck
to
th
e
dep
o
t
. Th
is will resu
lt
in
ope
n
path whe
r
e
t
h
e vehi
cle
starts
f
r
om
t
h
e
dep
o
t
a
n
d
en
ds i
n
one
o
f
t
h
e
cust
om
ers [
1
]
.
T
h
at
si
t
u
at
i
o
n
o
ccurs in
rub
b
ish
tran
spo
r
tatio
n
in
Palem
b
a
n
g. Th
e
v
e
h
i
cl
es u
s
u
a
lly are
n
o
t
in
d
e
po
t after tran
sp
orting
th
e
rubb
ish
.
Th
e ro
u
t
es
will b
e
op
en
rou
t
es and we call
it Op
en
Cap
acitated
Veh
i
cle Rou
ting
Prob
lem
(OCVRP).
If we fo
cu
s on
o
n
e
d
e
po
t and
th
e cap
acity o
f
th
e v
e
h
i
cles th
en
th
e p
r
ob
lem will b
e
Op
en
Cap
acitated
Veh
i
cle
R
out
i
n
g Pr
obl
e
m
(OC
V
R
P
).
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
252
-88
14
IJAAS
Vol. 2, No.
4, Decem
ber :
193
–
200
19
4
Savel
s
ber
gh
[
2
]
gave
det
a
i
l
expl
a
n
at
i
on a
b
o
u
t
t
i
ght
e
n
i
n
g t
h
e rel
a
xed
Li
near P
r
o
g
r
a
m
i
n
M
i
xed
In
teg
e
r Li
n
i
ear Prog
ram
(MILP) b
y
u
tilizin
g
pr
obi
ng
and
pre
p
r
o
cessi
ng
techn
i
qu
es
wh
ich
resu
lt in
th
e
red
u
ct
i
o
n i
n
b
o
u
n
d
s a
n
d
si
ze
of
coe
ffi
ci
ent
of c
o
nst
r
ai
nt
m
a
t
r
i
ces. In t
h
i
s
case, Sa
vel
s
ber
g
h [
2
]
ge
ne
rat
e
t
h
e
fram
e
wor
k
t
o
dra
w
vari
ous
t
echni
que
s
pre
p
roces
si
n
g
a
nd
pr
o
b
i
n
g i
n
M
I
LP s
o
t
h
at
set
of t
h
e
feasi
b
l
e
sol
u
t
i
o
n
s
o
f
relax
e
d
li
n
e
ar
p
r
o
g
rammin
g
can
b
e
redu
ced
b
u
t
t
h
e set
of th
e feasi
b
le so
lu
tion
s
o
f
MILP will
n
o
t
ch
an
g
e
.
In
fact
,
t
h
e
pr
o
b
i
n
g a
n
d
pre
p
r
o
cessi
ng
t
echni
qu
e
b
a
sically atte
m
p
t to
ch
eck an
d ch
ang
e
a
fo
rm
ul
at
i
on of
t
h
e con
s
t
r
ai
nt
s so t
h
at
t
h
at
fo
rm
ul
at
i
on can be s
o
l
v
e
d
e
a
sily. For inst
ance, in
real case of
Fi
xed
-
C
h
a
r
ge Net
w
or
k Fl
o
w
Pro
b
l
e
m
s
[3]
.
The p
r
e
p
r
o
c
e
ssi
ng t
e
c
hni
q
u
e i
s
al
ready
appl
i
e
d i
n
pr
e
v
i
o
us
researc
h
o
n
C
V
RP [4]
-
[
9]
.
So
, i
n
th
is p
a
per, th
e co
n
t
ribu
tio
n
will b
e
based
on
ap
p
l
yin
g
pr
obi
ng
and
pre
p
r
o
cessi
ng
o
f
OC
VRP
esp
ecially f
o
r
i
d
en
tif
ying
nonf
easib
le con
s
train
t
s, r
e
dund
an
t v
a
r
i
ab
les, im
p
r
o
v
i
ng
boun
d
s
and
co
ef
f
i
cien
t an
d
arran
g
e
m
e
n
t
of v
a
riab
le
v
a
l
u
es.
We t
h
en
v
a
lid
ate th
e m
o
d
e
l and
co
mp
are t
o
in
itial m
o
d
e
l. He
ru
bb
ish
trans
p
ortation
m
odel is foc
u
s
e
d
on rubbis
h
t
r
ans
p
ortation i
n
Kecam
atan Sako Palem
b
ang.
2.
R
E
SEARC
H M
ETHOD
To
sim
p
lify th
e m
o
d
e
l o
f
th
at
tran
spo
r
tation
syste
m
, we cond
u
c
t t
h
ree stages as
fo
llows.
1.
Fo
rm
th
e
OVC
RP m
o
d
e
l
The m
odel is
form
ed according to rubbis
h
transpor
tation data in Kecamatan Sako Pale
m
b
ang s
u
ch as
ro
ut
es,
di
st
anc
e
bet
w
ee
n FR
D an
d TR
Ds,
vehi
cl
e’s
cap
aci
t
y
, num
ber of
ve
hi
cl
es u
s
ed a
nd
ru
b
b
i
s
h
v
o
l
u
m
e. W
e
ob
tain
th
e data th
rou
g
h
surv
eyin
g
and
in
terv
iewing
in
d
e
tails’ to
staff
o
f
rubb
ish
m
a
n
a
g
e
men
t
i
n
FR
D
of
Su
k
a
ban
g
u
n
area
a
n
d
se
veral
dri
v
ers
of
r
u
b
b
i
s
h t
r
uc
ks.
2.
Si
m
p
lify th
e OCVRP m
o
d
e
l
To si
m
p
l
i
f
y
the m
odel
,
we
con
d
u
ct
st
ep
s such as st
re
ngt
heni
ng t
h
e
bo
u
nds
of c
onst
r
ai
nt
va
ri
a
b
l
e
s,
el
im
i
n
at
i
ng
red
u
n
d
a
n
t
co
nst
r
ai
nt
s a
n
d
fi
xi
ng
vari
a
b
l
e
s.
3.
So
lv
e th
e
OC
VRP m
o
d
e
l
Th
e so
lu
tion
is to
ob
tain
op
timal o
b
j
ectiv
e fu
n
c
tion
and
each
d
ecisio
n
v
a
riab
les of th
e m
o
d
e
l. Th
e so
l
u
tio
n
i
s
based
on
no
n-si
m
p
l
i
f
i
e
d
m
odel
a
nd si
m
p
l
i
f
i
e
d m
odel
and we see
k
t
o
com
p
are t
h
at
sim
p
l
i
f
i
e
d
m
o
d
e
l
yield efficient
result.
3.
R
E
SU
LTS AN
D ANA
LY
SIS
In
t
h
i
s
part
,
we
desc
ri
be t
h
e st
eps
of
si
m
p
l
i
f
yi
ng
OC
VR
P m
odel
usi
n
g
p
r
e
p
r
o
cessi
ng
t
echni
que
s.
For Wor
k
ing Area
1
Sako
Mo
d
e
l OCVR
P
after
settin
g u
p
th
e prob
ing
tech
n
i
qu
e
is
Min
z
= 6,
5
y
01
+2
y
02
+6
y
03
+8,5
y
04
+8.5
x
12
+1
3,5
x
13
+15
x
14
+8,5
x
21
+4
x
23
+6,5
x
24
+13,5
x
31
+4
x
32
+2,5
x
34
+15
x
41
+6,5
x
42
+2,5
x
43
(1
)
Subject t
o
x
12
+
x
13
= 1
(2a
)
y
03
+
y
30
= 1
(4a
)
x
31
+
x
32
= 1
(4b)
y
04
+
y
40
= 2
(5a
)
y
01
+
y
02
+
y
03
+
y
04
+
y
10
+
y
20
+
y
30
+
y
40
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
4.
2
(6
)
y
10
+
y
20
+
y
30
+
y
40
-
y
01
-
y
02
-
y
03
-
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
0
(7
)
y
10
+
y
20
+
y
30
+
y
40
= 1
(8
)
Nonn
eg
ativ
ity requ
irem
en
ts:
x
12
≥
0 ;
x
13
≥
0 ;
x
14
≥
0 ;
x
21
≥
0 ;
x
23
≥
0
;
x
24
≥
0
;
x
31
≥
0
;
x
32
≥
0
;
x
34
≥
0
;
x
41
≥
0
;
x
42
≥
0
;
x
43
≥
0
;
y
01
≥
0
;
y
02
≥
0
;
y
03
≥
0
;
y
04
≥
0
;
y
10
≥
0
;
y
20
≥
0
;
y
30
≥
0
;
y
40
≥
0.
x
12
,
x
13
,
x
14
,
x
21
,
x
23
,
x
24
,
x
31
,
x
32
,
x
34
,
x
41
,
x
42
,
x
43
{0
, 1, 2}
y
01
,
y
02
,
y
03
,
y
04
,
y
10
,
y
20
,
y
30
,
y
40
{0,
1}
We c
ont
i
n
ue
t
o
p
r
ep
roce
ssi
n
g
t
e
hni
q
u
e a
s
f
o
l
l
ows.
x
12
+
x
13
≤
1
(
2
a*
)
y
03
+
y
30
≤
1
(
4
a*
)
x
31
+
x
32
≤
1
(
4b*
)
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
AA
S I
S
SN
:
225
2-8
8
1
4
The
Prep
roces
si
ng
a
n
d
Pr
o
b
i
n
g
Tec
hni
que
of
O
p
e
n
C
a
p
a
c
i
t
a
t
e
d Ve
hi
cl
e Ro
ut
i
n
g
Pr
obl
e
m
(
I
r
m
ei
l
y
a
na)
19
5
y
04
+
y
40
≤
1
(
5
a*
)
y
10
+
y
20
+
y
30
+
y
40
≤
1
(
8
*
)
Preproces
sing Technique
1.
Stren
gthen
th
e bounds
of c
o
nstr
aint
variables
x
12
,
x
13
,
x
14
,
x
21
,
x
23
,
x
24
,
x
31
,
x
32
,
x
34
,
x
41
,
x
42
,
x
43
{0, 1, 2}
d
a
n set
i
a
p va
ri
a
b
el
m
e
m
puny
ai
bat
a
san n
o
n
n
e
gat
i
f
>
0, m
a
ka, apa
b
i
l
a
di
m
i
sal
k
an
x
12
=0;
x
13
=1;
x
14
=0;
x
21
=2;
x
23
=0;
x
24
=0;
x
31
=1;
x
32
=0;
x
34
=0;
x
41
= 0;
x
42
=1;
x
43
=2.
y
01
,
y
02
,
y
03
,
y
04
,
y
10
,
y
20
,
y
30
,
y
40
{
0
,
1
}
da
n set
i
a
p
v
a
ri
abel
m
e
m
puny
ai
bat
a
sa
n
n
o
n
n
e
g
at
i
f
>
0, m
a
ka,
di
m
i
sal
k
an
y
01
=1;
y
02
=1;
y
03
=1
;
y
04
=1;
y
10
=0;
y
2
=0;
y
30
=0;
y
40
=1.
Str
e
ng
th
en
t
h
e
b
oun
d fo
r v
a
r
i
ab
le
x
12
,
x
13
in (2
a*).
Str
e
ng
th
en
t
h
e
b
oun
d fo
r v
a
r
i
ab
le y
03
,
y
30
in
(4
a
*
)
.
Str
e
ng
th
en
t
h
e
b
oun
d fo
r v
a
r
i
ab
le
x
31
,
x
32
in
(4
b*)
.
Str
e
ng
th
en
t
h
e
b
oun
d fo
r v
a
r
i
ab
le
y
04
,
y
40
in
(5
a*
).
Varia
b
le
y
01
,
y
02
,
y
03
,
y
04
,
y
10
,
y
10
,
y
20
,
y
30
and
y
40
in
(6
) canno
t b
e
streng
th
en
ed
.
Varia
b
le
x
12
,
x
13
,
x
14
,
x
21
,
x
23
,
x
24
,
x
31
,
x
32
x
34
x
41
,
x
42
and
x
43
i
n
(6
) ca
nn
ot
be
st
ren
g
t
h
e
n
e
d
.
Varia
b
le
y
10
y
20
y
30
y
40
y
01
y
02
y
03
y
04
x
12
x
13
x
14
x
21
x
23
x
2
x
31
x
32
x
34
x
41
x
42
x
43
in (7
) can
not
be
strengthe
n
ed.
Str
e
ng
th
en
t
h
e
b
oun
d fo
r v
a
r
i
ab
le
y
10
y
20
y
30
y
40
in (8
).
2.
Elimina
t
e Redunda
n
t
va
riables
Fo
r Co
nstra
i
nt
(6)
a.
W
e
go
t th
e n
o
n
n
e
g
a
tiv
e boun
d
af
ter
str
e
ngth
e
n
i
ng
th
e bou
nd
s th
at ar
e
x
12
≥
0;
0
≤
x
13
≤
1;
x
14
=0;
x
21
=2;
x
23
=0;
x
24
=0; 0
≤
x
31
≤
1;
x
32
≥
0;
x
34
=0;
x
41
=0;
x
42
=1;
x
43
=2;
y
01
=1;
y
02
=1; 0
≤
y
03
≤
1;
0
≤
y
04
≤
1;
y
10
=0;
y
20
=0;
y
30
≥
0;
0
≤
y
40
≤
1
.
By
u
s
ing
upp
er
bo
und
,
w
e
ob
tain
th
at (
6
)
satisf
y
th
e u
p
p
e
r
bo
und
of
n
onn
eg
ativ
ity co
nstrain
t
.
b.
W
e
go
t th
e n
o
n
n
e
g
a
tiv
e boun
d
af
ter
str
e
ngth
e
n
i
ng
th
e bou
nd
s th
at ar
e
x
12
=0;
x
13
=1;
x
14
=0;
x
21
=2;
x
23
=0;
x
24
=0;
x
31
=1;
x
32
=0;
x
34
=0;
x
41
=0;
x
42
=1;
x
43
=2;
y
02
=1;
y
03
=1;
y
04
=1;
y
10
=0;
y
20
=0;
y
30
=0;
y
40
=1.
By u
s
in
g
l
o
wer bou
nd
,
we
ob
tain
th
at (6) satisfy
t
h
e l
o
we
r b
o
u
n
d
of
n o
nne
gat
i
v
i
t
y
co
nst
r
ai
nt
.
We
co
n
c
l
u
d
e
th
at
(3
.6
) is redu
nd
an
t.
Hen
c
e,
we
can
elim
in
ate (6
).
Fo
r Co
nstra
i
nt
(7)
We ob
tain
th
at (7
) satisfy th
e up
p
e
r bou
nd
and
lo
wer of no
nn
eg
ativ
ity co
n
s
train
t
.
Hen
c
e, it can
b
e
eliminated sinc
e it is redundant.
3.
Fi
x t
h
e
vari
a
b
l
es
a.
E
val
u
a
te va
ri
abl
e
x
13
.
Sinc
e the const
r
aint (2a*) has t
h
e
num
be
r of bi
gge
st const
r
aints exceed RHS,
then t
h
at c
onst
r
aint s
h
ould be
elim
inated.
b.
E
val
u
a
te
v
a
ri
abl
e
x
31
.
Sin
c
e th
e con
s
tr
aint (
4b*
)
h
a
s th
e nu
m
b
er of
bi
gge
st constrai
nts excee
d R
H
S,
then t
h
at c
onst
r
aint s
h
ould be
elim
inated.
We
obt
ai
n
n
e
w
OC
VR
P m
ode
l
as f
o
l
l
o
w
s
.
Min
z
= 6,5
y
01
+2
y
02
+ 6
y
03
+
8,5
y
04
+ 8.
5
x
12
+ 13,5
x
13
+
15
x
14
+ 8,
5
x
21
+ 4
x
23
+ 6,5
x
24
+ 13,5
x
31
+
4
x
32
+ 2,
5
x
34
+ 15
x
41
+ 6,
5
x
42
+ 2,5
x
43
(1
*)
Subject t
o
x
12
≤
1
(
2
a**
)
y
03
+
y
30
≤
1
(
4
a*
)
x
32
≤
1
(
4b*
*)
y
04
+
y
40
≤
2
(
5
a*
)
y
10
+
y
20
+
y
30
+
y
40
≤
1
(
8
*
)
and
x
12
≥
0;
0
≤
x
13
≤
1;
x
14
= 0;
x
21
= 2;
x
23
= 0;
x
24
= 0;
0
≤
x
31
≤
1;
x
32
≥
0;
x
34
= 0;
x
41
=0;
x
42
=1;
x
43
=2 ;
y
01
=1;
y
02
= 1;
0
≤
y
03
≤
1;
0
≤
y
04
≤
1;
y
10
= 0;
y
20
=
0;
y
30
≥
0;
0
≤
y
40
≤
1.
x
12
,
x
13
,
x
14
,
x
21
,
x
23
,
x
24
,
x
31
,
x
32
,
x
34
,
x
41
,
x
42
,
x
43
{0
, 1, 2}
y
01
,
y
02
,
y
03
,
y
04
,
y
10
,
y
20
,
y
30
,
y
40
{0,
1}
We tra
n
sfo
r
m into
initia
l
form a
s
fo
llo
ws.
Min
z = 6,5
y
01
+2
y
02
+
6
y
03
+
8,5
y
04
+
8.
5
x
12
+ 13,5
x
13
+ 15
x
14
+
8,
5
x
21
+ 4
x
23
+ 6,5
x
24
+ 13,5
x
31
+ 4
x
32
+ 2,
5
x
34
+ 15
x
41
+ 6,
5
x
42
+
2,5
x
43
(9
)
Subject t
o
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
252
-88
14
IJAAS
Vol. 2, No.
4, Decem
ber :
193
–
200
19
6
x
12
= 1
(10)
y
03
+
y
30
= 1
(11)
x
32
= 1
(12)
y
04
+
y
40
= 2
(13)
y
10
+
y
20
+
y
30
+
y
40
= 1
(14)
and
x
12
≥
0;
0
≤
x
13
≤
1;
x
14
= 0;
x
21
= 2;
x
23
= 0;
x
24
= 0;
0
≤
x
31
≤
1;
x
32
≥
0;
x
34
= 0;
x
41
=0;
x
42
=1;
x
43
=2 ;
y
01
=1;
y
02
=1; 0
≤
y
03
≤
1;
0
≤
y
04
≤
1;
y
10
= 0;
y
20
=
0;
y
30
≥
0;
0
≤
y
40
≤
1.
x
12
,
x
13
,
x
14
,
x
21
,
x
23
,
x
24
,
x
31
,
x
32
,
x
34
,
x
41
,
x
42
,
x
43
{0
, 1, 2}.
y
01
,
y
02
,
y
03
,
y
04
,
y
10
,
y
20
,
y
30
,
y
40
{0,
1}
. F
o
r
the
rest
of
Wo
rki
n
g
A
r
ea,
we
conduct t
h
e sa
me steps as a
b
ove
,
an
d it is su
mmarized
i
n
to
Table 1
b
e
low.
Table 1. Opti
mal Route for
ea
ch W
o
rking
Area in Sako
Workin
g
Area
Ro
ute
I
II
I
II
IV
V
VI
1
3 0
2
4
0
1
2 3
4
2
5
0
1
3
4
6
1
2
0
3
4
1
2
0
3
0 1
2
3
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
AA
S I
S
SN
:
225
2-8
8
1
4
The
Prep
roces
si
ng
a
n
d
Pr
o
b
i
n
g
Tec
hni
que
of
O
p
e
n
C
a
p
a
c
i
t
a
t
e
d Ve
hi
cl
e Ro
ut
i
n
g
Pr
obl
e
m
(
I
r
m
ei
l
y
a
na)
19
7
Tabel 2. OCVRP Model
Before Appl
ying Preproces
sing
Technique
WA
M
odel OCVRP
Model Befor
e
Apply
i
ng Pr
epr
o
cessing T
echnique
Iteration
Nu
m
b
e
r
Variable
Nu
m
b
e
r
Cosntraint
Nu
m
b
e
r
M
odel
I
9
24
7
Z
= 6,
5
y
01
+2
y
02
+
6
y
03
+ 8,5
y
04
+
8,
5
x
12
+ 13,
5
x
13
+ 15
x
14
+ 8,
5
x
21
+
4
x
23
+ 6,
5
x
24
+ 13,
5
x
31
+ 4
x
32
+ 2
,
5
x
34
+ 15
x
41
+ 6,
5
x
42
+ 2,
5
x
43
Kendala :
x
12
= 1
y
03
+
y
30
= 1
x
32
= 1
y
04
+
y
40
= 2
y
10
+
y
20
+
y
30
+
y
40
+
y
01
+
y
02
+
y
03
+
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
4,
2
y
10
+
y
20
+
y
30
+
y
40
-
y
01
-
y
02
-
y
03
-
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
0
y
10
+
y
20
+
y
30
+
y
40
= 1
I
I
6
21
8
Z
= 6,
5
y
01
+9
y
02
+
8,
5
y
03
+ 9
y
04
+
15,
5
x
12
+ 15
x
13
+
15,
5
x
14
+
15,
5
x
21
+ 0,
5
x
23
+
x
24
+
15
x
31
+ 0,
5
x
32
+ 0,
5
x
34
+ 15,
5
x
41
+
x
42
+ 0,
5
x
43
Kendala :
x
13
+
x
14
= 1
y
02
+
y
20
= 1
x
24
= 1
y
03
+
y
30
= 1
y
04
+
y
40
= 1
y
10
+
y
20
+
y
30
+
y
40
+
y
01
+
y
02
+
y
03
+
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
4,
6
y
10
+
y
20
+
y
30
+
y
40
-
y
01
-
y
02
-
y
03
-
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
0
Y
10
+
y
20
+
y
30
+
y
40
= 1
I
I
I
6
42
11
Z
= 9
y
01
+ 6
y
02
+
5.
5
y
03
+
8
y
04
+ 9
y
05
+ 15
y
06
+3
x
12
+
3,
5
x
13
+ 6,5
x
14
+ 7,
5
x
15
+ 13,
5
x
16
+ 3
x
21
+ 0,
5
x
23
+
3
x
24
+ 4
x
25
+
10,
5
x
26
+
3,
5
x
31
+ 0,
5
x
32
+ 2,
5
x
34
+ 3,
5
x
35
+ 10
x
36
+ 6,
5
x
41
+
3
x
42
+ 2,
5
x
43
+
x
45
+ 7,
5
x
46
+7,5
x
51
+ 4
x
52
+ 3,
5
x
53
+
x
54
+ 6,
5
x
56
+ 13,
5
x
61
+ 10,
5
x
62
+ 10
x
63
+ 7,5
x
64
+ 6,
5
x
65
Kendala :
y
02
+
y
20
= 1
x
25
= 1
y
03
+
y
30
= 1
x
31
= 1
y
04
+
y
40
= 1
x
46
= 1
y
05
+
y
50
= 1
y
60
= 1
y
10
+
y
20
+
y
30
+
y
40
+
y
01
+
y
02
+
y
03
+
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
6,
7
3
y
10
+
y
20
+
y
30
+
y
40
-
y
01
-
y
02
-
y
03
-
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
0
y
01
+
y
02
+
y
03
+
y
04
+
y
05
+
y
06
= 1
I
V
6
20
8
Z
= 2
y
01
+ 8
y
02
+ 10
y
03
+ 11
y
04
+
9
x
12
+ 11
x
13
+ 12
x
14
+
9
x
21
+ 2
x
23
+ 3
x
24
+ 11
x
31
+ 2
x
32
+
x
34
+ 12
x
41
+3
x
42
+
x
43
Kendala :
x
12
+
x
13
= 1
y
02
+
y
20
= 1
y
03
+
y
30
= 1
y
04
+
y
40
= 1
x
43
= 1
y
10
+
y
20
+
y
30
+
y
40
+
y
01
+
y
02
+
y
03
+
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
4,
2
y
10
+
y
20
+
y
30
+
y
40
-
y
01
-
y
02
-
y
03
-
y
04
+
x
12
+
x
13
+
x
14
+
x
21
+
x
23
+
x
24
+
x
31
+
x
32
+
x
34
+
x
41
+
x
42
+
x
43
≥
0
Y
10
+
y
20
+
y
30
+
y
40
= 1
V
3
12
6
Z
= 1,
6
x
01
+ 2
x
02
+ 3
x
03
+ 11
x
04
+ 1,
6
x
10
+
x
12
+ 2
x
13
+ 2
x
20
+
x
21
+
x
23
+ 3
x
30
+ 2
x
31
+
x
32
Kendala :
x
01
+
x
02
+
x
03
= 2
x
12
+
x
13
= 1
x
20
+
x
21
+
x
23
= 1
x
30
+
x
31
= 2
x
01
+
x
02
+
x
03
+
x
04
+
x
10
+
x
12
+
x
13
+
x
20
+
x
21
+
x
23
+
x
30
+
x
31
+
x
32
>
0
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
252
-88
14
IJAAS
Vol. 2, No.
4, Decem
ber :
193
–
200
19
8
Tabel 3. OCVRP Model AfterAppl
ying Pr
eprocessing T
echnique
WA
M
odel OCVRP
Model After
Apply
i
n
g
Pr
epr
o
cessing Technique
Iteration
Nu
m
b
e
r
Variable
nu
m
b
er
Constr
aint
Nu
m
b
e
r
M
odel
I
4
4
6
Z
= 6,
5
y
01
+2
y
02
+6
y
03
+8,5
y
04
+8,
5
x
12
+15
x
14
+8,5
x
21
+4
x
23
+6,5
x
24
+4
x
32
+2,5
x
34
+15
x
41
+ 6,
5
x
42
+ 2,5
x
43
Kendala :
x
12
= 1
y
03
+
y
30
= 1
x
32
= 1
y
04
+
y
40
= 2
y
10
+
y
20
+
y
30
+
y
40
= 1
I
I
2
5
6
Z
= 6,
5
y
01
+9
y
02
+8,5
y
03
+9
y
04
+15
x
13
+15,
5
x
14
+0,5
x
23
+
x
24
+
15
x
31
+ 0
,
5
x
32
+ 0,
5
x
34
+ 15,5
x
41
+
x
42
+ 0,
5
x
43
Kendala :
x
13
+
x
14
= 1
y
02
+
y
20
= 1
x
24
= 1
y
03
+
y
30
= 1
y
04
+
y
40
= 1
y
10
+
y
20
+
y
30
+
y
40
= 1
I
I
I
4
8
9
Z
= 9
y
01
+ 8
y
04
+ 9
y
05
+ 15
y
06
+3
x
12
+ 3,5
x
13
+ 6,5
x
14
+ 7,5
x
15
+ 13,5
x
16
+ 3
x
21
+ 0,
5
x
23
+ 3
x
24
+ 4
x
25
+ 10,
5
x
26
+3,5
x
31
+
0,
5
x
32
+
2,
5
x
34
+ 3,
5
x
35
+
10
x
36
+
6,
5
x
41
+ 3
x
42
+ 2,
5
x
43
+
x
45
+ 7,
5
x
46
+7,5
x
51
+ 4
x
52
+
3,
5
x
53
+
x
54
+ 6,5
x
56
+ 13,
5
x
61
+ 1
0
,5
x
62
+ 10
x
63
+ 7,5
x
64
+ 6,
5
x
65
Kendala :
y
02
+
y
20
= 1
x
25
= 1
y
03
+
y
30
= 1
x
31
= 1
y
04
+
y
40
= 1
x
46
= 1
y
05
+
y
50
= 1
y
60
= 1
y
01
+
y
02
+
y
03
+
y
04
+
y
05
+
y
06
=1
IV
2
6 6
Z
= 2
y
01
+ 8
y
02
+
10
y
03
+
11
y
04
+
9
x
12
+ 11
x
13
+
9
x
21
+
2
x
23
+ 3
x
24
+ 11
x
31
+ 2
x
32
+
x
34
+ 3
x
42
+
x
43
Kendala :
x
12
+
x
13
= 1
y
02
+
y
20
= 1
y
03
+
y
30
= 1
y
04
+
y
40
= 1
x
43
= 1
y
10
+
y
20
+
y
30
+
y
40
= 1
V
2
5
5
Z
= 1,
6
x
01
+ 2
x
02
+
3
x
03
+
1
1
x
04
+
1,
6
x
10
+ 2
x
13
+
2
x
20
+
x
23
+ 3
x
30
+ 2
x
31
+
x
32
Kendala :
x
01
+
x
02
+
x
03
= 2
x
13
= 1
x
20
+
x
23
= 1
x
30
+
x
31
= 2
Tab
l
e 2
and
Tab
l
e 3
exp
l
ain th
at OCVRP m
o
d
e
l b
y
ap
p
l
yin
g
prepro
cessin
g
techn
i
qu
e will y
i
eld
sim
p
l
e
r OC
V
R
P m
odel
co
m
p
ared t
o
m
odel
by
not
a
p
pl
y
i
ng t
h
at
t
echni
que
by
s
h
o
w
i
n
g t
h
e
re
du
ct
i
on i
n
num
ber
of
i
t
e
r
a
t
i
on a
n
d
re
d
u
c
t
i
on i
n
n
u
m
b
er
of c
o
nst
r
ai
nt
s
.
Fi
gu
re
1 bel
o
w sh
o
w
s
us t
h
e com
p
ari
s
o
n
bet
w
ee
n OC
V
R
P m
odel
bef
o
re a
n
d aft
e
r
appl
y
i
n
g
t
h
e
pre
p
r
o
cessi
ng
and
pr
obi
ng t
e
chni
que
.
W
e
c
a
n see t
h
at
t
h
e num
ber o
f
i
t
e
rat
i
on, va
ri
abl
e
and c
onst
r
ai
nt
red
u
ce
si
gni
fi
ca
nt
l
y
aft
e
r ap
pl
y
i
ng t
h
e pr
ep
roce
ssi
ng t
ech
ni
q
u
e.
For e
x
am
pl
e, in t
e
rm
of num
ber o
f
va
ri
abl
e
, we
have
t
r
em
endo
us
red
u
ct
i
o
n i
n
n
u
m
b
er o
f
var
i
abl
e
s aft
e
r
ap
p
l
y
i
ng t
h
e
p
r
ep
r
o
cessi
n
g
a
n
d
p
r
o
b
i
n
g t
e
c
hni
q
u
e.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
AA
S I
S
SN
:
225
2-8
8
1
4
The
Prep
r
oces
si
ng
a
n
d
Pr
o
b
i
n
g
Tec
hni
que
of
O
p
e
n
C
a
p
a
c
i
t
a
t
e
d Ve
hi
cl
e Ro
ut
i
n
g
Pr
obl
e
m
(
I
r
m
ei
l
y
a
na)
19
9
Fi
gure 1.
C
o
m
p
ari
s
on of
N
u
mber of Iter
at
i
o
ns, V
a
ri
a
b
l
e
s
an
d Co
sntr
a
i
nts
B
e
f
o
re an
d
A
fter
A
p
pl
y
i
ng
Preproces
sing and
Pr
obin
g Techniques
4.
CO
NCL
USI
O
N
We ca
n c
oncl
ude
t
h
at
by
a
ppl
y
i
n
g
pre
p
r
o
cessi
n
g
t
e
hcn
i
que i
n
t
h
e
p
r
obl
em
of t
r
a
n
spo
r
t
i
n
g t
h
e
ru
b
b
i
s
h,
t
h
e
si
m
p
l
e
r OC
VR
P
m
odel
can
be
obt
ai
ne
d,
t
h
e
f
a
st
er o
p
t
i
m
al
sol
u
t
i
o
n ca
n
be
achi
e
ve
d c
o
m
p
ared
t
o
n
o
t
app
l
yin
g
t
h
e
p
r
ep
ro
cessi
n
g
techn
i
qu
e.
In
ad
d
ition
,
b
y
ap
p
l
ying
th
e
prepro
cessing
tech
n
i
q
u
e
, th
e
nu
m
b
er
o
f
iteratio
n and con
s
train
t
is also
redu
ced
.
ACKNOWLE
DGE
M
ENTS
Thi
s
re
searc
h
was
part
i
a
l
l
y
sup
p
o
rt
e
d
by
H
i
bah B
e
rsai
n
g
Gra
n
t
o
f
Di
re
ct
orat
e
Gene
ra
l
of
Hi
g
h
e
r
Education
of Indonesia (DIKTI) year
2011. The authors
would als
o
like to
thank t
o
the editor and referees
fo
r thei
r
valua
b
le com
m
en
ts an
d su
gg
estion.
REFERE
NC
ES
[1]
Letchford, A.N
.
, J. Ly
s
g
aard
.,
an
d R.W
.
Egl
e
s
e
.
A branch and
cut algorithm for capacita
ted o
p
en veh
icle routing
problem
,
2006.
[cited
2009 11
July
]
;
Availab
l
e f
r
om: http
://www.lan
c
s.ac.uk/staff
/le
tchfoa/articles
/
ovrp/pdf.
[2]
Savelsbergh, M.W.P. “Prepro
cessing and probin
g
techn
i
ques for
mi
xed integer
programming problems”,
ORSA J.
on Computing
, Vol
.
6
. Pp. 445-
454, 1994
.
[3] Nemhauser,
G.L.
and
L
.
A. W
o
l
s
e
y
,
Int
e
ger and
Combinatorial
Optimization
, C
a
nada: John Wiley
& Sons, In
c,
1999.
[4]
Irmeily
ana, et
al. “Analisis Pengg
unaan Model SCVR
P untuk Men
e
ntukan Rute Optimal
Transportasi Pengangkutan
Sampah di Kota Palembang”
, L
aporan Penelitian Hibah Pe
nelitian PHK A2 Ju
rusan Matematika FMIPA Unsri
.
2007.
[5]
S
a
ri, Y.M
., Indr
awati
,
and Irm
ei
l
y
ana
.
“
P
enerap
an
Model Open Capacitated Vehi
cle Routing Problem (OCVR
P
)
dalam Mencari
Rute Minimum Transporta
si Pen
g
angkutan S
a
mpah di Kecamatan
Sako Kota Palembang, in Jurus
a
n
Matem
a
tik
a”
,
S
k
ripsi S1
,
Jurusan Matematika FMIPA Univ
ersitas Sriwijay
a
: Ind
r
alay
a, 2009.
[6]
Nuratika
,
Indra
w
ati,
and Irm
ei
l
y
ana
.
“
P
enentu
an Rute M
i
n
i
m
u
m
Open Capacit
a
ted Veh
i
c
l
e
Routing P
r
obl
em
(OCVRP) pada Masalah Tr
ansporta
si Sampah
di Kota Palembang,
in
Jurusan Matem
a
tik
a F
M
IPA,
Skripsi S1
,
Universitas Sriw
ijay
a
, 2009.
[7]
Irmeily
ana, F.M
.
Puspita,
and In
draw
ati. “The d
e
termination of
optimal r
oute of
open cap
acitated vehicle rou
tin
g
problem (OCVRP) on garbage transpor
tation
model in Ke
camatan Seber
a
ng Ulu II Kot
a
Palembang”,
in
Proceed
ing of In
ternational Conf
erence on
App
lie
d Analysis and A
l
gebra (
I
CAAA)
2011.
Yildiz University
, Istanbul,
2011.
[8]
Irmeily
ana, et al. “Modeling an
d Optimal Solution of
Open C
a
pac
ita
ted Veh
i
cle R
outing Problem (Ocvrp) in
Garbage Tr
ans
portation in Ke
ca
m
a
tan
Seberang
Ulu I Kota Palembang”,
Austr
a
lian Journal of Basic and Applied
Scien
ces
,
Vol/Is
s
ue:
5
(5). Pp. 9-
17, 2011
.
0
5
10
15
20
25
30
35
40
45
iteration
v
ariable
c
onstraint
i
teration
variable
constraint
before
applying
preprocessing
a
fter
applying
preprocessing
9
24
7
44
6
6
21
8
2
5
6
6
42
11
4
8
9
6
20
8
2
66
3
12
6
2
55
I
II
III
IV
V
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
252
-88
14
IJAAS
Vol. 2, No.
4, Decem
ber :
193
–
200
20
0
[9]
Irm
eil
y
ana
,
et
al
. Preprocessing t
echniqu
es in SCVRP
m
odel: cas
e of rubbish tran
sportation probl
em
in Kecam
ata
n
Ilir Bar
a
t II Palembang South Su
matera Indon
esia”
,
International Journal of Ad
van
ces in App
lied
Scien
ces(
I
JAAS
)
,
Vol/Issue:
1
(3)
.
Pp. 108-115, 20
12.
BIOGRAP
HI
ES OF
AUTH
ORS
Irmeily
ana r
e
ceived her S.Si
(U
ndergraduate Degree in Scien
ce)
in Mathematics
from Bogor
Agricultur
e
Institute (IPB) Ind
onesia in
1997.
Then
she r
e
ceiv
e
d her
Master Degr
ee
in
Mathematics from Bandung Technolog
y
Institute (ITB) Indones
i
a in 1999. Sh
e has been
a
M
a
them
ati
c
s
Departm
e
nt m
e
m
b
er at F
acul
t
y
M
a
them
ati
c
s
and Natural S
c
ie
nces
S
r
iwija
ya
University
South Sumatera Indonesia. Her r
e
sear
ch
inter
e
sts include Sta
tistics, o
p
timization and
its app
lic
ations
.
Fitri Ma
ya Puspita re
ceiv
e
d her
B.S. degre
e
in
Mathem
ati
c
s from
Sriwija
y
a
Un
iversit
y
, South
Sumatera, Indo
nesia in 1997. Then she receiv
ed her M.Sc in Mathematics from Curtin
University
of
Technolog
y
(CUT)
Western Australia
in 2004
. She
is curren
t
ly
PhD
cand
i
date of
F
acult
y of S
c
ie
nce and
Te
chno
log
y
Is
lam
i
c S
c
ie
nc
e Universi
t
y
of Mala
ysi
a
(
U
SIM), Nilai,
Negeri Sembilan Darul Khusus,
Malay
s
ia. She ha
s
been a M
a
them
atics
Depart
m
e
nt m
e
m
b
er at
Faculty
mathematics and
Natural Scien
ces Sriwijay
a
Univ
ersi
ty
S
outh Sumatera I
ndonesia sin
ce
1998. Her research interests in
cl
ude optimizatio
n and its
app
l
ications such as v
e
hicle routing
problems and Q
o
S pricing
and
charging
in th
ird
generation
intern
et.
Indrawati
re
ceiv
e
d her rece
ived
her B.S
.
degre
e
in M
a
them
ati
c
s
from
S
r
iwijaya Unive
r
s
i
t
y
,
South Su
matera, Indonesia in 1996. Then she r
eceived M.Si in
Mathematics Actuar
ial from
Bandung Institut
e
of Technolog
y, Indonesia in 2
004. She has been a Math
em
ati
c
s Departm
e
n
t
m
e
m
b
er at Fac
u
lt
y m
a
them
at
ic
s and Natura
l
Scienc
es Sriwij
a
y
a Unive
r
sit
y
South Sum
a
tera
Indonesia since 1998.
Her research
interest includes actu
a
rial scie
nce and its appl
ications in
insurance and
ris
k
theor
y
.
Fitra Nur Az
iza
h
rec
e
ived
her
B.S. degr
ee
in
Mathem
ati
c
s fro
m
Sriwija
ya Un
iversit
y
,
South
Sumatera, Indon
esia in 2011. Her research interest
includes Optimization
,
Graph Theor
y
and its
applications.
Evaluation Warning : The document was created with Spire.PDF for Python.