## 2 Vehicle Routing Problem with Time Windows
### A Sequential Genetic Algorithm for Solving the VRPTW  
GAs are search procedures inspired by evolutionary theories synthesizing the Darwinian evolution through natural selection with the Mendelian genetic inheritance [40]. This type of evolutionary algorithm stands out for its robustness and its ability to carry out one intelligent search in large, complicated, and unpredictable search spaces. These algorithms can be applied to solve diverse problems by encoding the candidate solutions as sequences of genes, as well as by defining an appropriate fitness function. In particular, GA can be applied to solve the VRP by encoding the candidate solutions using a sequence of integer-based values, where each value represents one customer or one delivery vehicle [41]. Several studies have been carried out implementing one GA to solve VRP instances, where various encoding schemes and several genetic operators have been proposed. In particular, the GA-VRPTW method [1] is a sequential algorithm using the _best-selection_ operator and two new recombination operators: _crossover-k_ and mutation-s. These genetic operators are described in Table 1. Each gene in a chromosome represents one customer that must be visited by one vehicle. This gene has several associated values: The Euclidean distance between two customers, as well as the demand and the time window associated with one customer (\(c_{ij}\), \(d_{i}\), and [\(a_{i}\), \(b_{i}\)] in the previously mathematical formulation, respectively). The general scheme of the GA-VRPTW implementation is depicted in Figure 1. First, the initial population with only feasible solutions is created using the k-means clustering algorithm [42]. Next, the evolutionary process applies genetic operators to generate only feasible new solutions. Finally, the best candidate solution in the final population is selected as the result of the GA-VRPTW algorithm. In this approach, the mutation-s operator implements an iterated local search to reduce the total travel distance. This operator alters the order of the chromosome genes and ensures that this perturbation improves the fitness value of the mutated chromosome, and accomplishes this with the defined constraints (demand, time window, and distance). The use of the mutation-s operator in one chromosome with 10 genes is shown in Figure 2. In this example, the candidate genes to be mutated have a distance of 11.1 and 5.6, respectively. These genes are interchanged, the associated values are updated, and the new total travel distance is computed. If this is not a valid perturbation, other candidate genes must be selected. This local search procedure causes the computation time of the mutation operator to increase considerably as compared to the time used by the other genetic operators. \begin{table}
\begin{tabular}{c p{142.3 pt}} \hline \hline
**Operator** & **Description** \\ \hline best-selection & This is a commonly used operator in literature. It selects the best chromosome from a population. \\ \hline crossover-k & This operator generates two new offspring by making a random crossover of two chromosomes. _Crossover-k_ operator randomly takes two numbers and carries out the crossover exclusively in the customer that corresponds to both chromosomes. This is done in order to avoid repetition and violation of time and capacity restrictions. \\ \hline mutation-s & This operator is termed intelligent because it does not randomly make changes, rather it attempts to reduce the total travelled distance by making only changes that satisfy time and capacity constraints. This operator searches for a gene with a greater distance with respect to the previous customer, this is the _gene-candidate_. It searches for another gene with a shorter distance, this is the _gene-mutation_. Once the mutation-s operator has identified these genes, the _gene-mutation_ makes the change if time and capacity constraints are not violated. The fitness is reduced due to the movements of genes in an offspring. \\ \hline \hline \end{tabular}
\end{table}