# Comparative Study of Swarm-Based Algorithms for Location-Allocation Optimization of Express Depots

Authors: Yong-Wei Zhang; Qin Xiao; Xue-Ying Sun; Liang Qi
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

The location and capacity of express distribution centers and delivery point allocation are mixed-integer programming problems modeled as capacitated location and allocation problems (CLAPs), which may be constrained by the position and capacity of distribution centers and the assignment of delivery points. The solution representation significantly impacts the search efficiency when applying swarm-based algorithms to CLAPs. In a traditional encoding scheme, the solution is the direct representation of position, capacity, and assignment of the plan and the constraints are handled by punishment terms. However, the solutions that cannot satisfy the constraints are evaluated during the search process, which reduces the search efficiency. A general encoding scheme that uses a vector of uniform range elements is proposed to eliminate the effect of constraints. In this encoding scheme, the number of distribution centers is dynamically determined during the search process, and the capacity of distribution centers and the allocation of delivery points are determined by the random proportion and random key of the elements in the encoded solution vector. The proposed encoding scheme is verified on particle swarm optimization, differential evolution, artificial bee colony, and powerful differential evolution variant, and the performances are compared to those of the traditional encoding scheme. Numerical examples with up to 50 delivery points show that the proposed encoding scheme boosts the performance of all algorithms without altering any operator of the algorithm.


---

## Body

## 1. Introduction

Since 2014, the express delivery volume in China has ranked first in the world for six consecutive years [1]. Statistics show 107.7 billion pieces of delivery in China in 2021, with a 31% growth compared with 2020 [2].The rapid growth of the Express Delivery Industry has brought fierce competition among the participants. The primary delivery companies actively improve service quality and delivery efficiency. For regional express delivery service suppliers, the location of the service center has a significant impact on efficiency and, hence, the overall operation cost.Such a problem is typically modeled as a logistic distribution problem, which minimizes total distances between the distribution center (DC) and associated delivery points (DPs) under certain constraints. The problem is twofold: one considers the location-allocation problem (LAP) of the distribution centers and the other considers the vehicle routing problem (VRP) that starts at the distribution center and goes through each delivery point and back to the distribution center. The joint problem is the location and routing problem (LRP) [3]. Both LAP and VRP are NP-hard, and the combined LRP has attracted attention since the 1960s [4]. The problem structure of LRP is shown in Figure 1.Figure 1
Problem structure of LAP, VRP, and LRP.In LRP, the optimal route associated with a given distribution center may change with the demands of the delivery point or the policy of distribution centers. Therefore, the VRP may be left to the distribution centers to solve. Since the delivery points for each distribution center are not many, the local VRP can be solved easily. Therefore, the separation of LAP and VRP could significantly reduce the complexity of the problem.The LAP may apply to a broader region, such as a country, state, or province. The options for locations are limited to a list of lower-level cities, and the options for allocation are subsets of delivery points. The solution of location usually uses binary representation because the number of options is fixed. The solution of allocation usually uses integers to denote the belonging of delivery points. Since the total number of distribution centers and delivery points is fixed, the size of a solution can be fixed as well. However, for a city-level LAP, the model and solution representation may vary because the available options for distribution centers can be many, and the setup cost and capacity of different options have a significant impact on the total cost.On the other hand, the NP-hard nature of LAP makes heuristic algorithms favorable, among which swarm-based algorithms are representative [3, 5, 6]. The solution representation plays a vital role in applying the algorithm because an efficient encoding scheme may reduce the length of the solution string, smooth the solution space, or eliminate the constraints. For example, choosing N distribution centers out of 100 candidate locations requires 100 binary bits to represent the solution, whereas a floating number representation of the coordinates needs only 2N numbers. When considering the capacity of a distribution center, the binary representation quantizes the solution space and loses smoothness. Finally, the LAP constraints may result in many infeasible solutions, hence reducing the search efficiency.This paper discusses the city-level express distribution center location problem and provides a new perspective for simplifying the LAP. Floating numbers denote the coordinates of distribution centers, and the delivery point assignment for each distribution center is determined by the decoded sequence of delivery points and the capacity of the distribution center. The total distance between the distribution center and delivery points, setup costs, and operational costs is used to evaluate the solution. Representative swarm-based algorithms, including particle swarm optimization (PSO), differential evolution (DE), artificial bee colony (ABC), and a powerful variant of DE, and LSHADE-cnEpSin [7], are compared under two solution encoding schemes.


## 2. Literature Review

The LAP tries to determine the location of distribution centers and the delivery points assigned to each distribution center simultaneously. LAP can take various forms in different scenarios. For example, distribution centers are sites for distributing medical services in public health emergencies, and delivery points are affected in literature [8]. Distribution centers are wastewater treatment plants in the wastewater treatment problem, and delivery points are processing units in literature [9]. Distribution centers are web servers in web services, and delivery points are user centers in literature [10]. For an express distribution center location problem, the operational cost involves the capacity and location of each distribution center, and the capacity is either determined or constrained by the assigned delivery points. Such a problem is called a capacitated location-allocation problem (CLAP) [11].Much effort has been put into this issue. Pham et al. [12] applied a hybrid of the Fuzzy-Delphi-TOPSIS approach to identify the critical criteria for choosing the logistic distribution center. Yang et al. [13] considered the distances between manufactory and distribution centers and between the distribution center and customers and combined tabu search and genetic algorithm to select four distribution centers out of ten candidates. Karaoglan et al. [14] modeled the LRP with simultaneous pickup and delivery, which reflects the practice of beer distribution and empty bottle collection. The problem is then solved using an improved version of the simulated annealing (SA) algorithm.The solution of CLAP may benefit from a geospatial information system (GIS) since the regional division and distance between two points can be more precise. Vafaeinejad et al. [15] developed a vector assignment ordered capacitated median problem (VAOCMP) model to describe the fire station location and allocation problem. In the VAOCMP model, the arrival time of the fire engine to demand points and the capacity of the fire facility are considered. The closeness of the fire facilities ranks the demand, and a facility will be filled up with closer demands. The problem is then solved by tabu search and simulated annealing (SA). Zheng et al. [16] proposed that the underground metro might be used as a complement to the urban logistics system. They utilize GIS to find the shortest path through all the most demanding points. The demanding points are allocated by the Voronoi diagram, which partitions a plane into polygons such that all the points inside a polygon are closest to one of the communities [17].The demand for delivery points may be stochastic. Expert opinions can be introduced to build the distribution model of the customers with a lack of data. Zhou and Liu [18] used fuzzy numbers to model the customer demand, and the expected cost was used as the minimization goal. The expected cost is obtained by fuzzy simulation, and the model is solved by network simplex programming and genetic algorithms. The location of the demands may also be stochastic. Mousavi and Niaki [19] used the normal distribution to model demand location and fuzzy variables to model the amount of demand. Three cost functions were proposed: (1) minimization of the fuzzy expected cost, which is the integration of the credibility of fuzzy events; (2) the β-cost minimization model, which minimizes the upper bound of transportation cost that has credibility greater than β; and (3) the credibility maximization model. The model is then solved by using fuzzy simulation and a genetic algorithm.Noticing the redundancy of express terminal nodes that different express service suppliers establish in the same city, Meng et al. [20] proposed the express terminal nodes optimization integration problem (ETNOIP). The goal of ETNOIP is to establish the minimum number of shared express terminal nodes that could serve a given number of customer clusters. The capacity and scope of an express terminal are included in the cost as well. The model is then solved by SA with neighbor search and shows advantages over immune genetic algorithm (IGA) and CPLEX, an IBM optimization solver.Many swarm-based algorithms and their variations have emerged in the last two decades. Many swarm-based algorithms have been applied to LAP as well. Xu et al. [21] used the wolf-pack algorithm to optimize the total distance. Bao et al. [6] applied particle swarm optimization (PSO) to a logistic vehicle routing problem. A supported vector machine was introduced to distinguish the state of a particle, and the state will determine whether or not a group of particles will be updated. Moonsri et al. [5] discussed the poultry logistics planning problem, which routes vehicles to each established depot. A new mutation formula is developed in the reinitialization phase of differential evolution (DE) to protect the local structure of the solution, and a location search of partial variables is used to enhance the exploitation ability. Guo and Zhang [3] considered the vehicle routing problem and location-allocation problem as a whole and applied a discrete artificial bee colony (ABC) to determine the choice of recycling centers, the vehicles that serve the recycling center, and the route of the vehicles.Various models have been proposed in the past decades to describe different scenarios, and more algorithms have been developed to solve the proposed models. The NP-hard nature of CLAP and the constraints that come with it make algorithms unable to reach their full potential. Taking the express distribution center location-allocation problem as an example, we propose a general encoding method for swarm-based algorithms, which eliminates the capacity constraint in allocating delivery points and improves the efficiency of the compared algorithms.


## 3. Swarm-Based Algorithms for LAP

### 3.1. Particle Swarm Optimization (PSO)

PSO is the most representative swarm-based algorithm. The core mechanism is defined as follows:(1)xi,jt+1=xi,jt+vi,jt+1,vi,jt+1=wtvi,jt+c1randxi,jgbest−xi,jt+c2rxi,jpbest−xi,jt.The position of particles represents the candidate solutions. The symbolxi,jt+1 denotes the j-th coordinate of a particle i in the t+1 generation, which is updated by the velocity vi,jt+1 associated with each particle. Three parts determine the velocity of a particle in the next generation:(1)
Current velocity is weighted by a linearly decreasing factorwt.(2)
The difference between the current position and the global best positionxi,jgbest is scaled by the social learning factor c1 and a uniform distribution random number rand∈0,1.(3)
The difference between the current position and the personal best positionxi,jpbest is scaled by the personal learning factor c2 and another uniform distribution random number rand∈0,1. The last two parts represent social learning and self-learning.


### 3.2. Differential Evolution (DE)

