Search

CN-121981350-A - Real-time task allocation and path planning integrated optimization method for heterogeneous motorcade

CN121981350ACN 121981350 ACN121981350 ACN 121981350ACN-121981350-A

Abstract

The invention discloses a real-time task allocation and path planning integrated optimization method of a heterogeneous vehicle team, which aims at the core pain points with infeasibility of a scheme and poor global optimization capability caused by a scheme of 'first allocation and then planning' in the prior 'unmanned plane-unmanned vehicle' collaborative distribution; and finally, iteratively optimizing an initial solution through a neighborhood search strategy, and synchronously outputting an optimal task allocation scheme, an optimal path planning result and a maximum total path profit. The method realizes the deep coupling and dynamic optimization of task allocation and path planning, remarkably improves the reliability, safety and overall operation efficiency of cooperative delivery of heterogeneous motorcades, and can be widely applied to scenes such as urban logistics, emergency delivery and the like.

Inventors

  • Rao Zicong

Assignees

  • 华东交通大学

Dates

Publication Date
20260505
Application Date
20251231

Claims (9)

  1. 1. The real-time task allocation and path planning integrated optimization method for the heterogeneous motorcade is characterized by comprising the following steps of: S1, acquiring distribution task information and heterogeneous fleet information, wherein the heterogeneous fleet comprises unmanned aerial vehicles and unmanned vehicles, abstracting the distribution task into articles to be loaded into a knapsack based on the information, abstracting the unmanned aerial vehicles and the unmanned vehicles into a plurality of backpacks with different loads and voyages/mileage constraints, and constructing a heterogeneous fleet multi-knapsack collaborative optimization problem model; S2, carrying out iterative task allocation based on a greedy strategy, and embedding real-time path planning and constraint verification to generate an initial scheme, wherein the method specifically comprises the following steps: S2.1, calculating a priority Score (i, v) for each unassigned task i and each vehicle v with a residual load; S2.2, selecting a task-carrier pair (i, v) with the highest current priority score; S2.3, temporarily distributing the task i to the vehicle v, calling a path planning module based on an improved saving algorithm, planning an optimal or near optimal path for the updated task set of the vehicle v, and calculating the total path length D v ; S2.4, judging whether D v meets the maximum range/mileage constraint L v of the vehicle v and whether the current total load meets the maximum load constraint C v , if so, confirming allocation, updating a task list and a path, if not, refusing allocation, punishing the priority score of the task-vehicle pair, and returning to S2.2; S2.5, repeating the steps S2.1 to S2.4 until all the task allocation is completed or no feasible allocation exists, and generating an initial solution, wherein the initial solution comprises a task allocation scheme, each carrier path planning result and the maximum total path profit of the system; s3, optimizing an initial solution by adopting a neighborhood searching strategy, and taking the maximum total path profit as a target; s4, integrally outputting a final task allocation scheme, an optimal path planning result of each carrier and the maximum total path profit.
  2. 2. The method for optimizing real-time mission allocation and route planning integration of a heterogeneous fleet of vehicles according to claim 1, wherein in step S1, the mission information includes cargo weight W i , profit r i , destination coordinates of the mission, and the heterogeneous fleet information includes type of vehicles, maximum load C v , maximum mileage/voyage L v , current location pos (v), fixed cost F v , and unit distance transportation cost q.
  3. 3. The method for optimizing real-time task allocation and path planning integration of heterogeneous fleet according to claim 1, wherein in step S2.1, the priority Score (i, v) is calculated based on the reciprocal distance between the task and the current position of the vehicle, the matching degree between the task weight and the residual load, and the path cost increment factor, and the formula is: , Wherein, the Is a weight coefficient and satisfies ; Distance between the task and the current position of the carrier; The matching degree is the load; Is a path cost increment.
  4. 4. The method for optimizing real-time task allocation and path planning integration of a heterogeneous fleet of vehicles according to claim 3, The calculation mode of (a) is as follows: if the carrier v is an unmanned aerial vehicle, calculating by using Euclidean distance: ; if the vehicle v is an unmanned vehicle, the road detour coefficient is introduced Typical values The calculation mode is as follows: 。
  5. 5. The method for optimizing real-time task allocation and path planning integration of heterogeneous fleet of vehicles according to claim 3, wherein the load matching degree is The formula for the ratio of the current remaining load of the vehicle v to the weight of the mission i is: , Wherein, the For the set of tasks that the vehicle v has assigned, Is the cargo weight of mission a.
  6. 6. The method for optimizing real-time task allocation and path planning integration of heterogeneous fleet of vehicles according to claim 3, wherein the incremental path cost For the difference between the total cost of the new path and the total cost of the original path after temporarily allocating the task i, the formula is: , Wherein, the For the total path cost, including fixed cost and distance cost, the formula is: , To indicate a function, when a vehicle v is tasked with Otherwise ; For the current total path length of the vehicle v.
  7. 7. The integrated optimization method for real-time task allocation and path planning for heterogeneous fleets according to claim 1, wherein in step S2.3, the formula for calculating the total path length D v by the improved saving algorithm path planning module is: , Wherein, the For a sequence of paths of the temporary task set, Is the distance between the two points.
  8. 8. The integrated optimization method for real-time task allocation and path planning for heterogeneous fleet according to claim 1, wherein in step S2.5, the maximum total path profit is the difference between the total task profit and the total path production cost, and the formula is: 。
  9. 9. The method for integrating and optimizing real-time task allocation and path planning of heterogeneous motorcades according to claim 1, wherein in step S3, the neighborhood search operation comprises at least one of task cross-path insertion, task exchange and intra-path 2-opt optimization, and in the optimization process, course/mileage constraint verification is performed on each candidate solution through a path planning module, so that the feasibility of the scheme is ensured.

