# Multiobjective Multidepot Capacitated Arc Routing Optimization Based on Hybrid Algorithm

Authors: Liang Wu
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

The multidepot capacitated arc routing problem (CARP) is investigated with the hybrid optimization algorithm of the Dijkstra algorithm and genetic algorithm. The complex multidepot CARP is transformed into multiple single depot CARP by systematic clustering analysis. After completing the system clustering, the Dijkstra algorithm is used to adjust the boundary arc locally and merge it to a reasonable depot, while in the genetic algorithm, the structure of the chromosome is reset to use the path as the way of real coding, and the elite selection is used to decode to obtain the optimal path optimization scheme. Finally, Lanzhou road network data as experimental data, through Matlab to achieve the practicability of the algorithm in sprinkler applications. The results show that the improved genetic algorithm can successfully solve the multi-segment CARP with a certain road network scale, ensuring the correctness and feasibility of the algorithm. In addition, the efficiency of the algorithm in the later iteration is basically controlled at about 0.5 seconds, indicating that the efficiency of the algorithm is worth identifying.


---

## Body

## 1. Introduction

With the rapid advancement of computer technology, intelligent computing has become increasingly widely employed in various areas, while the problem of vehicle path optimization is one of the best examples. In real life, the driving route plan of the work vehicle usually depends on the experience of the staff, which will undoubtedly increase driving costs and reduce work efficiency. The research topic of this study is to apply artificial intelligence algorithms to vehicle operation path planning, which is one of the important contents of intelligent calculation methods to solve practical problems. The capacitated arc routing problem (CARP), originally proposed by Golden and Wong [1] in 1981, is a well-known combinatorial problem. The current research can be roughly divided into two categories: one is the vehicle routing problem (VRP) with the point of service, and the most common application is the point path problem. The other is an arc routing problem (ARP) with a path as the service object, which can be defined as a connected graph where several edges require a type of service, a point is used as a depot. Each side must be serviced by a car and the service needs to be completed at one time. All edges are allowed to be passed any number of times. Each vehicle departs from the depot and returns only after the service is completed. The total service demand on the route passed does not exceed the capacity of the vehicle [2].At present, domestic and overseas scholars have investigated the CARP widely. For small-scale ARP, an exact algorithm can be used to solve the problem, but for large-scale ARP, heuristic algorithms are required to obtain approximate solutions, such as taboo search algorithm [3], large-scale greedy algorithm [4], variable neighborhood search [5, 6], multi-population cooperative coevolutionary algorithm (MPCCA) [7], and improved ant colony algorithm [8]. In this regard, there are a variety of practical applications, such as urban garbage recycling [9], road maintenance deicing and salting in winter [10], and electricity meter [11]. Tirkolaee et al. [9] took the driver’s and occupant’s working hours into consideration to make the scheduling of the service more reasonable. Yang et al. [12, 13] developed an empirical model to estimate the standard deviation, quantile, and BTI of optimal TSP trips. Genetic algorithm is used to find the shortest paths randomly generated to connect N customers in a specific service region through experiments. To be more realistic, Tagmouti et al. [14] converted the arc routing problem into a vehicle routing problem with the point and used the variable domain search descent algorithm VND to move the neighborhood arc. The arc path problem was solved by arc crossover and arc resection transformation, and the time window can be considered to solve the problem of dynamic change according to time and weather during driving. However, it is not suitable to consider the time only during the time window. The traffic delay caused by the traffic signal control and traffic conditions should be taken into account moderately because the traffic situations at different times of the day cannot be estimated accurately [15–21].When solving large-scale path problems, Willemse and Joubert [22] combined the greedy algorithm with existing local search operations and optimized the acceleration mechanisms of greedy compound independent moves and static move descriptors to solve the problem more efficiently. The open CARP is an extension of the general CARP [23, 24]. It does not require a path to form a loop but limits the vehicle’s capacity and distance traveled, and minimizes research costs without exceeding these limits. For the multiobjective CARP, Shang et al. [25] proposed an extended search (ED-MAENS) method to deal with MO-CARP, using weights to decompose it into a single-objective problem. To ensure the rationality of multiple objective solutions, the priority of the scheme is proposed. However, there is still no guarantee that the distribution balance will be achieved when the weights are assigned, and the search range is wide. In this article, nondominant ranking and crowding are considered as the tradeoff between the two goals, which is better than assigning weights to the two goals, because the influence of two targets cannot be calibrated with a reasonable number [26–28]. For the drawbacks of weight distribution, Chen and Hao [29] proposed a two-stage method. In the first stage, the number of vehicles was minimized as the main target, while in the second stage, the minimum number of vehicles was taken as the upper limit to minimize the total cost. However, in the case of a small search space, it is easy to fall into a local optimal solution. Archetti, Lu, and Linfati and Escobar [30–32] investigated the specific demand and profit units on each edge of a series of edge sets. The profit on one edge is collected by at most one vehicle, and the vehicle can serve several edges. It was to determine a set of paths to meet the vehicle capacity limit and maximize profits within the maximum time limit. Zachariadis and Kiranoudis [33] explored the goal of maximizing profit and making the shortest travel time. When one of the two goals is close, the other target can be used as the preferred criterion. Dhein et al. [34] designed a genetic local search algorithm to maximize profit, and the construction path adopts nonlinear dispersion metrics to capture the routing characteristics found when the vehicle is driving in harsh environments, which is a new direction worth studying.For the research of the CARP, the predecessors have made many improvements and innovations in the algorithm, not only in the use of combinatorial optimization algorithms [35] but also on the premise of combined algorithms to improve search efficiency and search scale. However, for the development of modern society, sustainable development has become our primary goal, thus low carbon and emission reduction has become one of the issues emphasized [36–38]. Bruglieri et al. [39] proposed a green vehicle path problem with capacity alternative fuel stations (AFSs), based on the integer programming formula, two variants of the precise cut plane method were proposed to shorten the solution time. In addition, the time window was introduced to allow AFSs to be reserved. Pelletie et al. [40] discussed electric vehicles that are less polluting than conventional trucks. Robust optimization and large-scale neighborhood search are used to obtain the lowest cost route of energy consumption uncertainty. Erfan et al. [41] studied the difference in carbon emissions generated by different fuel types and concluded that the theoretical carbon emission factor coefficient was consistent with the actual experimental data. Different consumptions are generated in different vehicle loading states [42].Consequently, this article takes into account the carbon emissions from the sprinklers in operation, to achieve a more green service plan than the traditional way. Sprinkler operations are carried out when the sprinkler is working through an arc that requires service, as a result, the amount of water carried changes, hence the difference in carbon emissions will occur during driving. When the route is not required to be serviced, only the distance is accumulated, but the water carrying capacity does not change, which means that the load of the vehicle does not change. Therefore, traveling on such a path, the carbon emissions will remain the same until the curve to be serviced changes. It can be known that the carbon emissions generated under different load conditions are different. Thus, this article considers the shortest driving path and minimum carbon emissions as the two objectives of the study.This article is organized as follows. Section2 describes the background of the problem. Section 3 gives the mathematical model and symbol definition for this problem. Section 4 describes two heuristic algorithms to solve this problem, one is the single-objective two-stage method and the other is the multiobjective one-stage method. Section 5 proposes the algorithm-specific algorithm flow chart and algorithm steps. Section 6 presents the specific solution results obtained from the examples. Finally, conclusions and further research directions are summarized.


## 2. Problem Description