DE is another widely used swarm-based algorithm that uses other solutions in a swarm, instead of the global or personal best, to generate new solutions. Many mutation operators have been proposed in the literature. In this paper, we adopt the “DE/rand/1” strategy as follows:(2)vi,jt+1=xr1,jt+Fxr2,jt−xr3,jt,r1≠r2≠r3≠i,ui,jt+1=vi,jt+1,ifrand•≤CR∨j=randn1,D,xi,jt+1,otherwise.The mutated solutionvi,jt+1 is generated from three solutions that are randomly selected from the swarm and are different from the current solution and each other. The difference between the two is scaled by a factor F and then added to the third solution. Note that only some bits of the selected solution are mutated by probability CR, allowing a subtle modification of the solution. Additionally, randn1,D is a random natural number in the range 1,D, ensuring that at least one bit is mutated. The candidate solution ui,jt+1 is retained if the corresponding cost is better than the current one. Given the differential nature of the mutation operator (2), DE conducts large-scale exploration in the early stages and subtle exploitation in the later stages.


### 3.3. Artificial Bee Colony (ABC)

ABC produces new solutions in three ways that mimic the behaviors of three types of bees: employed, onlooker, and scout bees. The food sources represent the current best solutions. The employed and onlooker bees share the same mutation operator as follows:(3)vi,jt+1=xi,jt+2rand•−1xi,jt−xr,jt,r≠i.The difference between the current solutionxi,jt and a randomly selected solution xr,jt is scaled by a random number in [−1,1], and added to the current solution. This mechanism allows employed and onlooker bees to search for the alternative to the current solution. The behavior difference between employed and onlooker bees is that the employed bees make sure each food source is visited once in a cycle. In contrast, the food source i is visited by an onlooker bee with a probability pi defined as follows:(4)pi=fiti∑n=1nPopfitn,where nPop is the population size and fiti is the fitness of the food source i. The onlooker bees are dispatched based on the roulette selection–the solutions with better cost have a higher chance of being visited. Each food source (solution) has a visiting limit. If there is no better solution found around the current solution after a certain number of visits, the food source is abandoned, and a scout bee is sent to generate a new random solution in the search space.The mechanism of employed bees maintains the diversity of the swarm; onlooker bees exploit the neighbors for better solutions, and the food source visiting limit ensures that the algorithm will not be stuck on some solutions.


### 3.4. Ensemble Sinusoidal Parameter Adaptation Incorporated with LSHADE (LDES)

The parameter settings of DE partially depend on the problem. Therefore, research on the parameter settings of DE [22] and the adaptive parameters of DE [23] is proposed to tackle this problem. In the research stream of adaptive DE, Zhang and Sanderson [24] proposed a self-adaptive DE, JADE, which generalizes the “DE/current-to-best” mutation strategy to “DE/current-to-p-best” and controls the parameters in a self-adaptive manner. Tanabe and Fukunag [25] proposed a Success-History-Based Adaptive DE (SHADE). As an enhancement to JADE, SHADE utilized a history-based parameter adaptation scheme and ranked third in the real-parameter single objective optimization competition, CEC 2013. Tanabe and Fukunaga [26] later proposed the LSHADE algorithm, which extends the SHADE algorithm with the Linear Population Size Reduction (LPSR). The LPSR of LSHADE reduces the number of function evaluations in the exploitation stage of optimization and further enhances the performance. LSHADE wins the CEC 2014 competition.Two years later, Awad et al. [7] proposed the LSHADE-EpSin algorithm, which incorporated the ensemble sinusoidal parameter adaptation and became the joint winner of the competition of CEC 2016. One year later, Awad et al. [27] proposed an improved algorithm, LSHADE-cnEpSin, to tackle the problems with high correlation between variables. LSHADE-cnEpSin became the second winner in the competition of CEC 2017. For brevity, we will denote LSHADE-cnEpSin as LDES in the rest of the paper.


## 3.1. Particle Swarm Optimization (PSO)

PSO is the most representative swarm-based algorithm. The core mechanism is defined as follows:(1)xi,jt+1=xi,jt+vi,jt+1,vi,jt+1=wtvi,jt+c1randxi,jgbest−xi,jt+c2rxi,jpbest−xi,jt.The position of particles represents the candidate solutions. The symbolxi,jt+1 denotes the j-th coordinate of a particle i in the t+1 generation, which is updated by the velocity vi,jt+1 associated with each particle. Three parts determine the velocity of a particle in the next generation:(1)
Current velocity is weighted by a linearly decreasing factorwt.(2)
The difference between the current position and the global best positionxi,jgbest is scaled by the social learning factor c1 and a uniform distribution random number rand∈0,1.(3)
The difference between the current position and the personal best positionxi,jpbest is scaled by the personal learning factor c2 and another uniform distribution random number rand∈0,1. The last two parts represent social learning and self-learning.


## 3.2. Differential Evolution (DE)

DE is another widely used swarm-based algorithm that uses other solutions in a swarm, instead of the global or personal best, to generate new solutions. Many mutation operators have been proposed in the literature. In this paper, we adopt the “DE/rand/1” strategy as follows:(2)vi,jt+1=xr1,jt+Fxr2,jt−xr3,jt,r1≠r2≠r3≠i,ui,jt+1=vi,jt+1,ifrand•≤CR∨j=randn1,D,xi,jt+1,otherwise.The mutated solutionvi,jt+1 is generated from three solutions that are randomly selected from the swarm and are different from the current solution and each other. The difference between the two is scaled by a factor F and then added to the third solution. Note that only some bits of the selected solution are mutated by probability CR, allowing a subtle modification of the solution. Additionally, randn1,D is a random natural number in the range 1,D, ensuring that at least one bit is mutated. The candidate solution ui,jt+1 is retained if the corresponding cost is better than the current one. Given the differential nature of the mutation operator (2), DE conducts large-scale exploration in the early stages and subtle exploitation in the later stages.


## 3.3. Artificial Bee Colony (ABC)

ABC produces new solutions in three ways that mimic the behaviors of three types of bees: employed, onlooker, and scout bees. The food sources represent the current best solutions. The employed and onlooker bees share the same mutation operator as follows:(3)vi,jt+1=xi,jt+2rand•−1xi,jt−xr,jt,r≠i.The difference between the current solutionxi,jt and a randomly selected solution xr,jt is scaled by a random number in [−1,1], and added to the current solution. This mechanism allows employed and onlooker bees to search for the alternative to the current solution. The behavior difference between employed and onlooker bees is that the employed bees make sure each food source is visited once in a cycle. In contrast, the food source i is visited by an onlooker bee with a probability pi defined as follows:(4)pi=fiti∑n=1nPopfitn,where nPop is the population size and fiti is the fitness of the food source i. The onlooker bees are dispatched based on the roulette selection–the solutions with better cost have a higher chance of being visited. Each food source (solution) has a visiting limit. If there is no better solution found around the current solution after a certain number of visits, the food source is abandoned, and a scout bee is sent to generate a new random solution in the search space.The mechanism of employed bees maintains the diversity of the swarm; onlooker bees exploit the neighbors for better solutions, and the food source visiting limit ensures that the algorithm will not be stuck on some solutions.


## 3.4. Ensemble Sinusoidal Parameter Adaptation Incorporated with LSHADE (LDES)

The parameter settings of DE partially depend on the problem. Therefore, research on the parameter settings of DE [22] and the adaptive parameters of DE [23] is proposed to tackle this problem. In the research stream of adaptive DE, Zhang and Sanderson [24] proposed a self-adaptive DE, JADE, which generalizes the “DE/current-to-best” mutation strategy to “DE/current-to-p-best” and controls the parameters in a self-adaptive manner. Tanabe and Fukunag [25] proposed a Success-History-Based Adaptive DE (SHADE). As an enhancement to JADE, SHADE utilized a history-based parameter adaptation scheme and ranked third in the real-parameter single objective optimization competition, CEC 2013. Tanabe and Fukunaga [26] later proposed the LSHADE algorithm, which extends the SHADE algorithm with the Linear Population Size Reduction (LPSR). The LPSR of LSHADE reduces the number of function evaluations in the exploitation stage of optimization and further enhances the performance. LSHADE wins the CEC 2014 competition.Two years later, Awad et al. [7] proposed the LSHADE-EpSin algorithm, which incorporated the ensemble sinusoidal parameter adaptation and became the joint winner of the competition of CEC 2016. One year later, Awad et al. [27] proposed an improved algorithm, LSHADE-cnEpSin, to tackle the problems with high correlation between variables. LSHADE-cnEpSin became the second winner in the competition of CEC 2017. For brevity, we will denote LSHADE-cnEpSin as LDES in the rest of the paper.


## 4. Problem Formulation and Solution Representation

### 4.1. Capacitated Location-Allocation Problem

A complete planning scheme of distribution centers includes the number of distribution centers, the location and capacity of each distribution center, and the delivery points that are serviced by each distribution center.The location of distribution centers affects the delivery mode and distance, hence the efficiency and service quality of the distribution centers. The factors that may affect the location selection of distribution centers may be classified into two classes: natural factors and social factors. Natural factors include the natural conditions, such as mountains and rivers, the conditions of the land, and the distribution of roads [11]. Social factors may include infrastructure, client demand distribution, suppliers, and policies.The capacity of distribution centers determines whether the demand of the assigned delivery point can be served. The assignment of delivery points determines the transportation cost and the operational cost.This paper focuses on the transportation, setup, and operational cost to simplify the model and highlight the main factors. To build up the objective functions for the cost, let us define the symbols as shown in Table1.Table 1
Symbols and description.
DescriptionSymbolPropertyMaximum number of distribution centersNmaxParameterNumber of distribution centersNDecision variableNumber of delivery pointsMParameterHorizontal coordinate of distribution centeripitx,i∈1,…,NDecision variableVertical coordinate of distribution centeripity,i∈1,…,NDecision variableMaximum horizontal coordinate of distribution centerpmaxtxHorizontal coordinate of the delivery pointjpjdx,j=1,…,MParameterVertical coordinate of the delivery pointjpjdy,j=1,…,MParameterDistance between thei-th distribution center and j-th delivery pointdijParameterCapacity of distribution centerici,i∈1,…,NDecision variableThe demand of delivery pointjrj,j∈j,…,MParameterTotal demand of all delivery pointsRParameterSet of all delivery pointsΩ=1,…,MParameterSet of delivery points served by distribution centeriΩiDecision variableAverage operational cost is determined by the position of the distribution centerpitx,pityTpitx,pityParameter


#### 4.1.1. Transportation Cost

