• Previous Article
    Designing and analysis of a Wi-Fi data offloading strategy catering for the preference of mobile users
  • JIMO Home
  • This Issue
  • Next Article
    Inventory replenishment policies for two successive generations price-sensitive technology products
May  2022, 18(3): 1651-1663. doi: 10.3934/jimo.2021037

Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations

Department of Mechanical and Systems Engineering, Korea Military Academy, Hwarang-Ro, Nowon-Gu, Seoul, 01805, Republic of Korea

* Corresponding author: Namsu Ahn, Soochan Kim

Received  May 2020 Revised  October 2020 Published  May 2022 Early access  March 2021

During military operations, obtaining information on remote battlefields is essential and recent advances in unmanned aerial vehicle technology have led to the use of drones to view battlefields. However, the use of drones in military operations introduces the new problem of determining travel routes for the drones. This type of problem is similar to the well-known classical vehicle routing problem, but the main difference is its objective function. For maintenance purposes, a minimized difference in travel distances is preferred. In addition, obtaining a shorter route in terms of travel distance is important. In this research, we propose a mathematical formulation and an optimal algorithm for the problem and suggest a simple heuristic to handle the large size instance of the problem. The computational results indicate that this algorithm can solve the real-scale instances of the problem, and the heuristic exhibits good performance even when the instance size of the problem is large.

Citation: Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1651-1663. doi: 10.3934/jimo.2021037
References:
[1]

N. AgatzP. Bouman and M. Schmidt, Optimization approaches for the traveling salesman problem with drone, Transportation Science, 52 (2018), 965-981. 

[2]

M. Dell'AmicoR. Montemanni and S. Novellani, Matheuristic algorithms for the parallel drone scheduling traveling salesman problem, Annals of Operations Research, 289 (2020), 211-226.  doi: 10.1007/s10479-020-03562-3.

[3]

K. DorlingJ. HeinrichsG. G. Messier and S. Magierowski, Vehicle routing problems for drone delivery, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47 (2017), 70-85.  doi: 10.1109/TSMC.2016.2582745.

[4]

Q. M. HaY. DevilleQ. D. Pham and M. H. Ha, On the min-cost traveling salesman problem with drone, Transportation Research Part C: Emerging Technologies, 86 (2018), 597-621.  doi: 10.1016/j.trc.2017.11.015.

[5]

G. Kim, What happened to the five major game-changer?, E-daily, (2019). www.edaily.co.kr.

[6]

J. Kim, N. Ahn, S. Kim, M. Kim and N. Cho, A study on the construction method of surveillance system using drone in transport command, Korea Military Academy Technical report, 18 (2018).

[7]

P. KitjacharoenchaiM. VentrescaM. Moshref-JavadiS. LeeJ. M. Tanchoco and P. A. Brunese, Multiple traveling salesman problem with drones: Mathematical model and heuristic approach, Computers & Industrial Engineering, 129 (2019), 14-30.  doi: 10.1016/j.cie.2019.01.020.

[8]

J. Li and Y. Han, A hybrid multi-objective artificial bee colony algorithm for flexible task scheduling problems in cloud computing system, Cluster Computing, 23 (2020), 2483-2499.  doi: 10.1007/s10586-019-03022-z.

[9]

J. Li, Y. Han, P. Duan, Y. Han, B. Niu, C. Li, Z. Zheng and Y. Liu, Meta-heuristic algorithm for solving vehicle routing problems with time windows and synchronized visit constraints in prefabricated systems, Journal of Cleaner Production, 250 (2020).

[10]

Ministry of National Defense (MND), Military Reform Plan 2014$\sim$2030, Seoul, 2014.

[11]

C. C. Murray and A. G. Chu, The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transportation Research Part C: Emerging Technologies, 54 (2015), 86-109.  doi: 10.1016/j.trc.2015.03.005.

[12]

S. PoikonenX. Wang and B. Golden, The vehicle routing problem with drones: Extended models and connections, Networks, 70 (2017), 34-43.  doi: 10.1002/net.21746.

[13]

D. SacramentoD. Pisinger and S. Ropke, An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones, Transportation Research Part C: Emerging Technologies, 102 (2019), 289-315.  doi: 10.1016/j.trc.2019.02.018.

[14]

D. SchermerM. Moeini and O. Wendt, Algorithms for solving the vehicle routing problem with drones, Asian Conference on Intelligent Information and Database Systems, 10751 (2018), 352-361. 

[15]

D. SchermerM. Moeini and O. Wendt, A matheuristic for the vehicle routing problem with drones and its variants, Transportation Research Part C: Emerging Technologies, 106 (2019), 166-204.  doi: 10.1016/j.trc.2019.06.016.

[16]

