Search

CN-121981642-A - Path optimization method and equipment for multi-area picking and delivering task

CN121981642ACN 121981642 ACN121981642 ACN 121981642ACN-121981642-A

Abstract

The invention relates to the technical field of path planning and intelligent scheduling, and provides a path optimization method and equipment for multi-area picking and delivering tasks. According to the method, a multi-subarea modeling is carried out on a taking and sending task environment, and a task graph model comprising taking and sending task nodes and cross-area connecting nodes is constructed so as to characterize structural features of high communication in subareas and sparse communication among subareas. In the path planning process, the intra-area structural features of task nodes in the subareas and the inter-area communication features among different subareas are respectively extracted, and fusion processing is carried out on the features according to the current path state. On the basis, a candidate target node set is generated through a planning stage, and the actually accessed fetching task nodes are determined in an execution stage, so that the path state is gradually updated until the path planning is completed. The method takes the structured decision flow as a core, and is suitable for a path optimization scene of multi-subarea fetching and delivering tasks.

Inventors

  • LI CHAO
  • MENG YUN
  • SUN JUN
  • SHAN MIN
  • WANG YONG

Assignees

  • 江南大学

Dates

Publication Date
20260505
Application Date
20260126

Claims (8)

  1. 1. A path optimization method and equipment for multi-area picking and delivering tasks are characterized by comprising the following steps: 1) Acquiring environment information of a taking task, modeling the taking task, and constructing a multi-subarea taking task graph model, wherein the multi-subarea taking task graph model comprises a taking task node set, a cross-regional connecting node set and an accessible edge set between nodes; 2) Initializing path state information before path planning begins, wherein the path state information comprises an accessed task node set, a current access position and a task node set which is not accessed yet, and providing an initial state for subsequent path decision; 3) Constructing basic feature representation of the node aiming at the task node which is not accessed in the current path state, wherein the basic feature representation comprises position information of the task node and a sub-area identifier to which the task node belongs; 4) Aiming at task nodes which are not accessed in the current path state, extracting structural features in the areas of the task nodes in the same subarea according to the subareas to which the nodes belong; 5) Based on the cross-region connection node set Analyzing the reachable relation among different subareas, and extracting cross subarea communication characteristics; 6) Performing weighted fusion processing on the intra-region feature representation and the inter-region feature representation, and adaptively adjusting the influence weights of different scale features in the path decision according to the current path state to generate a fusion feature representation; 7) Based on the fusion characteristic representation, under the current path state, determining a task node which is actually accessed next by adopting a double-stage path decision mechanism with a planning stage and an execution stage separated; 7.1 Planning phase potential target generation During the planning phase, based on the current path state The fusion characteristic representation corresponding to each non-access task node carries out global evaluation on the non-access task node to generate a candidate target node used for representing the potential preferential access direction under the current path state, wherein the candidate target node is used for providing global guide information for the path decision of the subsequent execution stage, but is not directly used as the actually-accessed task node; 7.2 Stage of execution: directed actual node selection In the execution phase, in the current path state Candidate target nodes generated in planning stage As global guiding information, evaluating feasible task nodes in a task node set meeting reachability constraint, and selecting a task node with optimal contribution to current path expansion as an actual access task node of a current decision step on the premise of taking the total cost of an optimized overall delivery path as a target; wherein the candidate target node The method is used for guiding the priority ordering of the feasible task nodes in the node selection evaluation process of the execution stage, so that the task nodes consistent with the potential access direction of the planning stage are preferentially selected by the execution stage on the premise of meeting the accessibility constraint; the set of task nodes meeting the reachability constraint is recorded as Which is represented in the current path state Starting from the current task node, the method can directly access in one-time path expansion, and simultaneously satisfies a set formed by non-accessed task nodes of the feasibility constraint of the taking and delivering task and the region communication constraint; 7.3 Inter-phase collaboration and status update The actual access task node selected by the execution stage is used for updating the current path state, and the updated path state is used as the input of the next planning stage, so that the gradual coordination between the planning stage and the execution stage is realized in the path construction process; 8) Adding the actually accessed task node into a current fetching path, judging whether a path termination condition is met according to the updated path state information of the task node, returning to the step 3) to continue execution if the path termination condition is not met, and outputting a complete fetching path scheme if the path termination condition is met, wherein the path termination condition comprises that the current fetching path has completed the access of all fetching task nodes or no unaccessed task node meeting the accessibility constraint exists in the current path state.
  2. 2. The method for optimizing a path for a multi-region delivery task according to claim 1, wherein in step 1), the multi-region delivery task graph model is: Wherein, the Representing a set of fetching task nodes, Representing a preset set of cross-regional connection nodes, The method comprises the steps of representing a set of reachable edges among nodes, wherein the reachable edges among the nodes are jointly determined by the space layout of a fetching task and a preset passing constraint, and introducing a sub-region mapping function for describing sub-regions to which the task nodes belong: Wherein, the Representing task nodes The sub-region to which it belongs is represented, Is a set of sub-regions.
  3. 3. The method of optimizing a path for a multi-area pick-up and delivery task of claim 1, wherein in step 3), for any one of the task nodes The basic characteristics are expressed as follows: Wherein, the Indicating the location information of the i-th task node, Representing the identity of the sub-region to which it belongs, For an embedded mapping function used to generate a node characteristic representation.
  4. 4. The method of optimizing a path for a multi-area pick-up and delivery task of claim 1, wherein in step 4), further, for the task nodes The structural characteristics in the area are expressed as follows: Wherein, the The regional characteristic extraction module is used for extracting the structural characteristics of task nodes in the same subregion and is used for representing the task distribution characteristics and the local path constraint relation in the subregion, and the regional characteristics are used for describing the local distribution structures among the task nodes in the same subregion; The basic feature representation representing the task node i, The basic feature representation representing the task node j, And respectively representing the sub-area identifiers of the ith and j-th task nodes.
  5. 5. The method of optimizing a path for a multi-area pick-up and delivery task of claim 1, wherein in step 5), further, for the task nodes Its cross-region connectivity features are expressed as: Wherein, the Representing a cross-regional feature extraction module for extracting cross-regional connectivity, wherein the cross-regional feature extraction module is used for representing cross-regional path accessibility and cross-regional path constraint features, and k represents a node different from a task node Task nodes in the subareas; A basic feature representation representing a task node k, Representing the sub-region identification to which the kth task node belongs.
  6. 6. A method of path optimization for a multi-zone delivery task of claim 1, wherein in step 6), the fusion features represent Wherein, the Representing the current path state information and, And the characteristic fusion module is used for carrying out self-adaptive fusion on the characteristics in the region and the cross-region characteristics according to the path state.
  7. 7. The method of claim 1, wherein in step 7), the candidate target nodes in the planning phase are expressed as: Wherein, the A potential target generation module for representing planning stage, the current path state The actual access task node selected by the execution stage in the last decision step is updated and obtained, and is used for reflecting the current path construction progress and generating the input of candidate target nodes as a planning stage; the actually accessed task nodes are expressed as: Wherein, the The representation belongs to Is a candidate task node of (c) for a task, Representing the actual access task node determined in the current path state, Representing candidate task nodes The corresponding fusion feature representation is used to represent, Representing the current path state information and, Representing candidate target node representations generated by the planning stage, The task node selection evaluation function is used for describing the relative priority degree of each feasible task node serving as the next access node under the current path state and the planning and guiding conditions; the total path cost of the fetch path may be expressed as: Wherein, the The resulting fetch path is shown as such, Representing path costs between adjacent access task nodes.
  8. 8. A multi-zone delivery task oriented path optimization device comprising at least one processor and a memory communicatively coupled to the at least one processor, wherein the memory stores instructions executable by the at least one processor to cause the at least one processor to perform a multi-zone delivery task oriented path optimization method of any of claims 1-7.

