|
Abstract:
|
This
pap er
considers
two
discrete
lo cation
problems:
Bus
Terminal
Lo cation
Problem
(BTLP)
and
Long-term
Care
Facility
Lo cation
Problem
(LTCFLP).
Vari-
able
Neighb orho o d
Search
(VNS)
metho d
for
solving
BTLP
and
LTCFLP
is
pre-
sented
in
this
pap er.
VNS
is
a
single-solution
based
metaheuristic
based
on
system-
atic
change
of
neighb orho o ds
while
searching
for
optimal
solution
of
the
problem.
It
consists
two
main
phases:
shake
phase
and
lo cal
search
phase.
BTLP
is
a
discrete
lo cation
problem
which
considers
lo cating
bus
terminals
in
order
to
provide
the
highest
p ossible
quality
of
public
service
to
the
clients.
Clients
are
presented
as
public
transp ortation
stations,
such
as
bus
or
metro
stations.
VNS
algorithm
is
used
for
solving
BTLP.
This
algorithm
uses
improved
lo cal
search
based
on
e cient
neighb orho o d
interchange.
VNS
is
parallelized
(PVNS)
which
leads
to
signi cant
time
improvement
in
function
of
the
pro cessor
core
count.
Computa-
tional
results
show
that
prop osed
PVNS
metho d
improves
existing
results
from
the
literature
in
terms
of
quality.
Larger
instances,
based
on
instances
from
the
Trav-
eling
Salesman
Problem
library,
are
presented
and
computational
results
for
those
instances
are
rep orted.
LTCFLP
is
created
as
a
part
of
health
care
infrastructure
planning
in
South
Korea.
Clients
are
considered
as
groups
of
patients
with
a
need
of
long-term
health
care,
while
established
facilities
present
lo cations
where
the
centers
that
provide
health
care
services
should
b e
built.
Prede ned
are
n
lo cations
where
centers
are
to
b e
established.
This
problem
seeks
at
most
K
lo cations
to
establish
health
centers
so
they
are
to
b e
equally
loaded
with
clients
demand.
For
solving
LTCFLP,
by
using
VNS
algorithm,
data
structure
based
on
fast
interchange
is
presented.
It
reduces
the
time
complexity
of
one
iteration
of
lo cal
search
algorithm
to
O
(
n
·
max(
n,K
2
))
comparing
to
the
known
time
complexity
from
the
literature
O
(
K
2
·
n
2
)
.
Reduced
time
complexity
of
the
presented
VNS
leads
to
b etter
quality
solutions,
due
to
larger
numb er
of
VNS
iterations
that
can
b e
p erformed
in
less
computational
time.
This
pap er
presents
computational
results
that
outp erform
the
b est
known
results
from
the
literature. |