CN113706081B

CN113706081B - Unmanned aerial vehicle picking and delivering system and method based on automatic express delivery device on city roof

Info

Publication number: CN113706081B
Application number: CN202111010035.XA
Authority: CN
Inventors: 伍国华; 洪芳宇
Original assignee: Central South University
Current assignee: Central South University
Priority date: 2021-08-31
Filing date: 2021-08-31
Publication date: 2024-07-16
Anticipated expiration: 2041-08-31
Also published as: CN113706081A

Abstract

The invention discloses an unmanned aerial vehicle picking and delivering system and method based on an automatic express device on a city roof, wherein the method comprises the following steps: acquiring position information and delivery information of multiple warehouses, multiple unmanned aerial vehicles and multiple client points; designing comprehensive scheduling problems of multiple centers, multiple client points and multiple unmanned aerial vehicles; assigning an initial task to the single center, and reassigning the task according to a plurality of neighborhood operators; finding a path planning scheme for completing tasks for each warehouse according to a plurality of neighborhood operators; the steps are iterated and interacted continuously, and a global optimal solution is found until an algorithm termination condition is met; and distributing the multi-unmanned aerial vehicle to take and deliver goods from multiple warehouses and multiple client points according to the global optimal solution. The invention fully utilizes the vacant space of the city; the unmanned plane can fly straight in the middle, and the taking and delivering efficiency is high; the competition of space backlog and queuing with the traditional picking and delivering is avoided; compared with the existing algorithm, the method can generate a high-quality scheduling scheme in reasonable time.

Description

Unmanned aerial vehicle picking and delivering system and method based on automatic express delivery device on city roof

Technical Field

The invention belongs to the technical field of logistics, and particularly relates to an unmanned aerial vehicle taking and delivering system and method based on an automatic express delivery device on a city roof.

Background

At present, most of unmanned aerial vehicles are applied to the research of package delivery problems and focus on the mode of independently using unmanned aerial vehicles or trucks and unmanned aerial vehicles, most of technical schemes focus on solving the package delivery problems, but with the increase of online shopping, reverse logistics caused by goods returning, goods changing and other services is lack of scientific solutions, and few technical schemes consider the package delivery and package pickup problems; more technical schemes utilize unmanned aerial vehicles to solve the last kilometer of packages, the mode of trucks and unmanned aerial vehicles is adopted, the form of automatic access equipment and unmanned aerial vehicles does not appear, and related technical scheme algorithms on solving the problem of unmanned aerial vehicle package taking and delivering are all in an integral solution mode. In solving the problem of large-scale task scheduling, the solutions generated by classical heuristic algorithms and meta-heuristic algorithms are not satisfactory, and it is difficult to generate a more satisfactory solution in a reasonable time.

Disclosure of Invention

In view of this, the present invention has studied a new model, which applies an Unmanned Aerial Vehicle (UAV) to a last kilometer logistics scene considering both pick-up and delivery, and this scheme sets the pick-up and delivery point on the roof, so that customers can pick up and send a piece as conveniently as possible, and the automation degree of the last kilometer is improved. The perfection of automatic storage devices and the maturation of unmanned aerial vehicle technology provide technical support for the invention. In this mode, we use the roof to set up multiple warehouses that can automatically access packages, assign customer points to each warehouse according to Euclidean distance, and then use the unmanned aerial vehicle group to complete the taking and delivering of packages at the same time, which is one mutil-drone parallel scheduling traveling salesmanproblem (mD-PSTSP). The scheduling problem of the package taking task of the multi-center, multi-client and multi-unmanned aerial vehicle which consider a plurality of constraints such as voyage, loading and the like can be considered.

The invention builds a mixed integer linear programming model of multi-warehouse, multi-unmanned aerial vehicle and multi-client point package taking and sending problems, proposes a two-stage optimization framework to help solve the original problems, and finally designs an SATO-SVND algorithm, and the method shows better performance in the aspect of processing large-scale task allocation and path planning problems.

The invention discloses an unmanned aerial vehicle taking and delivering system based on an automatic express delivery device on a city roof, which is characterized in that the automatic express delivery device is arranged on the city roof, and the unmanned aerial vehicle can fly in a straight line by utilizing the free space of the city, so that the competition with the space backlog and queuing of the traditional taking and delivering system is avoided, and the system comprises:

The system comprises a data input module, a data processing module and a data processing module, wherein the data input module is used for acquiring position information and delivery information of multiple warehouses, multiple unmanned aerial vehicles and multiple client points, and the client points are automatic goods express devices arranged on a roof;

The scheduling module is used for designing the comprehensive scheduling problem of multiple centers, multiple client points and multiple unmanned aerial vehicles based on unmanned aerial vehicle package taking and delivering and unmanned aerial vehicle weight and voyage;

The task allocation module allocates an initial task to the single center and reallocates the task according to a plurality of neighborhood operators;

the path planning module finds a path planning scheme for completing tasks for each warehouse according to a plurality of neighborhood operators;

the optimization module is used for continuously iterating the scheduling task allocation module and the path planning module, and searching a global optimal solution until an algorithm termination condition is met; setting a small cycle and a large cycle, wherein the small cycle generates a new scheduling scheme meeting constraint conditions, the large cycle performs local search on the basis of the scheduling scheme generated by the small cycle to form a new scheduling scheme, and then determines whether to accept a local search result according to a greedy principle;

and the goods taking and delivering module is used for distributing the multi-unmanned aerial vehicle to take and deliver goods from multiple warehouses and multiple client points according to the global optimal solution.

Further, the unmanned aerial vehicle goes to the next customer point or warehouse after loading and unloading goods, or automatically replaces the battery on the roof; for the client point only taking goods, arranging an unmanned aerial vehicle to start from the warehouse to take goods from the client point, and then returning to the warehouse; for a client point only for delivery, arranging an unmanned aerial vehicle to deliver goods from a warehouse to the client point, and after delivery, selecting the unmanned aerial vehicle to deliver goods to the next client point and then returning to the warehouse, or selecting the unmanned aerial vehicle to directly return to a nearby warehouse; for a customer point with simultaneous goods taking and delivering tasks, arranging a unmanned aerial vehicle to send goods from a warehouse, taking the goods at the customer point after unloading, and then returning to the warehouse.

Further, the task distribution module divides tasks into three types according to task types of client points, stores the task points which have only goods taking requirements and have no goods taking requirements into PICKUP sets, stores the task points which have only goods taking requirements and have no goods taking requirements into a DROP set, and stores the task points which have goods taking requirements and have goods taking requirements into a PICK-DROP set; after task classification is completed, task points in the PICKUP, DROP and PICK-DROP sets are generated by adopting a k-means algorithm to generate an initial task allocation scheme considering geographic positions.