The objective of this article is to optimize the CARP path by minimizing the distance and carbon emissions of sprinklers. As the actual road network map increases, the service demand for the road will also increase, so the research object of this article belongs to the multidepot multiobjective CARP. The problem is described as follows: road topologyGV,E, where V=v1,v2,…,vn represents the set of n vertices in the graph. The arc set E=e1,e2,…em indicates that there are m directed arcs in the graph. The m arc contains ε service arcs and m−ε non-service arcs. The length of arc ei is Lei. There is a required value Nei=Lei×ρ for any service arc ei∈E. ρ is the demand factor (the specific value is determined by the actual situation), and there is no demand value for the non-service arcs.


## 3. Mathematical Model

### 3.1. Symbol Description

The specific meanings of some symbols involved in the article are described in Table1.Table 1
Symbol description.
SymbolDefinitionGConnected graphGV,EVSet of all nodes in the graph,V=v1,v2,…,vnEThe set of arc paths in a graphεNumber of service arcs in the figurekThere are currently a total ofk service arcsρSprinkler demand coefficientLeiLength of arc patheiσiDepoti, i=1,2,…iQThe carrying capacity of each carQ0The weight of each carQ1Current load of the vehiclefFuel consumption rate (FCR)xWeight of vehicle load (in tons)dijThe distance between nodei and node j in road network graphwijLoad from nodei to node j in road network graphμfuelijFuel consumption from nodei to node j in road network diagramCco2Carbon emissionsCfuelFuel consumptionFFuel conversion factor, gasoline vehicleF=2.30, diesel F=2.63TiPathiτiService arc setrBoundary arc setγJudging the critical threshold of boundary arcWCollection of nodes for all service arcs


### 3.2. Problem Hypothesis

It is stipulated by the Environmental protection department that the sprinkler operation should be carried out according to different weather conditions and road conditions. In this article, the weather is clear and the road condition is good.Assumption 1.
(1)
The sprinkler vehicle is a model with the same water carrying capacity.(2)
Each depot has a sufficient number of vehicles in multiple depots.(3)
All sprinkler vehicles travel at a uniform speed and are less than 30 km.(4)
When the sprinkler vehicle is fully loaded, it starts from the depot and returns to the original depot after the end of the service.(5)
For any service arc, only one sprinkler serves, and only once.(6)
When the sprinkler load meets the amount of sprinkler needed for the next arc path, the path is served; if the water load is less than the demand, it cannot meet the demand of the path and return to the original starting depot.


### 3.3. Mathematical Modeling

#### 3.3.1. Fuel Consumption

The regression equation of fuel consumption rate (FCR) calculated based on statistical data is(1)f=0.00556x+0.254,x∈0,22.4.The FCR under the current load is(2)μQ1=μ0+ε∗−ε0QQ1.The fuel consumption between nodei and node j is(3)μfuelij=μwijdij.


#### 3.3.2. Building Model

Objective function:(1)
The smallest total distance traveled by a vehicle is(4)minD=∑i=1kdistTi.(2)
The smallest carbon emissions of vehicles are(5)minCco2=F∑i∈V∑j∈Vμ0+ε∗−ε0QwijcijPij.Constraints:(1)
Vehicle load capacity constraints. The model of the sprinkler vehicle is fixed, and there is an upper limit of water carrying capacity, so the sprinkler demand is less than the upper limit of the water capacity of the vehicle.(6)NTi=∑j=1nρLei≤Q1≤i≤N.(2)
Constraint on the number of services. Each service arc is only allowed to be served by one arc path and can only be served once.(7)Ti∩Tj=∅,i,j=1,2,…,n.(3)
0–1 variable state selection constraint.(8)Pij=0,1,∀i,j∈V.(4)
The total number of service arcs for all paths must not exceedε.(9)∑i=1kTi≤ε.(5)
Flow conservation at the node. In the process of sprinkler travel service, the number of entries on any node is equal to the number of times the sprinkler leaves the node.(10)∑i,j∈Vxjik=∑i,j∈Vxijk.(6)
The calculation function of the driving distance of pathi.(11)distTi=dσ,Ti,1+∑j=1n−1LTi,j+dTi,j,Ti,j+1+LTi,|n|+dTi,|n|,σ.


## 3.1. Symbol Description

The specific meanings of some symbols involved in the article are described in Table1.Table 1
Symbol description.
SymbolDefinitionGConnected graphGV,EVSet of all nodes in the graph,V=v1,v2,…,vnEThe set of arc paths in a graphεNumber of service arcs in the figurekThere are currently a total ofk service arcsρSprinkler demand coefficientLeiLength of arc patheiσiDepoti, i=1,2,…iQThe carrying capacity of each carQ0The weight of each carQ1Current load of the vehiclefFuel consumption rate (FCR)xWeight of vehicle load (in tons)dijThe distance between nodei and node j in road network graphwijLoad from nodei to node j in road network graphμfuelijFuel consumption from nodei to node j in road network diagramCco2Carbon emissionsCfuelFuel consumptionFFuel conversion factor, gasoline vehicleF=2.30, diesel F=2.63TiPathiτiService arc setrBoundary arc setγJudging the critical threshold of boundary arcWCollection of nodes for all service arcs


## 3.2. Problem Hypothesis

It is stipulated by the Environmental protection department that the sprinkler operation should be carried out according to different weather conditions and road conditions. In this article, the weather is clear and the road condition is good.Assumption 1.
(1)
The sprinkler vehicle is a model with the same water carrying capacity.(2)
Each depot has a sufficient number of vehicles in multiple depots.(3)
All sprinkler vehicles travel at a uniform speed and are less than 30 km.(4)
When the sprinkler vehicle is fully loaded, it starts from the depot and returns to the original depot after the end of the service.(5)
For any service arc, only one sprinkler serves, and only once.(6)
When the sprinkler load meets the amount of sprinkler needed for the next arc path, the path is served; if the water load is less than the demand, it cannot meet the demand of the path and return to the original starting depot.


## 3.3. Mathematical Modeling

### 3.3.1. Fuel Consumption

The regression equation of fuel consumption rate (FCR) calculated based on statistical data is(1)f=0.00556x+0.254,x∈0,22.4.The FCR under the current load is(2)μQ1=μ0+ε∗−ε0QQ1.The fuel consumption between nodei and node j is(3)μfuelij=μwijdij.


### 3.3.2. Building Model

Objective function:(1)
The smallest total distance traveled by a vehicle is(4)minD=∑i=1kdistTi.(2)
The smallest carbon emissions of vehicles are(5)minCco2=F∑i∈V∑j∈Vμ0+ε∗−ε0QwijcijPij.Constraints:(1)
Vehicle load capacity constraints. The model of the sprinkler vehicle is fixed, and there is an upper limit of water carrying capacity, so the sprinkler demand is less than the upper limit of the water capacity of the vehicle.(6)NTi=∑j=1nρLei≤Q1≤i≤N.(2)
Constraint on the number of services. Each service arc is only allowed to be served by one arc path and can only be served once.(7)Ti∩Tj=∅,i,j=1,2,…,n.(3)
0–1 variable state selection constraint.(8)Pij=0,1,∀i,j∈V.(4)
The total number of service arcs for all paths must not exceedε.(9)∑i=1kTi≤ε.(5)
Flow conservation at the node. In the process of sprinkler travel service, the number of entries on any node is equal to the number of times the sprinkler leaves the node.(10)∑i,j∈Vxjik=∑i,j∈Vxijk.(6)
The calculation function of the driving distance of pathi.(11)distTi=dσ,Ti,1+∑j=1n−1LTi,j+dTi,j,Ti,j+1+LTi,|n|+dTi,|n|,σ.


## 3.3.1. Fuel Consumption

The regression equation of fuel consumption rate (FCR) calculated based on statistical data is(1)f=0.00556x+0.254,x∈0,22.4.The FCR under the current load is(2)μQ1=μ0+ε∗−ε0QQ1.The fuel consumption between nodei and node j is(3)μfuelij=μwijdij.


## 3.3.2. Building Model

