Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors
This paper addresses the team orienteering problem applied to unmanned aerial vehicles (UAVs), considering obstacle avoidance and environmental factors such as wind conditions and payload weight. The objective is to optimize UAV routes to maximize collected rewards while adhering to operational cons...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/6/309 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839655080441151488 |
|---|---|
| author | Alfons Freixes Javier Panadero Angel A. Juan Carles Serrat |
| author_facet | Alfons Freixes Javier Panadero Angel A. Juan Carles Serrat |
| author_sort | Alfons Freixes |
| collection | DOAJ |
| description | This paper addresses the team orienteering problem applied to unmanned aerial vehicles (UAVs), considering obstacle avoidance and environmental factors such as wind conditions and payload weight. The objective is to optimize UAV routes to maximize collected rewards while adhering to operational constraints. To achieve this, we employ a simheuristic algorithm for the overall route optimization, while integrating the A* algorithm to determine feasible paths between nodes that avoid obstacles in a 2D grid-based environment. Then, a feedforward neural network estimates travel time based on UAV speed, wind conditions, trajectory distance, and payload weight. This estimation is incorporated into the optimization process to improve route planning accuracy. Numerical experiments evaluate the impact of various parameters, including obstacle placement, UAV speed, wind conditions, and payload weight. These experiments include maps with 30 to 100 points of interest and varying obstacle densities and show that our hybrid method improves solution quality by up to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>15</mn><mo>%</mo></mrow></semantics></math></inline-formula> in total profit compared to a baseline approach. Furthermore, computation times remain within 5–10% of the baseline, showing that the added predictive layer maintains computational efficiency. |
| format | Article |
| id | doaj-art-92d629d2bc7d4a54bf757a0abfafba8d |
| institution | Matheson Library |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-92d629d2bc7d4a54bf757a0abfafba8d2025-06-25T13:21:17ZengMDPI AGAlgorithms1999-48932025-05-0118630910.3390/a18060309Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental FactorsAlfons Freixes0Javier Panadero1Angel A. Juan2Carles Serrat3Unit of Business Analytics, EUNCET Business School, 08225 Terrassa, SpainDepartment of Computer Architecture and Operating Systems, Universitat Autònoma de Barcelona, 08193 Bellaterra, SpainCIGIP, Universitat Politècnica de València, 03801 Alcoy, SpainDepartment of Mathematics, Universitat Politècnica de Catalunya, 08034 Barcelona, SpainThis paper addresses the team orienteering problem applied to unmanned aerial vehicles (UAVs), considering obstacle avoidance and environmental factors such as wind conditions and payload weight. The objective is to optimize UAV routes to maximize collected rewards while adhering to operational constraints. To achieve this, we employ a simheuristic algorithm for the overall route optimization, while integrating the A* algorithm to determine feasible paths between nodes that avoid obstacles in a 2D grid-based environment. Then, a feedforward neural network estimates travel time based on UAV speed, wind conditions, trajectory distance, and payload weight. This estimation is incorporated into the optimization process to improve route planning accuracy. Numerical experiments evaluate the impact of various parameters, including obstacle placement, UAV speed, wind conditions, and payload weight. These experiments include maps with 30 to 100 points of interest and varying obstacle densities and show that our hybrid method improves solution quality by up to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>15</mn><mo>%</mo></mrow></semantics></math></inline-formula> in total profit compared to a baseline approach. Furthermore, computation times remain within 5–10% of the baseline, showing that the added predictive layer maintains computational efficiency.https://www.mdpi.com/1999-4893/18/6/309unmanned aerial vehiclesA* algorithmteam orienteering problemartificial intelligence |
| spellingShingle | Alfons Freixes Javier Panadero Angel A. Juan Carles Serrat Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors Algorithms unmanned aerial vehicles A* algorithm team orienteering problem artificial intelligence |
| title | Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors |
| title_full | Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors |
| title_fullStr | Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors |
| title_full_unstemmed | Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors |
| title_short | Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors |
| title_sort | combining the a algorithm with neural networks to solve the team orienteering problem with obstacles and environmental factors |
| topic | unmanned aerial vehicles A* algorithm team orienteering problem artificial intelligence |
| url | https://www.mdpi.com/1999-4893/18/6/309 |
| work_keys_str_mv | AT alfonsfreixes combiningtheaalgorithmwithneuralnetworkstosolvetheteamorienteeringproblemwithobstaclesandenvironmentalfactors AT javierpanadero combiningtheaalgorithmwithneuralnetworkstosolvetheteamorienteeringproblemwithobstaclesandenvironmentalfactors AT angelajuan combiningtheaalgorithmwithneuralnetworkstosolvetheteamorienteeringproblemwithobstaclesandenvironmentalfactors AT carlesserrat combiningtheaalgorithmwithneuralnetworkstosolvetheteamorienteeringproblemwithobstaclesandenvironmentalfactors |