Operating a plurality of drones and trucks in package delivery

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 Σ∀dεD,pεPwp·A(d,p),
• subject to:
• A(d,p)ε{0,1}
• ∀d0,d1εD,pεP:A(do,p)=1A(d1,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),k0)+Σiε1 . . . |K|−2Distance(ki,ki+1)+Distance(k|K|−1,End(d))≦Range(d),
• wherein D represents a set of the drones,
• P represents a set of the packages,
• wp 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.

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 Σ∀dεD,pεP·wp·A(d,p),
• subject to:
• A(d,p)ε{0,1}
• ∀d0,d1εD, pεP:
• A(do,p)=1A(d1,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),k0)+Σiε1 . . . |K|−2Distance(ki,ki+1)+Distance(k|K|−1,End(d))≦Range(d),
• wherein D represents a set of the drones,
• P represents a set of the packages,
• wp 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.