A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Unmanned Aerial Vehicles

Citation: Peyman, M.; Martin, X.A.; Panadero, J.; Juan, A.A. A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Unmanned Aerial Vehicles. Algorithms 2024,17, 200. https://doi.org/ 10.3390/a17050200 Academic Editor: Marc Sevaux Received: 15 April 2024 Revised: 2 May 2024 Accepted: 7 May 2024 Published: 8 May 2024 Copyright: © 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). algorithms Article A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Unmanned Aerial Vehicles Mohammad Peyman 1, Xabier A. Martin 1, Javier Panadero 2and Angel A. Juan 1,* 1Research Center on Production Management and Engineering, Universitat Politècnica de València, Plaza Ferrandiz-Salvador, 03801 Alcoy, Spain; [email protected] (M.P.); [email protected] (X.A.M.) 2Department of Computer Architecture & Operating Systems, Universitat Autònoma de Barcelona, Carrer de les Sitges, 08193 Bellaterra, Spain; javier[email protected] *Correspondence: [email protected] Abstract: In this paper, we introduce a novel sim-learnheuristic method designed to address the team orienteering problem (TOP) with a particular focus on its application in the context of unmanned aerial vehicles (UAVs). Unlike most prior research, which primarily focuses on the deterministic and stochastic versions of the TOP, our approach considers a hybrid scenario, which combines deterministic, stochastic, and dynamic characteristics. The TOP involves visiting a set of customers using a team of vehicles to maximize the total collected reward. However, this hybrid version becomes notably complex due to the presence of uncertain travel times with dynamically changing factors. Some travel times are stochastic, while others are subject to dynamic factors such as weather conditions and traffic congestion. Our novel approach combines a savings-based heuristic algorithm, Monte Carlo simulations, and a multiple regression model. This integration incorporates the stochastic and dynamic nature of travel times, considering various dynamic conditions, and generates high-quality solutions in short computational times for the presented problem. Keywords: team orienteering problem; biased randomization; learnheuristic; simheuristic 1. Introduction The team orienteering problem (TOP) is a classic optimization problem in which a set of routes is constructed for a team of vehicles to traverse, aimed at collecting the highest possible reward from customers within the routes before a defined time limit [ 1 ]. In sectors such as search and rescue, surveillance, and logistics, addressing the TOP is crucial. One example of this could be a search and rescue mission, where a team of unmanned aerial vehicles (UAVs) must navigate through a disaster-stricken area to locate survivors and deliver supplies. While UAVs have emerged as essential assets in such missions due to their capacity to perform hazardous duties and their skill in sensing, monitoring, and navigating, the difficulties they face are difficult to overstate [ 2 ]. These challenges are multifaceted and include unpredictable environmental factors like weather or traffic conditions. Such unpredictability makes reliable behavior prediction impossible, resulting in suboptimal solutions and a reduced mission efficiency. Additionally, the natural limitations of UAVs, such as the limited battery life and cargo capacity, demand precise optimization for mission accomplishment. Despite these challenges, UAVs remain a critical technology for solving complex problems in various domains, emphasizing the importance of the TOP and its applicability to UAVs [ 3 ]. Furthermore, the integration of Internet of Things technologies stands as one of the most promising approaches for enabling UAVs to sense their surroundings and collect data. This integration facilitates UAVs to gather and exchange real-time environmental data, thereby optimizing their routes accordingly [4]. In recent years, the majority of studies focused on either deterministic or stochastic variants of the TOP. In the case of the deterministic TOP, many of the studies in the literature rely significantly on exact methods to solve this problem [ 5 ]. However, when presented with Algorithms 2024,17, 200. https://doi.org/10.3390/a17050200 https://www.mdpi.com/journal/algorithms Algorithms 2024,17, 200 2 of 19 challenges given by large-scale instances, these exact methods show limited effectiveness. On the other hand, in the case of the stochastic TOP, various studies have explored different strategies, such as stochastic programming [ 6 ], robust optimization [ 7 ], and, recently, the utilization of simheuristic approaches [ 8 ]. Furthermore, several versions of the TOP have been developed to address specific real-world scenarios, including heterogeneous vehicle capacities, customer time constraints, and unpredictable travel times and profits. For example, Kirac et al. [9] addressed the TOP with time windows and mandatory visits, Lin and Vincent [10] tackled the TOP with mandatory visits, Gunawan et al. [11] addressed the TOP with variable profits, and Panadero et al. [12] tackled the TOP with stochasticity. Our paper focuses on a hybrid variant of the TOP, which combines deterministic, stochastic, and dynamic characteristics, addressing a gap in the scientific literature. To solve this complex problem, a new sim-learnheuristic approach is introduced, with special applications in UAVs that can be used to aid in disaster rescue. This approach combines a biased-randomized savings-based heuristic, Monte Carlo simulations, and a multiple regression model. The main objective of this novel methodology is to combine the strengths of all three components, allowing for an agile exploration of the search space to produce high-quality solutions for the presented problem. Figure 1depicts this new variant of the TOP, where the travel times display a wide range of features. These features include certain travel times (deterministic), uncertain travel times (stochastic), and travel times that can change over time due to dynamic factors (dynamic), such as varying traffic congestion and weather conditions. This blend of characteristics results in a more precise representation of the complexities evident in real-world situations. Tdet Tdet Tdynamic Tdet Tdynamic (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Tstoch ∼ LogN(μ,σ) Tstoch ∼ LogN(μ,σ) Origin Destination Tstoch ∼ LogN(μ,σ) Tstoch ∼ LogN(μ,σ) Tstoch ∼ LogN(μ,σ) Non-collected nodes Figure 1. Hybrid variant of the TOP considering different kinds of travel times. The main contributions of this research are as follows: (i) we present a hybrid variant of the TOP, which combines deterministic, stochastic, and dynamically changing travel times due to factors such as traffic congestion and weather conditions; and (ii) we propose a novel methodology called the sim-learnheuristic algorithm to solve this rich variant of the TOP, where the integration of three distinct components is crucial for its capability to solve increasingly complex combinatorial optimization problems. Figure 2illustrates the integration of the three components. Initially, the metaheuristic component addresses the deterministic aspects of the problem. However, real-world scenarios often involve uncertainties. To account for this, the simulation component incorporates the stochastic nature of the environment. By combining this with the metaheuristic component, the simheuristic component effectively tackles stochastic problems. Moreover, real-world conditions are dynamic; thus, machine learning algorithms are employed to predict and Algorithms 2024,17, 200 3 of 19 adapt to these changes. Integrating these predictions within the simheuristic framework enables it to address and solve complex dynamic problems effectively. Figure 2. Integration of the sim-learnheuristic’s main three components. The remaining sections of the paper are structured as follows: Section 2presents brief reviews of related articles. Section 3presents the definition of the hybrid TOP, and Section 4 describes the proposed methodology of the sim-learnheuristic algorithm. Section 5carries out a series of computational experiments to illustrate the performance of the proposed algorithm, and Section 6presents the discussion of the obtained results. Finally, Section 7 highlights the main conclusions and future research lines of this work. 2. Related Work In the field of optimization, simheuristics and learnheuristics are increasingly being used to solve complex combinatorial optimization problems under uncertainty. Simheuristic methods combine the advantages of both simulation and heuristics to tackle such problems. On the other hand, learnheuristics employ machine learning algorithms to improve the quality of solutions over time. Gonzalez-Neira et al. [13] proposed a hybrid simheuristic method to solve a complex multicriteria stochastic permutation flow shop problem. This method combines a greedy randomized adaptive search procedure, Monte Carlo simulations, a Pareto archived evolution strategy, and an analytic hierarchy process to handle stochastic processing times and sequence-dependent setup times. It considers quantitative criteria like earliness/tardiness and qualitative criteria like product and customer importance. The experimental results showed the significant impact of processing time distributions and coefficients of variation on decision criteria. Similarly, Caldeira and Gnanavelbabu [14] proposed a simheuristic approach to solve the stochastic flexible job shop scheduling problem. They integrated Monte Carlo simulations into a Jaya algorithm framework to minimize the expected makespan, considering uncertainties in production processes represented by random variables with known probability distributions. The computational results demonstrated its effectiveness across different variability levels using reliability-based methods, showcasing its capability in handling stochasticity in flexible job shop scheduling. Yazdani et al. [15] proposed a novel simheuristic approach to address the waste collection routing problem in the context of construction and demolition waste management. The proposed approach utilized a hybrid genetic algorithm to optimize vehicle route planning from construction projects to recycling facilities. In their research. they conducted a comparative analysis with existing approaches and demonstrated the Algorithms 2024,17, 200 4 of 19 high performance of the proposed simheuristic algorithm. Real case studies from Sydney, Australia, were used for evaluation, contributing significantly to optimizing future waste collection problems and providing recommendations for decision-makers and practitioners. Crawford et al. [16] proposed a Q-learnheuristic framework integrating Q-Learning into metaheuristics to address the exploration–exploitation balance dilemma. This framework, applied to various metaheuristics including the Whale Optimization Algorithm and the Sine-Cosine Algorithm, enhanced the selection of operators like binarization schemes for binary combinatorial problems. This study extended the framework’s applicability, demonstrating statistical improvements in both the exploration–exploitation balance and the solution quality when solving the set covering problem. Gomez et al. [17] introduced a novel approach to tackle the capacitated dispersion problem, which involves selecting elements within a network while considering their bounded service capacities. The introduction of a random Bernoulli component influences node capacities, potentially resulting in nodes with zero capacity based on environmental variables. The proposed learnheuristic approach hybridizes a heuristic algorithm with reinforcement learning, offering a promising method to handle this intricate problem variant effectively. Bullah and van Zyl [18] proposed a novel learnheuristic approach to solve a constrained multi-objective portfolio optimization problem. The authors developed a hybrid approach that combines machine learning and a metaheuristic algorithm to obtain high-quality solutions that satisfy multiple objectives, such as maximizing returns while minimizing risk and adhering to constraints such as transaction costs and diversification requirements. The learnheuristic approach involves training a neural network to predict the quality of solutions obtained by a metaheuristic algorithm and using this prediction to guide the search toward promising regions of the solution space. Focusing on the TOP, several articles have been published in recent years. Notably, Tricoire et al. [19] employed an adaptive algorithm based on the Markov decision process to decide whether to continue the route or take a shortcut given a specific deadline. Mufalli et al. [20] discussed sensor assignment and routing for UAVs to maximize intelligence gathering, considering constraints like a limited battery and sensor weight. They proposed a detailed plan using mathematical models and local search strategies, with column generation for efficiency in larger missions. Likewise, Saeedvand et al. [21] presented a hybrid technique for solving the TOP in rescue operations using humanoid robots, aiming to optimize energy, task completion, and decision-making through a learning algorithm and an evolutionary multi-objective approach. Schmitt-Ulms et al. [22] presented a machine learning approach to solving a stochastic TOP with time windows. The authors used a reinforcement learning algorithm, specifically the Q-learning algorithm, to learn how to make routing decisions for a deliveryman facing stochastic travel times and customer demands. Also, Lee and Ahn [23] presented a data-efficient deep reinforcement learning (DRL) approach to solve a multi-start TOP for UAV mission re-planning. The authors propose a method that learns to adapt to changing conditions by iteratively updating a policy network through experience gained from previous UAV mission planning problems. Xu et al. [24] discussed a novel application of electric vehicles in TOP systems, focusing on charging energy-critical sensors using mobile chargers. Due to charger limitations, visiting all sensors was restricted, and costs were assigned considering charger energy consumption and travel. Different vehicle types and their capabilities were also considered, with sensors possibly visited by multiple vehicles, affecting profit margins. An approximation algorithm was proposed initially and later refined for handling vehicles of the same type. In contrast, Sundar et al. [25] introduced a concurrent multi-threaded branch-and-price algorithm with acceleration techniques for the TOP involving fixed-wing drones. They addressed the kinematic constraints limiting drones’ maneuverability, particularly quick turns and minimum turn radii. While their approach achieved optimal solutions for most cases, its reliance on exact methods hindered real-time solutions, crucial for dynamic systems. Wang et al. [26] focused on the dynamic and stochastic orienteering problem in autonomous transportation systems. They introduced self-adaptive heuristic algorithms to Algorithms 2024,17, 200 5 of 19 optimize task execution for intelligent agents, maximizing rewards and ensuring timely returns to the starting location within a limited time frame. The orienteering problem enables agents to selectively visit spots and optimize routing sequences for reward maximization. The study proposed a hybrid simulated annealing–tabu search algorithm for initial routing plans and three multi-stage optimization strategies for real-time adjustments. Simulation experiments demonstrated the effectiveness of the algorithm, improving the solution quality and ensuring timely arrivals for agents. Elzein and Di Caro [27] proposed a novel multi-stage metaheuristic algorithm to efficiently tackle large orienteering problem instances. The metaheuristic partitions a potentially large set of candidate sites into smaller clusters, where a solver is used to find near-optimal solutions within a bounded time. These solutions are then merged and optimized to provide a final high-quality solution. The metaheuristic significantly improves the computation time without a substantial loss in solution quality, making it suitable for online applications in robotics, logistics, and transportation scenarios with dynamic environments and a large number of candidate points. The results demonstrated the effectiveness and efficiency of the proposed approach over large benchmark instances. Le et al. [28] addressed the dynamic orienteering problem based on a VNS algorithm. The algorithm efficiently adapted existing solutions in a dynamic environment. Experimental comparisons were made with two other improvement heuristics using benchmark instances and road networks. This study evaluated the algorithm’s performance, considering the impact of dynamic node values and budget changes. Fang et al. [29] investigated the use of UAVs for monitoring landslide-prone areas by solving a TOP with mandatory visits that maximize data collection with multiple UAVs. The authors incorporated a novel algorithm such as a large neighborhood search with a neural network heuristic for an enhanced efficiency and solution quality in both smalland large-scale scenarios. Lastly, Juan et al. [30] provided a hybrid methodology that combined simulation and reinforcement learning to effectively manage a vehicle’s battery under dynamic settings. This approach demonstrated considerable advantages over non-informed decisions, showing its potential for routing plans that account for multiple dynamic elements such as weather, congestion, and battery conditions. Most of the reviewed papers are summarized in Table 1, which discuss deterministic, stochastic, and dynamic versions of the TOP. This paper considers the combination of stochastic and dynamic scenarios of the TOP, and introduces a novel sim-learnheuristic methodology designed to address these combined scenarios. Algorithms 2024,17, 200 6 of 19 Table 1. Summary of reviewed papers. Paper Year Proposed Approach Problem Domain Key Contributions Gonzalez-Neira et al. [13] 2021 Combined approach using GRASP, MSC, PAES, and AHP Permutation flow shop problem GRASP, simulation-based optimization, PAES, AHP Yazdani et al. [15] 2021 Hybrid genetic algorithm combined with Monte Carlo simulation Waste collection routing problem Simheuristic approach to address a real case study of waste collection planning Crawford et al. [16] 2021 Combination of Q-Learning with metaheuristics to address the exploration–exploitation dilemma Set covering problem Exploration–exploitation balance, Q-learnheuristics framework Gomez et al. [17] 2023 Combination of heuristics with reinforcement learning Capacitated dispersion problem Learnheuristic algorithm using reinforcement learning Bullah and van Zyl [18] 2023 Hybrid approach combining machine learning and metaheuristic optimization Constrained portfolio optimization Neural network prediction, guided search in solution space Tricoire et al. [19] 2010 Adaptive algorithm based on a Markov decision process TOP Decision-making based on deadlines Mufalli et al. [20] 2012 Combination of a mathematical method with local search strategies TOP Efficient algorithm for the TOP in critical situations Saeedvand et al. [21] 2020 Hybrid learning algorithm with an evolutionary multi-objective approach TOP with time windows Hybrid learning algorithm for dynamic decision-making Schmitt-Ulms et al. [22] 2022 Reinforcement learning using the Q-learning algorithm Stochastic TOP Machine learning approach for routing decisions in the TOP Lee and Ahn [23] 2024 Data-efficient DRL approach Multi-start TOP Adaptive policy network through DRL for UAV mission re-planning Xu et al. [24] 2020 An approximation algorithm refined for handling vehicles of the same type TOP Application of electric vehicles, focusing on charging energy-critical sensors using mobile chargers Sundar et al. [25] 2022 Concurrent multi-threaded branch-and-price algorithm with acceleration techniques TOP TOP variant involving fixed-wing drones with kinematic constraints Wang et al. [26] 2023 Self-adaptive heuristic algorithms Dynamic and stochastic orienteering problem Introduced algorithms to boost adaptability and efficiency in autonomous transportation. Elzein and Di Caro [27] 2022 Multi-stage metaheuristic Orienteering problem Merges and optimizes solutions for a high-quality parallelizable final path Algorithms 2024,17, 200 7 of 19 Table 1. Cont. Paper Year Proposed Approach Problem Domain Key Contributions Le et al. [28] 2021 Improve the heuristic based on a VNS algorithm Dynamic orienteering problem Proposed an efficient VNS-based heuristic for handling dynamic environments Fang et al. [29] 2023 Large neighborhood search algorithm embedding a neural network heuristic Dynamic TOP Verified the algorithm on synthetic datasets and a real-world large-scale case Juan et al. [30] 2023 Hybrid methodology combining simulation with reinforcement learning Dynamic TOP Efficient routing plans that significantly outperform non-informed decisions Algorithms 2024,17, 200 8 of 19 3. Problem Definition The TOP is an NP-hard optimization problem [ 1 ], with a formal definition on a directed graph G= (V , A) . The graph has V={ 0, 1, 2, . . . , n+ 1 } nodes, where the origin depot is node 0, the destination depot is node n+ 1, and N={ 1, . . . , n} are the intermediate nodes. The edges in A={(i , j)|i , j∈V , i=j} represent the connections between the nodes. We consider a set of homogeneous UAVs denoted as D , and each UAV d∈D begins its journey from the origin depot, serves a subset of intermediate nodes, and finally reaches the destination depot. The objective is to maximize the total reward collected by all UAVs. Following the mixed-integer linear programming model for the TOP proposed by [ 12 ], the hybrid version of the problem, where the travel times are either deterministic, stochastic, or dynamic, can be expressed formally as follows: max ∑ d∈D ∑ (i,j)∈A ujxd ij (1) where the objective is to maximize the aggregated deterministic reward of visited nodes over the set of edges. For each visited node in the route, it yields a reward ui≥ 0. Note that these rewards are zero for both the origin and destination depots, while they hold strictly positive values for the customers. More specifically, for each edge (i , j)∈A and each UAV d∈D , we consider the binary variable xd ij , which is equal to 1 if UAV d traverses through edge (i,j), and takes the value 0 otherwise. Below are the provided constraints with their explanations. In the course of the tour, each point is visited at most once to ensure that no point is revisited (2). ∑ d∈D ∑ i∈V xd ij ≤1∀j∈N(2) The variable yd i is introduced to indicate the position of node i in the tour made by vehicle d, and constraint (3) makes sure that there are no sub-tours. yd i−yd j+1≤(1−xd ij)|N| ∀i,j∈N,∀d∈D(3) Constraint (4) states that the total travel time of each vehicle should not be more than its threshold ( Tmax ), since each UAV d∈D starts its route and can only serve some intermediate nodes due to the limited travel time. The total travel time is the sum of the travel times of deterministic, dynamic, and stochastic edges, which are included in Adet , Adyn , and Astoch , respectively. These are disjoint sets that include all the edges of set A . For each edge (i , j)∈Adet , we assume that the travel time of each edge is deterministic and predefined ( tij =tji > 0). Similarly, for each edge (i , j)∈Astoch , we assume the travel time Tij is stochastic and can be modeled using a probability distribution function. Lastly, for each edge (i , j)∈Adyn , we assume the travel time ˆ tij is dynamic, which depends on various factors such as weather and traffic conditions. Since the stochastic and dynamic travel times bring in a level of uncertainty, this constraint introduces a probabilistic approach to account for such unpredictability in travel times. The parameter γ , which ranges between 0 and 1, represents a threshold that defines the acceptable level of probability for keeping the travel time within the specified travel limit. P ∑ (i,j)∈Adet tijxd ij +∑ (i,j)∈Adyn ˆ tijxd ij +∑ (i,j)∈Astoch Tijxd ij ≤Tmax ≥γ∀d∈D(4) Constraint (5) ensures that for every arrival at a node, there is a corresponding departure from that node. ∑ i∈V xd ij =∑ h∈V xd jh ∀d∈D∀j∈N(5) Algorithms 2024,17, 200 9 of 19 Constraint (6) indicates that the tour always commences at the starting node 0 and ends at the ending node n+1. ∑ j∈N x0jd =∑ j∈N xj(n+1)d=1∀d∈D(6) Constraints (7) and (8) refer to the nature of yd j and xd ij variables. Finally, the vehicle departs from each node it visited, except for the end node. yd j≥0∀j∈N∀d∈D(7) xd ij ∈ {0, 1} ∀i,j∈A,∀d∈D(8) Although the deterministic version of the TOP has been widely studied in the literature, the high degree of uncertainty in real-life applications of the TOP makes it a good candidate for our purpose. In this work, both stochastic and dynamic travel times are introduced in the TOP. Hence, we will consider that the travel time of some edges can be modeled as random variables following a theoretical probability distribution. Likewise, we will consider that other edges have uncertain travel times that have to be predicted using a multiple regression model. As far as we know, no other authors have addressed this realistic version of the TOP in the past. 4. Our Sim-Learnheuristic Approach To effectively solve the hybrid TOP described in Section 3, we propose a novel simlearnheuristic method that combines a biased-randomized heuristic multi-start (BR-MS) framework, Monte Carlo simulations (MCSs), and a multiple regression model. This methodology aims to combine the advantages of all elements, enabling efficient exploration of the search space for optimal solutions [31]. This sim-learnheuristic methodology extends the simheuristic approach proposed in [ 8 ] to solve the TOP with stochastic processing times. Figure 3outlines the main components of the sim-learnheuristic methodology. The sim-learnheuristic method can be summarized in the following six main steps, which can be identified by labels S1 through S6. First, the optimization problem is initially converted to its deterministic version, where variables are replaced by their expected or most likely values, effectively eliminating uncertainty. This deterministic problem is then solved using a BR-MS framework, leading to the generation of multiple high-quality solutions. These deterministic solutions are subsequently subjected to a comprehensive evaluation, considering the various sources of uncertainty inherent in the problem. This evaluation involves a short number of MCS runs, during which random variables and dynamic elements are assigned different values based on probability distributions or machine learning models, respectively. Additionally, constraints are assessed under uncertain conditions. Descriptive statistics are computed for each solution, yielding detailed insights into their performance. The examination of these solutions informs the generation of new solutions within the BR-MS framework until a predefined stopping criterion, such as a maximum execution time, is met. Following the previous stage, a subset of top-performing solutions, referred to as ’elite’ solutions, are further examined under uncertainty. This second examination involves a longer number of MCS runs than the initial evaluations. Based on this intensive examination, the solutions are ranked, and the best solution is recommended. The selection of the best solution may take into consideration measures of interest beyond just the expected value, such as variance or reliability, to ensure a more robust decision-making process. Algorithms 2024,17, 200 16 of 19 Table 2. Experimental results for the different scenarios. Instances Deterministic Scenario Stochastic Scenario Dynamic Scenario Hybrid Scenario BKS (1) OBD (2) GAP% (1)–(2) OBD-S OBS OBD-Dy OBDy OBD-H OBH p1.2.r 280 275 1.78 166.60 167.74 33.24 36.84 150.86 159.23 p1.2.h 110 110 0.00 70.21 73.96 84.70 105.00 68.46 72.72 p1.2.p 250 245 2.00 134.29 148.34 0.00 57.20 130.55 143.48 p1.4.k 100 100 0.00 69.85 71.01 52.48 58.62 68.47 70.60 p2.3.h 165 165 0.00 104.68 105.01 72.72 76.56 102.30 105.06 p2.3.e 120 120 0.00 79.83 83.77 58.02 63.10 80.69 80.72 p2.3.f 120 120 0.00 91.09 91.55 120.00 120.00 90.48 90.84 p2.2.i 230 230 0.00 173.92 176.50 146.62 147.21 163.42 172.80 p2.4.j 120 120 0.00 91.09 91.55 120.00 120.00 90.48 90.84 p3.3.j 380 380 0.00 258.12 267.25 130.36 130.63 262.35 262.82 p3.3.o 590 590 0.00 346.61 379.20 129.58 309.12 339.07 359.68 p3.2.a 90 90 0.00 58.10 61.26 54.69 56.39 58.21 58.62 p3.2.d 220 220 0.00 142.13 155.44 105.25 193.86 137.19 141.27 p3.4.j 310 310 0.00 200.25 225.31 159.61 251.68 194.09 222.26 p3.4.k 350 350 0.00 247.31 257.19 218.01 221.11 242.13 249.29 p3.4.i 270 270 0.00 170.68 178.18 90.48 117.33 166.88 173.25 p5.3.z 1635 1620 0.91 943.60 1235.26 2.34 1525.00 850.78 1240.57 p5.3.o 870 870 0.00 495.03 520.64 0.00 270.00 485.46 487.78 p5.2.i 480 450 6.25 297.43 306.67 90.22 424.38 265.05 292.62 p6.2.g 660 660 0.00 431.97 436.26 417.12 446.49 406.56 411.51 p6.2.f 588 588 0.00 336.04 361.62 1.18 2.65 327.81 332.51 p7.2.c 101 101 0.00 80.75 82.03 48.05 48.16 66.18 66.20 p7.4.e 123 123 0.00 113.46 113.81 113.90 115.47 76.49 77.01 Average: 354.86 352.47 0.47 221.87 243.02 97.76 212.90 209.73 233.10 Moreover, if we compare the computed averages for the different scenarios, we observe that we can classify the four different scenarios based on their uncertainty levels. Firstly, the deterministic scenario can be considered a reference scenario with perfect information (i.e., without uncertainty) for the expected reward under different uncertainty conditions. Conversely, in the stochastic scenario, we observe a lower uncertainty level, resulting in an average expected reward of 221.87 and 243.02 for the OBD-S and OBS, respectively. This can be attributed to half of the edges’ travel times being stochastic in nature, while the other half being deterministic. Similarly, for the hybrid scenario, we can observe a medium level of uncertainty which results in an average expected reward of 209.73 and 233.10 for the OBD-H and OBH, respectively. Lastly, considering the dynamic scenario, it demonstrates the highest level of uncertainty, driven by the dynamic conditions that result in highly variable travel times. The resulting average expected reward is 97.76 and 243.02 for the OBD-Dy and OBDy, respectively. The dynamic scenario comprises half the dynamic and half the deterministic travel time, while the hybrid scenario consists of roughly one-third of the dynamic and one-third of the stochastic travel times. In other words, the combined uncertainty of the travel times in the dynamic scenario surpasses that of the hybrid and stochastic scenarios. Figure 4shows an overview of Table 2which details the performance of our simlearnheuristic approach for all considered scenarios. The horizontal and vertical axes represent the four uncertainty scenarios and the percentage gap obtained with respect to the BKS reported in the literature, respectively. Median values are represented by triangles and lines, while outliers are presented by circles. The average percentage gap for the OBD-S is 33.48, while the average percentage gap for the OBS is 30.16. This means that, on average, the OBS solutions are closer to the BKS solutions in the stochastic scenario. In the hybrid scenario, if we compare the percentage gaps of the OBD-H with the OBH, we can see that the OBH outperforms the OBD-H and is closer to the BKS. However, the average gap for OBD-Dy is 55.12. This very high gap indicates that the deterministic approach Algorithms 2024,17, 200 17 of 19 does not adapt well to the changing dynamics of the system and results in considerably worse outcomes. Figure 4. Gaps with respect to BKS for the different scenarios. 7. Conclusions and Future Work This paper presents a hybrid version of the TOP encompassing deterministic, stochastic, and dynamic travel times. To address this problem, a novel sim-learnheuristic methodology is proposed, effectively combining a savings-based heuristic algorithm, Monte Carlo simulations, and a multiple regression model. By integrating stochastic and dynamic components in the sim-learnheuristic methodology, this approach captures the impact of randomness and variability, obtaining high-quality solutions in scenarios with uncertainty. This combination allows for the modeling of scenarios with both stochastic and dynamic components simultaneously. The computational experiments reveal that relying on the best solutions found for the deterministic version of the problem can lead to high variance and unreliability in realistic scenarios with uncertainties. These uncertainties can result in increasing travel times due to factors like traffic congestion and weather conditions. In contrast, the sim-learnheuristic approach is able to find high-quality solutions in uncertainty scenarios as it incorporates the stochastic and dynamic components in the search for solutions that maximize the collected rewards. This approach ensures the generated solutions are both reliable and robust, even in uncertain conditions with stochastic and dynamic travel times. Moving forward, our future work encompasses two key aspects. Firstly, we aim to solve the multi-depot variant of the TOP. Secondly, we intend to enhance the realism of our approach by employing discrete event simulations and more intricate machine learning models. This will enable us to account for diverse interactions and complex environmental conditions, such as synchronization between various vehicles or UAV battery levels. Author Contributions: Conceptualization, M.P. and A.A.J.; methodology, M.P. and X.A.M.; software, M.P. and X.A.M.; validation, M.P., X.A.M. and J.P.; writing—original draft preparation, M.P., X.A.M., J.P. and A.A.J.; writing—review and editing, A.A.J.; supervision, A.A.J. All authors have read and agreed to the published version of the manuscript. Funding: This work was partially funded by the Spanish Ministry of Science and Innovation (PRE2020-091842, PID2022-138860NB-I00, RED2022-134703-T) and the Horizon Europe program (HORIZON-CL4-2022-HUMAN-01-14-101092612). Institutional Review Board Statement: Not applicable. Algorithms 2024,17, 200 18 of 19 Informed Consent Statement: Not applicable. Data Availability Statement: Data are contained within the article. Conflicts of Interest: The authors declare no conflicts of interest. References 1. Chao, I.M.; Golden, B.L.; Wasil, E.A. The team orienteering problem. Eur. J. Oper. Res. 1996,88, 464–474. [CrossRef] 2. Gupta, A.; Afrin, T.; Scully, E.; Yodo, N. Advances of UAVs toward future transportation: The state-of-the-art, challenges, and opportunities. Future Transp. 2021,1, 326–350. [CrossRef] 3. Bayliss, C.; Juan, A.A.; Currie, C.S.; Panadero, J. A learnheuristic approach for the team orienteering problem with aerial drone motion constraints. Appl. Soft Comput. 2020,92, 106280. [CrossRef] 4. Poudel, S.; Moh, S. Hybrid path planning for efficient data collection in UAV-aided WSNs for emergency applications. Sensors 2021,21, 2839. [CrossRef] [PubMed] 5. Gunawan, A.; Lau, H.C.; Vansteenwegen, P. Orienteering problem: A survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 2016,255, 315–332. [CrossRef] 6. Evers, L.; Glorie, K.; Van Der Ster, S.; Barros, A.I.; Monsuur, H. A two-stage approach to the orienteering problem with stochastic weights. Comput. Oper. Res. 2014,43, 248–260. [CrossRef] 7. Yu, Q.; Cheng, C.; Zhu, N. Robust team orienteering problem with decreasing profits. INFORMS J. Comput. 2022,34, 3215–3233. [CrossRef] 8. Panadero, J.; Juan, A.A.; Bayliss, C.; Currie, C. Maximising reward from a team of surveillance drones: A simheuristic approach to the stochastic team orienteering problem. Eur. J. Ind. Eng. 2020,14, 485–516. [CrossRef] 9. Kirac, E.; Gedik, R.; Oztanriseven, F. Solving the team orienteering problem with time windows and mandatory visits using a constraint programming approach. Int. J. Oper. Res. 2023,46, 20–42. [CrossRef] 10. Lin, S.W.; Vincent, F.Y. Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing. Comput. Ind. Eng. 2017,114, 195–205. [CrossRef] 11. Gunawan, A.; Ng, K.M.; Kendall, G.; Lai, J. An iterated local search algorithm for the team orienteering problem with variable profits. Eng. Optim. 2018,50, 1148–1163. [CrossRef] 12. Panadero, J.; Juan, A.A.; Ghorbani, E.; Faulin, J.; Pagès-Bernaus, A. Solving the stochastic team orienteering problem: Comparing simheuristics with the sample average approximation method. Int. Trans. Oper. Res. 2023,31, 3039–3060. [CrossRef] 13. Gonzalez-Neira, E.M.; Montoya-Torres, J.R.; Jimenez, J.F. A multicriteria simheuristic approach for solving a stochastic permutation flow shop scheduling problem. Algorithms 2021,14, 210. [CrossRef] 14. Caldeira, R.H.; Gnanavelbabu, A. A simheuristic approach for the flexible job shop scheduling problem with stochastic processing times. Simulation 2021,97, 215–236. [CrossRef] 15. Yazdani, M.; Kabirifar, K.; Frimpong, B.E.; Shariati, M.; Mirmozaffari, M.; Boskabadi, A. Improving construction and demolition waste collection service in an urban area using a simheuristic approach: A case study in Sydney, Australia. J. Clean. Prod. 2021, 280, 124138. [CrossRef] 16. Crawford, B.; Soto, R.; Lemus-Romani, J.; Becerra-Rozas, M.; Lanza-Gutiérrez, J.M.; Caballé, N.; Castillo, M.; Tapia, D.; CisternasCaneo, F.; García, J.; et al. Q-learnheuristics: Towards data-driven balanced metaheuristics. Mathematics 2021,9, 1839. [CrossRef] 17. Gomez, J.F.; Uguina, A.R.; Panadero, J.; Juan, A.A. A Learnheuristic Algorithm for the Capacitated Dispersion Problem under Dynamic Conditions. Algorithms 2023,16, 532. [CrossRef] 18. Bullah, S.; van Zyl, T.L. A Learnheuristic Approach to A Constrained Multi-Objective Portfolio Optimisation Problem. In Proceedings of the 2023 7th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, Virtual, 23–24 April 2023; pp. 58–65. 19. Tricoire, F.; Romauch, M.; Doerner, K.F.; Hartl, R.F. Heuristics for the multi-period orienteering problem with multiple time windows. Comput. Oper. Res. 2010,37, 351–367. [CrossRef] 20. Mufalli, F.; Batta, R.; Nagi, R. Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans. Comput. Oper. Res. 2012,39, 2787–2799. [CrossRef] 21. Saeedvand, S.; Aghdasi, H.S.; Baltes, J. Novel hybrid algorithm for Team Orienteering Problem with Time Windows for rescue applications. Appl. Soft Comput. 2020,96, 106700. [CrossRef] 22. Schmitt-Ulms, F.; Hottung, A.; Sellmann, M.; Tierney, K. Learning to solve a stochastic orienteering problem with time windows. In Proceedings of the International Conference on Learning and Intelligent Optimization, Milos Island, Greece, 5–10 June 2022; Springer: Cham, Switzerland, 2022; pp. 108–122. 23. Lee, D.H.; Ahn, J. Multi-start team orienteering problem for UAS mission re-planning with data-efficient deep reinforcement learning. Appl. Intell. 2024,54, 4467–4489. [CrossRef] 24. Xu, W.; Xu, Z.; Peng, J.; Liang, W.; Liu, T.; Jia, X.; Das, S.K. Approximation algorithms for the team orienteering problem. In Proceedings of the IEEE INFOCOM 2020—IEEE Conference on Computer Communications, Toronto, ON, Canada, 6–9 July 2020; pp. 1389–1398. 25. Sundar, K.; Sanjeevi, S.; Montez, C. A branch-and-price algorithm for a team orienteering problem with fixed-wing drones. EURO J. Transp. Logist. 2022,11, 100070. [CrossRef] Algorithms 2024,17, 200 19 of 19 26. Wang, B.; Bian, Z.; Mansouri, M. Self-adaptive heuristic algorithms for the dynamic and stochastic orienteering problem in autonomous transportation system. J. Heuristics 2023,29, 77–137. [CrossRef] 27. Elzein, A.; Di Caro, G.A. A clustering metaheuristic for large orienteering problems. PLoS ONE 2022,17, e0271751. [CrossRef] [PubMed] 28. Le, H.T.; Middendorf, M.; Shi, Y. An improvement heuristic based on variable neighborhood search for a dynamic orienteering problem. In Proceedings of the Evolutionary Computation in Combinatorial Optimization: 21st European Conference, EvoCOP 2021, Held as Part of EvoStar 2021, Virtual Event, 7–9 April 2021; Springer: Cham, Switzerland, 2021; pp. 68–83. 29. Fang, C.; Han, Z.; Wang, W.; Zio, E. Routing UAVs in landslides Monitoring: A neural network heuristic for team orienteering with mandatory visits. Transp. Res. Part E Logist. Transp. Rev. 2023,175, 103172. [CrossRef] 30. Juan, A.A.; Marugan, C.A.; Ahsini, Y.; Fornes, R.; Panadero, J.; Martin, X.A. Using Reinforcement Learning to Solve a Dynamic Orienteering Problem with Random Rewards Affected by the Battery Status. Batteries 2023,9, 416. [CrossRef] 31. Martí, R.; Resende, M.G.; Ribeiro, C.C. Multi-start methods for combinatorial optimization. Eur. J. Oper. Res. 2013,226, 1–8. [CrossRef] 32. Tang, H.; Miller-Hooks, E. A tabu search heuristic for the team orienteering problem. Comput. Oper. Res. 2005,32, 1379–1407. [CrossRef] 33. Ke, L.; Archetti, C.; Feng, Z. Ants can solve the team orienteering problem. Comput. Ind. Eng. 2008,54, 648–665. [CrossRef] 34. Dang, D.C.; Guibadj, R.N.; Moukrim, A. An effective PSO-inspired algorithm for the team orienteering problem. Eur. J. Oper. Res. 2013,229, 332–344. [CrossRef] Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.