Further, the neighborhood operators include 2-exchange, 3-exchange, 30% -exchange, relocation, other-relocation, and 10% -relocation.

Further, the 2-exchange operator operation method comprises the following steps: randomly selecting two task points i, j (i, j E Pickup) under a warehouse in a planned path, and exchanging the positions of the two client points i, j; the 3-exchange operator operation method comprises the following steps: three client points i, j, k (i, j, k E P_ckup) under a warehouse are randomly selected from the planned path, and then the positions of the three points i, j, k are randomly exchanged; the 30% -exchange operator specifically operates as follows: 30% of the customer points in the planned path are randomly selected and then the order of the customer points is randomly disturbed.

Further, the specific operation method of the Relocation operator is as follows: randomly selecting a client point i (i epsilon PICKUP) in the a warehouse, randomly selecting an insertion point in the existing path planning scheme of the b warehouse, and migrating the client point i into the path planning scheme of the b warehouse according to the constraint condition of the model; the specific operation method of the Other-relocation is as follows: selecting a client point i (i epsilon PICKUP U PICK-DROP) from all tasks allocated to the a warehouse, and randomly inserting the client point i into a path scheduling scheme of the b warehouse to be executed according to a model constraint condition; the specific operation method of 10% -relocation is as follows: and randomly selecting one warehouse at a time, and migrating the client points farthest from the warehouse according to the distance between the client points and the warehouse, wherein the number of the migrated client points is 20% of the total client points of the warehouse.

Further, the path planning module generates an initial solution S ₀, which specifically includes the following steps:

Generating a task allocation scheme of all warehouses: for the tasks distributed to each warehouse, the tasks are divided into three types of goods taking only, goods delivering only and goods taking and delivering tasks at the same time according to the characteristics of the tasks, and the tasks are respectively stored in three sets G _k-pick、G_k-drop、G_k -pick & drop, and the sets are initialized Storing a task sequence of a warehouse k; randomly taking out task points in the G _k -drop set, storing the task points in P _k, randomly taking out task points in the G _k -pick set, storing the task points in P _k, and finally storing the task points in the G _k -pick & drop set in P _k in sequence; the task sequences of all the warehouses are put together to obtain a processed task allocation scheme;

And (3) path planning: when constructing an initial solution, firstly assigning task points in a DROP set and a PICK-DROP set to different unmanned aerial vehicles, and then randomly assigning PICKUP types of task points to unmanned aerial vehicles which are already assigned with the DROP tasks or reassigning a new unmanned aerial vehicle for execution; a plurality of different path planning schemes are constructed based on the task allocation scheme, and a scheme with the minimum cost is selected as an initial solution according to a greedy principle.

Further, the unmanned aerial vehicle path scheduling scheme under each warehouse is re-planned according to the initial solution, and the method specifically comprises the following steps:

Given an initial solution s ₀, selecting one from 6 neighborhood operators to perform neighborhood search on the initial solution to form a new solution

Calculating the cost of a new solutionIf the cost of the new solution is less than the cost of the initial solution (s ₀), then the new solution is acceptedOtherwise accept the new solution with a certain probabilityAt the same time handleAssignment toIf the two conditions are not satisfied, the initial solution s ₀ is assigned toWill beStoring in the solution space S, updating the values of S ₀ and cost (S ₀);

Repeating the above steps until the loop termination condition is satisfied, and then finding the path planning scheme with the minimum cost from the solution space S As the current optimal scheduling scheme.

Further, a warehouse is randomly selected from the current optimal scheduling schemes, and the scheduling scheme of the warehouse is locally searched, and the method specifically comprises the following steps:

Classifying the client points to be executed in the selected warehouse: the customer points of the goods are classified into s _1k -pick; the customer points of the delivery only are classified into s _1k -drop; meanwhile, the client points of the pick-up and delivery tasks are classified into s _1k -pick & drop; when both s _1k -pick and s _1k -drop are not empty sets, classifying the client points of the unmanned aerial vehicle in s _1k -pick, which are sent from the warehouse to the client points of the warehouse and then returned to the warehouse, to pick ₁, and classifying the client points of the unmanned aerial vehicle in s _1k -drop set, which are sent from the warehouse to the client points and then returned to the warehouse, to drop ₁;

And randomly selecting a pick-only client point p ₁ and a delivery-only client point d ₁ from two sets of pick ₁ and drop ₁ respectively, combining the tasks originally assigned to the two unmanned aerial vehicles, and completing the tasks by one unmanned aerial vehicle.

The unmanned aerial vehicle goods taking and delivering method based on the automatic express device of the urban roof disclosed by the second aspect of the invention is applied to the system and comprises the following steps:

acquiring position information and delivery information of multiple warehouses, multiple unmanned aerial vehicles and multiple client points;

Designing comprehensive scheduling problems of multiple centers, multiple client points and multiple unmanned aerial vehicles based on unmanned aerial vehicle package taking and delivering, unmanned aerial vehicle weight and range;

Task allocation stage: assigning an initial task to the single center, and reassigning the task according to a plurality of neighborhood operators;

Path planning stage: finding a path planning scheme for completing tasks for each warehouse according to a plurality of neighborhood operators;

Continuously iterating the task allocation stage and the path planning stage of the interaction step, and searching a global optimal solution until an algorithm termination condition is met; setting a small cycle and a large cycle, wherein the small cycle generates a new scheduling scheme meeting constraint conditions, the large cycle performs local search on the basis of the scheduling scheme generated by the small cycle to form a new scheduling scheme, and then determines whether to accept a local search result according to a greedy principle;

and distributing the multi-unmanned aerial vehicle to take and deliver goods from multiple warehouses and multiple client points according to the global optimal solution.

The beneficial effects of the invention are as follows:

the vacant space of the city is fully utilized;

the straight line flight can be carried out in the middle, and the taking and delivering efficiency is high;

The competition with the traditional goods taking and delivering for space backlog and queuing is avoided;

compared with 6 heuristic and non-heuristic algorithms, the method generates a high-quality scheduling scheme in reasonable time, and is superior to other heuristic and meta-heuristic algorithms in solving quality and time efficiency.

Drawings

FIG. 1 is a flow chart of a two-stage optimization and iteration-based unmanned aerial vehicle pick-and-delivery method of the present invention;

FIG. 2 is a schematic diagram of a unmanned aerial vehicle pick-and-delivery system according to the present invention;

FIG. 3 is a coding scheme of the present invention;

