CN-122022095-A - Low-computation-complexity path optimization method based on tribe

CN122022095ACN 122022095 ACN122022095 ACN 122022095ACN-122022095-A

Abstract

The application relates to a low-computation-complexity path optimization method based on clans. The method comprises the steps of dividing all nodes into a plurality of clans, calculating the center position of each clan, expanding search radius if the number of clan nodes is larger than a preset value, traversing all nodes based on the expanded search radius, dividing all nodes into clans again until the number of clan nodes is smaller than or equal to the preset value, calculating the moving time among all clans based on the moving acceleration and the speed of each clan, calculating the optimal path of clan which accesses all clan nodes once and does not return to the starting point based on the moving time among all clans and the shortest time criterion, and calculating the path optimization inside the clan according to the optimal path of clan to obtain the optimal path of all nodes. The application uses the clan center as the clan node, converts the path optimization problem under the large-scale node into the path sub-optimization problem under the small-scale clan node, and greatly reduces the calculation complexity.

Inventors

HOU YUXING
GUO YUZHANG
WEI HAILIANG
YAN ZHENZHEN
WANG HAIYING
SU XINXUAN
ZHANG XI
YONG JUN
HUANG PUJUN
LIU JINHUI

Assignees

西安黄河机电有限公司

Dates

Publication Date: 20260512
Application Date: 20260127

Claims (10)

