CN-120688967-B - Dynamic programming method, equipment and medium for space-ground collaborative terminal distribution

CN120688967BCN 120688967 BCN120688967 BCN 120688967BCN-120688967-B

Abstract

The embodiment of the specification discloses a dynamic planning method, equipment and medium for air-ground collaborative terminal distribution, relates to the technical field of path planning, and is used for solving the problem that the planning effect is poor due to the fact that the current problem of sudden road failure cannot be responded quickly. The method comprises the steps of updating a road network diagram corresponding to a current distribution area in real time, determining whether to trigger distribution scheme updating of the current distribution area based on a failure unit of the road network diagram, if yes, constructing an air-ground collaborative terminal distribution model of the current distribution area based on information corresponding to the road network diagram, solving the air-ground collaborative terminal distribution model based on a double-stage layering initialization strategy and a double-layer hybrid cross strategy to obtain an initial air-ground collaborative terminal distribution path of a vehicle and an unmanned aerial vehicle, and iteratively updating the initial air-ground collaborative terminal distribution path based on a pareto front edge to obtain an optimal solution as an optimal air-ground collaborative terminal distribution path of the current distribution area.

Inventors

QI WEI
LI ANG
DONG LEI
ZHOU JINNAN
LI XUESONG
ZHANG JIE

Assignees

北京迈拓规划设计有限公司

Dates

Publication Date: 20260508
Application Date: 20250605

Claims (8)