FIG. 4 is a schematic view of a 2-exchange of the present invention;

FIG. 5 is a schematic illustration of the present invention prior to dispensing 10% -relocation;

FIG. 6 is a schematic illustration of the present invention after 10% -relocation dispensing;

FIG. 7 is a schematic view of a partial search of the present invention;

FIG. 8 is a graph showing how the SATO-SVND benefit of the present invention compares to the different algorithms;

FIG. 9 is a graph of the results of different algorithms;

FIG. 10 is a comparison of different algorithm runtimes;

FIG. 11 is a map marking of test points used in the present invention;

fig. 12 is an iterative descent graph of the present invention.

Detailed Description

The invention is further described below with reference to the accompanying drawings, without limiting the invention in any way, and any alterations or substitutions based on the teachings of the invention are intended to fall within the scope of the invention.

As shown in fig. 1, the unmanned aerial vehicle picking and delivering system based on two-stage optimization and iteration disclosed by the invention comprises the following steps:

The data input module acquires the position information and the delivery information of multiple warehouses, multiple unmanned aerial vehicles and multiple client points;

The scheduling module designs the comprehensive scheduling problem of multiple centers, multiple client points and multiple unmanned aerial vehicles based on unmanned aerial vehicle package taking and delivering and unmanned aerial vehicle weight and voyage;

the task allocation module: assigning an initial task to the single center, and reassigning the task according to a plurality of neighborhood operators;

and a path planning module: finding a path planning scheme for completing tasks for each warehouse according to a plurality of neighborhood operators;

And an optimization module: continuously iterating the interactive task allocation stage and the path planning stage, and searching a global optimal solution until an algorithm termination condition is met; setting a small cycle and a large cycle, wherein the small cycle generates a new scheduling scheme meeting constraint conditions, the large cycle performs local search on the basis of the scheduling scheme generated by the small cycle to form a new scheduling scheme, and then determines whether to accept a local search result according to a greedy principle;

and (5) taking a delivery module: and distributing the multi-unmanned aerial vehicle to take and deliver goods from multiple warehouses and multiple client points according to the global optimal solution.

The following section specifically illustrates the principles of the present invention.

Problem hypothesis

The unmanned aerial vehicle goods taking and delivering system for the last kilometer consists of multiple unmanned aerial vehicles and multiple automatic storing and taking devices. It is assumed that a plurality of unmanned aerial vehicle logistics centers are distributed in a city, each center is provided with a plurality of unmanned aerial vehicles, and each unmanned aerial vehicle logistics center can be used as a warehouse. The urban cell roof is taken as a delivery and delivery point of goods, and each delivery/delivery point is regarded as a client point. An automatic storage device and an automatic cargo handling device are arranged on the roof, and the unmanned aerial vehicle can go to the next place after the cargo is handled in a warehouse. Meanwhile, the unmanned aerial vehicle can automatically replace the battery on the roof, and the replaced battery is charged on the roof, so that the conveying efficiency and the unmanned aerial vehicle voyage are improved.

As shown in fig. 2, the present invention has a plurality of customer points, a plurality of warehouses, and a plurality of drones. In fig. 2, the drone has various routes, such as the drone may load goods from a warehouse to a customer point, after which the drone may choose to return to the nearest warehouse or to go to the next customer point; the unmanned aerial vehicle can go to a customer point from a warehouse to pick up goods and then return to the warehouse; the unmanned aerial vehicle can load goods from the warehouse to a client point, and if the client point has a task of taking goods, the unmanned aerial vehicle can unload the goods at the client point and reload the goods, and then return to the warehouse. The problem can be regarded as a comprehensive scheduling problem of multi-center, multi-client and multi-unmanned aerial vehicle taking into consideration unmanned aerial vehicle package taking, unmanned aerial vehicle weight and range. In the aspect of obstacle avoidance, non-patent literature "Huan Liu.An Autonomous Path Planning Method for Unmanned Aerial Vehicle Based on a Tangent Intersection and Target Guidance Strategy" proposes an automatic obstacle avoidance method for an unmanned aerial vehicle, when an obstacle is encountered, the method generates two paths between two points based on tangential line intersection and a target guiding strategy, and selects one path according to heuristic rules, so that a satisfactory collision-free path can be generated in an uncertain environment in near real time. Because the warehouse and the taking and delivering points are arranged on the roof of the city, and the unmanned aerial vehicle is less in obstacle, the invention mainly considers two aspects of task allocation and path planning, and the specific three-dimensional obstacle avoidance method can refer to the method. Aiming at the package taking and delivering problems of multi-center, multi-client and multi-unmanned aerial vehicle, the following assumptions are adopted:

(1) The goods transported by the unmanned aerial vehicle are packed by adopting special boxes with uniform size

(2) The remaining range becomes the maximum range after the battery is replaced by the unmanned aerial vehicle.

(3) The unmanned aerial vehicle flies to the customer point directly, and the battery is not changed by the midway detour and then goes to the customer point.

(4) The drone can only carry one parcel at a time.

(5) The unmanned aerial vehicle flies at a constant speed, and the energy consumption of taking off and landing of the unmanned aerial vehicle is not considered.

Objective function

Basic element description: depots set B: {1,2, …, m }, UAVset U: {1,2, …, k }, customer point set C = {1,2, …, c }. In order to describe three different task types of only picking, only delivering and simultaneously carrying out picking and delivering of the client, defining a set DROP of client points as client points of only delivering tasks; defining a set PICKUP of customer points as pick-only customer points; the set of client points PICK-DROP is defined as client points having both PICK-up and delivery tasks. To distinguish between two different operations of pick and delivery, we split each point in the customer set into two points, one describing the pick task and one describing the delivery task, i.e., C ^pick＝{1,2,...,c},C^drop = { c+1, c+2,..2C }. For example, originallyCorresponding to point i ε C ^pick and point i+c ε C ^drop. h is the maximum range of the unmanned aerial vehicle when no load exists.

TABLE 1 symbol definition

Sign symbol	Description of the invention
		B	Warehouse set, b= {1,2, …, m }
U	Unmanned plane set, u= {1,2, …, k }
		C	Client point set, c= {1,2, …, C }
i,j	Client index
		k	Unmanned aerial vehicle index
n	Task index
		u_k	UAVk cost of flight
T_i	Task type of client Point i
		c_n	Weighting of task n
c_max	Maximum capacity of unmanned aerial vehicle

Definition of the 0-1 variableIf drone k performs a delivery/pick-up task from customer point i to customer point j,OtherwiseDefining the flight distance of the d _i,j unmanned plane k from the client point i to the client point j; u _k is defined as the number of unmanned aerial vehicle starts.

