Information Technology Reference
In-Depth Information
Fig. 1. Remove (6,4) and (9,24). Insert(6,9) and (4,24) by reversing the orientation
and swapping days i+1 and i+2.
- Time oriented removal - removes a subset of q mandatory cities from daily
sequence i and from daily sequence i +1. The subset to be removed does not
include the first and the last mandatory cities visited, respectively, on day i
and day i + 1, so as to not disrupt the connections between days other than
i and i +1.
- Route proximity removal - considers two daily sequences, i and i + k (k > 1),
which are geographically close, removes a subset of q mandatory cities from
daily sequence i and q mandatory cities from daily sequence i + k .
- Inter day removal - removes two arcs connecting two daily sequences of visits
to mandatory cities.
The daily removal, time oriented removal and route proximity removal opera-
tors remove subsets of mandatory cities by disconnecting them from the current
circuit, leaving partial circuits and/or isolated cities. By removing two arcs, the
inter day removal operator is always conducted to three partial circuits in the
solution. The daily removal and the route proximity removal only affect daily
sequences of consecutive visits to mandatory cities. The time oriented removal
steps in both daily sequences and night connections, which link consecutive daily
sequences. The inter day removal moves within the set of night connections. The
time oriented removal and the route proximity heuristics are based on the idea
that the q mandatory cities removed from daily sequence i are easily inter-
changed with those removed from day i + k due to geographical proximity, while
maintaining time windows constraints feasibility.
At each iteration of the algorithm, a neighborhood defining operator is se-
lected, among the set of four operators defined above. The execution of a removal
operator leads to a set of partial sub-circuits disconnected from each other. Then,
an insertion operator should be applied in order to repair the solution. We have
considered that neighborhoods N i ,i =1 , ..., 4 induced by the removal operators
will take care of both the removal and insertion steps. That is, the set of partial
sub-circuits will be reconnected among them by a least cost insertion operator.
The least cost insertion heuristic looks to sub-circuits without taking into ac-
count their orientation. As a consequence it may reverse the orientation of some
circuits. This can have some impact while repairing inter day arc removals as
illustrated in the example of Figure 1.
The selection of the operators is based on a roulette wheel scheme that rep-
resents the past performance of each removal/insertion heuristic. A score π i is
associated with each operator i . The initialization of the score vector attributes
an equal score to each removal/insertion operator. Whenever operator i finds a
solution x better than the current solution x the score π i is updated to increase
 
Search WWH ::




Custom Search