1. A clan-based low computational complexity path optimization method, the method comprising: constructing a plane area and generating all nodes in the plane area; Setting a search radius, traversing all nodes based on the search radius, dividing all nodes into a plurality of clans, and calculating the central position of each clan; if the number of the clan nodes is larger than a preset value, expanding the searching radius, traversing all the nodes based on the expanded searching radius, and re-dividing all the nodes into the clans until the number of the clan nodes is smaller than or equal to the preset value; Calculating a movement time between each of the clans based on the movement acceleration and speed of each of the clans; Calculating a clan optimal path that accesses all clan nodes once and does not return to the starting point based on the travel time between each of the clans and a minimum time criterion; and calculating path optimization in the clan according to the clan optimal path to obtain the optimal path of all nodes.
2. The clan-based low computational complexity path optimization method of claim 1 wherein the step of constructing a planar region and generating all nodes within the planar region comprises: The plane area is an [ X, Y ] area; Generating a plurality of randomly distributed clans within said [ X, Y ] region; or generating a plurality of clans of random distribution and combined distribution in the [ X, Y ] area.
3. The clan-based low computational complexity path optimization method of claim 2 wherein the step of generating a plurality of randomly distributed clans within the [ X, Y ] area comprises: assuming that the total number of the clans is n, n is less than or equal to 20; Randomly generating n clans in the [ X, Y ] area, setting the central position of the ith clan as (Axi, ayi), the radius of the clan as r 0 , the number of nodes in the clan as m i , the coordinates of the nodes in the clan as (X ij ,y ij ), and the total number of nodes in the [ X, Y ] area as Wherein i=1, 2,..n, j=1, 2,..m i , axi represent the X-axis coordinates of the center position of the ith said clan and Ayi represent the Y-axis coordinates of the ith said center position.
4. A clan-based low computational complexity path optimization method as in claim 3 wherein the step of generating a plurality of randomly distributed and combined distributed clans within the [ X, Y ] region comprises: assuming that the total number of the clans distributed randomly and in combination is n, wherein n is less than or equal to 20; Generating n 1 clans in the [ X, Y ] area, wherein the n 1 clans are arranged in a line and mutually overlapped to form a strip shape; Assuming that the center position of the ith clan is (Axi, ayi), the radius of the clan is r 0 , the number of nodes inside the clan is m i , and the coordinates of nodes inside the clan are (X ij ,y ij ), wherein i=1, 2, n 1 ,j=1,2,...,m i , axi represents the X-axis coordinate of the center position of the ith clan, ayi represents the Y-axis coordinate of the center position of the ith clan; Generating 3 clans in the [ X, Y ] area, wherein the 3 clans are arranged and overlapped mutually to form a triangle; Assuming that the center position of the ith clan is (Ax i ,Ay i ), the radius of the clan is r 0 , the number of nodes inside the clan is m i , and the coordinates of nodes inside the clan are (x ij ,y ij ), wherein i=n1+1, n1+2, n1+3, j=1, 2,..m i ; Randomly generating (n-n 1 -3) claps within the [ X, Y ] region, the claps having a center position of (Axi, ayi), i=n 1 +4,n 1 +5,..n, n, the claps having a radius of r 0 , a number of nodes within the claps m i , a node coordinate within the claps being (X ij ,y ij ), and a total number of nodes within the [ X, Y ] region being Wherein i=n 1 +4,n 1 +5,...,n,j=1,2,...m i .
5. The clan-based low computational complexity path optimization method of claim 4 wherein the step of setting a search radius, traversing all nodes based on the search radius, dividing all nodes into clans, and calculating a center location of each clan comprises: Determining an initial node from all the nodes, and performing all the node searches, wherein the all the node searches comprise a first search, a second search and a third search; searching for the first time, namely searching for the nodes by taking the initial node as the circle center and 2 times of searching radius; If the node is not searched, the initial node is self-formed into a tribe, and the search is ended; If other nodes are searched, calculating the central positions of all the searched nodes for the first time according to the searched nodes, wherein the central positions of all the searched nodes are recorded as the first central positions; If the distance between the first central position and the initial node is smaller than or equal to the searching radius, re-searching the node by taking the first central position as the circle center and the searching radius, and recording the searched node; If the distance between the first central position and the starting node is larger than the searching radius, carrying out node searching again by taking the position, which is on the connecting line of the starting node and the first central position and is away from the starting node, as a circle center, with the searching radius, recording the searched nodes, and calculating the central positions of all the searched nodes for the second time according to the searched nodes, wherein the central positions of all the searched nodes are recorded as second central positions; Searching for a third time, namely re-searching for nodes by taking the second central position as the center of a circle and 1.2 times of searching radius, recording the searched nodes, and incorporating the searched nodes into the clan; Determining a new starting node from the residual nodes, and searching the residual nodes in the same mode as that of all the nodes; And incorporating all the nodes into the clans, completing clan division, dividing the nodes into n clans, numbering the clans, obtaining initial clan numbers, and calculating the central position of each clan.
6. The clan-based low computational complexity path optimization method of claim 5, wherein the step of expanding the search radius if the number of clan nodes is greater than a preset value, traversing all nodes based on the expanded search radius, and re-dividing all nodes into clans until the number of clan nodes is less than or equal to the preset value comprises: Setting the search radius as the advance The expanded searching radius is r+ Based on the expanded search radius r + And re-dividing the clans, counting the number of the clan nodes, and if the number of the clan nodes is still larger than the preset value, continuing to expand the searching radius by the searching radius until the number of the clan nodes is smaller than or equal to the preset value, wherein the preset value is 20.
7. The clan-based low computational complexity path optimization method of claim 6 wherein the step of calculating the travel time between each of said clans based on the acceleration and velocity of movement of each of said clans comprises: Calculating a preset distance between clans according to the moving acceleration and the speed, wherein the preset distance between clans The calculation formula of (2) is as follows: (1) In the formula, Representing a preset distance between clans, a representing a moving acceleration, and v representing a speed; If the distance between the clans is smaller than The movement time between the clans is ; If the distance between the clans is greater than or equal to The movement time between the clans is 。
8. The clan-based low computational complexity path optimization method of claim 7, further comprising: If there is no communication between two of the clan nodes, the travel time between the clans is infinite.
9. The clan-based low computational complexity path optimization method of claim 7 wherein the step of calculating a clan optimal path that accesses all clan nodes once and does not return to the starting point based on travel time between each of the clans and a minimum time criterion comprises: And according to the movement time among the clans, accessing all the clan nodes once and not returning to the starting point for the shortest time, wherein the path corresponding to the shortest time is the optimal path, and obtaining the clan access sequence, wherein the clan access sequence comprises clan No.1 to clan No. n.
10. The clan-based low computational complexity path optimization method of claim 9, wherein the step of calculating path optimization within the clan based on the clan optimal path to obtain optimal paths for all nodes comprises: Sequencing the internal nodes of the tribe No.1, wherein the central position of the tribe No.2 is taken as an end point, and the optimal path of all the nodes in the tribe No.1 is solved by utilizing a dynamic programming method to obtain the optimal sequencing of the internal nodes of the tribe No. 1; sequencing the internal nodes of the clan No. 2, wherein the internal nodes of the clan No. 1 are used as starting points, the central position of the clan No. 3 is used as an end point, and a dynamic programming method is utilized to solve and access the optimal paths of all the nodes in the clan No. 2 so as to obtain the optimal sequencing of the internal nodes of the clan No. 2; Sequencing internal nodes of clan i, wherein the internal nodes of clan i-1 are used as starting points, the central position of clan i+1 is used as an end point, and the optimal path of all nodes in clan i is solved by using a dynamic programming method to obtain the optimal sequencing of the internal nodes of clan i, wherein 1< i < n; sequencing the internal nodes of the clan number N, wherein the method comprises the steps of taking the last node of the internal sequencing of the clan number N-1 as a starting point, accessing the optimal paths of all the nodes in the clan number N to obtain the optimal sequencing of the internal nodes of the clan number N; Obtaining access orders of all clan internal nodes from the optimal order of the clan number 1 internal nodes to the optimal order of the clan number n internal nodes; And obtaining the access sequence of all nodes according to the access sequence of the clans and the access sequence of all nodes in the clans.