An integer variable T _i is defined that represents the task type of client point i. Wherein, T _i = -1 represents that there is a delivery task at the customer point i, T _i = 0 represents that there is no delivery/pickup task at the customer point i, and T _i = 1 represents that there is a pickup task at the customer point i.

Definition of the definitionFor the maximum voyage of the unmanned aerial vehicle k when loading the cargo n. The flight time of the drone decreases linearly with increasing payload. Therefore, it can be assumed that there is a linear correlation between the range and the load of the unmanned aerial vehicle, and when the unmanned aerial vehicle k flies from the point i to the point j, the maximum range of the unmanned aerial vehicle decreases with the increase of the weight of the load carried by the unmanned aerial vehicle at this time, which is specifically expressed as follows:

the size of the payload can affect the energy consumption and flight range of the drone. At a fixed time, there is a linear correlation between the power decay and the load capacity of the unmanned aerial vehicle. The invention specifically expresses the cargo load penalty coefficient beta as follows:

Wherein β _max is the penalty factor maximum, c _max is the unmanned aerial vehicle maximum load, when the unmanned aerial vehicle is empty, β=1; when the drone is fully loaded, β=β _max.

Optimization objective of model: a first object of the invention is to ensure that the total flight distance of the unmanned aerial vehicle to service all customers and return to the warehouse is minimal; furthermore, the model is a mD-PSTSP problem, and the second optimization goal of the model is to complete tasks with as few unmanned aerial vehicles as possible, considering that each unmanned aerial vehicle is started with corresponding energy consumption and depreciation. The objective of the objective function is to minimize the total energy consumption of the drone and the weighted sum of the total number of drones.

Wherein alpha, ρ is the weight coefficient of unmanned aerial vehicle total distance of traveling, unmanned aerial vehicle start-up frame number.

Constraint conditions:

C1 (decision variables):

C2 (task point constraint):

and C3: the drone must start from the warehouse and eventually return to the warehouse:

C4 (service point constraint):

after the unmanned aerial vehicle delivers goods, the unmanned aerial vehicle can choose to go to the next goods taking point or warehouse; because the unmanned aerial vehicle can only carry one package at a time, the unmanned aerial vehicle must return to a warehouse immediately after picking up goods; for the optimal cost, the task points with the simultaneous presence of the taking and sending tasks are completed by one unmanned plane:

C5 (voyage constraint):

when the drone k loads the package n to fly from the customer point i to the customer point j, the maximum range of the drone cannot be exceeded.

Constraint 6:

load-carrying capacity constraint: the weight of the goods to be delivered taken by the unmanned aerial vehicle each time cannot exceed the maximum load of the unmanned aerial vehicle;

Wherein c _n is the weight of the nth customer point cargo.

The package taking and delivering problem of multiple centers, multiple customer points and multiple unmanned aerial vehicles is a very complex combination optimization problem. The invention designs a two-stage optimization method as a solution to the problem so as to improve the computing power.

Algorithm framework

As the number of client points increases, the computational complexity of mD-PSTSP increases dramatically. Traditional heuristic algorithms and meta-heuristic algorithms have difficulty finding high quality path planning schemes in a short time. Therefore, the invention designs a two-stage optimization method and is named SATO-SVND algorithm. The method decomposes the original multi-warehouse, multi-client and multi-unmanned aerial vehicle task scheduling problem into a plurality of simple single-center task scheduling problems, and then solves the respective path planning schemes independently. The algorithm consists of two phases: a task allocation stage for converting the multi-center task scheduling problem into a single-center task scheduling problem; and a single-center path planning stage, namely a path planning scheme stage for finding a completed task for each warehouse. To find a globally optimal solution, the two phases need to iterate interactions constantly.

The first stage of task distribution is carried out, the tasks are divided into three types according to the task types of the client points, the task points which have only the delivery requirements and have no delivery requirements are stored in PICKUP sets, the task points which have only the delivery requirements and have no delivery requirements are stored in a DROP set, and finally the task points which have the delivery requirements and have the delivery requirements are stored in a PICK-DROP set. After task classification is completed, task points in PICKUP, DROP and PICK-DROP sets are generated by adopting a k-means algorithm to generate an initial task allocation scheme considering geographic positions, and a multi-center task scheduling problem is converted into a single-center task scheduling problem. At this time, the task is distributed to each warehouse, and the result is an unordered state which cannot be directly delivered to the unmanned aerial vehicle for execution. Therefore, we need to make path planning.

In the second stage, a SVND algorithm containing 6 neighborhood operators is designed according to each single-center task allocation result, and a path planning scheme meeting constraint conditions is generated. At this time, all the central tasks are orderly, and all the central task scheduling schemes are integrated to be a complete task scheduling scheme which can be submitted to the unmanned aerial vehicle for execution. In order to adjust the existing scheme and obtain a better solution, the invention designs 3 operators such as 6 operators (2-exchange、3-exchange、30％-exchange、relocation、other-relocation、10％-relocation).2-exchange and 3-exchange、30％-exchange and the like to adjust a task allocation scheme in a warehouse, and tasks are exchanged between two or three unmanned aerial vehicles under the warehouse. relocation and other-relocation, 10% -relocation are task allocation schemes that adjust two warehouses to transfer tasks allocated to one warehouse point to another warehouse.

The two phases iterate until the algorithm termination condition is met. Two loop structures are arranged in the algorithm: the small loop uses a variable neighborhood search algorithm to generate a new scheduling scheme that satisfies the constraint. Judging whether a new scheduling scheme is accepted according to metropolis principles every time, if so, recording the new scheduling scheme until the number of the new scheduling schemes meets the preset number, wherein the recorded new scheduling scheme forms a solution space; the large cycle is to find the optimal scheduling scheme based on the solution space generated by the small cycle, and the temperature is reduced every time the cycle is performed until the temperature reaches the lowest temperature. In order to jump out the Local optimum, a Local Search algorithm is designed in the large loop, the current best solution found in each solution space needs to be subjected to Local Search again, the existing solution structure is destroyed through the Local Search algorithm, a new scheduling scheme is formed, and then whether the result of the Local Search is accepted is determined according to a greedy principle. The two-stage algorithm successfully converts multi-center mD-PSTSP into single-center mD-PSTSP, and the solving difficulty of the original problem is reduced.

TABLE 2SATO-SVND algorithm pseudocode

Coding mode

