A Route Planning Strategy for Commercial …
323
Table 5 a Details of simulation experiments b Summary of selected results across multiple
simulations for different numbers of orders (K)
Inputs : Grid (2D) dimensions, Number of orders (K)
max number of items in any single order (nmax items )
and max quantity of any item (nmax units )
The same grid was used for all experiments,
customer coordinates randomly generated for each run
For each fixed K, multiple order sets randomly
generated such that in any customer order
number of unique items ≤ nmax items = 7
quantity of any item ≤ nmax units = 4
# orders
% improvement
(K) over baseline approach
min mean
max
50
45.40 48.35
49.82
100
48.44 49.35
50.19
200
49.92 50.50
51.15
500
52.25 52.84
53.71
1000 52.65 53.42
54.21
(a)
(b)
computation overhead and hence may not be suitable for a dynamic scenario where
orders are frequently updated. The main advantage of our proposed approach is its
simplicity which allows scalability to practical scenarios. We are currently working
on extending it to the scenario of multiple drones and multiple warehouses.
References
1. Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manage Sci 6:8091
2. Crevier B, Cordeau J-F, Laporte G (2007) The multi-depot vehicle routing problemwith interdepot routes. Eur J Oper Res 176(2):756773
3. Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: optimization of
drone-assisted parcel delivery. Transp Res Part C 54:86–109
4. Ha, Minh, Deville, Yves, Pham, Dung, Ha, Minh (2018) On the min-cost traveling salesman
problem with drone. Transp Res Part C: EmergingTechnol 86:597–621
5. Dorling K, Heinrichs J, Messier GG, Magierowski S (2017) Vehicle routing problems for drone
delivery. IEEE Trans SMC 47(1):70–85
6. Wang X, Poikonen S, Golden B (2017) The vehicle routing problem with drones:several worstcase results. Optim Lett 11:679697
7. Chang Y, Lee HJ (2018) Optimal delivery routing with wider drone-deliveryareas along a
shorter truck-route. Expert Syst Appl 104:307–317
8. Caric T, Gold H (eds) (2008) Vehicle routing problem. In-Tech
323
Table 5 a Details of simulation experiments b Summary of selected results across multiple
simulations for different numbers of orders (K)
Inputs : Grid (2D) dimensions, Number of orders (K)
max number of items in any single order (nmax items )
and max quantity of any item (nmax units )
The same grid was used for all experiments,
customer coordinates randomly generated for each run
For each fixed K, multiple order sets randomly
generated such that in any customer order
number of unique items ≤ nmax items = 7
quantity of any item ≤ nmax units = 4
# orders
% improvement
(K) over baseline approach
min mean
max
50
45.40 48.35
49.82
100
48.44 49.35
50.19
200
49.92 50.50
51.15
500
52.25 52.84
53.71
1000 52.65 53.42
54.21
(a)
(b)
computation overhead and hence may not be suitable for a dynamic scenario where
orders are frequently updated. The main advantage of our proposed approach is its
simplicity which allows scalability to practical scenarios. We are currently working
on extending it to the scenario of multiple drones and multiple warehouses.
References
1. Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manage Sci 6:8091
2. Crevier B, Cordeau J-F, Laporte G (2007) The multi-depot vehicle routing problemwith interdepot routes. Eur J Oper Res 176(2):756773
3. Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: optimization of
drone-assisted parcel delivery. Transp Res Part C 54:86–109
4. Ha, Minh, Deville, Yves, Pham, Dung, Ha, Minh (2018) On the min-cost traveling salesman
problem with drone. Transp Res Part C: EmergingTechnol 86:597–621
5. Dorling K, Heinrichs J, Messier GG, Magierowski S (2017) Vehicle routing problems for drone
delivery. IEEE Trans SMC 47(1):70–85
6. Wang X, Poikonen S, Golden B (2017) The vehicle routing problem with drones:several worstcase results. Optim Lett 11:679697
7. Chang Y, Lee HJ (2018) Optimal delivery routing with wider drone-deliveryareas along a
shorter truck-route. Expert Syst Appl 104:307–317
8. Caric T, Gold H (eds) (2008) Vehicle routing problem. In-Tech