Objective function:(1)
The smallest total distance traveled by a vehicle is(4)minD=∑i=1kdistTi.(2)
The smallest carbon emissions of vehicles are(5)minCco2=F∑i∈V∑j∈Vμ0+ε∗−ε0QwijcijPij.Constraints:(1)
Vehicle load capacity constraints. The model of the sprinkler vehicle is fixed, and there is an upper limit of water carrying capacity, so the sprinkler demand is less than the upper limit of the water capacity of the vehicle.(6)NTi=∑j=1nρLei≤Q1≤i≤N.(2)
Constraint on the number of services. Each service arc is only allowed to be served by one arc path and can only be served once.(7)Ti∩Tj=∅,i,j=1,2,…,n.(3)
0–1 variable state selection constraint.(8)Pij=0,1,∀i,j∈V.(4)
The total number of service arcs for all paths must not exceedε.(9)∑i=1kTi≤ε.(5)
Flow conservation at the node. In the process of sprinkler travel service, the number of entries on any node is equal to the number of times the sprinkler leaves the node.(10)∑i,j∈Vxjik=∑i,j∈Vxijk.(6)
The calculation function of the driving distance of pathi.(11)distTi=dσ,Ti,1+∑j=1n−1LTi,j+dTi,j,Ti,j+1+LTi,|n|+dTi,|n|,σ.


## 4. Algorithm Design

### 4.1. Chromosome Design

This article employs the chromosomal gene sequence priority coding scheme. The chromosome designed by this scheme consists of each chromosome on the side of the road network map. Each gene position represents an edge, and all service arcs form a complete chromosome. The length of the chromosome is adjusted according to the number of sides of the service that the actual problem requires. SupposeW=p is the number of arcs to be serviced, and each edge is numbered by a natural number. Then any random number from natural numbers 1 to p is a chromosome. The order in which gene values appear determines the priority of the service edges. Suppose all edges in the graph need to serve a total of 14 service arcs, so generating an arbitrary arrangement from 1 to 14 is a complete chromosome, such as(12)chrom=6159271012118131443.The specific node of the service side can be expressed in a matrix form as(13)W=41361575269478885910221096111153.Each of the numbers in the matrixW represents each node in Figure 1. The first row in the matrix W can be represented as the start point (end point) of the edge vivj, and the second row in the matrix W can be represented as the end point (starting point) of the edge vivj. The corresponding set of service edges can be expressed as(14)W=v4v5,v1v2,v3v6,v6v9,v1v4,v5v7,v7v8,v8v10,v8v9,v5v6,v9v11,v10v11,v2v5,v2v3.Figure 1
Simple road map.The resulting chromosomes differ in the order in which they are accessed. As a result, the number of vehicles arranged is different, and the fuel consumption of a single sprinkler is different. Each access route is encoded and decoded so that the shortest driving distance and the least fuel consumption of the vehicle among all routes can be searched.


### 4.2. Genetic Manipulation

#### 4.2.1. Fast Non-Dominated Sort

The NSGA-II algorithm is layered according to the dominance relationship between individuals before the execution of the selection operator, and the algorithm complexity can be reduced toOn. Before the selection operation is performed, the population is sorted according to the dominance and non-domination relationship between the individuals to achieve the layering effect. The detailed practices are as follows:(1)
By calculating the fitness function to compare the values of fitness, the dominance and non-domination between individualsi and j are obtained i≠j. If there is no fitness value of any individual j that is better than the fitness function value of individual i, then j is marked as the dominant individual.(2)
For each individuali, there are two parameters ni and si, where ni is the number of dissolving individuals who dominate the individual in the population. si is a collection of dissolving individuals governed by individual i.(3)
Find all individuals withni=0 in the population (all individuals in the population that are not dominated by other individuals) are classified to the set F1 of the leading edge 1.(4)
For the individualj governed by each individual i in the set F1, the number of solutions governing j is decremented by 1 and stored in the set H.(5)
UsingF1 as the first-level nondominated individual set and assigning the same nondominated order to the individuals in the set, and then continuing to repeat the above-mentioned hierarchical operation on the set H and assigning the corresponding nondominated order.(6)
Only the individuals who control the number of individuals to 0 are the current frontier until all individuals are classified.


#### 4.2.2. Congestion Calculation

The average distance between two points on either side of the point is calculated according to each objective function. The density of the surrounding individuals of a given individual in the population can be visually represented as an individual. As shown in Figure2, the congestion coefficient of the ith solution is the length of the surrounding cuboids (indicated by the dotted line). The specific calculation method is as follows:Step 1: Initialize the crowded distance of each individual with the number of noninferior layers wherei is located, di=0.Step 2: Each individuali is sorted on the corresponding target, and the crowded distance between different target individuals is solved by the formula objnext−objprevious/fki+1−fki−1, where obj is the subscript and fki is the kth target value after the ith individual is sorted on the kth target.Step 3: Set the distance between the first and last individuals after sorting to infinity,di=∞.Step 4: Sort each individual into different dimensional targets and select individuals with large crowded distances to enter the next generation.Figure 2
Congestion degree of the individuali.The calculation of congestion degree is an important part of ensuring the diversity of the population. The population is sorted based on the objective function so that the congestion degree of the boundary individual is infinity. After the nondominated sorting and congestion degree are computed, each individual in the population has a corresponding nondominated sorting number and congestion degree. Through the two indicators, the dominating and non-dominating relationship of any two individuals in the population can be distinguished, in this way, the constraint relationship between the two objectives can be balanced.


#### 4.2.3. Binary Bidding Selection

The tournament method selection strategy is referred to taking a certain number of individuals from the population each time and then selecting the best one to enter the offspring population. This operation is repeated until the new population size reaches the original size. The specific steps are as follows:(1)
Determine the number of individuals selected each time and determine the new population size.(2)
Two individualsi and j are randomly selected (each subject has the same probability of being selected) from the population to form a group each time i≠j.(3)
According to the dominance number and the degree of crowding of each individual, the individuals with the highest order of dominance are preferentially selected. Similarly, it is preferable to select an individual with a large degree of congestion, and finally, select an individual for which the conditional ranking is satisfied to enter the progeny population.(4)
Repeat step (2) and step (3) until the number of individuals reaches the population size to form a new generation population.


#### 4.2.4. Fragmented Crossover Operator

Randomly two parent chromosomesC1 and C2 are selected from the initial population of chromosomes using a binary bidding selection mechanism, and then random number n1≤n≤p−1 is generated to select the gene position as the entry point, and successive n genes are selected from the (n + 1)th gene position for exchange. The resulting gene fragments are inserted into the heads of C2 and C1, respectively, to obtain C1′ and C2′, and the duplicate numbers are deleted to achieve two progeny, for example, generating a random gene position n = 3, the crossover operation is(15)C1=2,4,1,3¯,6¯,5¯C2=4,1,6,5¯,3¯,2¯⇓C1′=5¯,3¯,2¯,2,4,1,3¯,6¯,5¯C2′=3¯,6¯,5¯,4,1,6,5¯,3¯,2¯⇓C1′=5,3,2,4,1,6C2′=3,6,5,4,1,2.


#### 4.2.5. Gene Swap Mutation Operator

A chromosome is selected from the parent chromosome population. The pair of genes that produce mutations is decided by the length of the chromosome, and the formula isd=ceilp/10 (Indicates rounding up). The variant gene position is determined by generating a random integer n1, and n2. In addition, the mutated gene position check mechanism is set to prevent the same random integer from being generated and the variation is invalid. This ensures the correct validity of the mutation operation. According to the gene position, a specific gene value is obtained in the chromosome, and the gene value is exchanged to obtain a new daughter chromosome. For example, the length of chromosome A is p = 9. The logarithm of the gene that produces the mutation is d = 1. The location of the variant gene is n1 = 5 and n2 = 8. Thus,(16)A=5,9,8,7,2¯,3,1,4¯,6⇒A′=5,9,8,7,4¯,3,1,2¯,6.


