CN117114375B - Multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving - Google Patents
Multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving Download PDFInfo
- Publication number
- CN117114375B CN117114375B CN202311385838.2A CN202311385838A CN117114375B CN 117114375 B CN117114375 B CN 117114375B CN 202311385838 A CN202311385838 A CN 202311385838A CN 117114375 B CN117114375 B CN 117114375B
- Authority
- CN
- China
- Prior art keywords
- truck
- unmanned aerial
- aerial vehicle
- path
- point
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 101
- 238000005457 optimization Methods 0.000 claims abstract description 16
- 239000011159 matrix material Substances 0.000 claims description 45
- 230000004927 fusion Effects 0.000 claims description 11
- 238000004364 calculation method Methods 0.000 claims description 2
- 238000003780 insertion Methods 0.000 claims 1
- 230000037431 insertion Effects 0.000 claims 1
- 238000010586 diagram Methods 0.000 description 5
- 229920003229 poly(methyl methacrylate) Polymers 0.000 description 5
- 239000004926 polymethyl methacrylate Substances 0.000 description 5
- 235000003801 Castanea crenata Nutrition 0.000 description 1
- 244000209117 Castanea crenata Species 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000001186 cumulative effect Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000013507 mapping Methods 0.000 description 1
- 238000013178 mathematical model Methods 0.000 description 1
- 230000015654 memory Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
- G06Q10/063—Operations research, analysis or management
- G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F18/00—Pattern recognition
- G06F18/20—Analysing
- G06F18/23—Clustering techniques
- G06F18/232—Non-hierarchical techniques
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N5/00—Computing arrangements using knowledge-based models
- G06N5/01—Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
- Y02T10/00—Road transport of goods or passengers
- Y02T10/10—Internal combustion engine [ICE] based vehicles
- Y02T10/40—Engine management systems
Landscapes
- Engineering & Computer Science (AREA)
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Economics (AREA)
- General Physics & Mathematics (AREA)
- Strategic Management (AREA)
- Entrepreneurship & Innovation (AREA)
- General Business, Economics & Management (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Operations Research (AREA)
- Marketing (AREA)
- Game Theory and Decision Science (AREA)
- General Engineering & Computer Science (AREA)
- Development Economics (AREA)
- Evolutionary Computation (AREA)
- Artificial Intelligence (AREA)
- Bioinformatics & Computational Biology (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Evolutionary Biology (AREA)
- Life Sciences & Earth Sciences (AREA)
- Educational Administration (AREA)
- Computational Linguistics (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
Abstract
The invention discloses a multi-truck multi-unmanned aerial vehicle task allocation method based on mileage saving and marginal cost, which relates to the technical field of parcel delivery, and the method for constructing a solution is coupled with the method for optimizing the solution, so that the relevance between an unmanned aerial vehicle path and a truck path is considered, and the solved quality is improved; advancing the current solution along the direction of solution optimization so as to avoid the problem of overlong searching time in a solution space for advancing the solution along the direction of optimization in the existing multi-stage heuristic algorithm, improve the efficiency and improve the problem of long time consumption of the algorithm; the problem that each truck can only carry one unmanned aerial vehicle is solved.
Description
Technical Field
The invention relates to the technical field of parcel delivery, in particular to a multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving.
Background
In recent years, unmanned aerial vehicles are widely used in the fields of mapping scanning, disaster relief, logistics distribution and the like due to the high efficiency of unmanned aerial vehicles. Key research contents of the multi-truck multi-unmanned aerial vehicle collaborative parcel pickup and delivery task allocation problem are as follows: firstly, a customer point set and a flight path of each unmanned aerial vehicle service are determined, and secondly, the unmanned aerial vehicle is released or recycled at which truck stopping points of each truck and the order of the truck visiting the truck stopping points are determined, so that the total travel distance of all trucks and unmanned aerial vehicles is minimized while the unmanned aerial vehicle loading capacity and the flight distance constraint are met. In the prior art, aiming at the task allocation problem of the cooperation package pickup and delivery of the truck unmanned aerial vehicle, the current solving method mostly aims at the problem of the cooperation of multiple unmanned aerial vehicles by a single truck and the cooperation of multiple unmanned aerial vehicles by multiple trucks, and is a method for carrying one unmanned aerial vehicle on each truck, and lacks the efficient solving method of the cooperation of multiple unmanned aerial vehicles by multiple trucks, namely the method for carrying multiple unmanned aerial vehicles on each truck. Because the problem of multi-truck multi-unmanned aerial vehicle collaborative parcel pickup and delivery task allocation is an NP-hard optimization problem, and it is difficult to obtain an optimal solution in a short time, the current solving method is mostly a heuristic algorithm, such as a classical heuristic algorithm and a multi-stage heuristic algorithm. The former has simple principle and wide applicability, and obtains the suboptimal solution of the large-scale optimization problem in polynomial time, but has insufficient local searching capability and long time consumption; the method is characterized in that an initial solution meeting the constraint of a truck and an unmanned aerial vehicle is firstly constructed, then disturbance or local search strategy is applied to the initial solution for optimization, a greedy method is often adopted to quickly obtain the initial solution, but the subsequently applied optimization strategy has certain uncertainty, and the local search strategy is unstable in optimization performance.
Disclosure of Invention
Aiming at the defects in the prior art, the multi-truck multi-unmanned aerial vehicle task allocation method based on the mileage saving and marginal cost solves the problems that the algorithm local searching capability is insufficient, the optimization performance of the local searching strategy is unstable, the time consumption is long and the multi-truck collaborative multi-unmanned aerial vehicle method is lacked in the prior art.
In order to achieve the aim of the invention, the invention adopts the following technical scheme:
the multi-truck multi-unmanned aerial vehicle task allocation method based on the mileage saving and marginal cost comprises the following steps:
s1, acquiring a client point set and a truck parking point set;
s2, calculating a client point set and a truck stop point position set to obtain an conservation matrix among all client points;
s3, acquiring a truck path set according to the saving matrix among the client points;
s4, acquiring an unmanned aerial vehicle path set according to the truck path set;
s5, calculating based on the truck path set and the unmanned aerial vehicle path set to obtain a path set corresponding to each unmanned aerial vehicle and a total distance of the corresponding truck unmanned aerial vehicle; the path sets corresponding to the unmanned aerial vehicles are distributed unmanned aerial vehicle path sets;
And S6, carrying out iterative optimization on the truck path set, the allocated unmanned aerial vehicle path set and the total distance of the corresponding truck unmanned aerial vehicle to obtain an optimal truck path set corresponding to each truck, an optimal unmanned aerial vehicle path set and the optimal total distance of the corresponding truck unmanned aerial vehicle.
The beneficial effects of the invention are as follows: the method couples the method of constructing the solution and the method of optimizing the solution together, and considers the relevance between the unmanned plane path and the truck path, thereby improving the quality of the required path; advancing the current solution along the direction of solution optimization so as to avoid the problem of overlong searching time in a solution space for advancing the solution along the direction of optimization in the existing multi-stage heuristic algorithm, improve the efficiency of path allocation and improve the problem of long time consumption of the algorithm; the problem that each truck can only carry one unmanned aerial vehicle is solved.
Drawings
FIG. 1 is a flow chart of the present invention;
FIG. 2 is a schematic diagram of a computational savings matrix of the present invention;
FIG. 3 is a schematic diagram of constructing an initial unmanned path set in accordance with the present invention;
FIG. 4 is a schematic diagram of four cases of the present invention satisfying the fusion condition;
FIG. 5 is a diagram showing four cases of determining whether to fuse according to the present invention;
Fig. 6 is a schematic diagram of the present invention for determining whether a fused unmanned path is feasible;
FIG. 7 is an illustration of a state identification matrix of the present invention;
FIG. 8 is a scene graph of a set of paths for a drone that a drone path cannot be plugged into a truck;
FIG. 9 is a graph comparing total distance of points for different customers with a number of drones of 1, a load of 5, and a number of trucks of 3;
FIG. 10 is a graph comparing total distance of points for different customers with a number of unmanned aerial vehicles of 1, a load of 10, and a truck of 3;
FIG. 11 is a graph comparing total distance of points for different customers with a number of unmanned aerial vehicles of 1, a load of 20, and a truck of 3;
FIG. 12 is a graph comparing total distance of points for different customers with 3 unmanned aerial vehicles, 5 load, and 3 truck;
FIG. 13 is a graph comparing total distance of points for different customers with 3 unmanned aerial vehicles, 10 load capacity, and 3 truck capacity;
FIG. 14 is a graph comparing total distance of points for different customers with 3 unmanned aerial vehicles, 20 load capacity, and 3 truck capacity;
FIG. 15 is a graph comparing total distance of points for different customers with 5 unmanned aerial vehicles, 5 load capacity, and 3 truck capacity;
FIG. 16 is a graph comparing total distance of points for different customers with 5 unmanned aerial vehicles, 10 load capacity, and 3 truck capacity;
fig. 17 is a graph comparing total distance of different customer points for a number of drones of 5, a load of 20 and a number of trucks of 3.
Detailed Description
The following description of the embodiments of the present invention is provided to facilitate understanding of the present invention by those skilled in the art, but it should be understood that the present invention is not limited to the scope of the embodiments, and all the inventions which make use of the inventive concept are protected by the spirit and scope of the present invention as defined and defined in the appended claims to those skilled in the art.
As shown in fig. 1, a multi-truck multi-unmanned aerial vehicle task allocation method based on mileage conservation and marginal cost comprises the following steps:
s1, acquiring a client point set and a truck parking point set;
s2, calculating a client point set and a truck stop point position set to obtain an conservation matrix among all client points;
s3, acquiring a truck path set according to the saving matrix among the client points;
S4, acquiring an unmanned aerial vehicle path set according to the truck path set;
s5, calculating based on the truck path set and the unmanned aerial vehicle path set to obtain a path set corresponding to each unmanned aerial vehicle and a total distance of the corresponding truck unmanned aerial vehicle; the path sets corresponding to the unmanned aerial vehicles are distributed unmanned aerial vehicle path sets;
and S6, carrying out iterative optimization on the truck path set, the allocated unmanned aerial vehicle path set and the total distance of the corresponding truck unmanned aerial vehicle to obtain an optimal truck path set corresponding to each truck, an optimal unmanned aerial vehicle path set and the optimal total distance of the corresponding truck unmanned aerial vehicle.
As shown in fig. 2, step S2 further includes:
s2-1, according to the client point setTruck dock set +.>Acquiring Euclidean distance matrix between each client point and each truck stop point>The method comprises the steps of carrying out a first treatment on the surface of the Wherein the client Point set->，/>Representing the number of customer points, truck dock set +.>Initially the truck dock set->，/>Representing the number of trucks given +.>Representing a given number of truck stops;
s2-2, utilizing Prim clustering algorithm to gather client pointsAnd truck dock set->Clustering to obtain truck stop point set clustered to each client point >；
S2-3, according to the formula:
obtaining a customer pointAnd corresponding clustered truck stop ∈>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Representing customer points->Representing vertex(s),>representing customer points->And vertex->Euclidean distance of>Representing the maximum flight distance of the unmanned aerial vehicle, +.>Representing the variable value corresponding to the minimum value, < ->Representing a set of client points that have not been clustered, and +.>Initial value is client point set->，/>Representation clustered to truck dock +.>Is>Indicate->A truck stop;
s2-4, judging the client pointWhether or not it is feasible; if yes, entering a step S2-5; otherwise, ending the operation;
s2-5, enabling truck stop points to be gatheredIs->And according to the formula:
updating to obtain updated client point setUpdated truck stop set +.>Updated customer point->Corresponding clustered truck stops +.>；
S2-6, judging updated client point setWhether it is an empty set; if yes, entering a step S2-7; otherwise, returning to the step S2-2;
s2-7, according to the formula:
obtain the firstIndividual client Point->And->Individual client Point->Distance cost saving value of the path formed between them +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>The initial value is 1->Representation clustered to customer point- >Truck stop point (I)>Representations clustered to customer pointsTruck stops;
if it isThe client point is->Customer Point->Corresponding distance cost saving value +.>Record to saving matrix->Will save matrix +.>Current total number of lines->The corresponding formula is:
wherein,the initial value is 1, saving matrix->The initial value is an empty set;
s2-8, judgment reference numeralsWhether or not equal to the number of customer points->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S2-9; otherwise, the label->Adding 1 and returning to the step S2-7;
s2-9, saving matrix from third column to last columnAccording to the value of the third column, descending order is performed to obtain the saving matrix +.>。
As shown in fig. 3 and 4, step S3 further includes:
s3-1, according to the updated truck stop point setAcquiring Euclidean distance matrix between stop points>；
S3-2, according to the truck stop point set clustered to each client pointConstructing an initial unmanned aerial vehicle path set +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>，/>；
S3-3, orderWherein->Represents the current set of unmanned paths, +.>Representing a current savings matrix;
s3-4, judging the current saving matrixWhether it is an empty set; if yes, entering a step S3-12; otherwise, enter step S3-5;
S3-5, according to the formula:
removing savings matrixAnd in the unmanned plane path set +.>Searching to obtain updated saving matrix +.>Respectively and client point->And customer Point->Corresponding unmanned plane path->And->；
S3-6, according to customer pointAnd->In unmanned plane path->And->In (2) position determination unmanned plane path +.>Andwhether to perform fusion or not; if yes, entering a step S3-7; otherwise, returning to the step S3-4;
s3-7, according to the formula:
unmanned aerial vehicle pathAnd->Fusing to obtain a fused unmanned plane path +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein,representing unmanned path->Ordered vertex set in->Representing unmanned path->An ordered set of vertices in (a); />And->Respectively represent unmanned plane path->And->Is the total number of vertices;
s3-8, judging the fused unmanned aerial vehicle pathWhether the maximum flight distance constraint and the load constraint of the unmanned aerial vehicle are simultaneously met; if yes, entering a step S3-9; otherwise, returning to the step S3-4;
s3-9, willAs a current unmanned path set +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein,is indicated at->Remove->；
S3-10, judging the fused unmanned aerial vehicle pathIs>And landing Point->Whether or not the same; if yes, returning to the step S3-4; otherwise, enter step S3-11;
S3-11, according to the formula:
updating Euclidean distance matrix between stop pointsThe method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Representing a fused unmanned path +.>Is the total number of vertices;
s3-12, utilizing a minimum marginal algorithm and according to the formula:
obtaining the path of each truckAnd update the truck dock set +.>And truck path->The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Indicates the truck number>Representing truck dock +.>Assigned truck number,/->Representing truck dock +.>Insert into truck path->Is (are) located>Representing truck dock +.>Insert into truck path->Is>Truck after each positionPath of->Indicating the total distance corresponding to the truck path, +.>Represents the current cumulative distance travelled by the unmanned aerial vehicle, +.>Representing the client point +.>An assigned truck number record array;
s3-13, repeating the step S3-12 until the truck stops are gatheredFor empty sets, a set of truck paths is obtained.
As shown in fig. 5, the fusion judgment criteria of step S3-6 are:
if the client pointsAnd->Located in the same unmanned plane path, i.e.)>No fusion is performed;
if in unmanned plane pathCustomer point (S)>Not the first customer point served by the unmanned aerial vehicle, nor the last customer point served by the unmanned aerial vehicle, then do not merge;
If in unmanned plane pathCustomer point (S)>Not the first customer point served by the unmanned aerial vehicle, nor the last customer point served by the unmanned aerial vehicle, then do not merge;
if in unmanned plane pathCustomer point (S)>And in unmanned path->Customer point (S)>Neither the first nor the last client point served by the drone, no fusion is performed.
The maximum flight distance constraint of the unmanned aerial vehicle in the step S3-8 is as follows:
according to the formula:
obtaining a fused unmanned plane pathThe current unmanned plane corresponding to each vertex of the list is integrated with the flight distance +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>、/>Respectively represent +.>Vertex and->Vertex(s)>Represent the firstApexes->And->Apexes->Euclidean distance between them;
sequentially judging the accumulated flight distance of the current unmanned aerial vehicle corresponding to each vertexWhether is greater than the maximum flight distance of the unmanned aerial vehicle +.>The method comprises the steps of carrying out a first treatment on the surface of the If the fused unmanned plane path is +>The accumulated flight distance of the current unmanned aerial vehicle corresponding to the last vertex in the plurality of unmanned aerial vehiclesLess than or equal to the maximum flight distance of the unmanned aerial vehicle>The maximum flight distance constraint of the unmanned aerial vehicle is met, otherwise, the maximum flight distance constraint of the unmanned aerial vehicle is not met;
the unmanned aerial vehicle load constraint of step S3-8 is:
according to the formula:
Sequentially obtaining fused unmanned aerial vehicle pathsTotal amount of packages corresponding to each vertex in +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein,indicate->Vertex(s)>Indicate->Apexes->The weight of the package to be delivered;
according to the formula:
obtaining unmanned aerial vehicle path after leaving fusion of unmanned aerial vehicleMiddle->Weight of package carried by individual customer points: wherein (1)>Indicate->Apexes->The weight of the package to be collected;
judging fused unmanned plane pathThe wrap total amount array of each vertex in (1)>Whether the elements are greater than the portable maximum package weight +.>The method comprises the steps of carrying out a first treatment on the surface of the If yes, the unmanned aerial vehicle load constraint is not satisfied; otherwise, the unmanned aerial vehicle load constraint is satisfied.
Step S4 further comprises:
s4-1, repeating the steps S3-3 to S3-8 according to a mileage saving algorithm to obtain a fused unmanned plane path meeting the maximum flight distance constraint and the load constraint of the unmanned plane;
s4-2, judging whether the fused unmanned aerial vehicle path meeting the maximum flight distance constraint and the load constraint of the unmanned aerial vehicle is feasible or not; if yes, obtaining a feasible unmanned aerial vehicle path and entering a step S4-3; otherwise, returning to the step S4-1;
s4-3, judging whether the feasible unmanned aerial vehicle paths meet the number constraint of unmanned aerial vehicles or not; if yes, entering a step S4-4; otherwise, returning to the step S4-1;
S4-4, updating the unmanned aerial vehicle path set according to the formula of the step S3-9；
S4-5, judging saving matrixWhether it is an empty set; if yes, entering a step S4-6; otherwise, returning to the step S4-1;
s4-6, according to the formula:
obtaining the truckAlong the truck path>Is>And will->The value of (2) is added to 1; wherein, truck number->The initial value is 1, total distance->The initial value is 0->Representing truck Path set +.>Is a total number of stops;
s4-7, as a stop pointAt the time, stop point->Restoring to the initial value, and +.>The value of (2) is added to 1;
s4-8, repeating the steps S4-6 and S4-7, and obtaining all total distancesAdding to get truck path set->Is>；
S4-9, according to the formula:
performing calculation until reaching vertexObtaining a total distance added to the distance travelled on the unmanned pathThe method comprises the steps of carrying out a first treatment on the surface of the Wherein, vertex->Initial value is 2, total distance->The initial value is +.>，/>Representing unmanned aerial vehicle path setsIs the total number of vertices;
s4-10, will stopAdding 1 to the value of (1) to add the vertex->Restoring to an initial value;
s4-11, repeating the steps S4-9 and S4-10 for the total distanceUpdating to obtain truck path set +.>Set with unmanned plane path->Corresponding total distance->。
As shown in fig. 6, step S4-2 judges whether the fused unmanned aerial vehicle path is feasible or not as follows:
If the departure point and the landing point of the fused unmanned aerial vehicle path are accessed by different trucks respectively, the fused unmanned aerial vehicle path is not feasible;
if the flying spot and the landing point of the fused unmanned aerial vehicle path are accessed by the same truck and the flying spot and the landing point of the fused unmanned aerial vehicle path are different, the truck accesses the landing point of the unmanned aerial vehicle path first and then accesses the flying spot of the unmanned aerial vehicle path, and the fused unmanned aerial vehicle path is not feasible;
the number constraint of unmanned aerial vehicles in the step S4-3 is as follows:
let the feasible unmanned plane path be a truckUnmanned aerial vehicle on the truck is accessed, and truck +.>Corresponding truck path>Truck->Sequential access to truck stops->Flying spot of feasible unmanned plane path +.>I.e.Then according to the formula:
obtaining an initial unmanned aerial vehicle path set；
In initial unmanned path setFind out a device with different flying and landing points, respectively +.>Unmanned plane path set for flying spot and falling spot>And->According to the following:
judging truckLeave truck dock->The number of unmanned aerial vehicles carried at the time ∈>Whether or not to be less than or equal to the nothing carried by each truckMan-machine number->The method comprises the steps of carrying out a first treatment on the surface of the If yes, the number constraint of the unmanned aerial vehicle is met; otherwise, the number constraint of the unmanned aerial vehicle is not satisfied; wherein, Indicating truck->Flying from other truck stop to truck stop +.>Unmanned aerial vehicle number->Indicating truck->From truck dock->Number of unmanned aerial vehicles taking off and landing to other truck stops, +.>Indicating truck->At the exit truck stop->The number of unmanned aerial vehicles carried in the back is calculated by the following steps:
obtaining the truckAt the exit truck stop->The number of unmanned aerial vehicles carried in the rear part>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Representing the landing point with different departure and landing points and stopping with a truck +.>Unmanned plane path set for flying spot, < ->Indicating truck->From truck dock->The number of unmanned aerial vehicles taking off and landing to other truck stopping points;
if it isThen->The method comprises the steps of carrying out a first treatment on the surface of the Otherwise, will->Is added to 1 and is according to the formula:
sequentially calculating trucksLeave truck dock->The number of unmanned aerial vehicles carried->Up to->The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>The initial value is 1->Indicating truck->Leave truck dock->Number of unmanned aerial vehicles carried, < > or->Representing the landing point with different departure and landing points and stopping with a truck +.>Unmanned plane path set for landing point, +.>Representing the stop in truck with different departure and landing points +.>To reduce the number of unmanned paths at the drop point,representing the landing point with different departure and landing points and stopping with a truck +. >A collection of unmanned aerial vehicle paths that are flying spots,representing the stop in truck with different departure and landing points +.>Number of unmanned paths as flying spots.
As shown in fig. 7 and 8, step S5 further includes:
s5-1, according to unmanned aerial vehicle path setTruck Path set->Truck number record array->Acquiring a unmanned aerial vehicle path set>The corresponding formula is:
wherein,indicate->Unmanned path->Indicate->The>Client Point, unmanned plane Path set->Initially empty;
s5-2, initializingValue and according to the unmanned plane path set corresponding to each truck +.>Obtaining two sizes asStatus identification matrix +.>And->The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>；
S5-3, unmanned aerial vehicle path set corresponding to each truckSearching to obtain the stop point of the truck>Unmanned plane path set for flying spot +.>And initialize +.>；
S5-4, based on state identification matrixAnd->The unmanned plane path set is sequentially subjected to +.>Distributing each unmanned aerial vehicle path, and judging whether the flying point and the landing point of each distributed unmanned aerial vehicle path are the same; if yes, entering a step S5-5; otherwise, enter step S5-6;
s5-5, according to the formula:
Unmanned aerial vehicle pathDistribution to unmanned plane->And update truck +.>Unmanned aerial vehicle->Unmanned plane path set->And a status identification matrix->Step S5-7 is carried out;
s5-6, according to the formula:
judging unmanned aerial vehicle pathWhether or not to insert into a truck->Unmanned aerial vehicle->Unmanned plane path set->The method comprises the steps of carrying out a first treatment on the surface of the If yes, according to the formula:
unmanned aerial vehicle pathDistribution to unmanned plane-> And update truck +.>Unmanned aerial vehicle->Unmanned plane path set->Status identification matrix->Unmanned aerial vehicle->At truck dock set->Status identification matrix +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Indicate and/or->Representing the position of the landing point of the unmanned aerial vehicle in the truck path;
s5-7, judging the currentWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S5-8; otherwise, will->Adding 1 to the value of (2) and returning to the step S5-4;
s5-8, judging the currentWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S5-9; otherwise, will->Adding 1 to the value of (2) and returning to the step S5-3;
s5-9, judging the currentWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, obtaining the distributed unmanned plane path set +.>The method comprises the steps of carrying out a first treatment on the surface of the Otherwise, will->Add 1 to the value of (c) and return to step S5-2.
State identification matrix of step S5-2Describing the use state of each stop point of the unmanned aerial vehicle on a truck path when the departure point and the landing point of the unmanned aerial vehicle are different; the use states are four states, namely:
Truck with a frameUnmanned aerial vehicle->At truck stop->Do not perform any operation ∈>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Indicating truck->Unmanned aerial vehicle->At truck stop->State of (2);
truck with a frameUnmanned aerial vehicle->At truck stop->Executing a take-off or landing operation；
Truck with a frameUnmanned aerial vehicle->At truck stop->It needs to execute one landing and take off again, then；
Truck with a frameUnmanned aerial vehicle->Without passing or landing at truck stop +.>Then->；
Define two sizes asMatrix of->And->The method comprises the steps of carrying out a first treatment on the surface of the Initially, truck number>Matrix->Andis a zero matrix;
step S5-2 of State identification matrixThe method is used for the number of take-off times of the unmanned aerial vehicle at the take-off point of the unmanned aerial vehicle when the unmanned aerial vehicle route has the same take-off point and landing point.
Step S6 further comprises:
s6-1, according to the formula:
obtaining a current optimal truck path setCurrent optimal unmanned plane path set>Current optimal total distance->Current optimal truck stop set +.>And iteration number +.>；
S6-2, according to the formula:
get removed truck dockTruck dock set->；
S6-3, gathering truck stop pointsThe same method as the steps S2 to S4 is adopted as a parameter, and a corresponding truck path set and unmanned aerial vehicle path set are obtained;
S6-4, gathering truck stop pointsAs a parameter, judging whether to generate a feasible solution by adopting the same method as that of the steps S2-2 to S2-4; if yes, entering a step S6-5; otherwise, enter step S6-7;
s6-5, judging based on truck stop point setThe total distance obtained>Whether or not it is smaller than the current optimal total distance +.>The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S6-6; otherwise, enter step S6-7;
s6-6, according to the formula:
for the current optimal truck path setUnmanned plane path set->Current optimum total distanceCurrent optimal truck stop set +.>Updating;
s6-7, judging the iteration timesWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S6-8; otherwise, iteration times->Adding 1 and returning to the step S6-2;
s6-8, judging the current optimal total distanceWhether or not is less than->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S6-9; otherwise, obtaining an optimal truck path set corresponding to each truck, an optimal unmanned aerial vehicle path set and an optimal total distance of corresponding truck unmanned aerial vehicles;
s6-9, repeating the step S5 to obtain a flight path set of each unmanned aerial vehicleGathering truck paths->Assignment as the current optimal truck Path set +.>The distributed unmanned plane path set +.>Assigned as the flight path set of each unmanned plane +. >Total distance +.>Assigning a current optimal total distance +.>Gathering truck stops->Assigning a value as the current optimal truck dock set +.>And returns to step S6-1.
In one embodiment of the invention, the vertex is the location of a customer point or truck dock on a map.
Experimental test is carried out on 3.10GHz and 8GB memories of Intel Kuri 5-10500H processor, algorithm is written by Matlab 2020, PMMA, PNIA, VMMA, VNIA and HCWA are adopted to compare with the algorithm PCWA provided by the invention, and the number of unmanned aerial vehicles is differentLoad capacity of different unmanned aerial vehicles>Pounds and number of different customer points->Is carried out in 9 scenes of (2) and assumes that the number of trucks in each scene is 3 and the maximum flight distance of each unmanned aerial vehicle is +.>The speed of the truck is 1500 m, the speed of the truck is equal to the speed of the unmanned plane, the warehouse points corresponding to each truck are selected from 35 truck stopping points which are uniformly distributed, and the range of the areas of the client points and the truck stopping points of 9 scenes is equal to the size of the area of the truck stopping points>In 20 examples in each scene, the distribution of truck stop points and client points ensures that each client point can be unmannedAnd (5) machine service. Wherein PMMA is fused with Prim clustering strategy and minimum marginal cost algorithm, PNIA is fused with Prim clustering strategy and nearest neighbor interpolation algorithm, VMMA is fused with Voronoi clustering strategy and minimum marginal cost algorithm, VNIA is fused with Voronoi clustering strategy and nearest neighbor interpolation algorithm, the four algorithms all use iterative optimization strategy in the invention, and HCWA is obtained by adjusting a mathematical model and algorithm extracted in a heuristic method.
In FIG. 9, whenThe total distance of PCWA is greater than the total distance of PNIA, VMMA, VNIA and HCWA; in other cases, the total distance of PCWA is less than the total distance of other algorithms. In fig. 10, 11, 13, 14, 16 and 17, the total distance of PCWA is less than that of other algorithms. In FIG. 12, when->The total distance of PCWA is less than the total distance of PNIA, VMMA, VNIA; when->The total distance of PCWA is greater than the total distance of PMMA, PNIA, VMMA, VNIA and HCWA; in other cases, the total distance of PCWA is less than the total distance of other algorithms. In FIG. 15, when->The total distance of PCWA is less than the total distance of PNIA, VMMA, VNIA; when->The total distance of PCWA is greater than the total distance of PMMA, PNIA, VMMA, VNIA and HCWA; in other cases, the total distance of PCWA is less than the total distance of other algorithms. Wherein each six identifications in fig. 9-17 are PMMA, PNIA, VMMA, VNIA, HCWH and PCWA, respectively.
Table 1 each algorithm solves for the average run time of 20 different examples
As shown in table 1, in any case, the average run time of PCWA is much smaller than that of the other 5 algorithms.
In summary, the method for constructing the solution and the method for optimizing the solution are coupled together, and the correlation between the unmanned plane path and the truck path is considered, so that the quality of the path is improved; advancing the current solution along the direction of solution optimization so as to avoid the problem of overlong searching time in a solution space for advancing the solution along the direction of optimization in the existing multi-stage heuristic algorithm, improve the efficiency of path allocation and improve the problem of long time consumption of the algorithm; the problem that each truck can only carry one unmanned aerial vehicle is solved.
Claims (8)
1. A multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving is characterized in that: the method comprises the following steps:
s1, acquiring a client point set and a truck parking point set;
s2, calculating a client point set and a truck stop point position set to obtain an conservation matrix among all client points;
s3, acquiring a truck path set according to the saving matrix among the client points;
s4, acquiring an unmanned aerial vehicle path set according to the truck path set;
s5, calculating based on the truck path set and the unmanned aerial vehicle path set to obtain a path set corresponding to each unmanned aerial vehicle and a total distance of the corresponding truck unmanned aerial vehicle; the path sets corresponding to the unmanned aerial vehicles are distributed unmanned aerial vehicle path sets;
s6, carrying out iterative optimization on the truck path set, the allocated unmanned aerial vehicle path set and the total distance of the corresponding truck unmanned aerial vehicle to obtain an optimal truck path set corresponding to each truck, an optimal unmanned aerial vehicle path set and the optimal total distance of the corresponding truck unmanned aerial vehicle;
the step S2 further includes:
s2-1, according to the client point setTruck dock set +.>Acquiring Euclidean distance matrix between each client point and each truck stop point >The method comprises the steps of carrying out a first treatment on the surface of the Wherein the client Point set->，/>Representing the number of customer points, truck dock set +.>Initially the truck dock set->，/>Representing the number of trucks given +.>Representing a given number of truck stops;
s2-2, utilizing Prim clustering algorithm to gather client pointsAnd truck dock set->Clustering to obtain truck stop point set clustered to each client point>；
S2-3, according to the formula:
obtaining a customer pointAnd corresponding clustered truck stop ∈>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Representing customer points->The vertex is represented as such,representing customer points->And vertex->Euclidean distance of>Representing the maximum flight distance of the unmanned aerial vehicle, +.>Representing the variable value corresponding to the minimum value, < ->Representing a set of client points that have not been clustered, and +.>Initial value is client point set->，Representation clustered to truck dock +.>Is>Indicate->A truck stop;
s2-4, judging the client pointWhether or not it is feasible; if yes, entering a step S2-5; otherwise, ending the operation;
s2-5, enabling truck stop points to be gatheredIs->And according to the formula:
updating to obtain updated client point setUpdated truck stop set +.>Updated customer point->Corresponding clustered truck stops +. >；
S2-6, judging updated client point setWhether it is an empty set; if yes, entering a step S2-7; otherwise, returning to the step S2-2;
s2-7, according to the formula:
obtain the firstIndividual client Point->And->Individual client Point->Distance cost saving value of the path formed between them +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein,the initial value is 1->Representation clustered to customer point->Truck stop point (I)>Representation clustered to customer point->Truck stops;
if it isThe client point is->Customer Point->Corresponding distance cost saving value +.>Record to saving matrixWill save matrix +.>Current total number of lines->The corresponding formula is:
wherein,the initial value is 1, saving matrix->The initial value is an empty set;
s2-8, judgment reference numeralsWhether or not equal to the number of customer points->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S2-9; otherwise, the label->Adding 1 and returning to the step S2-7;
s2-9, saving matrix from third column to last columnAccording to the value of the third column, descending order is performed to obtain the saving matrix +.>；
The step S6 further includes:
s6-1, according to the formula:
obtaining a current optimal truck path setCurrent optimal unmanned plane path set>Current optimal total distance->Currently optimal truck dock Point set->And iteration number +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Representing a set of truck paths, +.>Representing the allocated set of unmanned paths, +.>Indicating the total distance of the truck drone,representing a set of truck dock locations,/->Representing a given number of trucks;
s6-2, according to the formula:
get removed truck dockTruck dock set->；
S6-3, gathering truck stop pointsAs a parameter and adopting the same method as the steps S2 to S4, obtaining a corresponding truck path setAnd a unmanned aerial vehicle path set;
s6-4, gathering truck stop pointsAs a parameter, judging whether to generate a feasible solution by adopting the same method as that of the steps S2-2 to S2-4; if yes, entering a step S6-5; otherwise, enter step S6-7;
s6-5, judging based on truck stop point setThe total distance obtained>Whether or not it is smaller than the current optimum total distanceThe method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S6-6; otherwise, enter step S6-7;
s6-6, according to the formula:
for the current optimal truck path setUnmanned plane path set->Current optimal total distance->Current optimal truck stop set +.>Updating;
s6-7, judging the iteration timesWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S6-8; otherwise, iteration times- >Adding 1 and returning to the step S6-2; wherein (1)>Representing truck Path set +.>Is a total number of stops;
s6-8, judging the current optimal total distanceWhether or not is less than->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S6-9; otherwise, obtaining an optimal truck path set corresponding to each truck, an optimal unmanned aerial vehicle path set and an optimal total distance of corresponding truck unmanned aerial vehicles;
s6-9, repeating the step S5 to obtain a flight path set of each unmanned aerial vehicleGathering truck paths->Assignment as the current optimal truck Path set +.>The distributed unmanned plane path set +.>Assigned as the flight path set of each unmanned plane +.>Total distance +.>Assigning a current optimal total distance +.>Gathering truck stops->Assigning a value as the current optimal truck dock set +.>And returns to step S6-1.
2. The multi-truck multi-unmanned aerial vehicle mission allocation method based on mileage and marginal cost according to claim 1, wherein: the step S3 further includes:
s3-1, according to the updated truck stop point setAcquiring Euclidean distance matrix between stop points>；
S3-2, according to the truck stop point set clustered to each client pointConstructing an initial unmanned aerial vehicle path set +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1) >，/>；
S3-3, orderWherein->Represents the current set of unmanned paths, +.>Representing a current savings matrix;
s3-4, judging the current saving matrixWhether it is an empty set; if yes, entering a step S3-12; otherwise, enter step S3-5;
s3-5, according to the formula:
removing savings matrixAnd in the unmanned plane path set +.>Searching to obtain updated saving matrix +.>Respectively and client point->And customer Point->Corresponding unmanned plane path->And->；
S3-6, according to customer pointAnd->In unmanned plane path->And->In (2) position determination unmanned plane path +.>And->Whether to perform fusion or not; if yes, entering a step S3-7; otherwise, returning to the step S3-4;
s3-7, according to the formula:
unmanned aerial vehicle pathAnd->Fusing to obtain a fused unmanned plane path +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein the method comprises the steps of，/>Representing unmanned path->Ordered vertex set in->Representing unmanned path->Ordered vertex set in->And->Respectively represent unmanned plane path->And->Is the total number of vertices;
s3-8, judging the fused unmanned aerial vehicle pathWhether the maximum flight distance constraint and the load constraint of the unmanned aerial vehicle are simultaneously met; if yes, entering a step S3-9; otherwise, returning to the step S3-4;
S3-9, willAs a current unmanned path set +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein,is indicated at->Remove->；
S3-10, judging the fused unmanned aerial vehicle pathIs>And landing Point->Whether or not the same; if yes, returning to the step S3-4; otherwise, enter step S3-11;
s3-11, according to the formula:
updating Euclidean distance matrix between stop pointsThe method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Representing a fused unmanned path +.>Is the total number of vertices;
s3-12, utilizing a minimum marginal algorithm and according to the formula:
obtaining the path of each truckAnd update the truck dock set +.>And truck path->The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Indicates the truck number>Representing truck dock +.>Assigned truck number,/->Representing truck dock +.>Insertion into truck pathIs (are) located>Representing truck dock +.>Insert into truck path->Is>Truck after individual position->Path of->Indicating the total distance corresponding to the truck path, +.>Representation based on Euclidean distance matrix->Traversing a computed truck pathIs>Representing the client point +.>An assigned truck number record array;
s3-13, repeating the step S3-12 until the truck stops are gatheredFor empty sets, a set of truck paths is obtained.
3. The multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost according to claim 2, wherein: the fusion judgment standard of the step S3-6 is as follows:
If the client pointsAnd->Located in the same unmanned plane path, i.e.)>No fusion is performed;
if in unmanned plane pathCustomer point (S)>Not the first customer point served by the unmanned aerial vehicle, nor the last customer point served by the unmanned aerial vehicle, then do not merge;
if in unmanned plane pathCustomer point (S)>Not the first customer point served by the unmanned aerial vehicle, nor the last customer point served by the unmanned aerial vehicle, then do not merge;
if in unmanned plane pathCustomer point (S)>And in unmanned path->Customer point (S)>Neither the first nor the last client point served by the drone, no fusion is performed.
4. The multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost according to claim 2, wherein: the maximum flight distance constraint of the unmanned aerial vehicle in the step S3-8 is as follows:
according to the formula:
obtaining a fused unmanned plane pathThe current unmanned plane corresponding to each vertex of the list is integrated with the flight distance +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>、/>Respectively represent +.>Vertex and->Vertex(s)>Indicate->Apexes->And->Apexes->Euclidean distance between them;
sequentially judging the accumulated flight distance of the current unmanned aerial vehicle corresponding to each vertex Whether or not it is greater than the maximum flight distance of the unmanned aerial vehicleThe method comprises the steps of carrying out a first treatment on the surface of the If the fused unmanned plane path is +>The current unmanned plane corresponding to the last vertex of the pair of unmanned plane is integrated with the flight distance +.>Less than or equal to the maximum flight distance of the unmanned aerial vehicle>The maximum flight distance constraint of the unmanned aerial vehicle is met, otherwise, the maximum flight distance constraint of the unmanned aerial vehicle is not met;
the unmanned aerial vehicle loading constraint of the step S3-8 is as follows:
according to the formula:
sequentially obtaining fused unmanned aerial vehicle pathsTotal amount of packages corresponding to each vertex in +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Indicate->Vertex(s)>Indicate->Apexes->The weight of the package to be delivered;
according to the formula:
obtaining unmanned aerial vehicle path after leaving fusion of unmanned aerial vehicleMiddle->Weight of package carried by individual customer points: wherein (1)>Indicate->Apexes->The weight of the package to be collected;
judging fused unmanned plane pathThe wrap total amount array of each vertex in (1)>Whether the elements are greater than the portable maximum package weight +.>The method comprises the steps of carrying out a first treatment on the surface of the If yes, the unmanned aerial vehicle load constraint is not satisfied; otherwise, the unmanned aerial vehicle load constraint is satisfied.
5. The multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost according to claim 2, wherein: the step S4 further includes:
S4-1, repeating the steps S3-3 to S3-8 according to a mileage saving algorithm to obtain a fused unmanned plane path meeting the maximum flight distance constraint and the load constraint of the unmanned plane;
s4-2, judging whether the fused unmanned aerial vehicle path meeting the maximum flight distance constraint and the load constraint of the unmanned aerial vehicle is feasible or not; if yes, obtaining a feasible unmanned aerial vehicle path and entering a step S4-3; otherwise, returning to the step S4-1;
s4-3, judging whether the feasible unmanned aerial vehicle paths meet the number constraint of unmanned aerial vehicles or not; if yes, entering a step S4-4; otherwise, returning to the step S4-1;
s4-4, updating the unmanned aerial vehicle path set according to the formula of the step S3-9；
S4-5, judging saving matrixWhether or not it is an empty setThe method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S4-6; otherwise, returning to the step S4-1;
s4-6, according to the formula:
obtaining the truckAlong the truck path>Is>And will->The value of (2) is added to 1; wherein, truck number->The initial value is 1, total distance->The initial value is 0->Representing truck Path set +.>Is a total number of stops;
s4-7, as a stop pointAt the time, stop point->Restoring to the initial value, and +.>The value of (2) is added to 1;
s4-8, repeating the steps S4-6 and S4-7, and obtaining all total distancesAdding to get truck path set- >Is>；
S4-9, according to the formula:
performing calculation until reaching vertexObtaining a total distance plus the distance travelled on the unmanned path +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein, vertex->Initial value is 2, total distance->The initial value is +.>，/>Representing unmanned path set->Vertex sum of (2)A number;
s4-10, will stopAdding 1 to the value of (1) to add the vertex->Restoring to an initial value;
s4-11, repeating the steps S4-9 and S4-10 for the total distanceUpdating to obtain truck path set +.>Set with unmanned plane path->Corresponding total distance->。
6. The multi-truck multi-unmanned aerial vehicle mission allocation method based on mileage and marginal cost according to claim 5, wherein: the step S4-2 judges whether the fused unmanned aerial vehicle path is feasible or not according to the following criteria:
if the departure point and the landing point of the fused unmanned aerial vehicle path are accessed by different trucks respectively, the fused unmanned aerial vehicle path is not feasible;
if the flying spot and the landing point of the fused unmanned aerial vehicle path are accessed by the same truck and the flying spot and the landing point of the fused unmanned aerial vehicle path are different, the truck accesses the landing point of the unmanned aerial vehicle path first and then accesses the flying spot of the unmanned aerial vehicle path, and the fused unmanned aerial vehicle path is not feasible;
The number constraint of unmanned aerial vehicles in the step S4-3 is as follows:
let the feasible unmanned plane path be a truckUnmanned aerial vehicle on the truck is accessed, and truck +.>Corresponding truck path>Truck->Sequential access to truck stops->Flying spot of feasible unmanned plane path +.>I.e.Then according to the formula:
obtaining an initial unmanned aerial vehicle path set；
In initial unmanned path setFind out a device with different flying and landing points, respectively +.>Unmanned plane path set for flying spot and falling spot>And->According to the following:
judging truckLeave truck dock->The number of unmanned aerial vehicles carried at the time ∈>Whether or not the number of unmanned aerial vehicles carried by each truck is less than or equal to +.>The method comprises the steps of carrying out a first treatment on the surface of the If yes, the number constraint of the unmanned aerial vehicle is met; otherwise, the number constraint of the unmanned aerial vehicle is not satisfied; wherein,indicating truck->Flying from other truck stop to truck stop +.>Unmanned aerial vehicle number->Indicating truck->From truck dock->Number of unmanned aerial vehicles taking off and landing to other truck stops, +.>Indicating truck->At the exit truck stop->The number of unmanned aerial vehicles carried in the back is calculated by the following steps:
obtaining the truckAt the exit truck stop->The number of unmanned aerial vehicles carried in the rear part>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1) >Representing the landing point with different departure and landing points and stopping with a truck +.>Unmanned plane path set for flying spot, < ->Indicating truck->From truck dock->The number of unmanned aerial vehicles taking off and landing to other truck stopping points;
if it isThen->The method comprises the steps of carrying out a first treatment on the surface of the Otherwise, will->Is added to 1 and is according to the formula:
sequentially calculating trucksLeave truck dock->The number of unmanned aerial vehicles carried->Up to->The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>The initial value is 1->Indicating truck->Leave truck dock->Number of unmanned aerial vehicles carried, < > or->Representing the landing point with different departure and landing points and stopping with a truck +.>Unmanned plane path set for landing point, +.>Representing the stop in truck with different departure and landing points +.>Unmanned plane path number for falling point, +.>Representing the landing point with different departure and landing points and stopping with a truck +.>Unmanned plane path set for flying spot, < ->Representing the stop in truck with different departure and landing points +.>Number of unmanned paths as flying spots.
7. The multi-truck multi-unmanned aerial vehicle mission allocation method based on mileage and marginal cost according to claim 6, wherein: the step S5 further includes:
s5-1, according to unmanned aerial vehicle path set Truck Path set->Truck number record array->Acquiring a unmanned aerial vehicle path set>The corresponding formula is:
wherein,indicate->Unmanned path->Indicate->The>Client Point, unmanned plane Path set->Initially empty;
s5-2, initializingValue and according to the unmanned plane path set corresponding to each truck +.>Two sizes of +.>Status identification matrix +.>And->The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>；
S5-3, unmanned aerial vehicle path set corresponding to each truckSearching to obtain the stop point of the truck>Unmanned plane path set for flying spot +.>And initialize +.>；
S5-4, based on state identification matrixAnd->The unmanned plane path set is sequentially subjected to +.>Each unmanned plane path is distributed, and each distributed unmanned plane path is judgedWhether the flying point and the landing point of the unmanned plane path are the same; if yes, entering a step S5-5; otherwise, enter step S5-6;
s5-5, according to the formula:
unmanned aerial vehicle pathDistribution to unmanned plane->And update truck +.>Unmanned aerial vehicle->Unmanned aerial vehicle path collection of (a)And a status identification matrix->Step S5-7 is carried out;
s5-6, according to the formula:
judging unmanned aerial vehicle pathWhether or not to insert into a truck- >Unmanned aerial vehicle->Unmanned plane path set->The method comprises the steps of carrying out a first treatment on the surface of the If yes, according to the formula:
unmanned aerial vehicle pathDistribution to unmanned plane->And update truck +.>Unmanned aerial vehicle->Unmanned aerial vehicle path collection of (a)Status identification matrix->Unmanned aerial vehicle->At truck dock set->Status identification matrix +.>The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Indicate and/or->Representing the position of the landing point of the unmanned aerial vehicle in the truck path;
s5-7, judging the currentWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S5-8; otherwise, will->Adding 1 to the value of (2) and returning to the step S5-4;
s5-8, judging the currentWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, entering a step S5-9; otherwise, will->Adding 1 to the value of (2) and returning to the step S5-3;
s5-9, judging the currentWhether or not equal to->The method comprises the steps of carrying out a first treatment on the surface of the If yes, obtaining the distributed unmanned plane path set +.>The method comprises the steps of carrying out a first treatment on the surface of the Otherwise, it willAdd 1 to the value of (c) and return to step S5-2.
8. The multi-truck multi-unmanned aerial vehicle mission allocation method based on mileage and marginal cost according to claim 7, wherein: the state identification matrix of the step S5-2Describing the use state of each stop point of the unmanned aerial vehicle on a truck path when the departure point and the landing point of the unmanned aerial vehicle are different; the using states are four states, namely:
Truck with a frameUnmanned aerial vehicle->At truck stop->Do not perform any operation ∈>The method comprises the steps of carrying out a first treatment on the surface of the Wherein,indicating truck->Unmanned aerial vehicle->At truck stop->State of (2);
truck with a frameUnmanned aerial vehicle->At truck stop->Execute a take-off or landing operation, then +.>；
Truck with a frameUnmanned aerial vehicle->At truck stop->It needs to execute one landing and take off again, then；
Truck with a frameUnmanned aerial vehicle->Without passing or landing at truck stop +.>Then->；
Define two sizes asMatrix of->And->The method comprises the steps of carrying out a first treatment on the surface of the Initially, truck number>Matrix->And->Is a zero matrix;
the state identification matrix of the step S5-2The method is used for the number of take-off times of the unmanned aerial vehicle at the take-off point of the unmanned aerial vehicle when the unmanned aerial vehicle route has the same take-off point and landing point.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311385838.2A CN117114375B (en) | 2023-10-25 | 2023-10-25 | Multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311385838.2A CN117114375B (en) | 2023-10-25 | 2023-10-25 | Multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN117114375A CN117114375A (en) | 2023-11-24 |
| CN117114375B true CN117114375B (en) | 2024-03-15 |
Family
ID=88806075
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202311385838.2A Active CN117114375B (en) | 2023-10-25 | 2023-10-25 | Multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117114375B (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117726059B (en) * | 2024-02-08 | 2024-04-30 | 深圳大学 | Truck unmanned aerial vehicle task allocation method under time window constraint |
| CN118378981B (en) * | 2024-06-21 | 2024-10-11 | 深圳大学 | Multi-truck multi-unmanned aerial vehicle task allocation method based on improved variable neighborhood descent |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US10956855B1 (en) * | 2015-08-16 | 2021-03-23 | Palidian Incorporated | Integrated multi-location scheduling, routing, and task management |
| CN112945255A (en) * | 2021-01-29 | 2021-06-11 | 中国人民解放军国防科技大学 | Method and system for planning multi-area coverage path by cooperation of multiple unmanned aerial vehicles carried by automobile |
| CN114358675A (en) * | 2021-12-10 | 2022-04-15 | 浙江建德通用航空研究院 | Multi-unmanned aerial vehicle-multi-truck cooperative logistics distribution path planning method |
| CN114841582A (en) * | 2022-05-11 | 2022-08-02 | 浙江财经大学 | Truck and unmanned aerial vehicle cooperative distribution method |
| CN116502874A (en) * | 2023-06-27 | 2023-07-28 | 深圳大学 | Single-truck single-unmanned aerial vehicle task planning method based on marginal cost under time sequence constraint |
| CN116720642A (en) * | 2023-06-08 | 2023-09-08 | 合肥工业大学 | Method and system for optimizing path of cooperative distribution of vehicle and unmanned aerial vehicle |
-
2023
- 2023-10-25 CN CN202311385838.2A patent/CN117114375B/en active Active
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US10956855B1 (en) * | 2015-08-16 | 2021-03-23 | Palidian Incorporated | Integrated multi-location scheduling, routing, and task management |
| CN112945255A (en) * | 2021-01-29 | 2021-06-11 | 中国人民解放军国防科技大学 | Method and system for planning multi-area coverage path by cooperation of multiple unmanned aerial vehicles carried by automobile |
| CN114358675A (en) * | 2021-12-10 | 2022-04-15 | 浙江建德通用航空研究院 | Multi-unmanned aerial vehicle-multi-truck cooperative logistics distribution path planning method |
| CN114841582A (en) * | 2022-05-11 | 2022-08-02 | 浙江财经大学 | Truck and unmanned aerial vehicle cooperative distribution method |
| CN116720642A (en) * | 2023-06-08 | 2023-09-08 | 合肥工业大学 | Method and system for optimizing path of cooperative distribution of vehicle and unmanned aerial vehicle |
| CN116502874A (en) * | 2023-06-27 | 2023-07-28 | 深圳大学 | Single-truck single-unmanned aerial vehicle task planning method based on marginal cost under time sequence constraint |
Non-Patent Citations (3)
| Title |
|---|
| 基于卡车和无人机联合运输下的末端配送算法研究;承琦;李磊;;物流工程与管理;20200315(第03期) * |
| 基于卡车和无人机联合运输下的末端配送算法研究;承琦等;《物流工程与管理》;第42卷(第3期);第62-65页 * |
| 考虑时变路网的卡车与多架无人机协同配送路径规划问题;蔡乐;《中国优秀硕士学位论文全文数据库工程科技Ⅱ辑》;第C034-2页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN117114375A (en) | 2023-11-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN117114375B (en) | Multi-truck multi-unmanned aerial vehicle task allocation method based on mileage and marginal cost saving | |
| CN112833905B (en) | Distributed multi-AGV collision-free path planning method based on improved A-x algorithm | |
| CN110231040B (en) | Path planning method and device | |
| CN110858073B (en) | Dispatching method and dispatching device for automatic guided vehicles | |
| CN110567459B (en) | Path planning method and device | |
| CN116090931B (en) | Terminal distribution method and device based on customer classification | |
| CN110096838A (en) | A kind of helicopter flow field numerical value Parallel Implicit method for solving based on N-S equation | |
| CN111353107A (en) | Road network moving object-oriented continuous k neighbor query method and system | |
| CN109292347A (en) | Tiered warehouse facility intelligent control method and system | |
| CN118378981B (en) | Multi-truck multi-unmanned aerial vehicle task allocation method based on improved variable neighborhood descent | |
| CN116166690A (en) | Mixed vector retrieval method and device for high concurrency scene | |
| CN111736524A (en) | Multi-robot scheduling method, device and equipment based on time and space | |
| Chawla et al. | Material handling robots fleet size optimization by a heuristic | |
| CN103268633A (en) | Contour surface construction method for raster data | |
| CN113934217A (en) | Intelligent scheduling processing system based on 5G | |
| JPWO2020174663A1 (en) | Transport route design device, transport route design method, and program | |
| CN112001646A (en) | Material scheduling method and device, storage medium and electronic equipment | |
| CN117333099A (en) | Method, system and equipment for planning cooperative gathering and distribution path of truck and unmanned aerial vehicle | |
| CN117168488A (en) | Vehicle path planning method, device, equipment and medium | |
| CN111507652A (en) | Task path determination method and device | |
| CN109710633A (en) | The determination method, apparatus and intelligent terminal of go-between's information | |
| CN114355867B (en) | Multi-AGV collision-free and deadlock-free motion planning method and device | |
| CN116451961B (en) | Modeling optimization method for inter-city demand response type public transportation service | |
| EP4350661A1 (en) | Vehicle control method and apparatus, and system | |
| CN109325090A (en) | A kind of tile map display methods, system, terminal and storage medium |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |