Operating a plurality of drones and trucks in package delivery

• US 9,792,576 B1
• Filed: 10/24/2016
• Issued: 10/17/2017
• Est. Priority Date: 10/24/2016
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jamjoom, Hani T., Lubensky, David M., Manweiler, Justin G., Weisz, Justin D.
• Primary Examiner(s): O'Hara, Brian M
• Application Number:
  US15/331,989
• Time in Patent Office: 358 Days
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• CPC Class Codes: B64U 2101/60 for transporting passengers; for transporting goods other than weapons
• CPC Class Codes: B64U 2101/64 for parcel delivery or retrieval
• CPC Class Codes: B64U 70/99 Means for retaining the UAV on the platform, e.g. dogs or magnets
• CPC Class Codes: B64U 80/25 for recharging batteries; for refuelling
• CPC Class Codes: B64U 80/86 Land vehicles
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06Q 10/0832 Special goods or special handling procedures, e.g. handling of hazardous or fragile goods

Abstract

Controlling drones and vehicles in package delivery, in one aspect, may include routing a delivery vehicle loaded with packages to a dropoff location based on executing on a hardware processor a spatial clustering of package destinations. A set of drones may be dispatched. A drone-to-package assignment is determined for the drones and the packages in the delivery vehicle. The drone is controlled to travel from the vehicle'"'"'s dropoff location to transport the assigned package to a destination point and return to the dropoff location to meet the vehicle. The delivery vehicle may be alerted to speed up or slow down to meet the drone at the return location, for example, without the delivery vehicle having to stop and wait at the dropoff location while the drone is making its delivery.

Claims

1. A method of controlling drones and vehicles in package delivery, comprising:

routing a delivery vehicle loaded with drones and packages to a dropoff location based on executing on a hardware processor a spatial clustering of package destinations;

configuring a drone to package assignment for the drones in the vehicle and the packages in the delivery vehicle, the configuring performed based on executing on the hardware processor an optimization function that maximizes a number of the packages delivered by the drones subject to a plurality of constraints, the optimization function given as input at least the dropoff location and the plurality of constraints,

the plurality of constraints comprising;

at least that a given package can only be delivered one time by one drone,

that weight of the given package must not exceed capacity of the drone, and

that for a single drone, a combined distance from the delivery vehicle to a first delivery plus a distance between each delivery, must not exceed a battery life of the drone subject to current wind conditions in drone'"'"'s delivery path, wherein the optimization function comprises maximizing Σ

<sub>∀

dε

D,pε

P</sub>w_p·

A(d,p),

subject to;

A(d, p)ε

{0,1}

∀

d₀,d₁ε

D,pε

P;

A(d_o,p)=1A(d₁,p)=0;

∀

dε

D,pε

P;

A(d,p)=1Capacity (d)≧

Weight (p); and

∀

dε

D;

Let K={∀

pε

P|A(d,p)=1}s. t. ∃

Permuation(K)|

Distance(Start(d),k₀)+Σ

<sub>iε

1 . . . |K|−

2</sub>Distance(k_i,k_i+1)+Distance(k<sub>|K|−

1</sub>,End(d))≦

Range(d),

wherein D represents a set of the drones,

P represents a set of the packages,

w_p represents a weight factor given to a package p being delivered to its destination,

Weight(p) represents a weight given to a package p,

Capacity(d) represents the maximum weight of a package that a drone can carry for delivery,

Range(d) represents a maximum distance a drone can travel based on a power source of the drone,

Start(d) represents a geographic location from where a drone is dispatched,

End(d) represents a geographic location where the drone returns after completing delivery of a package,

A(d, p)=1 represents that drone d will deliver package,

A(d, p)=0 represents that drone d will not deliver package p,

K represents a delivery order of packages,

k represents each stop along a drone'"'"'s delivery assignment of a package,

wherein A(d,p) and K are decision variables solved in the optimization function; and

