{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T03:04:23Z","timestamp":1783393463287,"version":"3.54.6"},"reference-count":43,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"French National Research Agency","award":["16-IDEX-0001"],"award-info":[{"award-number":["16-IDEX-0001"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Evolutionary algorithms have been widely studied in the literature to find sub-optimal solutions to complex problems as the Traveling Salesman Problem (TSP). In such a problem, the target positions are usually static and punctually defined. The objective is to minimize a cost function as the minimal distance, time or energy. However, in some applications, as the one addressed in this paper\u2014namely the data collection of buried sensor nodes by means of an Unmanned Aerial Vehicle\u2014 the targets are areas with varying sizes: they are defined with respect to the radio communication range of each node, ranging from a few meters to several hundred meters according to various parameters (e.g., soil moisture, burial depth, transmit power). The Unmanned Aerial Vehicle has to enter successively in these dynamic areas to collect the data, without the need to pass at the vertical of each node. Some areas can obviously intersect. That leads to solve the Close Enough TSP. To determine a sub-optimal trajectory for the Unmanned Aerial Vehicle, this paper presents an original and efficient strategy based on an evolutionary algorithm completed with geometrical heuristics. The performances of the algorithm are highlighted through scenarios with respectively 15 and 50 target locations. The results are analyzed with respect to the total route length. Finally, conclusions and future research directions are discussed.<\/jats:p>","DOI":"10.3390\/a16010044","type":"journal-article","created":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T01:57:48Z","timestamp":1673315868000},"page":"44","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Evolutionary Algorithm with Geometrical Heuristics for Solving the Close Enough Traveling Salesman Problem: Application to the Trajectory Planning of an Unmanned Aerial Vehicle"],"prefix":"10.3390","volume":"16","author":[{"given":"Christophe","family":"Cariou","sequence":"first","affiliation":[{"name":"INRAE, UR TSCF, University Clermont Auvergne, 9 Av. Blaise Pascal CS 20085, F-63178 Aubi\u00e8re, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laure","family":"Moiroux-Arvis","sequence":"additional","affiliation":[{"name":"INRAE, UR TSCF, University Clermont Auvergne, 9 Av. Blaise Pascal CS 20085, F-63178 Aubi\u00e8re, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fran\u00e7ois","family":"Pinet","sequence":"additional","affiliation":[{"name":"INRAE, UR TSCF, University Clermont Auvergne, 9 Av. Blaise Pascal CS 20085, F-63178 Aubi\u00e8re, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7011-4535","authenticated-orcid":false,"given":"Jean-Pierre","family":"Chanet","sequence":"additional","affiliation":[{"name":"INRAE, UR TSCF, University Clermont Auvergne, 9 Av. Blaise Pascal CS 20085, F-63178 Aubi\u00e8re, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Grlj, C.G., Krznar, N., and Pranjic, M. (2022). A Decade of UAV Docking Stations: A Brief Overview of Mobile and Fixed Landing Platforms. Drones, 6.","DOI":"10.3390\/drones6010017"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Aslan, M.F., Durdu, A., Sabanci, K., Ropelewska, E., and Gultekin, S.S. (2022). A Comprehensive Survey of the Recent Studies with UAV for Precision Agriculture in Open Fields and Greenhouses. Appl. Sci., 12.","DOI":"10.3390\/app12031047"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Srivastava, S.K., Seng, K.P., Ang, L.M., Pachas, A.N.A., and Lewis, T. (2022). Drone-Based Environmental Monitoring and Image Processing Approaches for Resource Estimates of Private Native Forest. Sensors, 22.","DOI":"10.3390\/s22207872"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Nguyen, M.T., Nguyen, C.V., Do, H.T., Hua, H.T., Tran, T.A., Nguyen, A.D., Ala, G., and Viola, F. (2021). UAV-Assisted Data Collection in Wireless Sensor Networks: A Comprehensive Survey. Electronics, 21.","DOI":"10.3390\/electronics10212603"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1660003","DOI":"10.1142\/S0218213016600034","article-title":"Fine-tuning of UAV control rules for spraying pesticides on crop fields: An approach for dynamic environments","volume":"25","author":"Pessin","year":"2016","journal-title":"Int. J. Artif. Intell. Tools"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/MCOM.2014.6979956","article-title":"Exploiting the use of unmanned aerial vehicles to provide resilience in wireless sensor networks","volume":"52","author":"Ueyama","year":"2014","journal-title":"IEEE Commun. Mag."},{"key":"ref_7","first-page":"879","article-title":"A discrete tree-seed algorithm for solving symmetric traveling salesman problem","volume":"23","author":"Cinar","year":"2020","journal-title":"Eng. Sci. Technol. International J."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"106720","DOI":"10.1016\/j.asoc.2020.106720","article-title":"Heterogenous adaptive ant colony optimization with 3-opt local search for the Travelling Salesman Problem","volume":"97","author":"Tuani","year":"2020","journal-title":"Appl. Soft Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., and Neumann, F. (2012, January 16\u201320). Local search and the Traveling Salesman Problem: A feature-based characterization of problem hardness. Proceedings of the International Conference on Learning and Intelligent Optimization, Paris, France.","DOI":"10.1007\/978-3-642-34413-8_9"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"8091","DOI":"10.1007\/s11042-020-10139-6","article-title":"A review on genetic algorithm: Past, present, and future","volume":"80","author":"Katoch","year":"2021","journal-title":"Multimed. Tools Appl."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Qu, F., Yu, W., Xiao, K., Liu, C., and Liu, W. (2022). Trajectory generation and optimization using the mutual learning and adaptive colony algorithm in uneven environments. Appl. Sci., 12.","DOI":"10.3390\/app12094629"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"164820","DOI":"10.1109\/ACCESS.2021.3133493","article-title":"An enhanced swap sequence-based particle swarm optimization algorithm to Solve TSP","volume":"9","author":"Emambocus","year":"2021","journal-title":"IEEE Access"},{"key":"ref_13","unstructured":"Gambardella, L.M., and Dorigo, M. (1996, January 20\u201322). Solving symmetric and asymmetric TSPs by ant colonies. Proceedings of the IEEE International Conference on Evolutionary Computation, Nagoya, Japan."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"313767","DOI":"10.1155\/2014\/313767","article-title":"An adaptive evolutionary algorithm for traveling salesman problem with precedence constraints","volume":"2014","author":"Sung","year":"2014","journal-title":"Sci. World J."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Carwalo, T., Thankappan, J., and Patil, V. (2017, January 7\u20138). Capacitated vehicle routing problem. Proceedings of the 2nd International Conference on Communication Systems, Computing and IT Applications (CSCITA), Tokyo, Japan.","DOI":"10.1109\/CSCITA.2017.8066555"},{"key":"ref_16","unstructured":"Berg, M., Gudmundsson, J., and Katz, M. (2002, January 17\u201321). TSP with neighborhoods of varying size. Proceedings of the 10th Annual European Symposium, Rome, Italy."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Sinha Roy, D., Golden, B., Wang, X., and Wasil, E. (2021). Estimating the tour length for the close enough traveling salesman problem. Algorithms, 14.","DOI":"10.3390\/a14040123"},{"key":"ref_18","first-page":"579","article-title":"The close enough traveling salesman problem with time window","volume":"13","author":"Semami","year":"2019","journal-title":"Int. J. Circuits Syst. Signal Process."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Huang, H., Shi, J., Wang, F., and Zhang, D. (2020). Theoretical and experimental studies on the signal propagation in soil for wireless underground sensor networks. Sensors, 20.","DOI":"10.3390\/s20092580"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"3443","DOI":"10.1109\/COMST.2019.2934365","article-title":"Towards the Internet of Underground Things: A systematic survey","volume":"21","author":"Saeed","year":"2019","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Salam, A., and Raza, U. (2020). Current advances in Internet of Underground Things. Signals in the Soil, Springer Nature Switzerland AG. Chapter 10.","DOI":"10.1007\/978-3-030-50861-6"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Vuran, M.C., Salam, A., Wong, R., and Irmak, S. (2018, January 5\u20138). Internet of underground things: Sensing and communications on the field for precision agriculture. Proceedings of the IEEE 4th World Forum on Internet of Things (WF-IoT), Singapore.","DOI":"10.1109\/WF-IoT.2018.8355096"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Silva, A.R., and Vuran, M.C. (2010, January 13\u201315). (CPS)2: Integration of center pivot systems with wireless underground sensor networks for autonomous precision agriculture. Proceedings of the IEEE\/ACM International Conference on Cyber-Physical Systems, Stockholm, Sweden.","DOI":"10.1145\/1795194.1795206"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/j.adhoc.2006.04.003","article-title":"Wireless underground sensor networks: Research challenges","volume":"4","author":"Akyildiz","year":"2006","journal-title":"Ad Hoc Netw."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Ferreira, C.B.M., Peixoto, V.F., de Brito, J.A.G., de Monteiro, A.F.A., de Assis, L.S., and Henriques, F.R. (2019, January 1\u20132). UnderApp: A system for remote monitoring of landslides based on wireless underground sensor networks. Proceedings of the WTIC, Rio de Janeiro, Brazil.","DOI":"10.5753\/webmedia_estendido.2019.8142"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"106770","DOI":"10.1016\/j.compag.2022.106770","article-title":"Evaluation of LoRa technology in 433-MHz and 868-MHz for underground to aboveground data transmission","volume":"194","author":"Cariou","year":"2022","journal-title":"Comput. Electron. Agric."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0377-2217(85)90151-1","article-title":"A cutting plane procedure for the travelling salesman problem on road networks","volume":"21","author":"Fleischmann","year":"1985","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","unstructured":"Clausen, J. (1999). Branch and Bound Algorithms-Principles and Examples, Department of Computer Science, University of Copenhagen."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0377-2217(92)90138-Y","article-title":"The traveling salesman problem: An overview of exact and approximate algorithms","volume":"59","author":"Laporte","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Sanches, D., Whitley, D., and Tinos, R. (2017, January 15\u201319). Improving an exact solver for the traveling salesman problem using partition crossover. Proceedings of the Genetic and Evolutionary Computation Conference, Berlin, Germany.","DOI":"10.1145\/3071178.3071304"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.cor.2017.04.001","article-title":"Solving large batches of traveling salesman problems with parallel and distributed computing","volume":"85","author":"Ozden","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v023.i02","article-title":"TSP\u2014Infracstructure for the traveling salesperson problem","volume":"23","author":"Hahsler","year":"2007","journal-title":"J. Stat. Softw."},{"key":"ref_33","unstructured":"Helsgaun, K. (2006). An Effective Implementation of K-Opt Moves for the Lin-Kernighan TSP Heuristic. [Ph.D. Thesis, Roskilde University]."},{"key":"ref_34","unstructured":"Helsgaun, K. (2017). An Extension of the Lin-Kernighan-Helsgaun TSP solver for Constrained Traveling Salesman and Vehicle Routing Problems, Roskilde University."},{"key":"ref_35","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_36","doi-asserted-by":"crossref","first-page":"1417","DOI":"10.1016\/j.pnsc.2008.03.028","article-title":"An ant colony optimization method for generalized TSP problem","volume":"18","author":"Yang","year":"2008","journal-title":"Prog. Nat. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-0-387-39934-8_16","article-title":"Close enough traveling salesman problem: A discussion of several heuristics","volume":"36","author":"Gulczynski","year":"2006","journal-title":"Perspect. Oper. Res."},{"key":"ref_38","unstructured":"Dong, J., Yang, N., and Chen, M. (2007). Heuristic approaches for a TSP variant: The automatic meter reading shortest tour problem. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Springer."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Mennell, W., Golden, B., and Wasil, E. (2011, January 9\u201311). A steiner-zone heuristic for solving the close-enough traveling salesman problem. Proceedings of the 12th INFORMS Computing Society Conference, Homeland Defense, Monterey, CA, USA.","DOI":"10.1287\/ics.2011.0004"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1287\/ijoc.2016.0711","article-title":"A Branch-and-Bound algorithm for the Close-Enough Traveling Salesman Problem","volume":"28","author":"Coutinho","year":"2016","journal-title":"Informs J. Comput."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Elbassioni, K., Fishkin, A., Mustafa, N., and Sitters, R. (2005, January 11\u201315). Approximation Algorithms for Euclidian Group TSP. Proceedings of the International Colloquium on Automata, Languages, and Programming, Lisbon, Portugal.","DOI":"10.1007\/11523468_90"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.cor.2016.09.003","article-title":"A novel discretization scheme for the Close Enough Traveling Salesman Problem","volume":"78","author":"Carrabs","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1109\/TKDE.2007.1062","article-title":"On the optimal robot routing problem in wireless sensor networks","volume":"19","author":"Yuan","year":"2007","journal-title":"IEEE Trans. Knowl. Data Eng."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/44\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:04:54Z","timestamp":1760119494000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":43,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["a16010044"],"URL":"https:\/\/doi.org\/10.3390\/a16010044","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,9]]}}}