The transportation costs may be affected by capital, fuel, lubricant, and operational costs. Sahin et al. [28] showed that the total cost of a unit of cargo in road transportation with trucks consists of 14% investment cost, 60% fuel cost, 17% operational cost and maintenance cost of the vehicle, and 9% external cost, which are positively related to the route length. Assuming the vehicles are fully loaded and the cost has a linear relationship with the route length, the total transportation cost Ct can be formulated in the following equation:(5)Ct=∑iN∑j∈Ωidij,where dij is the city block distance as follows:(6)dij=pitx−pjdx+pity−pjdy.


#### 4.1.2. Setup Cost

The setup cost may vary depending on how the distribution center is set, such as renting a warehouse or building a new depot. Assuming that the average setup cost for any possible location is known, the total setup cost is simply as follows:(7)Cs=∑iNTpitx,pity,where the operational cost for a given point pitx,pity can be determined in advance through investigation.


#### 4.1.3. Operational Cost

The operational cost depends on how many demands a distribution center needs to meet, which is usually described by a cubic function of demand [29]. Therefore, a distribution center’s operational cost per unit demand is a quadratic function of demand. The total operational cost is formulated as follows:(8)Co=∑iNa1Qi3+a2Qi2+a3Qi,Qi=∑j∈Ωirj,where akk=1,2,3 are polynomial coefficients. The total demand Qi that is assigned to the distribution center i is determined by the decision variable Ωi. The cost per unit demand is then formulated as(9)Cpud=a1Qi2+a2Qi+a3.The optimal capacity for a distribution center is the solution to the following equation:(10)dCpuddQi=2a1Qi+a2=0.To summarize, the total cost for an express CLAP is(11)C=Ctwt+Csws+Cowo,where wt, ws, and wo are the weight coefficients for transportation, setup, and operational cost, respectively.


#### 4.1.4. Constraints

The boundary constraints for the decision variables are as follows:(12)0≤N≤Nmax,(13)0≤pitx≤pmaxtx,0≤pity≤pmaxty,i∈1,…,N.The capacity of the distribution center must satisfy the total demand of all delivery points serviced by it:(14)Qi≤ci≤R,R=∑j=1Mrj,where R is the total demand as described in Table 1. Each delivery point is serviced by one distribution center:(15)Ω=∑i=1NΩi,Ωi∩Ωj=∅for anyi≠j.


### 4.2. Encoding Scheme and Evaluation Criteria

The selected algorithms work on a set of floating number vectorsxi (known as the population X=xi,…,xnPopT, where nPop is the population size). Therefore, the solutions of CLAP need to be encoded into floating number vectors before the algorithms can be applied. When a new vector is found by an algorithm, it must be interpreted (decoded) into the actual location and allocation plans before it can be evaluated. This section discusses the encoding/decoding schemes and the evaluation criteria of the plan.


#### 4.2.1. Traditional Encoding Scheme

A complete location planning scheme of distribution centers can be represented by the decision variables described in Table1. The location of a distribution center requires two numbers to denote the horizontal and vertical coordinates. Another quantity is required to denote the capacity. Furthermore, a number denoting the belonging of a delivery point is also required. Given that the length of the solution representation in the selected algorithms is fixed, the traditional encoding/decoding scheme can be as shown in Figure 2.Figure 2
Traditional encoding/decoding scheme TES.For a traditional encoding/decoding scheme, the length of a solution string is 3N+M, where gj∈Z+,j∈1,…,N is a positive integer and denotes that the j-th delivery point belongs to the gj-th distribution center. The decision variables are obtained as follows:(16)pitx=x3i−2,pity=x3i−1,ci=x3i,i=1,…,N,gj=x3N+j,j=1,…,M,Ωi=j=1,…,M|gj=i,where xi∈ℝ+ are floating numbers. x3i−2 and x3i−1 (i=1,…,N) have the same range as pitx and pity, respectively. The range of x3i (i=1,⋯,N) is 0,R because the lower bound of the capacity cannot be determined in this encoding scheme. x3N+j∈0,N (j=1,⋯,M) and ⌈⋅⌉ is the rounded-up function.The traditional encoding scheme is straightforward, but the drawbacks are clear: (1) the number of distribution centers must be determined in advance, and (2) solution strings generated in the search process may violate the constraints. For the boundary constraints defined in Equations (12) and (13), the abovementioned algorithms will truncate the exceeded solutions. However, for the constraints in Equations (12) and (13), an infeasible solution means that the decoded plan cannot be executed.For example, the delivery points assigned to a distribution center may have greater total demand than the capacity of the distribution center, or no delivery points may be assigned to a distribution center. Hence, a punishment term is defined as follows to suppress the infeasible solutions:(17)Cp=∑iNmax∑j∈Ωirj−ci,0.The modified cost function can be as follows:(18)C=Ctwt+Csws+Cowo+Cpwp,where wp is the weight of the punishment term. If no delivery point is assigned to a distribution center, the wasted resources are naturally a punishment for the cost. Such solutions will not compete with the solutions that take advantage of the available capacity.


#### 4.2.2. Constraint-Solved Encoding Scheme

The abovementioned encoding scheme and cost function allow the existence of infeasible solutions, which decreases the search efficiency since there are invalid calculations for the infeasible solutions. This paper presents an improved encoding scheme that introduces random proportion and random key (RPK) as shown in Figure3, which transfers the constraint problem into an unconstraint problem.Figure 3
Unconstraint encoding/decoding scheme RPK.As shown in Figure3, a floating number vector x=x1,…,x3Nmax+M+1 is used as the solution string, where xi∈0,1. The number x1 will be mapped into the number of distribution centers and x2,…,x2N+1 will be mapped into the position of each distribution centers by(19)N=x1Nmax,(20)pitx=x2ipmaxtx,pity=x2i+1pmaxty,i=1,…N.Note that ifN<Nmax, the numbers x2N+2,…,x2Nmax+1 will be omitted.The numbersx2Nmax+2,…,x3Nmax+M+1 can be decoded into the capacity of each distribution center and the assignment of delivery points through random proportion and random key mapping.The random key mapping determines a sequence of delivery points as follows. The partial vectorx3Nmax+2,…,x3Nmax+M+1 is sorted in either ascending or descending order to obtain the sorting index h1,…,hM. For example, h1 denotes the order of x3N+2 in the sorted vector and hM denotes the order of x3N+M+1 in the sorted vector. The index h1,…,hM represents the sequence of the delivery points.The random proportion mapping uses a partial vectorx2Nmax+2,…,x2Nmax+N+1 to determine the lower bound capacity c˜i of a distribution center:(21)c˜i=x2N+1+i∑j=2N+1+i3N+1xjR,i=1,…,N−1.Note that the numbers [x2Nmax+N+2,…,x3Nmax+1] are omitted as well if N<Nmax.The assignment of delivery points for the distribution centeri is determined as follows:(22)Ωi=hai,…,hbi,c˜i≤∑j∈Ωirj,i=1,…,N−1,(23)1=a1<b1<a2<b2<…<aN<bN=M,where hai,…,hbi is a continuous partial sequence in h1,…,hM, which makes the summation of demands from the set of delivery points Ωi just greater than the lower bound c˜i.The actual capacity of the distribution centeri is determined by the summation of demand from the delivery point assigned to it:(24)ci=∑j∈Ωirj,i=1,…,N.The idea of RPK is to determine the number of distribution centers dynamically and make the capacity just enough for the assigned delivery points. The logical procedure of obtaining a feasible capacitated location-allocation plan from anyx∈0,13N+M+1 is as follows:Step 1: obtain the number of distribution centersN by Equation (19)Step 2: obtain the position ofN distribution centers by Equation (20)Step 3: sortx3Nmax+2,…,x3Nmax+M+1 and get the index h1,…,hMStep 4:a1←1Step 5: fori in 1,…,N−1 doCalculate the lower bound capacityc˜i by (21)Starting fromai+1, find the first bi that satisfies Equation (22)The set of delivery points assigned to the distribution centeri is Ωi=hai,…,hbiai+1←bi+1Obtain the actual capacity of the distribution centeri by (24)Step 6:ΩN=hb3+1,…,hM, cN=∑j∈ΩNrjA decoding example is as follows. Assume thatNmax=2, M=5, pmaxtx=100, pmaxty=120, and R=500, and demands for each delivery point are [100, 80, 110, 150, 60]. A vector x with the length 3N+M+1=12 is [0.66, 0.1, 0.35, 0.5, 0.6, 0.7, 0.9, 0.4, 0.95, 0.25, 0.55, 0.6]. Then, N=0.66×2=2, p1tx=0.1×100=10, p1ty=0.35×120=42, p2tx=0.5×100=50, p2ty=0.6×120=72, c˜1=0.7/0.7+0.9×500=218.75, and c˜2=0.9/0.7+0.9×500=281.25. The sorting index of the ascending order of [0.4, 0.95, 0.25, 0.55, 0.6] is [1–5]. The minimum set Ω1 that satisfies equation (22) is 2,5,1; therefore, c1=r2+r5+r1=240, Ω2=3,4, and c2=r3+r4=260.For an arbitraryx∈0,1, the RPK encoding scheme always produces a unique and feasible plan. The total capacity of the distribution centers equals the total demand, which maximizes resource utilization. Furthermore, the RPK encoding scheme allows algorithms to operate on a uniform vector x∈0,1, which facilitates the application of algorithms.


## 4.1. Capacitated Location-Allocation Problem

