Time Constraints: The Cost of Sustainability - Sustainable Urban Logistics: Concepts, Methods and Information Systems - page 175

Fig. 16 Readjustment of the arrival time to customer i as close as possible to the re-opening of
the time window
2.3 Genetic Algorithm Solution Procedure
We developed and implemented an algorithm to solve the VRPATW, based on the
sequence of stops provided by a basic Genetic Algorithm, built according to the
design shown in Fig. 17 . The operators of this GA can be briefly described as
follows:
Crossover: built according to the evaluative procedure proposed by Uchimura and
Sakaguchi ( 2002 ).
Mutation: random selection and exchange of two stops in the sequence.
Probabilistic selection: assigning a probability of survival linearly distributed
between 0 and 1 depending on the fitness of the individual (which depends on the
total number of vehicles used and the total duration of the routes).
Population restart: when the best fitness value is less than 5 % below the average
fitness value, keeping only the three best individuals of the population.
The stopping criterion is only associated to the number of iterations.
The rest of this section describes the procedure to calculate the fitness of a given
individual (a sequence of customers to visit), which is based on the discussion of
the different routing situations in the previous section. The flowchart of this fitness
function is shown in Fig. 18 .
The fitness calculation starts with the sequence of customers provided by the
GA and an empty route associated to the first vehicle. For each customer i, the
procedure is as follows:
If customer i is not located inside the restricted zone, the procedure enters block
N. This block explores the previous customer i-1 in the route and, in case it was
located inside the restricted zone, determines whether the time window closes in
the process of traveling from i-1toi. Should this happen, the procedure modifies