S. A. V$ \rm\acute{a} $squez, G. Angulo and M. A. Klapp, An exact solution method for the TSP with drone based on decomposition, Comput. Oper. Res., 127 (2021), 105127. doi: 10.1016/j.cor.2020.105127.

[17]

K. WangB. YuanM. Zhao and Y. Lu, Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach, Journal of the Operational Research Society, 71 (2020), 1657-1674.  doi: 10.1080/01605682.2019.1621671.

[18]

X. WangS. Poikonen and B. Golden, The vehicle routing problem with drones: Several worst-case results, Optimization Letters, 11 (2017), 679-697.  doi: 10.1007/s11590-016-1035-3.

[19]

Z. Wang and J. B. Sheu, Vehicle routing problem with drones, Transportation Research Part B: Methodological, 122 (2019), 350-364.  doi: 10.1016/j.trb.2019.03.005.

[20]

E. Yakici, Solving location and routing problem for UAVs, Computers & Industrial Engineering, 102 (2016), 294-301.  doi: 10.1016/j.cie.2016.10.029.

[21]

E. E. Yurek and H. C. Ozmutlu, A decomposition-based iterative optimization algorithm for traveling salesman problem with drone, Transportation Research Part C: Emerging Technologies, 91 (2018), 249-262.  doi: 10.1016/j.trc.2018.04.009.

show all references

References:
[1]

N. AgatzP. Bouman and M. Schmidt, Optimization approaches for the traveling salesman problem with drone, Transportation Science, 52 (2018), 965-981. 

[2]

M. Dell'AmicoR. Montemanni and S. Novellani, Matheuristic algorithms for the parallel drone scheduling traveling salesman problem, Annals of Operations Research, 289 (2020), 211-226.  doi: 10.1007/s10479-020-03562-3.

[3]

K. DorlingJ. HeinrichsG. G. Messier and S. Magierowski, Vehicle routing problems for drone delivery, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47 (2017), 70-85.  doi: 10.1109/TSMC.2016.2582745.

[4]

Q. M. HaY. DevilleQ. D. Pham and M. H. Ha, On the min-cost traveling salesman problem with drone, Transportation Research Part C: Emerging Technologies, 86 (2018), 597-621.  doi: 10.1016/j.trc.2017.11.015.

[5]

G. Kim, What happened to the five major game-changer?, E-daily, (2019). www.edaily.co.kr.

[6]

J. Kim, N. Ahn, S. Kim, M. Kim and N. Cho, A study on the construction method of surveillance system using drone in transport command, Korea Military Academy Technical report, 18 (2018).

[7]

P. KitjacharoenchaiM. VentrescaM. Moshref-JavadiS. LeeJ. M. Tanchoco and P. A. Brunese, Multiple traveling salesman problem with drones: Mathematical model and heuristic approach, Computers & Industrial Engineering, 129 (2019), 14-30.  doi: 10.1016/j.cie.2019.01.020.

[8]

J. Li and Y. Han, A hybrid multi-objective artificial bee colony algorithm for flexible task scheduling problems in cloud computing system, Cluster Computing, 23 (2020), 2483-2499.  doi: 10.1007/s10586-019-03022-z.

[9]

J. Li, Y. Han, P. Duan, Y. Han, B. Niu, C. Li, Z. Zheng and Y. Liu, Meta-heuristic algorithm for solving vehicle routing problems with time windows and synchronized visit constraints in prefabricated systems, Journal of Cleaner Production, 250 (2020).

[10]

Ministry of National Defense (MND), Military Reform Plan 2014$\sim$2030, Seoul, 2014.

[11]

C. C. Murray and A. G. Chu, The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transportation Research Part C: Emerging Technologies, 54 (2015), 86-109.  doi: 10.1016/j.trc.2015.03.005.

[12]

S. PoikonenX. Wang and B. Golden, The vehicle routing problem with drones: Extended models and connections, Networks, 70 (2017), 34-43.  doi: 10.1002/net.21746.

[13]

D. SacramentoD. Pisinger and S. Ropke, An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones, Transportation Research Part C: Emerging Technologies, 102 (2019), 289-315.  doi: 10.1016/j.trc.2019.02.018.

[14]

D. SchermerM. Moeini and O. Wendt, Algorithms for solving the vehicle routing problem with drones, Asian Conference on Intelligent Information and Database Systems, 10751 (2018), 352-361. 

[15]

D. SchermerM. Moeini and O. Wendt, A matheuristic for the vehicle routing problem with drones and its variants, Transportation Research Part C: Emerging Technologies, 106 (2019), 166-204.  doi: 10.1016/j.trc.2019.06.016.

[16]

S. A. V$ \rm\acute{a} $squez, G. Angulo and M. A. Klapp, An exact solution method for the TSP with drone based on decomposition, Comput. Oper. Res., 127 (2021), 105127. doi: 10.1016/j.cor.2020.105127.

[17]

