# A Memetic Algorithm for an External Depot Production Routing Problem
## 3 Memetic Algorithm
### Selection and Crossover Procedure  
Each child from the initial generation \(CHILDS_{0}\) is the result of the crossover of two parents selected by a binary tournament procedure. A selection by binary tournament consists of selecting the best solution from two randomly drawn solutions in the population \(Pop_{0}\). Let \(A\) be the parent selected at the first selection procedure and \(B\) the parent selected at the second selection procedure. Then a two-point crossover procedure of parents \(A\) and \(B\) is implemented for the determination of a single child \(E\). The crossover procedure can be described as follows: Let us note by (\(\bullet\)) the membership operator. By this operator writing \(A\bullet R\) means that \(R\) belongs to \(A\). Let us note \(R_{p}\) or \(R(p)\) the element of rank \(p\) in \(R\) and \(R_{p\to q}\) or \(R(p\to q)\) the sub-list of \(R\) going from \(p\) to \(q\). In this work, the cutting points must correspond only to the day delimiter (\(-1\)). For the determination of cutting points, a random draw of two dates \(t_{1}\), \(t_{2}\in T/\{l\}\) with \(t_{1}\
eq t_{2}\) is made. Then \(d_{1}\) and \(d_{2}\) are determined so that \(d_{1}=\min(t_{1},t_{2})\) and \(d_{2}=\max(t_{1},t_{2})\). Let \(pos(t)\) be the function that at each date associates its position in \(A\bullet R\) (\(p=pos(t)\)). \(A\bullet R\) will be segmented into three parts. The left part will be identified by \(A\bullet RL=A\bullet R(1\to pos(d_{1}))\). The middle of \(A\bullet R\) is represented by \(A\bullet RM=A\bullet R(pos(d_{1})+1\to pos(d_{2}))\) and the right part by \(A\bullet RR=A\bullet R(pos(d_{2})+1\to pos(d_{2})+1\to pos(l))\). Similarly, parent \(B\) will also be segmented according to the values of \(d_{1}\) and \(d_{2}\) determined for the \(A\bullet R\) segmentation. The construction of child \(E\) from the crossover of \(A\) and \(B\) is done as follows: let \(E\bullet RL\), \(E\bullet RM\), and \(E\bullet RR\) be the three parts of \(E\bullet R\). These three parts will be initialized as follows: \(E\bullet RL=B\bullet RL\), \(E\bullet RM=A\bullet RM\) and \(E\bullet RR=B\bullet RR\). After the initialization of \(E\bullet R\), a check is made to correct any anomalies in its construction. Contrary to Boudia et Prins' correction strategy of browsing the symbols in \(E\bullet R\)[28] we adopt a simplified correction strategy of browsing the symbols in \(N_{c}\). This strategy allows to quickly identify the missing customers in \(E\bullet R\) and make the appropriate corrections. The correction is as follows: Let \(i\) be the browsing index of \(N_{c}\), \(TX_{i}\) the total quantity delivered to the customer \(i\) over \(T\) in \(E\bullet X\) and \(TU_{i}\) the total quantity of product that was to be delivered to \(i\) over \(T\). We have \(TX_{i}=\sum_{l\in T}X_{i}\) and \(TU_{i}=\sum_{l\in T}d_{il}-I_{l0}\). Through a comparison between \(TX_{i}\) and \(TU_{i}\), We group customers into three subsets. The first subset is that of customers representing Case 1 such as \(TX_{i}=TU_{i}\). The second subset representing Case 2 concerns the customers \(i\) for whom \(TX_{i}>TU_{i}\) and Case 3 brings together the customers for whom \(TX_{i}<TU_{i}\). In the process of repairing the chromosome, all customers affected by Case 2 are treated first. Then come the customers concerned by Case 3 and finally those concerned by Case 1. Each case is treated as follows:  
Case 1. If \(TX_{i}=TU_{i}\), then there is nothing to do for the costumer \(i\). All demands \((d_{it},\forall t\in T)\) are already met by the initial stock (\(I_{i0}\)) and the quantities delivered over \(T\) (\(TX_{i}\)). Case 2. If \(TX_{i}>TU_{i}\), then a reverse browsing of \(T\) is made (from \(i\) to \(1\)). \(E\bullet X_{it}\) is successively reduced by a demand \(d_{it}\). For a given period \(t\), if \(E\bullet X_{it}\) falls to \(0\) then \(i\) is removed from its trip at the date \(t\) in \(E\bullet R\). This correction stops at the period \(t\) at which \(TX_{i}=TU_{i}\). Case 3.