CN-122015893-A - Unmanned sanitation vehicle path planning method and system based on improved NSGA-II

CN122015893ACN 122015893 ACN122015893 ACN 122015893ACN-122015893-A

Abstract

The invention relates to the technical field of vehicle path planning, and provides an unmanned sanitation vehicle path planning method and system based on improved NSGA-II, which realize the efficient acquisition of path cost by constructing task and road section mapping and node pair shortest distance matrix and combining greedy path simulation and NSGA-II optimization algorithm, A multi-objective optimization model with the minimum vehicle deployment quantity, the minimum system total energy consumption and the minimum uncovered task area ratio as cores is established, a K-Means clustering initialization strategy is introduced to accelerate convergence in a solving stage, a dynamic starting point is combined to determine a greedy path simulation with a dynamic cut-off mechanism, and multi-dimensional optimization is carried out by utilizing an improved NSGA-II algorithm on the premise of not depending on a fixed garage. Through the mechanism, the resource investment and the operation coverage rate of the unmanned sanitation vehicle can be cooperatively optimized, and the path planning efficiency and the solution feasibility are improved.

Inventors

WANG LINSHEN
WANG DIANYIN
JI NAN
CUI NA
PAN KUN
HAN QING

Assignees

济南大学

Dates

Publication Date: 20260512
Application Date: 20260212

Claims (10)