K. WangB. YuanM. Zhao and Y. Lu, Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach, Journal of the Operational Research Society, 71 (2020), 1657-1674.  doi: 10.1080/01605682.2019.1621671.

[18]

X. WangS. Poikonen and B. Golden, The vehicle routing problem with drones: Several worst-case results, Optimization Letters, 11 (2017), 679-697.  doi: 10.1007/s11590-016-1035-3.

[19]

Z. Wang and J. B. Sheu, Vehicle routing problem with drones, Transportation Research Part B: Methodological, 122 (2019), 350-364.  doi: 10.1016/j.trb.2019.03.005.

[20]

E. Yakici, Solving location and routing problem for UAVs, Computers & Industrial Engineering, 102 (2016), 294-301.  doi: 10.1016/j.cie.2016.10.029.

[21]

E. E. Yurek and H. C. Ozmutlu, A decomposition-based iterative optimization algorithm for traveling salesman problem with drone, Transportation Research Part C: Emerging Technologies, 91 (2018), 249-262.  doi: 10.1016/j.trc.2018.04.009.

Figure 1.  20 years old male population in ROK by year (unit: 1000)
Figure 2.  Travel routes when four surveillance targets and one base station are given with two drones
Figure 3.  Example of the graph modification procedure
Figure 4.  The procedure of the optimal algorithm for the mVRPD
Figure 5.  Surveillance area which is composed of seven surveillance targets
Table 1.  Performance comparison between drone operating personnel and the algorithm
Drone operating personnel Optimal algorithm Comparison
Route for drone 1 0$ \rightarrow $1$ \rightarrow $2$ \rightarrow $7$ \rightarrow $0 0$ \rightarrow $2$ \rightarrow $3$ \rightarrow $5$ \rightarrow $6$ \rightarrow $0 -
Route for drone 2 0$ \rightarrow $3$ \rightarrow $4$ \rightarrow $5$ \rightarrow $6$ \rightarrow $0 0$ \rightarrow $4$ \rightarrow $7$ \rightarrow $1$ \rightarrow $0 -
Total distance 20.4 19.8 3$ \% $ $ \downarrow $
$ z_{max} - z_{min} $ 3.1 0.6 81$ \% $ $ \downarrow $
Drone operating personnel Optimal algorithm Comparison
Route for drone 1 0$ \rightarrow $1$ \rightarrow $2$ \rightarrow $7$ \rightarrow $0 0$ \rightarrow $2$ \rightarrow $3$ \rightarrow $5$ \rightarrow $6$ \rightarrow $0 -
Route for drone 2 0$ \rightarrow $3$ \rightarrow $4$ \rightarrow $5$ \rightarrow $6$ \rightarrow $0 0$ \rightarrow $4$ \rightarrow $7$ \rightarrow $1$ \rightarrow $0 -
Total distance 20.4 19.8 3$ \% $ $ \downarrow $
$ z_{max} - z_{min} $ 3.1 0.6 81$ \% $ $ \downarrow $
Table 2.  Computational results when the number of drones is two
Optimal algorithm Heuristic
$ |V| $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $
4 105.92 96.11 9.82 202.03 0.16 186.47 73.76 112.71 260.23 0.27
5 221.53 205.37 16.16 426.89 0.39 292.08 98.51 193.57 390.59 0.36
6 149.85 149.61 0.24 299.45 4.22 177.55 55.46 122.09 233.01 0.41
7 216.99 216.84 0.15 433.83 41.06 294.30 190.87 103.44 485.17 0.51
8 250.07 250.07 0.00 500.13 234.65 367.26 98.00 269.26 465.26 0.62
9 200.39 200.39 0.00 400.79 78.60 524.20 72.72 451.49 596.92 0.75
10 287.46 287.46 0.00 574.93 8.82 321.32 266.22 55.10 587.54 0.89
Optimal algorithm Heuristic
$ |V| $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $
4 105.92 96.11 9.82 202.03 0.16 186.47 73.76 112.71 260.23 0.27
5 221.53 205.37 16.16 426.89 0.39 292.08 98.51 193.57 390.59 0.36
6 149.85 149.61 0.24 299.45 4.22 177.55 55.46 122.09 233.01 0.41
7 216.99 216.84 0.15 433.83 41.06 294.30 190.87 103.44 485.17 0.51
8 250.07 250.07 0.00 500.13 234.65 367.26 98.00 269.26 465.26 0.62
9 200.39 200.39 0.00 400.79 78.60 524.20 72.72 451.49 596.92 0.75
10 287.46 287.46 0.00 574.93 8.82 321.32 266.22 55.10 587.54 0.89
Table 3.  Computational results when the number of drones is three
Optimal algorithm Heuristic
$ |V| $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $
4 80.52 63.81 16.71 212.45 0.16 80.56 37.58 42.99 181.95 0.33
5 110.15 81.65 28.49 277.04 0.27 160.84 18.87 141.97 264.95 0.43
6 119.65 116.00 3.65 355.18 1.44 178.16 46.69 131.47 351.18 0.53
7 133.07 128.67 4.40 385.43 9.35 257.85 91.93 165.91 459.31 0.61
8 157.83 157.10 0.72 472.54 599.82 325.39 48.37 277.01 461.24 0.75
9 Fail to obtain solution within 10 minutes 236.44 159.86 76.58 573.02 1.33
10 Fail to obtain solution within 10 minutes 218.13 134.78 83.35 504.72 1.50
Optimal algorithm Heuristic
$ |V| $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $
4 80.52 63.81 16.71 212.45 0.16 80.56 37.58 42.99 181.95 0.33
5 110.15 81.65 28.49 277.04 0.27 160.84 18.87 141.97 264.95 0.43
6 119.65 116.00 3.65 355.18 1.44 178.16 46.69 131.47 351.18 0.53
7 133.07 128.67 4.40 385.43 9.35 257.85 91.93 165.91 459.31 0.61
8 157.83 157.10 0.72 472.54 599.82 325.39 48.37 277.01 461.24 0.75
9 Fail to obtain solution within 10 minutes 236.44 159.86 76.58 573.02 1.33
10 Fail to obtain solution within 10 minutes 218.13 134.78 83.35 504.72 1.50
Table 4.  Computational results when the number of drones is four
Optimal algorithm Heuristic
$ |V| $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $
5 103.71 34.99 68.73 263.60 0.09 103.71 34.99 68.73 263.60 0.22
6 83.45 66.03 17.42 308.09 0.19 99.44 25.06 74.38 291.21 0.48
7 90.83 68.00 22.83 309.91 0.61 86.70 44.72 41.98 272.22 0.59
8 97.02 93.38 3.63 381.29 2.72 190.32 51.23 139.10 484.29 0.68
9 Fail to obtain solution within 10 minutes 229.64 95.52 134.12 676.03 1.35
10 Fail to obtain solution within 10 minutes 243.52 59.23 184.29 635.55 1.55
Optimal algorithm Heuristic
$ |V| $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $ $ Max. $ $ Min. $ $ Diff. $ $ Total $ $ Time $
5 103.71 34.99 68.73 263.60 0.09 103.71 34.99 68.73 263.60 0.22
6 83.45 66.03 17.42 308.09 0.19 99.44 25.06 74.38 291.21 0.48
7 90.83 68.00 22.83 309.91 0.61 86.70 44.72 41.98 272.22 0.59
8 97.02 93.38 3.63 381.29 2.72 190.32 51.23 139.10 484.29 0.68
9 Fail to obtain solution within 10 minutes 229.64 95.52 134.12 676.03 1.35
10 Fail to obtain solution within 10 minutes 243.52 59.23 184.29 635.55 1.55
[1]

Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control and Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026

