Model and algorithm of two-stage distribution location routing with hard time window for city cold-chain logistics

applied sciences Article Model and Algorithm of Two-Stage Distribution Location Routing with Hard Time Window for City Cold-Chain Logistics Liying Yan 1,2,3,4 , Manel Grifoll 5and Pengjun Zheng 1,3,4,* 1Faculty of Maritime and Transportation, Ningbo University, Collaborative Innovation Center for Ningbo Port Logistics Service System, Ningbo 315211, Zhejiang, China; [email protected] 2 Department of Basic Courses, Ningbo University of Finance & Economics, Ningbo 315211, Zhejiang, China 3Ningbo University Sub-Center, National Traffic Management Engineering& Technology Research Centre, Ningbo 315211, Zhejiang, China 4Collaborative Innovation Center for Modern Urban Traffic Technologies, Nanjing 211189, Jiangsu, China 5Barcelona Innovation in Transport (BIT), Barcelona School of Nautical Studies, Universitat Politècnica de Catalunya-BarcelonaTech, 08003 Barcelona, Spain; [email protected] *Correspondence: [email protected] Received: 15 March 2020; Accepted: 3 April 2020; Published: 8 April 2020   Abstract: Taking cold-chain logistics as the research background and combining with the overall optimisation of logistics distribution networks, we develop two-stage distribution location-routing model with the minimum total cost as the objective function and varying vehicle capacity in different delivery stages. A hybrid genetic algorithm is designed based on coupling and collaboration of the two-stage routing and transfer stations. The validity and feasibility of the model and algorithm are verified by conducting a randomly generated test. The optimal solutions for different objective functions of two-stage distribution location-routing are compared and analysed. Results turn out that for different distribution objectives, different distribution schemes should be employed. Finally, we compare the two-stage distribution location-routing to single-stage vehicle routing problems. It is found that a two-stage distribution location-routing system is feasible and effective for the cold-chain logistics network, and can decrease distribution costs for cold-chain logistics enterprises. Keywords: two-stage distribution; location-routing; hybrid genetic algorithm 1. Introduction Many cities find it challenging to set up a high-efficiency city logistics system to increase freight efficiency and decrease the impacts of city distribution on city living conditions [ 1 ]. Macharis et al. [ 2 ] pointed out that urban goods distribution (UGD) has an important impact on the sustainable development of cities. It is necessary to find new solutions for the management of freight distribution in order to reach a higher level of efficiency. So a city logistics model and some urban freight traffic policies have been studied by many researchers such as Taniguchi et al. [ 3 ], Allen et al. [ 4 ], Taniguchi et al. [ 5 ], Anand et al. [ 6 ], Danielis et al. [ 7 ]. Allen et al. [ 8 ] showed that the use of urban consolidation centers (UCC) is presumed to provide more efficient distribution in an urban area, and it can decrease energy use and environmental impact. A UCC can be described as a logistics facility located in relatively close proximity to the geographic area that it serves, and with the range of terms used to refer to the UCC concept main including a public distribution depot, urban trans-shipment center, freight platforms, cooperative delivery system, urban distribution center, consolidation center (sometimes specific, e.g., retail, construction), pick-up drop-offlocation, offsite logistics support concept and so on [ 9 ]. UCCs are one of the most frequently implemented and studied city logistics initiatives, and according to Lagorio Appl. Sci. 2020,10, 2564; doi:10.3390/app10072564 www.mdpi.com/journal/applsci Appl. Sci. 2020,10, 2564 2 of 16 et al. [ 10 ] many case studies have been presented in literature [ 11 , 12 ]. One of the most efficient and typical ways to implement goods consolidation is to adopt multi-stage distribution systems, especially two-stage distribution system, where the delivery from distribution center to customers is managed by routing and consolidating the freight through intermediate depots called transfer stations [ 13 ]. Therefore, selection of the locations of the transfer stations and planning of the two-phase distribution routes are key problems in city logistics system optimization. With the development of the economy and the continuous improvement of people’s living standards in China, demand for cold-chain products has also increased to a large extent, which promotes rapid development of the cold-chain logistics. The cold chain has become an important part of the urban distribution system. The remainder of this paper is organised as follows. Firstly, the location-routing problem is described in a literature review. Then a two-stage location-routing model is constructed and a metaheuristic algorithm is implemented to solve the model. The algorithm is included as a hybrid genetic algorithm [ 14 ]. Finally, the feasibility and validity of the model and algorithm are demonstrated through a test example, and results of the study are summarised. 2. Literature Review The concept of the location-routing problem (LRP) can be traced back to 1961. Von Boventer first discussed the relationship between location selection and transportation cost in transportation problems [ 15 ]. LRP and its variants have been studied extensively in the past. Perl and Daskin proposed a multi-vehicle and multi-facility warehouse location-routing problem model with vehicle capacity constraints [ 16 ]. Li et al. [ 17 ] studied a three-tier distribution system with suppliers, warehouses, and multiple geographically dispersed retailers, where retailers could replenish goods from warehouses and suppliers. A model was established to minimize the long-term average cost within the system while meeting the demand of each retailer. Prodhon [ 18 ] put forward a linear programming model for multi-plan periodic location paths by reasonably defining variables and designed a hybrid evolutionary algorithm to solve it. Xu [ 19 ] introduced the damage cost of goods incurred in transit and established a location-route optimisation model considering two-stage transportation cost, damage cost, and penalty cost, and service level. A Genetic Algorithm-Particle Swarm Optimization algorithm was designed to solve the problem. However, the energy consumption cost was not considered in the model. Song et al. [ 20 ] studied the LRP of a multi-journey vehicle path, i.e., considering that the vehicle runs multiple routes within the travel constraint time, and a three-stage heuristic algorithm was designed to solve the problem. Zhao et al. [ 21 ] build a heterogeneous fleet two-echelon capacitated location-routing model for joint delivery in city logistics. Wang et al. [ 22 ] proposed a bi-objective model, and designed an improved algorithm. The effectiveness of the improved algorithm was demonstrated through a comparison. Koç et al. [ 23 ] established a location-routing problem model considering a heterogeneous fleet and time windows. A hybrid evolutionary algorithm combining multiple heuristics was designed to solve the problem. Leng et al. [ 24 ] considered multiple conditions in the regional low-carbon location-routing problem, such as simultaneous pickup and delivery, time windows. Yu et al. [ 25 ] and Zhao et al. [ 26 ] studied location-routing problem with simultaneous pick-up and delivery. To solve the problem, a simulated annealing (SA) heuristic algorithm was designed and a hyper-heuristic approach based on iterated local search was proposed, respectively. For the cold-chain logistics problems, Yang et al. [ 27 ] studied a location model for perishable products in two-tier distribution centers, introduced the cost of goods damage into the objective function, designed an improved genetic algorithm to solve the model, and demonstrated the effectiveness of the model and algorithm through an example. However, the distance studied was calculated using the radial shape of the location and demand points. Zhao et al. [ 28 ] designed a satisfaction degree function according to service time windows and introduced a minimum envelope clustering analysis method and tabu search algorithm to solve the problem. Zheng et al. [ 29 ] constructed location inventory routing problem under a demand environment in a cold-chain logistics network, and non-dominated Appl. Sci. 2020,10, 2564 3 of 16 sorting introduced a multi-objective genetic algorithm (GA). Wang et al. [ 30 ] studied a cold-chain logistics distribution network considering carbon footprint, the model of minimum total cost including carbon emission cost was constructed, and a hybrid algorithm was designed to solve the model. Most of the existing LRP research focused on a general logistics distribution network and single-stage location-routing problems. When it comes to two-stage LRP, most of the models assume that the transportation path between the distribution center and the transfer stations is radial, i.e, the vehicle only provides services for one transfer station at a time and then returns to the distribution center, and most of the algorithms are involved in single-stage optimisation of transfer station selection and paths without considering the coupling and collaborative optimisation of the two stages. In view of this, we studied a two-stage cold-chain logistics distribution network, including two-stage optimisation of transfer station locations and routing. A two-stage location-routing model with the minimum total cost associated with the hard time window is constructed, and different types of vehicles are considered for distribution tasks. An integrated approach is employed to design the algorithm to ensure the quality of the solution. Finally, through a case study, we verify the feasibility and effectiveness of the model and algorithm. 3. Model Formulation 3.1. Problem Description The cold-chain logistics problem considered in this study comprises a cold-chain logistics distribution center, multiple potential cold-chain logistics transfer stations and customer points. The distribution center need to deliver goods to the customers through transfer stations within a specified time window. In the system, the distribution center, transfer stations, and routing between them constitute the first-stage city logistics network. The transfer stations, customers, and routing between them constitute the second-stage city logistics network. As shown in Figure 1, we optimise locations of transfer stations and the two-stage distribution network vehicle routing problem under the condition of minimum total cost. Appl. Sci. 2019, 9, x FOR PEER REVIEW 3 of 17 For the cold-chain logistics problems, Yang et al. [27] studied a location model for perishable 88 products in two-tier distribution centers, introduced the cost of goods damage into the objective 89 function, designed an improved genetic algorithm to solve the model, and demonstrated the 90 effectiveness of the model and algorithm through an example. However, the distance studied was 91 calculated using the radial shape of the location and demand points. Zhao et al. [28] designed a 92 satisfaction degree function according to service time windows and introduced a minimum 93 envelope clustering analysis method and tabu search algorithm to solve the problem. Zheng et al. 94 [29] constructed location inventory routing problem under a demand environment in a cold-chain 95 logistics network, and non-dominated sorting introduced a multi-objective genetic algorithm (GA). 96 Wang et al. [30] studied a cold-chain logistics distribution network considering carbon footprint, 97 the model of minimum total cost including carbon emission cost was constructed, and a hybrid 98 algorithm was designed to solve the model. 99 Most of the existing LRP research focused on a general logistics distribution network and 100 single-stage location-routing problems. When it comes to two-stage LRP, most of the models 101 assume that the transportation path between the distribution center and the transfer stations is 102 radial, i.e, the vehicle only provides services for one transfer station at a time and then returns to the 103 distribution center, and most of the algorithms are involved in single-stage optimisation of transfer 104 station selection and paths without considering the coupling and collaborative optimisation of the 105 two stages. In view of this, we studied a two-stage cold-chain logistics distribution network, 106 including two-stage optimisation of transfer station locations and routing. A two-stage 107 location-routing model with the minimum total cost associated with the hard time window is 108 constructed, and different types of vehicles are considered for distribution tasks. An integrated 109 approach is employed to design the algorithm to ensure the quality of the solution. Finally, through 110 a case study, we verify the feasibility and effectiveness of the model and algorithm. 111 3. Model Formulation 112 3.1. Problem Description 113 The cold-chain logistics problem considered in this study comprises a cold-chain logistics 114 distribution center, multiple potential cold-chain logistics transfer stations and customer points. The 115 distribution center need to deliver goods to the customers through transfer stations within a 116 specified time window. In the system, the distribution center, transfer stations, and routing between 117 them constitute the first-stage city logistics network. The transfer stations, customers, and routing 118 between them constitute the second-stage city logistics network. As shown in Figure 1, we optimise 119 locations of transfer stations and the two-stage distribution network vehicle routing problem under 120 the condition of minimum total cost. 121 122 Figure 1. Schematic map of location-routing in two-stage distribution. 123 Figure 1. Schematic map of location-routing in two-stage distribution. 3.2. Problem Assumptions To facilitate the study, the following assumptions are made: (1) the geographical location of distribution center, potential transfer stations, time window, demand of customers are known; (2) each customer can only be served by one delivery vehicle; (3) the demand of a single customer is less than the vehicle capacity. (4) traffic congestion is not considered; (5) the cargo load of a vehicle should not exceed its rated load; Appl. Sci. 2020,10, 2564 4 of 16 (6) the unit transfer cost for each transfer station is known and is a constant; temperature changes and the first stage-cargo losses are not considered; (7) transfer stations compete with each other, and enterprises can choose different transfer stations to provide services according to their own cost minimization; (8) the capacity of refrigerated transport vehicles for distribution center (first-stage route) is known, and the demand of a transfer station can be greater than the capacity of a transport vehicle, i.e. the demand of the first-stage distribution path can be split; (9) the capacity of refrigerated transport vehicles (second-stage route) for transfer stations is known, and can not be exceeded. Each vehicle will return to the starting point after completing tasks; (10) types of vehicles are different for deliveries from distribution center and transfer stations, and capacities of same type of vehicles are the same, and there are enough transport vehicles for the system. 3.3. Parameter and Variables To build the model, the following parameters and variables are defined: M: Set of candidate transfer stations and distribution center; M1: Set of candidate transfer stations; Ng: Set of customers assigned to transfer station g, and transfer station g; K: Set of refrigerated vehicles in the distribution center; Lg: Set of refrigerated vehicles in the gtransfer station; dij: Distance between ipoint and jpoint; v1: Average speed of refrigerated vehicles in the first-stage route; v2: Average speed of refrigerated vehicles in the second-stage route; sl i: Service times of vehicle lfor the i-th customer (or transfer station); c1: Use and consumption cost of vehicles per kilometre in the first-stage route; c2: Use and consumption cost of vehicles per kilometre in the second-stage route; c0 1: Cost of the driver in the first-stage route; c0 2: Cost of the driver in the second-stage route; uk j : Remaining cargo volume of the refrigerated vehicle kwhen arriving at the transfer station or the customer point j; bk j : Remaining cargo volume of the refrigerated vehicle kwhen leaving the transfer station or customer point j; P1: Price of unit commodity; θ1: Spoilage rate of product in the transportation process; θ2: Spoilage rate of product in unloading process; W1: Fuel consumed in operating the refrigerator during transportation; W2: Fuel consumed in refrigerator operation during unloading; θ3: Fuel price per unit weight; tl i: Time when the refrigerated vehicle lreaches point i; tl ij: Time required by a refrigerated vehicle lto travel between two points iand j; tl 0g: Departure time of refrigerated vehicle lfrom the transfer station g; λ1: Transit cost per unit of time; Wg: Amount of goods transferred at the g transfer station; v3: Transfer point unloading processing speed; qi: Demand of transfer station i; q0 i: Demand of customer i; Q1: Vehicle capacity in the first-stage route; Appl. Sci. 2020,10, 2564 5 of 16 Q2: Vehicle capacity in the second-stage route; Xk ij is a 0–1 variable: when Xk ij =1, the vehicle kpasses the road between transfer station(or distribution center) iand transfer station(or distribution center) j; otherwise, Xk ij =0; xk jis a 0–1 variable: when xk j=1, the vehicle kservices for customer i; otherwise, xk j=0; xl ijg is a 0–1 variable: when xl ijg =1, the vehicle lof transfer station gpasses the road between customer (or transfer station ) iand customer (or transfer station) j; otherwise, Xl ijg =0; Zgis a 0–1 variable: when Zg=1, the transfer station gis used; otherwise, Zg=0; yl ig is a 0–1 variable: when yl ig =1, the vehicle lof transfer station g provides service for customer i; otherwise, yl ig =0. 3.4. Model Development The two-stage distribution location-routing with hard time window for city cold-chain logistics model constructed in this paper takes the minimum total cost as the objective function. In consequence, the sub-cost should be analyzed firstly. Then the total cost of the two-stage distribution location-routing is obtained by the various sub-costs. 3.4.1. Objective Function Analysis of Model (1) Transportation Cost The transportation cost mainly includes vehicle use cost, fuel used in the process of transportation, driver’s cost, and other factors. For the convenience of research, the transportation cost is considered in two parts, referring to the use and consumption cost of vehicles per kilometre and driver’s cost. The transportation cost of a refrigerated vehicle in the first-stage and second-stage routes can be expressed as follows: C1=c1X k∈K X i,j∈M Xk ijdij+c0 1X k∈K X i,j∈M (Xk ij dij v1 +sk j)(1) C0 1=c2X g∈M1 X l∈Lg X i,j∈Ng Zgdijxl ijg +c0 2X g∈M1 X l∈Lg X i,j∈Ng Zg(dij v2 xl ijg +sl j)(2) (2) Damage Cost Commodities in the cold-chain distribution are easily spoiled and therefore need to be kept in an appropriate low-temperature environment. The quality of perishable goods gradually declines or can lose value with time. When the quality of the product declines to a certain extent, spoilage cost will be incurred. The cost of damage is divided into two parts: the damage cost of goods accumulated over time in the process of transportation and the damage cost incurred when opening the door in the process of unloading. Because the first-stage delivery is usually carried out in an enclosed environment, spoilage cost will be minimal. We only considered the damage cost in the second-stage distribution. Hence, the total damage cost can be expressed as: C0 2=P1X g∈M1 X l∈Lg X j∈Ng Zgyl jg(1−e−θ1(tl ij−tl 0g))ul j+P1X g∈M1 X l∈Lg X j∈Ng Zgyl jg(1−e−θ2sl j)bl j(3) The first part represents the cost of cargo damage in the transportation process, and the second part represents the cost of cargo damage in the unloading process. (3) Refrigeration Cost The cost of storage associated with maintaining the temperature and humidity inside the carriage is called the refrigeration cost. The refrigeration methods employed in refrigerated vehicles on the market Appl. Sci. 2020,10, 2564 6 of 16 today mainly include liquid nitrogen refrigeration, mechanical refrigeration, dry ice refrigeration, and cold plate refrigeration. The refrigeration method considered in this study is mechanical refrigeration, and the cost generated in the refrigeration process is related to fuel consumption, time, and weight of goods. Literature [31,32] proposed a formula for calculating the fuel consumption: W=ωεPe ξ∗10−3. The refrigeration cost includes the cost associated with the energy consumption of the vehicle in maintaining a low-temperature environment during delivery and the cost of additional energy supplied to the refrigeration system during the unloading process. The refrigeration cost in the first-stage and second-stage route can be expressed as follows: C3=θ3W1X k∈K X i,j∈M dijxk ijuk j v1 +θ3W2X k∈K X j∈M xk jbk jsk j(4) C0 3=θ3W1X g∈M1 X l∈Lg X i,j∈Ng Zg dijxl ijgul j v2 +θ3W2X g∈M1 X l∈Lg X j∈Ng Zgsl jbl j(5) where, W is the fuel consumption (g/h); ω is the power utilization coefficient of the refrigerator; ε is the fuel consumption rate (g/kW · h); Pe is the effective power of the refrigerator (kW); ξ is the specific gravity of the fuel; W1 is the fuel oil consumption during transportation; and W2 is the fuel consumption during unloading. The first part represents the refrigeration cost of refrigerated vehicles during transportation, and the second part represents the refrigeration cost of the refrigerated vehicles during unloading. (4) Penalty Cost In an actual distribution process, the distribution vehicles may not arrive on time for various reasons, this will incur a penalty cost. The concept of a time window is introduced. As the timing for first-stage distribution is flexible, we only consider the time window requirements of the customers in the second-stage distribution. The time window is divided into a hard time window and a soft time window. Considering the characteristics of cold-chain distribution, we calculated the penalty costs associated with the hard time window. Assuming that the earliest service time allowed by customer i is ET i ,the latest service time allowed by customer iis LT i , the service time window required by the customer iis [ETi,LTi]. The penalty function equation can be expressed as follows [33]: C4=P(t) =          M t <ET 0ET ≤t≤LT M t >LT where Mis infinite. tis the time when the vehicle arrives at the customer. [ET,LT] is the service time window required by the customer. (5) Transfer Cost The cost at the transfer station mainly consists of the time cost incurred in the transfer of goods from large refrigerated vehicles to small refrigerated vehicles. Therefore, the transfer cost can be expressed as follows: C5=λ1X g∈M1 Zg Wg v3 (6) Appl. Sci. 2020,10, 2564 7 of 16 3.4.2. Model Setting Based on the analysis of sub-cost in Section 3.4.1, a two-stage distribution location-routing model with the hard time window constrains for city cold-chain logistics is established as follows: Minz1=C1+C0 1+C0 2+C3+C0 3+C4+C5(7) Subject to: X i∈M1 Xk iqi≤Q1k∈K(8) X i∈Ng q0 iyl ig ≤Q2g∈M1,l∈Lg(9) X j∈M Xk ij =Xk ii∈M;k∈K(10) X i∈M Xk ij =Xk j,j∈M;k∈K(11) X i∈Ng X g∈M1 xl ijg =yl jg j∈Ng,l∈Lg(12) X j∈Ng X g∈M1 xl ijg =yl ig i∈Ng,l∈Lg(13) X g∈M1 X l∈Lg yl jg =1j∈Ng(14) X j∈Ng xl ijg =X j∈Ng xl jig ≤1i=g∈M1;l∈Lg(15) X j∈M1 Xk ij =X j∈M1 xk ji ≤1i=0; k∈K(16) X i∈Ng q0 iyig ≤Zgqgg∈M1(17) ETi≤tl i≤LTi(18) The objective function of the model is shown in (7). Constraint (8) shows that a vehicle cannot exceed its maximum load in the first level distribution. Constraint (9) shows that vehicle can not exceed its maximum load in the second-level distribution. The first stage of distribution flow balance is shown in (10) and (11). The second-stage of distribution flow balance is shown in (12) and (13). Constraint (14) shows that there is only one refrigerated vehicle providing a delivery service for one customer. As per constraints (15) and (16), the refrigerated vehicles starting from a transfer station must return to the same after serving the customer, and the refrigerated vehicles starting from the distribution center must return to the distribution center after serving transfer stations. The total customer requirements assigned to a transfer station must be lower than or equal to the storage capacity of the transfer station, which is imposed by (17). Constraint (18) represents the time window for customer i. 4. Algorithm Design Two-stage distribution location-routing belong to the NP-Hard problem, so we use heuristic algorithms to solve this problem. A hybrid genetic algorithm is proposed in the paper combining heuristic rules and distance clustering. The flow chart of the algorithm is shown in Figure 2. Appl. Sci. 2020,10, 2564 8 of 16 Appl. Sci. 2019, 9, x FOR PEER REVIEW 9 of 17 Decoded chromosome Transfer station capacity; vehicle capacity; Whether the termination criterion is met? End: Stop iteration and get the best population If the generation of the new population reaches the pre-set evolutionary i d h ii id Fitness evaluation: Fi=1/Zi ;Roulette gambling Two-point crossover; l Generating feasible initial population at random Starting Chromosome coding Each chromosome consists of three Mutation i Crossover i Interchange mutation; Inversion mutation; Selection operation 4. Algorithm Design 261 Two-stage distribution location-routing belong to the NP-Hard problem, so we use heuristic 262 algorithms to solve this problem. A hybrid genetic algorithm is proposed in the paper combining 263 heuristic rules and distance clustering. The flow chart of the algorithm is shown in Figure 2. 264 Figure 2. Flow chart of hybrid genetic algorithm. 265 4.1. Chromosome Coding 266 Each chromosome consists of three sub-strings: Sub-string 1 involves encoding length J. The 267 integer of gene 1 − J is a non-repetitive sequence, representing the priority selection order and 268 delivery order of the transfer station. Sub-string 2 is encoded as an integer with length N and gene 1 269 − N, representing the distribution order of the demand points. Sub-string 3 is encoded as an integer 270 code of length 1, indicating the number of transfer station selected. For example, when J = 5 and N = 271 6, namely, there are 5 transfer station and 6 customer point, for the chromosome shown in Figure 3, 272 the priority of the transition to be selected is 5, 4, 2, 1, 3. The distribution path of the demand points 273 is 2-3-4-1-5-6; 2 indicates that the first two bits of the first layer of coding are selected to set up a 274 transfer station. Moreover, 5, 4 coded in the first layer is the order of distribution of the transfer 275 station. 276 N Y Figure 2. Flow chart of hybrid genetic algorithm. 4.1. Chromosome Coding Each chromosome consists of three sub-strings: Sub-string 1 involves encoding length J. The integer of gene 1 − Jis a non-repetitive sequence, representing the priority selection order and delivery order of the transfer station. Sub-string 2 is encoded as an integer with length Nand gene 1 − N, representing the distribution order of the demand points. Sub-string 3 is encoded as an integer code of length 1, indicating the number of transfer station selected. For example, when J=5 and N=6, namely, there are 5 transfer station and 6 customer point, for the chromosome shown in Figure 3, the priority of the transition to be selected is 5, 4, 2, 1, 3. The distribution path of the demand points is 2-3-4-1-5-6; 2 indicates that the first two bits of the first layer of coding are selected to set up a transfer station. Moreover, 5, 4 coded in the first layer is the order of distribution of the transfer station. Appl. Sci. 2019, 9, x FOR PEER REVIEW 10 of 17  3 21 2|6-5-1-4-3-2|3-1-2-4-5 substring substringsubstring  277 Figure 3. Chromosome coding example. 278 4.2. Generate the Initial Population at Random 279 Genetic algorithm starts from the population of the problem solutions, so it is necessary to 280 generate an initial population as the starting point of evolution. According to the encoding method, 281 N chromosomes are randomly generated. 282 4.3. Crossover Operation 283 To maintain the diversity of the population, we conducted crossover operations for each 284 sub-string in the chromosome. Two-point crossover operation is carried out in sub-string 1. Cycle 285 crossover operation is chosen to perform on sub-string 2. Two-point crossover operation is used in 286 sub-string 3. The detailed description of crossover operation is as follows: 287 (1) Crossover operation of sub-string 1 288 Two-point crossover: firstly, two chromosomes are randomly selected as the parent, and 289 generating two random natural numbers r1 and r2. Secondly, the gene fragments between r1 and r2 290 of two parent chromosomes are exchanged, two offspring chromosomes are obtained. Finally, the 291 chromosomes of the two offspring are modified so that no conflict occurs. For example, parent 292 chromosome 1: 1 3 2 5 4, parent chromosome 2: 1 2 4 5 3, random numbers r1 = 2, r2 = 4. The 293 offspring chromosomes after crossing are offspring chromosome 1: 1 2 4 5 4 and offspring 294 chromosome 2: 1 3 2 5 3. Finally, two new offspring chromosome are obtained by repairing, new 295 offspring chromosome 1: 1 2 4 5 3, new offspring chromosome 2: 1 3 2 5 4. 296 (2) Crossover operation of sub-string 2 297 Cycle crossover: firstly, a cycle will be found according to the corresponding gene position of 298 the parent chromosome. Secondly, the circulating gene is replicated to the offspring. Thirdly, the 299 remaining genes are identified for the offspring, and the remaining genes outsides the parent 300 chromosome cycle are used to fill with the original offspring. Finally, forming new descendants. For 301 example : Firstly, parent chromosome 1 : 2 7 5 6 4 8 9 1 3, parent chromosome 2 : 4 3 6 8 9 7 1 2 5, 302 find cycle 1 : 2 4 9 1 2, cycle 2：4 2 1 9 4. Secondly, offspring chromosome 1: 2 * * * 4 * 9 1 * , offspring 303 chromosome 2 : 4 * * * 9 * 1 2 *. Thirdly, parent 1 remaining chromosome: * 3 6 8 * 7 * * 5, parent 2 304 remaining chromosome: * 7 5 6 * 8 * * 3. Finally, new offspring chromosome 1: 2 3 6 8 4 7 9 1 5; new 305 offspring chromosome 2: 4 7 5 6 9 8 1 2 3. 306 (3) Crossover operation of sub-string 3 307 Two-point crossover: random selection of two chromosomes as parents and two offspring 308 chromosomes are obtained by direct exchange of two parent chromosomes. For example, select two 309 parent chromosomes 1 and 2, the chromosomes of the crossed offspring are 2 and 1. 310 4.4. Mutation Operation 311 To maintain the diversity of the population, we conducted mutation operation for each 312 sub-string in the chromosome. Interchange mutation operation is carried out in sub-string 1. 313 Inversion mutation operation is chosen to perform on sub-string 2. Single-point mutation operation 314 is used in sub-string 3. The detailed description of mutation operation is as follows: 315 (1) Mutation operation of sub-string 1 316 Figure 3. Chromosome coding example. Appl. Sci. 2020,10, 2564 9 of 16 4.2. Generate the Initial Population at Random Genetic algorithm starts from the population of the problem solutions, so it is necessary to generate an initial population as the starting point of evolution. According to the encoding method, N chromosomes are randomly generated. 4.3. Crossover Operation To maintain the diversity of the population, we conducted crossover operations for each sub-string in the chromosome. Two-point crossover operation is carried out in sub-string 1. Cycle crossover operation is chosen to perform on sub-string 2. Two-point crossover operation is used in sub-string 3. The detailed description of crossover operation is as follows: (1) Crossover operation of sub-string 1 Two-point crossover: firstly, two chromosomes are randomly selected as the parent, and generating two random natural numbers r1 and r2. Secondly, the gene fragments between r1 and r2 of two parent chromosomes are exchanged, two offspring chromosomes are obtained. Finally, the chromosomes of the two offspring are modified so that no conflict occurs. For example, parent chromosome 1: 1 3 2 5 4, parent chromosome 2: 1 2 4 5 3, random numbers r1 =2, r2 =4. The offspring chromosomes after crossing are offspring chromosome 1: 1 2 4 5 4 and offspring chromosome 2: 1 3 2 5 3. Finally, two new offspring chromosome are obtained by repairing, new offspring chromosome 1: 1 2 4 5 3, new offspring chromosome 2: 1 3 2 5 4. (2) Crossover operation of sub-string 2 Cycle crossover: firstly, a cycle will be found according to the corresponding gene position of the parent chromosome. Secondly, the circulating gene is replicated to the offspring. Thirdly, the remaining genes are identified for the offspring, and the remaining genes outsides the parent chromosome cycle are used to fill with the original offspring. Finally, forming new descendants. For example: Firstly, parent chromosome 1: 2 7 5 6 4 8 9 1 3, parent chromosome 2: 4 3 6 8 9 7 1 2 5, find cycle 1: 2 4 9 1 2, cycle 2: 4 2 1 9 4. Secondly, offspring chromosome 1: 2 * * * 4 * 9 1 *, offspring chromosome 2: 4 * * * 9 * 1 2 *. Thirdly, parent 1 remaining chromosome: * 3 6 8 * 7 * * 5, parent 2 remaining chromosome: * 7 5 6 * 8 * * 3. Finally, new offspring chromosome 1: 2 3 6 8 4 7 9 1 5; new offspring chromosome 2: 4 7 5 6 9 8 1 2 3. (3) Crossover operation of sub-string 3 Two-point crossover: random selection of two chromosomes as parents and two offspring chromosomes are obtained by direct exchange of two parent chromosomes. For example, select two parent chromosomes 1 and 2, the chromosomes of the crossed offspring are 2 and 1. 4.4. Mutation Operation To maintain the diversity of the population, we conducted mutation operation for each sub-string in the chromosome. Interchange mutation operation is carried out in sub-string 1. Inversion mutation operation is chosen to perform on sub-string 2. Single-point mutation operation is used in sub-string 3. The detailed description of mutation operation is as follows: (1) Mutation operation of sub-string 1 Interchange mutation: Two random points are selected in the encoding string, and their positions are swapped. For example, select exchange points 3 and 7 from chromosomes 1 4 3| 926 7| 5 8, the chromosome obtained after exchange mutation is 1 4 7|9263|5 8. (2) Mutation operation of sub-string 2 Appl. Sci. 2020,10, 2564 16 of 16 32. Wang, G. Optimization Research of Common Distribution Routing Problem of Cold Chain Logistics Based on Joint Distribution Mode. Master’s Thesis, Beijing Jiaotong University, Beijing, China, 2018. 33. Shi, C.C.; Wang, X.; Ge, X.L. Research on vehicle scheduling problem of multi-distribution centers with time window. Comput. Eng. Appl. 2009,45, 21–24. © 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).