The scheduling scheme under each warehouse is defined to start from the warehouse to a task point and finally return to the warehouse; the unmanned aerial vehicle can directly return to the warehouse after sending to the task point of delivering goods from the warehouse or return to the warehouse after getting goods from the nearest goods taking point; because the drone can only carry one package at a time, the drone must return to the warehouse after picking up the goods. In summary, the unmanned plane has the following three paths: 1) The unmanned aerial vehicle starts from the warehouse, goes to a customer point to pick up goods, and then returns to the warehouse; 2) The unmanned aerial vehicle starts from the warehouse, goes to a customer point for delivering goods and then returns to the warehouse; 3) The unmanned aerial vehicle starts from the warehouse and goes to the customer point for delivery, and then returns to the warehouse after getting the delivery from the customer point.

In the prior art, when solving the path problem, the heuristic algorithm and the meta heuristic algorithm usually do not consider the warehouse point at first, only the client point to be accessed is encoded, the path is decoded under the condition that the distance cost, the fitness and the like are calculated later and the complete path is required, and the warehouse point is added to form the complete path. The invention adopts a new coding mode in consideration of the need of distinguishing three different situations of returning to the warehouse after taking goods from the warehouse to the client point, returning to the warehouse after sending goods from the warehouse to the client point, returning to the warehouse after taking goods from the client point and the like. As shown in FIG. 3, when encoding, each warehouse and customer site is uniquely numbered to distinguish between warehouse, customer site with only pick-up requirements, customer site with only delivery requirements and customer site with both pick-up and delivery requirements. The number of the warehouse is directly continued to be numbered on the basis of the number of the client points, and if the number of the last client point is x and the total number of the warehouse is m, the number of the warehouse points is x+1, x+2. The scheduling schemes of the individual warehouses are combined together to form a complete scheduling scheme.

Task allocation

(1) Task classification

Unlike parallel unmanned aerial vehicle scheduling traveller problem (PDSTSP), construction of solutions to multi-warehouse, multi-unmanned aerial vehicle parallel scheduling traveller problem (m-Drone-PSTSP WITH drop & pickup synchronization at Multi-drop) with simultaneous delivery requires distinguishing task types

(2) Initial task allocation

In the initial task allocation stage, a k-means clustering algorithm considering the geographic position is used for allocating client points to different warehouses, and the problem is converted into a single-center problem. Then, a single warehouse plans an unmanned aerial vehicle path, and the unmanned aerial vehicle is assigned to visit each client point to complete the picking and delivering task.

(3) Task reassignment

In order to optimize the initial task allocation result, an optimal scheduling scheme is found, and 6 neighborhood operators such as 2-exchange, 3-exchange, 30% -exchange, relocation and, other-relocation, 10% -relocation and the like are designed to redistribute the task allocation scheme.

① 2-Exchange: and exchanging the goods taking tasks distributed to the two unmanned aerial vehicles under the same warehouse. The specific operation method is as follows: and randomly selecting two task points i, j (i, j E Pickup) under a warehouse in the planned path, and exchanging the positions of the two client points i, j. The specific operation is shown in fig. 4.

② 3-Exchange: and exchanging delivery tasks allocated to three unmanned aerial vehicles under the same warehouse. The specific operation method is similar to that of 2-exchange: three client points i, j, k (i, j, k epsilon Pickup) under a warehouse are randomly selected from the planned path, and then the positions of the three points i, j, k are randomly exchanged.

③ 30% -Exchange: in the face of large-scale tasks, 2-exchange and 3-exchange are relatively low in optimizing efficiency, so that 30% -exchange is developed. When the number of client points served by a warehouse is greater than 10, we use 30% -exchange, which exchanges 30% of the client point access order under a single warehouse at a time. The specific operation is similar to 2-exchange: 30% of the customer points in the planned path are randomly selected and then the order of the customer points is randomly disturbed.

④ Relocation: and randomly selecting one picking task from all tasks allocated to the warehouse a, and transferring the picking task to the warehouse b for execution. The specific operation method is as follows: and randomly selecting a client point i (i epsilon PICKUP) in the a warehouse, randomly selecting an insertion point in the existing path planning scheme of the b warehouse, and migrating the client point i into the path planning scheme of the b warehouse according to the constraint condition of the model. As shown in fig. 5 and 6.

⑤ Other-relocation: and selecting a delivery task which is farthest from the warehouse from all tasks allocated to the warehouse a, and transferring the delivery task to the warehouse b for execution. The specific operation method is as follows: and selecting a client point i (i epsilon PICKUP U PICK-DROP) from all tasks allocated to the a warehouse, and randomly inserting the client point i into a path scheduling scheme of the b warehouse according to a model constraint condition to execute.

⑥ 10% -Relocation: similar to 30% -exchange we have developed 10% -relocation for handling large-scale tasks. When the number of customer points for warehouse service is greater than 20, we use 10% -relocation. The specific operation method is as follows: and randomly selecting one warehouse at a time, and migrating the client points farthest from the warehouse according to the distance between the client points and the warehouse, wherein the number of the migrated client points is 20% of the total client points of the warehouse.

Path planning

(1) Generating an initial solution

For convenience in solution, for a customer point with multiple pick/delivery package tasks, the customer point may be split into multiple customer points, with each customer point having at most one pick-up and one delivery task. For customer points with simultaneous pick-up and delivery requirements, it is provided that the pick-up and delivery tasks of such customer points are completed by the same unmanned aerial vehicle. Because the unmanned aerial vehicle can only load one package at a time, when the parallel unmanned aerial vehicle packages are distributed, the task points in the DROP and PICK-DROP sets all need to be independently loaded by the unmanned aerial vehicle from a warehouse to be delivered to a client; the task points in the PICK-DROP set have goods delivery tasks and simultaneously have goods taking tasks, so that the unmanned aerial vehicle can directly take goods in situ after goods in the PICK-DROP set are delivered; the unmanned aerial vehicle can load goods from a warehouse; after the unmanned aerial vehicle finishes delivering goods, the unmanned aerial vehicle can directly return to a warehouse or go to the next goods taking task point to take goods according to the needs; all drones must return to the warehouse for unloading after loading the cargo. The above is the path planning principle of the warehouse.

