# A Memetic Algorithm for an External Depot Production Routing Problem
## 3 Memetic Algorithm
### Construction of the Initial Population  
Let \(Pop\_size\) be the size or number of individuals (solutions) in the initial population \(Pop_{0}\). This population consists of a \(Pop\_size\) number of randomly generated solutions. Everyone in the initial population is generated in three steps described as follows:  
Step 1: \(Y\) construction. The construction of \(Y\) consists in determining the days of production. Here, it is a question of determining the days \(t\) for which \(Y_{t}=1\). To achieve this goal, we will first determine the total quantity produced over the planning horizon. Let \(NP\) be this quantity of products. It can be obtained by the following relationship: \(NP=\sum_{t\in T}P_{t}=\left(\sum_{t\in T}\sum_{i\in N_{k}}d_{it}-\sum_{i\in N _{k}}I_{0}\right)\). It is equal to the difference between the sum of the demands of all customers and the sum of the initial inventory at the depot and at the customers. Once the total quantity to be produced is calculated, we determine the number of days required to produce that quantity. To avoid a problem of hard bin packing with the limited fleet, we will limit the capacity of the fleet to 90%. Let \(cf\) be the capacity of the fleet and \(NY\) (\(NY=\sum\limits_{t\in T}Y_{t}\)) the number of days needed to produce \(NP\). Then \(cf\) and \(NY\) are calculated as follows: \(cf=0.9\times m\times Q\) and \(NY=\left[\left(\sum_{t\in T}\sum_{i\in N_{k}}d_{it}-\sum_{i\in N_{k}}I_{0} \right)/\min(C,cf,L_{0})\right]\). Once \(NY\) is determined, a \(NY\) number of days are randomly drawn in \(T/\{l\}\). It is not possible to produce on the last day of the planning horizon (\(l\)) because this production cannot be distributed to customers. Here, \(P\) can already be initialized by assigning \(NP\) to \(P_{t}\) for which \(t\) is the smallest value of \(T\) having \(Y_{t}=1\) without considering the violation of maximum production capacity (\(C\)). Step 2: \(P\) and \(X\) construction day after day. For any customer \(i\), \(X_{i1}\) is initialized with the necessary quantity so that \(I_{i0}\) and \(X_{i1}\) at least constitute a demand (for each costumer \(i\), \(d_{it}\)). For example, if the demand \(d_{it}=10\) \begin{table}
\begin{tabular}{c c c c c c c c c c c c c} \hline \hline \(i\) & **0** & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** & **11** \\ \hline \(d_{it}\) & - & 10 & 15 & 15 & 7 & 13 & 16 & 22 & 13 & 19 & 22 & - \\ \(I_{i0}\) & 76 & 5 & 15 & 15 & 3 & 13 & 40 & 55 & 6 & 47 & 44 & - \\ \(L_{i}\) & 152 & 30 & 60 & 60 & 21 & 52 & 112 & 154 & 39 & 133 & 132 & - \\ \hline \hline \end{tabular}
\end{table} 
Table 1: An example of a data for (\(n=10\), \(l=3\), \(m=3\)). \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c} \hline \hline \(R\) & **0** & **1** & **4** & **8** & **11** & \(-\)**1** & **2** & **5** & **3** & **6** & \(-\)**1** & **7** & **9** & **10** & \(-\)**1** \\ \hline \(X\) & - & 25 & 18 & 33 & 0 & 137 & 30 & 26 & 30 & 8 & 0 & 11 & 10 & 22 & 0 \\ \(Y\) & - & - & - & - & - & 1 & - & - & - & - & 0 & - & - & - & 0 \\ \(P\) & - & - & - & - & - & 137 & - & - & - & - & 0 & - & - & - & 0 \\ \hline \hline \endfor \(I_{0}=5\), we have on a \(X_{i1}=5\). For \(I_{0}=10\), we have \(X_{i1}=0\) and for \(I_{0}=15\) we have \(X_{i1}=0\). For each period \(t\), giving priority to customers who are out of stock, we aggregate demands for each customer \(i\) without violating its storage limit capacity \(L_{i}\), and that of the fleet \(cf\) in respect of the quantity of products available at the depot the day before \(I_{0,t-1}\). The quantities produced are then adapted to the production capacity \(C\) and then to the capacity of the fleet \(cf\) and those of the depot \(L_{0}\). This makes it possible to resolve the production capacity overrun authorized in step 1. This approach is an adaptation of the dynamic programming (DP) proposed by [PERSON] and [PERSON] [49] for the resolution of the classic LSP. Step 3: Construction of \(R\) day after day.