Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
9,
No.
2,
April
2019,
pp.
1275
1287
ISSN:
2088-8708,
DOI:
10.11591/ijece.v9i2.pp1275-1287
r
1275
T
ra
v
el
r
oute
scheduling
based
on
user’
s
pr
efer
ences
using
simulated
annealing
Z.K.A.
Baizal,
K
emas
M.
Lhaksmana,
Aniq
A.
Rahmawati,
Mizanul
Kir
om,
Zidni
Mubar
ok
Department
of
Computational
Science,
T
elk
om
School
of
Engineering,
T
elk
om
Uni
v
eristy
,
Indonesia
Article
Inf
o
Article
history:
Recei
v
ed
Apr
13,
2018
Re
vised
Sep
12,
2018
Accepted
Oct
8,
2018
K
eyw
ords:
multi-agent
system
intelligent
tra
v
elling
planner
tra
v
el
route
scheduling
simulated
annealing
tra
v
eling
salesman
problem
ABSTRA
CT
No
w
adays,
t
ra
v
eling
has
become
a
routine
acti
vity
for
man
y
people,
so
that
man
y
researchers
ha
v
e
de
v
eloped
studies
in
the
tourism
domain,
especially
for
the
determi-
nation
of
tourist
routes.
Based
on
prior
w
ork,
the
problem
of
determining
tra
v
el
route
is
analogous
to
finding
the
solution
for
tra
v
elling
salesman
problem
(TSP).
Ho
we
v
er
,
the
majority
of
w
orks
only
dealt
with
generating
the
tra
v
el
route
within
one
day
and
also
did
not
tak
e
into
account
se
v
eral
user’
s
preference
criteria.
This
paper
proposes
a
model
for
generating
a
tra
v
el
route
schedule
within
a
fe
w
days,
and
considers
some
user
needs
criteria,
so
that
the
determination
of
a
tra
v
el
route
ca
n
be
considered
as
a
multi-criteria
issue.
The
tra
v
el
route
is
generated
based
on
se
v
eral
constraints,
such
as
tra
v
el
time
limits
per
day
,
opening/closing
hours
and
the
a
v
erage
length
of
visit
for
each
tourist
destination.
W
e
use
simulated
annealing
method
to
generate
the
optimum
tra
v
el
route.
Based
on
e
v
aluation
result,
the
optimality
of
the
tra
v
el
route
generated
by
the
system
is
not
significantly
dif
ferent
with
ant
colon
y
result.
Ho
we
v
er
,
our
model
is
f
ar
more
superior
in
running
time
compared
to
Ant
Colon
y
method.
Copyright
c
2019
Insitute
of
Advanced
Engineeering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Name
Z.K.A.
Baizal,
Af
filiation
Department
of
Computational
Science,
T
elk
om
School
of
Engineering,
T
elk
om
Uni
v
ersity
,
Address
Jl
T
elek
omunikasi
No.1,
Jl
T
erusan
Buah
Batu,
Bojongsoang,
Bandung.
Phone
022
7564108
Email
baizal@telk
omuni
v
ersity
.ac.id
1.
INTR
ODUCTION
These
days,
tra
v
elling
has
become
a
daily
need
for
people,
especially
during
holidays.
On
most
cas
es,
tourist
will
try
to
visit
ne
w
tourism
places
the
y
ne
v
er
visit
before
[1].
Therefore,
plenty
of
tourists
w
ant
to
visit
that
places
for
se
v
eral
days.
So,
the
tourists
need
to
plan
their
tra
v
el.
Usually
,
tourists
ha
v
e
tra
v
el
agent
to
plan
the
tra
v
el
schedule
and
guide
their
trip.
There
are
man
y
studies
that
de
v
elop
the
systems
that
are
able
to
replace
tra
v
el
agent,
specifically
on
deciding
which
destination
suits
the
user’
s
need,
as
well
as
determining
tra
v
el
route.
This
system
e
v
olv
ed
as
a
recommender
system,
capable
of
recommending
tourism
destination
and
tra
v
el
routes.
The
tra
v
el
routes
are
generated
based
on
its
opening
hours
and
visiting
duration
[2].
Ho
we
v
er
,
the
model
in
the
determination
of
the
tra
v
el
route
can
only
accommodate
one-day
visit
time.
V
ansteenwe
gen
et
al
utilize
Greedy
Randomized
Adapti
v
e
Search
Procedure
(GARSP)
t
o
de
v
elop
City
T
rop
Planner
for
planning
route
5
cities
in
Belgium
[3].
F
orm
that
research,
the
model
created
is
able
to
schedule
a
tra
v
el
route
for
se
v
eral
days
with
constraints
such
as
open
hours
on
and
rest
periods
i.e.
lunch.
Ho
we
v
er
,
the
selection
of
that
route
scheduling
is
only
based
on
tra
v
el
time,
whereas
in
the
real
w
orld,
tourists
choose
tourism
destinations
based
on
man
y
criteria,
such
as
popularity
,
the
re
vie
ws
on
those
destinations,
entry
fee
and
so
forth.
In
man
y
w
orks,
the
problem
of
determining
tra
v
el
route
is
similar
to
finding
the
solution
from
the
T
ra
v
eling
Salesman
Problem
(TSP)
.
TSP
is
a
problem
where
a
sal
esman
must
visit
each
node
e
xactly
once
with
optimal
time
where
the
start
node
and
the
end
node
are
the
same
node.
In
a
tra
v
el
route,
TSP
can
be
J
ournal
homepage:
http://ijece
.iaescor
e
.com
Evaluation Warning : The document was created with Spire.PDF for Python.
1276
r
ISSN:
2088-8708
analogous
to
visiting
tourist
attractions
e
xactly
once
in
one
day
where
the
start
and
end
node
is
the
tourist’
s
lodge.
There
are
plenty
of
algorithms
which
can
be
implemented
to
solv
e
TSP
,
i.e.,Genetic
Algorithm
(GA)
[4],
Simulated
Annealing
(SA)
[5],
T
aboo
Search
[6],
P
arti
cle
Sw
arm
Optimization
[7],
Harmon
y
Search
[8],
Quan-
tum
Annealing
[9],
Ant
Colon
y
optimalization
(A
CO)
[10],
neural
netw
ork
[11]
and
so
on.
W
e
use
Simulated
Annealing
algorithm
(SA)
to
generate
tra
v
el
route
schedule,
because
SA
is
an
algorithm
with
the
best
tra
v
el
solution
quality
based
on
3
aspects:
mean
v
alue,
standard
de
viation,
running
time
[12].
Simulated
Anneali
ng
is
a
method
to
find
the
solution
of
combinatorial
problem
[13,
14],
de
v
eloped
from
Metropolish
algorithm,
which
is
an
algorithm
for
solving
problems
in
t
he
field
of
ph
ysics.
The
Metropol-
ish
algorithm
w
as
de
v
eloped
around
1940’
s,
utilizing
the
Monte
Carlo
simulation
process
[15].
Simulated
Annealing
w
orks
by
taking
beha
vioral
analogy
in
ph
ysics
proce
ss,
particularly
the
process
of
freezing
or
an-
nealing.
This
process
start
s
when
the
temperature
of
the
liquid
object
is
still
high
and
then
the
temperature
is
slo
wly
lo
wered
to
a
specified
temperature.
If
the
temperature
is
done
drastically
,
it
will
end
bad.
The
majority
of
the
pre
vious
researches
de
v
eloped
a
model
of
determining
of
tra
v
el
routes
in
one
day
and
did
not
accommodate
tourist’
s
preferences
of
the
desired
routes,
which
probably
in
v
olv
e
multiple
criteria.
This
paper
proposes
a
model
by
adopting
Simulated
Annealing
method,
to
generate
a
tra
v
el
route
schedule
within
se
v
eral
days,
taking
into
account
the
three
criteria
of
tourist’
s
needs:
1).
T
ourists
w
ant
to
visit
as
man
y
attractions
as
possible
within
a
fe
w
days,
2)
tourists
w
ant
to
visit
the
popular
destinations,
3)
tourists
w
ant
a
tra
v
el
route
that
minimizes
the
b
udget.
Thus,
the
problem
of
determining
the
tra
v
el
route
is
seen
as
a
multi-criteria
problem.
T
o
solv
e
the
mul
ti-criteria
problem,
we
utilize
the
concept
of
multi
attrib
ute
utility
theory
(MA
UT).
MA
UT
is
a
method
which
is
frequently
used
for
e
v
aluating
products
based
on
the
v
alue
of
weight
and
utilities
of
some
criteria/attrib
utes
[16]
The
weight
of
each
criterion
is
obtained
based
on
de
gree
of
interest
(DOI)
of
users.
DOI
is
a
user
de
gree
of
interest
for
each
criterion,
with
the
interv
al
[0,1].
T
ra
v
el
route
schedule
determination
also
considers
some
constraints,
which
are:
1)
tra
v
el
time
limits
per
day
,
2)
opening/closing
hours,
and
3)
the
a
v
erage
amount
of
visit
time
for
each
destination.
This
research
is
one
part
of
our
research
project,
to
de
v
elop
a
con
v
ersation-based
recommender
system
in
the
tourism
domain.
The
system
will
recommend
tourist
destinations
as
well
as
recommend
a
tour
route
based
on
e
xplicitly
stated
user
needs.
This
research
is
one
part
of
our
research
project,
to
de
v
elop
a
con
v
ersation-ba
sed
recommender
system
in
the
tourism
domain.
The
system
will
recommend
tourist
destinations
as
well
as
recommend
a
tour
route
based
on
e
xplicitly
stated
user
needs.
The
system
generat
es
con
v
ersation
by
utilizing
the
concept
of
semantic
reasoning
[17,
18,
19]
2.
THE
SYSTEM
O
VER
VIEW
The
system
is
able
to
recommend
tra
v
el
route
schedule
based
on
user
preferences.
The
proposed
model
generates
the
tra
v
el
route
schedule
which
is
based
on
Simulated
Annealing
algorithm.
1
sho
ws
the
system
o
v
ervie
w
.
Generally
,
the
steps
in
generating
tra
v
el
route
schedule
are
as
follo
w:
1.
User
pro
vides
:
(a)
T
ra
v
el
Destinations
User
is
gi
v
en
the
opportunity
to
choose
the
desired
tra
v
el
destination.
(b)
Hotel
The
hotel
or
the
lodge
where
the
user
stays.
(c)
DOI
(de
gree
of
Interest)
DOI
is
the
user
de
gree
of
int
erest
to
each
criterion,
as
a
form
of
user
preferences.
The
system
accommodates
3
dif
ferent
criteria
of
needs,
which
are:
1)
tourist
w
ant
to
visit
as
man
y
places
as
possible
within
a
fe
w
days
(routes
are
based
on
tra
v
el
time),
2)
t
ourist
w
ant
to
visit
popular
destinations
(routes
based
on
rating),
3)
tourists
w
ant
a
tra
v
el
route
that
minimized
the
b
udget
(routes
based
on
tarif
f).
The
v
alue
of
DOI
is
between
the
interv
al
of
[0,1].
2.
System
performs
optimal
route
search
with
Simulat
ed
Annealing
algorithm.
At
this
stage,
system
re-
trie
v
es
the
destination
data
and
time
matrix
data
from
database,
for
the
calculation
of
fitness
v
alue.
3.
Once
the
optimal
route
is
obtained,
then
the
system
performs
the
scheduling
process
using
the
accumu-
lated
tra
v
el
time
and
the
duration
of
visits
on
each
tourist
destination.
Int
J
Elec
&
Comp
Eng,
V
ol.
9,
No.
2,
April
2019
:
1275
–
1287
Evaluation Warning : The document was created with Spire.PDF for Python.
Int
J
Elec
&
Comp
Eng
ISSN:
2088-8708
r
1277
Figure
1.
The
Ov
ervie
w
of
the
System
4.
The
system
displays
the
tra
v
el
route
schedule
(maximum
in
3
days
as
well
the
visual
display
of
the
route,
by
utilizing
the
help
of
google
maps
API).
3.
SIMULA
TED
ANNEALING
FOR
R
OUTE
SCHEDULING
Basically
,
the
determination
of
tra
v
el
route
can
be
vie
wed
as
a
problem
to
find
the
solution
for
TSP
.
Generally
,
the
optimal
TSP
route
is
determined
based
on
the
time
or
nearest
distance.
This
research
proposes
a
model
to
generate
tra
v
el
route
schedule
(TSP)
based
on
3
criteria
(multi
criteria
).
As
discussed
in
section
2,
these
three
criteria
can
be
considered
as
parameters
for
route
determination,
which
are:
1).
T
ra
v
el
time,
2).
Rating,
3).
The
price
of
each
tourist
desti
nation.
The
ti
me
tra
v
el
is
tak
en
from
Google
Maps,
taking
the
typical
time
instead
of
real
time,
since
tourists
can
plan
the
tours
in
adv
ance.
In
addition,
there
is
also
checking
for
constraints
such
as
opening
and
closing
hours
on
each
accumulation
of
each
tourist
destination
schedule
and
the
maximum
time
of
tourist
visits
in
one
day
.
The
steps
of
determining
tra
v
el
route
are
as
follo
w:
3.1.
P
arameter
Initialization
Some
of
the
initialized
Simulated
Annealing
parameters
are:
initial
temperature,
cooling
rate,
s
topping
temperature.
The
parameters
are
used
to
determine
the
nu
m
ber
of
iteration
in
the
annealing
process.
At
the
stage
of
parameter
initialization,
the
parameters
used
are
tak
en
by
e
xperiment.
(a)
The
Initialization
of
The
First
(tour)
Solution
In
this
st
age,
the
system
will
generate
initial
(tour)
solution.
The
initial
generation
of
tour
can
be
done
by
making
tour
randomly
.
(b)
The
F
ormation
of
Ne
w
T
our
(Solution)
The
formation
of
ne
w
tour
(solution)
as
the
candidate
for
the
solution.
This
ne
w
solution
can
be
a
better
solution
than
the
pre
vious
solution.
F
or
the
formation
of
a
ne
w
(tour)
solution,
the
system
uses
the
sw
apping
mutation
method.
Sw
apping
mutation
is
done
by
selecting
2
nodes
randomly
from
the
pre
vious
solution.
After
that,
the
nodes
are
re
v
ersed
to
generate
a
ne
w
(tour)
solution.
Here’
s
an
illustrat
ion
of
generating
a
ne
w
tour
(solution).
Solution
before
1
2
4
5
3
T
r
avel
r
oute
sc
heduling
based
on...
(Z.K.A.
Baizal,
K
emas
M.
Lhaksmana)
Evaluation Warning : The document was created with Spire.PDF for Python.
1278
r
ISSN:
2088-8708
Figure
2.
The
steps
of
generating
tra
v
el
route
schedule
Ne
w
solution
1
2
5
4
3
(c)
The
Determination
of
T
ime
Accumulation
After
tw
o
(tour)
solutions
obtained,
its
total
time
will
be
accumulated
to
obtain
the
tourist
route
per
day
.
Each
tour
visit
be
gins
and
ends
a
t
the
hotel
selected
by
user
.
Ev
ery
day
,
the
tour
be
gins
at
08.00
until
20.00.
T
o
determine
the
tra
v
el
route
per
day
,
the
system
checks
the
schedule
of
the
opening
and
closing
hours
each
destination.
The
algorithm
for
time
accumulation
is
e
xplained
in
Algorithm
1.
Algorithm
1
AcumulateT
ime
(solution)
input
:
solution,
output
:
perDaySolution
1:
per
D
ay
S
ol
ution
[]
;
2:
cur
r
entnode
hotel
;
3:
f
or
i
in
range(solution)
do
4:
arri
v
alT
ime(node[i])=finishedT
ime(currentnode)
+
tra
v
el(currentnode,node[i])
5:
finishedT
ime(node[i])=arri
v
alT
ime(node[i])
+
duration(node[i])
6:
if
arri
v
alT
ime(node[i])
in
T
ime
Constraints
then
7:
if
arri
v
alT
ime(node[i])
in
constraint
open
and
closed
time
then
8:
put
node[i]
into
perDaySolution
list;
9:
currentnode
node[i]
10:
end
if
11:
end
if
12:
end
f
or
13:
r
etur
n
perDaySolution;
The
steps
in
algorithm
1
can
be
e
xplained
as
follo
ws,
If
the
kno
wn
(tour)
solution
is
as
follo
w
,
1
2
4
5
3
7
6
8
W
ith
the
open
and
close
hours
are
sho
wn
in
T
able
1.
T
ime
Calculation
The
time
displayed
in
the
scheduling
is
the
time
range
from
arri
v
al
time
until
finish
of
each
tourist
Int
J
Elec
&
Comp
Eng,
V
ol.
9,
No.
2,
April
2019
:
1275
–
1287
Evaluation Warning : The document was created with Spire.PDF for Python.
Int
J
Elec
&
Comp
Eng
ISSN:
2088-8708
r
1279
T
able
1.
The
opening
and
closing
hours
of
each
destination
Node
Opening
and
closing
hours
1
00.00
-
00.00
2
07.00
-
22.00
4
08.00
-
12.00
5
08.00
-
20.00
3
08.00
-
20.00
7
08.00
-
20.00
6
08.00
-
20.00
8
08.00
-
20.00
T
able
2.
The
result
of
time
accumulation
of
each
destination
Node
Opening
and
closing
hours
1
08.00
-
10.00
2
11.00
-
12.00
4
14.00
-
17.00
destination
AT
(
node
[
i
])
=
(
F
T
(
hotel
)
+
T
(
hotel
;
node
[
i
])
if
i
=
0
F
T
(
node
[
i
1])
+
T
(
node
[
i
1]
;
node
[
i
])
other
w
ise
(1)
where,
AT
(
node
[
i
])
=
the
arri
v
al
time
on
i
th
destination.
F
T
(
node
[
i
])
=
the
finished
time
on
ith
destination.
T
(
a;
b
)
=
time
tra
v
el
between
tw
o
tourist
destination
from
point
A
to
point
B.
Illustrate
d
as
follo
ws:
T
able
2
sho
ws
the
time
accumulation
of
each
tourist
destinati
on
in
the
range
solution.
Range
so-
lution
is
the
number
of
tourist
desti
nation,
then
at
each
accumulated
destination,
the
system
checks
the
opening
and
closing
hours
according
to
T
able
1.
Because
the
4
th
node
e
xceeds
the
closing
time,
then
1
2
4
5
3
7
6
8
The
node
will
be
sa
v
ed
for
the
ne
xt
day
route,
then
the
scheduling
continues
to
the
ne
xt
node
until
the
time
constraint
is
met.
T
ime
constraint
has
the
v
alue
of
”true”
when
the
time
range
is
between
08.00-20.00
(in
accordance
with
the
time
limit
of
tourist
visits
in
1
day).
Based
on
the
accumulation
of
time,
the
results
of
the
tour
in
one
day
can
be
seen
in
T
able
3.
Fitness
V
alue
Calculation
The
fitness
v
alue
in
Simulated
Annealing,
commonl
y
referred
to
ener
gy
[20].
The
calculation
of
fitness
v
alue
aims
for
the
selection
of
the
(tour)
solution,
so
that
the
best
solution
can
be
determined.
In
this
research,
optimized
tour
search
is
done
by
tw
o
kinds
of
fitness
v
alue
calculation:
a
Based
on
single
criteria
(tra
v
el
time).
The
calculati
o
n
of
fitness
v
alue
only
uses
a
single
crite-
rion,
which
is
tra
v
el
time.
The
fitness
v
alue
calculation
can
be
formulated
with
the
follo
wing
equation:
T
ime
(
x
)
=
dur
ation
(
hotel
;
x
0
)
+
P
n
1
i
=1
dur
ation
(
x
i
;x
i
+1
)
n
1
+
dur
ation
(
x
j
;
hotel
)
3
(2)
T
able
3.
The
tour
result
per
day
Node
Opening
and
closing
hours
1
08.00
-
10.00
2
11.00
-
12.00
5
13.00
-
15.00
3
15.30
-
16.00
7
18.00
-
19.30
T
r
avel
r
oute
sc
heduling
based
on...
(Z.K.A.
Baizal,
K
emas
M.
Lhaksmana)
Evaluation Warning : The document was created with Spire.PDF for Python.
1280
r
ISSN:
2088-8708
where,
X
=
The
tra
v
el
tour
solution
of
x
1
;
x
2
;
:::;
x
n
.
T
ime
(
X
)
=
Fitness
v
alue
based
on
tra
v
el
time
n
=
Length
of
node
or
tour
x
i
=
The
i
th
node/tourist
spot
D
ur
atio
n
(
a;
b
)
=
T
rip
duration
from
node
a
to
b
b
Based
on
multi
criteria
(time,
rating,
and
f
are)
The
fitness
v
alue
calculated
by
using
Multi
Attrib
ute
Utility
Theory
(MA
UT)
method,
includ-
ing
tra
v
el
time,
rating
and
f
are
of
each
tourist
destination.
The
fitness
v
alue
can
be
formulated
as
follo
ws,
F
(
time
(
X
)
;
r
ating
(
X
)
;
tar
if
f
(
X
))
=
w
1
time
(
X
)
+
w
2
r
ating
(
X
)
+
w
3
tar
if
f
(
X
)
3
(3)
where,
w
1
=
weight
of
tra
v
el
time
w
2
=
weight
of
rating
w
3
=
weight
of
f
are
The
definitions
for
time
(
X
)
is
pro
vided
in
Eq.
2,
while
r
ating
(
X
)
and
tar
if
f
(
X
)
are
pro-
vided
in
Eq.
5
and
6,
respecti
v
ely
.
In
this
case,
normalization
is
required
in
determining
dur
ation
(
a;
b
)
as
defined
in
Eq.
4
dur
ation
(
a;
b
)
=
dur
ation
(
a;
b
)
+
P
n
1
i
=1
dur
ation
(
x
i
;x
i
+1
)
n
1
+
dur
ation
(
x
j
;
hotel
)
3
(4)
where
n
min
dur
ation
is
the
minimum
v
alue
duration
and
max
dur
ation
refers
to
the
maximum
v
alue
of
duration.
The
fitness
v
alue
which
is
formulated
based
on
the
popularity
rating
is
formulated
as
follo
ws,
r
ating
(
a;
b
)
=
P
n
i
=1
r
ating
(
x
i
)
n
(5)
Where
n
is
the
length
of
the
solution.
As
for
the
fitness
v
alue
which
is
based
on
tarif
f,
the
formulation
is
as
follo
ws,
tar
if
f
(
a;
b
)
=
P
n
i
=1
tar
if
f
(
x
i
)
n
(6)
where
n
is
the
length
of
the
solution.
Normalization
operations
for
r
ating
(
X
)
and
tar
if
f
(
X
)
are
performed
as
the
same
as
that
of
dur
ation
(
a;
b
)
.
Acceptance
Probability
Calculation
After
the
fitness
v
alue
from
the
ne
w
(tour)
solution
is
obtained,
we
ha
v
e
to
checks
whether
the
ne
w
(tour)
solution
is
a
better
(tour)
than
pre
vious
solution
by
this
acceptance
probabilit
y
.
The
algorithm
to
determine
the
best
solution
candidate
is
sho
wn
in
Algorithm
2
[21].
Algorithm
2
Acceptence
Probability
(solution,ne
wSolution)
input
:
solution
and
ne
wSolution
output
:
solution
1:
if
new
S
ol
ution
>
sol
ution
then
2:
sol
ution
new
S
ol
usion
;
3:
if
r
andom
(0
;
1)
<
pr
obabil
ity
(
sol
ution;
new
S
ol
ution
)
then
4:
sol
ution
new
S
ol
usion
;
5:
end
if
6:
end
ifr
etur
n
solution;
The
function
of
acceptance
probability
can
be
formulated
as
follo
ws
[22]
P
accept
(
S
(
i
)
;
S
(
i
1))
(
1
if
S
(
i
)
>
S
(
i
1)
exp
S
T
other
w
ise
(7)
Int
J
Elec
&
Comp
Eng,
V
ol.
9,
No.
2,
April
2019
:
1275
–
1287
Evaluation Warning : The document was created with Spire.PDF for Python.
Int
J
Elec
&
Comp
Eng
ISSN:
2088-8708
r
1281
where,
P
accept
=
The
acceptance
probability
function
to
obtain
the
best
solution
candidate
T
=
T
emperature.
S
(
i
)
=
Solution
g
ained
on
iteration-
i
S
=
F
(
S
(
i
1))
F
(
S
(
i
))
T
emperature
decrease
item
The
each
iteration
is
done
to
decrease
the
temperature
v
alue.
The
common
w
ay
to
decrease
this
temperature
is
the
geometric
cooling
schedule
[21].
F
ormally
,
the
temperature
drop
can
be
formu-
lated
as
follo
ws,
T
=
cool
ing
r
ate
T
(8)
where
T
is
temperature
and
cool
ing
r
ate
is
a
constant
for
the
decrease
in
the
Simulated
Annealing
algorithm
The
iteration
is
complete
if
the
temperature
v
alue
is
less
than
the
stopping
temperature.
Based
on
this
iteration,
we
get
a
solution
(tour)
that
will
be
tak
en
as
a
tourist
route
in
one
day
.
4.
EV
ALU
A
TION
F
or
e
v
aluati
on,
we
ha
v
e
to
determine
the
best
parameters
of
the
simulated
annealing
algorithm,
such
as
temperature
T
,
cooling
rate
,
and
stopping
temperature.
W
e
conduct
s
ome
test
s
for
it,
by
combining
those
parameters.
F
or
each
combination,
a
trial
w
as
done
10
times
to
get
the
test
results.
T
able
4
sho
ws
the
result
of
the
parameter
test
with
predetermined
interv
al
v
alue.
The
best
parameter
combination
is
determined
from
the
total
node,
running
time,
and
total
days.
Based
on
table
4,
we
notice
that
the
best
combination
is
temperature
=
15000,
cooling
rate
=
0.99,
and
stopping
temperature
=
0.0002.
After
obtaining
the
best
parameters,
then
those
parameters
will
be
used
on
system
performance
testing.
W
e
e
v
aluate
the
system
by
considering
tw
o
aspects;
performance
test
and
running
time
test.
The
results
of
the
proposed
model
wil
l
be
compared
with
the
results
of
the
ant
colon
y
optimization
algorithm,
in
our
pre
vious
w
ork
[23].
The
performance
test
use
single
criterion
(time)
and
multi
criteria
(time,
rating,
f
are).
W
e
in
v
olv
e
28
tourist
destination.
This
test
is
done
in
10
trials.
The
performance
is
determined
by
the
optimum
aspect
of
the
tra
v
el
route
resulted
and
also
the
running
time.
4.1.
T
ra
v
el
T
our
Optimality
T
est
4.1.1.
The
Optimality
Based
on
Number
of
T
ourist
Places
(Nodes)
in
T
our
Figure
3
sho
ws
the
test
results
based
on
the
number
of
nodes
(tourist
destinations)
in
a
tour
using
a
single
criterion
(tra
v
el
time)
approach.
F
or
the
input
nodes
2
to
7
nodes,
we
notice
t
h
a
t
there
are
no
dif
ference
performance
for
both
algorithm.
Meanwhile,
input
nodes
8
through
21
using
the
Ant
Colon
y
algorithm,
produce
more
nodes
in
the
tour
,
compared
to
Simulated
Anneali
n
g
algorithm.
But
for
man
y
input
nodes
(22
to
27),
the
number
of
nodes
in
tour
for
the
Simulated
Annealing
algorithm
has
better
res
ults
than
the
Ant
Colon
y
algorithm.
Figure
4
sho
ws
the
test
results
based
on
the
number
of
nodes
in
best
tour
using
multi
criteria
approach.
It
can
be
seen
that
these
results
do
not
ha
v
e
a
significant
dif
ference
with
the
results
obtained
from
the
single
criterion
approach.
The
Ant
Colon
y
algorithm
has
better
results
when
the
input
nodes
are
8
to
21,
while
the
Simulated
Annealing
algorithm
has
better
results
with
input
nodes
of
22
to
27.
Based
on
both
test
results,
we
notice
that:
1)
the
number
of
nodes
in
tour
,
no
significant
trend
dif
ferences
between
single
criterion
and
multi
criteria
approach,
2)
F
or
a
small
number
of
input
nodes,
Ant
Colon
y
is
superior
,
ho
we
v
er
for
the
lar
ger
number
of
input
nodes
(in
this
case
is
o
v
er
22
nodes),
the
model
proposed
using
Simulated
Annealing
is
better
in
terms
of
optimality
.
4.1.2.
The
Optimality
Based
on
the
Amount
of
V
isit
Days
Optimality
test
based
on
the
amount
of
days
of
tourist
visit
by
using
single
criteria
approach,
is
sho
wn
by
Figure
5.
It
sho
ws
that
the
result
of
Simulated
Annealing
algorithm
has
no
significant
dif
ference
to
the
Ant
Colon
y
algorithm.
The
dif
ference
occurs
only
in
the
number
of
i
nput
nodes
of
7,
where
the
Simulated
Annealing
algorithm
has
slightly
better
results.
T
r
avel
r
oute
sc
heduling
based
on...
(Z.K.A.
Baizal,
K
emas
M.
Lhaksmana)
Evaluation Warning : The document was created with Spire.PDF for Python.
1282
r
ISSN:
2088-8708
T
able
4.
P
arameters
T
esting
T
emperature
Cooling
rate
Stopping
temperature
Running
time
T
otal
Days
T
otal
nodes
10000
0,99
0,0001
3,031,276
3
14,4
10000
0,99
0,0002
2,902,693
3
14,9
10000
0,99
0,0003
2,811,509
3
14,5
10000
0,99
0,0004
2,942,692
3
14,5
10000
0,99
0,0005
2,627,159
3
14,7
10000
0,99
0,0006
2,563,514
3
14,4
10000
0,99
0,0007
2,675,937
3
14,3
10000
0,99
0,0008
2,574,788
3
14,4
10000
0,99
0,0009
2,598,967
3
14,2
10000
0,99
0,001
2,467,172
3
14,1
10000
0,98
0,0001
1,738,658
3
14,6
10000
0,98
0,0002
1,564,106
3
14,0
10000
0,98
0,0003
1,464,694
3
14,5
10000
0,98
0,0004
1,465,630
3
14,3
10000
0,98
0,0005
1,547,616
3
13,8
10000
0,98
0,0006
1,371,457
3
13,8
10000
0,98
0,0007
1,352,592
3
14,0
10000
0,98
0,0008
1,387,917
3
13,9
10000
0,98
0,0009
1,332,604
3
14,0
10000
0,98
0,001
1,342,466
3
14,0
15000
0,99
0,0001
2,945,110
3
14,6
15000
0,99
0,0002
2,884,138
3
14,9
15000
0,99
0,0003
2,754,234
3
14,2
15000
0,99
0,0004
2,692,822
3
14,7
15000
0,99
0,0005
2,648,845
3
14,7
15000
0,99
0,0006
2,605,332
3
14,8
15000
0,99
0,0007
2,497,663
3
14,7
15000
0,99
0,0008
2,555,489
3
14,5
15000
0,99
0,0009
2,622,557
3
14,6
15000
0,99
0,001
2,579,650
3
14,6
15000
0,98
0,0001
1,721,198
3
14,5
15000
0,98
0,0002
1,596,287
3
14,1
15000
0,98
0,0003
1,499,446
3
14,1
15000
0,98
0,0004
1,504,758
3
14,1
15000
0,98
0,0005
1,462,044
3
14,2
15000
0,98
0,0006
1,553,272
3
14,2
15000
0,98
0,0007
1,467,576
3
13,7
15000
0,98
0,0008
1,400,846
3
13,8
15000
0,98
0,0009
1,412,756
3
14,4
15000
0,98
0,001
1,368,984
3
13,9
Figure
3.
T
our
T
est
with
Single
Criteria
Approach
Int
J
Elec
&
Comp
Eng,
V
ol.
9,
No.
2,
April
2019
:
1275
–
1287
Evaluation Warning : The document was created with Spire.PDF for Python.
Int
J
Elec
&
Comp
Eng
ISSN:
2088-8708
r
1283
Figure
4.
T
our
T
est
with
Multi
Criteria
Approach
Figure
5.
Number
of
Days
T
est
with
Single
Criteria
Approach
Figure
6.
Number
of
Days
with
Multi
Criteria
Approach
T
r
avel
r
oute
sc
heduling
based
on...
(Z.K.A.
Baizal,
K
emas
M.
Lhaksmana)
Evaluation Warning : The document was created with Spire.PDF for Python.
1284
r
ISSN:
2088-8708
Figure
7.
Running
T
ime
T
est
Based
on
Single
Criteria
Approach
Figure
8.
Running
T
ime
T
est
Based
on
Multi-Criteria
Approach
Figure
6
sho
ws
the
optimality
test
results
based
on
the
number
of
tourist
visits
by
multi
criteria.
It
can
be
seen
that
there
is
no
significant
dif
ference
between
the
Simulated
Annealing
algorithm
and
the
Ant
Colon
y
algorithm.
The
only
di
f
ference
is,
for
the
number
of
input
node
is
7,
the
Ant
Colon
y
algorithm
has
slightly
better
results,
which
is
the
7
nodes
are
visited
in
an
a
v
erage
of
2
days,
while
the
Simulated
Annealing
with
the
a
v
erage
of
3
days.
Ho
we
v
er
,
with
these
2
test
results,
it
can
be
noticed
that
the
performance
of
the
proposed
model
using
the
Simulated
Annealing
algorithm
is
no
dif
ferent
from
the
model
using
Ant
Colon
y
algorithm.
In
addition,
referring
to
Figure
5
and
6,
we
also
notice
that
there
is
a
slight
dif
ference
in
the
number
of
days
recommended,
especially
in
the
total
input
of
8
nodes.
Meanwhile,
in
the
other
total
input
nodes,
the
recommended
number
of
days
is
the
same.
4.2.
Running
T
ime
T
est
Figure
7
sho
ws
the
result
of
running
time
testing
using
single
criterion
approach.
F
or
a
small
number
of
input
nodes,
Simulated
Annealing
model
has
a
slo
wer
running
time,
whereas
when
the
number
of
input
nodes
i
s
lar
ger
,
the
model
with
the
Simulated
Annealing
Model
has
f
aster
running
time
compare
to
Ant
Colon
y
model.
The
running
time
test
for
the
multi-criteria
a
p
pr
o
a
ch
is
sho
wn
in
Figure
8.
W
e
notice
that
this
result
has
no
significant
dif
ference
from
the
result
that
used
a
single
criterion.
In
the
test
for
a
small
number
of
nodes,
Simulated
Annealing
has
a
longer
time
running,
whereas
when
the
number
of
total
input
nodes
is
lar
ge,
Simulated
Annealing
has
f
aster
running
time
compared
to
the
Ant
Colon
y
algorithm.
Int
J
Elec
&
Comp
Eng,
V
ol.
9,
No.
2,
April
2019
:
1275
–
1287
Evaluation Warning : The document was created with Spire.PDF for Python.