• Previous Article
    A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project
  • JIMO Home
  • This Issue
  • Next Article
    Coordination strategy for a dual-channel electricity supply chain with sustainability
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 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 & Management Optimization, 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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

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

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

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

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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 & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026

[2]

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

[3]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021051

[4]

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

[5]

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 & Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789

[6]

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 & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

[7]

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 & Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012

[8]

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

[9]

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 & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435

[10]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021094

[11]

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

[12]

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 & Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200

[13]

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 & Management Optimization, 2017, 13 (3) : 1189-1211. doi: 10.3934/jimo.2016068

[14]

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 & Optimization, 2011, 1 (3) : 487-493. doi: 10.3934/naco.2011.1.487

[15]

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

[16]

Yuan-mei Xia, Xin-min Yang, Ke-quan Zhao. A combined scalarization method for multi-objective optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2669-2683. doi: 10.3934/jimo.2020088

[17]

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

[18]

Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095

[19]

Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002

[20]

Alireza Eydi, Rozhin Saedi. A multi-objective decision-making model for supplier selection considering transport discounts and supplier capacity constraints. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020134

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]