Information Technology Reference
In-Depth Information
π
i
the value of the correspondent probability,
j
=1
π
j
, for being chosen. The new
solution
x
is accepted if the total traveled distance covered is less than or equal
to the total traveled distance covered by the current solution
x
. Note that in cases
where all the mandatory cities share the same time windows for all days
h
H
,
the acceptance criteria ensure that the corresponding time window constraints
are valid for
x
, without being necessary to check them in each iteration.
∈
Algorithm 1.
ANS algorithm pseudo-code
Require:
x
feasible solution
1:
repeat
2: Use roulette wheel selection based on the scores vector
π
to choose a re-
moval/insert operator inducing neighborhood
N
i
.
3: Consider the heuristics correspondent to the induced neighborhood
N
i
and ob-
tain a new solution
x
from
x
.
4:
if
vopt
(
x
)
<vopt
(
x
)
then
5:
x
=
x
6:
end if
7: Update the roulette wheel statistic score
π
i
of neighborhood
N
i
8:
until
No improvement over
x
is achieved within
k
consecutive iterations
4 Computational Results for Two Real-World
Applications
In this section we present two combinatorial optimization problems that arise in
practice which can be modeled through the mathematical programming formu-
lation presented in Section 2 and solved by the solution approach proposed in
Section 3. The first case concerns the route design for a ship while the second case
deals with the route design for a sales representative. Computational results for
both applications are presented and discussed. We used the R programming lan-
guage for coding the first and third phases of the solution approach. The second
phase was coded in C using the CPLEX Optimization Studio Academic Research
12.2 library. The time limit for the branch-and-bound was set to
T
= 1600 sec-
onds. All tests were performed on a Intel Core 2 Quad Q6600, 2.4 GHz with
4GB RAM.
4.1 Designing Ship Routes (DSR)
Once a year, a research vessel from IPMA, the Portuguese Institute of the Sea
and Atmosphere, carries out a sampling survey to obtain abundance estimates
of several fish species off the Portuguese coast. Sampling is made at predefined
geographic locations, fixed from year to year, scattered along the Portuguese
continental shelf and slope. In each location (fishing station) only one haul is
carried out: the trawl is set on the bottom of the sea, towed for 30 minutes and
hauled back into the ship. The duration of the haul lasts around 60 minutes,