A complete planning scheme of distribution centers includes the number of distribution centers, the location and capacity of each distribution center, and the delivery points that are serviced by each distribution center.The location of distribution centers affects the delivery mode and distance, hence the efficiency and service quality of the distribution centers. The factors that may affect the location selection of distribution centers may be classified into two classes: natural factors and social factors. Natural factors include the natural conditions, such as mountains and rivers, the conditions of the land, and the distribution of roads [11]. Social factors may include infrastructure, client demand distribution, suppliers, and policies.The capacity of distribution centers determines whether the demand of the assigned delivery point can be served. The assignment of delivery points determines the transportation cost and the operational cost.This paper focuses on the transportation, setup, and operational cost to simplify the model and highlight the main factors. To build up the objective functions for the cost, let us define the symbols as shown in Table1.Table 1
Symbols and description.
DescriptionSymbolPropertyMaximum number of distribution centersNmaxParameterNumber of distribution centersNDecision variableNumber of delivery pointsMParameterHorizontal coordinate of distribution centeripitx,i∈1,…,NDecision variableVertical coordinate of distribution centeripity,i∈1,…,NDecision variableMaximum horizontal coordinate of distribution centerpmaxtxHorizontal coordinate of the delivery pointjpjdx,j=1,…,MParameterVertical coordinate of the delivery pointjpjdy,j=1,…,MParameterDistance between thei-th distribution center and j-th delivery pointdijParameterCapacity of distribution centerici,i∈1,…,NDecision variableThe demand of delivery pointjrj,j∈j,…,MParameterTotal demand of all delivery pointsRParameterSet of all delivery pointsΩ=1,…,MParameterSet of delivery points served by distribution centeriΩiDecision variableAverage operational cost is determined by the position of the distribution centerpitx,pityTpitx,pityParameter


### 4.1.1. Transportation Cost

The transportation costs may be affected by capital, fuel, lubricant, and operational costs. Sahin et al. [28] showed that the total cost of a unit of cargo in road transportation with trucks consists of 14% investment cost, 60% fuel cost, 17% operational cost and maintenance cost of the vehicle, and 9% external cost, which are positively related to the route length. Assuming the vehicles are fully loaded and the cost has a linear relationship with the route length, the total transportation cost Ct can be formulated in the following equation:(5)Ct=∑iN∑j∈Ωidij,where dij is the city block distance as follows:(6)dij=pitx−pjdx+pity−pjdy.


### 4.1.2. Setup Cost

The setup cost may vary depending on how the distribution center is set, such as renting a warehouse or building a new depot. Assuming that the average setup cost for any possible location is known, the total setup cost is simply as follows:(7)Cs=∑iNTpitx,pity,where the operational cost for a given point pitx,pity can be determined in advance through investigation.


### 4.1.3. Operational Cost

The operational cost depends on how many demands a distribution center needs to meet, which is usually described by a cubic function of demand [29]. Therefore, a distribution center’s operational cost per unit demand is a quadratic function of demand. The total operational cost is formulated as follows:(8)Co=∑iNa1Qi3+a2Qi2+a3Qi,Qi=∑j∈Ωirj,where akk=1,2,3 are polynomial coefficients. The total demand Qi that is assigned to the distribution center i is determined by the decision variable Ωi. The cost per unit demand is then formulated as(9)Cpud=a1Qi2+a2Qi+a3.The optimal capacity for a distribution center is the solution to the following equation:(10)dCpuddQi=2a1Qi+a2=0.To summarize, the total cost for an express CLAP is(11)C=Ctwt+Csws+Cowo,where wt, ws, and wo are the weight coefficients for transportation, setup, and operational cost, respectively.


### 4.1.4. Constraints

The boundary constraints for the decision variables are as follows:(12)0≤N≤Nmax,(13)0≤pitx≤pmaxtx,0≤pity≤pmaxty,i∈1,…,N.The capacity of the distribution center must satisfy the total demand of all delivery points serviced by it:(14)Qi≤ci≤R,R=∑j=1Mrj,where R is the total demand as described in Table 1. Each delivery point is serviced by one distribution center:(15)Ω=∑i=1NΩi,Ωi∩Ωj=∅for anyi≠j.


## 4.1.1. Transportation Cost

The transportation costs may be affected by capital, fuel, lubricant, and operational costs. Sahin et al. [28] showed that the total cost of a unit of cargo in road transportation with trucks consists of 14% investment cost, 60% fuel cost, 17% operational cost and maintenance cost of the vehicle, and 9% external cost, which are positively related to the route length. Assuming the vehicles are fully loaded and the cost has a linear relationship with the route length, the total transportation cost Ct can be formulated in the following equation:(5)Ct=∑iN∑j∈Ωidij,where dij is the city block distance as follows:(6)dij=pitx−pjdx+pity−pjdy.


## 4.1.2. Setup Cost

The setup cost may vary depending on how the distribution center is set, such as renting a warehouse or building a new depot. Assuming that the average setup cost for any possible location is known, the total setup cost is simply as follows:(7)Cs=∑iNTpitx,pity,where the operational cost for a given point pitx,pity can be determined in advance through investigation.


## 4.1.3. Operational Cost

The operational cost depends on how many demands a distribution center needs to meet, which is usually described by a cubic function of demand [29]. Therefore, a distribution center’s operational cost per unit demand is a quadratic function of demand. The total operational cost is formulated as follows:(8)Co=∑iNa1Qi3+a2Qi2+a3Qi,Qi=∑j∈Ωirj,where akk=1,2,3 are polynomial coefficients. The total demand Qi that is assigned to the distribution center i is determined by the decision variable Ωi. The cost per unit demand is then formulated as(9)Cpud=a1Qi2+a2Qi+a3.The optimal capacity for a distribution center is the solution to the following equation:(10)dCpuddQi=2a1Qi+a2=0.To summarize, the total cost for an express CLAP is(11)C=Ctwt+Csws+Cowo,where wt, ws, and wo are the weight coefficients for transportation, setup, and operational cost, respectively.


## 4.1.4. Constraints

The boundary constraints for the decision variables are as follows:(12)0≤N≤Nmax,(13)0≤pitx≤pmaxtx,0≤pity≤pmaxty,i∈1,…,N.The capacity of the distribution center must satisfy the total demand of all delivery points serviced by it:(14)Qi≤ci≤R,R=∑j=1Mrj,where R is the total demand as described in Table 1. Each delivery point is serviced by one distribution center:(15)Ω=∑i=1NΩi,Ωi∩Ωj=∅for anyi≠j.


## 4.2. Encoding Scheme and Evaluation Criteria

The selected algorithms work on a set of floating number vectorsxi (known as the population X=xi,…,xnPopT, where nPop is the population size). Therefore, the solutions of CLAP need to be encoded into floating number vectors before the algorithms can be applied. When a new vector is found by an algorithm, it must be interpreted (decoded) into the actual location and allocation plans before it can be evaluated. This section discusses the encoding/decoding schemes and the evaluation criteria of the plan.


### 4.2.1. Traditional Encoding Scheme

A complete location planning scheme of distribution centers can be represented by the decision variables described in Table1. The location of a distribution center requires two numbers to denote the horizontal and vertical coordinates. Another quantity is required to denote the capacity. Furthermore, a number denoting the belonging of a delivery point is also required. Given that the length of the solution representation in the selected algorithms is fixed, the traditional encoding/decoding scheme can be as shown in Figure 2.Figure 2
Traditional encoding/decoding scheme TES.For a traditional encoding/decoding scheme, the length of a solution string is 3N+M, where gj∈Z+,j∈1,…,N is a positive integer and denotes that the j-th delivery point belongs to the gj-th distribution center. The decision variables are obtained as follows:(16)pitx=x3i−2,pity=x3i−1,ci=x3i,i=1,…,N,gj=x3N+j,j=1,…,M,Ωi=j=1,…,M|gj=i,where xi∈ℝ+ are floating numbers. x3i−2 and x3i−1 (i=1,…,N) have the same range as pitx and pity, respectively. The range of x3i (i=1,⋯,N) is 0,R because the lower bound of the capacity cannot be determined in this encoding scheme. x3N+j∈0,N (j=1,⋯,M) and ⌈⋅⌉ is the rounded-up function.The traditional encoding scheme is straightforward, but the drawbacks are clear: (1) the number of distribution centers must be determined in advance, and (2) solution strings generated in the search process may violate the constraints. For the boundary constraints defined in Equations (12) and (13), the abovementioned algorithms will truncate the exceeded solutions. However, for the constraints in Equations (12) and (13), an infeasible solution means that the decoded plan cannot be executed.For example, the delivery points assigned to a distribution center may have greater total demand than the capacity of the distribution center, or no delivery points may be assigned to a distribution center. Hence, a punishment term is defined as follows to suppress the infeasible solutions:(17)Cp=∑iNmax∑j∈Ωirj−ci,0.The modified cost function can be as follows:(18)C=Ctwt+Csws+Cowo+Cpwp,where wp is the weight of the punishment term. If no delivery point is assigned to a distribution center, the wasted resources are naturally a punishment for the cost. Such solutions will not compete with the solutions that take advantage of the available capacity.


### 4.2.2. Constraint-Solved Encoding Scheme