Description

Real-time task allocation and path planning integrated optimization method for heterogeneous motorcade Technical Field The invention belongs to the technical field of intelligent transportation and intelligent logistics, and particularly relates to an integrated optimization method for task allocation and path planning of unmanned aerial vehicles and unmanned vehicle heterogeneous fleets, which is particularly suitable for collaborative scheduling in urban logistics, emergency distribution and other scenes. Background Along with the popularization of unmanned aerial vehicle technology in terminal logistics distribution, the unmanned aerial vehicle-unmanned aerial vehicle heterogeneous vehicle team collaborative distribution mode becomes a research hot spot of logistics industry by virtue of the large load and long endurance advantages of unmanned aerial vehicles and the flexible and efficient characteristics of unmanned aerial vehicles. The core of this model is how to efficiently distribute multiple delivery tasks to heterogeneous fleet members and plan feasible execution paths. The existing mainstream method mostly adopts a step-by-step strategy of 'first distributing and then planning', namely firstly distributing tasks to vehicles based on rules such as distance, load and the like or an optimization algorithm, and then solving a path problem for each vehicle independently. The mode has inherent defects that firstly, the path aggregation effect is not considered in the task allocation stage, the infeasible conditions of exceeding the range, the load overrun and the like of an allocation scheme in the path planning stage can be caused, and the calculation resource waste is caused by reallocation, and secondly, the strong coupling relation between the task allocation and the path planning is split by step decision, so that the overall planning of the cost minimization and the path minimization can not be realized from the global view, and the global optimization capability is poor. According to the task allocation method for the intelligent warehouse transportation equipment disclosed in the China patent CN201610840518.5, although the scheduling sequence is optimized through comprehensive evaluation indexes and a path is planned by adopting an A-algorithm, the task allocation method is still a step-by-step execution mode of 'first allocation and then planning', and path feasibility constraint is not embedded in an allocation stage, so that path conflict or resource waste is easy to generate. According to the logistics unmanned aerial vehicle intelligent path planning method provided by the Chinese patent CN202411878716.1, linkage of task distribution and path generation is realized, but the essence still follows a step-by-step flow, synchronous optimization is not realized, and global cost and path efficiency are difficult to comprehensively arrange. In summary, the prior art has not solved the problems of real-time coupling and global optimization of task allocation and path planning, resulting in the existence of obvious short boards in terms of feasibility, efficiency and safety of heterogeneous fleet cooperative systems. The information disclosed in this background section is only for enhancement of understanding of the general background of the invention and should not be taken as an acknowledgement or any form of suggestion that this information forms the prior art already known to a person of ordinary skill in the art. Disclosure of Invention The invention aims to provide an integrated optimization method taking embedded path planning as real-time constraint in a task allocation stage, so that integrated synchronous optimization of task allocation and path planning is realized, the feasibility of a scheme is ensured from the source, the global distribution efficiency is improved, and the defects in the prior art are overcome. In order to achieve the above purpose, the invention provides a real-time task allocation and path planning integrated optimization method for heterogeneous motorcades, comprising the following steps: Step S1, problem modeling and initializing; The method comprises the steps of obtaining delivery task information and heterogeneous fleet information, wherein the delivery task information comprises destination coordinates (X i,Yi) of each task, cargo weight W i and task profit r i, and the heterogeneous fleet information comprises the type (UAV/UGV) of each carrier, maximum load C v, maximum range/mileage L v, current position pos (v) (initialized to delivery center coordinates (0, 0)), fixed cost F v and unit distance transportation cost q; Abstracting a delivery task as an article to be loaded into a knapsack, abstracting an unmanned aerial vehicle and an unmanned aerial vehicle as the knapsack with different loads and voyage constraints, constructing a heterogeneous fleet multi-knapsack collaborative optimization model, and defining a mixed fleet set V= { V 1,V2,...,Vn }, a ta