#### 4.2.6. Elite Selection Strategy

Elite selection is also called the optimal preservation strategy, meaning a certain number of individuals with the best fitness in the current group are saved in the temp array and do not participate in cross-variation operations. If the best individual in the preserved population is better than the new generation of individuals, then the next generation of the population is copied directly to replace the corresponding number of individuals with the worst fitness. If it is no better than a new generation of individuals, it will not be replaced. To prevent the optimal individual of the current group from being lost in the next generation, and then the genetic algorithm cannot converge to the global optimal solution. The common competition mechanism between the parent population and the offspring population is introduced so that the next generation population can inherit the superior genes of the ancestors.


### 4.3. Chromosome Decoding Operation

#### 4.3.1. Decoding Strategy

Decoding strategy for chromosomechrom=s1,s2,…,sp:(1)
The strategy of driving and serving. According to the chromosomal gene order priority coding scheme, if the first representative gene represents an edge ofsi, the corresponding node number is vivj, and the starting point is vi. Therefore, the sprinkler chooses the shortest path from the depot to vi. If it is through the served arc, it will travel in the order of the gene and will not serve it.(2)
The strategy of returning route without service. When the vehicle’s load capacity limit cannot serve the next arc, the service is terminated and returned to the depot on the shortest path, and the service will no longer be serviced to any side of the return path.(3)
Path segmentation strategy. A breakpoint is generated when a condition for ending the service of a vehicle is reached during the decoding process. This breakpoint splits a complete chromosome and after segmentation, the breakpoint is placed in the undecoded segment chromosome to continue decoding.Supposechrom=6159271012118131443 gets the split points r1 = 3 and r2 = 5 during the decoding process, to prevent confusion between the node and the service arc number, the starting point is set to a. Then the service paths of the three vehicles are described, respectively.Chromosome ①: a 6 1 aChromosome ②: a 5 9 aChromosome ③: a 2 7 10 12 11 8 13 14 4 3 aThe termination condition of the decoding algorithm:(1)
The water capacity of the sprinkler cannot meet the demand for the next service arc.(2)
All service arcs have been traversed.(3)
All genes of the chromosome are traversed during the decoding process.


#### 4.3.2. Decoding Specific Steps

Step 1: Randomly select the vehicle to depart from the depot. Select chromosomes from the population in order.Step 2: Select the gene value according to the priority, and get the service arcei.Step 3: Select the starting point of the service arcei from the nearest node of the depot as the route to determine the direction of travel.Step 4: According to the strategy of serving while driving, a 0–1 matrixP record is used for the serviced arc path during driving.Step 5: After the new vertex is reached at the end of the selected edge, calculate the shortest distance from the current node to the next service arc and record the corresponding arc path.Step 6: Consider the capacity of the vehicle. When the water capacity of the sprinkler can support the demand for a new service arc, turn to step 5 and update the remaining water capacity of the vehicle.Step 7: If the sprinkling demand of the new service arc exceeds the upper limit of the sprinkler, the vehicle returns to the starting depot. Record the location of the chromosome breakpoint gene.Step 8: Choose the next vehicle. Reload the gene at the breakpoint into the remaining undecoded gene of the strip and return to step 2.Step 9: If all service arcs are traversed, go to step 10.Step 10: Terminate the algorithm.


## 4.1. Chromosome Design

This article employs the chromosomal gene sequence priority coding scheme. The chromosome designed by this scheme consists of each chromosome on the side of the road network map. Each gene position represents an edge, and all service arcs form a complete chromosome. The length of the chromosome is adjusted according to the number of sides of the service that the actual problem requires. SupposeW=p is the number of arcs to be serviced, and each edge is numbered by a natural number. Then any random number from natural numbers 1 to p is a chromosome. The order in which gene values appear determines the priority of the service edges. Suppose all edges in the graph need to serve a total of 14 service arcs, so generating an arbitrary arrangement from 1 to 14 is a complete chromosome, such as(12)chrom=6159271012118131443.The specific node of the service side can be expressed in a matrix form as(13)W=41361575269478885910221096111153.Each of the numbers in the matrixW represents each node in Figure 1. The first row in the matrix W can be represented as the start point (end point) of the edge vivj, and the second row in the matrix W can be represented as the end point (starting point) of the edge vivj. The corresponding set of service edges can be expressed as(14)W=v4v5,v1v2,v3v6,v6v9,v1v4,v5v7,v7v8,v8v10,v8v9,v5v6,v9v11,v10v11,v2v5,v2v3.Figure 1
Simple road map.The resulting chromosomes differ in the order in which they are accessed. As a result, the number of vehicles arranged is different, and the fuel consumption of a single sprinkler is different. Each access route is encoded and decoded so that the shortest driving distance and the least fuel consumption of the vehicle among all routes can be searched.


## 4.2. Genetic Manipulation

### 4.2.1. Fast Non-Dominated Sort

The NSGA-II algorithm is layered according to the dominance relationship between individuals before the execution of the selection operator, and the algorithm complexity can be reduced toOn. Before the selection operation is performed, the population is sorted according to the dominance and non-domination relationship between the individuals to achieve the layering effect. The detailed practices are as follows:(1)
By calculating the fitness function to compare the values of fitness, the dominance and non-domination between individualsi and j are obtained i≠j. If there is no fitness value of any individual j that is better than the fitness function value of individual i, then j is marked as the dominant individual.(2)
For each individuali, there are two parameters ni and si, where ni is the number of dissolving individuals who dominate the individual in the population. si is a collection of dissolving individuals governed by individual i.(3)
Find all individuals withni=0 in the population (all individuals in the population that are not dominated by other individuals) are classified to the set F1 of the leading edge 1.(4)
For the individualj governed by each individual i in the set F1, the number of solutions governing j is decremented by 1 and stored in the set H.(5)
UsingF1 as the first-level nondominated individual set and assigning the same nondominated order to the individuals in the set, and then continuing to repeat the above-mentioned hierarchical operation on the set H and assigning the corresponding nondominated order.(6)
Only the individuals who control the number of individuals to 0 are the current frontier until all individuals are classified.


### 4.2.2. Congestion Calculation

The average distance between two points on either side of the point is calculated according to each objective function. The density of the surrounding individuals of a given individual in the population can be visually represented as an individual. As shown in Figure2, the congestion coefficient of the ith solution is the length of the surrounding cuboids (indicated by the dotted line). The specific calculation method is as follows:Step 1: Initialize the crowded distance of each individual with the number of noninferior layers wherei is located, di=0.Step 2: Each individuali is sorted on the corresponding target, and the crowded distance between different target individuals is solved by the formula objnext−objprevious/fki+1−fki−1, where obj is the subscript and fki is the kth target value after the ith individual is sorted on the kth target.Step 3: Set the distance between the first and last individuals after sorting to infinity,di=∞.Step 4: Sort each individual into different dimensional targets and select individuals with large crowded distances to enter the next generation.Figure 2
Congestion degree of the individuali.The calculation of congestion degree is an important part of ensuring the diversity of the population. The population is sorted based on the objective function so that the congestion degree of the boundary individual is infinity. After the nondominated sorting and congestion degree are computed, each individual in the population has a corresponding nondominated sorting number and congestion degree. Through the two indicators, the dominating and non-dominating relationship of any two individuals in the population can be distinguished, in this way, the constraint relationship between the two objectives can be balanced.


### 4.2.3. Binary Bidding Selection