After the tasks are distributed, the tasks are in an unordered state, and the tasks are ordered to form an initial solution S ₀. For the tasks distributed to each warehouse, firstly, the tasks are divided into three types of goods taking only, goods delivering only, goods taking and goods delivering tasks at the same time according to the characteristics of the tasks, and the tasks are respectively stored in three sets G _k-pick、G_k-drop、G_k -pick & drop. Initializing a collectionThe task sequence of repository k is stored. And randomly taking out task points in the G _k -drop set, storing the task points in P _k, randomly taking out task points in the G _k -pick set, storing the task points in P _k, and finally storing the task points in the G _k -pick & drop set in P _k in sequence. The task sequences of all warehouses are put together to be a processed task allocation scheme. After this solution we have performed path planning according to constraints 3-4. When constructing the initial solution, we assign the task points in the DROP set and the PICK-DROP set to different unmanned aerial vehicles, and then randomly assign the PICKUP type of task points to unmanned aerial vehicles with assigned DROP tasks or reassign a new unmanned aerial vehicle to execute. To ensure solution stability, we construct a number of different path planning schemes based on the task allocation scheme, and choose the least cost scheme as the initial solution based on the greedy principle.

(2) Iterative optimization

Based on a two-stage optimization framework, a simulated annealing algorithm is provided, tasks are reassigned by a plurality of transformation factors, and after the tasks are reassigned, an unmanned aerial vehicle path scheduling scheme under each warehouse is re-planned by a variable neighborhood search algorithm (SVND, A Special Variable Neighborhood Descent Algorithm).

The variable neighborhood search algorithm is an improved meta-heuristic optimization algorithm and can be used for solving the combined optimization problem. The invention designs a special variable neighborhood search algorithm: under the condition of meeting algorithm circulation, an initial solution s ₀ is given, then the initial solution is optimized by using a neighborhood structure formed by different actions, and a new solution can be obtained in each circulation. The new solution is compared with the initial solution s ₀, and the quality of the new solution is judged and whether the new solution is accepted is determined. The valid solutions are stored in a set of solutions PICK-DROP. Repeating the steps until the maximum iteration number is reached. The optimal solution in the solution set S is the optimal path planning scheme searched by the current algorithm. Notably, to jump out of local optima and get a globally optimal solution, we use the Metropolis principle to determine if a new solution is accepted.

For SVND algorithm, we set an initial solution s ₀, select one from 6 neighborhood operators of 2-exchange, 3-exchange, 30% -exchange, relocation and, other-relocation, 10% -relocation and so on to perform neighborhood search on the initial solution to form a new solutionCalculating the cost of a new solutionIf the cost of the new solution is less than cost (s ₀), then accept the new solutionOtherwise accept the new solution with a certain probabilityAt the same time handleAssignment toIf the two conditions are not satisfied, then assign s ₀ toWill beThe values of S ₀ and cost (S ₀) are updated in the solution space S. The above steps are repeated until the cycle termination condition is satisfied. Then find the least costly path planning scheme from the solution space SAs an output of the SVND algorithm. Table 3 gives the pseudo code for SVND.

TABLE 3SVND pseudo code

Local search

In order to jump out the local optimization of the variable neighborhood algorithm and obtain a global optimal solution, a local search algorithm is designed, namely a current optimal scheduling scheme is found in a solution space generated by the SVND algorithm, and local search is carried out on the basis of the optimal scheme.

The specific operation method is that a warehouse is randomly selected from the currently found optimal scheduling schemes, and the scheduling scheme of the warehouse is locally searched. First, the client points to be executed by the selected warehouse are classified: the customer points of the goods are classified into s _1k -pick; the customer points of the delivery only are classified into s _1k -drop; the customer points for both pick and delivery tasks are categorized into s _1k -pick & drop. When neither s _1k -pick nor s _1k -drop is empty, we categorize the client points in s _1k -pick where the drone left the warehouse to pick up and then returned to the warehouse to pick ₁, Similarly, the unmanned aerial vehicle in the s _1k -drop set is classified into drop ₁ from the point where the unmanned aerial vehicle starts from the warehouse, sends the goods to the point where the unmanned aerial vehicle returns to the warehouse. A pick-only client point p ₁ and a delivery-only client point d ₁ are randomly selected from the two sets of pick ₁ and drop ₁, combining tasks which are originally allocated to two unmanned aerial vehicles and are completed by one unmanned aerial vehicle; That is, the drone starts d ₁ for delivery from the warehouse, then goes p ₁ for pick up and then returns to the warehouse. Fig. 7 shows the optimization procedure of the algorithm. Table 4 gives the pseudo code for the local search.

TABLE 4 local search pseudocode

Simulation experiment

In this section, the present invention evaluated the effectiveness of the present invention by comparison with 6 heuristic algorithms and meta heuristic algorithms, and experiments were performed in a real scene. The algorithm and other seven algorithms provided by the invention run on a PC with CPU of Core i5-8400, memory of 8G and operating system of Windows 10.

Experimental setup

In the problems researched by the invention, the problems of customer scale, warehouse quantity, unmanned aerial vehicle weight, association between unmanned aerial vehicle weight and voyage, customer distribution and the like are required to be considered. Because of the short study time of the PDSTRP problem associated with mD-PSTSP, there is temporarily no unified test dataset available for reference. Therefore, when testing the effectiveness of the algorithm, we choose to experiment with a randomly generated dataset and 6 heuristic and meta heuristic methods to demonstrate the effectiveness of the algorithm of the present invention.

Table 5 experimental algorithm parameter table

The simulation scenario is applicable to 50km×50KM areas. The client points are randomly distributed within the area. The pickup and delivery requirements for each customer point are randomly generated. The weight of each pick-up and delivery package is randomly generated, assuming that all drones perform the same, with the weight of each package being between 1KG and 8 KG. The relevant parameter settings of the performance parameter set SATO-SVND algorithm of the unmanned aerial vehicle are shown in table 6. We generated 6 examples 40, 60, 80, 100, 150, 200, the parameter settings of the algorithm of the invention were finalized based on the literature and experimental trial and error.

Compared with other meta-heuristics and heuristics

To verify the performance of the SATO-SVND algorithm, we compared the SATO-SVND algorithm with the other seven heuristics and meta-heuristics. We set 13 cases, the number of customer points set to 40, 60, 80, 100, 150, 200. Each algorithm was run 10 times to solve each case, and finally, the average of 10 experimental results was used to compare, and the data in the table are all the average of 10 experimental results. The experimental setup of the present invention was for two reasons: firstly, the advantages of the two-stage algorithm in solving the picking and delivering problems of multiple warehouses, multiple client points and multiple unmanned aerial vehicles are studied, and secondly, the generation of an initial solution of the SATO-SVND algorithm and the effectiveness of a neighborhood structure are examined.