controlling the drone to travel from the dropoff location to transport the assigned package to a destination point and return to the dropoff location to meet the vehicle.

2. The method of claim 1, further comprising controlling the delivery vehicle to speed up or slow down to meet the drone at the dropoff location without the delivery vehicle having to stop and wait at the dropoff location while the drone is making a delivery.

3. The method of claim 2, wherein the controlling the delivery vehicle further comprises tracking a current position of the delivery vehicle via a global positioning system.

4. The method of claim 1, wherein the delivery vehicles comprises a plurality of delivery vehicles each carrying a set of packages and a set of drones for assignment.

5. The method of claim 4, wherein the plurality of delivery vehicles have different dropoff locations from one another for dispatching and meeting with the set of drones.

6. The method of claim 1, wherein the optimization problem further outputs an assignment of delivery path comprising multiple delivery stops for the drone.

7. The method of claim 1, wherein the configuring a drone to package assignment and controlling the drone to travel from the dropoff location to transport the assigned package to a destination point and return to the dropoff location to meet the vehicle are repeated until all packages in the delivery vehicle are assigned for delivery.

8. A computer readable storage device storing a program of instructions executable by a machine to perform a method of controlling drones and vehicles in package delivery, the method comprising:

routing a delivery vehicle loaded with drones and packages to a dropoff location based on executing on a hardware processor a spatial clustering of package destinations;

configuring a drone to package assignment for the drones in the vehicle and the packages in the delivery vehicle, the configuring performed based on executing on the hardware processor an optimization function that maximizes a number of the packages delivered by the drones subject to a plurality of constraints, the optimization function given as input at least the dropoff location,

the plurality of constraints comprising;

at least that a given package can only be delivered one time by one drone,

that weight of the given package must not exceed capacity of the drone, and

that for a single drone, a combined distance from the delivery vehicle to a first delivery plus a distance between each delivery, must not exceed a battery life of the drone subject to current wind conditions in drone'"'"'s delivery path, wherein the optimization function comprises maximizing Σ

<sub>∀

dε

D,pε

P</sub>w_p·

A(d,p),

subject to;

A(d,p)ε

{0,1}

∀

d₀,d₁ε

D,pε

P;

A(d_o,p)=1A(d₁,p)=0;

∀

dε

D,pε

P;

A(d,p)=1Capacity (d)≧

Weight (p); and

∀

dε

D;

Let K={∀

pε

P|A(d,p)=1}s. t. ∃

Permuation(K)|

Distance(Start(d),k₀)+Σ

<sub>iε

1 . . . |K|−

2</sub>Distance(k_i,k_i+1)+Distance(k<sub>|K|−

1</sub>,End(d))≦

Range(d),

wherein D represents a set of the drones,

P represents a set of the packages,

w_p represents a weight factor given to a package p being delivered to its destination,

Weight(p) represents a weight given to a package p,

Capacity(d) represents the maximum weight of a package that a drone can carry for delivery,

Range(d) represents a maximum distance a drone can travel based on a power source of the drone,

Start(d) represents a geographic location from where a drone is dispatched,

End(d) represents a geographic location where the drone returns after completing delivery of a package,

A(d, p)=1 represents that drone d will deliver package,

A(d, p)=0 represents that drone d will not deliver package p,

K represents a delivery order of packages,

k represents each stop along a drone'"'"'s delivery assignment of a package,

wherein A(d,p) and K are decision variables solved in the optimization function; and

controlling the drone to travel from the dropoff location to transport the assigned package to a destination point and return to the dropoff location to meet the vehicle.

9. The computer readable storage device of claim 8, further comprising controlling the delivery vehicle to speed up or slow down to meet the drone at the dropoff location without the delivery vehicle having to stop and wait at the dropoff location while the drone is making a delivery.

10. The computer readable storage device of claim 9, wherein the controlling the delivery vehicle further comprises tracking a current position of the delivery vehicle via a global positioning system.