The abovementioned encoding scheme and cost function allow the existence of infeasible solutions, which decreases the search efficiency since there are invalid calculations for the infeasible solutions. This paper presents an improved encoding scheme that introduces random proportion and random key (RPK) as shown in Figure3, which transfers the constraint problem into an unconstraint problem.Figure 3
Unconstraint encoding/decoding scheme RPK.As shown in Figure3, a floating number vector x=x1,…,x3Nmax+M+1 is used as the solution string, where xi∈0,1. The number x1 will be mapped into the number of distribution centers and x2,…,x2N+1 will be mapped into the position of each distribution centers by(19)N=x1Nmax,(20)pitx=x2ipmaxtx,pity=x2i+1pmaxty,i=1,…N.Note that ifN<Nmax, the numbers x2N+2,…,x2Nmax+1 will be omitted.The numbersx2Nmax+2,…,x3Nmax+M+1 can be decoded into the capacity of each distribution center and the assignment of delivery points through random proportion and random key mapping.The random key mapping determines a sequence of delivery points as follows. The partial vectorx3Nmax+2,…,x3Nmax+M+1 is sorted in either ascending or descending order to obtain the sorting index h1,…,hM. For example, h1 denotes the order of x3N+2 in the sorted vector and hM denotes the order of x3N+M+1 in the sorted vector. The index h1,…,hM represents the sequence of the delivery points.The random proportion mapping uses a partial vectorx2Nmax+2,…,x2Nmax+N+1 to determine the lower bound capacity c˜i of a distribution center:(21)c˜i=x2N+1+i∑j=2N+1+i3N+1xjR,i=1,…,N−1.Note that the numbers [x2Nmax+N+2,…,x3Nmax+1] are omitted as well if N<Nmax.The assignment of delivery points for the distribution centeri is determined as follows:(22)Ωi=hai,…,hbi,c˜i≤∑j∈Ωirj,i=1,…,N−1,(23)1=a1<b1<a2<b2<…<aN<bN=M,where hai,…,hbi is a continuous partial sequence in h1,…,hM, which makes the summation of demands from the set of delivery points Ωi just greater than the lower bound c˜i.The actual capacity of the distribution centeri is determined by the summation of demand from the delivery point assigned to it:(24)ci=∑j∈Ωirj,i=1,…,N.The idea of RPK is to determine the number of distribution centers dynamically and make the capacity just enough for the assigned delivery points. The logical procedure of obtaining a feasible capacitated location-allocation plan from anyx∈0,13N+M+1 is as follows:Step 1: obtain the number of distribution centersN by Equation (19)Step 2: obtain the position ofN distribution centers by Equation (20)Step 3: sortx3Nmax+2,…,x3Nmax+M+1 and get the index h1,…,hMStep 4:a1←1Step 5: fori in 1,…,N−1 doCalculate the lower bound capacityc˜i by (21)Starting fromai+1, find the first bi that satisfies Equation (22)The set of delivery points assigned to the distribution centeri is Ωi=hai,…,hbiai+1←bi+1Obtain the actual capacity of the distribution centeri by (24)Step 6:ΩN=hb3+1,…,hM, cN=∑j∈ΩNrjA decoding example is as follows. Assume thatNmax=2, M=5, pmaxtx=100, pmaxty=120, and R=500, and demands for each delivery point are [100, 80, 110, 150, 60]. A vector x with the length 3N+M+1=12 is [0.66, 0.1, 0.35, 0.5, 0.6, 0.7, 0.9, 0.4, 0.95, 0.25, 0.55, 0.6]. Then, N=0.66×2=2, p1tx=0.1×100=10, p1ty=0.35×120=42, p2tx=0.5×100=50, p2ty=0.6×120=72, c˜1=0.7/0.7+0.9×500=218.75, and c˜2=0.9/0.7+0.9×500=281.25. The sorting index of the ascending order of [0.4, 0.95, 0.25, 0.55, 0.6] is [1–5]. The minimum set Ω1 that satisfies equation (22) is 2,5,1; therefore, c1=r2+r5+r1=240, Ω2=3,4, and c2=r3+r4=260.For an arbitraryx∈0,1, the RPK encoding scheme always produces a unique and feasible plan. The total capacity of the distribution centers equals the total demand, which maximizes resource utilization. Furthermore, the RPK encoding scheme allows algorithms to operate on a uniform vector x∈0,1, which facilitates the application of algorithms.


## 4.2.1. Traditional Encoding Scheme

A complete location planning scheme of distribution centers can be represented by the decision variables described in Table1. The location of a distribution center requires two numbers to denote the horizontal and vertical coordinates. Another quantity is required to denote the capacity. Furthermore, a number denoting the belonging of a delivery point is also required. Given that the length of the solution representation in the selected algorithms is fixed, the traditional encoding/decoding scheme can be as shown in Figure 2.Figure 2
Traditional encoding/decoding scheme TES.For a traditional encoding/decoding scheme, the length of a solution string is 3N+M, where gj∈Z+,j∈1,…,N is a positive integer and denotes that the j-th delivery point belongs to the gj-th distribution center. The decision variables are obtained as follows:(16)pitx=x3i−2,pity=x3i−1,ci=x3i,i=1,…,N,gj=x3N+j,j=1,…,M,Ωi=j=1,…,M|gj=i,where xi∈ℝ+ are floating numbers. x3i−2 and x3i−1 (i=1,…,N) have the same range as pitx and pity, respectively. The range of x3i (i=1,⋯,N) is 0,R because the lower bound of the capacity cannot be determined in this encoding scheme. x3N+j∈0,N (j=1,⋯,M) and ⌈⋅⌉ is the rounded-up function.The traditional encoding scheme is straightforward, but the drawbacks are clear: (1) the number of distribution centers must be determined in advance, and (2) solution strings generated in the search process may violate the constraints. For the boundary constraints defined in Equations (12) and (13), the abovementioned algorithms will truncate the exceeded solutions. However, for the constraints in Equations (12) and (13), an infeasible solution means that the decoded plan cannot be executed.For example, the delivery points assigned to a distribution center may have greater total demand than the capacity of the distribution center, or no delivery points may be assigned to a distribution center. Hence, a punishment term is defined as follows to suppress the infeasible solutions:(17)Cp=∑iNmax∑j∈Ωirj−ci,0.The modified cost function can be as follows:(18)C=Ctwt+Csws+Cowo+Cpwp,where wp is the weight of the punishment term. If no delivery point is assigned to a distribution center, the wasted resources are naturally a punishment for the cost. Such solutions will not compete with the solutions that take advantage of the available capacity.


## 4.2.2. Constraint-Solved Encoding Scheme

The abovementioned encoding scheme and cost function allow the existence of infeasible solutions, which decreases the search efficiency since there are invalid calculations for the infeasible solutions. This paper presents an improved encoding scheme that introduces random proportion and random key (RPK) as shown in Figure3, which transfers the constraint problem into an unconstraint problem.Figure 3
Unconstraint encoding/decoding scheme RPK.As shown in Figure3, a floating number vector x=x1,…,x3Nmax+M+1 is used as the solution string, where xi∈0,1. The number x1 will be mapped into the number of distribution centers and x2,…,x2N+1 will be mapped into the position of each distribution centers by(19)N=x1Nmax,(20)pitx=x2ipmaxtx,pity=x2i+1pmaxty,i=1,…N.Note that ifN<Nmax, the numbers x2N+2,…,x2Nmax+1 will be omitted.The numbersx2Nmax+2,…,x3Nmax+M+1 can be decoded into the capacity of each distribution center and the assignment of delivery points through random proportion and random key mapping.The random key mapping determines a sequence of delivery points as follows. The partial vectorx3Nmax+2,…,x3Nmax+M+1 is sorted in either ascending or descending order to obtain the sorting index h1,…,hM. For example, h1 denotes the order of x3N+2 in the sorted vector and hM denotes the order of x3N+M+1 in the sorted vector. The index h1,…,hM represents the sequence of the delivery points.The random proportion mapping uses a partial vectorx2Nmax+2,…,x2Nmax+N+1 to determine the lower bound capacity c˜i of a distribution center:(21)c˜i=x2N+1+i∑j=2N+1+i3N+1xjR,i=1,…,N−1.Note that the numbers [x2Nmax+N+2,…,x3Nmax+1] are omitted as well if N<Nmax.The assignment of delivery points for the distribution centeri is determined as follows:(22)Ωi=hai,…,hbi,c˜i≤∑j∈Ωirj,i=1,…,N−1,(23)1=a1<b1<a2<b2<…<aN<bN=M,where hai,…,hbi is a continuous partial sequence in h1,…,hM, which makes the summation of demands from the set of delivery points Ωi just greater than the lower bound c˜i.The actual capacity of the distribution centeri is determined by the summation of demand from the delivery point assigned to it:(24)ci=∑j∈Ωirj,i=1,…,N.The idea of RPK is to determine the number of distribution centers dynamically and make the capacity just enough for the assigned delivery points. The logical procedure of obtaining a feasible capacitated location-allocation plan from anyx∈0,13N+M+1 is as follows:Step 1: obtain the number of distribution centersN by Equation (19)Step 2: obtain the position ofN distribution centers by Equation (20)Step 3: sortx3Nmax+2,…,x3Nmax+M+1 and get the index h1,…,hMStep 4:a1←1Step 5: fori in 1,…,N−1 doCalculate the lower bound capacityc˜i by (21)Starting fromai+1, find the first bi that satisfies Equation (22)The set of delivery points assigned to the distribution centeri is Ωi=hai,…,hbiai+1←bi+1Obtain the actual capacity of the distribution centeri by (24)Step 6:ΩN=hb3+1,…,hM, cN=∑j∈ΩNrjA decoding example is as follows. Assume thatNmax=2, M=5, pmaxtx=100, pmaxty=120, and R=500, and demands for each delivery point are [100, 80, 110, 150, 60]. A vector x with the length 3N+M+1=12 is [0.66, 0.1, 0.35, 0.5, 0.6, 0.7, 0.9, 0.4, 0.95, 0.25, 0.55, 0.6]. Then, N=0.66×2=2, p1tx=0.1×100=10, p1ty=0.35×120=42, p2tx=0.5×100=50, p2ty=0.6×120=72, c˜1=0.7/0.7+0.9×500=218.75, and c˜2=0.9/0.7+0.9×500=281.25. The sorting index of the ascending order of [0.4, 0.95, 0.25, 0.55, 0.6] is [1–5]. The minimum set Ω1 that satisfies equation (22) is 2,5,1; therefore, c1=r2+r5+r1=240, Ω2=3,4, and c2=r3+r4=260.For an arbitraryx∈0,1, the RPK encoding scheme always produces a unique and feasible plan. The total capacity of the distribution centers equals the total demand, which maximizes resource utilization. Furthermore, the RPK encoding scheme allows algorithms to operate on a uniform vector x∈0,1, which facilitates the application of algorithms.


## 5. Evaluation Experiments

### 5.1. Experiment Settings

