322
S. Manna and A. Narasimhamurthy
Table 4 a and b Order Sets 1 & 2. The Order details column specifies the items ordered by that
customer as a set of (ProductID, Quantity) tuples. Eg. (P1,4),(P2,7) specifies that the order contains
4 units of product P1 and 7 units of product P2. c and d: Schedule computed by NAPD approach
for order set 1 (possible to combine more than one whole order) and order set 2 (not possible to
combine any two orders without exceeding drone capacity). The numbers indicate the distance for
that particular leg of the tour. e Order split which yielded the lowest overall distance and f Schedule
computed by the APD approach
(a) Order set 1 details
(b) Order set 2 details
Customer Location Order Weight
Details (gm)
C1
(10,10) (P1,10) 500
C2
(15,10) (P2,10) 500
C3
(15,18) (P3,10) 500
C4
(17,10) (P4,10) 500
Customer Location Order
Weight
Details
(gm)
C1
(10,10) (P1,4),(P2,7) 550
C2
(15,10) (P1,4),(P4,6) 500
C3
(15,18) (P3,7),(P4,5) 600
C4
(17,10) (P3,8),(P4,3) 550
NAPD results
(c) Computed NAPD schedule for order set 1
(d) Computed NAPD schedule for order set 2
Tour 1
H → C1 → C2 → H
14.14 + 5 + 18.03
Tour 2
H → C4 → C3 → H
19.72 + 8.24 + 23.41
Total distance
88.57 m
Tour 1
H → C1 → H(2 × 14.14)
Tour 2
H → C2 → H(2 × 18.03)
Tour 3
H → C4 → H(2 × 19.72)
Tour 4
H → C3 → H(2 × 23.41)
Total distance
150.65 m
APD results
CustomerId Location Order
Weight
details
(gm)
C1
(10,10) (P1,4),(P2,7) 550
C2.1
(15,10) (P1,4)
200
C2.2
(15,10) (P4,6)
300
C3
(15,18) [(P3,7),(P4,5)] 600
C4
(17,10) [(P3,8),(P4,3)] 550
Tour 1
H → C1 → C2.1 → H
14.14 + 5 + 18.03
Tour 2
H → C2.2 → C4 → H
18.03 + 2 + 19.72
Tour 3
H → C3 → H
23.43 + 23.43
Total distance 123.78 m
(e) Best order split (APD) for order set 2
(f) APD schedule computed for order set 2
where d alg and d baseline are the total distances covered by the schedules computed
by the algorithm and baseline approach, respectively. The minimum, average and
maximum percentage improvement across multiple order sets and for different K
are shown in Table 5. Although the improvement depends on the actual order details
and locations of customers relative to the warehouse, we observed that the proposed
approach was significantly better than the baseline in every case. The minimum
improvement observed was > 45%. As number of orders increases, the algorithm
would tend to yield significant improvement since there is more scope for combining
multiple orders in every step.
5 Conclusions
In this work, a heuristics based greedy heuristics approach is proposed for scheduling
drone deliveries. Although different types of approaches have been proposed in the
literature for various scheduling and routing problems, many entail a significant
S. Manna and A. Narasimhamurthy
Table 4 a and b Order Sets 1 & 2. The Order details column specifies the items ordered by that
customer as a set of (ProductID, Quantity) tuples. Eg. (P1,4),(P2,7) specifies that the order contains
4 units of product P1 and 7 units of product P2. c and d: Schedule computed by NAPD approach
for order set 1 (possible to combine more than one whole order) and order set 2 (not possible to
combine any two orders without exceeding drone capacity). The numbers indicate the distance for
that particular leg of the tour. e Order split which yielded the lowest overall distance and f Schedule
computed by the APD approach
(a) Order set 1 details
(b) Order set 2 details
Customer Location Order Weight
Details (gm)
C1
(10,10) (P1,10) 500
C2
(15,10) (P2,10) 500
C3
(15,18) (P3,10) 500
C4
(17,10) (P4,10) 500
Customer Location Order
Weight
Details
(gm)
C1
(10,10) (P1,4),(P2,7) 550
C2
(15,10) (P1,4),(P4,6) 500
C3
(15,18) (P3,7),(P4,5) 600
C4
(17,10) (P3,8),(P4,3) 550
NAPD results
(c) Computed NAPD schedule for order set 1
(d) Computed NAPD schedule for order set 2
Tour 1
H → C1 → C2 → H
14.14 + 5 + 18.03
Tour 2
H → C4 → C3 → H
19.72 + 8.24 + 23.41
Total distance
88.57 m
Tour 1
H → C1 → H(2 × 14.14)
Tour 2
H → C2 → H(2 × 18.03)
Tour 3
H → C4 → H(2 × 19.72)
Tour 4
H → C3 → H(2 × 23.41)
Total distance
150.65 m
APD results
CustomerId Location Order
Weight
details
(gm)
C1
(10,10) (P1,4),(P2,7) 550
C2.1
(15,10) (P1,4)
200
C2.2
(15,10) (P4,6)
300
C3
(15,18) [(P3,7),(P4,5)] 600
C4
(17,10) [(P3,8),(P4,3)] 550
Tour 1
H → C1 → C2.1 → H
14.14 + 5 + 18.03
Tour 2
H → C2.2 → C4 → H
18.03 + 2 + 19.72
Tour 3
H → C3 → H
23.43 + 23.43
Total distance 123.78 m
(e) Best order split (APD) for order set 2
(f) APD schedule computed for order set 2
where d alg and d baseline are the total distances covered by the schedules computed
by the algorithm and baseline approach, respectively. The minimum, average and
maximum percentage improvement across multiple order sets and for different K
are shown in Table 5. Although the improvement depends on the actual order details
and locations of customers relative to the warehouse, we observed that the proposed
approach was significantly better than the baseline in every case. The minimum
improvement observed was > 45%. As number of orders increases, the algorithm
would tend to yield significant improvement since there is more scope for combining
multiple orders in every step.
5 Conclusions
In this work, a heuristics based greedy heuristics approach is proposed for scheduling
drone deliveries. Although different types of approaches have been proposed in the
literature for various scheduling and routing problems, many entail a significant