1. A dynamic programming method for space-to-ground collaborative terminal distribution, the method comprising: based on the distribution demand information and the actual road network information of the current distribution area, updating a road network diagram corresponding to the current distribution area in real time, and based on a failure unit of the road network diagram, determining whether to trigger the distribution scheme update of the current distribution area; if yes, constructing an air-ground collaborative terminal distribution model of the current distribution area based on the information corresponding to the road network diagram, wherein the air-ground collaborative terminal distribution model comprises an optimization target and constraint conditions, and the optimization target comprises a demand coverage optimization target, a cost optimization target and a time optimization target; Solving the air-ground collaborative terminal distribution model based on a double-stage layering initialization strategy and a double-layer hybrid cross strategy to obtain an initial air-ground collaborative terminal distribution path of the vehicle and the unmanned aerial vehicle; Iteratively updating the initial space-ground collaborative terminal distribution path based on the pareto front edge to obtain an optimal solution as an optimal space-ground collaborative terminal distribution path of the current distribution area; Solving the air-ground collaborative terminal distribution model based on a double-stage layering initialization strategy and a double-layer hybrid cross strategy to obtain an initial air-ground collaborative terminal distribution path of the vehicle and the unmanned aerial vehicle, wherein the method specifically comprises the following steps: Determining a distribution center node and a failure node based on the information of the road network diagram at a random initialization layer, and generating a first initial vehicle path and a first initial unmanned aerial vehicle path based on random initialization of the distribution center node and the failure node; Calculating the saving value of each node pair based on a preset truck path optimization method at a heuristic initialization layer, and sorting the node pairs in descending order based on the node values to obtain a second initial vehicle path by combining paths, wherein the saving value of each node pair ; Is taken as a point And (3) with Euclidean distance between them; Selecting a task with the largest marginal benefit based on a greedy algorithm to obtain a second initial unmanned aerial vehicle path; Summarizing the first initial vehicle path and the second initial vehicle path to obtain an initial vehicle path, and summarizing the first initial unmanned aerial vehicle path and the second initial unmanned aerial vehicle path to obtain an initial unmanned aerial vehicle path; Processing the initial vehicle path and the initial unmanned aerial vehicle path through a double-layer hybrid crossing strategy to obtain an initial solution of the air-ground collaborative terminal distribution model, wherein the initial solution is used as an initial air-ground collaborative terminal distribution path; processing the initial vehicle path and the initial unmanned aerial vehicle path through a double-layer hybrid intersection strategy to obtain an initial solution of the air-ground collaborative terminal distribution model, wherein the initial solution is used as an initial air-ground collaborative terminal distribution path and specifically comprises the following steps: Selecting parent individuals from a population formed by the initial vehicle path and the initial unmanned aerial vehicle path by adopting a tournament strategy; sequentially crossing the initial vehicle paths to reserve continuous segments of parent individuals of the initial vehicle paths and obtain child new solutions of the initial vehicle paths; Uniformly crossing the initial unmanned aerial vehicle paths to mix parent individuals of the initial unmanned aerial vehicle paths through a mask matrix, and greedy selecting conflict tasks to obtain new child solutions of the initial unmanned aerial vehicle paths; And obtaining an initial solution of the air-ground collaborative terminal distribution model based on the new solution of the offspring of the initial vehicle path and the new solution of the offspring of the initial unmanned aerial vehicle path, and taking the initial solution of the air-ground collaborative terminal distribution model as an initial air-ground collaborative terminal distribution path.
2. The method for dynamically planning air-ground collaborative terminal distribution according to claim 1, wherein the method for dynamically planning air-ground collaborative terminal distribution is characterized by updating a road network map corresponding to a current distribution area in real time based on distribution demand information and actual road network information of the current distribution area, and determining whether to trigger distribution scheme update of the current distribution area based on a failure unit of the road network map, specifically comprising: Determining a node set of a current distribution area according to actual road network information and distribution demand information of the current distribution area, wherein the node set comprises a road intersection, a client demand point, a distribution center and an unmanned aerial vehicle take-off and landing point; determining the weight of each side based on the passing cost and the passing distance corresponding to the road section corresponding to each node; Mapping based on the node set and the weight of each edge to obtain a road network diagram corresponding to the current distribution area, wherein the road network diagram is a grid-shaped road network topology diagram; and calculating the vulnerability of the road section based on the failure unit of the road network diagram so as to trigger the update of the distribution scheme of the current distribution area.
3. The method for dynamic planning of air-ground collaborative end distribution according to claim 2, wherein the calculating the vulnerability of the road section based on the failure unit of the road network graph to trigger the update of the distribution scheme of the current distribution area specifically comprises: obtaining a vulnerability identification model corresponding to a failure unit of the road network graph, wherein the vulnerability identification model comprises a node failure vulnerability identification model and an edge failure vulnerability identification model; acquiring preset initial network efficiency, determining current network efficiency by sequentially removing road sections corresponding to each failure unit, and determining a network efficiency change rate based on preset initial network sales and the current network efficiency; Determining the relative size of the maximum connected subgraph after removing the road sections corresponding to the failure units based on the failure units, and determining the road section importance of the road sections corresponding to the failure units based on the weight of each side; substituting the comprehensive measure value indexes corresponding to the network efficiency change rate, the maximum connected subgraph relative size and the road section importance into the vulnerability identification model to obtain the road section vulnerability so as to trigger the update of the distribution scheme of the current distribution area.
4. The dynamic programming method for space-ground collaborative terminal distribution according to claim 1, wherein constructing a space-ground collaborative terminal distribution model of the current distribution area based on the information corresponding to the road network graph specifically comprises: constructing an optimization target and constraint conditions of an air-ground collaborative terminal distribution model of the current distribution area based on the information corresponding to the road network diagram; The demand coverage optimization objective in the optimization objective is to cover customer demand points around the failed road node to the maximum extent, and the corresponding demand coverage objective function is as follows: wherein, the method comprises the steps of, For the segment vulnerability value, i denotes the node, r denotes the segment, c= {1,2,3,.., For a set of unmanned aerial vehicle paths, Representing customer nodes Located at road section Then Otherwise , For clients Is serviced by vehicle k Otherwise , For clients Is routed by unmanned aerial vehicle Service Otherwise ; The cost optimization objective is to minimize the transportation cost of the vehicle and the unmanned aerial vehicle, and the corresponding cost objective function is: wherein, the method comprises the steps of, The cost per unit distance of transportation for the vehicle, The transportation cost per unit distance of the unmanned aerial vehicle is calculated, For passing through an arc for vehicles Is used for the driving distance of the vehicle, Is a path of unmanned aerial vehicle Through an arc Is used for controlling the flying distance of the vehicle, Representing a set of all of the arcs, For passing the delivery path of vehicle k Then ; Delivery path for unmanned aerial vehicle Through an arc Then ; The time optimization objective is to minimize the delivery time, and the corresponding time objective function is: wherein, the method comprises the steps of, For the speed of the vehicle k, Is the speed of the unmanned aerial vehicle u; 0-1 variable if node i is a drone path Is to (1) recycle point Otherwise ; The moment when the vehicle reaches the node i epsilon V1; The moment when the vehicle reaches the node i epsilon V1; the average service time of the vehicle at node i.
5. The method for dynamic programming of air-ground collaborative end distribution according to claim 4, wherein the constraints include: A first constraint for representing that each customer demand point can only be serviced by a vehicle or drone once; A customer point for representing all vehicles passing by, having a second constraint condition formula for delivery by the vehicles; A third constraint condition formula for representing that all client points served by the unmanned aerial vehicle are passed by the unmanned aerial vehicle path; a fourth constraint condition for indicating that each path arc unmanned aerial vehicle is allowed to pass only once; A fifth constraint condition for constraining the dynamic coordinated take-off and landing points, each unmanned aerial vehicle launch and recovery point must have vehicles passing through, and each unmanned aerial vehicle delivery path serves at least one customer point; A sixth constraint condition that the load capacity does not exceed the maximum load capacity when the unmanned plane path for constraining the load capacity is completed and leaves any client point i; the seventh constraint condition is used for representing that the electric quantity of the transmitting point of any path of the unmanned aerial vehicle meets the maximum endurance time; When any path of the unmanned aerial vehicle returns to the junction, the electric quantity meets an eighth constraint condition formula of 10% of the maximum endurance time; A ninth constraint condition for representing time constraints of arrival and departure of the vehicle at the node i, respectively: , ; The moment when the vehicle reaches the node i epsilon V1; For the moment when the vehicle leaves the node i e V1, M is a sufficiently large positive number; the moment when the vehicle leaves the node i; Tenth constraint condition expression for respectively representing time constraint of arrival and departure of unmanned plane from node i: , ; the moment the vehicle arrives at node i e V1, The moment when the unmanned plane path leaves the node i epsilon V1; an eleventh constraint condition for indicating that at the unmanned aerial vehicle departure point, the vehicle departure time must be later than the unmanned aerial vehicle departure time; and a twelfth constraint condition for representing that at the landing point of the unmanned aerial vehicle, the vehicle is converged with the landing point, and the arrival time of the vehicle is not later than the arrival time of the unmanned aerial vehicle.
6. The dynamic programming method for space-ground cooperative end distribution according to claim 1, wherein the iterative updating of the initial space-ground cooperative end distribution path based on pareto front is performed to obtain an optimal solution as the optimal space-ground cooperative end distribution path of the current distribution area, and specifically comprising: layering the initial space-ground collaborative end distribution paths according to a dominance relation to divide a solution set into a plurality of leading edge levels based on a rapid ordering method; defining the maximum value solution of the direction on the current pareto front as an extreme point based on each target direction corresponding to the optimization target; Carrying out normalization processing on each target space based on the extreme points so as to calculate congestion entropy of each solution on the current pareto front edge, sequencing according to the congestion entropy, and filtering low-entropy solutions to obtain new solutions; And combining the new solution with each solution on the current pareto front, extracting non-dominant solutions to form a set of next-generation solutions, and iteratively updating the solutions of the pareto front to obtain an optimal solution serving as an optimal space-ground collaborative end distribution path of the current distribution area.
7. A dynamic programming device for space-floor collaborative end distribution, the 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 enable the at least one processor to perform the method of any one of the preceding claims 1-6.
8. A non-volatile storage medium storing computer executable instructions, wherein the computer executable instructions are capable of performing the method of any one of claims 1-6.

Description

Dynamic programming method, equipment and medium for space-ground collaborative terminal distribution Technical Field The present disclosure relates to the field of path planning technologies, and in particular, to a dynamic planning method, apparatus, and medium for space-ground collaborative end distribution. Background The traditional urban terminal distribution is carried out by express men through an urban road network by utilizing vehicles, and the road network is easily influenced by uncertain factors such as natural disasters, traffic accidents, sanitary events, collective activities and the like, so that phenomena such as local road section congestion, sealing, regional paralysis and the like are generated, delay or interruption of terminal distribution is caused, and certain losses are brought to distribution enterprises and terminal clients. With the frequent occurrence of natural disasters and emergencies in recent years, emergency logistics related research is gradually increased, and a facility site selection-path optimization problem (LRP) becomes a research hotspot. The current mode of planning the joint delivery path of the vehicle and the unmanned aerial vehicle is generally based on fixed road network information, and cannot respond to dynamic changes such as road failure, congestion and the like in real time, so that a delivery scheme is difficult to avoid a high-risk failure road section preferentially when the delivery scheme fails under an emergency. In addition, when the traditional algorithm, such as a standard genetic algorithm, optimizes the collaborative distribution of the vehicle and the unmanned aerial vehicle, the conflict of multiple latitude targets is difficult to effectively balance, the path planning structure falls into a local optimal solution, the initial population generation strategy is single, the solution space is insufficient, and the algorithm convergence speed and the global optimality are affected. Disclosure of Invention In order to solve the above technical problems, one or more embodiments of the present disclosure provide a dynamic planning method, apparatus, and medium for air-ground collaborative end distribution. One or more embodiments of the present disclosure adopt the following technical solutions: one or more embodiments of the present disclosure provide a dynamic planning method for space-floor collaborative end distribution, where the method includes: based on the distribution demand information and the actual road network information of the current distribution area, updating a road network diagram corresponding to the current distribution area in real time, and based on a failure unit of the road network diagram, determining whether to trigger the distribution scheme update of the current distribution area; if yes, constructing an air-ground collaborative terminal distribution model of the current distribution area based on the information corresponding to the road network diagram, wherein the air-ground collaborative terminal distribution model comprises an optimization target and constraint conditions, and the optimization target comprises a demand coverage optimization target, a cost optimization target and a time optimization target; Solving the air-ground collaborative terminal distribution model based on a double-stage layering initialization strategy and a double-layer hybrid cross strategy to obtain an initial air-ground collaborative terminal distribution path of the vehicle and the unmanned aerial vehicle; and iteratively updating the initial space-ground collaborative end distribution path based on the pareto front edge to obtain an optimal solution as the optimal space-ground collaborative end distribution path of the current distribution area. Optionally, in one or more embodiments of the present disclosure, based on the delivery requirement information and the actual road network information of the current delivery area, updating the road network map corresponding to the current delivery area in real time, and based on the failure unit of the road network map, determining whether to trigger the update of the delivery scheme of the current delivery area specifically includes: Determining a node set of a current distribution area according to actual road network information and distribution demand information of the current distribution area, wherein the node set comprises a road intersection, a client demand point, a distribution center and an unmanned aerial vehicle take-off and landing point; determining the weight of each side based on the passing cost and the passing distance corresponding to the road section corresponding to each node; Mapping based on the node set and the weight of each edge to obtain a road network diagram corresponding to the current distribution area, wherein the road network diagram is a grid-shaped road network topology diagram; and calculating the vulnerability of the road section based on the failure u