The evaluation experiments were conducted on a 10 km by 10 km square region of Zhenjiang, China [30]. The map of this region is divided into 10 × 10 grids, and the setup cost for each lattice is obtained via investigation. The map, grid, and setup cost matrix are shown in Figure 4.Figure 4
The regional grid map of Zhenjiang, China, with an operational cost for each lattice.The setup costs are scaled into five levels. Level 5 represents the most expensive setup cost. The central area (slightly above the middle) has the highest cost, and the suburbs have the lowest cost. A mountain is located slightly below the middle, and some waters are in the north, where a distribution center cannot be set up. We set the cost much higher than the maximum level cost (20 in this case) to prevent generating a distribution center located in these areas. While a finer grid may bring a plan closer to reality, a 10× 10 grid is sufficient to show the algorithm’s mechanism and maintain the map’s readability.The TES and RPK encoding schemes are applied to four algorithms: PSO, DE, ABC, and LDES. Since the compared algorithms use different population sizes, we use the number of cost function evaluations (FEs) instead of the number of generations to measure the performance. The algorithms will stop when the maximum FEs are reached. RPK works on a unified search space and transforms a solutionx∈0,1D into a location and allocation plan, where D is the dimension of the search space, i.e., the number of variables. The algorithm parameters are shown in Table 2.Table 2
Parameter settings for PSO, DE, ABC, and LDES algorithms.
Parameter descriptionValueGeneral parametersThe maximum number of cost function evaluationsFEmax200,000Search space0,1DTransportation cost weightwt1Setup cost weightws1Operational cost weightwt0.1Punishment weightwp30Polynomial coefficientsa for operational cost0.0025,−0.1,2Coordinate boundspmaxtx,pmaxty0,1PSO parameters (Bao et al. [6])Social learning factorc12Personal learning factorc22Weight range [wmin,wmax][0.4,0.9]Population size nPop30Velocity range [vmin,vmax][−0.2,0.2]DE parameters (Moonsri et al. [5])Population size nPop37Crossover probability0.9455Scaling factor0.6497ABC parameters (Guo and Zhang [3])Population size50Number of onlooker bees25Number of employed bees25Food source visiting limit500LDES parameters (Awad et al. [27])Initial population size360Minimum population size4Covariance matrix learning probability pc0.4Selection probability ps0.5Selection rate of the best solutions p_best_rate0.11Archive rate arc_rate1.4Memory size4The initial number of neighbors SEL180Scaling factorsAdaptive adjust


### 5.2. Comparison of TES and RPK Encoding Schemes

The comparison is conducted on the map in Figure4. There are 20 delivery points on the map, each with different demands. The maximum number of delivery centers is set to 5. The location of delivery points and the associated demands are shown in Figure 5.Figure 5
Location and demands of delivery points. The circles show the location, and the circle’s diameter shows the value of demand. The larger the diameter, the greater the demand.Each algorithm runs 30 times, and the optimum costs found by each algorithm are averaged over 30 runs. The results are shown in Table3.Table 3
Average cost over 30 runs and standard deviate for PSO, DE, ABC, and LDES using RPK and TES encoding scheme.
Encoding schemeAverage cost (standard deviation)PSODEABCLDESRPK17.23 (0.74)15.95 (0.05)15.54 (0.4)15.96 (0.09)TES21.71 (1.39)19.35 (0.61)17.53 (0.52)18.82 (0.52)Improvement20.64%17.57%11.38%15.20%From Table3, we observe that the RPK encoding scheme improves the performance of all compared algorithms. The average optimum cost was reduced by at least 11.38%. ABC shows the best average performance for both RPK and TES encoding schemes. The DE and LDES show comparable performance with ABC for the RPK encoding scheme, while the smaller standard deviations (0.05 and 0.09), respectively, indicate more stable performance.The improvement has two sources: first, the RPK allows automatic selection of the number of distribution centers; since each distribution center has a setup cost, fewer distribution center reduces the total cost. However, fewer distribution centers increase the number of delivery points to be serviced, hence increasing the route length of travel through all delivery points and leading to greater transportation costs. On the other hand, TES adopts a fixed number of distribution centers (in this case, 5), and the setup cost is on an average greater than RPK. The RPK balances the number of distribution centers and the route length, which allows each distribution center to operate at a lower average cost.Second, the capacity distribution mechanism in RPK ensures that the total capacity equals the total demand and no capacity is wasted, which produces a more efficient allocation plan.The statistics and convergence curves of the four algorithms in the two encoding schemes are shown in Figures6 and 7. The nonoverlapping notch of the boxes corresponding to different encoding schemes of the same algorithm shows that RPK reduces the median of the optimal cost by 5%.Figure 6
Statistics of the optimal costs in 30 runs of PSO, DE, ABC, and LDES using RPK and TES encoding scheme.Figure 7
Convergence curves of PSO, DE, ABC, and LDES using RPK and TES encoding scheme.Figure7 shows that most optimization processes converge within 50000 function evaluations regardless of the algorithm or the encoding scheme. Except for ABC with RPK, the search of the other algorithms makes small progress throughout the entire process. This observation shows that the visiting limit mechanism keeps the ABC from being stuck in the local optima.The best location and allocation plan found by ABC using RPK and TES encoding schemes are shown in Figure8. A distribution center and associated delivery points are depicted in the markers with the same shape, where a solid marker denotes the distribution center and hollow markers denote delivery points. The size of each marker is proportional to the capacity/demand of DC/DP.Figure 8
Location and allocation plan of ABC using RPK (a) and TES (b) encoding schemes.
(a)(b)Both RPK and TES avoid the mountains and water areas. RPK allows the algorithm to automatically choose the number of distribution centers (in this case, 3). The delivery points are clustered around each distribution center to minimize transportation costs. The optimized number of distribution centers distributes the demands so that each distribution center may operate at a capacity with the lowest possible cost. For the TES, a fixed number of distribution centers prevents some distribution centers from operating at the lowest possible cost. Although the average transportation cost is reduced due to fewer delivery points serviced by each distribution center, the increased setup cost and operational cost make the allocation plan less economical.The algorithm is smart enough under both encoding schemes to choose a location right on the edge of the lattice, which minimizes the setup cost and the transportation cost simultaneously. The detailed plan is shown in Table4. The symbols Ct,i, Cs,i, and Co,i represent the transportation, setup, and operational costs of each distribution center, respectively.Table 4
The detailed location and allocation plan of ABC using RPK and TES encoding schemes.
EncodingDC indexpitxpityciΩiQiCt,iCs,iCo,iRPKDC #10.9000.50024.000[3, 5–7, 9, 15, 18, 19]242.501124.960DC #20.3500.10020.000[2, 4, 11, 14, 20]201.651120.000DC #30.2490.9009.000[1, 8, 10, 12, 13, 16, 17]92.051111.723SubtotalN/AN/A53.000N/A536.203356.683TESDC #10.5500.9511.0711710.00112.031DC #20.3500.10020.001[2, 4, 11, 14, 20]201.650120.001DC #30.9000.50019.054[3, 6, 7, 9, 15, 18, 19]192.001119.097DC #40.3990.1005.004550.40117.817DC #50.1000.8508.000[1, 8, 10, 12, 13, 16]81.700110.880SubtotalN/AN/A53.130N/A535.753559.825The coordinatespitx and pity show that all distribution centers are located on the edge of the lattices, where the setup cost is the lowest, and the distance to delivery points is minimized. The capacities of each distribution center with the RPK encoding scheme are the same as the total demands assigned to them. In contrast, the capacities of TES are slightly greater than the demands, which are a waste of resources and cause greater costs. Meanwhile, the capacities of RPK are closer to the optimal capacity (the optimal capacity can be obtained by solving (10), which is 20 in this case). The total transportation cost of RPK is greater than TES. However, lower setup costs and operational costs compensate for the overall cost.


### 5.3. Sensitivity of the Number of DCs and DPs

