## 3 Non-Dominated Sorting Genetic Algorithms
### General Principle  
The proposed approaches work on a population of solutions and can be seen as an adaptation of the non-dominated sorting genetic algorithm (_NSGAII_). It is a Pareto-optimal method based on the dominance concept. Dominance relations in the Pareto sense are defined as follows: for two objectives \(Z_{1}\) and \(Z_{2}\) to be minimized, we say that a solution \(x\) dominates a solution \(y\) (\(x\prec y\)) if \((Z_{1}(x)\leq Z_{1}(y)\)_and_\(Z_{2}(x)<Z_{2}(y))\), _or_\((Z_{1}(x)<Z_{1}(y)\)_and_\(Z_{2}(x)\leq Z_{2}(y))\). This lets us say that a solution is non-dominated, or is efficient if no solution can be found that improves strictly both objectives. In other terms, it is impossible to improve one of the objectives without deteriorating the other one.  
The optimization in the Pareto sense computes the set of non-dominated solutions called the Pareto front. A non-dominated sorting uses a ranking method for the fitness assignment and a crowding distance for maintaining the diversity of the population.  
In _NSGAII_, successive generations of solutions are classified into non-dominated fronts. Each non-dominated front is identified and ranked according to the level of non-domination from Front 0 until the partition of the population is complete. Besides ranking, _NSGAII_ uses a crowding distance as a measure that indicates how near solutions on the same front are to each other. Indeed, the crowding distance measures the density of solutions in a front. Considering our two objectives for the VRPTW-SP and a front \(F\), the crowding distance of a solution \(k\) is computed as follows:  
\[\textit{Crowding distance}(F(k))=\frac{Z_{1}^{\textit{pred}(k)}-Z_{1}^{ \textit{suc}(k)}}{Z_{1}^{\textit{max}}-Z_{1}^{\textit{min}}}+\frac{Z_{2}^{ \textit{suc}(k)}-Z_{2}^{\textit{pred}(k)}}{Z_{2}^{\textit{max}}-Z_{2}^{\textit {min}}} \tag{4}\]  
\(suc(k)\) and \(pred(k)\) are respectively the successor and the predecessor solution of the \(k^{\text{th}}\) one in the sorted front (see Figure 1). \(Z_{c}^{\textit{max}}\) (respectively \(Z_{c}^{\textit{min}}\)) corresponds to the worst (respectively best) value of objective \(c\), with \(c=1,2\). For the extreme points in all fronts, the _crowding distance_ is set to \(\infty\).  
The population update is illustrated in Figure 2 designed by [PERSON] et al. (2016). Let \(t\) be the population rank. First, a population \(P_{t}\) and the offspring population \(Q_{t}\) are merged to obtain a population \(R_{t}\) of size \(2 NP\). \(R_{t}\) is then sorted out according to the non-domination criterion. Solutions in front \(F_{0}\) are obviously of better quality and have to be conserved in the following population. However, if the size of the front \(F_{0}\) is bigger than \(NP\), only a part of the front is kept. In the case where the size of \(F_{0}\) is strictly less than \(NP\), the population \(P_{t+1}\) has to be completed with solutions from the following fronts. In both cases, the choice is based on the crowding distance measure taken in descending order.  
Figure 1: Crowding distance.  
Basically, at each generation of _NSGAII_, an initial population (\(P_{0}\)) of \(NP\) individuals is generated and sorted according to the non-domination criterion. At each iteration, a child-population (\(Q_{0}\)) containing \(NP\) individuals is produced. To get this population (\(Q_{0}\)), pairs of parents \(P_{1}\), \(P_{2}\) are selected using the binary tournament method. Then, a crossover operator is applied to the two selected parents to obtain children, which are added to (\(Q_{0}\)). Finally, \(P_{0}\) and \(Q_{0}\) are merged to obtain a mixed-population of size \(2 NP\) (\(R_{0}=P_{0}\cup Q_{0}\)). The latter is then sorted out (according to the non-domination criterion), and just the \(NP\) first solutions are retained to the next iteration. This process is repeated until a stopping condition is satisfied.