[go: up one dir, main page]

CN112801601B - Method and device for allocating routes, storage medium and electronic equipment - Google Patents

Method and device for allocating routes, storage medium and electronic equipment Download PDF

Info

Publication number
CN112801601B
CN112801601B CN202110377402.3A CN202110377402A CN112801601B CN 112801601 B CN112801601 B CN 112801601B CN 202110377402 A CN202110377402 A CN 202110377402A CN 112801601 B CN112801601 B CN 112801601B
Authority
CN
China
Prior art keywords
conflict
target
alternative
route
routes
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
Application number
CN202110377402.3A
Other languages
Chinese (zh)
Other versions
CN112801601A (en
Inventor
安培
张邦彦
张继伟
眭泽智
黄金鑫
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Beijing Sankuai Online Technology Co Ltd
Original Assignee
Beijing Sankuai Online Technology Co Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Beijing Sankuai Online Technology Co Ltd filed Critical Beijing Sankuai Online Technology Co Ltd
Priority to CN202110377402.3A priority Critical patent/CN112801601B/en
Publication of CN112801601A publication Critical patent/CN112801601A/en
Application granted granted Critical
Publication of CN112801601B publication Critical patent/CN112801601B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; 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/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
    • G06Q10/083—Shipping
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; 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
    • G06Q10/06312—Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling

Landscapes

  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Engineering & Computer Science (AREA)
  • Economics (AREA)
  • Strategic Management (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Quality & Reliability (AREA)
  • Development Economics (AREA)
  • Marketing (AREA)
  • Operations Research (AREA)
  • Tourism & Hospitality (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Game Theory and Decision Science (AREA)
  • Educational Administration (AREA)
  • Traffic Control Systems (AREA)

Abstract

The disclosure relates to a method, a device, a storage medium and an electronic device for allocating routes, which can establish a route conflict cost table between a first alternative route of at least one flight task and a second alternative route of other flight tasks, wherein the route conflict cost table is provided with conflict influence values among different routes, and the conflict influence values are used for representing the severity of mutual conflict among the different routes; acquiring a plurality of alternative air route sets corresponding to a target flight task of a current air route to be allocated, and determining a target conflict influence value of each alternative air route set according to the conflict influence value, wherein the target conflict influence value is used for representing the conflict degree between the air routes in the corresponding alternative air route set; and determining a target air route corresponding to each target flight task according to the target conflict influence value so as to distribute the corresponding target air route for each target flight task, and sending the target air route to a control terminal of the unmanned aerial vehicle so that the control terminal controls the unmanned aerial vehicle to execute the target air route.

Description

Method and device for allocating routes, storage medium and electronic equipment
Technical Field
The present disclosure relates to lane allocation in the distribution field, and in particular, to a method, an apparatus, a storage medium, and an electronic device for allocating lanes.
Background
Along with the development of unmanned aerial vehicle technique, unmanned aerial vehicle's reliability and carrying capacity have obtained very big promotion, and unmanned aerial vehicle delivery has also obtained extensive concern as a neotype logistics distribution mode, for example, can be applied to unmanned aerial vehicle and carry out takeaway delivery in the city, nevertheless because the extensive and ageing nature of takeaway order form, it will become the normality to have a large amount of unmanned aerial vehicle to develop the delivery task in same operation region, in order to improve the ageing nature of extensive delivery, the airline when needing to carry out the delivery task to unmanned aerial vehicle carries out the rational distribution.
In the related art, sequence allocation is directly performed during airline allocation, or airline allocation is performed according to airline priorities and distribution task priorities, but in the case of conflict between airlines, for example, the same airline is allocated to unmanned aerial vehicles corresponding to a plurality of distribution tasks, and in the case of conflict between distribution times, airline conflict between two distribution tasks is caused, or airline conflict is caused when two airlines cross in a region in space.
Disclosure of Invention
The invention aims to provide a method, a device, a storage medium and an electronic device for allocating routes.
In a first aspect, there is provided a method of allocating routes, the method comprising:
establishing a flight path conflict cost table between a first alternative flight path of at least one flight task and a second alternative flight path of other flight tasks, wherein conflict influence values among different flight paths are set in the flight path conflict cost table, and the conflict influence values are used for representing the severity of mutual conflict among the different flight paths; acquiring a plurality of alternative route sets corresponding to target flight tasks of current routes to be allocated, wherein the alternative route sets comprise an alternative route corresponding to each target flight task; determining a target conflict influence value of each alternative airline set according to the conflict influence value in the airline conflict cost table, wherein the target conflict influence value is used for representing the conflict degree between airlines in the corresponding alternative airline sets; determining a target route corresponding to each target flight task according to the target conflict influence value so as to distribute the corresponding target route for each target flight task; and sending the target route to a control terminal of the unmanned aerial vehicle so that the control terminal controls the unmanned aerial vehicle to execute the target route.
Optionally, the determining a target collision influence value of each alternative airline set according to the collision influence value in the airline collision cost table includes: for each alternative route set, searching target influence values corresponding to every two routes in the alternative route set from the route conflict cost table; and taking the sum of the target influence values corresponding to every two routes in the alternative route set as the target conflict influence value corresponding to the alternative route set.
Optionally, before the determining the target collision influence value of each alternative route set according to the collision influence value in the route collision cost table, the method further includes: acquiring the times of each alternative route in the alternative route set occupied in a preset time period aiming at each alternative route set; the determining a target collision impact value for each alternative airline set according to the collision impact values in the airline collision cost table comprises: and determining a target conflict influence value of each alternative route set according to the conflict influence value and the times in the route conflict cost table.
Optionally, the determining a target collision influence value of each candidate airline set according to the collision influence value and the number of times in the airline collision cost table includes: for each alternative route set, searching target influence values corresponding to every two routes in the alternative route set from the route conflict cost table; and determining the target conflict influence value of the alternative route set according to the target influence values corresponding to every two routes in the alternative route set and the times of each alternative route in the alternative route set being occupied in a preset time period.
Optionally, the determining a target route corresponding to each target flight task according to the target conflict influence value includes: and taking the route in the candidate route set with the minimum target conflict influence value as the target route.
Optionally, the obtaining of a plurality of candidate flight route sets corresponding to a target flight task of a current flight route to be allocated includes:
aiming at each target flight task in at least one target flight task, determining at least one alternative route corresponding to the target flight task from a plurality of preset routes; and combining each alternative route corresponding to a first flight task with each alternative route corresponding to a second flight task to obtain a plurality of alternative route sets, wherein the first flight task is any target flight task, and the second flight task is a target flight task except the first flight task in at least one target flight task.
Optionally, the establishing a route conflict cost table between the first alternative route of at least one flight task and the second alternative routes of other flight tasks includes: aiming at every two alternative routes, acquiring a preset anti-collision occupied area corresponding to one of the two alternative routes, wherein each two alternative routes comprises one first alternative route and one second alternative route; determining the length of the other alternative route in the preset anti-collision occupied area; determining first conflict durations of the two alternative routes according to the route length; and determining the conflict influence values corresponding to the two alternative routes according to the first conflict duration.
Optionally, before the determining the collision influence values corresponding to the two candidate routes according to the first collision duration, the method further includes: acquiring conflict data corresponding to the two alternative routes based on big data statistics, wherein the conflict data comprise a second conflict duration or a conflict level; the determining the collision influence values corresponding to the two alternative routes according to the first collision duration includes: determining the collision influence values corresponding to the two alternative routes according to the first collision duration and the collision data by the following formula:
Figure 26711DEST_PATH_IMAGE001
wherein,
Figure 748417DEST_PATH_IMAGE002
representing the conflict effect values for the two alternative routes,
Figure DEST_PATH_IMAGE003
a first duration of the collision is indicated,
Figure 423112DEST_PATH_IMAGE004
a second collision duration is indicated and,
Figure DEST_PATH_IMAGE005
the level of the conflict is indicated,
Figure 884180DEST_PATH_IMAGE006
indicating the confidence factor that the conflicting data corresponds to,
Figure DEST_PATH_IMAGE007
and representing a confidence factor corresponding to the first conflict duration.
Optionally, after the corresponding target route is allocated to each target flight task, the method further includes: acquiring a plurality of actual conflict durations corresponding to the two alternative routes according to a plurality of actual flight tasks on the two alternative routes; updating the conflict data according to a plurality of actual conflict durations; and updating the collision influence values corresponding to the two alternative routes according to the updated collision data.
In a second aspect, there is provided an apparatus for allocating routes, the apparatus comprising: the system comprises a cost table construction module, a cost table construction module and a cost calculation module, wherein the cost table construction module is used for establishing a flight path conflict cost table between a first alternative flight path of at least one flight task and a second alternative flight path of other flight tasks, conflict influence values among different flight paths are arranged in the flight path conflict cost table, and the conflict influence values are used for representing the severity of mutual conflict among the different flight paths; the system comprises a first acquisition module, a second acquisition module and a third acquisition module, wherein the first acquisition module is used for acquiring a plurality of alternative route sets corresponding to target flight tasks of current routes to be allocated, and each alternative route set comprises an alternative route corresponding to each target flight task; a first determining module, configured to determine a target collision influence value of each alternative airline set according to the collision influence value in the airline collision cost table, where the target collision influence value is used to characterize a degree of collision between airlines in a corresponding alternative airline set; the second determining module is used for determining a target route corresponding to each target flight task according to the target conflict influence value so as to allocate the corresponding target route to each target flight task; and the sending module is used for sending the target air route to a control terminal of the unmanned aerial vehicle so that the control terminal controls the unmanned aerial vehicle to execute the target air route.
Optionally, the first determining module is configured to, for each alternative route set, search, from the route conflict cost table, a target influence value corresponding to each two routes in the alternative route set; and taking the sum of the target influence values corresponding to every two routes in the alternative route set as the target conflict influence value corresponding to the alternative route set.
Optionally, the apparatus further comprises: the second acquisition module is used for acquiring the times of each alternative route in the alternative route set being occupied in a preset time period aiming at each alternative route set; and the first determining module is used for determining a target conflict influence value of each alternative route set according to the conflict influence value and the times in the route conflict cost table.
Optionally, the first determining module is configured to, for each alternative route set, search, from the route conflict cost table, a target influence value corresponding to each two routes in the alternative route set; and determining the target conflict influence value of the alternative route set according to the target influence values corresponding to every two routes in the alternative route set and the times of each alternative route in the alternative route set being occupied in a preset time period.
Optionally, the second determining module is configured to use the route in the candidate route set with the smallest target collision influence value as the target route.
Optionally, the first obtaining module is configured to, for each target flight task of the at least one target flight task, determine at least one alternative route corresponding to the target flight task from among multiple preset routes; and combining each alternative route corresponding to a first flight task with each alternative route corresponding to a second flight task to obtain a plurality of alternative route sets, wherein the first flight task is any target flight task, and the second flight task is a target flight task except the first flight task in at least one target flight task.
Optionally, the cost table building module is configured to obtain, for each two alternative routes, a preset anti-collision occupied area corresponding to one of the two alternative routes, where the two alternative routes include the first alternative route and the second alternative route; determining the length of the other alternative route in the preset anti-collision occupied area; determining first conflict durations of the two alternative routes according to the route length; and determining the conflict influence values corresponding to the two alternative routes according to the first conflict duration.
Optionally, the cost table constructing module is configured to obtain conflict data corresponding to the two alternative routes based on big data statistics, where the conflict data includes a second conflict duration or a conflict level; determining the collision influence values corresponding to the two alternative routes according to the first collision duration and the collision data by the following formula:
Figure 251707DEST_PATH_IMAGE008
wherein,
Figure 962174DEST_PATH_IMAGE002
representing the conflict effect values for the two alternative routes,
Figure 204675DEST_PATH_IMAGE003
a first duration of the collision is indicated,
Figure 316987DEST_PATH_IMAGE004
a second collision duration is indicated and,
Figure 324257DEST_PATH_IMAGE005
the level of the conflict is indicated,
Figure 522021DEST_PATH_IMAGE006
indicating the confidence factor that the conflicting data corresponds to,
Figure 335256DEST_PATH_IMAGE007
and representing a confidence factor corresponding to the first conflict duration.
Optionally, the apparatus further comprises: the updating module is used for acquiring a plurality of actual conflict durations corresponding to the two alternative routes according to a plurality of actual flight tasks on the two alternative routes; updating the conflict data according to a plurality of actual conflict durations; and updating the collision influence values corresponding to the two alternative routes according to the updated collision data.
In a third aspect, a computer readable storage medium is provided, on which a computer program is stored, which program, when being executed by a processor, carries out the steps of the method according to the first aspect of the disclosure.
In a fourth aspect, an electronic device is provided, comprising: a memory having a computer program stored thereon; a processor for executing the computer program in the memory to implement the steps of the method of the first aspect of the disclosure.
According to the technical scheme, as the conflict influence value in the airline conflict cost table represents the severity of mutual conflict among different airlines, in other words, the conflict influence value represents space constraint among the airlines, when the target conflict influence value of each alternative airline set is determined according to the conflict influence value, and the target airline to be allocated is further determined based on the target conflict influence value, namely, actual space constraint among the airlines is considered for allocating the airlines, so that congestion delay in the execution process of large-scale airlines is reduced, and timeliness of completing flight tasks is improved.
Additional features and advantages of the disclosure will be set forth in the detailed description which follows.
Drawings
The accompanying drawings, which are included to provide a further understanding of the disclosure and are incorporated in and constitute a part of this specification, illustrate embodiments of the disclosure and together with the description serve to explain the disclosure without limiting the disclosure. In the drawings:
FIG. 1 is a flow chart illustrating a first method of allocating routes in accordance with an exemplary embodiment;
FIG. 2 is a schematic diagram illustrating the relationship of a delivery mission to an alternate route in accordance with an exemplary embodiment;
FIG. 3 is a flowchart illustrating a method of constructing a airline conflict cost table in accordance with an exemplary embodiment;
FIG. 4 is a flow chart illustrating a method of second allocating routes in accordance with an exemplary embodiment;
FIG. 5 is a block diagram illustrating an apparatus for a first allocated lane in accordance with an exemplary embodiment;
FIG. 6 is a block diagram illustrating an apparatus for a second allocated lane in accordance with an exemplary embodiment;
FIG. 7 is a block diagram illustrating an apparatus for allocating routes of a third type in accordance with an exemplary embodiment;
fig. 8 is a block diagram illustrating a structure of an electronic device according to an example embodiment.
Detailed Description
The following detailed description of specific embodiments of the present disclosure is provided in connection with the accompanying drawings. It should be understood that the detailed description and specific examples, while indicating the present disclosure, are given by way of illustration and explanation only, not limitation.
First, an application scenario of the present disclosure is introduced, and the present disclosure is mainly applied to a scenario in which a flight mission is allocated with a flight route, for example, the present disclosure may be applied to a scenario in which a flight mission is allocated with a flight route when an unmanned aerial vehicle is used for distribution, in the related art, sequence allocation is directly performed when a flight route is allocated, or flight route allocation is performed based on a flight route priority and a distribution mission priority, but when there is a conflict between flight routes, for example, the same flight route is allocated to an unmanned aerial vehicle corresponding to a plurality of distribution missions, and when there is a conflict in distribution time, a flight route conflict between two distribution missions may be caused, or a flight route conflict may be caused when two flight routes intersect in a space.
In order to solve the existing problems, the present disclosure provides a method, an apparatus, a storage medium, and an electronic device for allocating routes, which may first establish a route conflict cost table between a first alternative route of at least one flight task and a second alternative route of other flight tasks, where the route conflict cost table is provided with conflict influence values between different routes, the conflict influence values are used to characterize the severity of mutual conflicts between different routes, determine a target conflict influence value of each alternative route set according to the conflict influence values in the route conflict cost table, and the target conflict influence value is used to characterize the conflict degree between routes in a corresponding alternative route set; and determining a target air route corresponding to each target flight task according to the target conflict influence value so as to allocate the corresponding target air route for each target flight task, and sending the target air route to a control terminal of the unmanned aerial vehicle so that the control terminal controls the unmanned aerial vehicle to execute the target air route.
By adopting the method, the conflict influence value in the airline conflict cost table represents the severity of mutual conflict among different airlines, in other words, the conflict influence value represents space constraint among the airlines, so that when the target conflict influence value of each alternative airline set is determined according to the conflict influence value and the target airline to be allocated is further determined based on the target conflict influence value, the airline allocation is carried out by considering the actual space constraint among the airlines, thereby reducing the congestion delay in the execution process of large-scale airlines and improving the timeliness of completing flight tasks.
Specific embodiments of the present disclosure will be described in detail below with reference to the accompanying drawings.
FIG. 1 is a flow chart illustrating a method of allocating airlines, as may be implemented in a server for allocating airlines, as shown in FIG. 1, and including the steps of:
in step S101, a route conflict cost table between a first alternative route of at least one flight task and a second alternative route of other flight tasks is established, and a conflict influence value between different routes is set in the route conflict cost table.
Wherein the conflict impact value is used for representing the severity of the mutual conflict among different routes.
In step S102, a plurality of candidate airline sets corresponding to target flight tasks of current airlines to be allocated are obtained, where the candidate airline sets include one candidate airline corresponding to each target flight task.
In this step, for each target mission of at least one target mission, at least one alternative route corresponding to the target mission may be determined from a plurality of preset routes, and then each alternative route corresponding to a first mission is combined with an alternative route corresponding to each second mission to obtain a plurality of alternative route sets, where the first mission is any target mission, and the second mission is at least one target mission other than the first mission in the target mission.
The target flight mission may include, among other things, a delivery mission, such as a take-away order delivery mission.
In this step, a starting point and an ending point corresponding to the target mission may be obtained, and then at least one alternative route corresponding to the target mission may be determined according to the starting point and the ending point, that is, the plurality of preset routes starting from the starting point to the ending point may be used as the alternative routes corresponding to the target mission.
In addition, in the step, in the process of combining each alternative route corresponding to the first flight task with each alternative route corresponding to the second flight task to obtain a plurality of alternative route sets, one alternative route can be respectively extracted from at least one alternative route corresponding to the first flight task and each second flight task to be arranged and combined to obtain a plurality of alternative route sets.
For example, taking the flight mission as an example of a delivery mission, fig. 2 is a schematic diagram illustrating a correspondence relationship between the delivery mission and an alternative route according to an exemplary embodiment, and as shown in fig. 2, it is assumed that three orders to be delivered need to be delivered from a to a '(delivery mission a), from B to B' (delivery mission B), and from C to C '(delivery mission C), as shown in fig. 2, three alternative routes a1, a2, and A3 exist between a and a', that is, the alternative route corresponding to the delivery mission a is: a1, A2 and A3, and B1 and B2 candidate routes are arranged between B and B', namely the candidate route corresponding to the task B is: b1 and B2, wherein a C1 alternative route is arranged between C and C', namely the alternative route corresponding to the task C is as follows: c1, it is obvious that the distribution task a may be allocated to any one of the lanes a1, a2, A3, the distribution task B may be allocated to any one of the lanes B1, B2, and the distribution task C may be allocated to the lane C1, in the process of executing this step, one alternative lane corresponding to each of the three distribution tasks may be combined to obtain a plurality of alternative lanes sets (a 1, B1, C1), (a 1, B2, C1), (a 2, B1, C1), (a 2, B2, C1), (A3, B1, C1), (A3, B2, C1).
In step S103, a target conflict influence value of each alternative route set is determined according to the conflict influence value in the route conflict cost table.
Wherein the conflict influence value is used for representing the severity of mutual conflict between any two routes, the higher the conflict influence value is, the more severe the conflict between the two corresponding routes is, in a possible implementation manner, the conflict influence value may be recorded by a preset table (i.e. the route conflict cost table), the target conflict influence value is used for representing the conflict degree between the routes in the corresponding alternative route set, taking the alternative route set (a 1, B1, C1) as an example, and the method can be used for determining the conflict degree between the routes in the alternative route set
Figure 302075DEST_PATH_IMAGE009
Representing a target conflict influence value of the alternative route set, wherein the target conflict influence value represents the conflict degree of the three routes A1, B1 and C1 on time and space, the higher the target conflict influence value is, the more serious the conflict degree of the routes in the alternative route set is, and when the route in the alternative route set is selected as the target route to be allocated for the flight mission, the congestion degree isThe higher.
In this step, for each alternative route set, the target influence values corresponding to every two routes in the alternative route set can be searched from the route conflict cost table; and then taking the sum of the target influence values corresponding to every two routes in the alternative route set as the target conflict influence value corresponding to the alternative route set.
Illustratively, continuing with the three delivery tasks A, B, C shown in FIG. 2, any set of alternative routes corresponding to the three delivery tasks may be represented as
Figure 542563DEST_PATH_IMAGE010
Wherein
Figure 663841DEST_PATH_IMAGE011
Table 1 is a route conflict cost table corresponding to fig. 2 and used for recording the preset conflict influence value, and the target influence values corresponding to every two routes in the alternative route set may be searched from table 1 and are respectively:
Figure 15188DEST_PATH_IMAGE012
thus, the set of alternative routes may be calculated by the following formula
Figure 836513DEST_PATH_IMAGE013
The corresponding target collision impact value:
Figure 247903DEST_PATH_IMAGE014
in addition, considering that the flight time of a plurality of flight missions on the same flight path is in conflict, the flight paths corresponding to the two flight missions are in conflict, therefore, in another possible implementation manner of the step, before the step is executed, the number of times that each alternative route in the alternative route set is occupied in a preset time period can be obtained for each alternative route set, the preset time period may be set according to the current time, for example, the preset time period may be a preset time period before and after the current time (e.g. within 10 minutes before and after the current time), the preset time period may be a preset time period taking the current time as the starting time, or a preset historical time period taking the current time as the ending time, and the preset time period may be arbitrarily set according to actual requirements, which is not limited by the present disclosure.
It should be noted that, it is assumed that the preset time period is a preset time period before and after the current time, that is, the number of times that the alternative airline is occupied in the past historical time and the number of times that the alternative airline is to be occupied in a future time period are considered, and therefore, the number of times that the alternative airline is occupied in the preset time period may reflect the historical missions or other missions on the alternative airline, that is, the impact of mutual conflicts between different missions on the same airline.
In an actual application scenario, a target route corresponding to each flight task (including the executed flight task and the flight task to which the target route has been allocated but the execution time is short) and the execution time for executing the flight task on the corresponding target route are recorded in the server, so in this step, the number of flight tasks on each alternative route, the execution time of which is within the preset time period, can be obtained from information recorded by the server as the number of times that the alternative route is occupied within the preset time period.
In this way, in this step, the target conflict influence value of each alternative airline set can be determined according to the conflict influence value and the number in the airline conflict cost table, so that the actual space constraint between airlines and the influence of historical delivery tasks or other delivery tasks on the same airline can be comprehensively considered for airline distribution, and the congestion delay in the large-scale airline execution process is further reduced.
For each alternative route set, searching a target influence value corresponding to each two routes in the alternative route set from the route conflict cost table; and determining the target conflict influence value of the alternative route set according to the target influence values corresponding to every two routes in the alternative route set and the times of each alternative route in the alternative route set being occupied in a preset time period.
Illustratively, continuing with the three delivery tasks A, B, C shown in FIG. 2, any set of alternative routes corresponding to the three delivery tasks may be represented as
Figure 154679DEST_PATH_IMAGE015
Wherein
Figure 44138DEST_PATH_IMAGE016
Table 1 is a route conflict cost table corresponding to fig. 2 and used for recording the conflict influence value, and the target influence values corresponding to every two routes in the candidate route set may be found from table 1 as follows:
Figure 985549DEST_PATH_IMAGE017
thus, the set of alternative routes may be calculated by the following formula
Figure 331954DEST_PATH_IMAGE018
The corresponding target collision impact value:
Figure 726027DEST_PATH_IMAGE019
wherein,
Figure 419176DEST_PATH_IMAGE020
representing a set of alternative routes
Figure 152777DEST_PATH_IMAGE021
Is determined based on the target collision impact value of (a),
Figure 905969DEST_PATH_IMAGE022
respectively representing the times of the corresponding alternative routes being occupied in the preset time period, and the obtaining mode of the times is already advanced in step S103The description is omitted here.
Figure 787338DEST_PATH_IMAGE023
TABLE 1
The foregoing examples are illustrative only, and the disclosure is not limited thereto.
In step S104, a target route corresponding to each target flight task is determined according to the target conflict influence value, so as to allocate the corresponding target route to each target flight task.
As mentioned above, the target conflict influence value is used to characterize the degree of conflict between the airlines in the corresponding candidate airline set, and the higher the target conflict influence value, the more serious the degree of conflict between airlines in the candidate airline set is, so to avoid the problem of airline conflict, in this step, the airline in the candidate airline set with the smallest target conflict influence value may be used as the target airline.
In addition, considering the situation that each flight task generally corresponds to multiple route selections in a large-scale route task allocation system, in order to allocate a more ideal route for each flight task more efficiently, the route selection of multiple flight tasks can be converted into a 0-1 planning problem to be solved, and therefore the complexity of the problem is reduced.
Illustratively, continuing with the example of three delivery tasks A, B, C shown in FIG. 2, where the alternative route to which delivery task A corresponds is
Figure 284178DEST_PATH_IMAGE024
The alternative route corresponding to the distribution task B is
Figure 433137DEST_PATH_IMAGE025
The alternative route corresponding to the distribution task C is
Figure 357231DEST_PATH_IMAGE026
Set a variable quantity
Figure 725895DEST_PATH_IMAGE027
Representing the set of alternative routes for the delivery task A, B, C, the process of converting the route selection for the multi-delivery task into a 0-1 planning problem for solution is as follows:
constraint conditions are as follows:
Figure 760848DEST_PATH_IMAGE028
an objective function:
Figure 531357DEST_PATH_IMAGE029
wherein,
Figure 564036DEST_PATH_IMAGE030
representing a set of alternative routes
Figure 419996DEST_PATH_IMAGE031
May represent the set of candidate routes having the smallest target collision impact value as
Figure 757174DEST_PATH_IMAGE032
Representing other alternative route sets except the alternative route set with the minimum target conflict influence value as
Figure 116611DEST_PATH_IMAGE033
Thus, based on the above-mentioned objective function, it is possible to obtain
Figure 382508DEST_PATH_IMAGE034
I.e., the target route corresponding to the delivery task A, B, C, to complete the route allocation of the delivery task, the above example is merely illustrative and the disclosure is not limited thereto.
In step S105, the target route is sent to the control terminal of the drone so that the control terminal controls the drone to execute the target route.
Wherein, this control terminal can be for handheld terminal, like unmanned aerial vehicle's remote controller, or also can be other arbitrary terminal equipment that can control unmanned aerial vehicle.
In this step, the route identification information of the target route may be sent to the control terminal of the corresponding unmanned aerial vehicle.
For example, it is assumed that after step S104 is executed, it is determined that the target route corresponding to the delivery task a is a1, the target route corresponding to the delivery task B is B2, and the target route corresponding to the delivery task C is C1, at this time, the server may send the identification information of the target route a1 to the control terminal of the unmanned aerial vehicle executing the delivery task a, send the identification information of the target route B2 to the control terminal of the unmanned aerial vehicle executing the delivery task B, and send the identification information of the target route C1 to the control terminal of the unmanned aerial vehicle executing the delivery task C, so that each control terminal controls the corresponding unmanned aerial vehicle to execute the corresponding target route.
By adopting the method, because the conflict influence value in the airline conflict cost table represents the severity of mutual conflict among different airlines, in other words, the conflict influence value represents space constraint among airlines, and the times of each alternative airline being occupied in the preset time period can reflect historical flight tasks or other flight tasks on the alternative airline, when the target conflict influence value of each alternative airline set is determined according to the conflict influence value and the times of each alternative airline being occupied in the preset time period, the target airline to be allocated is further determined based on the target conflict influence value, namely the actual space constraint among airlines and the influence of the historical flight tasks or other flight tasks on the same airline are comprehensively considered for allocation, thereby reducing congestion delay in the execution process of large-scale airlines, the timeliness of the completion of the flight task is improved.
The process of creating the airline collision cost table described in step S101 is explained below, and fig. 3 is a flowchart illustrating a method of creating an airline collision cost table according to an exemplary embodiment, as shown in fig. 3, the method including the steps of:
in step S301, for every two alternative routes, a preset anti-collision occupied area corresponding to one of the two alternative routes is obtained, where the two alternative routes include one first alternative route and one second alternative route.
In a possible implementation manner, the preset anti-collision occupied area may be a circular area with any point on the alternative route as a center of a circle and a preset distance as a radius, where the preset distance may be set arbitrarily according to an empirical value or an actual requirement, and the present disclosure does not limit this, for example, taking two alternative routes X and Y that intersect each other in space as an example, the preset anti-collision occupied area may be a circular area with an intersection of the routes X and Y as a center of a circle and a preset distance D as a radius.
In step S302, a lane segment length of another candidate lane of the two candidate lanes located in the preset anti-collision occupied area is determined.
In this step, two intersection points of the other alternative route and the boundary of the preset anti-collision occupied area may be obtained, and then a distance length between the two intersection points is used as a route length of the other alternative route located in the preset anti-collision occupied area.
In step S303, a first conflict duration of the two alternative routes is determined according to the route length.
In this step, the first conflict duration may be determined according to the flight speed of the drone on the alternative route and the route segment length.
It can be understood that the longer the route segment length of the other alternative route located in the preset anti-collision occupied area is, the longer the first collision duration is, which indicates that the two alternative routes have a more serious mutual collision, therefore, in the early operation stage of the unmanned aerial vehicle distribution service, one possible implementation manner may determine the collision influence value corresponding to the two alternative routes based on the first collision duration, that is, the first collision duration is directly used as the collision influence value corresponding to the two alternative routes.
After the unmanned aerial vehicle distribution service is operated for a long time in a large scale, actual execution data of the unmanned aerial vehicle for executing distribution tasks on the allocated routes can be acquired, for example, for the alternative routes X and Y, the unmanned aerial vehicles for executing distribution tasks on the alternative routes X and Y can be acquired, when the unmanned aerial vehicle takes off at the same take-off time, the late arrival time of the unmanned aerial vehicle on one route relative to the unmanned aerial vehicle on the other route can be considered as congestion time of the two routes, and after the unmanned aerial vehicle is operated for a long time, a plurality of late arrival times of the unmanned aerial vehicles for executing distribution tasks on the two alternative routes X and Y can be obtained through statistics based on big data, relatively accurate actual conflict time of the two alternative routes X and Y can be obtained (for example, the average value of the plurality of late arrival times is taken as the actual conflict time of the two alternative routes X and Y), in this case, to improve the accuracy of the collision influence values corresponding to the two alternative routes, the determined collision influence value may be updated based on the actual collision data of the two alternative routes obtained through big data statistics, and therefore, in another possible implementation manner of the present disclosure, the collision influence value may be determined by performing steps S304-S305.
In step S304, collision data corresponding to the two candidate routes is obtained based on big data statistics, and the collision data includes a second collision duration or a collision level.
Wherein the second conflict duration is the actual conflict duration of the two alternative routes obtained after the unmanned aerial vehicle delivery service is operated for a long time and in a large scale, the conflict level may be another quantized data that is obtained by conversion according to the second conflict duration and represents the degree of conflict between the two alternative routes, for example, different conflict levels may be set in advance for the actual conflict durations located in different sections, the longer the actual conflict duration is, the higher the corresponding conflict level is, or the conflict level may also be a level formed by quantizing the number of conflicts occurring between the two obtained routes (the number of conflicts may be directly obtained from the historical scheduling task execution data corresponding to the routes recorded by the server), the specific manner of converting the second conflict duration to obtain the conflict level and converting the number of conflicts to obtain the conflict level may set a corresponding conversion policy according to the actual requirements, the present disclosure is not limited thereto.
In this step, the second conflict duration corresponding to the two alternative routes may be obtained based on the big data statistics in the following manner:
based on actual execution data (such as data of takeoff time, flight time and the like) of the unmanned aerial vehicle in the historical scheduling task when the unmanned aerial vehicle executes the flight task on the allocated air route, the waiting time or the detour time of the air route detour when the unmanned aerial vehicle on each alternative air route conflicts with the unmanned aerial vehicle on another alternative air route in the air route execution process is obtained, and the waiting time or the detour time is used as the second conflict time of the two corresponding alternative air routes.
For example, suppose that a drone executing route K waits for a drone on route J to avoid
Figure 725764DEST_PATH_IMAGE004
The time of (1) to continue to execute the route, then
Figure 368098DEST_PATH_IMAGE035
For example, the flight time of the detour route part of the unmanned aerial vehicle after adjustment is the second conflict time corresponding to the flight routes K and J, which is only an example, and the disclosure does not limit the second conflict time.
In addition, if a conflict exists between two routes in an actual application scene, the unmanned aerial vehicles on the two routes avoid the conflict, and the unmanned aerial vehicle on one route delays the takeoff time, so that the takeoff delay time of the unmanned aerial vehicles on the two alternative routes can be used as the second conflict duration of the two corresponding alternative routes.
Illustratively, if it is executedIn order to avoid collision between the unmanned plane of the airline K and the unmanned plane executing the airline J, the takeoff time of the unmanned plane of the airline K is delayed
Figure 847621DEST_PATH_IMAGE036
Take off at the same time, then
Figure 18839DEST_PATH_IMAGE037
I.e., the second conflict duration for airline K and airline J.
It should be further noted that, in the process of obtaining the second conflict duration based on big data statistics, in order to improve the accuracy of the determined conflict influence value between routes, an average value of multiple measurement results may be used as the second conflict duration.
In step S305, the conflict influence value corresponding to the two alternative routes is determined according to the first conflict duration and the conflict data.
In this step, the collision influence value corresponding to the two alternative routes can be determined by the following formula:
Figure 849392DEST_PATH_IMAGE038
wherein,
Figure 528373DEST_PATH_IMAGE002
representing the conflicting impact values for the two alternative routes,
Figure 862402DEST_PATH_IMAGE003
a first duration of the collision is indicated,
Figure 470101DEST_PATH_IMAGE004
a second collision duration is indicated and,
Figure 522371DEST_PATH_IMAGE005
the level of the conflict is indicated,
Figure 240928DEST_PATH_IMAGE006
representing conflicting data pairsThe confidence factor of the response is determined,
Figure 695043DEST_PATH_IMAGE007
a confidence factor indicating the correspondence of the first collision duration,
Figure 473643DEST_PATH_IMAGE006
、
Figure 13209DEST_PATH_IMAGE007
are each a number greater than 0 and less than 1.
In addition, the confidence factor corresponding to the conflict data in the formula
Figure 33993DEST_PATH_IMAGE006
Confidence factor corresponding to first conflict duration
Figure 77035DEST_PATH_IMAGE007
For example, in an initial operation period, the confidence factor corresponding to the first conflict duration is generally greater than the confidence factor corresponding to the conflict data, and after a long time of operation, as the statistical result of the big data is more and more accurate, the value of the confidence factor corresponding to the conflict data is higher and higher, and the value of the confidence factor corresponding to the first conflict duration is lower and higher.
Based on the method, after big data analysis is carried out according to a large-scale operation result, the conflict influence value corresponding to each two alternative routes is maintained and updated, so that the confidence coefficient of the conflict influence value is improved, and the reliability and the effectiveness of route allocation are further improved.
In addition, fig. 4 is a flowchart of another method for allocating air routes according to the embodiment shown in fig. 1, and as shown in fig. 4, after step S105 is executed, in order to further improve the reliability of the collision influence value corresponding to each two alternative air routes, after the unmanned aerial vehicle executes a flight mission according to the allocated target air route, big data statistics may be performed again to obtain the latest collision data corresponding to the two alternative air routes, so that the collision influence value is continuously updated and maintained based on the latest acquired collision data. Thus, as shown in fig. 4, the method further comprises the steps of:
in step S106, a plurality of actual conflict durations corresponding to the two candidate routes are obtained according to a plurality of actual flight tasks on the two candidate routes.
The manner of acquiring the actual conflict duration has already been described in steps S303 to S304, and is not described herein again.
In step S107, the conflict data is updated according to a plurality of the actual conflict durations.
In this step, an average duration of a plurality of actual collision durations may be obtained, and then the average duration is used as the updated second collision duration, and then the collision level is updated based on the updated second collision duration.
In step S108, the conflict influence values corresponding to the two candidate routes are updated according to the updated conflict data.
In this step, the updated collision influence value may be obtained by combining the formula in step S305 with the updated collision data.
By adopting the method, the actual space constraint among the air routes and the influence of the historical flight tasks or other flight tasks of the same air route are comprehensively considered for carrying out air route distribution, so that the congestion delay in the execution process of the large-scale air route is reduced, the distribution timeliness is improved, in addition, the big data analysis is carried out according to the large-scale operation result to maintain and update the conflict influence values corresponding to every two alternative air routes, the confidence coefficient of the conflict influence values is improved, and the reliability and the effectiveness of the air route distribution are improved.
FIG. 5 is a block diagram illustrating an apparatus for allocating routes, as shown in FIG. 5, according to an exemplary embodiment, including:
the cost table building module 501 is used for building a flight path conflict cost table between a first alternative flight path of at least one flight task and a second alternative flight path of other flight tasks, wherein conflict influence values among different flight paths are set in the flight path conflict cost table, and the conflict influence values are used for representing the severity of mutual conflict among the different flight paths;
a first obtaining module 502, configured to obtain a plurality of alternative airline sets corresponding to target flight tasks of current airlines to be allocated, where each alternative airline set includes an alternative airline corresponding to each target flight task;
a first determining module 503, configured to determine a target collision influence value of each alternative airline set according to the collision influence value in the airline collision cost table, where the target collision influence value is used to characterize a degree of collision between airlines in a corresponding alternative airline set;
a second determining module 504, configured to determine a target route corresponding to each target flight task according to the target conflict influence value, so as to allocate the corresponding target route to each target flight task;
a sending module 505, configured to send the target route to a control terminal of the unmanned aerial vehicle, so that the control terminal controls the unmanned aerial vehicle to execute the target route.
Optionally, the first determining module 503 is configured to, for each alternative route set, find, from the route conflict cost table, a target influence value corresponding to each two routes in the alternative route set; and taking the sum of the target influence values corresponding to every two routes in the alternative route set as the target conflict influence value corresponding to the alternative route set.
Optionally, fig. 6 is a block diagram of an apparatus for allocating routes according to the embodiment shown in fig. 5, as shown in fig. 6, the apparatus further comprising:
a second obtaining module 506, configured to obtain, for each alternative route set, the number of times that each alternative route in the alternative route set is occupied within a preset time period;
the first determining module 503 is configured to determine a target collision influence value of each candidate route set according to the collision influence value and the number in the route collision cost table.
Optionally, the first determining module 503 is configured to, for each candidate route set, search, from the collision influence values, a target influence value corresponding to each two routes in the candidate route set; and determining the target conflict influence value of the alternative route set according to the target influence values corresponding to every two routes in the alternative route set and the times of each alternative route in the alternative route set being occupied in a preset time period.
Optionally, the second determining module 504 is configured to use the route in the set of candidate routes with the smallest target collision influence value as the target route.
Optionally, the first obtaining module 502 is configured to, for each target flight task of at least one target flight task, determine at least one alternative route corresponding to the target flight task from multiple preset routes; and combining each alternative route corresponding to the first flight task with each alternative route corresponding to the second flight task to obtain a plurality of alternative route sets, wherein the first flight task is any target flight task, and the second flight task is at least one target flight task except the first flight task in the target flight tasks.
Optionally, the cost table constructing module 501 is configured to, for every two alternative routes, obtain a preset anti-collision occupied area corresponding to one of the two alternative routes, where the every two alternative routes include one first alternative route and one second alternative route; determining the length of the other alternative route in the preset anti-collision occupied area; determining a first conflict duration of the two alternative routes according to the route length; and determining the conflict influence value corresponding to the two alternative routes according to the first conflict duration.
Optionally, the cost table constructing module 501 is configured to obtain conflict data corresponding to the two alternative routes based on big data statistics, where the conflict data includes a second conflict duration or a conflict level; determining the conflict influence values corresponding to the two alternative routes according to the first conflict duration and the conflict data by the following formula:
Figure 26536DEST_PATH_IMAGE039
wherein,
Figure 584557DEST_PATH_IMAGE002
representing the conflicting impact values for the two alternative routes,
Figure 910496DEST_PATH_IMAGE003
a first duration of the collision is indicated,
Figure 73624DEST_PATH_IMAGE004
a second collision duration is indicated and,
Figure 928447DEST_PATH_IMAGE005
the level of the conflict is indicated,
Figure 239343DEST_PATH_IMAGE006
indicating the confidence factor that the conflicting data corresponds to,
Figure 103394DEST_PATH_IMAGE007
and representing a confidence factor corresponding to the first conflict duration.
FIG. 7 is a block diagram of an apparatus for allocating routes, shown in FIG. 7, according to the embodiment shown in FIG. 6, further comprising:
the updating module 507 is configured to obtain a plurality of actual conflict durations corresponding to the two alternative routes according to a plurality of actual flight tasks on the two alternative routes; updating the conflict data according to a plurality of actual conflict durations; and updating the collision influence values corresponding to the two alternative routes according to the updated collision data.
With regard to the apparatus in the above-described embodiment, the specific manner in which each module performs the operation has been described in detail in the embodiment related to the method, and will not be elaborated here.
By adopting the device, the actual space constraint between the air routes and the influence of the historical flight tasks or other flight tasks on the same air route are comprehensively considered for carrying out air route allocation, so that the congestion delay in the execution process of the large-scale air routes is reduced, the timeliness of the completion of the flight tasks is improved, in addition, the big data analysis is carried out according to the large-scale operation result to maintain and update the conflict influence values corresponding to every two alternative air routes, the confidence coefficient of the conflict influence values is improved, and the reliability and the effectiveness of the air route allocation are improved.
Fig. 8 is a block diagram illustrating an electronic device 800 in accordance with an example embodiment. For example, the electronic device 800 may be provided as a server. Referring to fig. 8, an electronic device 800 includes a processor 822, which may be one or more in number, and a memory 832 for storing computer programs executable by the processor 822. The computer programs stored in memory 832 may include one or more modules that each correspond to a set of instructions. Further, the processor 822 may be configured to execute the computer program to perform the method of allocating routes described above.
Additionally, the electronic device 800 may also include a power component 826 and a communication component 850, the power component 826 may be assigned to perform power management of the electronic device 800, and the communication component 850 may be assigned to enable communication, e.g., wired or wireless communication, of the electronic device 800. The electronic device 800 may also include input/output (I/O) interfaces 858. The electronic device 800 may operate based on an operating system, such as Windows Server, stored in the memory 832TM，Mac OS XTM，UnixTM，LinuxTMAnd so on.
In another exemplary embodiment, a computer readable storage medium comprising program instructions which, when executed by a processor, implement the steps of the method of allocating lanes described above is also provided. For example, the computer readable storage medium may be the memory 832 including program instructions as described above that are executable by the processor 822 of the electronic device 800 to perform the method of allocating routes described above.
In another exemplary embodiment, a computer program product is also provided, which comprises a computer program executable by a programmable apparatus, the computer program having code portions for performing the above-described method of allocating airlines when executed by the programmable apparatus.
The preferred embodiments of the present disclosure are described in detail with reference to the accompanying drawings, however, the present disclosure is not limited to the specific details of the above embodiments, and various simple modifications may be made to the technical solution of the present disclosure within the technical idea of the present disclosure, and these simple modifications all belong to the protection scope of the present disclosure.
It should be noted that, in the foregoing embodiments, various features described in the above embodiments may be combined in any suitable manner, and in order to avoid unnecessary repetition, various combinations that are possible in the present disclosure are not described again.
In addition, any combination of various embodiments of the present disclosure may be made, and the same should be considered as the disclosure of the present disclosure, as long as it does not depart from the spirit of the present disclosure.

Claims (10)

1. A method of allocating airlines, the method comprising:
establishing a flight path conflict cost table between a first alternative flight path of at least one flight task and a second alternative flight path of other flight tasks, wherein conflict influence values among different flight paths are set in the flight path conflict cost table, and the conflict influence values are used for representing the severity of mutual conflict among the different flight paths;
acquiring a plurality of alternative route sets corresponding to target flight tasks of current routes to be allocated, wherein the alternative route sets comprise an alternative route corresponding to each target flight task;
determining a target conflict influence value of each alternative airline set according to the conflict influence value in the airline conflict cost table, wherein the target conflict influence value is used for representing the conflict degree between airlines in the corresponding alternative airline sets;
determining a target route corresponding to each target flight task according to the target conflict influence value so as to distribute the corresponding target route for each target flight task;
sending the target route to a control terminal of an unmanned aerial vehicle so that the control terminal controls the unmanned aerial vehicle to execute the target route;
the determining a target collision impact value for each alternative airline set according to the collision impact values in the airline collision cost table comprises:
for each alternative route set, searching target influence values corresponding to every two routes in the alternative route set from the route conflict cost table; taking the sum of the target influence values corresponding to every two routes in the alternative route set as the target conflict influence value corresponding to the alternative route set; or,
before the determining a target collision impact value for each set of alternative routes from the collision impact values in the route collision cost table, the method further comprises: acquiring the times of each alternative route in the alternative route set occupied in a preset time period aiming at each alternative route set; the determining a target collision impact value for each alternative airline set according to the collision impact values in the airline collision cost table comprises: and determining a target conflict influence value of each alternative route set according to the conflict influence value and the times in the route conflict cost table.
2. The method of claim 1 wherein said determining a target collision impact value for each of said set of alternative routes according to said collision impact values and said number of times in said route collision cost table comprises:
for each alternative route set, searching target influence values corresponding to every two routes in the alternative route set from the route conflict cost table;
and determining the target conflict influence value of the alternative route set according to the target influence values corresponding to every two routes in the alternative route set and the times of each alternative route in the alternative route set being occupied in a preset time period.
3. The method of claim 1, wherein the determining a target flight path corresponding to each of the target flight missions according to the target collision impact values comprises:
and taking the route in the candidate route set with the minimum target conflict influence value as the target route.
4. The method of claim 1, wherein the obtaining a plurality of alternative route sets corresponding to the target flight mission of the current route to be allocated comprises:
aiming at each target flight task in at least one target flight task, determining at least one alternative route corresponding to the target flight task from a plurality of preset routes;
and combining each alternative route corresponding to a first flight task with each alternative route corresponding to a second flight task to obtain a plurality of alternative route sets, wherein the first flight task is any target flight task, and the second flight task is a target flight task except the first flight task in at least one target flight task.
5. The method of any one of claims 1-4, wherein establishing a course collision cost table between a first alternative course for at least one flight mission and a second alternative course for other flight missions comprises:
aiming at every two alternative routes, acquiring a preset anti-collision occupied area corresponding to one of the two alternative routes, wherein each two alternative routes comprises one first alternative route and one second alternative route;
determining the length of the other alternative route in the preset anti-collision occupied area;
determining first conflict durations of the two alternative routes according to the route length;
and determining the conflict influence values corresponding to the two alternative routes according to the first conflict duration.
6. The method of claim 5, wherein prior to said determining said conflict impact values for the two candidate routes according to said first duration of conflict, said method further comprises:
acquiring conflict data corresponding to the two alternative routes based on big data statistics, wherein the conflict data comprise a second conflict duration or a conflict level;
the determining the collision influence values corresponding to the two alternative routes according to the first collision duration includes:
determining the collision influence values corresponding to the two alternative routes according to the first collision duration and the collision data by the following formula:
Figure 691097DEST_PATH_IMAGE001
wherein,
Figure 139396DEST_PATH_IMAGE002
representing the conflict effect values for the two alternative routes,
Figure 653554DEST_PATH_IMAGE003
a first duration of the collision is indicated,
Figure 970135DEST_PATH_IMAGE004
a second collision duration is indicated and,
Figure 518928DEST_PATH_IMAGE005
the level of the conflict is indicated,
Figure 138128DEST_PATH_IMAGE006
indicating the confidence factor that the conflicting data corresponds to,
Figure 811686DEST_PATH_IMAGE007
to representA confidence factor corresponding to the first conflict duration.
7. The method of claim 6, wherein after said assigning a corresponding target flight path for each of said target missions, said method further comprises:
acquiring a plurality of actual conflict durations corresponding to the two alternative routes according to a plurality of actual flight tasks on the two alternative routes;
updating the conflict data according to a plurality of actual conflict durations;
and updating the collision influence values corresponding to the two alternative routes according to the updated collision data.
8. An apparatus for allocating routes, the apparatus comprising:
the system comprises a cost table construction module, a cost table construction module and a cost calculation module, wherein the cost table construction module is used for establishing a flight path conflict cost table between a first alternative flight path of at least one flight task and a second alternative flight path of other flight tasks, conflict influence values among different flight paths are arranged in the flight path conflict cost table, and the conflict influence values are used for representing the severity of mutual conflict among the different flight paths;
the system comprises a first acquisition module, a second acquisition module and a third acquisition module, wherein the first acquisition module is used for acquiring a plurality of alternative route sets corresponding to target flight tasks of current routes to be allocated, and each alternative route set comprises an alternative route corresponding to each target flight task;
a first determining module, configured to determine a target collision influence value of each alternative airline set according to the collision influence value in the airline collision cost table, where the target collision influence value is used to characterize a degree of collision between airlines in a corresponding alternative airline set;
the second determining module is used for determining a target route corresponding to each target flight task according to the target conflict influence value so as to allocate the corresponding target route to each target flight task;
the sending module is used for sending the target route to a control terminal of the unmanned aerial vehicle so that the control terminal controls the unmanned aerial vehicle to execute the target route;
the first determining module is used for searching target influence values corresponding to every two routes in the alternative route set from the route conflict cost table for each alternative route set; taking the sum of the target influence values corresponding to every two routes in the alternative route set as the target conflict influence value corresponding to the alternative route set; or,
the device further comprises: the second acquisition module is used for acquiring the times of each alternative route in the alternative route set being occupied in a preset time period aiming at each alternative route set; and the first determining module is used for determining a target conflict influence value of each alternative route set according to the conflict influence value and the times in the route conflict cost table.
9. A computer-readable storage medium, on which a computer program is stored which, when being executed by a processor, carries out the steps of the method according to any one of claims 1 to 7.
10. An electronic device, comprising:
a memory having a computer program stored thereon;
a processor for executing the computer program in the memory to carry out the steps of the method of any one of claims 1 to 7.
CN202110377402.3A 2021-04-08 2021-04-08 Method and device for allocating routes, storage medium and electronic equipment Active CN112801601B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202110377402.3A CN112801601B (en) 2021-04-08 2021-04-08 Method and device for allocating routes, storage medium and electronic equipment

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110377402.3A CN112801601B (en) 2021-04-08 2021-04-08 Method and device for allocating routes, storage medium and electronic equipment

Publications (2)

Publication Number Publication Date
CN112801601A CN112801601A (en) 2021-05-14
CN112801601B true CN112801601B (en) 2021-07-02

Family

ID=75816590

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110377402.3A Active CN112801601B (en) 2021-04-08 2021-04-08 Method and device for allocating routes, storage medium and electronic equipment

Country Status (1)

Country Link
CN (1) CN112801601B (en)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114154870B (en) * 2021-11-30 2025-06-17 北京京东振世信息技术有限公司 Resource allocation method, resource allocation device, computer readable medium and device
CN116339324B (en) * 2023-03-09 2026-01-30 北京航天发射技术研究所 A route planning method and system suitable for unmanned surface vessel swarm control

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101131755A (en) * 2007-10-19 2008-02-27 北京航空航天大学 A path planning method for maintaining team CGF formation based on real terrain
CN103116825A (en) * 2013-01-29 2013-05-22 江苏省邮电规划设计院有限责任公司 Intelligent city management system

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105069595A (en) * 2015-08-18 2015-11-18 杨珊珊 Express system and method employing unmanned plane
CN105354633A (en) * 2015-10-26 2016-02-24 努比亚技术有限公司 Transportation route calculation system and method
CN107886201B (en) * 2017-11-29 2021-01-12 合肥有空科技信息技术有限公司 Multi-objective optimization method and device for multi-unmanned aerial vehicle task allocation
CN108446914A (en) * 2018-03-20 2018-08-24 中国计量大学 A kind of unmanned plane method of servicing and system based on cloud platform
JP7094365B2 (en) * 2018-07-18 2022-07-01 良平 上瀧 Air rights management system
CN109598470B (en) * 2018-12-03 2021-09-24 上海木木聚枞机器人科技有限公司 Method and system for delivering medicines in a hospital

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101131755A (en) * 2007-10-19 2008-02-27 北京航空航天大学 A path planning method for maintaining team CGF formation based on real terrain
CN103116825A (en) * 2013-01-29 2013-05-22 江苏省邮电规划设计院有限责任公司 Intelligent city management system

Also Published As

Publication number Publication date
CN112801601A (en) 2021-05-14

Similar Documents

Publication Publication Date Title
US12014625B2 (en) Node of a decentralized airspace management system
KR102315364B1 (en) Method and device for outputting information
US10580309B2 (en) Resilient enhancement of trajectory-based operations in aviation
JP2892336B2 (en) Runway reservation system
CN112783195A (en) Routing inspection route planning method and device for multiple unmanned aerial vehicles and computer equipment
US11605300B2 (en) Aircraft operation system
Khochare et al. Heuristic algorithms for co-scheduling of edge analytics and routes for UAV fleet missions
US11380209B2 (en) Information processing apparatus
JP2022523231A (en) Drone cluster system, takeoff control method, equipment, system and readable medium
US11222546B2 (en) Pairing aircraft during flight
CN112801601B (en) Method and device for allocating routes, storage medium and electronic equipment
JP7071544B2 (en) Information processing equipment
US12154445B2 (en) Collaborative traffic management
Ji et al. An evolutionary approach for dynamic single-runway arrival sequencing and scheduling problem
EP3789984A1 (en) System for optimising transient kerbside access
CN112447068A (en) Runway allocation method, terminal and storage device for multi-runway airport
CN118153920A (en) Multi-point unmanned aerial vehicle flight task intelligent planning method and system and electronic equipment
Li et al. An integrated optimization strategy for mission planning and control resource allocation for long-endurance unmanned aerial vehicle
US12300112B2 (en) Pre-departure sequencing using multi-agent reinforcement learning
EP4372640A1 (en) Pre-departure sequencing using multi-agent reinforcement learning
US20250029033A1 (en) System and method for optimizing airport operations
Sadovsky et al. Bin-and-sort: a Policy and Method for Having a Distributed System Schedule and Arbitrate Flights Pre-departure
Sadovsky et al. A Simulation Study of Bin-and-Sort Policies in a Distributed System for Flights Scheduling
CN120877561A (en) Time window-based double-layer low-altitude route network flight plan allocation method and system
CN120913454A (en) Empty pipe scene instruction recommendation method and system combined with knowledge graph

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