• 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
    Quadratic surface support vector machine with L1 norm regularization
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  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]

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

[2]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066

[3]

Melis Alpaslan Takan, Refail Kasimbeyli. Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2073-2095. doi: 10.3934/jimo.2020059

[4]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[5]

Chonghu Guan, Xun Li, Rui Zhou, Wenxin Zhou. Free boundary problem for an optimal investment problem with a borrowing constraint. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021049

[6]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[7]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[8]

Giulio Ciraolo, Antonio Greco. An overdetermined problem associated to the Finsler Laplacian. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1025-1038. doi: 10.3934/cpaa.2021004

[9]

Yang Zhang. A free boundary problem of the cancer invasion. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021092

[10]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463

[11]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2739-2776. doi: 10.3934/dcds.2020384

[12]

Sergei Avdonin, Julian Edward. An inverse problem for quantum trees with observations at interior vertices. Networks & Heterogeneous Media, 2021, 16 (2) : 317-339. doi: 10.3934/nhm.2021008

[13]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[14]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

[15]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205

[16]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453

[17]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031

[18]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2907-2946. doi: 10.3934/dcds.2020391

[19]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, 2021, 15 (3) : 445-474. doi: 10.3934/ipi.2020075

[20]

Jianli Xiang, Guozheng Yan. The uniqueness of the inverse elastic wave scattering problem based on the mixed reciprocity relation. Inverse Problems & Imaging, 2021, 15 (3) : 539-554. doi: 10.3934/ipi.2021004

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]