The tournament method selection strategy is referred to taking a certain number of individuals from the population each time and then selecting the best one to enter the offspring population. This operation is repeated until the new population size reaches the original size. The specific steps are as follows:(1)
Determine the number of individuals selected each time and determine the new population size.(2)
Two individualsi and j are randomly selected (each subject has the same probability of being selected) from the population to form a group each time i≠j.(3)
According to the dominance number and the degree of crowding of each individual, the individuals with the highest order of dominance are preferentially selected. Similarly, it is preferable to select an individual with a large degree of congestion, and finally, select an individual for which the conditional ranking is satisfied to enter the progeny population.(4)
Repeat step (2) and step (3) until the number of individuals reaches the population size to form a new generation population.


### 4.2.4. Fragmented Crossover Operator

Randomly two parent chromosomesC1 and C2 are selected from the initial population of chromosomes using a binary bidding selection mechanism, and then random number n1≤n≤p−1 is generated to select the gene position as the entry point, and successive n genes are selected from the (n + 1)th gene position for exchange. The resulting gene fragments are inserted into the heads of C2 and C1, respectively, to obtain C1′ and C2′, and the duplicate numbers are deleted to achieve two progeny, for example, generating a random gene position n = 3, the crossover operation is(15)C1=2,4,1,3¯,6¯,5¯C2=4,1,6,5¯,3¯,2¯⇓C1′=5¯,3¯,2¯,2,4,1,3¯,6¯,5¯C2′=3¯,6¯,5¯,4,1,6,5¯,3¯,2¯⇓C1′=5,3,2,4,1,6C2′=3,6,5,4,1,2.


### 4.2.5. Gene Swap Mutation Operator

A chromosome is selected from the parent chromosome population. The pair of genes that produce mutations is decided by the length of the chromosome, and the formula isd=ceilp/10 (Indicates rounding up). The variant gene position is determined by generating a random integer n1, and n2. In addition, the mutated gene position check mechanism is set to prevent the same random integer from being generated and the variation is invalid. This ensures the correct validity of the mutation operation. According to the gene position, a specific gene value is obtained in the chromosome, and the gene value is exchanged to obtain a new daughter chromosome. For example, the length of chromosome A is p = 9. The logarithm of the gene that produces the mutation is d = 1. The location of the variant gene is n1 = 5 and n2 = 8. Thus,(16)A=5,9,8,7,2¯,3,1,4¯,6⇒A′=5,9,8,7,4¯,3,1,2¯,6.


### 4.2.6. Elite Selection Strategy

Elite selection is also called the optimal preservation strategy, meaning a certain number of individuals with the best fitness in the current group are saved in the temp array and do not participate in cross-variation operations. If the best individual in the preserved population is better than the new generation of individuals, then the next generation of the population is copied directly to replace the corresponding number of individuals with the worst fitness. If it is no better than a new generation of individuals, it will not be replaced. To prevent the optimal individual of the current group from being lost in the next generation, and then the genetic algorithm cannot converge to the global optimal solution. The common competition mechanism between the parent population and the offspring population is introduced so that the next generation population can inherit the superior genes of the ancestors.


## 4.2.1. Fast Non-Dominated Sort

The NSGA-II algorithm is layered according to the dominance relationship between individuals before the execution of the selection operator, and the algorithm complexity can be reduced toOn. Before the selection operation is performed, the population is sorted according to the dominance and non-domination relationship between the individuals to achieve the layering effect. The detailed practices are as follows:(1)
By calculating the fitness function to compare the values of fitness, the dominance and non-domination between individualsi and j are obtained i≠j. If there is no fitness value of any individual j that is better than the fitness function value of individual i, then j is marked as the dominant individual.(2)
For each individuali, there are two parameters ni and si, where ni is the number of dissolving individuals who dominate the individual in the population. si is a collection of dissolving individuals governed by individual i.(3)
Find all individuals withni=0 in the population (all individuals in the population that are not dominated by other individuals) are classified to the set F1 of the leading edge 1.(4)
For the individualj governed by each individual i in the set F1, the number of solutions governing j is decremented by 1 and stored in the set H.(5)
UsingF1 as the first-level nondominated individual set and assigning the same nondominated order to the individuals in the set, and then continuing to repeat the above-mentioned hierarchical operation on the set H and assigning the corresponding nondominated order.(6)
Only the individuals who control the number of individuals to 0 are the current frontier until all individuals are classified.


## 4.2.2. Congestion Calculation

The average distance between two points on either side of the point is calculated according to each objective function. The density of the surrounding individuals of a given individual in the population can be visually represented as an individual. As shown in Figure2, the congestion coefficient of the ith solution is the length of the surrounding cuboids (indicated by the dotted line). The specific calculation method is as follows:Step 1: Initialize the crowded distance of each individual with the number of noninferior layers wherei is located, di=0.Step 2: Each individuali is sorted on the corresponding target, and the crowded distance between different target individuals is solved by the formula objnext−objprevious/fki+1−fki−1, where obj is the subscript and fki is the kth target value after the ith individual is sorted on the kth target.Step 3: Set the distance between the first and last individuals after sorting to infinity,di=∞.Step 4: Sort each individual into different dimensional targets and select individuals with large crowded distances to enter the next generation.Figure 2
Congestion degree of the individuali.The calculation of congestion degree is an important part of ensuring the diversity of the population. The population is sorted based on the objective function so that the congestion degree of the boundary individual is infinity. After the nondominated sorting and congestion degree are computed, each individual in the population has a corresponding nondominated sorting number and congestion degree. Through the two indicators, the dominating and non-dominating relationship of any two individuals in the population can be distinguished, in this way, the constraint relationship between the two objectives can be balanced.


## 4.2.3. Binary Bidding Selection

The tournament method selection strategy is referred to taking a certain number of individuals from the population each time and then selecting the best one to enter the offspring population. This operation is repeated until the new population size reaches the original size. The specific steps are as follows:(1)
Determine the number of individuals selected each time and determine the new population size.(2)
Two individualsi and j are randomly selected (each subject has the same probability of being selected) from the population to form a group each time i≠j.(3)
According to the dominance number and the degree of crowding of each individual, the individuals with the highest order of dominance are preferentially selected. Similarly, it is preferable to select an individual with a large degree of congestion, and finally, select an individual for which the conditional ranking is satisfied to enter the progeny population.(4)
Repeat step (2) and step (3) until the number of individuals reaches the population size to form a new generation population.


## 4.2.4. Fragmented Crossover Operator

Randomly two parent chromosomesC1 and C2 are selected from the initial population of chromosomes using a binary bidding selection mechanism, and then random number n1≤n≤p−1 is generated to select the gene position as the entry point, and successive n genes are selected from the (n + 1)th gene position for exchange. The resulting gene fragments are inserted into the heads of C2 and C1, respectively, to obtain C1′ and C2′, and the duplicate numbers are deleted to achieve two progeny, for example, generating a random gene position n = 3, the crossover operation is(15)C1=2,4,1,3¯,6¯,5¯C2=4,1,6,5¯,3¯,2¯⇓C1′=5¯,3¯,2¯,2,4,1,3¯,6¯,5¯C2′=3¯,6¯,5¯,4,1,6,5¯,3¯,2¯⇓C1′=5,3,2,4,1,6C2′=3,6,5,4,1,2.


## 4.2.5. Gene Swap Mutation Operator

A chromosome is selected from the parent chromosome population. The pair of genes that produce mutations is decided by the length of the chromosome, and the formula isd=ceilp/10 (Indicates rounding up). The variant gene position is determined by generating a random integer n1, and n2. In addition, the mutated gene position check mechanism is set to prevent the same random integer from being generated and the variation is invalid. This ensures the correct validity of the mutation operation. According to the gene position, a specific gene value is obtained in the chromosome, and the gene value is exchanged to obtain a new daughter chromosome. For example, the length of chromosome A is p = 9. The logarithm of the gene that produces the mutation is d = 1. The location of the variant gene is n1 = 5 and n2 = 8. Thus,(16)A=5,9,8,7,2¯,3,1,4¯,6⇒A′=5,9,8,7,4¯,3,1,2¯,6.


