A Route Planning Strategy for Commercial …
319
3 Drone Scheduling Algorithms
We propose mainly two models for drone delivery scheduling system, we refer to
these as 1) Not Allowing Partial Delivery (NAPD) Model and 2) Allowing Partial
Delivery (APD) Model. No partial delivery is allowed in the NAPD scheme, only
those orders whose total weight is within the capacity of the drone (M) are serviced.
The APD scheme allows the option of splitting orders, this allows servicing even
those orders whose weight exceeds the drone capacity as long as the order can be
split item wise such that each the total weight of each suborder is within the drone’s
capacity. However, there may be multiple trips made to a customer location.
3.1 NAPD Model
Initially, the status of each order is set to FALSE. A new trip is always assumed to
start from the warehouse H. Scan the list d HC and identify the customer closest to H
whose order has not been fulfilled yet, let this customer be c i . Add c i to the current
trip, calculate weight of current order (CW) and update the remaining capacity of
drone (RW). Update start location of the next leg to c i . Scan the relevant list in D to
identify the nearest customer to c i , whose order is not yet fulfilled and order weight
is within remaining capacity. Repeat until no more orders can be included in current
trip. The algorithm details are given in Table 1, the sub-routine new-route is called
repeatedly on remaining customers until all orders are fulfilled.
Table 1 NAPD algorithm (sub-routine to compute a new trip)
319
3 Drone Scheduling Algorithms
We propose mainly two models for drone delivery scheduling system, we refer to
these as 1) Not Allowing Partial Delivery (NAPD) Model and 2) Allowing Partial
Delivery (APD) Model. No partial delivery is allowed in the NAPD scheme, only
those orders whose total weight is within the capacity of the drone (M) are serviced.
The APD scheme allows the option of splitting orders, this allows servicing even
those orders whose weight exceeds the drone capacity as long as the order can be
split item wise such that each the total weight of each suborder is within the drone’s
capacity. However, there may be multiple trips made to a customer location.
3.1 NAPD Model
Initially, the status of each order is set to FALSE. A new trip is always assumed to
start from the warehouse H. Scan the list d HC and identify the customer closest to H
whose order has not been fulfilled yet, let this customer be c i . Add c i to the current
trip, calculate weight of current order (CW) and update the remaining capacity of
drone (RW). Update start location of the next leg to c i . Scan the relevant list in D to
identify the nearest customer to c i , whose order is not yet fulfilled and order weight
is within remaining capacity. Repeat until no more orders can be included in current
trip. The algorithm details are given in Table 1, the sub-routine new-route is called
repeatedly on remaining customers until all orders are fulfilled.
Table 1 NAPD algorithm (sub-routine to compute a new trip)