This section considers the impact of the number of distribution centers and delivery points. The number of delivery points is 10, 20, 30, 40, and 50. The maximum number of distribution centers is 2, 4, 6, 8, and 10. All four algorithms are tested. RPK and TES are also compared. The results are given in Table5.Table 5
The averaged optimal costs and standard deviations with various numbers of DCs and DPs.
Number of DCsAlgorithmEncoding schemeNumber of DPs#DP = 10#DP = 20#DP = 30#DP = 40#DP = 50#DC = 2PSORPK9.75 (0.2)17.71 (1.1)28.93 (0.9)63.35 (1.1)100.94 (0.9)TES10.00 (0.6)19.14 (0.8)31.29 (1.1)66.06 (1.3)104.53 (1.6)DERPK9.79 (0.0)16.18 (0.4)27.11 (0.3)60.78 (0.3)97.12 (0.6)TES9.17 (0.3)16.65 (0.6)27.39 (0.5)61.36 (0.7)102.68 (3.7)ABCRPK9.00 (0.2)15.94 (0.0)27.07 (0.2)60.52 (0.1)97.19 (0.2)TES9.16 (0.3)16.76 (0.4)28.22 (0.6)62.24 (0.7)99.26 (0.9)LDESRPK9.76 (0.2)15.94 (0.0)27.04 (0.3)60.90 (0.3)97.11 (0.3)TES8.87 (0.1)16.12 (0.2)28.47 (0.7)63.70 (0.9)102.22 (1.0)#DC = 4PSORPK9.74 (0.2)17.20 (0.9)25.67 (1.1)36.72 (1.7)46.76 (1.7)TES12.38 (0.8)21.14 (1.3)29.44 (1.9)42.22 (1.6)54.54 (2.1)DERPK9.79 (0.0)15.95 (0.0)21.69 (0.7)34.98 (2.5)44.31 (2.1)TES12.09 (0.5)17.95 (0.4)24.19 (1.3)37.95 (2.6)48.81 (3.4)ABCRPK8.94 (0.2)15.59 (0.3)21.43 (0.4)30.07 (0.6)38.86 (0.6)TES10.85 (0.3)16.68 (0.5)22.56 (0.6)32.68 (0.9)42.24 (1.3)LDESRPK9.75 (0.1)15.94 (0.0)22.01 (0.4)31.75 (1.3)41.42 (1.4)TES10.99 (0.3)17.74 (0.5)24.52 (1.0)35.54 (1.5)46.47 (1.6)#DC = 6PSORPK9.76 (0.1)17.74 (0.9)25.53 (1.2)36.94 (1.5)45.41 (1.6)TES15.42 (1.2)23.72 (1.6)33.20 (1.9)44.28 (2.5)53.08 (2.3)DERPK9.79 (0.0)15.94 (0.0)21.44 (0.5)34.33 (2.7)41.59 (3.0)TES14.25 (0.8)20.49 (0.6)26.99 (1.4)40.48 (3.5)51.23 (5.3)ABCRPK8.92 (0.2)15.53 (0.4)21.55 (0.4)30.11 (0.6)36.45 (1.1)TES12.72 (0.2)18.46 (0.4)23.88 (0.5)31.47 (0.8)37.29 (1.0)LDESRPK9.79 (0.0)15.94 (0.0)22.21 (0.7)31.52 (1.6)39.23 (2.4)TES13.19 (0.5)20.39 (0.9)26.53 (1.1)35.21 (1.3)41.94 (2.1)#DC = 8PSORPK9.73 (0.2)17.31 (0.9)25.66 (1.3)37.13 (1.5)45.11 (1.8)TES17.94 (1.2)27.92 (1.9)37.98 (2.1)48.02 (3.0)56.36 (3.3)DERPK9.78 (0.0)15.96 (0.0)23.17 (1.1)34.54 (1.9)43.21 (3.8)TES15.37 (0.5)22.49 (0.5)36.58 (2.5)48.52 (10.8)58.75 (15.8)ABCRPK8.94 (0.2)15.54 (0.4)21.49 (0.4)30.32 (0.5)36.47 (0.7)TES14.76 (0.2)20.41 (0.4)25.98 (0.5)32.75 (0.6)37.29 (0.8)LDESRPK9.79 (0.0)15.96 (0.1)22.27 (0.7)31.10 (1.5)38.72 (2.7)TES15.73 (0.7)22.22 (0.8)29.23 (2.2)36.24 (1.3)42.00 (2.1)#DC = 10PSORPK9.76 (0.1)17.86 (1.1)25.67 (1.7)36.81 (1.3)45.10 (1.8)TES22.21 (1.9)31.67 (3.0)41.91 (3.3)52.69 (3.1)60.96 (3.4)DERPK9.78 (0.1)17.02 (0.7)24.45 (1.3)33.70 (2.0)40.60 (3.1)TES17.60 (0.7)24.81 (0.8)39.60 (3.1)57.69 (14.9)82.14 (27.3)ABCRPK9.07 (0.2)15.47 (0.4)21.66 (0.7)30.33 (0.7)36.75 (0.9)TES16.74 (0.2)22.40 (0.5)27.97 (0.5)34.60 (0.5)39.06 (0.8)LDESRPK9.69 (0.3)15.95 (0.0)22.62 (0.9)31.09 (1.9)38.77 (2.5)TES17.40 (0.5)23.96 (0.9)31.38 (2.5)38.13 (1.3)45.89 (4.5)Improvement of RPK over TES can be observed in most cases (except for DE and LDES with #DP = 10 and #DC = 2). For #DC = 2 cases, the improvements of RPK with different numbers of delivery points are not significant because two distribution centers are not enough for any encoding scheme to distribute the demands into economic capacity. When #DC = 4, the average improvement is at least 5% (ABC with #DP = 30), and the highest improvement is 21.3% (PSO with #DP = 10). When #DC = 10, the average improvement is up to 56.05% (PSO with #DP = 10).For #DP = 10, the averaged costs of RPK are steady with different numbers of distribution centers, whereas the averaged costs of TES keep rising with the increasing number of distribution centers. The reason behind this observation is that two distribution centers are sufficient for the optimal distribution of the total demand of 10 delivery points. Even if the maximum number of distribution centers varies, RPK automatically selects two distribution centers to distribute the demands and produce similar solutions. On the other hand, TES uses a fixed number of distribution centers. Therefore, the TES has a similar performance with RPK when #DC = 2 but deteriorated performance with the increasing number of distribution centers because additional distribution centers cause additional setup and operational costs.The statistics of different combinations of algorithms, encoding schemes, and the number of distribution centers are shown in Figure9.Figure 9
Boxplots of the performance statistics for different combinations of algorithms, encoding schemes, number of DCs, and number of DPs.The improvements of RPK over TES are shown in Figure10. When the total demands rise with the number of delivery points, the maximum number of distribution centers that RPK shows a significant improvement (over 20%) rises as well. For example, when #DP = 10, the maximum number of distribution centers needs to be at least 4 for PSO to have an improvement of greater than 20%. When #DP = 50, the number rises to 10. Below a certain maximum number of distribution centers, neither RPK nor TES could find a better allocation plan. In contrast, above the threshold, the dynamic number of distribution centers in RPK shows excellent efficiency in solving the CLAP.Figure 10
Improvement of RPK over TES when the number of DPs increases.


## 5.1. Experiment Settings

The evaluation experiments were conducted on a 10 km by 10 km square region of Zhenjiang, China [30]. The map of this region is divided into 10 × 10 grids, and the setup cost for each lattice is obtained via investigation. The map, grid, and setup cost matrix are shown in Figure 4.Figure 4
The regional grid map of Zhenjiang, China, with an operational cost for each lattice.The setup costs are scaled into five levels. Level 5 represents the most expensive setup cost. The central area (slightly above the middle) has the highest cost, and the suburbs have the lowest cost. A mountain is located slightly below the middle, and some waters are in the north, where a distribution center cannot be set up. We set the cost much higher than the maximum level cost (20 in this case) to prevent generating a distribution center located in these areas. While a finer grid may bring a plan closer to reality, a 10× 10 grid is sufficient to show the algorithm’s mechanism and maintain the map’s readability.The TES and RPK encoding schemes are applied to four algorithms: PSO, DE, ABC, and LDES. Since the compared algorithms use different population sizes, we use the number of cost function evaluations (FEs) instead of the number of generations to measure the performance. The algorithms will stop when the maximum FEs are reached. RPK works on a unified search space and transforms a solutionx∈0,1D into a location and allocation plan, where D is the dimension of the search space, i.e., the number of variables. The algorithm parameters are shown in Table 2.Table 2
Parameter settings for PSO, DE, ABC, and LDES algorithms.
Parameter descriptionValueGeneral parametersThe maximum number of cost function evaluationsFEmax200,000Search space0,1DTransportation cost weightwt1Setup cost weightws1Operational cost weightwt0.1Punishment weightwp30Polynomial coefficientsa for operational cost0.0025,−0.1,2Coordinate boundspmaxtx,pmaxty0,1PSO parameters (Bao et al. [6])Social learning factorc12Personal learning factorc22Weight range [wmin,wmax][0.4,0.9]Population size nPop30Velocity range [vmin,vmax][−0.2,0.2]DE parameters (Moonsri et al. [5])Population size nPop37Crossover probability0.9455Scaling factor0.6497ABC parameters (Guo and Zhang [3])Population size50Number of onlooker bees25Number of employed bees25Food source visiting limit500LDES parameters (Awad et al. [27])Initial population size360Minimum population size4Covariance matrix learning probability pc0.4Selection probability ps0.5Selection rate of the best solutions p_best_rate0.11Archive rate arc_rate1.4Memory size4The initial number of neighbors SEL180Scaling factorsAdaptive adjust


## 5.2. Comparison of TES and RPK Encoding Schemes

The comparison is conducted on the map in Figure4. There are 20 delivery points on the map, each with different demands. The maximum number of delivery centers is set to 5. The location of delivery points and the associated demands are shown in Figure 5.Figure 5
Location and demands of delivery points. The circles show the location, and the circle’s diameter shows the value of demand. The larger the diameter, the greater the demand.Each algorithm runs 30 times, and the optimum costs found by each algorithm are averaged over 30 runs. The results are shown in Table3.Table 3
Average cost over 30 runs and standard deviate for PSO, DE, ABC, and LDES using RPK and TES encoding scheme.
Encoding schemeAverage cost (standard deviation)PSODEABCLDESRPK17.23 (0.74)15.95 (0.05)15.54 (0.4)15.96 (0.09)TES21.71 (1.39)19.35 (0.61)17.53 (0.52)18.82 (0.52)Improvement20.64%17.57%11.38%15.20%From Table3, we observe that the RPK encoding scheme improves the performance of all compared algorithms. The average optimum cost was reduced by at least 11.38%. ABC shows the best average performance for both RPK and TES encoding schemes. The DE and LDES show comparable performance with ABC for the RPK encoding scheme, while the smaller standard deviations (0.05 and 0.09), respectively, indicate more stable performance.The improvement has two sources: first, the RPK allows automatic selection of the number of distribution centers; since each distribution center has a setup cost, fewer distribution center reduces the total cost. However, fewer distribution centers increase the number of delivery points to be serviced, hence increasing the route length of travel through all delivery points and leading to greater transportation costs. On the other hand, TES adopts a fixed number of distribution centers (in this case, 5), and the setup cost is on an average greater than RPK. The RPK balances the number of distribution centers and the route length, which allows each distribution center to operate at a lower average cost.Second, the capacity distribution mechanism in RPK ensures that the total capacity equals the total demand and no capacity is wasted, which produces a more efficient allocation plan.The statistics and convergence curves of the four algorithms in the two encoding schemes are shown in Figures6 and 7. The nonoverlapping notch of the boxes corresponding to different encoding schemes of the same algorithm shows that RPK reduces the median of the optimal cost by 5%.Figure 6
Statistics of the optimal costs in 30 runs of PSO, DE, ABC, and LDES using RPK and TES encoding scheme.Figure 7
Convergence curves of PSO, DE, ABC, and LDES using RPK and TES encoding scheme.Figure7 shows that most optimization processes converge within 50000 function evaluations regardless of the algorithm or the encoding scheme. Except for ABC with RPK, the search of the other algorithms makes small progress throughout the entire process. This observation shows that the visiting limit mechanism keeps the ABC from being stuck in the local optima.The best location and allocation plan found by ABC using RPK and TES encoding schemes are shown in Figure8. A distribution center and associated delivery points are depicted in the markers with the same shape, where a solid marker denotes the distribution center and hollow markers denote delivery points. The size of each marker is proportional to the capacity/demand of DC/DP.Figure 8
Location and allocation plan of ABC using RPK (a) and TES (b) encoding schemes.
(a)(b)Both RPK and TES avoid the mountains and water areas. RPK allows the algorithm to automatically choose the number of distribution centers (in this case, 3). The delivery points are clustered around each distribution center to minimize transportation costs. The optimized number of distribution centers distributes the demands so that each distribution center may operate at a capacity with the lowest possible cost. For the TES, a fixed number of distribution centers prevents some distribution centers from operating at the lowest possible cost. Although the average transportation cost is reduced due to fewer delivery points serviced by each distribution center, the increased setup cost and operational cost make the allocation plan less economical.The algorithm is smart enough under both encoding schemes to choose a location right on the edge of the lattice, which minimizes the setup cost and the transportation cost simultaneously. The detailed plan is shown in Table4. The symbols Ct,i, Cs,i, and Co,i represent the transportation, setup, and operational costs of each distribution center, respectively.Table 4
The detailed location and allocation plan of ABC using RPK and TES encoding schemes.
EncodingDC indexpitxpityciΩiQiCt,iCs,iCo,iRPKDC #10.9000.50024.000[3, 5–7, 9, 15, 18, 19]242.501124.960DC #20.3500.10020.000[2, 4, 11, 14, 20]201.651120.000DC #30.2490.9009.000[1, 8, 10, 12, 13, 16, 17]92.051111.723SubtotalN/AN/A53.000N/A536.203356.683TESDC #10.5500.9511.0711710.00112.031DC #20.3500.10020.001[2, 4, 11, 14, 20]201.650120.001DC #30.9000.50019.054[3, 6, 7, 9, 15, 18, 19]192.001119.097DC #40.3990.1005.004550.40117.817DC #50.1000.8508.000[1, 8, 10, 12, 13, 16]81.700110.880SubtotalN/AN/A53.130N/A535.753559.825The coordinatespitx and pity show that all distribution centers are located on the edge of the lattices, where the setup cost is the lowest, and the distance to delivery points is minimized. The capacities of each distribution center with the RPK encoding scheme are the same as the total demands assigned to them. In contrast, the capacities of TES are slightly greater than the demands, which are a waste of resources and cause greater costs. Meanwhile, the capacities of RPK are closer to the optimal capacity (the optimal capacity can be obtained by solving (10), which is 20 in this case). The total transportation cost of RPK is greater than TES. However, lower setup costs and operational costs compensate for the overall cost.