## 4.2.6. Elite Selection Strategy

Elite selection is also called the optimal preservation strategy, meaning a certain number of individuals with the best fitness in the current group are saved in the temp array and do not participate in cross-variation operations. If the best individual in the preserved population is better than the new generation of individuals, then the next generation of the population is copied directly to replace the corresponding number of individuals with the worst fitness. If it is no better than a new generation of individuals, it will not be replaced. To prevent the optimal individual of the current group from being lost in the next generation, and then the genetic algorithm cannot converge to the global optimal solution. The common competition mechanism between the parent population and the offspring population is introduced so that the next generation population can inherit the superior genes of the ancestors.


## 4.3. Chromosome Decoding Operation

### 4.3.1. Decoding Strategy

Decoding strategy for chromosomechrom=s1,s2,…,sp:(1)
The strategy of driving and serving. According to the chromosomal gene order priority coding scheme, if the first representative gene represents an edge ofsi, the corresponding node number is vivj, and the starting point is vi. Therefore, the sprinkler chooses the shortest path from the depot to vi. If it is through the served arc, it will travel in the order of the gene and will not serve it.(2)
The strategy of returning route without service. When the vehicle’s load capacity limit cannot serve the next arc, the service is terminated and returned to the depot on the shortest path, and the service will no longer be serviced to any side of the return path.(3)
Path segmentation strategy. A breakpoint is generated when a condition for ending the service of a vehicle is reached during the decoding process. This breakpoint splits a complete chromosome and after segmentation, the breakpoint is placed in the undecoded segment chromosome to continue decoding.Supposechrom=6159271012118131443 gets the split points r1 = 3 and r2 = 5 during the decoding process, to prevent confusion between the node and the service arc number, the starting point is set to a. Then the service paths of the three vehicles are described, respectively.Chromosome ①: a 6 1 aChromosome ②: a 5 9 aChromosome ③: a 2 7 10 12 11 8 13 14 4 3 aThe termination condition of the decoding algorithm:(1)
The water capacity of the sprinkler cannot meet the demand for the next service arc.(2)
All service arcs have been traversed.(3)
All genes of the chromosome are traversed during the decoding process.


### 4.3.2. Decoding Specific Steps

Step 1: Randomly select the vehicle to depart from the depot. Select chromosomes from the population in order.Step 2: Select the gene value according to the priority, and get the service arcei.Step 3: Select the starting point of the service arcei from the nearest node of the depot as the route to determine the direction of travel.Step 4: According to the strategy of serving while driving, a 0–1 matrixP record is used for the serviced arc path during driving.Step 5: After the new vertex is reached at the end of the selected edge, calculate the shortest distance from the current node to the next service arc and record the corresponding arc path.Step 6: Consider the capacity of the vehicle. When the water capacity of the sprinkler can support the demand for a new service arc, turn to step 5 and update the remaining water capacity of the vehicle.Step 7: If the sprinkling demand of the new service arc exceeds the upper limit of the sprinkler, the vehicle returns to the starting depot. Record the location of the chromosome breakpoint gene.Step 8: Choose the next vehicle. Reload the gene at the breakpoint into the remaining undecoded gene of the strip and return to step 2.Step 9: If all service arcs are traversed, go to step 10.Step 10: Terminate the algorithm.


## 4.3.1. Decoding Strategy

Decoding strategy for chromosomechrom=s1,s2,…,sp:(1)
The strategy of driving and serving. According to the chromosomal gene order priority coding scheme, if the first representative gene represents an edge ofsi, the corresponding node number is vivj, and the starting point is vi. Therefore, the sprinkler chooses the shortest path from the depot to vi. If it is through the served arc, it will travel in the order of the gene and will not serve it.(2)
The strategy of returning route without service. When the vehicle’s load capacity limit cannot serve the next arc, the service is terminated and returned to the depot on the shortest path, and the service will no longer be serviced to any side of the return path.(3)
Path segmentation strategy. A breakpoint is generated when a condition for ending the service of a vehicle is reached during the decoding process. This breakpoint splits a complete chromosome and after segmentation, the breakpoint is placed in the undecoded segment chromosome to continue decoding.Supposechrom=6159271012118131443 gets the split points r1 = 3 and r2 = 5 during the decoding process, to prevent confusion between the node and the service arc number, the starting point is set to a. Then the service paths of the three vehicles are described, respectively.Chromosome ①: a 6 1 aChromosome ②: a 5 9 aChromosome ③: a 2 7 10 12 11 8 13 14 4 3 aThe termination condition of the decoding algorithm:(1)
The water capacity of the sprinkler cannot meet the demand for the next service arc.(2)
All service arcs have been traversed.(3)
All genes of the chromosome are traversed during the decoding process.


## 4.3.2. Decoding Specific Steps

Step 1: Randomly select the vehicle to depart from the depot. Select chromosomes from the population in order.Step 2: Select the gene value according to the priority, and get the service arcei.Step 3: Select the starting point of the service arcei from the nearest node of the depot as the route to determine the direction of travel.Step 4: According to the strategy of serving while driving, a 0–1 matrixP record is used for the serviced arc path during driving.Step 5: After the new vertex is reached at the end of the selected edge, calculate the shortest distance from the current node to the next service arc and record the corresponding arc path.Step 6: Consider the capacity of the vehicle. When the water capacity of the sprinkler can support the demand for a new service arc, turn to step 5 and update the remaining water capacity of the vehicle.Step 7: If the sprinkling demand of the new service arc exceeds the upper limit of the sprinkler, the vehicle returns to the starting depot. Record the location of the chromosome breakpoint gene.Step 8: Choose the next vehicle. Reload the gene at the breakpoint into the remaining undecoded gene of the strip and return to step 2.Step 9: If all service arcs are traversed, go to step 10.Step 10: Terminate the algorithm.


## 5. Algorithm Flow Chart

### 5.1. Single Objective Multidepot One-Stage Algorithm

Service arc setτi=em is obtained based on cluster analysis, but there is no rounding for the arc at the boundary of the area, i.e., there is a boundary arc r=e1,e2,…,en, 1≤n<m. Complete clustering needs to include all service arcs, so the boundary arc needs to be adjusted. For any boundary arc ei∈r, in terms of the shortest arc distance matrix, the shortest distance from the boundary arc to each depot σi can be obtained. Set a threshold γ0<γ≤1, let D=dei,σi/dei,σj. If D≤γ, the boundary arc is merged into the depot σi otherwise it is merged into σj.The specific algorithm flow chart is shown in Figure3.Figure 3
Flow chart of two-stage hybrid genetic algorithm.


### 5.2. Multi-Target Multidepot One-Stage Algorithm Process

Step 1: The randomly generated path chromosomes constitute the initial populationPt, t = 1. The population size is N.Step 2: Perform fast nondominated sorting onPt, and label the number of levels and calculate the congestion between individuals.Step 3: Perform binary competition, selection, and cross variation onPt.Step 4: Generate a child groupQt, merge the child Qt and the parent Pt to get Rt.Step 5: Perform fast nondominated sorting onR and calculate crowding between individuals.Step 6: Retain the topN priority individuals according to the elite strategy and update the population.Step 7: Determine the termination condition of the algorithm. If the upper limit of the number of iterations is reached, the corresponding pareto solution is output, otherwisePt=Pt+1, and go to step 2.The specific algorithm flow chart is shown in Figure4.Figure 4
NSGA-II algorithm flow chart.


