# Research on the Cleaning Method of Unmanned Sweeper Based on Target Distribution Situation Analysis
## 3 Proposed Methodology
### Optimal Sweeping Path Planning Based on Simulated Annealing Algorithm
#### 3.2.3 Solutions for Multiple Convex Hull Set  
Finally, a simulated annealing-based TSP-CPP scavenging path accuracy method is executed.  
The TSP problem is an NP-hard problem in combinatorial optimization, where the difficulty lies in the fact that as the number of objectives increases, so does the amount of data to be processed. For this task, the problem consists of solving the shortest path to visit each area to be cleaned once, given a series of areas to be cleaned and the distance between the areas. Specifically, this problem is a symmetric TSP problem, i.e., the distances between two regions to be cleaned are equal. We propose to use the simulated annealing algorithm to solve the TSP-CPP problem.  
SA is a stochastic optimization algorithm based on the Monte-Carlo iterative solution strategy. The algorithmic optimization is carried out by continuously rearranging the current solution internally and gradually arranging it into the solution that achieves the minimum value of the objective function. The process of continuously optimizing the solution needs to remove the limitations of the greedy algorithm and can have a certain probability of jumping out of the local optimum to reach the global optimum. The exact computation progress is described in Algorithm 3.  
```
Input: City location \(Y=(y_{1},y_{2},\ldots,y_{m})\);  Current path \(i\);  Next path \(i+1\);  Cooling rate \(q\);  iteration \(c\);  Initial temperature of the system \(T_{0}\);  Lower limit of temperature \(T_{min}\); Output: output \(P,L\)
1\(P(i)=random(m)\); \(L(p(i))=pathlength(P(i))\); while\((T_{0}>T_{min})\) Generate a new path \(i=i+1\)do
2 if\(L(p(i+1))<L(p(i+1))\)then
3 Accept \(P(i+1)\) as optimal route;
4 Accept \(L(p(i+1))\) as minimum distance;
5
6 else
7\(T_{0}=q\times T_{0}\)
8
9 end while
10
11 end while Return\(P,L\)
```  
**Algorithm 3**SA \((Y,i,q,c,T_{0},T_{min})\).  
Therefore, attention should be paid to the connection of local and global coverage paths to address the integrated TSP-CPP, including the full coverage paths in each ROI (region of interest), the access order within the area to be cleaned, and the entrance/exit locations.  
The city location data are the entrance and exit locations in the area to be cleaned, and for the large area to be cleaned as described in the previous section, the entrance and exit locations are at most 4 groups. The algorithm will calculate the travel cost for each of these 4 city distributions.  
Set the initial temperature \(T_{0}\) and randomly select a traversal path \(P(i)\) as the initial path and calculate its length \(L(P(i))\); then, randomly generate a new traversal path \(P(i+1)\) and calculate its length \(L(P(i+1))\). If \(L(P(i+1))<L(P(i))\), then receive \(P(i+1)\) as the new path; otherwise, receive \(P(i)\) with the probability of simulated annealing, and then cool down the temperature. The above steps are repeated until the temperature reaches the minimum value \(T_{min}\).  
There are 3 main methods for generating new traversal paths:  
1. Randomly select 2 nodes and swap the order of these 2 nodes in the path.
2. Randomly select 2 nodes and reverse the order of the nodes between these 2 nodes in the path.
3. Randomly select 3 nodes \(m,n,k\), and then shift the nodes between nodes m and n to behind node \(k\).  
The higher the number of iterations, the more accurate the result will be; however, too many iterations will require too long a calculation time, so the number of iterations needs to be chosen appropriately.  
In path planning, the algorithm will compute the coverage of the Convex Hull set in real time and enter the next region when the target sweep is detected without turning back, avoiding the problem of the SA having to go back to the starting point.