1. Introduction
China is currently in the process of urbanization, more and more people are pouring into cities, and the scale of cities is getting bigger and bigger. The city gathers resources from all directions, and it also generates a lot of garbage. As of the end of 2015, the urban permanent population has reached 770 million, an increase of more than 20 million over the end of the previous year, and the urbanization rate has reached 56.1% (Wang, 2016). In the future, this rate will further increase, gradually approaching the 80% urbanization rate of developed countries, and the current annual growth rate of waste in the world has reached 8%. As the world’s largest emerging economy, China’s garbage growth rate has even reached 10%. As early as 2013, global waste production exceeded 500 million tons, and China accounted for more than 30% of it at that time.
With the continuous improvement of the living standards of urban residents and the continuous development of cities, the output of urban domestic waste in China is increasing. The impact of waste on the living environment and human health has attracted widespread attention. The problem of garbage encircling cities is getting more and more serious, and its harm is getting bigger and bigger. How to efficiently transfer garbage to a treatment or disposal site is an urgent problem that needs to be solved. In recent years, many large and medium-sized cities in China have invested in the construction of waste landfills to solve the problem of garbage siege, but there will be problems with the original collection and transportation system and its incompatibility. Under normal circumstances, the collection and transportation of urban garbage are mainly rickshaws and cars with relatively small tonnage, which are not suitable for long-distance transportation, and garbage disposal sites are generally far away from urban areas. To solve this contradiction, garbage transfer stations came into being. On the one hand, the garbage transfer station can receive the garbage from the garbage collection point, and on the other hand, it is the starting point of the garbage landfill or incineration site, which plays a role in connecting the previous and the next.
At present, the management of urban domestic waste in China follows the principle of comprehensive and hierarchical management, and adheres to the general principle of “harmlessness, reduction, and resource utilization” as the guide. Waste transfer is one of the most important logistics systems under the framework of integrated waste management. On this basis, China can only achieve efficient and sustainable management of domestic waste from different sources through the optimal management of the municipal solid waste system, through a strategic approach, maximizing the effective use of resources and providing reasonable technology for harmlessness disposal. Both theoretical and practical studies have shown that the garbage transfer system is an indispensable part of the framework of the comprehensive management system of urban domestic waste. The comprehensive management system of domestic waste not only uses technology to treat domestic waste and improve the environment, but also reduces the health and safety risks faced by residents to ensure the sustainable development of the urban ecological environment and natural ecological environment. Therefore, this article will focus on the research on the weaker transfer links in China’s urban waste disposal system, and discuss the location and route planning of waste transfer stations with the smallest distribution cost and the smallest impact on the surrounding environment under the guidance of data support and algorithm theory.
2. Literature Review
Considering this topic, there are two main research focuses: The first is to explore the characteristics of the adjacent facilities such as waste transfer stations and the scientific problems behind them. The second is to solve the problem of location and route planning in the waste transfer network based on intelligent algorithm.
2.1. Garbage Transfer and Neighbor Avoidance Effect
Xiang et al. (2016) briefly discussed the status quo of the classification and recycling of domestic waste in major cities around the world, and analyzed the practical conditions of various treatment methods based on these status quo and the specific conditions of each region, and compared them.
Zhu & Zhao (2019) discussed the three most commonly used methods of harmless garbage disposal in China, namely incineration, composting, and landfill, and concluded that incineration is the future direction of development.
Vigo (2016) used Japanese garbage disposal methods as a reference, discussed the existing garbage transportation, transfer, and treatment methods in Wuhan, and gave corresponding opinions.
Bakan (2016) analyzed the current waste management situation in Wuhan from the perspective of waste management. In the research, he paid attention to the contradictions that are easy to cause in the waste treatment process, and proposed corresponding countermeasures.
Demirbas et al. (2017) discussed the impact of neighboring facilities on surrounding residents from a political perspective. The article points out that the degree of fairness and the degree of public participation have a significant impact on the benefits of avoiding neighbors, and it is proposed that both efficiency and fairness should be considered in the selection of neighboring facilities.
Gill et al. (2018) pointed out that the contradiction arising in the process of garbage disposal is essentially the contradiction of avoiding neighbors, so the core issue is to eliminate the benefit of avoiding neighbors. The root cause of this contradiction is that the generation of garbage and the disposal of garbage are not carried out at the same place. He proposed that in order to resolve this contradiction, it is necessary to provide subsidies to residents who have been negatively affected.
Ghadimi et al. (2017) described the root cause of the contradiction in response to the garbage compression station demonstration, and gave relevant solutions at the government level. The first is to enable the government to play a central role in the construction of garbage stations, and then conduct rational dialogue and communication with the public, and finally establish relevant legal systems to regulate the construction and operation of garbage stations.
Pires et al. (2019) pointed out that a garbage incineration plant is a kind of neighboring facility. As the name suggests, it is a facility that is not popular with surrounding residents. The feature of avoidance facilities is that it will have a negative externality impact on the surrounding residents.
2.2. Location and Route Planning of Garbage Transfer Station
Crociata et al. (2016) conducted a research on the location of waste incineration transfer station. First, the specific influencing factors of the site selection of the garbage transfer station are analyzed, and the preliminary site selection is completed through the analytic hierarchy process. Then use fuzzy mathematics to describe the corresponding accurate location model of multi-objective planning. Finally, an example is used to verify the correctness of the model.
Xiao et al. (2018) analyzed the role of the media in the contradiction in the location of waste incineration transfer stations. It is pointed out that while reporting the truth, the media should also correctly guide the direction of public opinion. It is pointed out that the garbage transfer station must communicate with the surrounding people at the beginning of the site selection, and actively eliminate the negative impact caused by the garbage transfer station.
Hu & Yang (2020) discussed the location of waste transfer stations from the perspective of risk management. They pointed out that the reason why the construction of waste transfer stations was opposed by residents was that, in the final analysis, the risk distribution was unreasonable and everyone produced waste at the same time. However, only a small number of people are affected by the garbage transfer station. Although the government has always advocated waste incineration, the public refused to choose a location around them while accepting that waste incineration is a reasonable way to dispose of waste. He proposed the establishment of an online monitoring system to allow the public to participate in supervision to break this dilemma.
Han et al. (2019) presented a model for selecting a location for a waste incineration transfer station based on a compensation mechanism, and demonstrated the importance of compensation in the location of avoidance facilities. And through the analytic hierarchy process, the weight of each influencing factor is analyzed, and the compensation plan is given.
Prasertsri & Sangpradid (2020) analyzed the selection principle of waste incineration transfer station, summarized the requirements of laws and regulations for the location of waste incineration transfer station, and gave general site selection opinions.
Zhao et al. (2015) used the SWOT matrix to compare candidate sites in the site selection of waste transfer stations, comparing strengths, weaknesses, opportunities, and threats, and determined the best choice.
Li et al. (2021) introduced geographic information system (GIS) into the site selection study of urban waste treatment plants, and used GIS to determine the actual traffic conditions between the waste treatment plant and residential areas, thereby improving the accuracy of site selection.
2.3. Intelligent Algorithm for Solving Problems
In this study, genetic algorithm is mainly used to solve the location problem in the waste transfer network, and ant colony algorithm is used to solve the transfer vehicle route planning problem.
1) Application of genetic algorithm in Location selection
Guo (2020) made a detailed operation process for the location selection of the logistics system distribution network based on the genetic algorithm in accordance with the actual location selection operation of the logistics system distribution network. In the research, the algorithm analysis case is determined, and the advantages of genetic algorithm for the location of logistics system distribution network are explored in depth.
Elkblek (2020) analyzed the respective characteristics of the genetic algorithm and the simulated annealing algorithm, and proposed that fusing the two together in the case of constraint solving can play a role in enhancing the efficiency of the algorithm, and made a case study at the same time. After building a model, a comparative study was made on the time complexity and space complexity of the above three types of resource search algorithms. It can be seen that the resource search algorithm based on the hierarchical structure is better than the other two resource search algorithms in terms of the performance of the algorithm.
2) Application of ant colony algorithm in vehicle routing problem
According to the parallel characteristics of ant colony algorithm, Mansour et al. (2020) proposed a location optimization method based on multi-tree parallel ant colony algorithm. This method divides the geographical space into multi-trees, collects the pheromone information gradually left by the ants when they travel between the multi-trees, and selects paths to obtain ideal candidate solutions. The improved method can obtain a more ideal solution in a short time, and is suitable for calculating the problem of spatial resource allocation in a large area.
Zheng et al. (2019) proposed a new model of location selection combined with multi-agent and ant colony algorithm. Yang et al. (2019) constructed a distribution center location model that aims to minimize the total cost and is suitable for solving the single assignment constraint and capacity constraint facility location problem. The improvement of the ant colony algorithm specifically divides the solution process into two-layer ant colonies related to each other in the facility selection layer and the demand assignment layer.
It can be seen from the above-mentioned scholars’ research that ant colony algorithm is a common algorithm to solve route planning problems. However, in the actual application process, the conventional ant colony algorithm is not very accurate, and it is easy to fall into the local optimal solution, which is not conducive to the global solution of route planning. For this reason, in the follow-up research of this subject, we will learn from the improved design experience of scholars, and design an ant colony algorithm with improved solution strategy to solve the route planning problem of garbage transfer vehicles.
3. The Modeling of Urban Domestic Waste Transfer Network
With the rapid development of China’s national economy and the continuous expansion of the scale of cities, the production of urban domestic waste is increasing, and the pollution of garbage to the environment is also becoming more and more serious. White pollution and garbage siege have become major problems that plague urban development. Therefore, how to economically and effectively transport and dispose of the monthly increase in urban domestic waste has become a hot spot of social concern. From a global perspective, the most commonly used method of garbage disposal is to build an interval, large-capacity garbage landfill far away from the urban area, but this will increase the distance of garbage collection and transportation, resulting in the number of garbage collection trucks. And the increase in transportation costs has also increased the degree of urban traffic congestion. Therefore, in order to solve this problem, it is necessary to establish a garbage collection and transfer station in a suitable location in the city. Therefore, the optimization of the location of the garbage collection and transportation system also arises at the historic moment.
From the analysis of logistics theory, the collection and transportation system of municipal solid waste is a special reverse logistics recycling network. Reverse logistics is a logistics activity that includes product return, item reuse, waste disposal, repair and remanufacturing and other processes. The garbage collection and transportation system includes three parts: collection, transfer, and transportation, namely: the garbage collection and transportation are separated through the transfer station, and the garbage in each residential area is first transported to the transfer station with a collection truck with a compression device, and then the large capacity is used. Transport trucks transport the garbage to the comprehensive treatment center for sorting and processing. Therefore, the optimization of the municipal solid waste system can be considered from three inverse aspects, namely, the optimization of garbage collection and transportation routes and the optimization of the location of transfer stations and treatment stations, so how to determine the optimal number of transfer stations and comprehensive treatment plants and Location is the key to building a garbage collection network model. However, the location of the garbage transfer station and treatment plant is a difficult problem, because it usually faces many conflicts. If the garbage transfer station and treatment center are too close to the residential area, the pollution it produces will definitely affect the lives of citizens. Quality, however, if the garbage transfer station and processing center are too far away from the city where the garbage is mainly generated, it will cause inconvenience to the collection and transfer of garbage, and it will also greatly increase the transportation cost. Therefore, the site selection of waste transfer stations should take into account economic, environmental and social benefits, that is, it is a multi-objective planning problem subject to multiple criteria. Although Yan (2019) and Yan et al. (2020) have studied the optimal location model and solution method of garbage transfer station, most of them only consider the single-objective optimization problem with the least cost, and ignore the negative impact on the environment and citizens. Although Yang and Chang (2020) considered the impact of the location of garbage transfer station on society and the environment, there is no specific optimization model and algorithm. Yi et al. (2020) established a model for evaluating existing garbage transfer stations, but it is also limited to the evaluation objective of optimal cost. The selection strategies obtained by these single-objective optimization problems undoubtedly have great limitations, because for decision makers, they hope to have as many selection strategies as possible. The multi-objective planning model established in this paper is the optimal location of the waste collection and transportation system. This allows government departments to have more decision-making choices when selecting locations for garbage transfer stations.
3.1. Basic Idea of Model Building
The two-level programming model is used to analyze and study the problems with two levels of decision-making. When faced with complex problems, it can be dealt with in stages and levels, comprehensively considered, and finally achieve the overall optimum. Combined with the characteristics of the urban domestic waste transfer network, this paper establishes a two-level planning model to achieve the optimization goal as follows: the total cost of the site selection cost of the waste transfer station and the waste treatment center and the cost of the distribution vehicle is minimized. The dynamic optimization process of the upper and lower layers is reflected through the two-layer model. The specific goals are as follows:
The cost of the urban domestic waste transfer network studied in this paper is composed of the construction cost of the waste transfer station and the waste treatment center and the distribution cost of the distribution vehicle. The two-layer model established in this paper includes the construction and operation costs of waste transfer stations and the penalty cost of NIMBY facilities in the upper model; the lower model includes the transportation cost and vehicle input cost of the vehicle routing problem.
The upper-level planning model mainly determines the number and location of site selection for waste transfer stations and waste treatment centers. When constructing the upper-level mathematical model, in addition to considering the fixed location costs of waste transfer stations and waste treatment centers, the cost of NIMBY facilities is also considered. The influence factors of penalty cost on site selection are taken into account, and the site selection problem of waste transfer station and waste treatment center is jointly optimized.
When building the lower-level mathematical model, when the distribution center scheme of the upper-level model is considered, the planning of the urban domestic garbage collection path is realized. The main factors considered in the lower model mainly include the transportation cost of garbage trucks and the vehicle input cost. In this paper, a two-layer model is constructed based on the above ideas.
3.2. Model Assumptions and Symbol Description
1) Model assumptions
In order to facilitate the establishment of the model, we give the following assumptions and explanations:
a) The garbage collection points are all residential areas, and the larger the population of the residential area, the more garbage will be produced;
b) The unit transportation cost is known, and the transportation cost is proportional to the transportation volume and distance;
c) Considering the small scale of the city, only one comprehensive treatment plant will be built;
d) Garbage from each garbage collection point can only be transported to one garbage transfer station;
e) The compensation cost of each candidate garbage transfer station is determined by the city loop, which means that the compensation cost of the candidate garbage transfer station is relatively fixed;
f) There are no other garbage transfer stations in the construction area, and there is no competition between the newly built garbage transfer stations. At this time, the garbage in a single residential area is provided by a single garbage transfer station;
g) The garbage transfer stations are independent of each other, and there is no coordinated transfer;
h) The current waste transfer system uses a uniform type of waste transfer vehicle;
i) The garbage transfer station has a certain number of garbage trucks, each garbage truck belongs to only one garbage transfer station, and there is no situation that multiple garbage transfer stations dispatch the same vehicle at the same time;
j) The speed of the vehicle is known and fixed during transportation, and the service garbage collection points are all residential areas. After completing the task, you must return to the garbage transfer station, regardless of the situation that the residential area sends its own vehicles to transport domestic garbage.
2) Symbol description
, i refers to residential areas;
, j refers to the transfer station to be selected;
, k refers to the treatment plant to be selected.
: Number of population in residential area i; T: Planned service life of transfer station and treatment plant; r: Per capita daily garbage production;
: Unit transportation cost;
: Capacity of garbage transfer station j;
: Indicates the load of vehicle h when it departs from the distribution center;
: Fixed construction cost of transfer station j;
:Compensation fee for transfer station j;
: Fixed construction cost of comprehensive treatment plant k;
: Distance from residential area i to transfer station j;
: Distance from transfer station j to comprehensive treatment plant k;
:Distance from residential area i to comprehensive treatment plant k. This chapter intends to design an improved ant colony algorithm to solve this problem. Therefore, it is necessary to add a variable description: represents the rated load of the garbage truck.
In addition, set the following three 0 - 1 variables to clarify the relationship between nodes.
3.3. Two-Tier Model Construction
This paper divided the analyzed cost targets into upper and lower models. The cost of the urban domestic waste transfer network studied in this paper is composed of the construction cost of the waste transfer station and the waste treatment center and the distribution cost of the distribution vehicle. The two-layer model established in this paper includes the construction and operation costs of waste transfer stations and the penalty cost of NIMBY facilities in the upper model; the lower model includes the transportation cost and vehicle input cost of the vehicle routing problem.
The upper and lower model of the urban domestic waste transfer network problem is established.
1) Upper model
As the garbage transfer station and treatment plant will have a negative effect on the living environment of nearby residents, their location should be as far away as possible from the residential area. On the other hand, the garbage transfer cost should be minimized after the location is determined. Based on the above site selection goals, the site selection model for garbage transfer stations established in this paper is as follows:
(3.1)
(3.2)
(3.3)
s.t.
(3.4)
(3.5)
(3.6)
The first two items of the first objective function respectively represent the construction cost of the waste transfer station and the treatment plant and the compensation fee of the waste transfer station. The middle item represents the transportation cost of garbage from the residential area to the transfer station within the planning period, and the last item represents the transportation cost of garbage from the transfer station to the treatment plant. The second goal means that the sum of the distances from the garbage mountain residential area to the corresponding transfer station is the smallest, and the third goal is to maximize the minimum distance from the garbage treatment plant to the residential area. The constraint condition (3.4) indicates that the garbage in each residential area can only be transported to one garbage transfer station. The formula (3.5) indicates that only one comprehensive waste treatment center will be built. Equation (3.6) indicates that only a transfer station has been built in place j to be able to transport garbage here.
2) Lower model
The lower model includes the transportation cost and vehicle input cost of the vehicle routing problem.
(3.7)
s.t.
(3.8)
(3.9)
(3.10)
(3.11)
Equation (3.7) represents the objective function of the lower-level model, which is the minimum transportation cost, and the vehicle input cost is represented by the number of vehicles in the finalized plan. The constraint condition (3.8) indicates that the garbage in each residential area can only be transported to one garbage transfer station. The formula (3.9) indicates that only one comprehensive waste treatment center will be built. Equation (3.10) indicates the capacity limit of the transfer station j. Equation (3.11) indicates that the vehicle cannot exceed the rated load of the vehicle when collecting domestic garbage.
4. Solution Algorithm Design
4.1. Upper-Level Model Solving Algorithm
In this paper, a multi-objective genetic algorithm based on SPEA2 is used to solve the upper model, and the optimal solution of the model can be obtained by selecting the appropriate coding method and operator.
1) Coding
In this paper, real number coding based on ordinal number is used to represent chromosomes. Firstly, the garbage collection points, alternative transfer stations and disposal sites are numbered, and then the composition of the chromosomes is determined according to the characteristics of the solution. The chromosome is designed into a structure of length
. Each chromosome is composed of two gene strings u and v, where the length of u is I, and the length of v is 1. This article uses integer encoding from 1 to J for u to construct the following string:
,. I is the total number of residential areas. The value of
represents the number of the transit station serving residential area i. Its value range is [1 - J]. The value of v represents the number of the selected comprehensive treatment plant. Its value range is [1, K]. In the example of this paper, if the code of an individual is 37868104828425672555544876776671, the first 30 digits indicate in turn: the first residential area is served by the third transit station, the second residential area is served by the seventh transit station, and the third The residential area is served by the 8th transfer station, and the last digit 1 means that the comprehensive treatment field number 1 is selected for construction.
2) Decoding
The encoding of u needs to be decoded into the following matrix with 1 row and J columns:
indicates that garbage collection point i is served by transfer station j, otherwise
. Similarly, decode v into a K-dimensional vector as follows
, If the value of v is k, then
, otherwise
. In this example, if the code of an individual is 37868104828425672555544876776673, then
3) Constraint handling and fitness value allocation
The first and second goals of the original model are to find the minimum value, and the third goal is to find the maximum value. In order to facilitate the solution, the third goal is also transformed into a minimum value, that is
. This article uses the penalty function method to deal with the constraints. The constraints are transformed into the following form:
The construction method of the penalty function is
, Where
is the constraint function, L is the total number of constraints. In this model
, the penalty function is:
Then the following functions are constructed:
,
and
are the coefficients of the penalty term. They are gradually increasing with the increase of genetic algebra. In order to unify the dimensions, the standardized operation of
is carried out for
,
. According to the function value of each individual, calculate their fitness value F using the method of SPEA2.
4) Hybridization and mutation
In this paper, we use two-point uniform crossing. The crossing probability is set to 0.8; for two different crossing parents, two different crossing points are randomly generated, such as:
Father 1 37868104828|425672555544|876776673,
Father 2 38113102272|776656556549|947776662.
Then randomly generate a number
between 0 and 1. If
, then exchange the first paragraph, that is, the part before the first hybridization point; If
, then swap the second part, the part between the two points; If
, then swap the third part. For example when
, two offspring can be obtained by swapping the middle part of the parent one and the parent two.
Offspring 1 37868104828776656556549876776673
Offspring 2 38113102272425672555544947776662
The mutation rate in this paper is set as
. xdim is chromosome length. The specific mutation method is: for an individual
, v. For the first half
, first randomly generate an array with 1 row and 1 column
,
,
. If
, Corresponding locus
is mutated. After mutation
and
. For the latter gene position v, a number is also generated
. If
, v is mutated.After mutation
and
.
5) Algorithm flow
Step 1: Determine the parameters: given population size N, archive set size M, maximum number of iterations
, hybridization probability
, mutation probability
.
Step 2: Initialize the population: randomly generate the initial population
, and make the archive set
empty.
Step 3: Fitness allocation: Calculate the fitness of all individuals in
and
.
Step 4: Environmental selection: save all non-dominated individuals to
in the evolutionary population
and archive set
. If the size of
exceeds M, use the trimming process to reduce its size; if the size ratio of
is smaller than M, select the dominant individual from
and
to fill
.
Step 5: End condition: If
, then
, and go to step 6, otherwise, output all non-dominated individuals in
, and the operation ends.
Step 6: Cross and mutation, use the championship selection method to select individuals from
to perform crossover and mutation operations, and save the results to
, and return to the second step.
4.2. Lower-Level Model Solving Algorithm
1) Improvement ideas
For complex VRP and LRP variant problems, the efficiency and quality of the traditional ant colony algorithm are relatively low, or even impossible to solve, so the traditional algorithm needs to be improved. At present, there are three main directions for the improvement of ant colony algorithm. One is to improve and optimize a single algorithm, which is mainly designed for the basic rules of ant colony algorithm, including the improvement of probability transfer formula and the addition of new influence factors. The second is to mix other heuristic algorithms, such as the fusion with genetic algorithm, and the fusion with immune algorithm, etc.; The strategy gives different basic rules or control parameters to each ant colony, and the common settings are shown in literature. This paper draws on the improvement ideas of the above-mentioned ant colony algorithm, designs an improved algorithm rule, and incorporates a multi-ant colony intelligent algorithm for neighborhood search.
Different from the traditional multi-ant colony algorithm, the solution strategy of each ant colony in the multi-ant colony algorithm set in this paper is fundamentally different. By analyzing the difference between the ant colony algorithm for solving the VRP problem and the TSP problem, it is found that the ant colony algorithm’s solution strategy for the two problems is fundamentally different. When solving the TSP problem, any individual in the ant colony needs to traverse all the nodes. At this time, the ant path is a feasible solution to the problem, which is called the full traversal strategy; when solving the VRP problem, the ant individual can choose either the full traversal strategy or The current iteration can be ended after a delivery is completed, which is called a single-loop strategy. At this time, the ant path is only a part of the feasible solution, and it needs to be spliced to form a new feasible solution. Considering the full traversal strategy, the algorithm can more easily obtain feasible solutions, but it is easy to fall into the local optimum. The single loop strategy has better global search capabilities, but the solution speed is too slow. Therefore, in the multi-ant colony algorithm set in this article, one child ant colony adopts a full traversal strategy, and the other child ant colony adopts a single-loop strategy. Different rule parameters and colony scales are set for the two child ant colonies. After the two child colonies are stopped, the pheromone between the exchange ant colonies is updated and exchanged. The 2-opt neighborhood search algorithm is introduced to update the feasible solution of the algorithm and further improve the quality of the solution.
2) Improved basic rule design of ant colony algorithm
For the convenience of describing the mathematical model, the following basic parameters are defined:
indicates the pheromone concentration on the line of node i and j;
represents the visibility between nodes i and j,
;
represents a collection of accessible points for ant k;
represents the probability that ant k transfers from node i to j at time t;
indicates the volatilization factor of the information number.
1) Design of transfer rules
First, improve the transition probability formula. In this paper, a saving distance factor is added to the traditional transition probability formula to ensure that the next node selected by the ant contributes the most to the target value. The new transition probability formula is shown in formula:
The above formula represents the pheromone heuristic factor, represents the visibility heuristic factor, in order to save the distance heuristic factor, in order to save the distance, its calculation formula is as shown in formula, consider when the ants start from the yard, the saving distance setting Set as 1.
In order to solve the problem of premature convergence of the algorithm, variables are introduced in the process of ants selecting the next node q0, the rule for ants to choose to visit the next node is shown in formula.
The above formula q represents a random number,
q0 indicates the set upper limit variable. When q < q0, Ants choose to visit the node with the largest transition probability, otherwise randomly choose a node that has not been visited yet, considering that the different stages of the algorithm iteration have different characteristics, The change formula is shown in formula.
2) Pheromone update rules
After each iteration, the pheromone content on the path must be updated once. The pheromone update rule on the ant line in the basic ant colony algorithm is shown in formula.
The above formula
expresses the pheromone increment on the path between node i and node j in the current cycle, and its expression is shown in formula.
Among them:
represents the pheromone content left by the ant k on the path between nodes during this iteration. The calculation formula is different according to different ant systems. This article selects the calculation formula commonly used in the ant-cycle system. The global pheromone update is shown in formula, and the local pheromone update formula is shown in formula.
The above formula Q represents the total amount of pheromone carried by each ant, and Lk represents the total path traversed by the ant k in the current iteration.
The main improvements in this article are as follows:
a) Improvement of pheromone update rules
Different from the basic ant colony algorithm, this article defines pheromone as a scalar, that is, pheromone has no directionality, and the improved pheromone update rule is shown in formula:
b) Improvement of pheromone volatilization factor
In the basic ant colony algorithm, the volatilization factor is generally set as a constant. According to the algorithm iteration law, the change formula of the pheromone volatilization factor
set in this paper is shown in formula:
3) Feasible solution construction rules
Consider that the multi-ant colony intelligent algorithm designed in this paper contains two types of sub-ant colonies with different solving strategies. The path produced by each ant in the child ant colony using the full traversal strategy is a feasible solution. However, the path generated by each ant in the child ant colony using the single-loop strategy is only a part of the feasible solution, and it needs to be spliced and constructed. Based on this, this article mainly focuses on the concatenation structure of the feasible solution of the algorithm under the single-loop strategy.
To construct each ant path using the single-loop strategy, the result of the construction must be one of the feasible solutions, overflow infeasible solutions, underfilled infeasible solutions, and mixed infeasible solutions. A feasible solution consists of multiple sub-loops that include all nodes and are mutually different except for the distribution center; an overflow non-feasible solution includes all nodes, but there are common nodes other than the distribution center between some sub-loops; The full non-feasible solution means that it does not include all nodes, and the sub-paths are different from each other except the distribution center; the mixed infeasible solution consists of multiple sub-paths that are neither completely different from each other, nor do they include all the nodes.
4) Feasible solution update rule
In order to avoid the algorithm falling into the local optimum, after each iteration, the 2-opt local search method is used to update and optimize the feasible solution of the current iteration. The main idea of the 2-opt method is: randomly select any two nodes in the path, exchange the positions of the client nodes in the path according to certain rules, compare the length of the path before and after the exchange, and update the feasible solution path until all the client nodes have been exchanged and judged. For example, a feasible solution route is: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 1, select node 3 and 7 for 2-opt exchange, and add the path before node 3 unchanged to the new path, The path between nodes 3 to 7 is added to the new path after being flipped, and the path after node 7 is added to the new path unchanged. Then the new path is: 1 → 2 → 7 → 6 → 5 → 4 → 3 → 8 → 1, compare the length of the new path with the original path, and update the feasible solution.
5) Improved ant colony algorithm steps
The steps of using the improved ant colony algorithm to solve the SDVRPTW problem are as follows:
Step 1: Initialize each parameter. Set the initial number of iterations NC = 1, maximum number of iterations NCmax,
,
and
, Number of ants l, Pheromones Q,
,
, Initially set the pheromone concentration on each path to 1.
Step 2: Divide the ants into two groups A and B, the number of ants in group A is l/e, then the number of ants in group B is 1 - l/e. The A group of ants adopts a full traversal strategy, and the B group of ants adopts a single loop strategy. In each group, the ants are initialized to each garbage transfer station.
Step 3: For the ants starting from the garbage transfer station j, store the node of the garbage transfer station in the current solution set, and set the saving distance when starting from the garbage transfer station to 1. Calculate according to the transition probability formula j and get the next node j’ that the ant k will transfer from the garbage transfer station node, and place it in the current solution set and taboo table.
Step 4: (Group A) Determine whether the ant meets the load and time window constraints. If the constraints are not met, go to step 3; if the constraints are met, continue to choose to visit the next node and add the node to the table. If all the remaining residential area nodes are If it fails the inspection, the ant returns to an actual garbage transfer station according to the mileage saving method, clears the load, records the time, and continues the current step to verify whether the ant meets the requirements for continuing service. If it meets the requirements, select the previous garbage transfer station and place it in the current solution. Concentrate, continue to check whether the ants have traversed all the residential area nodes, if traversed, and go to Step 5. (Group B) determine whether the ants meet the load and time window constraints or traverse all nodes. If the next node cannot be accessed, add the current node to the table and go to Step 5. If the set loading rate is not reached, then Add the node to the taboo table, update it, and skip to Step 3; if all nodes are traversed, skip to Step 5; otherwise, add the node to the table and skip to Step 3.
Step 5: Determine whether the ant k returns to a garbage transfer station in the end. If it does not return to the garbage transfer station, add the node j’ to the Tabu table (group A) or Tabu_each table (group B), and go to Step 6, otherwise go directly to Step 6.
Step 6: Judge whether all the ants have constructed their solutions. If they are all constructed, construct feasible solutions for the solutions of group B, and add the constructed feasible solutions to the Tabu table; otherwise, go to Step 3.
Step 7: Perform pheromone update, update the Tau table, and get the best solution for the current iteration times.
Step 8: The 2-opt algorithm is used to locally optimize the best solution obtained under the current iteration number, and the related data table is cleared.
Step 9: Judge whether the NC exceeds the maximum number NCmax of iterations, if NC > NCmax, the algorithm is terminated, the optimal path and the optimal path length of the problem are output. Otherwise, NC = NC + 1, skip to Step 2.
5. Case Analysis
5.1. Algorithm Applicability Description
According to the design of the improved ant colony algorithm in the previous article, the improved ant colony algorithm proposed in this paper has certain advantages in solving TSP and VRP types of problems, but because the standard ant colony algorithm cannot be directly used to solve the multi-distribution center location problem in this paper. For this reason, this paper first scheme obtained using genetic algorithm to select the location of the distribution center, and then uses the improved ant colony algorithm to solve the distribution plan, so that not only can the problem studied in this paper be directly solved, but also the solution performance is better and the convergence speed is faster. The specific measures are: 1) Change the setting method of the taboo table, and change the way that each ant has a taboo table alone to all ants share a taboo table, so as to ensure that the sub-path of all ants is a closed loop, which eventually becomes a feasible solution to the problem; 2) The pheromone update method is modified, and the pheromone on the path is updated by adaptively adjusting the pheromone.
1) The genetic algorithm determines the location plan and the corresponding service level
2) According to the location plan determined by the genetic algorithm, the improved ant colony algorithm is used to determine the distribution plan.
The improved ant colony algorithm is used to perform J-TSP optimization based on the above information. After the optimization is completed, the distribution volume to each customer is calculated, and then the total distribution volume, total area, total cost and total revenue of the distribution center can be obtained, and feedback to Genetic algorithm. The program is run several times until the target value stabilizes, at which point the evaluation of the site selection plan for multiple distribution centers with competition ends. Since the location selection problem of multiple distribution centers studied in this paper takes the smallest cost, the shortest distance, and the farthest away from the waste treatment center as the objective function, the target values of multiple location options are compared, and representative target solutions are displayed.
The steps of applying the improved algorithm to the location selection problem of multi-waste transfer stations in this article are as follows:
Step 1: Scheme obtained using genetic algorithm;
Step 2: Use the improved ant colony algorithm to solve the distribution plan; initialize the key parameters;
Step 3: Clear the ant’s shared search taboo list tabu;
Step 4: Place the ants in the genetic algorithm to get the location of each garbage transfer station, and update these garbage transfer stations into the shared taboo table;
Step 5: The ants search for the next city according to the transition probability, and finally all the ants get their own closed-loop sub-path;
Step 6: Record the optimal solution of this iteration and the corresponding optimal service plan;
Step 7: When the optimal solution falls into the local optimal state, adjust the pheromone increment adaptively according to the design formula, and continue the search;
Step 8: When the number of cycles is reached to Nmax, end the search, otherwise return to Step 1;
Step 9: Output the most optimal location plan and service plan.
5.2. Simulation Experiment
Assume that there are 30 garbage collection points, 10 candidate garbage transfer stations, and 5 candidate treatment plants. The service life of the transfer station and treatment plant is T = 20 years. The location coordinates and population numbers of residential areas are shown in Table 1, the location coordinates, fixed construction costs and capacity of the to-be-selected transfer stations are shown in Table 2, and the location coordinates and fixed construction costs of the to-be-selected treatment plants are shown in Table 3. According to statistics from the World Bank, Chinese per capita daily waste production in 2020 is r = 1.l kg, and unit transportation cost β = 1 yuan is set to try to determine the optimal construction site and route optimization plan.
The numerical experiment has two main purposes: 1) To verify the effectiveness of encoding, decoding and hybridization algorithms; 2) To verify the effectiveness of the model.
Table 1. The coordinates of neighborhood and residential population.
Table 2. The location coordinates of transit station and fixed costs and its capacity.
Table 3. The coordinates of treatment plant and its fixed costs.
This article uses matlabR2016a to write the solution program, and the parameters are set as follows: pop = 100,
,
,
,
. The evolutionary algebra is 200. All experiments are run on a computer with Inter(R)Core(TM)i5-3230M CPU, 2.60 GHz frequency, and Windows7 operating system. The experiment took about 310 s. Finally, three representative non-dominated solutions were selected, and three optimal station construction and allocation plans were obtained after sorting out (the number outside the brackets represents the number of the selected transfer station, the number in the brackets (Indicates the number of the residential area it serves).
Option 1: 3, 4, 5, 6, 7. The processing center numbered 1 is selected.
,
,
.
Option 2: 1, 3, 4, 5, 7. The processing center numbered 3 is selected.
,
,
.
Option 3: 1, 3, 5, 7, 9. The processing center numbered 5 is selected.
,
,
.
According to the above analysis, the case is solved, the specific implementation steps of the algorithm are shown in the previous section, and the parameters and case data are as described above. Here, use MatlabR2016a as the programming tool and the operating system to solve the above problems on a computer with Windows 7 Ultimate Edition.
The experiment took about 440 s. Finally, three representative non-dominated solutions were selected. After sorting, three optimal station construction and allocation plans were obtained (the number outside the brackets represents the number of the selected transfer station to be built, and the number in the brackets The number indicates the number of the residential area it serves).
Option 1: 3 (3, 4, 5, 6, 7), 4 (7, 10, 11, 21, 22, 23, 24), 5 (13, 14, 15, 16, 17, 18, 19, 20), 6 (8, 28, 29, 30), 7 (9, 12, 28, 29, 30). The processing center numbered 1 is selected.
,
.
Option 2: 1 (13, 16, 8, 28, 29, 30), 3 (5, 4, 6, 3, 1, 2), 4 (10, 7, 11, 21, 22, 23, 24), 5 (20, 18, 15, 17, 19, 14), 7 (9, 25, 26, 27, 12). The processing center numbered 3 is selected.
,
.
Option 3: 1 (13, 16, 8, 28, 29, 30, 10, 7, 11), 3 (5, 4, 6, 3, 1, 2), 5 (20, 18, 15, 17, 19, 14), 7 (9, 25, 26, 27, 12), 9 (21, 22, 23, 24). The processing center numbered 5 is selected.
,
.
6. Conclusion
Adjacent avoidance facilities such as garbage transfer stations play an important role in urban life. The location problem is not only a research issue in the field of logistics systems, but also closely related to the field of social and people’s livelihood. This article starts from a review of the location of municipal solid waste transfer station, and uses genetic algorithm and improved ant colony algorithm to study it, aiming to provide some references for the location of such facilities. As an international student from Jordan, this article mainly completed the following tasks:
1) Analyze the site selection and route optimization model of the urban domestic waste transfer network. First of all, the definition and characteristics of the two-layer model are introduced, and combined with the research content of the urban domestic waste transfer network studied in this paper, the goal of the model to be established is expounded. Since the problem of site selection and route optimization has obvious hierarchical division, it is very effective to use a two-layer model to solve the problem of site selection and route optimization of urban domestic waste transfer network.
2) With the acceleration of the urbanization process and the continuous expansion of the city scale, the amount of garbage generated and the distance of garbage transportation will inevitably increase greatly. The construction of garbage transfer stations is conducive to reducing the total cost of urban garbage collection and transportation system. This chapter focuses on solving the upper-level model. In the model design process, not only the influence of economic factors, but also the influence of the garbage disposal center on the surrounding environment is considered, so it has more practical significance. In the selection of the solution method, genetic algorithm is selected to solve the problem, which can better solve the upper model.
3) Based on the solution of genetic algorithm, an improved ant colony algorithm is further designed. First, the mathematical model corresponding to the location of garbage transfer station is clarified; second, the traditional single-attribute ant colony algorithm is improved by improving the solution strategy to a multi-ant colony algorithm that combines a full traversal solution strategy and a single-loop solution strategy; finally based on numerical simulation experiments verify the superiority of the improved algorithm in solving this problem.
The construction of the site selection model for the domestic waste transfer station needs to consider many factors from all sides, and also involves logistics theory, environmental systems engineering, operations research theory, computer science and other disciplines, which also causes the location of the waste transfer station difficulty. Due to time constraints and other reasons, there are still many deficiencies in the research content of this article, mainly as follows:
1) In the example verified in this paper, only one garbage treatment center is selected to process garbage, and the situation of multiple garbage treatment centers for garbage treatment is not considered; only the construction cost of garbage treatment center, garbage transfer station, environmental compensation and environmental compensation are considered in the cost composition. The transportation cost ignores the cost of labor, vehicles, equipment, etc. In future research, the cost structure and location network can be enriched.
2) The data collection of the examples in this article is difficult to express with specific figures, and the analysis of some factors is not comprehensive enough. In future research, the index data can be further refined to improve the accuracy of the calculation model.
3) This article verifies through examples that the improved ant colony algorithm fused with genetic algorithm is superior to traditional genetic algorithm in search quality, and can be applied to the location problem of multiple distribution centers, but it cannot prove that the improved ant colony algorithm can solve the problem of multiple distribution centers. The best way to select the location of the distribution center still needs a long period of research and analysis.