320
S. Manna and A. Narasimhamurthy
Table 2 APD algorithm
3.2 APD Model
In the APD model, we allow partial delivery to the customers. The first trip is selected
in exactly the same manner as in the NAPD approach. Next, we consider splitting order of each customer whose order is not fulfilled as follows. For a candidate
customer, sort the items in ascending order of total weight. Select the first item if
its weight (= product unit weight x number of items) can be included within the
drone’s remaining capacity, continue including more items from same customer till
no more items can be included. This greedy approach which splits itemwise ensures
a unique split (if any) for each candidate customer. Run the NAPD approach on this
modified set of orders and compute the schedule. This is repeated for each candidate customer. Of all possible candidate splits, suppose splitting order of customer
c j yields the lowest overall distance. If this is lower than the solution from NAPD,
only then c j ’s order is split as above (since it yields a solution better than not splitting
any customer’s order). Table 2 provides the APD algorithm in detail.
4 Results
We illustrate the details of the two proposed schemes, first by toy examples, these
results are summarized in Table 4. We have run our experiments on larger problem
sizes in order to assess the running time of the approach, these results are summarized
in Table 5. In all our simulation experiments, we used a simple, basic approach as the
baseline for comparison.The baseline approach used for comparison is just servicing
one order fully in one trip, flying back to the warehouse, and so on till all orders are
fully serviced. For illustration we have used integer coordinates and weights in the
examples, we have dropped the unit for convenience, however, any suitable unit (e.g.
grams for weight and metres for distance) can be used for the real-world scenario.
Example 1 Toy example (the numbers are for illustration only:)
Product catalogue: 4 products P1,P2,P3,P4 each unit weight = 50 gms
Warehouse location = (0,0)
Initial location of drone = (0,0), Weight carrying capacity of drone = 1000 gms
Customer locations: C 1 : (10; 10);C 2 : (15; 10);C 3 : (15; 18);C 4 : (17; 10)
S. Manna and A. Narasimhamurthy
Table 2 APD algorithm
3.2 APD Model
In the APD model, we allow partial delivery to the customers. The first trip is selected
in exactly the same manner as in the NAPD approach. Next, we consider splitting order of each customer whose order is not fulfilled as follows. For a candidate
customer, sort the items in ascending order of total weight. Select the first item if
its weight (= product unit weight x number of items) can be included within the
drone’s remaining capacity, continue including more items from same customer till
no more items can be included. This greedy approach which splits itemwise ensures
a unique split (if any) for each candidate customer. Run the NAPD approach on this
modified set of orders and compute the schedule. This is repeated for each candidate customer. Of all possible candidate splits, suppose splitting order of customer
c j yields the lowest overall distance. If this is lower than the solution from NAPD,
only then c j ’s order is split as above (since it yields a solution better than not splitting
any customer’s order). Table 2 provides the APD algorithm in detail.
4 Results
We illustrate the details of the two proposed schemes, first by toy examples, these
results are summarized in Table 4. We have run our experiments on larger problem
sizes in order to assess the running time of the approach, these results are summarized
in Table 5. In all our simulation experiments, we used a simple, basic approach as the
baseline for comparison.The baseline approach used for comparison is just servicing
one order fully in one trip, flying back to the warehouse, and so on till all orders are
fully serviced. For illustration we have used integer coordinates and weights in the
examples, we have dropped the unit for convenience, however, any suitable unit (e.g.
grams for weight and metres for distance) can be used for the real-world scenario.
Example 1 Toy example (the numbers are for illustration only:)
Product catalogue: 4 products P1,P2,P3,P4 each unit weight = 50 gms
Warehouse location = (0,0)
Initial location of drone = (0,0), Weight carrying capacity of drone = 1000 gms
Customer locations: C 1 : (10; 10);C 2 : (15; 10);C 3 : (15; 18);C 4 : (17; 10)