Description

Path optimization method and equipment for multi-area picking and delivering task Technical Field The invention belongs to the technical field of intelligent scheduling and path planning, and particularly relates to a path optimization method and equipment for multi-area picking and delivering tasks. Background Along with the development of intelligent logistics systems and automatic transportation technologies, the problems of path planning and task scheduling are widely applied to the scenes of warehouse logistics, park distribution, multi-floor transportation and the like. In such applications, it is often desirable to plan an optimal path for a transportation entity to access multiple task nodes, while satisfying the delivery constraints, to reduce overall transportation costs or increase operational efficiency. In existing path planning and scheduling methods, the vehicle path problem (Vehicle Routing Problem, VRP) and its related variants are typically used to model and optimize the order of access for the multiple tasks. However, in practical application scenarios, the fetching tasks are often distributed over multiple mutually independent sub-areas, where there is a limited connection, e.g. a cross-floor connection by means of elevators in a multi-floor building. In such a scenario, the communication relationship between the different sub-regions is generally sparse, so that the overall task environment presents obvious partition structure characteristics. Aiming at the multi-subarea taking and sending task, the conventional method is mainly used for uniformly modeling the multi-subarea taking and sending task into a single plane or completely communicated path planning problem, and the characteristics of the internal structure of the subarea and the cross-area connection are not explicitly distinguished in the solving process, so that the model is difficult to effectively describe the cross-area path constraint, and the rationality and the stability of the path planning result are further influenced. In addition, methods based in part on optimization algorithms such as heuristic search or swarm intelligence typically generate path schemes by way of global searching when dealing with such problems. When the task scale is large or the structure of the subarea is complex, the method is easy to cause the problems of rapid expansion of the search space, reduction of convergence efficiency and the like, and the calculation efficiency is difficult to be considered while the solution quality is ensured. Therefore, how to effectively model the connection relation between the internal structure of the subarea and the cross-area in the multi-subarea sending task and realize efficient and stable path planning and scheduling decision on the basis of the connection relation is still a technical problem to be solved in the prior art. Disclosure of Invention The invention provides a path optimization method for a multi-region delivery task, which aims to solve the problem that the existing path planning method is difficult to effectively describe the sparse connection relation between the internal structure of a sub-region and a cross-region in the multi-region delivery task, so that the quality and stability of the path planning are insufficient. As shown in FIG. 2, the method integrally comprises a task modeling module, an intra-area structural feature extraction module, a cross-area communication feature extraction module, a feature fusion module and a path decision module. The technical scheme of the invention is as follows: a path optimization method for multi-area picking and delivering tasks comprises the following steps: 1) Acquiring environment information of a taking task, modeling the taking task, and constructing a multi-subarea taking task graph model, wherein the multi-subarea taking task graph model comprises a taking task node set, a cross-area connecting node set and an accessible edge set among nodes. Further, the multi-subarea fetching task graph model is as follows: Wherein, the Representing a set of fetching task nodes,Representing a preset set of cross-regional connection nodes,Representing a set of reachable edges between nodes. The reachable edges between the nodes are determined by the spatial layout of the fetching task and the preset passing constraint. To describe the sub-region to which the task node belongs, a sub-region mapping function is introduced: Wherein, the Representing task nodesThe sub-region to which it belongs is represented,Is a set of sub-regions. And mapping each sending task node to a corresponding subarea identifier through a subarea mapping function, so that the sending task environment presents structural characteristics of high communication in the subareas and sparse communication among the subareas. Through the modeling, the task environment explicitly shows structural features of high connectivity inside the subareas and sparse connectivity among the subareas.