Routing optimization of fourth party logistics with reliability constraints based on Messy GA

Li, Jia; Yanqiu, Liu; Zhongjun, Hu Article Routing optimization of fourth party logistics with reliability constraints based on Messy GA Journal of Industrial Engineering and Management (JIEM) Provided in Cooperation with: The School of Industrial, Aerospace and Audiovisual Engineering of Terrassa (ESEIAAT), Universitat Politècnica de Catalunya (UPC) Suggested Citation: Li, Jia; Yanqiu, Liu; Zhongjun, Hu (2014) : Routing optimization of fourth party logistics with reliability constraints based on Messy GA, Journal of Industrial Engineering and Management (JIEM), ISSN 2013-0953, OmniaScience, Barcelona, Vol. 7, Iss. 5, pp. 1097-1111, https://doi.org/10.3926/jiem.1126 This Version is available at: https://hdl.handle.net/10419/188645 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Journal of Industrial Engineering and Management JIEM, 2014 – 7(5) : 1097-1111 – Online ISSN: 2013-0953 – Print ISSN: 2013-8423 http://dx.doi.org/10.3926/jiem.1126 Routing Optimization of Fourth Party Logistics with Reliability Constraints based on Messy GA Li Jia, Liu Yanqiu, Hu Zhongjun School of Management, Shenyang University of Technology (China) simsfore[email protected], liuya[email protected], [email protected] Received: March 2014 Accepted: September 2013 Abstract: Purpose: The purpose of this paper is to choose a optimal routing in fourth party logistics (4PL) with the objective of transportation cost minimization under reliability level constraint. Design/methodology/approach: Reliability theory is applied to routing optimization problem. A mathematical model of the 4PL routing optimization problem with reliability constraints is built, which aims to find a route at the minimum cost. Due to the 4PL routing problem is NP-hard, two algorithms are designed: Messy Genetic Algorithm (Messy GA) and Enumeration Algorithm (EA). Findings: Through the model and algorithm, 4PL company can obtain the optimal solution quickly and effectively, according to customer’s reliability requirements. Practical implications: We give an example for test the effectiveness of the method and the algorithm. Originality/value : In this paper, we put objective factors that cause disturbances of transportation time into consideration, and reliability theory is applied to 4PL routing optimization problem. A Messy GA with double arrays encoding method is designed to solve the problem. -1097- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 Keywords: fourth party logistics, routing optimization, reliability constraints, Messy Genetic Algorithm, Enumeration Algorithm 1. Introduction With the growing of economic globalization, the transnational corporations’ demand of logistics and supply chain management is increasing timely. (Chen, Xie, Fan, Li, Zhang & Huang, 2012). In order to meet the unique and special needs of the corporations, the fourth party logistics (4PL) emerged (Chen, Liu & Li, 2004). The 4PL provider is a supply chain integrator that assembles and manages the resources, capabilities, and technology of its own organization with those of the third party logistics (3PL) providers to deliver a comprehensive supply chain solution. The customers can achieve their diversified integration solutions, and the fast, high-quality and low-cost logistics services will be provided (Yao, 2010). The 4PL network is a complex engineered system due to its size and span. Its reliability has increasingly become one focus of business concern. However, the current planning and design of logistics network take little customers’ demand of system reliability. Genetic Algorithms (GA) is a general-purpose stochastic and parallel search methods based on the mechanics of natural selection and natural genetics (Potvin & Bengio, 1996). Although GA is effective in solving many complex optimization problems, but it is poor in solving routing optimization of the 4PL. The chromosome length is variant. Hence, a Messy Genetic Algorithm (Messy GA) with double arrays encoding method is designed. The Messy GA uses three main operators: cut, splice and repair operator. These operators ensure the algorithms fast and effective. In this paper, the reliability technology is applied into the 4PL routing optimization. We put objective factors that cause disturbances of transportation time into consideration, and the mathematical model is set up. Based on the NP-hard characteristic of the problem, we will use the Messy GA and the Enumeration Algorithm (EA) to optimize the model. The effectiveness of the algorithms is tested and compared by simulation examples. The results indicate that the Messy GA outperforms the EA. 2. Literature Review The concept of 4PL was put forward in Accenture's report in 1998. Although many subsequent researches on 4PL were the extensive discussion of this concept, most of them focused on the concept interpretation of 4PL or on its qualitative discussion. Briefly summarized as follows: -1098- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 Bumstead and Cannons (2002) analyzed a series of problems from 4PL to the supply chain management and operation and explained the role of 4PL. Chen, Wang, Li and Liu (2003) introduced the concept of the 4PL and the decision supporting system in its operation. Bade and Mueller (1999) considered that 4PL can bring huge earnings to enterprises. The core ideas of these researches reveal the advantage of 4PL mode and reveal that 4PL become an inevitable trend in logistics industry development. When study the basic theories, the role and advantages of 4PL, the extensive researches on operational aspects of 4PL gradually increase, such as the design, implementation, operational status, operational technologies as well as the problems that existing in its operation. For example, Li, Wu and Mei (2012) described the structure models of supply chain and problems existing in the supply chain management, based on the excellent management ability of the 4PL and its ability to plan and design the supply chain. Shao and Chen (2011) considered that the 4PL made great efforts to integrate logistics resources and the efforts influenced the output of the third party logistics. They also researched on incentive mechanism of the 4PL subcontract with principal-agent theory. Li, Lu and Sun (2012) discussed the four operation modes of 4PL in China in detail: coordinated operation type, integrated program type, innovative industry type, and dynamic alliance type. They analyzed those modes and internal and external logistics business environment, firm size and industry conditions that the four types of models adapt to. Zhang, Chen and Liu (2004) set up a target system of transporters. They built a hierarchy model for 4PL. Win (2008) presented a conceptual model that is based on research of 4PL implementation. In addition, scholars also studied some special issues about 4PL. For example, Li, Ying, Liu, Chen and Huang (2003) developed a 4PL optimization system for operative planning tasks. Lau and Goh (2002) studied multi-Agent intelligent network systems based on 4PL. Wang, Zhao and Li (2006) presented a tabu search algorithm for model of integration of 4PL and so on. In the previous studies of 4PL, the parameters are fixed and deterministic, which is not realistic. In a real-world situation, the driving conditions could be affected by many factors, such as weather and human factors (Du & Yi, 2013). Under this condition, we put objective factors that cause disturbances of transportation time into consideration. We describe the transportation time of the problem as random variables, and a real world 4PL routing problem model is built by using the reliability theory. -1099- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 3. Description of Problem and Mathematical Model 3.1. Description of Problem A potential 4PL network is modeled as a directed graph G(V, E) . “V” denotes the set of supply, transshipment, and demand nodes. “E” denotes the set of the arcs, namely 3PL providers for transportation between two cities. There is one supply node and one demand node on the 4PL network. Each node has properties of cost and capacity. Since there may exist several 3PL providers for the transportation between any two nodes, there may have multiple arcs between two nodes (one arc stands for a 3PL provider), which results in a directed graph, which results in a directed graph. Each arc has properties of cost, time and capacity. Figure 1 is a directed graph for the 4PL routing optimization problem with twelve nodes. In this paper, the objective of the problem is to find a route (i.e., Origin-Destination pair) with minimum cost as well as subject to constraints on customer’s requirement for reliability and capacity. Figure 1. Directed graph with 12 nodes 3.2. The Reliability of 4PL The route of 4PL is composed of cities and 3PL providers. It forms a parallel system. According to reliability theory, the reliability of 4PL can be calculated by continued multiplication of the reliability of 3PL. Here, each 3PL is seen as a logistics unit. In this paper, the transportation time of the 3PL providers is uncertain and has normal distribution. Hence, the reliability of logistics unit can be defined as the probability of the goods delivered in a timely manner. It can be calculated by formula (1): (1) -1100- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 R(t): the reliability of logistics unit. T: the transportation time of logistics unit. We assume T ~ N(μ, σ2). t: the time limit of the customer's requirements. 3.3. Assumption of Model •There is only one task between the supply and demand nodes. •Each path on the 4PL network can not be reuse. •The transportation time of 3PL providers is uncertain and has normal distribution. It is independent from each other. 3.4. Establishment of Model The variables used in the representation of the routing optimization of 4PL with reliability constraints are defined as follows: qij: the number of 3PL provider between node i and j. eijk: the kth 3PL provider between node i and j, (i, j = 1, 2, …, n) (k = 1, 2, …, qij). rOD: Set of nodes and arcs in a route in directed graph. For example, rOD = {O, V2, V3, V5, V7, D}. Fijk: the unit transportation cost of the kth 3PL provider between node i and j. Fi': the unit cost of node i. Lijk: the transportation capacity of of the kth 3PL provider between node i and j. Mi: processing capacity of node i. Tijk: the time of 3PL provider represented by eijk, Tijk ~ N(μijk, σijk2). tij: time limit of node i to j. -1101- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 Rijk: the reliability of eijk, ROD: the reliability of OD pair, R0: desired reliability level. The mathematical model for 4PL routing optimization problem with reliability constraints can be described as follows: (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) Where (2) is the objective function containing the costs of all nodes and arcs on the route; constraint (3) indicates the reliability of OD pair must meet customer’s requirement; constraint (4) represents capacity of the selected 3PL provider must be not less than the transportation capacity L required by customer; constraint (5) denotes capacity of nodes in a route must be not less than customer required capacity M. Eq. (6) means to keep a balance of the network flow. Eqs. (7) and (8) ensure that the selected nodes and arcs should make up of routes from the source to the destination. Eqs. (9) and (10) represent that Xijk and Yi are 0-1 decision variables, respectively. Eq. (11) is used to ensure that the selected route is a legal one. -1102- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 4. Algorithm Design The 4PL routing optimization problem with reliability constraint is a typical NP-hard problem. According to the characteristics of the model, a Messy Genetic Algorithms (Messy GA) with double arrays encoding method is designed. In the following, we first describe the Messy GA in detail and then introduce an Enumeration Algorithm (EA), which is used to check the quality of the solutions obtained by the Messy GA. 4.1. The Messy GA According to the characteristics of the model, a Messy GA with double arrays encoding method is designed. Messy GA differs from normal genetic algorithms in that they allow variable-length strings. The detailed description of the process can be written as below: Step 1. Encoding. For the problem’s characteristic, the double arrays coding method is adopted where optional nodes in graph are the elements of one array coded by natural number and 3PL providers make up the other array coded by integer number and the length of individuals are variant. The dotted route in Figure 1 is shown in Figure 2, and it can be encoded as [O V1 V3 V7 V9 D e3 e2 e1 e3 e1]. O V1V3V7V9D e3e2e1e3e1 Figure 2. The encoding method of OD pair Step 2. Initialization. Generate the initial population of PS chromosomes randomly. Population size is PS. -1103- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 Step 3. Fitness function. The objective function is a commonly used fitness function to justify the quality of a solution (X, Y). So a fitness function is usually designed according to the objective function and constraints of the problem. In this paper, the reliability constraint is used as a penalty added to the objective function. The fitness function is represented by Equation (12). From the solution (X, Y) we obtain the objective value , as well as the penalty value. (12) λ is a factor that the decision-maker can adjust to weight the penalty of violating the reliability constraints. Based on the results of some preliminary experiments, we set λ = 2 in our numerical tests. A smaller fitness value f(X, Y) indicates better fitness. If a solution (X, Y) is feasible, the second part of Equation (12) is 0 and the fitness value is exactly the objective value; if the solution violates some of the reliability constraints, its fitness will be penalized by an amount based on the constraint violations. Step 4. Selection mechanism. The selection process is based on spinning the roulette wheel. Step 5. Crossover operation. Perform crossover operations on pairs of selected chromosomes with a crossover probability Pc. For example, two genes A and B shall be exchanged in the crossover procedure. The crossover procedure is shown in Figure 3. After cut operator and splicing operator, chromosome A’’ and B’’ may be invalid. Therefore, repairing operation is necessary. We need to adjust the chromosome to ensure that it is a connective route. Detailed description of the process can be written as below: Step 5.1. If there are same nodes on the route, delete one node and the adjacent arc. If not, go to Step 5.2. Step 5.2. If the new one is still a route from the source to the destination, quit with success. If not, add all the nodes after the crossover point into the Setp. Define the node before the crossover point as the tracker node Vt. Define the genes before the crossover point as the effective route L. -1104- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1126 Shao, J.G., & Chen, Q. (2011). The Advantages and Development Strategies of the Fourth Party Logistics in China. 2nd International Conference on Engineering and Business Management, 923-928. Wang, Y., Zhao, H., & Li, Y. (2006). Tabu search algorithm for optimization model of integration of job of 4th party logistics. Journal of Systems Engineering, 21(2), 143-149. Win, A. (2008). The value a 4PL provider can contribute to an organization. International Journal of Physical Distribution & Logistics Management, 38(9), 674-684. http://dx.doi.org/10.1108/09600030810925962 Yao, J.M. (2010). Decision optimization analysis on supply chain resource integration in fourth party logistics. Journal of Manufacturing Systems, 29(4), 121-129. http://dx.doi.org/10.1016/j.jmsy.2010.12.002 Zhang, H., Chen, J.Q., & Liu, W.H. (2004). Appraisement of Transporters in Fourth Party Logistics. Industrial Engineering Journal, 7(3), 36-39. Journal of Industrial Engineering and Management, 2014 (www.jiem.org) Article's contents are provided on a Attribution-Non Commercial 3.0 Creative commons license. Readers are allowed to copy, distribute and communicate article's contents, provided the author's and Journal of Industrial Engineering and Management's names are included. It must not be used for commercial purposes. To see the complete license contents, please visit http://creativecommons.org/licenses/by-nc/3.0/. -1111-