TSP with Multiple Time-Windows and Selective Cities - Computational Logistics - page 164

Each one of these subsets induced a variable fixing strategy. Consider four pre-
defined parameters α , β , η and T . Taking into account the optimal solution of
the LP relaxation, we fix to 1 the values of at most α decisions variables x ij
such that x ij ≥ XPE . Then we run a truncated

branch and bound within a time limit of T seconds. If the optimal solution is not
reached, a second step is required where some good temporal characteristics of
the best feasible solution obtained are explored. In the second step, considering
the best feasible solution given by the branch and bound, we identify the daily
sequences of consecutive visits to mandatory cities where at least η clients are
visited. Let DS =

β and x ij ∈ XEP or x ij ∈

be the set of these daily sequences where ds
contains the indexes of mandatory cities visited in daily sequence .Foreach
=1 , ..., c ,wefixtoone α decision variables x ij such that i,j

{ ds 1 , ..., ds c }

∈ ds and rerun

the branch and bound restricted to the time limit of T seconds.

3.3 Adaptive Neighborhood Search

Finally, in the third phase an adaptive neighborhood search (ANS) heuristic is
used to improve solutions obtained in phase 2. The main concern is to intro-
duce some robustness in the solutions obtained in the previous phase. Robust
solutions offer more stability and flexibility to adapt and recover from disrup-
tions that may occur during the journey. In order to obtain solutions that meet
some robustness we propose an ANS algorithm that uses four competitive sub-
heuristics to improve the traveled distance, while keeping fixed the number of
clients visited in each day.
The proposed ANS is based on the ALNS procedure developed by Pisinger
and Ropke in [5] and [6]. At each iteration, a removal heuristic that assigns
undefined values to at most q variables is followed by a repair heuristic that
re-assigns feasible values to those variables. As noted by several authors, usually
simple and fast removal/repair procedures lead to poor quality solutions. How-
ever, this disadvantage is offset by the fact that, large moves around the solution
space lead to a diverse set of feasible solutions that potentially includes good
quality solutions.
The particular structure of the TSPSNTW, with two types of city visits,
mandatory or selective, leads to a set of sequences of visits to mandatory cities
periodically intercalated (linked) by a visit to a selective city. Or, in a different
perspective, visits to selective cities connect sequences of consecutive visits to
mandatory cities. Moreover, these sequences of visits take place along a set
of days, whose cardinality must not exceed |H| . To exploit both the different
nature of the cities and the temporal structure we have considered four different
removal operators.

- Daily removal - removes a subset of q mandatory cities from a daily sequence
of consecutive visits to mandatory cities. The subset to be removed do not
include the first and the last mandatory cities visited on that day, in order
to preserve connections between different daily sequences.