1. The unmanned sanitation vehicle path planning method based on the improved NSGA-II is characterized by comprising the following steps of: Acquiring operation tasks and operation vehicle information, performing discretization on road sections corresponding to the operation tasks, establishing mapping between the tasks and the road sections, calculating the shortest distance between the discretized road nodes, and constructing a full node pair shortest distance matrix; Constructing a multi-objective path planning model by taking the minimum number of environmental sanitation vehicles, the minimum total energy consumption of the system and the minimum area ratio of uncovered tasks as optimization targets; And combining greedy path simulation with an NSGA-II optimization algorithm to obtain an improved NSGA-II optimization algorithm, solving the constructed multi-objective optimization model according to the mapping relation between the tasks and the road sections and the shortest distance matrix of all nodes, and obtaining a path planning scheme for executing the tasks of the vehicle.
2. The improved NSGA-II based unmanned sanitation vehicle path planning method of claim 1, wherein: The method for establishing the mapping of the tasks and the road sections comprises the following steps: dividing a road into a plurality of road segments according to a set length, wherein two end points of each road segment are used as nodes; defining the segmented adjacent node pair as minimum task units, distributing a unique task number for each minimum task unit, and recording the corresponding global node numbers at two ends of the task section to form an endpoint-task mapping table.
3. The unmanned sanitation vehicle path planning method based on the improved NSGA-II as set forth in claim 1, wherein the process of constructing the full node pair shortest distance matrix comprises the following steps: Constructing an undirected edge set based on segmented adjacent node pairs Taking the side length as the geometric length between two nodes to obtain an undirected weighted adjacency matrix; and constructing a graph object based on the undirected weighted adjacency matrix, and calculating the shortest path length between all node pairs as a matrix element value to obtain a full node pair shortest distance matrix.
4. The unmanned sanitation vehicle path planning method based on the improved NSGA-II as set forth in claim 1, wherein the solving constraint conditions of the multi-objective optimization model comprise a running time constraint, a single-time endurance and dynamic charging constraint, a task allocation uniqueness constraint and a job path connectivity constraint, wherein the task allocation uniqueness constraint means that any task section is allocated by one vehicle at most, and an unallocated task section is allowed to exist.
5. The unmanned sanitation vehicle path planning method based on the improved NSGA-II according to claim 1, wherein the method for solving the constructed multi-objective optimization model to obtain the path planning scheme of the task execution of the vehicle comprises the following steps: Step 31, encoding a vehicle task group in a mode of fusing a delimiter by a task number, generating a chromosome in a mode of combining a spatial clustering heuristic mechanism and a random mechanism, and constructing an initial population; Step 32, analyzing the gene sequence in each chromosome, identifying the position of the demarcation sign, and dividing the chromosome into segments Sub-sequences, wherein each sub-sequence corresponds to a task road section list of a vehicle, and chromosomes are converted into task allocation of the vehicle as decoding results; step 33, dynamically determining initial deployment nodes of each vehicle according to the decoded result, performing greedy path simulation of dynamic truncation, and performing connection cost filling on the shortest distance matrix based on the pre-calculated full nodes to generate a vehicle path; Step 34, carrying out fitness calculation based on the multi-objective optimization model to obtain the number of vehicles, the total driving distance and the area occupation ratio of uncovered tasks aiming at obtaining the vehicle path corresponding to each chromosome, carrying out constraint verification based on constraint conditions of the multi-objective optimization model, and carrying out rapid non-dominant sorting and congestion calculation based on fitness calculation results on the individual qualified in the constraint verification; step 35, performing selection, crossover, mutation and environment selection to generate a new chromosome, and performing step 32 to perform the next iteration until the iteration stop condition is met, thereby obtaining the pareto solution set.
6. The unmanned sanitation truck path planning method based on the improved NSGA-II according to claim 1, wherein the vehicle task group is encoded by means of a task number fusion delimiter, and each chromosome is obtained by means of the following specific encoding method: A non-zero gene value is adopted to represent the road task number; Setting delimiters, dividing a task sequence into a plurality of vehicle task segments, performing spatial clustering on all tasks according to the central coordinates of the vehicle task segments by using a K-Means algorithm, generating task pre-groupings with spatial adjacency, encoding task segments belonging to the same class of clusters into task sequences of the same vehicle, and obtaining encoded chromosomes serving as first partial individuals; randomly disturbing the task sequence, randomly inserting delimiters, distributing the vehicle task segments to vehicles, generating second parts of individuals, and forming an initial population by the first parts of individuals and the second parts of individuals; the delimiter is inserted into the task sequence to generate or reconstruct a chromosome, and the delimiter insertion satisfies the following conditions: delimiters do not appear at the beginning of the sequence; The delimiter is discontinuous; Each vehicle mission segment is not empty; If the end of the chromosome is the delimiter after insertion, the end delimiter is removed, and the end of the output chromosome is ensured not to be the delimiter.
7. The unmanned sanitation vehicle path planning method based on the improved NSGA-II as set forth in claim 1, wherein the method for generating the vehicle path comprises the steps of dynamically determining initial deployment nodes of each vehicle according to the decoded result, performing greedy path simulation with dynamic interception, and performing connection cost filling on the shortest distance matrix based on the pre-calculated full nodes, and comprises the following steps: The method comprises the steps of taking the shortest total travel distance as a target for completing tasks of all task road sections, and determining one endpoint node of a first task road section as a starting point, namely an initial deployment node of each vehicle through a full-node pair shortest distance matrix; Performing greedy selection and dynamic cut-off, namely performing tasks from a determined starting point, taking the minimum connection distance as a target, iterating greedy selection to determine the next task until all tasks determine a vehicle path and supplementing connection cost; Or executing the crossover process to generate a new chromosome, specifically, removing delimiters in two parent individuals aiming at the parent individuals carrying out the crossover process, crossly combining task sequences, and inserting the delimiters according to the number proportion of vehicles in the original individual scheme to obtain a new candidate scheme; Or the mutation process includes task exchange mutation and demarcation Fu Bianyi: Task exchange mutation, namely randomly selecting two positions in all task gene positions of non-delimiters for an individual to be mutated and exchanging task numbers of the two positions to disturb task execution sequence; Demarcation Fu Bianyi a demarcation is inserted at random locations or an existing demarcation is randomly deleted to change the number of vehicles.
8. Unmanned sanitation car path planning system based on improvement NSGA-II, characterized by comprising: The preprocessing module is configured to acquire the operation task and the operation vehicle information, discretize the road section corresponding to the operation task, establish the mapping between the task and the road section, calculate the shortest distance between the discretized road nodes, and construct a full node pair shortest distance matrix; The model construction module is configured to construct a multi-objective path planning model by taking the minimum number of deployment of sanitation vehicles, the minimum total energy consumption of the system and the minimum uncovered task area occupation ratio as optimization targets; And combining the greedy path simulation with the NSGA-II optimization algorithm to obtain an improved NSGA-II optimization algorithm, solving the constructed multi-objective optimization model according to the mapping relation between the tasks and the road sections and the shortest distance matrix by the full nodes, and obtaining a path planning scheme for executing the tasks of the vehicle.
9. An electronic device comprising a memory and a processor and computer instructions stored on the memory and running on the processor, which when executed by the processor, perform the steps in the improved NSGA-II based unmanned sanitation vehicle path planning method of any of claims 1 to 7.
10. A computer readable storage medium storing computer instructions which, when executed by a processor, perform the steps in the improved NSGA-II based unmanned sanitation vehicle path planning method of any of claims 1 to 7.

