A Route Planning Strategy for Commercial …
321
Consider a set of four customers and a product catalogue of four items as in
Example 1. The supporting data structures used repeatedly by the algorithms are
shown in Table 3. For the same warehouse and customer locations, we consider
two order sets as shown in Table 4a, b. In Order set 1, more than one order can be
accommodated within the drone’s capacity, whereas in Order set 2 no two orders
can be combined without exceeding the drone’s capacity. Table 4c, and d show
the schedule computed by the NAPD approach for the two order sets in the toy
example. As can be readily seen, the NAPD scheme tries to combine as many orders
as possible into a single trip. However, in order set 2, since no two orders can be
combined without exceeding the drone’s capacity, the NAPD schedule is the same as
the baseline approach. In the APD approach, the first trip is fixed as H → C 1 . Next,
the APD algorithm considers other customers as candidates whose orders can be split
and accommodated on the same trip. The modified order set obtained by splitting
order of customer C 2 is shown in Table 4e (split orders are assigned customer ids
as C 2:1 and C 2:2 ). For this example, the total distance covered in best split in APD
approach = 123.78, an improvement over the NAPD approach (distance = 150.65).
In the next set of experiments, multiple order sets each containing a fixed
number of orders (say K) were randomly generated. Our proposed approach was
run on each such order set and the percent improvement over the baseline
approach was computed as %improvement =
d baseline −d alg
d baseline
× 100
Table 3 Supporting data structures for toy example a Customers sorted in ascending order of
distance from warehouse, e.g. since warehouse is located at (0,0) and C 1 at (10,10) the Euclidean
distance is
√
200 = 14.14 b For each customer, list of other customers arranged in increasing order
of distance (D). For example, C 2 , C 4 and C 3 are located at distances of 5,7 and 9.43 from C 1
(a)
(b)
Customers arranged according to
distance from warehouse
H : [C1, 14.14], [C2, 18.03], [C4, 19.72], [C3, 23.41]
C1 [C2, 5] [C4, 7]
[C3, 9.43]
C2 [C4, 2] [C1, 5]
[C3, 8]
C3 [C2, 8] [C4, 8.24] [C1, 7]
C4 [C2, 2] [C1, 7]
[C3, 8.24]
321
Consider a set of four customers and a product catalogue of four items as in
Example 1. The supporting data structures used repeatedly by the algorithms are
shown in Table 3. For the same warehouse and customer locations, we consider
two order sets as shown in Table 4a, b. In Order set 1, more than one order can be
accommodated within the drone’s capacity, whereas in Order set 2 no two orders
can be combined without exceeding the drone’s capacity. Table 4c, and d show
the schedule computed by the NAPD approach for the two order sets in the toy
example. As can be readily seen, the NAPD scheme tries to combine as many orders
as possible into a single trip. However, in order set 2, since no two orders can be
combined without exceeding the drone’s capacity, the NAPD schedule is the same as
the baseline approach. In the APD approach, the first trip is fixed as H → C 1 . Next,
the APD algorithm considers other customers as candidates whose orders can be split
and accommodated on the same trip. The modified order set obtained by splitting
order of customer C 2 is shown in Table 4e (split orders are assigned customer ids
as C 2:1 and C 2:2 ). For this example, the total distance covered in best split in APD
approach = 123.78, an improvement over the NAPD approach (distance = 150.65).
In the next set of experiments, multiple order sets each containing a fixed
number of orders (say K) were randomly generated. Our proposed approach was
run on each such order set and the percent improvement over the baseline
approach was computed as %improvement =
d baseline −d alg
d baseline
× 100
Table 3 Supporting data structures for toy example a Customers sorted in ascending order of
distance from warehouse, e.g. since warehouse is located at (0,0) and C 1 at (10,10) the Euclidean
distance is
√
200 = 14.14 b For each customer, list of other customers arranged in increasing order
of distance (D). For example, C 2 , C 4 and C 3 are located at distances of 5,7 and 9.43 from C 1
(a)
(b)
Customers arranged according to
distance from warehouse
H : [C1, 14.14], [C2, 18.03], [C4, 19.72], [C3, 23.41]
C1 [C2, 5] [C4, 7]
[C3, 9.43]
C2 [C4, 2] [C1, 5]
[C3, 8]
C3 [C2, 8] [C4, 8.24] [C1, 7]
C4 [C2, 2] [C1, 7]
[C3, 8.24]