## 5.3. Sensitivity of the Number of DCs and DPs

This section considers the impact of the number of distribution centers and delivery points. The number of delivery points is 10, 20, 30, 40, and 50. The maximum number of distribution centers is 2, 4, 6, 8, and 10. All four algorithms are tested. RPK and TES are also compared. The results are given in Table5.Table 5
The averaged optimal costs and standard deviations with various numbers of DCs and DPs.
Number of DCsAlgorithmEncoding schemeNumber of DPs#DP = 10#DP = 20#DP = 30#DP = 40#DP = 50#DC = 2PSORPK9.75 (0.2)17.71 (1.1)28.93 (0.9)63.35 (1.1)100.94 (0.9)TES10.00 (0.6)19.14 (0.8)31.29 (1.1)66.06 (1.3)104.53 (1.6)DERPK9.79 (0.0)16.18 (0.4)27.11 (0.3)60.78 (0.3)97.12 (0.6)TES9.17 (0.3)16.65 (0.6)27.39 (0.5)61.36 (0.7)102.68 (3.7)ABCRPK9.00 (0.2)15.94 (0.0)27.07 (0.2)60.52 (0.1)97.19 (0.2)TES9.16 (0.3)16.76 (0.4)28.22 (0.6)62.24 (0.7)99.26 (0.9)LDESRPK9.76 (0.2)15.94 (0.0)27.04 (0.3)60.90 (0.3)97.11 (0.3)TES8.87 (0.1)16.12 (0.2)28.47 (0.7)63.70 (0.9)102.22 (1.0)#DC = 4PSORPK9.74 (0.2)17.20 (0.9)25.67 (1.1)36.72 (1.7)46.76 (1.7)TES12.38 (0.8)21.14 (1.3)29.44 (1.9)42.22 (1.6)54.54 (2.1)DERPK9.79 (0.0)15.95 (0.0)21.69 (0.7)34.98 (2.5)44.31 (2.1)TES12.09 (0.5)17.95 (0.4)24.19 (1.3)37.95 (2.6)48.81 (3.4)ABCRPK8.94 (0.2)15.59 (0.3)21.43 (0.4)30.07 (0.6)38.86 (0.6)TES10.85 (0.3)16.68 (0.5)22.56 (0.6)32.68 (0.9)42.24 (1.3)LDESRPK9.75 (0.1)15.94 (0.0)22.01 (0.4)31.75 (1.3)41.42 (1.4)TES10.99 (0.3)17.74 (0.5)24.52 (1.0)35.54 (1.5)46.47 (1.6)#DC = 6PSORPK9.76 (0.1)17.74 (0.9)25.53 (1.2)36.94 (1.5)45.41 (1.6)TES15.42 (1.2)23.72 (1.6)33.20 (1.9)44.28 (2.5)53.08 (2.3)DERPK9.79 (0.0)15.94 (0.0)21.44 (0.5)34.33 (2.7)41.59 (3.0)TES14.25 (0.8)20.49 (0.6)26.99 (1.4)40.48 (3.5)51.23 (5.3)ABCRPK8.92 (0.2)15.53 (0.4)21.55 (0.4)30.11 (0.6)36.45 (1.1)TES12.72 (0.2)18.46 (0.4)23.88 (0.5)31.47 (0.8)37.29 (1.0)LDESRPK9.79 (0.0)15.94 (0.0)22.21 (0.7)31.52 (1.6)39.23 (2.4)TES13.19 (0.5)20.39 (0.9)26.53 (1.1)35.21 (1.3)41.94 (2.1)#DC = 8PSORPK9.73 (0.2)17.31 (0.9)25.66 (1.3)37.13 (1.5)45.11 (1.8)TES17.94 (1.2)27.92 (1.9)37.98 (2.1)48.02 (3.0)56.36 (3.3)DERPK9.78 (0.0)15.96 (0.0)23.17 (1.1)34.54 (1.9)43.21 (3.8)TES15.37 (0.5)22.49 (0.5)36.58 (2.5)48.52 (10.8)58.75 (15.8)ABCRPK8.94 (0.2)15.54 (0.4)21.49 (0.4)30.32 (0.5)36.47 (0.7)TES14.76 (0.2)20.41 (0.4)25.98 (0.5)32.75 (0.6)37.29 (0.8)LDESRPK9.79 (0.0)15.96 (0.1)22.27 (0.7)31.10 (1.5)38.72 (2.7)TES15.73 (0.7)22.22 (0.8)29.23 (2.2)36.24 (1.3)42.00 (2.1)#DC = 10PSORPK9.76 (0.1)17.86 (1.1)25.67 (1.7)36.81 (1.3)45.10 (1.8)TES22.21 (1.9)31.67 (3.0)41.91 (3.3)52.69 (3.1)60.96 (3.4)DERPK9.78 (0.1)17.02 (0.7)24.45 (1.3)33.70 (2.0)40.60 (3.1)TES17.60 (0.7)24.81 (0.8)39.60 (3.1)57.69 (14.9)82.14 (27.3)ABCRPK9.07 (0.2)15.47 (0.4)21.66 (0.7)30.33 (0.7)36.75 (0.9)TES16.74 (0.2)22.40 (0.5)27.97 (0.5)34.60 (0.5)39.06 (0.8)LDESRPK9.69 (0.3)15.95 (0.0)22.62 (0.9)31.09 (1.9)38.77 (2.5)TES17.40 (0.5)23.96 (0.9)31.38 (2.5)38.13 (1.3)45.89 (4.5)Improvement of RPK over TES can be observed in most cases (except for DE and LDES with #DP = 10 and #DC = 2). For #DC = 2 cases, the improvements of RPK with different numbers of delivery points are not significant because two distribution centers are not enough for any encoding scheme to distribute the demands into economic capacity. When #DC = 4, the average improvement is at least 5% (ABC with #DP = 30), and the highest improvement is 21.3% (PSO with #DP = 10). When #DC = 10, the average improvement is up to 56.05% (PSO with #DP = 10).For #DP = 10, the averaged costs of RPK are steady with different numbers of distribution centers, whereas the averaged costs of TES keep rising with the increasing number of distribution centers. The reason behind this observation is that two distribution centers are sufficient for the optimal distribution of the total demand of 10 delivery points. Even if the maximum number of distribution centers varies, RPK automatically selects two distribution centers to distribute the demands and produce similar solutions. On the other hand, TES uses a fixed number of distribution centers. Therefore, the TES has a similar performance with RPK when #DC = 2 but deteriorated performance with the increasing number of distribution centers because additional distribution centers cause additional setup and operational costs.The statistics of different combinations of algorithms, encoding schemes, and the number of distribution centers are shown in Figure9.Figure 9
Boxplots of the performance statistics for different combinations of algorithms, encoding schemes, number of DCs, and number of DPs.The improvements of RPK over TES are shown in Figure10. When the total demands rise with the number of delivery points, the maximum number of distribution centers that RPK shows a significant improvement (over 20%) rises as well. For example, when #DP = 10, the maximum number of distribution centers needs to be at least 4 for PSO to have an improvement of greater than 20%. When #DP = 50, the number rises to 10. Below a certain maximum number of distribution centers, neither RPK nor TES could find a better allocation plan. In contrast, above the threshold, the dynamic number of distribution centers in RPK shows excellent efficiency in solving the CLAP.Figure 10
Improvement of RPK over TES when the number of DPs increases.


## 6. Conclusion

The solution representation of practical engineering problems may significantly affect the performance of swarm-based algorithms. Proper encoding of the solutions may bring three significant advantages:(1)
The encoded solution could have uniform ranges, which is suitable for the algorithm adopting a “crossover” operator that may switch the position of the elements in a solution vector(2)
The landscape of the solution space is altered to provide more “algorithm-friendly” information, such as gradients and continuity(3)
Some constraints may be eliminated, which increases the rate of feasible solutions in the newly generated solutions, hence improving the search efficiencyWe propose the random proportion and random key (RPK) encoding scheme to represent the location and allocation plan of an express CLAP. RPK brings three advantages over traditional encoding schemes:(1)
RPK dynamically chooses the number of distribution centers in the search process. The solutions with different numbers of distribution centers coexist and evolve in the same swarm.(2)
The allocation of delivery points is determined by the order of elements instead of the value of elements. Then, the candidate capacity is determined by the proportion of the total demand. This mechanism allows the delivery point assignment constraint and capacity/demand constraint to be satisfied simultaneously. There is no need to introduce a punishment term for violation of constraints.(3)
RPK benefits all continuous optimization algorithms, swarm-based or not, by the means of transformation of the search landscape and elimination of constraints.



---

*Source: 3635073-2022-08-29.xml*