Indonesian J
ournal of Ele
c
trical Engin
eering and
Computer Sci
e
nce
Vol. 2, No. 1,
April 201
6, pp. 180 ~ 18
6
DOI: 10.115
9
1
/ijeecs.v2.i1.page
s
180
Re
cei
v
ed
De
cem
ber 2
4
, 2015; Re
vi
sed
March 5, 201
6; Acce
pted
March 19, 20
16
Optimization of Ship’s Route Scheduling Using Genetic
Algorithm
Viv
i
Nur Wijay
a
ningrum*,
Wa
y
a
n Firdaus Mahmud
y
F
a
cult
y
of Com
puter Scie
nce,
Bra
w
ij
a
y
a U
n
iv
ersit
y
Jala
n Vetera
n 8, Malan
g
, Ind
ones
ia, Ph./F
ax:+
62
341-
57
79
11
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:vivinur
w
@
gm
ail.com
A
b
st
r
a
ct
Route sch
ed
uli
ng is a q
u
ite c
o
mplic
ated
pro
c
ess bec
a
u
se
it involv
es so
me
deter
mi
na
nt factors.
Severa
l metho
d
s hav
e be
en
used to h
e
lp
resolve th
e N
P
-hard pr
ob
le
ms. T
h
is rese
arch uses
ge
n
e
ti
c
alg
o
rith
m to assist in opti
m
i
z
i
ng shi
p
sched
ulin
g, that
w
here there are se
veral ports to b
e
visited by so
me
ships. T
he
go
a
l
is to div
i
d
e
th
e shi
p
to go t
o
a spec
if
ic port
so that eac
h p
o
rt is only v
i
sit
ed by
one s
h
i
p
to
mi
ni
mi
z
e
th
e t
o
tal
distanc
e
o
f
all s
h
i
p
s. T
h
e
co
mp
ut
ation
a
l
exp
e
ri
me
nt pr
oduc
es o
p
ti
ma
l
par
ameters s
u
ch
as the n
u
m
b
e
r of pops
i
z
e
is
3
0
, the nu
mber
of gen
erati
ons
is 10
0, crosso
v
e
r rate va
lue
is
0.3 an
d
mutati
o
n
rate valu
e is 0.7. T
he final res
u
lt is an opti
m
a
l
ship ro
ute by mi
ni
mi
z
i
ng th
e distanc
e of eac
h ship.
Ke
y
w
ords
: ge
netic al
gorith
m
,
ship, route
Copy
right
©
2016 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
In the area of communi
cati
on and tran
sp
ortation, the proble
m
s con
c
ernin
g
the ro
ute and
sched
uling
is
an a
r
e
a
of
extensiv
e
rese
arch. T
he
stabl
e e
c
on
omic g
r
owth
in
trad
e
re
sultin
g in
a
n
increa
sed
ne
ed for t
r
an
sp
ort of go
od
s. There a
r
e f
our type
s of
mode
s of tra
n
sp
ort a
r
e of
ten
use
d
for deliv
ery of good
s, namely
tru
c
ks, train
s
, plan
es, and
ship
s.
Indone
sia wit
h
more than
18,000 isl
and
s, is the large
s
t archipel
ag
o in the world
[1]. With
so many isl
a
nds in Ind
one
sia, the manu
facture
r
s
often cho
o
se to use the
ship i
n
orde
r to se
nd
good
s
pro
d
u
c
tion bet
wee
n
islan
d
s.Mo
st
ship
s
are
u
s
e
d
to d
e
liver th
e go
od
s a
s
si
gn
ship
s to
th
e
wee
k
ly frequ
ency for lo
ng-distan
ce
ship
ping servic
es. As a result, the good
s to be se
nt must
be
store
d
in wa
rehou
se
s or i
n
port before
hand, ca
u
s
in
g increa
sed
co
sts for sto
r
age. To red
u
c
e
these co
sts, plan
of ship
servi
c
e
of go
ods
shi
ppe
rs is exp
e
cte
d
to be o
p
timized i
n
terms of
sched
ule
s
an
d allocatio
n
of ship
s on some
rout
e
s
[2]. Fuel cost has the hi
ghe
st cal
c
ula
t
ion
prop
ortio
n
a
m
ong th
e va
rious op
eratio
nal
co
sts
of
sea
shippin
g
. Hig
h
fuel
co
nsum
ption
gi
ves
adverse imp
a
c
t on the e
n
vironm
ent be
cause it pro
d
u
c
e
s
CO
2
and
NO
x
emission
s that cau
s
e
air
pollution and
c
limate alteration [3] [4].Therefore,
s
h
ip
'
s
route
sch
e
d
u
ling i
s
i
m
po
rtant to b
e
ta
ke
n
to minimize t
he travel dist
ance so that the f
uel co
nsu
m
ption ca
n b
e
as little as p
o
ssible.
In the previou
s
re
sea
r
ch, genetic alg
o
rit
h
m is use
d
to determine th
e allocatio
n
o
f
berths
for co
ntaine
r ship
s in the
harb
o
r. The
purp
o
se of this allo
catio
n
plannin
g
is
to minimize t
h
e
amount of tim
e
se
rvice fo
r
each ship [5]. A simila
r
stu
d
y con
ducte
d
to optimize t
he sch
edulin
g of
the train ro
ute usin
g genet
ic algo
rithm
s
with arti
ficial neural
networks with
the ai
m of minimizi
ng
the delay time [6]. Each gene on
ch
ro
moso
me de
sc
rib
e
s a train
that is assig
ned to a ro
ute
whi
c
h i
s
rep
r
ese
n
ted by t
he value
of its ge
ne
s [7].Geneti
c
alg
o
rithm is
also
use
d
to o
p
timize
route
of
stacker i
n
a
u
tomati
c
wa
reh
o
u
s
e
becau
se
sta
c
ker
can
not
in
cre
a
se it
s
sp
eed
so
it ta
ke
s
much
time i
n
the p
r
o
c
ess o
f
tran
spo
r
tation g
ood
s [8].
In this
study, gen
etic
algo
rithm is u
s
ed
to
optimize th
e
ship’
s
route
s
che
duling
be
cau
s
e
gen
etic alg
o
rithm
h
a
ve a po
we
rto pro
d
u
c
e g
o
o
d
solutio
n
sfo
r
somereal
com
p
lex p
r
oble
m
s [9] [1
0]. T
h
is
pap
er prese
n
ts
a m
o
del to
solve
the
probl
em of
sche
duling
a
port visit to
minimize th
e
distan
ce
so
that the fuel
con
s
u
m
ptio
n is
redu
ce
d. The
prop
osed
sol
u
tion is tryin
g
to save
fuel
con
s
um
ption
of each ship
along th
e wa
y to
visit all the ports.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 25
02-4
752
IJEECS
Vol.
2, No. 1, April 2016 : 180 –
186
181
2. Genetic
Algorithm
Geneti
c
algo
rithms mimi
c the process o
f
bi
ological e
v
olution to so
lve a probl
e
m
, which
solutio
n
wa
s formed con
s
istin
g
of se
veral po
ssi
bl
e solutio
n
s [
6
]. Genetic
Algorithm (G
A)
,
develop
ed by
Holla
nd in 1
975, is
an o
p
t
imization
a
n
d
se
arch m
e
thod b
a
sed o
n
the pri
n
ci
pl
e of
the evolution
theory. In the
GA, the solu
tion
gen
erate
d
ra
ndomly.
The GA
save
s the
popul
ation
of po
ssibl
e
solutio
n
s fo
r seve
ral g
e
neratio
ns.
T
he po
pulatio
n consi
s
t
s
of a st
ring
of
chromo
som
e
s. A chromo
some con
s
ist
s
of a numbe
r of gene
s. In a populatio
n
,
the numbe
r
o
f
gene
s in a chrom
o
some i
s
usually the same a
s
the other chro
moso
me
s. Each ge
ne ha
s a
nume
r
ical value of binary o
r
intege
r. The
GA pr
ocess
begin
s
by sel
e
cting a p
a
re
nt chro
mo
so
me
based on it
s fitness valu
e that de
scri
bes th
e
quali
t
y of the chromosome. T
hen the d
e
scent
solutio
n
pro
d
u
ce
d by cro
s
sover a
nd mu
tation [11].
In contra
st to other optimi
z
ation meth
o
d
s,
geneti
c
a
l
gorithm can
be calle
d efficient in
solving
probl
ems with
the
extensive
se
arch
are
a
.
Th
ere
is no
gu
a
r
antee
that th
e result obtai
ned
from gen
etic algorithm is an optimal solutio
n
, but this algo
rith
m can p
r
ovide an acce
p
t
able
solutio
n
with reasona
ble proce
s
sing time
[6].
3. Rese
arch
Metho
d
The definitio
n
of a sche
dul
ing proble
m
can
be
exem
plified that th
ere a
r
e
a nu
mber
of
ship
s that ha
ve different capa
cities. Ea
ch ship se
nd
s goo
ds from
one port to the other
with
a
certai
n dista
n
c
e.
In this ca
se, there a
r
e 2
1
p
o
rts to be visi
ted by three ships
whi
c
h is
sho
w
n in Ta
b
l
e 1.
Table 1. Port
Visited
Number
Port
Name
1 Ambon
2 Balikpapan
3 Bengkulu
4 Cilacap
5 Cirebon
6 Gresik
7 Jakar
t
a
8 Jambi
9 Kalianget
10 Kupang
11 Makassar
12 Manado
13 Medan
14 Palembang
15 Panjang
16 Pekanbaru
17 Pontianak
18 Sabang
19 Samarinda
20 Semarang
21 Sorong
3.1. Chromo
somes Repr
esen
tatio
n
The first step in building GA is to
defi
ne the exa
c
t representati
on of
chrom
o
som
e
s
(en
c
odi
ng
). A good
chro
moso
me
s re
pre
s
entatio
n
is
very im
po
rtant be
cau
s
e
it will affe
ct the
effectivity of
GA in explor
i
ng the se
arch
spa
c
e [12].
On this issu
e
,
the chrom
o
some i
s
re
pres
e
n
ted u
s
in
g a perm
u
tation that describes the
seq
uen
ce of
ports th
at sh
ould be visite
d by ev
ery sh
ip. Chromo
so
mes that may
be establi
s
h
ed
are:
[21 12 18 8 3
6 7 2 1 10 11
17 9 20 5 15
13 16 14 1
9
4
]
Based
on the chromosom
e
representati
on, t
he possi
b
ility of routes could
be set up for
each shi
p
so
that each po
rt is only visited by
only one shi
p
in the delivery proce
s
s, sho
w
n in
Table 2.
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4
752
Optim
i
zation of Ship
’
s
Rou
t
e Scheduli
n
g
Usin
g Gen
e
tic Algorithm
(Vivi Nu
r Wija
yani
ngrum
)
182
Table 2. Ro
ute of Each Shi
p
Ship Route
1 0
→
21
→
12
→
18
→
8
→
3
→
6
→
7
→
0
2 0
→
2
→
1
→
10
→
11
→
17
→
9
→
20
→
0
3 0
→
5
→
15
→
13
→
16
→
14
→
19
→
4
→
0
Po
r
t
in
Su
r
aba
ya
is
as
su
me
d
a
s
the initial location of all ships, whi
c
h i
s
represented by
the numbe
r 0
.
Each ship h
a
s sequ
en
ce
s list of port
s
to be visited. The digit is written after dig
i
t 0
is the
po
rt n
u
mbe
r
that
should
be
visi
ted by
eve
r
y
shi
p
. After v
i
siting
all p
o
rts ba
se
d o
n
the
sequences list, all of
the ships will end at
the port in Surabaya.
In the exampl
e, the ship
1
will ma
ke trip
from the po
rt
in Surab
a
ya
and then to S
o
ron
g
,
Manad
o, Sab
ang, Jam
b
i, Beng
kulu, Gre
s
ik,
Jakarta,
and then b
a
ck agai
n to Surabaya.
3.2. Fitness
Function
In the previo
us
study, the func
tion
of fitness value i
s
cal
c
ulated
u
s
ing th
e total distan
ce
traveled a
nd t
i
me of service on a
n
y po
rt as a
refe
ren
c
e in calculatin
g the fitness
value[13]. Wh
ile
in this study, a modified fitness fun
c
ti
on use
d
is a
calcul
ation
based on th
e total distance
traveled by al
l the ship
s, so
the fitness
fu
nction u
s
e
d
is formulated in
Equation 1.
R
rV
V
n
n
n
r
r
d
D
F
1
,
10000
(1)
whe
r
e
r
i
s
a
route in
clu
ded
in
R
,
R
is a
colle
ction
of routes,
n
i
s
a
port i
s
in
clu
d
ed in
Vr
,
Vr
is
a
colle
ction of
node
s in
clud
ed in the rout
e
r
,
m
is a ports a
r
e in
clud
ed in
V
,
V
is a colle
ction o
f
the
visited port
s
, and
d
r,(n-1)n
is
the dis
t
ance between port
s
(1, 2, ...,
n
) of route
r
.
A list of the
d
i
stan
ce
between
port
s
in
Indon
es
i
a
a
r
e
sh
own in
Ta
ble 3. T
h
e
s
e
distan
ce
data are ta
ke
n from www.
sea-di
stan
ce
s.
org which me
asu
r
ed in n
a
u
t
ical miles.
Table 3. Di
stance betwee
n
Ports
in Ind
one
sia (n
auti
c
al mile
s)
Port Name
Ambon
Balikpapan
Bengkulu
Cilacap
...
Semarang
Sorong
Suraba
ya
Ambon 0
885
1651
1232
...
1114
346
980
Balikpapan 885
0
1103
883
...
583
1025
481
Bengkulu 1651
1103
0
532
...
568
1896
726
Cilacap 1232
883
532
0
...
631
1500
689
... ...
...
...
...
...
...
...
...
Semarang
1114
583
568
631
...
0
1359
194
Sorong
346
1025
1896
1500
...
1359
0
1253
Suraba
ya
980
481
726
689
...
194
1253
0
Based
on da
ta from Tabl
e 3, fitness
value ca
n b
e
cal
c
ulate
d
usin
g Equati
on 1 a
s
follows
:
6105
.
0
5006
4462
6912
10000
F
3.3. Cross
o
v
e
r
Cro
s
sove
r is
a ge
netic
op
erato
r
u
s
ed
to
ge
nerate n
e
w
ch
romo
so
mes
by sele
cting two
pare
n
ts to do
cro
s
sover. Crossove
r mea
n
s exchan
ge
a part of ch
ro
moso
me 1 wi
th another p
a
r
t
of chrom
o
so
me 2. Chrom
o
som
e
pro
d
u
c
ed coul
d b
e
better than both parents.
The 3 types of
cro
s
sove
r are
single p
o
int (1-poi
nt), 2-p
o
i
nt and 4-p
o
in
t [11].
In this rese
arch, 1-p
o
int crossover meth
od is
used be
cau
s
e this m
e
thod is sim
p
le [6].
In
this metho
d
, the two
chro
moso
me
s will
be ch
osen a
t
rando
m, the
n
one
cut poi
nt also
sele
ct
ed
rand
omly a
s
the exch
ang
e
limit of gene
s on
both
ch
romosome
s to
pro
d
u
c
e o
n
e
ch
romo
so
m
e
offsprin
g for e
v
ery one cro
s
sover p
r
o
c
e
s
s. Figure 1 illustrate
s the 1
-
point cro
s
so
ver.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 25
02-4
752
IJEECS
Vol.
2, No. 1, April 2016 : 180 –
186
183
Parent 1
0
1
2
3 5 4 6
7
Parent 2
0
3
4
6 2 1
5
7
Offspring
0
1
2
3
4
6
5
7
Figure 1. 1-p
o
intCrossove
r
3.4. Mutation
Mutation o
p
e
r
ator are u
s
e
d
to mai
n
tain
the dive
rsity
of the p
opula
t
ion so a
s
to
expand
the sea
r
ch area and h
e
lp the se
arch al
gorithm o
u
t from local opti
m
um sol
u
tion
s [14]. Mutation
method
used
in this
re
sea
r
ch
is
swap
pi
ng mutatio
n
whi
c
h i
s
do
n
e
by sel
e
ctin
g two g
ene
s
on a
chromo
som
e
rand
omly, the
n
exch
ange t
hose two
gen
es [15]. Figu
re 2 illust
rate
s the pro
c
e
s
s
o
f
swappi
ng mu
tation.
Parent
0
1 3
4 6 2 5
7
Offspring
0
4 3
1 6 2 5
7
Figure 2. Swappin
g
Mutation
3.5. Selectio
n
Selection i
s
an impo
rtant
part of the
geneti
c
alg
o
rithm b
e
cau
s
e it can aff
e
ct the
conve
r
ge
nce
rate. Th
e se
lection
metho
d
used i
s
elit
ism sele
ction
.
The
ba
si
c prin
ciple of
the
elitism
sele
ction is
ch
oo
sin
g
a chromo
some that
h
a
s the be
st fitness value.
Chrom
o
some
s
with
the best fitne
ss valu
e ch
osen will have a
chan
ce to su
rvive in the next generatio
n [16].
4. Results a
nd Discu
ssi
on
Test
s ca
rrie
d
out on the param
et
ers that are used i
n
geneti
c
alg
o
rithm, whi
c
h
con
s
ist
s
of testing
pop
size
, testing the numb
e
r of
generation
s
, testing the crossove
r rate
(
cr
)
va
lu
e
,
an
d
tes
t
ing the mutation rate (
mr
) value.
Testing
po
psi
z
e
i
s
used to
dete
r
mine
th
e num
be
r of
chromo
som
e
s in
o
r
de
r to
prod
uce
the be
st opti
m
al solution i
n
this
pro
b
le
m. The n
u
mb
er of
po
ps
ize
to be te
sted a
r
e 1
0
, 20, 30,
40,
and 50.
T
h
e
numbe
r of
g
e
neratio
ns
i
s
150, we
re
ob
tained f
r
om
p
r
eviou
s
re
sea
r
ch
[17].
Whil
e
the
cr
and
mr
value used
are 0.4
and 0
.
05, whi
c
h is
t
he re
sult of tests
co
ndu
ct
ed by Iliopoul
ou
[18].
Popsize
trials pe
rform
ed 5 times wit
h
t
he test re
sults sh
own in Figure 3.
Figure 3. The
Result of Testing
Pops
ize
The graph of
testing results in Figu
re 3
sho
w
that mo
re and m
o
re
pop
size
, the averag
e
fitness value
generated will likely incr
ease. In general, by incre
a
sin
g
pop
size
, fitnes
s
values
0.798
0.829
0.963
0.974
1.004
0.700
0.800
0.900
1.000
1.100
10
20
30
40
50
A
v
e
r
ag
e F
i
tn
ess
Valu
e
Pops
ize
Testing
Popsize
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4
752
Optim
i
zation of Ship
’
s
Rou
t
e Scheduli
n
g
Usin
g Gen
e
tic Algorithm
(Vivi Nu
r Wija
yani
ngrum
)
184
obtaine
d will be better be
cause of gene
tic algorithm
has a b
r
oa
de
r sea
r
ch area
. Howeve
r, at a
certai
n p
o
int, the fitne
s
s
value d
oes
not in
cre
a
se
sig
n
ifica
n
tly.The ave
r
a
g
e
fitness valu
e of
pop
size
1
0
to
30
incre
a
sed
,
while
the
av
erag
e valu
e
of fitness
wit
h
a
num
ber a
bove 3
0
ten
d
to
be stabl
e. This sh
ows that
30 is the mo
st optimal
pop
size
.
The second t
e
sting i
s
the t
e
sting
of gen
erat
ion
numb
e
r, whi
c
h i
s
u
s
ed to d
e
termine the
best nu
mbe
r
of gene
ration
s to produ
ce
the optimum
solution i
n
this p
r
obl
em. The num
be
r of
pop
size
whi
c
h is u
s
ed i
s
3
0
, is used to
test the num
ber of thi
s
ge
neratio
n be
ca
use th
e num
ber
can b
e
co
nsi
dere
d
an ave
r
age yield the
most optimal
fitness value.
While the val
ue of
cr
an
d
mr
,
usin
g the limi
t
values
used
in the
previo
us tr
i
a
ls. T
h
e
trial results
gene
ration
a
m
ount
sho
w
n
in
Figure 4.
Figure 4. The
Result of Testing Ge
neration Num
b
e
r
The gra
ph o
f
testing in
Figure 4 sho
w
s
that the more the ge
neratio
n num
ber, the
averag
e fitne
ss valu
e ge
n
e
rated
will likely incr
ea
se. The average
fitness valu
e
in gene
ration
20
to 100 increa
sed, whil
e the averag
e fitness va
lue wit
h
the generation numb
e
r in
over 100 ten
d
s
to be sta
b
le.
This in
dicates that the 1
00 is
the
mo
st optimal g
e
neratio
n num
ber. Pattern
of
increa
se fitne
ss valu
e whi
c
h is com
p
a
r
a
b
le to
the increase of gene
ration numb
e
r
wa
s also foun
d
in the research entitled "
G
enet
i
c
and
Particle Swarm Hybrid Qo
S Anycast Routing Algorit
hm"
[19].
The la
st te
sti
ng i
s
the
testi
ng of
cr
and
mr
value, whi
c
h i
s
used to
determine
th
e be
st
cr
and
mr
value
to prod
uce the optimum
solution in thi
s
probl
em. Th
e
pop
size
whi
c
h is
used is
30
and the g
ene
ration n
u
mbe
r
used is
100
beca
u
se it was con
s
ide
r
e
d
the numb
e
r could
pro
d
u
c
e
the most opti
m
al avera
ge
fitness valu
e. The
cr
and
mr
value which is used in thi
s
test ch
osen
by
considering
cr
and
mr
value
at each test
scena
rio fo
r a
total amou
nt equal to
1 be
cau
s
e th
e tests
perfo
rmed m
u
st be fair,
whi
c
h mea
n
s the offsprin
g numbe
r p
r
odu
ced in e
a
ch te
st sce
nario
sho
u
ld have t
he sam
e
total amount. The
trial re
sults g
eneration nu
mber
sho
w
n i
n
Figure 5.
Figure 5. The
Result of Testing
cr
and
mr
Value
0.677
0.786
0.835
0.838
0.909
0.925
0.934
0.936
0.924
0.925
0.600
0.700
0.800
0.900
1.000
20
40
60
80
100
120
140
160
180
200
A
v
e
r
ag
e F
i
tn
ess
Valu
e
Ge
ne
ra
tion Numbe
r
Testing Generation Number
1.097
1.000
1.133
1.050
1.090
1.049
1.023
1.007
0.929
0.800
0.900
1.000
1.100
1.200
0.1
0
.2
0.3
0
.4
0.5
0
.6
0.7
0
.8
0.9
A
v
e
r
ag
e F
i
tn
ess
Valu
e
cr
Value
Testing
cr
and
mr
Value
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 25
02-4
752
IJEECS
Vol.
2, No. 1, April 2016 : 180 –
186
185
The te
sting
result
s of
cr
a
nd
mr
value
s
in Fig
u
re
5
shows th
at the
be
st
cr
a
nd
mr
value
to produ
ce th
e optimal sol
u
tion is 0.3 f
o
r
cr
and 0.7
for
mr
. The high value of
cr
will provi
d
e
many ne
w ch
romo
som
e
in
the popul
atio
n. However, i
f
the
cr
value
is too hig
h
, a grou
p of gen
es
that ca
uses
the be
st fitn
ess
valu
e d
oes not
hav
e a
ch
an
ce
to stick to
o
ne a
nothe
r i
n
a
chromo
som
e
, which mea
n
s
that these
gene
s are
m
o
st likely to separate and
cau
s
e the fitn
ess
value b
e
com
e
s
sm
aller.
In
co
ntra
st, if t
he
cr
value
is too l
o
w, it
do
es
not
pro
d
u
c
e
ne
w
offspring
with a suffici
e
n
t amount [20
]
.
Table
4
sho
w
s the
re
sult
s
given by the
syst
em
by u
s
ing the
optim
al pa
ramete
r
values
whi
c
h h
a
ve b
een o
b
taine
d
from the te
st
re
sults
co
nsi
s
ting of the
n
u
mbe
r
of
p
ops
ize
is
30, the
gene
ration n
u
m
ber i
s
100,
cr
value i
s
0.3 and
mr
values is 0.7, with
the fitness value is 1,0
99.
Table 4. The
Re
sult Using
the Optimal Param
e
ter Val
ues
Ship Route
1 0
→
20
→
16
→
13
→
18
→
8
→
14
→
17
→
0
2 0
→
10
→
1
→
21
→
12
→
11
→
19
→
2
→
0
3 0
→
5
→
7
→
15
→
4
→
3
→
6
→
9
→
0
The result
s in
Table 4 expl
ains that the
seq
uen
ce of
ports th
at sh
ould be vi
site
d by the
ship
1
are S
u
rab
a
ya, Se
mara
ng, Pe
kanba
ru, M
e
d
an, Sab
ang,
Jambi,
Pale
mbang,
Ponti
ana
k,
and ba
ck a
g
a
in to Suraba
ya. The sequ
ence of ports
to be visited by the ship 2 are Suraba
ya,
Kupang, Am
bon, Sorong,
Manad
o, Maka
ssar, Sa
marin
da, Bal
i
kpa
pan, an
d
back ag
ain
to
Surab
a
ya. T
he
seq
uen
ce
of po
rts to
be visite
d by
shi
p
3
are
Surab
a
ya, Ci
rebo
n, Jakart
a,
Pajang, Cila
cap, Bengkulu,
Gre
s
ik, Kalia
nget, and ba
ck agai
n to Surabaya.
Table
5 sho
w
s
a
comp
a
r
iso
n
b
e
twee
n the fitne
s
s value of
ra
ndom
sche
d
u
ling a
nd
sched
uling
which
is do
ne
by usi
ng
a g
e
netic
algo
rit
h
m.
The
re
sult
s
sho
w
e
d
t
h
e
shi
p
sc
hed
ul
ing
usin
g gen
etic algorithm g
e
nerate
s
an av
erag
e
fitness values hi
ghe
r than rand
om
sch
eduli
ng.
Table 5. Co
m
pari
s
on Fitn
e
ss Valu
e
T
r
ial
Number
Fitness Value of Random
Scheduling
Fitness Value of Scheduling
using Genetic Algorithm
1 0.6105
1.0990
2 0.5850
1.0452
3 0.4162
1.0307
4 0.4580
1.0654
5 0.6239
1.1119
Average
0.5387
1.0704
Geneti
c
algo
rithm is also
compa
r
ed
with
gr
eedy alg
o
rithm. Greedy
algorithm
starts by
sele
cting
a p
o
rt which h
a
s
the
shorte
st di
stan
ce
t
o
the i
n
itial l
o
catio
n
. A ro
ute create
d
by
sele
cting
the
next po
rt by
con
s
id
erin
g t
he di
stan
ce
of
the nea
re
st
port. Geneti
c
al
go
rithm a
l
so
gives high
er
averag
e fitness value tha
n
greedy al
go
rithm that is equal to 1.017
1. This prove
s
that the
shi
p
’
s
route
sch
e
duling
optimi
z
ation
u
s
ing
geneti
c
al
gori
t
hm is abl
e t
o
p
r
ovide
bet
ter
results with hi
gher fitne
ss v
a
lue by mini
mizing the di
stance.
5. Conclusio
n
Based
on
the
testing
re
sul
t
s, it wa
s
co
n
c
lud
ed th
at g
enetic alg
o
rit
h
ms
ca
n b
e
use
d
to
determi
ne the
ship'
s
ro
ute sched
uling u
s
ing dista
n
ce
data between
ports a
s
a fa
ctor to calcul
ate
the fitness va
lue. The be
st
algorithm p
a
r
amete
r
s
use
d
to gene
rate
the optimal
solutio
n
are
30
for
pop
size
, 100 for the ge
neratio
n num
ber, 0.3 for
cr
value, and 0.7 for
mr
value.
In the next study, the application of algo
rith
ms for
shi
p's route sch
edulin
g can b
e
don
e
by adding fu
el to the calculation of fitn
ess val
ue,
co
nsid
erin
g the
fuel used for each ship co
uld
have be
en dif
f
erent. In ad
d
i
tion, the use
of the re
quire
d t
i
me limit
o
n
ea
ch
ship t
o
v
i
sit
ea
ch p
o
rt
can
also
be
taken int
o
accou
n
t. With the growi
ng complexity of the pro
b
lem
s
, the solution
s
prod
uced m
a
y also b
e
mo
re
compl
e
x, so it need
s hybridi
z
ation of geneti
c
alg
o
ri
thm
with
oth
e
r
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4
752
Optim
i
zation of Ship
’
s
Rou
t
e Scheduli
n
g
Usin
g Gen
e
tic Algorithm
(Vivi Nu
r Wija
yani
ngrum
)
186
algorith
m
s to
produ
ce
a
better
sol
u
tio
n
. Exploiting
neig
hbo
rho
od
solutio
n
s usi
ng va
ria
b
le
neighborhood search
(VNS
) will be cons
i
dered in the next study [21].
Referen
ces
[1]
Ardhi
ans
ya
h A
.
Pembak
uan
Nama P
u
l
au
d
i
Ind
ones
ia s
e
bag
ai
up
a
y
a
u
n
tuk me
nja
ga
keda
ulat
an
Neg
a
ra Re
pu
bl
ik Indon
esi
a
.
J Pand
ecta
. 201
1; 6(1): 1-26.
[2]
W
ang H, W
a
n
g
S, Men
g
Q.
Simulta
neo
us opti
m
i
z
at
ion of sched
ule
coor
d
i
nati
on
and c
a
r
go a
lloc
a
tio
n
for liner co
ntai
ner shi
ppi
ng n
e
tw
orks
.
T
r
ansp Res Part E Logist T
r
ansp
Rev. Elsevier Lt
d. 2014; 7
0
:
261-
273.
[3]
W
en M, Ro
pk
e S, Peters
en
HL, L
a
rsen
R,
Madse
n
OBG.
Co
mp
uters &
Operatio
ns R
e
search F
u
ll-
shipl
o
a
d
tra
m
p
ship
ro
uting
a
nd sc
hed
uli
n
g
w
i
th varia
b
le
s
pee
ds
. Com
p
u
t
Oper Res. E
l
sevier.
201
6;
70: 1-8.
[4]
Rein
har
dt LB, Plum CEM, Pi
sing
er D, Sigu
rd MM, Vial GT
P.
T
he liner
ship
pin
g
berth
schedu
li
n
g
problem
with transit times
. T
r
ansp R
e
s Part E. Elsevier Ltd.
2016; 8
6
: 116-
128.
[5]
Arang
o C, C
o
rtés P, M
uñuz
uri J, Oniev
a
L.
Berth al
loc
a
tion
pla
n
n
i
ng
in Sev
ill
e i
n
l
and
port b
y
simulati
on a
nd
opti
m
is
ation
. A
d
v Eng Informa
tics. Elsevier Lt
d. 2011; 2
5
(3): 452-
461.
[6]
Dün
dar S,
Ş
ahin I.
T
r
ain re
-sched
uli
ng w
i
th genetic a
l
g
o
rith
ms an
d a
r
tificial ne
ura
l
netw
o
rks for
si
n
g
l
e
-
tra
ck ra
ilwa
ys
.
T
r
ansp Res Part C Emerg T
e
chnol. 2
013; 27: 1-
15.
[7]
Sun Y, Cao C,
W
u
C.
Multi-Objective Opti
mi
z
a
t
i
o
n
of T
r
ain R
outin
g Pr
obl
e
m
Co
mb
in
ed w
i
th T
r
ain
Sched
uli
ng
on
a H
i
gh-S
p
e
e
d
Rai
l
w
a
y Netw
ork
. T
r
ansp R
e
s Part C
Em
erg T
e
chno
l.
Elsevi
er Ltd;
201
4; 44: 1-20.
[8]
Cha
ngq
in
g C, Yiqi
ang W
.
Ro
ute Optimizati
o
n
of Stacker i
n
Automatic W
a
reho
use b
a
se
d
on Gen
e
tic
Algorit
hm.
T
E
LKOMNIKA Indones
ian J
ourn
a
l of Electrica
l
Engi
neer
in
g
. 2013; 11(
11): 63
67-6
372.
[9]
Mahmu
d
y
W
F
, Maria
n
RM, L
uon
g
LHS.
R
e
al C
o
d
e
d
Gen
e
tic Al
gorith
m
s
for So
lvin
g F
l
exibl
e
J
ob-
Shop Sch
e
d
u
li
ng Prob
le
m - Part II: Optimi
z
a
t
i
on
. Adv Mater
Res. 201
3; 701
: 364-36
9.
[10]
Mahmu
d
y
W
F
, Maria
n
RM,
Luo
ng
LHS.
H
y
brid
Gen
e
tic Algorithms f
o
r Multi-P
e
riod Part T
y
pe
Selecti
on a
nd
Machi
ne L
o
a
d
i
ng Pro
b
lems
i
n
F
l
e
x
ib
le M
a
n
u
facturin
g S
y
stem. In:
IEEE International
Confer
ence on
Computati
o
n
a
l
Intellig
enc
e an
d Cyber
netics
. 201
3: 126-
130.
[11]
Al-Hamad
K, Al-Ibrahim
M, Al-Enez
y
E.
A
Genetic
Alg
o
r
ithm for S
h
ip
Ro
uting
a
nd
Sched
uli
n
g
Probl
e
m
w
i
th Time W
i
nd
ow
. Am J Oper Res. 201
2; 02(0
3
): 417-4
29.
[12]
Mahmu
d
y
W
F
, Maria
n
RM, L
uon
g
LHS.
R
e
al C
o
d
e
d
Gen
e
tic Al
gorith
m
s
for So
lvin
g F
l
exibl
e
J
ob-
Shop Sch
e
d
u
li
ng Prob
le
m - Part I: Modellin
g
. Adv Mater Res. 2013;7
01:35
9-36
3.
[13]
Karlaftis MG, Kepa
ptsogl
ou
K, Sambrac
o
s E.
Conta
i
n
e
rshi
p routi
n
g
w
i
th time d
e
adli
nes
an
d
simulta
neo
us
deliv
eri
e
s an
d
pick-ups
. T
r
ansp Res P
a
rt E Logist T
r
ans
p Rev. Elsev
i
er Ltd; 20
09;
45(1): 21
0-2
2
1
.
[14]
Xu
e S, W
u
W
.
Sched
uli
ng W
o
rkflo
w
in C
l
ou
d
Com
puti
ng Ba
sed on
H
y
bri
d
Particle S
w
a
r
m
Algorithm
.
Te
lkom
n
i
ka
. 20
12; 10(7): 1
560
-156
6.
[15]
X
u
Y
,
L
i
K
,
H
u
J
,
L
i
K
.
A
genetic algorithm
f
o
r task schedul
ing on heter
oge
neous computing systems
usin
g multip
le
priority q
ueu
es
. Inf Sci (Ny
)
. Elsevier Inc. 20
1
4
; 270: 25
5-28
7.
[16]
Liu F
,
L
i
a
ng S,
Xia
n
X. Optim
a
l P
a
th Pl
an
ni
ng for M
o
b
ile
Rob
o
t Usi
ng T
a
ilor
e
d
Geneti
c
Algor
ithm.
T
E
LKOMNIKA Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2014; 1
2
(1): 1
-
9.
[17]
Rahm
an HF
,
Sarker R, Ess
a
m D.
Co
mp
u
t
ers & Industri
a
l En
gin
eeri
n
g
A gen
etic al
gorith
m
fo
r
per
mutati
on fl
o
w
shop sch
edu
ling
un
der
mak
e
to stock pr
od
uction syste
m
.
Comp
ut Ind En
g. Elsevi
e
r
Ltd. 201
5; 90: 12-2
4
.
[18]
Iliop
oul
ou
C, Kepa
ptsog
l
ou K,
Karlaftis MG.
Route
pla
n
n
i
ng
for a sea
p
l
a
n
e
servic
e: T
he
case of t
h
e
Greek Islands
.
Comp
ut Oper Res. Elsevi
er. 201
5; 59: 66-7
7
.
[19]
T
aoshen LI, Qin X. Gen
e
tic a
nd Particl
e
S
w
arm H
y
brid Qo
S An
y
c
ast Rou
t
ing Alg
o
rithm.
IEEE
. 2009;
313-
317.
[20]
Hau
p
t RL, Hau
p
t SE.
Practical Genetic Alg
o
ri
thms
. Ca
nad
a: John W
ill
e
y
& Sons, Inc. 200
4.
[21]
Ma
h
m
udy
WF.
Op
ti
mi
za
ti
on
o
f
Pa
rt T
y
pe
Se
l
e
ctio
n
an
d Ma
ch
in
e
Lo
ad
i
n
g
Pro
b
l
e
ms i
n
Fl
ex
ib
l
e
Manufactur
i
ng
S
y
stem Usin
g Varia
b
le Ne
igh
borh
ood
Searc
h
.
IAENG Int J Com
p
ut Sci
. 2
015; 4
2
(3)
:
254-
264.
Evaluation Warning : The document was created with Spire.PDF for Python.