# A Memetic Algorithm for an External Depot Production Routing Problem
## 1 Introduction  
In the supply chain field, simultaneously planning production, inventories and distribution while minimizing the overall cost of these operations is a complex exercise known as the production routing problem (PRP) [1]. The PRP is a combination of two well-known problems in the literature. On the one hand, we have the lot sizing problem (LSP) and the vehicle routing problem (VRP) on the other hand. LSP determines the best trade-off between production and storage operations. The aim is to simultaneously determine the production schedule, quantities to be produced and quantities to be stored to minimize the overall cost of production and inventory. See [2] for more detailed literature review on the LSP. VRP is a difficult NP-Hard problem as a particular case of the traveling salesman problem (TSP) which is itself a NP-Hard problem [3, 4]. It consists of arranging routes between customers who must be visited at the same time based on the number of vehicles available and finding the best scheduling of visits to minimize the overall cost of transport over the planning horizon. Readers are also invited to see [5, 6, 7] for a review of the mathematical formulations of the problem and the methods or algorithms used to resolve it. In the practice of industries, these two problems are disjointedly and sequentially analyzed. However, the work of [PERSON] et al. [8, 9] have shown that it is possible to make gains of 3% to 20% on the overall cost of production and distribution by integrating and coordinating the decisions of LSP and VRP. This integrated and coordinated PRP is a NP-hard problem since it contains the VRP. In an integrated concept of supply chain planning,the customer no longer has exclusive control over decisions on his visit dates and quantities to be received. The implementation of new practices such as vendor managed inventory (VMI) and replenishment policies such as order-up-to-level (OU) and maximum level (ML) are necessary to achieve the goal of satisfying customer demand. VMI is a practice in which the supplier decides when and how much to deliver to the customer in a joint manner. He must also ensure that there is no shortage of stock at the customer. In the OU replenishment policy, all customers have maximum storage capacity and the amount delivered is such that the maximum level of storage is reached at each delivery. Whereas in the ML policy, all customers have maximum storage capacity and the quantity delivered is such that the maximum storage level is not exceeded at each delivery (\(0\leq q_{it}\leq L_{i}\)). See [10; 11; 12; 13] for more details on the practice of VMI and the use of OU and ML replenishment policies. A detailed literature review of PRP was provided by [1]. Although PRP is an NP-hard problem, exact methods for its resolution have been proposed. Among these exact approaches, the Lagrangian relaxation was one of the first methods proposed for the resolution of the PRP [14]. A branch-and-price algorithm was proposed to solve a PRP with the use of a homogeneous fleet of vehicles [15]. In a study using a single vehicle [16], the authors used a branch-and-cut (B&C) algorithm to solve the PRP problem. The B&C algorithm has also been proposed to solve the multivehicle version of the PRP [17]. Given the complexity of the PRP, several heuristics and metaheuristics have been developed for its resolution. In the first works on the PRP introduced by [PERSON] et al. [9], an H1 type decomposition method was proposed. The authors decomposed the problem into a capacitated LSP and VRP followed by some local search heuristics to solve the problem. Test results have shown that the integrated approach allows gains on the overall cost of operations ranging from 3% to 20%. Another two-phase decomposition method was presented for solving a PRP with a heterogeneous fleet of vehicles [18]. The authors used a mixed integer programming (MIP) to solve the first phase of the problem. This first phase of the problem concerns a problem of LSP with direct shipment (DS).