## 5.1. Single Objective Multidepot One-Stage Algorithm

Service arc setτi=em is obtained based on cluster analysis, but there is no rounding for the arc at the boundary of the area, i.e., there is a boundary arc r=e1,e2,…,en, 1≤n<m. Complete clustering needs to include all service arcs, so the boundary arc needs to be adjusted. For any boundary arc ei∈r, in terms of the shortest arc distance matrix, the shortest distance from the boundary arc to each depot σi can be obtained. Set a threshold γ0<γ≤1, let D=dei,σi/dei,σj. If D≤γ, the boundary arc is merged into the depot σi otherwise it is merged into σj.The specific algorithm flow chart is shown in Figure3.Figure 3
Flow chart of two-stage hybrid genetic algorithm.


## 5.2. Multi-Target Multidepot One-Stage Algorithm Process

Step 1: The randomly generated path chromosomes constitute the initial populationPt, t = 1. The population size is N.Step 2: Perform fast nondominated sorting onPt, and label the number of levels and calculate the congestion between individuals.Step 3: Perform binary competition, selection, and cross variation onPt.Step 4: Generate a child groupQt, merge the child Qt and the parent Pt to get Rt.Step 5: Perform fast nondominated sorting onR and calculate crowding between individuals.Step 6: Retain the topN priority individuals according to the elite strategy and update the population.Step 7: Determine the termination condition of the algorithm. If the upper limit of the number of iterations is reached, the corresponding pareto solution is output, otherwisePt=Pt+1, and go to step 2.The specific algorithm flow chart is shown in Figure4.Figure 4
NSGA-II algorithm flow chart.


## 6. Example Analysis

The example data of this article come from a part of the road network map within a certain district in Lanzhou, based on the optimization of the sprinkler route of the sanitation department, whose task is to sprinkle water and reduce dust on the roads in this area. The road topology diagram is shown in Figure5, which includes a total of 49 nodes (represented by the number of circles in the diagram), and 74 service edges. Each edge has a distance value and a demand value, and the number of each edge is the distance of each edge. The value of demand is determined by the distance and demand factor. As a result of the larger road network, the setting up of a depot for the allocation of sprinkler tasks, the time cost, and the high cost of fuel consumption, the subregional contract system is adopted in this area. According to the clustering analysis, the road is divided into three regions, one, two, and three, corresponding to the red area, the yellow area, and the blue area, and several vehicles are sent out by the three depots to be responsible for the sprinkler operation. The three depots are located at node 3, node 32, and node 49, respectively. All sprinkler vehicles complete the service at the depot and return to the original depot. Parameter settings are given in Table 2.Figure 5
Road topology of a district in Lanzhou.Table 2
Parameter settings.
Parameter nameSettingsPopulation number50Number of iterations500Selection rate0.5Cross rate0.8Mutation rate0.2Depot3, 32, 49Sprinkler model5tDemand factor0.8


### 6.1. Single Objective Solution

The road network map is divided into three areas, and the sprinkler vehicles are all 5 tons, where “ = ” indicates that the section of the road is sprinkled, and “–” means that only the road does not sprinkle water. Only object one is considered here. The objective equation is equation (1).A detailed description of multiple depots is listed in Table3. Although the empty-loaded rate of vehicles in region 1 is only 22.9%, less than 3 tons of sprinkler water is required in this area, allowing vehicles to carry 2 tons of water back to the warehouse with more carbon emissions than empty vehicles returning to the parking lot. From the empty-loaded rate of traffic volume in the three areas, the area of region 2 is larger than that of the other two areas, and the corresponding empty-loaded rate has increased by 10%. The second vehicle in region 2 needs only 1.3304 tons of water, which is not only an increase in empty traffic but also produces more carbon emissions than other vehicles. If the road network becomes larger, the number of vehicles required in different areas will continue to increase, which will easily lead to an increase in the empty-loaded rate in each area. If the cross-zone operation is allowed, the remaining water load of the second vehicle in region 2 can fully meet the demand of region 3, thus directly reducing the travel of a sprinkler. As a result, it can be found that although the division of this operation can be very convenient to divide their own sprinkler tasks, it is easy to cause waste of excess resources and increase costs.Table 3
Detailed description of multiple depots.
AreaVehDriving pathSprinkling capacity (tons)Travel distance (km)Empty rate (%)I13 = 10 = 12 = 13 = 14 = 15 = 6 = 5 = 4 = 3–10 = 11 = 18 = 17–18 = 19 = 2 = 3–2 = 1 = 21 = 22–21 = 19–18 = 12–13–14 = 8 = 6–8 = 7 = 9 = 4 = 32.93844.76722.9II132 = 34 = 41 = 47–41 = 39 = 35 = 34–32 = 36 = 37 = 38 = 35–34–32–36 = 28 = 27 = 25 = 26 = 30 = 31 = 42 = 45 = 33 = 34–32–36–28 = 29 = 23–29 = 37–38 = 40 = 39–41–34–33 = 31–42 = 44 = 43 = 24 = 26 = 20 = 19–20–26–30 = 32–36 = 35–34–324.75368.92333.4232 = 30–31 = 43–24 = 22 = 20 = 17 = 16 = 23 = 15–23 = 16 = 27–25 = 321.33042.51333.8III149 = 48 = 45–48 = 47 = 46 = 40–46 = 491.79362.90822.9Sum10.81619.11123.4Taking the search solution in region 1 as an example, as shown in Figure6, the solution obtained is also relatively poor, and the downward trend of the optimization curve is steep at the beginning of the optimization process. Because the initial population is randomly generated and the initial fitness of the group is poor as a whole, thus the corresponding iteration time is also relatively long. With the increase of the number of evolutionary iterations in the process of evolution, continuous elite selection to leave the contemporary optimal solution can be found to gradually approach the global optimal solution, and the speed of solution begins to become stable. From 300 generations later, the volatility of the solution starts to be stable, as well as the optimization curve, and gradually converges to the optimal solution.Figure 6
Evolution diagram of optimal solution and iteration time diagram of region 1.


### 6.2. Multiobjective Solution

The initial population produced is shown in Figure7 when the population size is 150.Figure 7
Solution of the initial population.Figure8 shows the solution when the number of iterations is 100. Compared with the initial solution generated in Figure 7, the target values of both targets are refined, and the optimal value of f1 is reduced from 5.4×104 to 4.55×104. The optimal value of f2 is decreased from 37 to 22.25. Compared with the initial solution, the solution after 100 iterations reveals an obvious sense of hierarchy, and the closer to the optimal solution, the more obvious, which fully reflects the effect of nondominant ordering used in NSGA-II.Figure 8
Solution of 100 iterations.Figure9 gives the optimal Pareto solution set at the end of the final iteration. It can be intuitively seen that there are four optimal solutions in the first layer, but there are six optimal solutions in the actual solution process, whereas the difference is only due to the difference between chromosomes and the same target value, so it cannot be shown in the graph. Different chromosomes denote that there are also many different work schemes when the same target value is obtained. The two-stage heuristic algorithm decomposes the sprinkler path optimization problem into two optimization issues and then solves them in stages, which is easy to lose the real optimal solution, while the hybrid algorithm proposed here belongs to the one-stage method, in which the path optimization problem of multidepot sprinkler is always optimized as a whole.Figure 9
Pareto solution set.Table4 shows the specific target values for the Pareto solution corresponding to Figure 9. From the numerical value, it can be figured out that the length of the distance cannot directly decide the amount of carbon emissions.Table 4
Pareto solution target value.
Pareto solutionTravel distance (km)Carbon emission (kg)Fuel consumption (L)Solution 132.29422.488.55Solution 229.65223.038.76Solution 332.90322.158.42Solution 432.60322.358.50The order in which the service arc is served in the arc path is one of the influencing factors on carbon emissions, because the greater the load in each driving process, the greater the carbon emissions. If the service volume is mainly concentrated on the first half of the formal distance, in the case of an increase in the empty-loaded rate in the second half, the carbon emissions generated will be smaller. Therefore, in the application of sprinklers, it is reasonable to take carbon emissions into account and can better plan low-carbon routes and reduce vehicle pollution, to achieve the concept of sustainable development.


