# A Memetic Algorithm for an External Depot Production Routing Problem
## 1 Introduction
Although the approximation of the Pareto front for each instance is discontinuous and not convex, it highlights the trade-off between the two objective functions. A reactive tabu search was presented for solving a PRP to satisfy a time varying demand with a homogeneous fleet of vehicles over a finite planning horizon [31]. The authors compared the test results with the results obtained with GRASP on instances of up to 200 clients and 20 periods. This comparison revealed an improvement in results ranging from 10% to 20% on the overall cost of operations with an increase in computing time. A Tabu search (TS) with path relinking (TSPR) was used for PRP resolution with a homogeneous fleet of vehicles [32]. Tests performed on datasets from the literature have shown that TSPR gives better results than memetic algorithm with population management (MA \(\mid\)PM) and an improvement in results ranging from 2.20% to 8.78% compared to RTS. An adaptive large neighborhood search (ALNS) procedure was used for computing the lower bound in the formulation of the multivehicle production and inventory routing problem (MVPRP) [33]. The results of tests carried out on small, medium, and large size instances established the effectiveness of ALNS on GRASP, MA \(\mid\)PM, RTS, and TSPR. The same authors also used ALNS for the computing of upper bounds in a B&C procedure for solving the MVPRP [17]. The variable neighborhood search (VNS) was developed for PRP resolution with a homogeneous fleet of vehicles [34]. The test results for this algorithm show that it is as competitive as the ALNS algorithm. Introduced by [PERSON] [35], memetic algorithm (MA) is a powerful version of GA based on the use of local search to intensify the search in order to increase its efficiency. The preservation of diversity is crucial in evolutionary algorithms in general [36] and in GA in particular. Crossover and mutation operators are the best means of guaranteeing the diversity of the population from one generation to the next. A good strategy of combining diversification and intensification is the key to success which gives the MA a definite advantage over the GA. In the area of chain supply planning, MA was used to resolve the LSP. In this problem family, MA has been proposed for a problem of stochastic multi-product sequencing and LSP [37]. It has also been used for LSP in soft drink plants [38] and for a multi-stage capacitated LSP [39]. For the VRP family, MA has been proposed for a VRP with time windows (VRPTW) [40; 41]. See also [42; 43] for the capacitated VRP as well as [44; 45] for the use of heterogeneous fleets of vehicles. The use of MA is also very present in the optimization of integrated problems such as PRP. A MA with population management (MA \(\mid\)PM) has been developed by [PERSON] and [PERSON] [46] to solve the integrated production, inventory, and distribution problem. The authors tackled a problem of simultaneous minimization of three costs consisting of the setup cost, the inventories cost and distribution cost. Tests on 90 randomly generated instances showed the efficiency of MA! MP compared to TPDH and GRAPS. The MA was also used in a study aimed at minimizing the overall cost of setup, inventory, and distribution in a multi-plant supply chain. In this supply chain, the information flow management system called \"KANBAN\" was implemented to manage information [47]. A real case study concerning the minimization of the overall cost of production and distribution was conducted in a large automotive company [48]. In this study, the authors modeled the problem as a non-linear mixed integer programming and used a custom MA for its resolution. The MA used in this work is an adaptation of the one proposed by [PERSON] and [PERSON] [46] to solve an integrated production, inventory, and distribution problem. The remainder of this work is organized as follows: Section 2 is a description of the EDPRP. Section 3 shows the details of the MA used for EDPRP resolution.