{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T00:54:12Z","timestamp":1780448052792,"version":"3.54.1"},"reference-count":38,"publisher":"MDPI AG","issue":"17","license":[{"start":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T00:00:00Z","timestamp":1598227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100007085","name":"National University of Defense Technology","doi-asserted-by":"publisher","award":["ZK18-03-18"],"award-info":[{"award-number":["ZK18-03-18"]}],"id":[{"id":"10.13039\/501100007085","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007085","name":"National University of Defense Technology","doi-asserted-by":"publisher","award":["1204053119078KY"],"award-info":[{"award-number":["1204053119078KY"]}],"id":[{"id":"10.13039\/501100007085","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>The unmanned aerial vehicle (UAV) has drawn increasing attention in recent years, especially in executing tasks such as natural disaster rescue and detection, and battlefield cooperative operations. Task assignment and path planning for multiple UAVs in the above scenarios are essential for successful mission execution. But, effectively balancing tasks to better excavate the potential of UAVs remains a challenge, as well as efficiently generating feasible solutions from the current one in constrained explosive solution spaces with the increase in the scale of optimization problems. This paper proposes an efficient approach for task assignment and path planning with the objective of balancing the tasks among UAVs and achieving satisfactory temporal resolutions. To be specific, we add virtual nodes according to the number of UAVs to the original model of the vehicle routing problem (VRP), thus make it easier to form a solution suitable for heuristic algorithms. Besides, the concept of the universal distance matrix is proposed to transform the temporal constraints to spatial constraints and simplify the programming model. Then, a Swap-and-Judge Simulated Annealing (SJSA) algorithm is therefore proposed to improve the efficiency of generating feasible neighboring solutions. Extensive experimental and comparative studies on different scenarios demonstrate the efficiency of the proposed algorithm compared with the exact algorithm and meta-heuristic algorithms. The results also inspire us about the characteristics of a population-based algorithm in solving combinatorial discrete optimization problems.<\/jats:p>","DOI":"10.3390\/s20174769","type":"journal-article","created":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T10:37:32Z","timestamp":1598265452000},"page":"4769","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":73,"title":["A Novel Simulated Annealing Based Strategy for Balanced UAV Task Assignment and Path Planning"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8717-2301","authenticated-orcid":false,"given":"Lisu","family":"Huo","sequence":"first","affiliation":[{"name":"College of Systems Engineering, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianghan","family":"Zhu","sequence":"additional","affiliation":[{"name":"College of Systems Engineering, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1552-9620","authenticated-orcid":false,"given":"Guohua","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhimeng","family":"Li","sequence":"additional","affiliation":[{"name":"College of Systems Engineering, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,24]]},"reference":[{"key":"ref_1","first-page":"20","article-title":"Drone duties: The dull, the dirty, and the dangerous","volume":"24","author":"Lundquist","year":"2003","journal-title":"Nav. Forces"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"6898","DOI":"10.1109\/JIOT.2020.2971645","article-title":"Multi-UAV Enabled Load-Balance Mobile Edge Computing for IoT Networks","volume":"7","author":"Yang","year":"2020","journal-title":"IEEE Internet Things J."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1109\/MWC.001.1900351","article-title":"Artificial Intelligence Aided Joint Bit Rate Selection and Radio Resource Allocation for Adaptive Video Streaming over F-RANs","volume":"27","author":"Chen","year":"2020","journal-title":"IEEE Wirel. Commun."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1109\/TSMC.2016.2582745","article-title":"Vehicle Routing Problems for Drone Delivery","volume":"47","author":"Dorling","year":"2017","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/j.neucom.2017.05.059","article-title":"Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm","volume":"266","author":"Yongbo","year":"2017","journal-title":"Neurocomputing"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The Truck Dispatching Problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"ref_7","unstructured":"Shima, T., Rasmussen, S.J., and Sparks, A.G. (2005, January 8\u201310). UAV cooperative multiple task assignments using genetic algorithms. Proceedings of the 2005 American Control Conference, Portland, OR, USA."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Tian, J., Shen, L., and Zheng, Y. (2006, January 27\u201329). Genetic algorithm based approach for Multi-UAV cooperative reconnaissance mission planning problem. Proceedings of the International Syposium on Methodologies for Intelligent Systems, Bari, Italy.","DOI":"10.1007\/11875604_13"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Junwei, Z., and Jianjun, Z. (2014, January 26\u201327). Study on Multi-UAV Task Clustering and Task Planning in Cooperative Reconnaissance. Proceedings of the 2014 Sixth International Conference on Intelligent Human-Machine Systems and Cybernetics, Hangzhou, China.","DOI":"10.1109\/IHMSC.2014.196"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1109\/JSEE.2015.00109","article-title":"Hierarchical method of task assignment for multiple cooperating UAV teams","volume":"26","author":"Hu","year":"2015","journal-title":"J. Syst. Eng. Electron."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Chen, H., Nan, Y., and Yang, Y. (2019). Multi-UAV Reconnaissance Task Assignment for Heterogeneous Targets Based on Modified Symbiotic Organisms Search Algorithm. Sensors, 19.","DOI":"10.3390\/s19030734"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.ast.2019.01.061","article-title":"An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles","volume":"86","author":"Yao","year":"2019","journal-title":"Aerosp. Sci. Technol."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.adhoc.2018.11.008","article-title":"Use of a quantum genetic algorithm for coalition formation in large-scale UAV networks","volume":"87","author":"Mousavi","year":"2019","journal-title":"Ad Hoc Networks"},{"key":"ref_14","unstructured":"Nikolos, I.K., and Brintaki, A.N. (2005, January 27\u201329). Coordinated UAV Path Planning Using Differential Evolution. Proceedings of the 2005 IEEE International Symposium on, Mediterrean Conference on Control and Automation Intelligent Control, Limassol, Cyprus."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1451","DOI":"10.1109\/TSMC.2013.2248146","article-title":"Route Planning for Unmanned Aerial Vehicle (UAV) on the Sea Using Hybrid Differential Evolution and Quantum-Behaved Particle Swarm Optimization","volume":"43","author":"Fu","year":"2013","journal-title":"IEEE Trans. Syst. Man Cybern. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"6444","DOI":"10.1109\/TGRS.2016.2585184","article-title":"Path Planning for GEO-UAV Bistatic SAR Using Constrained Adaptive Multiobjective Differential Evolution","volume":"54","author":"Sun","year":"2016","journal-title":"IEEE Trans. Geosci. Remote Sens."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"169599","DOI":"10.1109\/ACCESS.2019.2954408","article-title":"Trajectory Following and Improved Differential Evolution Solution for Rapid Forming of UAV Formation","volume":"7","author":"Bian","year":"2019","journal-title":"IEEE Access"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1109\/TII.2012.2198665","article-title":"Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path Planning","volume":"9","author":"Roberge","year":"2013","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4883","DOI":"10.1007\/s00500-016-2376-7","article-title":"Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms","volume":"21","author":"Ramirezatencia","year":"2017","journal-title":"Soft Comput."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Meng, H., and Xin, G. (2010, January 4\u20137). UAV route planning based on the genetic simulated annealing algorithm. Proceedings of the 2010 IEEE International Conference on Mechatronics and Automation, Xi\u2019an, China.","DOI":"10.1109\/ICMA.2010.5589035"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.ifacol.2015.08.109","article-title":"A modified simulated annealing algorithm for SUAVs path planning","volume":"48","author":"Behnck","year":"2015","journal-title":"IFAC-PapersOnLine"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Yue, X., and Zhang, W. (2018, January 25\u201327). UAV Path Planning Based on K-Means Algorithm and Simulated Annealing Algorithm. Proceedings of the 2018 37th Chinese Control Conference, Wuhan, China.","DOI":"10.23919\/ChiCC.2018.8483993"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Turker, T., Sahingoz, O.K., and Yilmaz, G. (2015, January 9\u201312). 2D path planning for UAVs in radar threatening environment using simulated annealing algorithm. Proceedings of the 2015 International Conference on Unmanned Aircraft Systems (ICUAS), Denver, CO, USA.","DOI":"10.1109\/ICUAS.2015.7152275"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Turker, T., Yilmaz, G., and Sahingoz, O.K. (2016, January 7\u201310). GPU-Accelerated Flight Route Planning for Multi-UAV Systems Using Simulated Annealing. Proceedings of the International Conference on Artificial Intelligence: Methodology, Systems, and Applications, Varna, Bulgaria.","DOI":"10.1007\/978-3-319-44748-3_27"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","article-title":"The Euclidean traveling salesman problem is NP-complete","volume":"4","author":"Papadimitriou","year":"1977","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The multiple traveling salesman problem: An overview of formulations and solution procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega Int. J. Manag. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1023\/A:1008202821328","article-title":"Differential evolution\u2013a simple and efficient heuristic for global optimization over continuous spaces","volume":"11","author":"Storn","year":"1997","journal-title":"J. Glob. Optim."},{"key":"ref_28","unstructured":"Price, K., Storn, R.M., and Lampinen, J.A. (2006). Differential Evolution: A Practical Approach to Global Optimization, Springer Science & Business Media."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1109\/TSMCB.2011.2167966","article-title":"An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization","volume":"42","author":"Islam","year":"2011","journal-title":"IEEE Trans. Syst. Man Cybern. Part B (Cybern.)"},{"key":"ref_30","unstructured":"Lichtblau, D. (2002, January 14\u201318). Discrete optimization using Mathematica. Proceedings of the World Multi-Conference on Systemics, Cybernetics and Informatics, Orlando, FL, USA."},{"key":"ref_31","unstructured":"Razali, N.M., and Geraghty, J. (2011). Genetic algorithm performance with different selection strategies in solving TSP. Proceedings of the World Congress on Engineering, International Association of Engineers."},{"key":"ref_32","unstructured":"Chudasama, C., Shah, S., and Panchal, M. (2011, January 4\u20136). Comparison of parents selection methods of genetic algorithm for TSP. Proceedings of the International Conference on Computer Communication and Networks CSI-COMNET-2011, Udaipur, India."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1109\/72.265964","article-title":"Convergence analysis of canonical genetic algorithms","volume":"5","author":"Rudolph","year":"1994","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"2179","DOI":"10.1016\/j.spl.2013.05.025","article-title":"The elitist non-homogeneous genetic algorithm: Almost sure convergence","volume":"83","author":"Cruz","year":"2013","journal-title":"Stat. Probab. Lett."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., and Yung, M. (2005). Automata, Languages and Programming: 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11\u201315, 2005, Proceedings, Springer.","DOI":"10.1007\/11523468"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.ipl.2007.06.016","article-title":"Simulated annealing versus metropolis for a TSP instance","volume":"104","author":"Meer","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J. Chem. Phys."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/MRA.2013.2283632","article-title":"Robot Vision: Obstacle-Avoidance Techniques for Unmanned Aerial Vehicles","volume":"20","author":"Carloni","year":"2013","journal-title":"IEEE Robot. Autom. Mag."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/17\/4769\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:05:41Z","timestamp":1760177141000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/17\/4769"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,24]]},"references-count":38,"journal-issue":{"issue":"17","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["s20174769"],"URL":"https:\/\/doi.org\/10.3390\/s20174769","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,24]]}}}