## 6.1. Single Objective Solution

The road network map is divided into three areas, and the sprinkler vehicles are all 5 tons, where “ = ” indicates that the section of the road is sprinkled, and “–” means that only the road does not sprinkle water. Only object one is considered here. The objective equation is equation (1).A detailed description of multiple depots is listed in Table3. Although the empty-loaded rate of vehicles in region 1 is only 22.9%, less than 3 tons of sprinkler water is required in this area, allowing vehicles to carry 2 tons of water back to the warehouse with more carbon emissions than empty vehicles returning to the parking lot. From the empty-loaded rate of traffic volume in the three areas, the area of region 2 is larger than that of the other two areas, and the corresponding empty-loaded rate has increased by 10%. The second vehicle in region 2 needs only 1.3304 tons of water, which is not only an increase in empty traffic but also produces more carbon emissions than other vehicles. If the road network becomes larger, the number of vehicles required in different areas will continue to increase, which will easily lead to an increase in the empty-loaded rate in each area. If the cross-zone operation is allowed, the remaining water load of the second vehicle in region 2 can fully meet the demand of region 3, thus directly reducing the travel of a sprinkler. As a result, it can be found that although the division of this operation can be very convenient to divide their own sprinkler tasks, it is easy to cause waste of excess resources and increase costs.Table 3
Detailed description of multiple depots.
AreaVehDriving pathSprinkling capacity (tons)Travel distance (km)Empty rate (%)I13 = 10 = 12 = 13 = 14 = 15 = 6 = 5 = 4 = 3–10 = 11 = 18 = 17–18 = 19 = 2 = 3–2 = 1 = 21 = 22–21 = 19–18 = 12–13–14 = 8 = 6–8 = 7 = 9 = 4 = 32.93844.76722.9II132 = 34 = 41 = 47–41 = 39 = 35 = 34–32 = 36 = 37 = 38 = 35–34–32–36 = 28 = 27 = 25 = 26 = 30 = 31 = 42 = 45 = 33 = 34–32–36–28 = 29 = 23–29 = 37–38 = 40 = 39–41–34–33 = 31–42 = 44 = 43 = 24 = 26 = 20 = 19–20–26–30 = 32–36 = 35–34–324.75368.92333.4232 = 30–31 = 43–24 = 22 = 20 = 17 = 16 = 23 = 15–23 = 16 = 27–25 = 321.33042.51333.8III149 = 48 = 45–48 = 47 = 46 = 40–46 = 491.79362.90822.9Sum10.81619.11123.4Taking the search solution in region 1 as an example, as shown in Figure6, the solution obtained is also relatively poor, and the downward trend of the optimization curve is steep at the beginning of the optimization process. Because the initial population is randomly generated and the initial fitness of the group is poor as a whole, thus the corresponding iteration time is also relatively long. With the increase of the number of evolutionary iterations in the process of evolution, continuous elite selection to leave the contemporary optimal solution can be found to gradually approach the global optimal solution, and the speed of solution begins to become stable. From 300 generations later, the volatility of the solution starts to be stable, as well as the optimization curve, and gradually converges to the optimal solution.Figure 6
Evolution diagram of optimal solution and iteration time diagram of region 1.


## 6.2. Multiobjective Solution

The initial population produced is shown in Figure7 when the population size is 150.Figure 7
Solution of the initial population.Figure8 shows the solution when the number of iterations is 100. Compared with the initial solution generated in Figure 7, the target values of both targets are refined, and the optimal value of f1 is reduced from 5.4×104 to 4.55×104. The optimal value of f2 is decreased from 37 to 22.25. Compared with the initial solution, the solution after 100 iterations reveals an obvious sense of hierarchy, and the closer to the optimal solution, the more obvious, which fully reflects the effect of nondominant ordering used in NSGA-II.Figure 8
Solution of 100 iterations.Figure9 gives the optimal Pareto solution set at the end of the final iteration. It can be intuitively seen that there are four optimal solutions in the first layer, but there are six optimal solutions in the actual solution process, whereas the difference is only due to the difference between chromosomes and the same target value, so it cannot be shown in the graph. Different chromosomes denote that there are also many different work schemes when the same target value is obtained. The two-stage heuristic algorithm decomposes the sprinkler path optimization problem into two optimization issues and then solves them in stages, which is easy to lose the real optimal solution, while the hybrid algorithm proposed here belongs to the one-stage method, in which the path optimization problem of multidepot sprinkler is always optimized as a whole.Figure 9
Pareto solution set.Table4 shows the specific target values for the Pareto solution corresponding to Figure 9. From the numerical value, it can be figured out that the length of the distance cannot directly decide the amount of carbon emissions.Table 4
Pareto solution target value.
Pareto solutionTravel distance (km)Carbon emission (kg)Fuel consumption (L)Solution 132.29422.488.55Solution 229.65223.038.76Solution 332.90322.158.42Solution 432.60322.358.50The order in which the service arc is served in the arc path is one of the influencing factors on carbon emissions, because the greater the load in each driving process, the greater the carbon emissions. If the service volume is mainly concentrated on the first half of the formal distance, in the case of an increase in the empty-loaded rate in the second half, the carbon emissions generated will be smaller. Therefore, in the application of sprinklers, it is reasonable to take carbon emissions into account and can better plan low-carbon routes and reduce vehicle pollution, to achieve the concept of sustainable development.


## 7. Conclusion

In this article, the multidepot CARP optimization is investigated with the hybrid optimization algorithm of Dijkstra algorithm and genetic algorithm. The complex multidepot CARP is transformed into a multiple single depot CARP by systematic clustering analysis. After completing the system clustering, the Dijkstra algorithm is used to adjust the boundary arc locally and merge it into a reasonable depot, while in the genetic algorithm, the structure of the chromosome is reset to use the path as the way of real coding, and the elite selection is used to decode to obtain the optimal path optimization scheme. Finally, the designed algorithm is applied to the actual sprinkler operation path optimization scheme, and the experimental results show that the improved genetic algorithm can successfully solve the multidepot CARP of a certain road network scale. Moreover, the efficiency of the algorithm in the later iteration is basically controlled at about 0.5 seconds, indicating that the efficiency of the algorithm is worthy of recognition. However, in the analysis of the results of the two-stage method, it is found that the increase in the number of vehicles with the expansion of the road network will lead to an increase in the empty driving rate, which will lead to the waste of resources and cause pollution problems. Therefore, the problem is transformed into a one-stage solution, and the partition strategy is no longer used. In this article, we considered that the driving path is as short as possible, the operation efficiency is improved, and the total carbon emission is minimized to reduce pollution, thus the hybrid algorithm of NSGA-II algorithm and Dijkstra algorithm is used to solve this problem. Taking the nondominant ranking and crowding degree as the tradeoff standard of the two objectives, this method performs better than allocating the weights of the two targets, because the influence of the two targets cannot be calibrated reasonably.In this study, although carbon emissions are taken into account, the water flow is sprinkled at a specific flow rate during the sprinkler operation. Therefore, the carbon emission in a service arc should be a real-time change as the amount of water decreases, which will be the direction of the next problem to be solved. In addition, due to the particularity of sprinkler operation, the working time required is also different from the general travel, so the time window factor is also worth studying.



---

*Source: 1846681-2022-06-17.xml*