Aiming at the problems of task allocation and path planning of unmanned aerial vehicles, the advantages of a two-stage algorithm in solving the problems of multi-warehouse, multi-client and multi-unmanned aerial vehicle picking and delivering are verified, and three efficient algorithms are designed to serve as comparison algorithms, namely ALNS, k-means & GA and k-means & LNS. As a comparison algorithm, we developed the k-means & GA algorithm using a two-stage solution framework and tournament operators. Meanwhile, in order to ensure that the individuals with good parents are not lost due to crossover or mutation operation, an elite strategy is adopted to keep the optimal individuals of the parents. ALNS and k-means & LNS algorithms are both destructive repair operators, and iterative optimization is repeated under the framework of the simulated return algorithm until the termination condition is met. To accommodate the solution of large-scale problems, we destroy 10% -20% of the solution structure at a time, and then repair the solution with a random repair operator and a greedy repair operator. In K-means & LNS, we first distribute tasks to multiple warehouses using K-means algorithm, then search in path planning using 2-opt, simple relocate, and swap move etc. neighborhood structure. ALNS the neighborhood structure incorporates the adaptation mechanism and worst-case removal operators.

In order to prove the correctness of the two-stage algorithm solving idea and the effectiveness of the neighborhood structure, three algorithms, namely SA-SVND, ETSA adopting random allocation tasks, SATO-VND1 without local search, are compared. In order to verify the effectiveness of the two stages, SA-SVND adopts a random distribution mode in a task distribution stage, then a single-center unmanned plane path planning stage adopts the SVND algorithm designed by the invention, and the iteration is repeated under the framework of SA, so that the optimal solution is finally found. SATO-VND1 is to remove the local search algorithm in SATO-SVND to verify the validity of the local search algorithm. Each instance runs 10 times of these 6 algorithms, respectively. The calculation result is shown in fig. 8.

For better comparison of the differences between algorithms, we use the Gap index to describe the differences between SATO-SVND and several other algorithms:

Wherein S _i represents the optimal solution for algorithm i, i represents one of algorithm ALNS, k-means & GA, k-means & LNS, SA-SVND, ETSA, and SATO-VND 1; s _SATO-SVND represents the optimal solution of the algorithm SATO-SVND of the invention. The calculation results are shown in Table 7.

From the cost point of view, as shown in fig. 8, the SATO-SVND algorithm designed by us has absolute advantages compared with other 6 heuristic algorithms and meta-heuristic algorithms in solving 13 cases. For better comparison of the merits of the algorithms, we process the experimental results. The optimal cost obtained by solving each case by the other seven heuristic algorithms and the meta heuristic algorithm is compared with the optimal cost obtained by solving the same case by the SATO-SVND algorithm, and the difference between the other seven algorithms and the optimal solution obtained by SATO-SVND is calculated. As can be seen from FIG. 8, the SATO-SVND algorithm is always superior to several other algorithms as the number of customer points increases. It can be noted that the cost increases suddenly when computing both cases c6 and c13, due to the large increase in customer points. We can see that SATO-SVND is very close to the optimal solution obtained by other algorithms when dealing with small-scale problems, but when dealing with large-scale problems, the effects of other algorithms are reduced to different degrees, wherein the difference between the optimal solution obtained by ALNS algorithm and the optimal solution obtained by SATO-SVND calculation is even more than 30%.

TABLE 6 Gap for different algorithm optimal solutions and the algorithm optimal solution of the present invention

The reason for the gap between SATO-SVND and SATO-VND1 is that SATO-VND1 does not use the Local Search operator to result in convergence and a locally optimal solution. However, SATO-SVND is very similar to SATO-VND1 in terms of computation time, indicating that Local Search can improve the solution in very little time consumption.

SATO-SVND is significantly better in cost than the SA-SVND algorithm, but the two algorithms are very similar in computation time, indicating that the SATO-SVND algorithm can produce a better solution in a reasonable time as compared to the SA-SVND algorithm.

ETSA is obviously better than SATO-SVND algorithm in calculation time, but the cost of a solution scheme obtained by SATO-SVND algorithm is obviously better than ETSA algorithm, which proves that SVND algorithm can improve the quality of the solution scheme to a great extent, ETSA algorithm is easy to converge on a local optimal solution, and ETSA algorithm can only be applied to scenes which are very sensitive to time and have low requirements on the quality of the solution scheme.

The SATO-SVND algorithm is significantly superior to the other six comparison algorithms, both in terms of algorithm stability and optimization, as can be seen from FIG. 9.

ETSA is superior to the other seven algorithms in terms of time efficiency, and the three algorithms of SA-SVND, SATO-VND1 are inferior. In contrast, as customer points increase, the time consumed by the search algorithms, k-means & GA, k-means-LNS, ALNS, etc., increases rapidly. Among them, k-means & GA performs the worst in time efficiency, followed by k-means-LNS, ALNS. The two algorithms of k-means-LNS and ALNS are different in that the k-means-LNS generates an initial solution based on a two-stage optimization method, and ALNS generates an initial solution randomly, and from the comparison of the two algorithms, the two-stage optimization method can greatly improve the optimization result of the algorithm in a small time consumption, but the k-means & LNS still has the problem of premature convergence, and the SATO-SVND algorithm far exceeds the k-means & LNS in the aspect of cost optimization due to the adoption of various variable neighborhood structures. Meanwhile, SATO-SVND is significantly shorter in operation time than k-means & LNS, indicating that SATO-SVND can produce a better scheduling scheme in a shorter time than SATO-LNS. The algorithm run time results are shown in fig. 10.

In order to further verify the effectiveness of the SATO-SVND algorithm in solving the large-scale task scheduling problem of multiple unmanned aerial vehicles, multiple warehouses and multiple client points, we choose the client points in the real scene as test data for further experimental verification. The invention selects the real geographic coordinates of 80 buildings in 9 cells of the Yue foot region of Hunan province and Changsha city as the client points of the multi-unmanned aerial vehicle, and the specific positions are shown in figure 9.5 warehouse points are set, and the weight of each cargo is a random number within 1KG-8 KG. The cost convergence curve is shown in fig. 11. The run time was 12.91s and the optimal cost was 15.8% lower than the initial solution.

As can be seen from FIG. 11, the cost of the scheduling scheme solved by the SATO-SVND algorithm is reduced at a faster rate within 50 iterations, which indicates that the SATO-SVND algorithm has a stronger reduction capability in a short time. The Metropolis principle, the related neighborhood structure and the local search operator avoid premature convergence of the algorithm. The algorithm converged to the optimal solution at 225 times.

The invention discloses a two-stage optimization and iteration-based unmanned aerial vehicle picking and delivering method, which comprises the following steps:

A task allocation stage, namely allocating an initial task to the single center, and reallocating the task according to a plurality of neighborhood operators;

