A memetic algorithm with extended random path encoding for a closed-loop supply chain model with flexible delivery

In previous studies, the design of forward and reverse logistics network was typically separated. In the field of forward logistics many models were developed as part of a traditional logistics network design. The common MILP model involves the choice of facilities to be open and the distribution network design to satisfy the demand with minimum cost.

Yeh [7] developed a MILP model for a supplier-production-distribution network. He revised existing mathematical models presented by other researchers and developed an efficient hybrid heuristic, which was enriched by applying three different local search techniques. The efficiency of the proposed methodology was demonstrated via computational results. Syarif et al. [8] proposed a MILP formulation for a fixed charge and multistage transportation problem for a single commodity supply chain model. They considered a spanning tree-based GA using Prüfer number representation to solve this problem. Some comparison between results obtained by this method and LINDO showed the efficiency of proposed method. A two-echelon facility location problem was studied by Tragantalerngsak et al. [9]. In this work, each facility in the second echelon was limited in capacity and could only be supplied by one facility in the first echelon. Also, each customer is serviced by only one facility of the second echelon. The authors presented a mathematical model for the problem and developed a Lagrangian relaxation-based branch-and-bound algorithm to solve it. A different two-stage distribution-planning problem was addressed by Gen et al. [10] to minimize the total cost including transportation and opening costs. They presented a priority-based genetic algorithm (pb-GA) with a new decoding and encoding method. Also they introduced a new crossover operator called Weight Mapping Crossover and analyzed the effect of the latter on the computational performance. They showed the efficiency of proposed method with regards to solution quality and computing time in comparison to two different GA approaches.

Due to legislative changes regarding end-of-life (EOL) [11] issues as well as economic factors [12], considering the forward logistic network and omitting any reverse flow is impractical. A general review of the current developments in reverse logistics was reported by Pokharel and Mutha [13]. They identified three factors, which differ for reverse logistics and a traditional supply chain: (1) Most logistics networks are not equipped to handle returned product movement; (2) Reverse distribution costs may be higher than moving the original product from the plant to customer; (3) Returned products may not be transported, stored, or handled in the same manner as in the regular channel [14]. In a study by Jayaraman et al. [15], an analytical model to minimize reverse distribution costs was developed. This MILP model limited supply of customer demand from a single distribution center. In addition, there was a tight bound on the number of collection and refurbishing sites. Apart from the formulation of a reverse distribution problem, the authors also presented a new heuristic solution method. The algorithm has three components: random selection of potential collection and refurbishing sites, heuristic concentration and heuristic expansion. Min et al. [16] designed a MINLP model to minimize the overall reverse logistics costs including spatial and temporal consolidation of returned products. The authors presented a mathematical model for the problem and solved it using GA. There are other studies on reverse logistics, which are limited to specific applications, such as carper recycling by Louwers et al. [17] and Realff et al. [18], battery recycling by Schultmann et al. [19] as well as Kannan et al. [20], tire recycling by Figueiredo and Mayerele [21], paper recycling by Pati et al. [22], plastic recycling by Huysman et al. [23], bottle recycling by Shen et al. [24], sand recycling by Listes and Dekker [25]. Notable work with a remanufacturing focus was presented by Krikke et al. [26] on copiers and Srivastava [27] on appliances and personal computers. Currently, no general model for reverse logistics exits.

In recent years, some researches started to integrate forward and reverse networks to close products cycles. The aim is to avoid sub-optimality of a solution due to separated design [28]. Lee and Dong [29] proposed a MILP model, which is capable to manage the forward and reverse flows at the same time for end-of-lease computer products. They presented the first attempt of solving the integrated design problem using a Tabu search-based MA. Lu and Bostel [30] designed a two-level location problem as a MILP model with three types of facility (producers, remanufacturing centers and intermediate centers). This model considers forward and reverse flows and their interactions simultaneously. The focus of this research was on remanufacturing to reduce costs of production and raw materials. The model was solved using Lagrangian heuristics, which requires lower and upper bound of the objective function. Pishvaee et al. [31] focused on a MILP model to integrate reverse logistics activities into the forward supply chain. To deal with uncertainty, they presented a scenario-based stochastic optimization model to minimize the total cost including fixed opening costs, transportation cost, processing costs and penalties for non-utilized capacities. Pishvaee et al. [32] proposed a linear multi-objective programming model to improve the total cost as well as responsiveness of the integrated forward/reverse logistics network. To find the set of non-dominated solutions, the authors proposed a solution algorithm based on a new dynamic search strategy using three different local searches. Within the model, they allowed for a hybrid distribution-collection facility. The authors compared their pareto-optimal solutions to recent GA results.

