Scribd
Upload
350 views11 pages

Optimizing Drone Delivery Trajectories

This document proposes using evolutionary algorithms to optimize drone delivery routing and scheduling. It describes a scenario where drones pickup and deliver packages between a warehouse and customers. The goal is to maximize the number of deliveries while minimizing flight path length and battery usage. Customers and drones are represented on a 2D grid. An ant colony optimization algorithm is suggested to select an optimal subset of customers for drones to service. The model also allows for replanning routes in response to urgent pickup requests.

Uploaded by

kadarsh226521
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
350 views11 pages

Optimizing Drone Delivery Trajectories

This document proposes using evolutionary algorithms to optimize drone delivery routing and scheduling. It describes a scenario where drones pickup and deliver packages between a warehouse and customers. The goal is to maximize the number of deliveries while minimizing flight path length and battery usage. Customers and drones are represented on a 2D grid. An ant colony optimization algorithm is suggested to select an optimal subset of customers for drones to service. The model also allows for replanning routes in response to urgent pickup requests.

Uploaded by

kadarsh226521
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

DRONE DELIVERY SYSTEM

Problem Statement
To apply evolutionary algorithms in calculating
flight trajectory of drone for packages delivery.
To propose which evolutionary algorithm to
use and apply it to the problem.
Scenario of drone delivery
There is distribution center of courier
company which takes and deliver products to
the consumers in the city and its outskirts
using drones.

The drones pickup and deliver products


between warehouse and customers.

The company wants to do such scheduling of


drones so that it optimizes the number of
Assumption
We have made certain assumptions to avoid
nonlinearity relations.
Such as :
Drone will travel at constant speed,
it will fly at constant height,
there is no restriction on air space so drone
will take straight line path,
battery utilization is constant if drone is in
air(either traveling or hovering in air) for a
certain amount of weight of courier packages.
Representation
Costumers location and drone position can be
located in 2d grid having longitude and
latitude as its coordinates.
The drones will start from a warehouse
distribute/pickup packages from customers
and end their journey in another distribution
center or charging station.
The customers can be represented as ordered
pair (xi,yi) and the solution is the permutation
of (xi,yi), each time a drone is schedule a new
Representation cont.
We have n customers out of which we have to
choose r customers such that accommodation
of package and their weights is optimum. And
for those r customers we have to decide the
shortest route (TSP).
Various functions needed
Length of path = [(xi+1,yi+1)-(xi,yi)]2
The fitness function is
F = k(p1c1+p2c2++prcr)+(1-k)(length of path)
k is a parameter that decides which to give
more priority whether number of customers
or length,(default k0.5)
Pi is the priority of customers this term will be
used to select the new customers in case of
mutation
Pi value will increase if a ith customer is left in
Function cont.
Battery usage = d1w1+d2w2+..drwr.
Modified fitness function
F = k(p1c1+p2c2++prcr)+(1-k)(battery usage)
Algorithm for solution
Since this is discrete optimization problem
hence ACO can be used.
But we are doing a selection of r customers
from n customer.
Trajectory replanning
While drone is on its route delivering packages
some urgent pickup request can come from
user.
Then the nearest drone to that user should
reroute its path such that it after delivering
the nearest customer it goes to that urgent
request location collect it and continue back
on its original route.
The routing depends upon the battery status
of drone that is on (1-k) factor of its fitness
Trajectory preplanning cont.
If there are lots of random request generated
more than 5 than we will need to re-run ACO
algorithm to find new route.
This time the initial customer will always be in
solution and selection will be made from
random request.

You might also like