Information Technology Reference
In-Depth Information
Concerning the first step of the heuristic branch-and-bound (Section 3.2),
we realized that, taking into account the LP relaxation solution at the root
node and fixing, for each of the subproblems, the value of just one of the
XPE
decision variables was enough to reach “good” quality integer solutions. In the
second step, we pick the best feasible solution given by the branch-and-bound
and look to daily routes where the vessel visits five or more fishing stations.
For each of these daily routes, we fix at most five decision variables, randomly
chosen in subset
XEE
and rerun the branch-and-bound. Note that, setting those
variables to one is not so restrictive as it looks at first sight. For example, if
on day
i
the vessel visits fishing stations 1 - 2 - 4 - 10 - 3 then we fix the
decision variables
x
1
,
2
=
x
2
,
4
=
x
4
,
10
=
x
10
,
3
= 1 and rerun the branch and
bound algorithm. Later, one can obtain solutions where a fixed daily connection
becomes a night connection changing the sequence of fishing stations visited
during the day. Returning to the above example this leads to a day
j
: ... - 1 -
2-4andaday
j
+ 1: 10 - 3 - ... in the new solution. Table 1 shows solutions
obtained by applying the solution approach described in Section 3 to each of the
two subproblems under the six different scenarios. The first column describes the
test instance where the notation N stands for the North subproblem and SSW for
South and Southwest subproblem. Following N or SSW appears a number. The
first two digits of this number describe the ship speed while the third and fourth
digits show the
value. Each test instance takes up two rows. The first row,
'cplex', stands for the first step of the branch-and-bound procedure. The second
row 'cplex(2)' concerns the second step of the branch-and-bound, after fixing a
new set of decision variables. Column 'Value' shows the objective solution value.
Columns '# Days visiting' and 'Max visit/day' present, respectively, the number
of days that the vessel sailed and the maximum number of fishing stations visited
by the ship in one day. Finally the last two columns display the total distance
traveled by boat given by, respectively, the solutions of the branch-and-bound
procedure and the ANS procedure. Note that, the ANS takes as input the best
feasible solution given by cplex or cplex(2), depending on which row we are
talking about.
Comparing cplex and cplex(2) solutions, one can see that the decrease in the
objective function value of cplex(2) is mainly due to a decrease in the number
of days sailing, which corresponds to a decrease in the time completion. For
the 12 instances this decrease was on average 1.5 days. However, in some cases,
this improvement may be followed by an increase in total traveled distance, as
occurred in
N
1415,
N
1715 and
SSW
1415. Noteworthy is the
N
1415 instance
where the increase in traveled distance was about 80 km, while there was a re-
duction of two days sailing. This highlights the contradictory nature of the two
objective function components. Given these results one may infer that the sec-
ond step branch-and-bound, mainly, focus on the time completion optimization.
Additionally, the ANS, which is driven to reduce the traveled distance, fulfills
its role by reducing the total traveled distance on average 13
.
5% (
−
170
.
2
km
)
for cplex solutions and on average 11% (
143
.
3
km
) for cplex(2) solutions. For
the 12 instances, the average traveled distance for the ANS procedure combined
−