[2]

Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021225

[3]

Nguyen Thi Toan. Generalized Clarke epiderivatives of the extremum multifunction to a multi-objective parametric discrete optimal control problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021088

[4]

Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1949-1977. doi: 10.3934/jimo.2021051

[5]

Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240

[6]

Henri Bonnel, Ngoc Sang Pham. Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions. Journal of Industrial and Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789

[7]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

[8]

Bariş Keçeci, Fulya Altıparmak, İmdat Kara. A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012

[9]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

[10]

Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial and Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435

[11]

Min Zhang, Guowen Xiong, Shanshan Bao, Chao Meng. A time-division distribution strategy for the two-echelon vehicle routing problem with demand blowout. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021094

[12]

Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021197

[13]

Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055

[14]

Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial and Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130

[15]

Zhongqiang Wu, Zongkui Xie. A multi-objective lion swarm optimization based on multi-agent. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022001

[16]

Poonam Savsani, Mohamed A. Tawhid. Discrete heat transfer search for solving travelling salesman problem. Mathematical Foundations of Computing, 2018, 1 (3) : 265-280. doi: 10.3934/mfc.2018012

[17]

Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200

[18]

Jian Xiong, Zhongbao Zhou, Ke Tian, Tianjun Liao, Jianmai Shi. A multi-objective approach for weapon selection and planning problems in dynamic environments. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1189-1211. doi: 10.3934/jimo.2016068

[19]

Dušan M. Stipanović, Claire J. Tomlin, George Leitmann. A note on monotone approximations of minimum and maximum functions and multi-objective problems. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 487-493. doi: 10.3934/naco.2011.1.487

[20]

Hamed Fazlollahtabar, Mohammad Saidi-Mehrabad. Optimizing multi-objective decision making having qualitative evaluation. Journal of Industrial and Management Optimization, 2015, 11 (3) : 747-762. doi: 10.3934/jimo.2015.11.747

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]