Description

Unmanned sanitation vehicle path planning method and system based on improved NSGA-II Technical Field The invention relates to the technical field related to vehicle path planning, in particular to an unmanned sanitation vehicle path planning method and system based on an improved NSGA-II. Background The statements in this section merely provide background information related to the present disclosure and may not necessarily constitute prior art. With the rapid development of information technology, artificial intelligence and automatic driving technology, smart city construction is becoming an important means for improving city governance capability and operation efficiency. The unmanned sanitation vehicle comprises various municipal service vehicles which realize autonomous operation such as an unmanned sweeper, an unmanned sprinkler, an unmanned garbage collection and transportation vehicle and the like, and is used as a core component of an intelligent sanitation system, has the advantages of continuous operation, high efficiency, energy conservation, intelligent scheduling and the like, realizes test point application in a plurality of cities, and has the potential of well replacing the traditional manual operation mode. In a large-scale urban road network, the complexity and breadth of road sanitation tasks are obviously improved, and multiple factors such as operation time window, duration limit, non-uniform task distribution and the like are involved, so that scientific and efficient facility deployment and path scheduling strategy support are needed. Therefore, the system optimization research is carried out on the facility space deployment and the path planning of the unmanned sanitation vehicle under the condition of large-scale road network, and the system optimization research has obvious practical significance and urgent requirements. However, the prior art has various disadvantages in coping with the above problems. Firstly, the optimization target is single, and the resource scheduling rationality and the system energy consumption control cannot be considered. The partial optimization model only focuses on the total distance of the vehicle paths or the work completion time, and the key resource parameter of the number of vehicles is not included in the overall optimization target, so that the vehicle configuration has redundancy risk or energy consumption cost and cannot be effectively compressed. Secondly, the existing optimization solution scheme lacks an optimization strategy capable of simultaneously taking global exploration and local rationality into consideration, and is easy to fall into low-quality or infeasible solution. In the existing optimization method, one class focuses on global searching capability but has poor solution feasibility, the other class emphasizes local greedy decisions but is easy to fall into local optimum, and a high-quality path planning scheme is difficult to stably obtain. Disclosure of Invention The invention provides an unmanned sanitation vehicle path planning method and system based on improved NSGA-II, which are used for realizing efficient acquisition of path cost by constructing task and road section mapping and node pair shortest distance matrixes, establishing a three-objective optimization model comprising vehicle quantity, system energy consumption and non-coverage rate by combining a greedy path simulation and NSGA-II optimization algorithm, and providing an improved NSGA-II algorithm based on K-Means cluster initialization and coverage rate threshold dynamic cutoff. According to the method, on the premise of not depending on fixed departure points, the number of unmanned sanitation vehicles, the energy consumption of the system and the cleaning area are optimized cooperatively, and the convergence speed of path planning and the practicability of solution are improved. In order to achieve the above purpose, the present invention adopts the following technical scheme: One or more embodiments provide an unmanned sanitation vehicle path planning method based on an improved NSGA-II, comprising the following steps: Acquiring operation tasks and operation vehicle information, performing discretization on road sections corresponding to the operation tasks, establishing mapping between the tasks and the road sections, calculating the shortest distance between the discretized road nodes, and constructing a full node pair shortest distance matrix; Constructing a multi-objective path planning model by taking the minimum number of environmental sanitation vehicles, the minimum total energy consumption of the system and the minimum area ratio of uncovered tasks as optimization targets; And combining greedy path simulation with an NSGA-II optimization algorithm to obtain an improved NSGA-II optimization algorithm, solving the constructed multi-objective optimization model according to the mapping relation between the tasks and the road sections and the shorte