11. The computer readable storage device of claim 8, wherein the delivery vehicles comprises a plurality of delivery vehicles each carrying a set of packages and a set of drones for assignment.

12. The computer readable storage device of claim 11, wherein the plurality of delivery vehicles have different dropoff locations from one another for dispatching and meeting with the set of drones.

13. The computer readable storage device of claim 8, wherein the configuring a drone to package assignment and controlling the drone to travel from the dropoff location to transport the assigned package to a destination point and return to the dropoff location to meet the vehicle are repeated until all packages in the delivery vehicle are assigned for delivery.

14. A system of controlling drones and vehicles in package delivery, comprising:

a hardware processor operable to control routing of a delivery vehicle loaded with drones and packages to a dropoff location based on executing a spatial clustering of package destinations;

the hardware processor operable to configure a drone to package assignment for the drones and the packages in the delivery vehicle, the configuring performed based on executing on the hardware processor an optimization function that maximizes a number of the packages delivered by the drones subject to a plurality of constraints, the optimization function given as input at least the dropoff location and the plurality of constraints,

the plurality of constraints comprising;

at least that a given package can only be delivered one time by one drone,

that weight of the given package must not exceed capacity of the drone, and

that for a single drone, a combined distance from the delivery vehicle to a first delivery plus a distance between each delivery, must not exceed a battery life of the drone subject to current wind conditions in drone'"'"'s delivery path, wherein the optimization function comprises maximizing Σ

<sub>∀

dε

D,pε

P</sub>·

w_p·

A(d,p),

subject to;

A(d,p)ε

{0,1}

∀

d₀,d₁ε

D, pε

P;

A(d_o,p)=1A(d₁,p)=0;

∀

dε

D,pε

P;

A(d,p)=1Capacity (d)≧

Weight (p); and

∀

dε

D;

Let K={∀

pε

P|A(d,p)=1}s. t. ∃

Permuation(K)|

Distance(Start(d),k₀)+Σ

<sub>iε

1 . . . |K|−

2</sub>Distance(k_i,k_i+1)+Distance(k<sub>|K|−

1</sub>,End(d))≦

Range(d),

wherein D represents a set of the drones,

P represents a set of the packages,

w_p represents a weight factor given to a package p being delivered to its destination,

Weight(p) represents a weight given to a package p,

Capacity(d) represents the maximum weight of a package that a drone can carry for delivery,

Range(d) represents a maximum distance a drone can travel based on a power source of the drone,

Start(d) represents a geographic location from where a drone is dispatched,

End(d) represents a geographic location where the drone returns after completing delivery of a package,

A(d, p)=1 represents that drone d will deliver package,

A(d, p)=0 represents that drone d will not deliver package p,

K represents a delivery order of packages,

k represents each stop along a drone'"'"'s delivery assignment of a package,

wherein A(d,p) and K are decision variables solved in the optimization function; and

the hardware processor operable to control a drone to travel from the dropoff location to transport the assigned package to a destination point and return to the dropoff location to meet the vehicle.

15. The system of claim 14, wherein the hardware processor controls the delivery vehicle to speed up or slow down to meet the drone at the dropoff location without the delivery vehicle having to stop and wait at the dropoff location while the drone is making a delivery.

16. The system of claim 15, wherein the hardware processor further tracks a current position of the delivery vehicle via a global positioning system to control the delivery vehicle.

17. The system of claim 14, wherein the delivery vehicles comprises a plurality of delivery vehicles each carrying a set of packages and a set of drones for assignment.

18. The system of claim 17, wherein the plurality of delivery vehicles have different dropoff locations.

19. The system of claim 14, wherein the delivery vehicles is equipped with a landing pad for allowing the drone to land on the delivery vehicle while the delivery vehicle is moving.

20. The system of claim 14, wherein the hardware processor repeats configuring a drone to package assignment and controlling the drone to travel from the dropoff location to transport the assigned package to a destination point and return to the dropoff location to meet the vehicle until all packages in the delivery vehicle are assigned for delivery.