Description

Low-computation-complexity path optimization method based on tribe Technical Field The application relates to the technical field of mathematical topology, in particular to a low-computation-complexity path optimization method based on clan. Background Path optimization is a classical algorithm problem, mainly referring to the problem of finding the shortest path between two places. The path optimization algorithm mainly relates to Floyd-Warshall algorithm, A-type algorithm, dijkstra algorithm and the like. The combination optimization and application characteristics of the path optimization algorithm make the path optimization algorithm receive general importance of traffic managers and decision leaders in the fields of combination mathematics, application mathematics, computer application technology, logistics science, network analysis, graph theory and operation and study, and the research of the algorithm has great practical significance. The direction of path optimization is diverse. In the related art, the Hamiltonian path problem is an NP difficult problem, and the accurate algorithm is only applicable to a small-scale node problem. The accurate solution can be obtained by adopting a dynamic programming algorithm when the small-scale node (n is less than or equal to 20), the genetic algorithm can be adopted when the medium-scale node (20 < n is less than or equal to 100), and the heuristic algorithm such as nearest neighbor can be adopted when the large-scale node (n is more than 100). But the path optimization algorithm has high computational complexity on the medium-large scale nodes. Accordingly, there is a need to provide a new solution to ameliorate one or more of the problems presented in the above solutions. It should be noted that the information disclosed in the above background section is only for enhancing understanding of the background of the application and thus may include information that does not form the prior art that is already known to those of ordinary skill in the art. Disclosure of Invention It is an object of the present application to provide a clan-based low computational complexity path optimization method that overcomes, at least in part, one or more of the problems due to the limitations and disadvantages of the related art. According to a first aspect of an embodiment of the present application, there is provided a clan-based low computational complexity path optimization method, the method comprising: constructing a plane area and generating all nodes in the plane area; Setting a search radius, traversing all nodes based on the search radius, dividing all nodes into a plurality of clans, and calculating the central position of each clan; if the number of the clan nodes is larger than a preset value, expanding the searching radius, traversing all the nodes based on the expanded searching radius, and re-dividing all the nodes into the clans until the number of the clan nodes is smaller than or equal to the preset value; Calculating a movement time between each of the clans based on the movement acceleration and speed of each of the clans; Calculating a clan optimal path that accesses all clan nodes once and does not return to the starting point based on the travel time between each of the clans and according to a minimum time criterion; and calculating path optimization in the clan according to the clan optimal path to obtain the optimal path of all nodes. In an embodiment of the present application, the step of constructing a planar area and generating all nodes in the planar area includes: The plane area is an [ X, Y ] area; Generating a plurality of randomly distributed clans within said [ X, Y ] region; or generating a plurality of clans of random distribution and combined distribution in the [ X, Y ] area. In an embodiment of the present application, the step of generating a plurality of randomly distributed clans within the [ X, Y ] area comprises: assuming that the total number of the clans is n, n is less than or equal to 20; Randomly generating n clans in the [ X, Y ] area, setting the central position of the ith clan as (Axi, ayi), the radius of the clan as r 0, the number of nodes in the clan as m i, the coordinates of the nodes in the clan as (X ij,yij), and the total number of nodes in the [ X, Y ] area as Wherein i=1, 2,..n, j=1, 2,..m i, axi represent the X-axis coordinates of the center position of the ith said clan, ayi represent the Y-axis coordinates of the center position of the ith said clan. In an embodiment of the present application, the step of generating a plurality of randomly distributed and combined distributed clans within the [ X, Y ] area comprises: assuming that the total number of the clans distributed randomly and in combination is n, wherein n is less than or equal to 20; Generating n 1 clans in the [ X, Y ] area, wherein the n 1 clans are arranged in a line and mutually overlapped to form a strip shape; Assuming that the central posit