To increase market share, companies try to increase customer satisfaction via fast delivery, which requires supply chain responsiveness [32, 33]. To deal with the issues of cost efficiency and network responsiveness simultaneously, researchers have proposed models to optimize the supply chain network, respectively [4, 32]. However, results are typically limited to shipments between consecutive stages or just indirect shipment mechanisms [4, 32, 34]. Lin et al. [35], formulated a MILP model by including direct shipment and direct delivery as well as inventory control for a three stages forward logistics network. To solve the problem, they proposed a hybrid evolutionary algorithm composed of Wanger within algorithm, GA, and fuzzy logic controller. Pishvaee and Rabbani [36] studied the responsiveness of a three-stage forward logistics network when (1) direct shipment between plant to customer is allowed and (2) direct shipment is forbidden. They proposed two mixed integer programming models for these conditions and proved that both of these problems can be modeled by a bipartite graph. To tackle these NP hard problems, a novel heuristic solution method was considered based on a new chromosome representation derived from graph theory. Based on the above review, extending the following restrictions can be considered a potential field of research:Within the literature, various facility location models based on mixed integer programming (MIP) were considered to determine maximal profit, optimal number and capacity of facilities as well as the optimal flow between them. Although typically larger models are required to represent real supply chains, researchers developed many heuristics [7, 15, 34, 37] and metaheuristics such as genetic algorithm [4, 6, 20, 38‐42], simulated annealing [43‐45], tabu search [29, 46], memetic algorithm [32, 47] and scatter search [34] to solve these NP hard problems. However, there is still a critical need in this area to increase the efficiency of solution approaches, especially, when the complexity of the model increases (Melo et al. [48]).

The problem addressed in this work includes integrated design of forward and reverse logistics as well as flexibility in delivery paths for a seven-stage closed-loop supply chain network. The proposed model as a complete and general network covers the previously described cases in the literature with less complexity. Additionally, the full delivery graph allows us to solve the conflicting goals profit and responsiveness, which otherwise may lead to greater cost [32]. From the computational point of view, we incorporate the graph structure in the chromosome representation, thereby avoiding different model and solution methodologies as, e.g., considered by Pishvaee and Rabbani [36].

The previously described IFRLN setting represents an integrated supply chain with seven echelons consisting of suppliers \(S\), plants \(P\), distribution centers \(Dc\), retailers \(R\) and customers \(C\) in forward flow, as well as collection/inspection centers \(Co\) and disposal centers \(Di\) in reverse flow, cf. Fig. 2 for a schematic sketch.

We like to point out that in accordance to Fig. 1, we consider a hybrid manufacturing-recovery-recycling facility as well as a hybrid collection-inspection facility. Establishing several facilities at the same location can decrease the price in comparison with separating design.

To adapt problem (1), we impose the following assumptions:The objective of this model is to minimize the total cost of the proposed supply chain, which is composed of fixed costs for facilities and variable costs for transportation. In terms of the above notation, the cost function, the sign and the integer conditions remain identical. The constraints in (1) are specialized and we have that the capacities in each node induce the inequalitiesAdditionally, by assumption only a fraction \(p^{\text {return}}\) is returned by customers and a fraction \(p^{\text {disposal}}\) of the returned products has to be disposed off. Apart from these exceptions, the supply chain network is subject to the law of the flow conservation, i.e., in-flow and out-flow in each node must be identical for these nodes. These conditions revealLast, the demands of customers must be satisfied.

A chromosome must have the necessary gene information for solving the problem. Selecting a proper chromosome representation highly affects the performance of metaheuristic algorithm. Therefore, the first step of applying MA to a specific problem is to decide how to design a chromosome. The tree-based representation is known to be one way for representing network problems. Different methods have been developed to encode trees. One of them is matrix-encoding, was is developed by Michalewicz [51]. In this method, the solution is presented by a \(|K|\cdot |J|\) matrix where |K| and |J| are the number of sources and depots, respectively. Although this solution approach has a simple representation, applying this method requires the development of a special crossover and mutation operator for obtaining a feasible solution as well as huge amount of memory. Another tree-based representation is the Prüfer number. The use of the Prüfer number representation for solving various network problems was introduced by Gen and Cheng [52]. It requires an array of the length \(|K|+|J|-2\) with |K| sources and |J| depots. Since this method may compute infeasible solutions [39], a repair mechanism has been developed. In this regard, Jo et al. [39] presented the procedure for repairing infeasible chromosomes. Later, Gen et al. [53] introduced determinant encoding using priority which does not need any repair mechanism to guarantee feasibility of solutions. In this approach, solutions are encoded as arrays of size \(|K|+|J|\), in which the position of each cell represents the sources and depots and the value in cells represent the priorities.

From the literature [41], we have found that both Prüfer and determinant encoding are efficient for the encoding of the spanning tree problem. However, as the determinant encoding overcomes the bottlenecks of Prüfer encoding [54], we utilize determinant encoding in our study. In the following encoding and decoding are discussed.

Fitter individuals have higher chances of survival. The evaluation assigns a fitness value to each individual, thereby inducing a measure. In our study, we apply the cost function as the fitness value. This fitness value is computed for the decoded chromosome to analyze the accuracy and efficiency of the proposed MA.

Crossover is known as the most important recombination of both parents’ feature to explore new solution within the search space. There are many variants of crossover operations developed in the literature, cf. [10]. Based on the characteristics of the chromosome, we chose the two-cut point crossover, which applies the steps shown in Algorithm 2.

We apply the well-known roulette wheel selection for generating the next generation of chromosomes. The strategy of roulette wheel is a probabilistic selection based on fitness.

Combing the aforementioned components, we obtain the procedure displayed in Algorithm 4 for solving our problem IFRLN.

Note that as we apply only one crossover and search step before selecting the next generation, our method belongs to the class of steady state MA.