In the path planning stage, a path planning scheme for completing tasks is found for each warehouse according to a plurality of neighborhood operators;

The task allocation stage and the path planning stage are iterated continuously, and a global optimal solution is searched until an algorithm termination condition is met; setting a small cycle and a large cycle, wherein the small cycle generates a new scheduling scheme meeting constraint conditions, the large cycle performs local search on the basis of the scheduling scheme generated by the small cycle to form a new scheduling scheme, and then determines whether to accept a local search result according to a greedy principle;

The beneficial effects of the invention are as follows:

the vacant space of the city is fully utilized;

The embodiment of the present invention is an implementation manner of the present invention, but the implementation manner of the present invention is not limited by the embodiment, and any other changes, modifications, substitutions, combinations, and simplifications made by the spirit and principle of the present invention should be equivalent substitution manner, and all the changes, substitutions, combinations, and simplifications are included in the protection scope of the present invention.

Claims

1. Unmanned aerial vehicle gets delivery system based on automatic express delivery device in city roof, its characterized in that, automatic express delivery device sets up in city roof, and the system includes:

The path planning module finds a path planning scheme for completing tasks for each warehouse according to a plurality of neighborhood operators; the neighborhood operators comprise 2-exchange, 3-exchange, 30% -exchange, relocation, other-relocation and 10% -relocation;

the 2-exchange operator operation method comprises the following steps: randomly selecting two task points under one warehouse in a planned path ，，Two client pointsIs used for the position exchange of the (a); the 3-exchange operator operation method comprises the following steps: three client points under a warehouse are randomly selected in a planned path，，，Then willThe positions of the three points are randomly exchanged; the 30% -exchange operator specifically operates as follows: randomly selecting 30% of the client points in the planned path, and then randomly disturbing the order of the client points;

2. The unmanned aerial vehicle pickup and delivery system based on the city roof automatic express delivery device of claim 1, wherein the unmanned aerial vehicle goes to the next customer point or warehouse after loading and unloading the goods, or automatically replaces the battery at the roof; for the client point only taking goods, arranging an unmanned aerial vehicle to start from the warehouse to take goods from the client point, and then returning to the warehouse; for a client point only for delivery, arranging an unmanned aerial vehicle to deliver goods from a warehouse to the client point, and after delivery, selecting the unmanned aerial vehicle to deliver goods to the next client point and then returning to the warehouse, or selecting the unmanned aerial vehicle to directly return to a nearby warehouse; for a customer point with simultaneous goods taking and delivering tasks, arranging a unmanned aerial vehicle to send goods from a warehouse, taking the goods at the customer point after unloading, and then returning to the warehouse.

3. The unmanned aerial vehicle picking and delivering system based on the automatic express delivery device of the urban roof according to claim 2, wherein the task allocation module classifies tasks into three types according to task types of client points, stores task points which have only picking demands and have no picking demands into PICKUP sets, stores task points which have only picking demands and have no picking demands into DROP sets, and stores task points which have picking demands and have picking demands into PICK-DROP sets; after task classification is completed, task points in the PICKUP, DROP and PICK-DROP sets are generated by adopting a k-means algorithm to generate an initial task allocation scheme considering geographic positions.

4. The unmanned aerial vehicle pickup and delivery system based on the urban roof automatic express delivery device according to claim 3, wherein the specific operation method of the Relocation operator is as follows: randomly selecting a client point in a warehouseRandomly selecting an insertion point from the existing path planning schemes of the b warehouse, and according to the constraint condition of the model, selecting the client pointMigrating to a b warehouse path planning scheme; the specific operation method of the Other-relocation is as follows: selecting a client point among all tasks assigned to the a warehouseAccording to the model constraint condition, randomly inserting the client point i into the path scheduling scheme of the b warehouse to be executed; the specific operation method of 10% -relocation is as follows: and randomly selecting one warehouse at a time, and migrating the client points farthest from the warehouse according to the distance between the client points and the warehouse, wherein the number of the migrated client points is 20% of the total client points of the warehouse.

5. The unmanned aerial vehicle pick and place system based on the city roof automatic express delivery device of claim 1, wherein the path planning module generates an initial solutionThe method comprises the following specific steps:

generating a task allocation scheme of all warehouses: for the tasks distributed to each warehouse, the tasks are divided into three types of goods taking only, goods delivering only and goods taking and delivering tasks simultaneously according to the characteristics of the tasks and are respectively stored in the warehouse -pick、-drop、Of the three sets pick & drop, the initialization setStoring a task sequence of a warehouse k; randomly take outTask point store within drop setThen randomly take outTask point store within pick setFinally, willTask points within the pick & drop set are stored in order; The task sequences of all the warehouses are put together to obtain a processed task allocation scheme;

6. The unmanned aerial vehicle pickup and delivery system based on the city roof automatic express delivery device of claim 5, wherein the unmanned aerial vehicle path scheduling scheme under each warehouse is re-planned according to the initial solution, and the specific steps are as follows:

Given an initial solution Selecting one from 6 neighborhood operators to perform neighborhood search on the initial solution to form a new solution；

Calculating cost of new solution) ; If the cost of the new solution is less than the cost of the initial solution) Accept the new solution; Otherwise accept the new solution with a certain probabilityAt the same time handleAssignment to; If the two conditions are not satisfied, the initial solution is performedAssignment to; Will beIs stored in the solution space S and updatedAnd cost%) Is a value of (2);

7. The unmanned aerial vehicle picking and delivering system based on the automatic express delivery device of the urban roof according to claim 6, wherein a warehouse is randomly selected from the current optimal scheduling schemes, and the scheduling scheme of the warehouse is locally searched, and the method specifically comprises the following steps:

Classifying the client points to be executed in the selected warehouse: sorting only pick-up customer points into categories -Pick; sorting delivery-only customer points into categories-Drop; customer points for simultaneous pick and delivery tasks are categorizedPick & drop; when (when)Pick-upWhen none of the drop sets is empty, it willThe unmanned aerial vehicle in pick takes goods from the client point from the warehouse and returns the goods to the client point of the warehouse to be classifiedWill beThe unmanned aerial vehicle in the drop set starts from the warehouse to send the goods from the customer point and returns to the customer point of the warehouse to be classified；

From the slaveAndRandomly selecting one pick-only client point from two setsDelivery-only customer pointAnd combining the tasks which are originally assigned to the two unmanned aerial vehicles and completed by one unmanned aerial vehicle.

8. Unmanned aerial vehicle picking and delivering method based on city roof automatic express device, characterized in that it is applied to the system according to any one of claims 1-7, comprising the following steps: