Information Technology Reference
In-Depth Information
Input:
ATPPinstance
σ
:= InitialTSP (V)
σ
:= InitialDrop (
σ
)
Calculate initial cost function
f
(
σ
)
Specify
L
fa
For all
k ∈{
0
...L
fa−
1
} f
k
:=
f
(
σ
)
Specify
l
First iteration
I
=0
σ
:=
σ
repeat
while
l ≥
1
do
σ
:=
σ
σ
:=
l
-
ConsecutiveDrop
(
σ, l
)
if
f
(
σ
)
≥ f
(
σ
)or
σ
not feasible
then
l
:=
l −
1
else
σ
:=
σ
end if
end while
repeat
σ
:=
σ
σ
: AddRandomMarket (
σ
)
until
σ
≥ σ
AND
σ
is feasible
σ
:= LAHCTSP (
σ
)
f
(
σ
)=
f
(
σ
)+
DeltaPenalty
(
σ
)
v
:=
ImodL
fa
if
f
(
σ
)
f
(
σ
)
or f
(
σ
)
≤
≤
f
v
then
σ
:=
σ
f
v
:=
f
(
σ
)
I
:=
I
+1
until stopping condition
return
σ
Fig. 2.
Pseudocode of the LAHC Algorithm
We developed two different types of LAHC algorithms to solve the TPP. The
first algorithm (LAHC, see Figure 2) strictly applies the list approach of LAHC
for the evaluation of candidate solution and the LAHCTSP method. The can-
didate solution is created by a sequence of a drop step, an add step and a TSP
heuristic and accepted if the LAHC constraints are fulfilled. The second algo-
rithm (sLAHC) simplifies this idea and accepts changes after an evaluation in
the drop step, add step and the TSP heuristic.
4 Computational Results
The algorithms described in Section 3.3 are implemented in Java and run on
a Intel Core 2.50GHz with 8 GB RAM. We tested the performance of the two
