A biased-randomised iterated local search for the team orienteering arc routing problem allowing different origin and destination

A Biased-Randomised Iterated Local Search for the Team Orienteering Arc Routing Problem Allowing Different Origin and Destination Xabier A. Martina,∗, Peter Keenanb, Javier Panaderoc, Sean McGarraghyb, Angel A. Juana aResearch Center on Production Management and Engineering, Universitat Polit`ecnica de Val`encia, Alcoy, Spain bCentre for Business Analytics, School of Business, University College Dublin, Belfield, Ireland cDepartment of Computer Architecture and Operating Systems, Universitat Aut`onoma de Barcelona, Bellaterra, Spain Abstract In this paper, we consider the hybridisation of the team orienteering problem and the arc routing problem, the so-called team orienteering arc routing problem (TOARP). This problem has recently raised interest among researchers and practitioners as it can model new routing problems involving unmanned aerial vehicles or other types of electric vehicles. In the TOARP, a fixed fleet of vehicles, initially located at a depot, has to collect as much reward as possible from visiting a set of arcs, while they must visit a set of required arcs. At the same time, they must return to the depot on or before a given deadline (which can be time-based or distance-based). In this paper, we explore an extension of the TOARP in which the origin depot and the destination depot may be different nodes in a network. To solve this version of the problem, we propose a novel biased-randomised iterated local search algorithm. Computational results show the capability, efficiency and robustness of our approach, which provides competitive solutions to the TOARP in short computing times and outperforms some of the best-known solution approaches in the literature. Keywords: arc routing problem; team orienteering problem; biased randomisation; iterated local search. 1. Introduction The team orienteering problem (TOP) and the arc routing problem (ARP) are challenging optimisation problems that have gained significant attention from the scientific community in recent years. These problems are known to be NP-hard, indicating their high computational complexity. However, their practical relevance extends beyond their theoretical complexity, as they find numerous applications in real-life logistics and transportation domains. In this paper, we focus on a hybrid version that combines both the TOP and the ARP, known as the team orienteering arc ∗Corresponding author Email addresses: [email protected] (Xabier A. Martin), [email protected] (Peter Keenan), [email protected] (Javier Panadero), [email protected] (Sean McGarraghy), [email protected] (Angel A. Juan) Preprint submitted to Journal of Heuristics December 3, 2025 routing problem (TOARP). This problem has attracted considerable interest among researchers and practitioners due to its ability to effectively model routing scenarios involving unmanned aerial vehicles (UAVs) or other types of electric vehicles (Wang et al., 2022). In the original version of the TOARP (Archetti et al., 2014), a predetermined fleet of vehicles, initially located at a central depot, needs to navigate using some traversing arcs before returning to the central depot. Along the way, the vehicles aim to maximise their cumulative rewards by visiting a set of profitable arcs, while they must visit a set of required arcs. Additionally, the vehicles must adhere to a given deadline, which can be defined either in terms of time or distance, ensuring that they reach the central depot on time or before a specified limit. This paper addresses an extension of the TOARP, which involves considering a destination depot that might be different from the origin one. By addressing this variant of the TOARP, we aim to contribute to the development of efficient strategies for routing unmanned aerial vehicles and other electric vehicles in practical applications. Figure 1 depicts a simple example of such a TOARP with two vehicles. Along their route, the vehicles traverse several arcs, some of which are required (red lines), others of which are profitable (blue lines), with the rest being traversing arcs used to reach the other kinds of arcs. The traversing arcs taken by the vehicles are depicted as solid lines, while the non-used traversing arcs are shown as dashed lines. Observe that the proposed solution is feasible, as the vehicles visit all required arcs in the network, while maximising the collected reward by visiting some profitable arcs before reaching the destination depot. Figure 1: Illustrative example of a TOARP solution with two vehicles. While the single-depot TOARP has been explored in existing literature, we have not found any research on the version in which the destination depot might be different from the origin depot. To tackle both the original and the new version of the TOARP, we propose a novel approach based on a biased-randomised iterated local search (BR-ILS) algorithm. This algorithm leverages biasedrandomisation techniques, as described in the work by Dominguez et al. (2016), to transform a 2 traditional greedy heuristic into a probabilistic algorithm. By introducing controlled randomisation during the solution-construction process, the algorithm enhances its ability to find high-quality solutions in short computing times. Addressing the extended TOARP with different origin and destination depots has practical implications such as routing unmanned aerial vehicles or electric vehicles considering a starting point different from the destination one. By studying this variant of the TOARP, we aim to develop effective solutions that cater to the complexities and requirements of such real-world applications. The main contributions of this paper are as follows: (i) addressing a variant of the TOARP with different origin and destination depots; (ii) providing a mathematical model describing the details of this version of the problem; and (iii) proposing a novel optimisation algorithm that combines a biased-randomised savings heuristic with an iterated local search (ILS) metaheuristic to solve this TOARP version as well as the original single-depot TOARP. This approach is able to outperform the best-known solution approaches in the literature for 4 of the 60 hardest TOARP benchmark instances. The remainder of this paper is structured as follows: Section 2 reviews the limited literature existing on the TOARP. Section 3 provides a formal description of the problem considered in this paper. Section 4 describes a BR-ILS algorithm to solve the extended version of the TOARP. Section 5 discusses the computational experiments and algorithm parameter tuning process. Section 6 presents the results obtained for the original version of the TOARP and shows the competitiveness of the proposed algorithm when compared with the best-known solution approaches in the literature. Section 7 shows that our BR-ILS algorithm can efficiently solve the extended TOARP version with a destination depot different from the origin depot. Finally, Section 8 summarises the main findings of this work. 2. Related Work In their seminal work, Malandraki and Daskin (1993) introduced two important optimisation problems: the single-vehicle maximum benefit Chinese postman problem (MBCPP) and the maximum benefit travelling salesman problem (MBTSP). In the MBCPP, a reward is obtained each time a link in a directed graph is traversed, while the MBTSP seeks to maximise the total benefit in a traditional travelling salesman problem setting. Chao et al. (1996) introduced another significant problem, the TOP, inspired by the sport of orienteering. Orienteering problems involve visiting vertices or arcs, each of which has a score, and the objective is to maximise the score subject to restrictions on the length of the route and requirements to visit certain vertices or arcs (Vansteenwegen et al., 2011). The classic TOP involves fixed start and end points, where each agent must navigate from the start to the end within a specified time or distance constraint. The agents are rewarded for visiting specific intermediate points, and the objective is to maximise the overall reward accumulated. However, due to time or distance limitations, visiting all the intermediate points may not be necessary or even feasible. Although the possibility of incorporating stochastic travel time was acknowledged in Chao et al. (1996), they did not explore it further. Expanding on this line of research for problems based on vertices, Archetti et al. (2010) introduced the undirected capacitated arc routing problem with profits (UCARPP). In general, ARPs aim to visit arcs rather than vertices (Corber´an et al., 2021). The arc routing with profits problem arises where reward and travel times are associated with arcs and the objective is to maximise reward within a distance limit (Feillet et al., 2005). Archetti et al. (2010) marked the first investigation into a multi-vehicle arc routing problem with rewards. In the UCARPP, there is a depot 3 from which each vehicle starts and returns. The goal is to determine the most profitable routes for vehicles while considering capacity constraints and the potential benefits associated with the arcs. Archetti et al. (2014) introduced the TOARP as an extension of the TOP by associating customers, demands, and rewards with arcs. Whereas in the TOP a route might visit a customer at a particular point, in the TOARP all customers on a road might be visited and the reward associated with that arc may be related to the number of customers or to the sum of their values. Similarly to their previous work on the UCARPP in Archetti et al. (2010), the TOARP involves a common depot for both the starting and ending point, unlike the original TOP where they can differ. In the TOARP, there are required arcs that must be serviced. Servicing a non-required arc potentially yields a reward, but the arc need not be serviced. A group of agents, each with a specified time capacity, is responsible for servicing the arcs. The objective of the TOARP is to determine the optimal set of traversed arcs that maximises the total collected reward while adhering to the time capacity constraints for each agent. Consequently, the TOARP can be regarded as a specific case of the more general time-capacitated arc routing problem in which not all arcs are required (de Armas et al., 2019). Building on the original work on the TOARP, Archetti et al. (2015) utilised a matheuristic approach to tackle the TOARP and achieved optimal solutions for nearly all tested instances, with only one exception. Riera-Ledesma and Salazar-Gonz´alez (2017) proposed a novel approach using column generation to address the limitations of existing branch-and-cut methods. Their approach transforms the problem from a customer-on-arc to a customer-on-vertex representation, simplifying both the branching and pricing phases and providing a more effective solution for instances where knapsack constraints heavily influence performance. Recent research has introduced variations of the TOARP to address additional challenges. Bianchessi et al. (2022) and Reula and Mart´ı (2023) discuss the profitable close-enough arc routing problem, which arises in modern applications such as radio-frequency identification based meter reading. In such scenarios, meters can be read remotely from a distance rather than at their exact locations. Agarwal and Akella (2022) explore the correlated arc orienteering problem in situations where the rewards of arcs exhibit correlation, such as in road inspection tasks following a flood, where neighbouring roads are also likely to be affected. Recently, Zhang et al. (2023) introduced a TOARP version including stochasticity. Table 1 summarises the key characteristics of each of the previous works and the version studied in this paper, which considers a more flexible extension of the TOARP with a destination depot that might be different from the origin. In addition, the version analysed in our paper considers both required and non-required arcs. The inclusion of distinct fixed start and end points in the TOARP represents a novel aspect in comparison to previous studies, aligning it more closely with the original definition of the TOP. As far as we are aware, no other work has represented the depot as two distinct points, which may or may not be the same. This extension also caters to various contemporary and foreseeable future arc routing scenarios involving delegated mapping, inspection, or delivery tasks. For instance, envision a scenario where a truck transports multiple drones, along with their respective cargoes if applicable, to a designated starting location. Once they arrived, the drones disperse and carry out their designated functions, such as inspecting electric cables. Meanwhile, the truck proceeds to the endpoint. Upon completion of their tasks, the drones do not need to return to their initial starting points, minimising the strain on their limited battery life. The truck serves as the primary mode of transportation, except when the drones disperse to carry out their specific delegated tasks. This framework accounts for the evolving range of operations involving collaborative efforts between vehicles and drones, accommodating the efficient execution of various tasks while optimising resource utilisation. 4 Table 1: Summary of different TOARP articles. Work Number of Vehicles All arcs required Collections per profitable arc Single depot Time constraint Capacity constraint Directed Stochastic Malandraki and Daskin (1993) 1 N Multiple Y N Y Y N Archetti et al. (2010) Many N 1 Y Y Y N N Archetti et al. (2014) Many N 1 Y Y N Y N Archetti et al. (2015) Many N 1 Y Y N Y N Riera-Ledesma and Salazar-Gonz´alez (2017) Many N 1 Y Y N Y N Zhang et al. (2023) Many N 1 Y Y N N Service Our study Many N 1 N Y N Y N 3. Formal Problem Description This section provides a formulation for the TOARP with possibly different origin and destination depots. This formulation extends and includes the one provided by Archetti et al. (2014) for the TOARP with a single depot. The goal of the problem is to maximise the total collected reward while ensuring that the constraints on the maximum number of vehicles available and the maximum time each vehicle can employ from its origin to its destination are not violated. Let V= {0,1,2, . . . , n, n+1}be the set of nodes connected by arcs, where node 0 is the origin (source) depot and node n+1 is the destination (sink) depot. Consider a set of arcs A={(i, j)|i∈V, j ∈V, i =j} connecting some of the nodes in V(the network does not have to be complete). The arcs can be divided into two types: required arcs and profitable arcs. The set of required arcs, Ar⊆A, need to be visited in any case, while profitable arcs, Ap⊆A, are optional and provide a reward the first time they are visited (they can be visited more than once, either by the same or by another vehicle, but no additional reward can be collected from these additional visits). Let us denote by tij the travelling time associated with each arc (i, j)∈A, and by rij the reward associated with each arc (i, j)∈Ap. We have a fleet K={1,2,...,|K|} of vehicles available. Each vehicle will depart from the origin depot and needs to reach the destination depot within a maximum time Tmax >0. It is important to note that some vehicles may not service any arcs and travel directly from the origin to the destination. This represents cases where some vehicles may not be used to achieve the optimal solutions, since fewer vehicles are needed to service the required and profitable arcs. In this paper, we assume, without loss of generality, that all vertices are incident with arcs in Ar∪Ap. If the network does not satisfy this condition, it can be transformed into an equivalent one that does. Moreover, given a subset of vertices S⊆V, let A(S) be the set of arcs with both endpoints in S, defined as A(S) = {(i, j)∈A|i, j ∈S}. Similarly, this can be defined for the set of required and profitable arcs Ar(S) and Ap(S), respectively. We introduce decision variables xk ij, representing the number of times an arc (i, j) is traversed by vehicle k∈K. The binary variable yk ij takes the value 1 if vehicle k∈Kis the one that visits for the first time arc (i, j), and is 0 otherwise. The objective is to maximise the total collected reward, given by: max X k∈K X (i,j)∈Ap rij ·yk ij (1) 5 subject to: i) The number of times a vehicle enters an intermediate node is balanced with the number of times it exits that node: X j∈V\{i,n+1} xk ji =X j∈V\{i,0} xk ij ∀i∈V\ {0, n + 1},∀k∈K(2) ii) Ensure the balance between the number of times a vehicle exits the origin/source and enters the destination/sink depot nodes (node 0 and node n+ 1, respectively): X j∈V\{0} xk 0j=X j∈V\{n+1} xk j,n+1 ∀k∈K(3) iii) If a vehicle services an arc, enforce the existence of a connected path from the origin to the destination across that arc. First, for any non-empty subset of nodes Sthat is a proper subset of Vand does not include the origin and the destination, guarantee that there is a connected path from the outside of Sto at least one node within Swhenever an arc awith both nodes in Sis serviced by vehicle k: X i∈V\S X j∈S xk ij ≥yk a∀S⊂V\ {0, n + 1}, S =∅,∀a∈Ar(S)∪Ap(S),∀k∈K(4) iv) Now, guarantee that there is a connected path from at least one node within Sto the outside of Swhenever an arc awith both nodes in Sis serviced by vehicle k: X i∈S X j∈V\S xk ij ≥yk a∀S⊂V\ {0, n + 1}, S =∅,∀a∈Ar(S)∪Ap(S),∀k∈K(5) v) Each vehicle traverses the arcs it services (i.e., the flow of vehicles entering an arc must be greater than or equal to the indicator variable representing whether the arc has been serviced): xk ij ≥yk ij ∀(i, j)∈Ar∪Ap,∀k∈K(6) vi) Each required arc is serviced by exactly one vehicle: X k∈K yk ij = 1 ∀(i, j)∈Ar(7) vii) A potential arc’s reward is collected by at most one vehicle, preventing duplicate collection: X k∈K yk ij ≤1∀(i, j)∈Ap(8) viii) Ensure that the total time spent by each vehicle on its route does not exceed the maximum time limit: X (i,j)∈A tij ·xk ij ≤Tmax ∀k∈K(9) ix) Finally, include the domain constraints: xk ij ∈N∀(i, j)∈A, ∀k∈K(10) yk ij ∈ {0,1} ∀(i, j)∈Ar∪Ap,∀k∈K(11) 6 4. A BR-ILS Algorithm for the TOARP We introduce a BR-ILS algorithm as a solution approach for the TOARP. This algorithm has an effective and relatively straightforward implementation in code, striking a favourable balance between simplicity and computational performance. Additionally, it features a reduced number of tuning parameters, eliminating the need for time-consuming configuration processes. The core concept of our BR-ILS algorithm involves extending a savings heuristic originally developed for the TOP to provide initial feasible solutions for the TOARP, and refining the initial solutions using an ILS metaheuristic to obtain high-quality solutions. Algorithm 1 outlines the key components of our BR-ILS algorithm, which consists of two stages. In the first stage, we generate a feasible initial solution (initSol) utilising a novel savings heuristic inspired by the savings heuristic proposed by Panadero et al. (2020) for solving the TOP. We have adapted and extended this heuristic to account for the specific characteristics of the TOARP. These characteristics include: (i) the target of the service is defined on arcs, categorised into required arcs and profitable arcs; and (ii) visiting a potential arc allows for the collection of its reward at most once. The novel savings heuristic will be presented below as Algorithm 3. Once the initial solution is generated, it is assigned as the base solution (baseSol) for the ILS and the best-found solution (bestSol). During the second phase of our approach, we employ an ILS metaheuristic to improve the base solution by systematically exploring the search space. The ILS is a relatively straightforward metaheuristic that consists of a perturbation phase followed by a local search operator to generate new solutions until a stopping criterion is met. The perturbation and local search procedures will be described next as Algorithm 5 and Algorithm 6, respectively. Once a new solution (newSol) has been generated, the base solution and the best-found solution may be updated. More precisely: •If the reward of the new solution improves upon the reward of the base solution, the latter is updated. •Similarly, if the reward of the new solution improves upon the reward of the best-found solution, the latter is updated. In order to further diversify the search and reduce the probability of getting trapped in a local maximum, the algorithm might occasionally accept non-improving solutions following an acceptance criterion based on the concept of credit (Talbi, 2009). That is, the base solution is updated if the new solution is worse than the base solution but the difference in reward is lower than the improvement (credit) obtained in the last update of the base solution. Finally, once the stopping criterion is met, the best-found solution is returned as the output of the BR-ILS algorithm. Algorithm 2 details the process of generating an initial solution, which employs a biasedrandomised variant of the novel savings heuristic. This involves extending the deterministic heuristic to a probabilistic approach by assigning diminishing probabilities to the different savings in the sorted list. Following the methodology proposed in Estrada-Moreno et al. (2019), a skewed Geometric probability distribution is introduced to control the selection process, which is governed by a parameter β∈(0,1). This approach ensures that the same solution is not obtained repeatedly and allows for the discovery of solutions that outperform those obtained through purely greedy behaviour. Thus, the solution generation process utilises the biased-randomised savings heuristic to create a new solution (newSol). This solution is then checked for feasibility. How a solution is deemed feasible will be explained in Algorithm 3. If the initial solution is not feasible, new solutions are constructed iteratively until a feasible solution is obtained. Once a feasible solution is found, it is returned from the procedure as the initial solution (initSol). Note that the generation 7 Algorithm 1 BR-ILS algorithm. 1: function BR-ILS(inputs, maxT ime, α, β, Tmax ) 2: initSol ←genInitSol(inputs, α, β, Tmax ) 3: baseSol ←initSol 4: bestSol ←initSol 5: time ←0 6: credit ←0 7: while time < maxT ime do 8: perturbedSol ←perturbation(baseSol, Tmax ) 9: newSol ←localSearch(perturbedSol, Tmax ) 10: ∆ ←reward(baseSol)−reward(newSol) 11: if ∆<0then 12: credit ← −∆ 13: baseSol ←newSol 14: if reward(newSol)>reward(bestSol)then 15: bestSol ←newSol 16: end if 17: else if 0<∆≤credit then 18: credit ←0 19: baseSol ←newSol 20: end if 21: time ←time +elapsedTime() 22: end while 23: return bestSol 24: end function of new solutions is a rapid process, capable of producing multiple solutions within a few seconds. Furthermore, testing has shown that even in the most challenging instances, only a few iterations are typically required to find a feasible solution. This ensures the process is highly efficient. Algorithm 2 Generate initial solution procedure. 1: function genInitSol(inputs, α, β, Tmax ) 2: initSol ← ∅ 3: feasible ←false 4: while not feasible do 5: newSol ←savingsHeuristic(inputs, α, β, Tmax ) 6: if isFeasible(newSol)then 7: feasible ←true 8: initSol ←newSol 9: end if 10: end while 11: return initSol 12: end function Algorithm 3 provides a detailed description of the novel savings heuristic employed in this study. Initially, the heuristic calculates the shortest paths and corresponding traversal times between all pairs of nodes and in the set of Vnodes using the Floyd-Warshall algorithm (Magzhan and Jani, 2013). This computation yields matrices P(representing the shortest-time paths between each pair of nodes) and T(representing the shortest traversal times between each pair of nodes), enabling the graph to be treated as complete. Subsequently, the heuristic generates an initial dummy solution (newSol) that considers one route per target arc (required or profitable arc). Thus, each route starts from the origin depot, traverses a required arc or a profitable arc, and continues towards 8 the destination depot. It is important to note that this dummy solution comprises two types of routes based on the arc visited: required routes and profitable routes. If any profitable route in this dummy solution violates the maximum time constraint (Tmax), the associated arc is eliminated from the solution as it cannot be reached with the current maximum time constraint. The next step involves computing the “savings” associated with a pair of arcs, representing the benefits of merging two routes. (The detailed procedure to compute the savings list (savingsList) will be presented below in Algorithm 4 and its associated discussion). Subsequently, an iterative routemerging process based on the savings list is initiated. At each iteration, the saving (ijSaving) is extracted from the savings list in a biased-randomised manner, along with its corresponding arcs (iArc and jArc). The algorithm checks various conditions: (i) the routes to which the two arcs belong are not identical; (ii) the two associated arcs are exterior arcs; and (iii) the merge of the two routes adheres to the maximum time constraint (Tmax). Here, an exterior arc in a route refers to an arc connected to the origin or destination depot through a path that does not include any required or profitable arc. Incorporating exterior arcs during the route-merging process allows for the exclusion of entire sections from these routes without forfeiting any assigned arc rewards. If the constraints are satisfied, the two routes are merged into a new route (newRoute) that traverses the path between the corresponding arcs. The merged route replaces the two merged routes, which are removed from the solution. Once the savings list is empty, the goal is to select as many profitable routes as possible while considering the number of vehicles available in the fleet. Thus, the profitable routes in the solution are sorted in descending order based on their rewards, and the routes that collect the lowest reward are removed from the solution taking into account the restricted number of vehicles (|K|) in the fleet. As long as the required routes can be visited within the fleet’s vehicle capacity, the solution is deemed feasible. Finally, the heuristic reconstructs the routes of the solution to connect the required and profitable arcs through the shortest paths matrix P. This way, the algorithm avoids the deadheading circuits problem commonly found in ARPs and minimises unnecessary travel time. Notably, the presented savings heuristic is capable of handling cases where profitable and required arcs are not mutually exclusive. In other words, vehicles can collect rewards from required arcs when such situations arise. Thus, the heuristic exhibits flexibility in managing scenarios where profitable and required arcs overlap. As outlined in Algorithm 4, for each pair of required or profitable arcs (i, j) and (k, l), we calculate the shortest times from the arc (i, j) to the destination depot and from the origin depot to the arc (k, l). Based on these values, we compute the associated savings using the equation sij,kl =T(j, n + 1) + T(0, k)−T(j, k). Notice that, this equation uses the shortest traversal times T. However, to account for both the travel times and the cumulative reward obtained by visiting both arcs, we have extended the notion of savings as follows: s′ ij,kl =α·sij,kl + (1 −α)·(rij +rkl) (12) The enriched saving, denoted by s′ ij,kl, incorporates the trade-off between travel times and the aggregated reward of the arcs rij +rkl. Here, α∈(0,1) is a tuning parameter that needs to be empirically adjusted, taking into account the heterogeneity of the target arcs in terms of rewards. Next, the savings computed are divided into two lists, namely, “required” and “profitable”, based on whether the arcs involved are required or not. These lists are sorted in descending order according to their associated enriched savings value. Lastly, the two lists are concatenated into a single savings list with the required elements first, followed by the profitable elements. This ensures that the heuristic prioritises merging routes that include required arcs first, guaranteeing that the required arcs can be visited by the available vehicles in the fleet. 9 Table 4: Computational results for the sets of instances D. p= 0 p= 0.25 p= 0.5 # Solved 27 27 27 # Opt 14 16 16 |K|= 2 Av. Gap 0.72 0.81 1.22 Av. Gap (Archetti et al., 2015) 1.02 1.06 1.94 Av. Gap∗0.72 0.81 1.22 Max. Gap 3.91 4.11 6.12 Max. Gap (Archetti et al., 2015) 5.40 10.68 12.42 Max. Gap∗3.91 4.11 6.12 # Solved 22 24 25 # Opt 16 16 17 |K|= 3 Av. Gap 1.34 1.15 1.85 Av. Gap (Archetti et al., 2015) 1.14 1.55 7.50 Av. Gap∗0.49 0.64 1.06 Max. Gap 6.95 6.79 15.11 Max. Gap (Archetti et al., 2015) 12.50 9.34 20.07 Max. Gap∗4.26 4.50 7.89 # Solved 16 21 22 # Opt 15 17 17 |K|= 4 Av. Gap 2.10 1.35 1.70 Av. Gap (Archetti et al., 2015) 2.00 1.23 2.91 Av. Gap∗0.18 0.30 0.33 Max. Gap 9.68 6.99 9.37 Max. Gap (Archetti et al., 2015) 10.98 9.27 22.07 Max. Gap∗2.89 3.40 3.65 Table 5: Computational results for the sets of instances G. p= 0 p= 0.25 p= 0.5 # Solved 27 27 26 # Opt 16 18 19 |K|= 2 Av. Gap 1.43 1.89 2.24 Av. Gap (Archetti et al., 2015) 0.73 1.04 0.87 Av. Gap∗1.43 1.89 2.24 Max. Gap 6.67 7.69 13.95 Max. Gap (Archetti et al., 2015) 4.00 8.33 7.35 Max. Gap∗6.67 7.69 13.95 # Solved 24 26 27 # Opt 17 18 19 |K|= 3 Av. Gap 1.51 1.60 1.68 Av. Gap (Archetti et al., 2015) 1.17 1.11 2.07 Av. Gap∗1.04 1.43 .68 Max. Gap 6.73 8.70 8.70 Max. Gap (Archetti et al., 2015) 7.69 9.11 12.20 Max. Gap∗5.32 8.70 8.70 # Solved 13 14 12 # Opt 12 11 8 |K|= 4 Av. Gap 4.01 3.25 6.39 Av. Gap (Archetti et al., 2015) 4.54 2.30 4.28 Av. Gap∗0.25 1.04 2.65 Max. Gap 13.77 15.36 25.26 Max. Gap (Archetti et al., 2015) 13.08 17.46 44.61 Max. Gap∗3.23 6.12 14.29 16 achieves the optimal solutions for class R, percentage gaps of 0.92%, 0.74%, and 0.28% for class D instances, and 1.79%, 1.40%, and 1.27% for class G instances. The computational times needed to reach these average gaps are 0.33 seconds, 0.14 seconds, and 2.14 seconds for class R instances, 160.8 seconds, 168.5 seconds, and 145.1 seconds for class D instances, and 103.1 seconds, 130.1 seconds, and 134.7 seconds for class G instances, respectively. These results highlight the strengths of our algorithm. It consistently delivers highly competitive solutions for problems with a smaller number of vehicles, and yields good-quality solutions even for instances with a higher number of vehicles. Moreover, our algorithm finds the best solutions in a low computational time, often significantly earlier than the maximum allowed time. This is particularly notable for class R instances, where optimal solutions are achieved in mere fractions of a second. For class D and class G instances, while the computational times are longer due to increased complexity, they remain efficient and well within acceptable limits. Lastly, notice that our BR-ILS was able to improve the lower bound solutions for some of the class D instances. This further establishes the competitiveness of the BR-ILS algorithm, particularly for instances where the optimal solution is known. In addition, our algorithm consistently outperforms the matheuristic proposed by Archetti et al. (2015), as indicated by lower average and maximum percentage gaps.              | K |                    Figure 2: Percentage gaps of our BR-ILS algorithm for the classes R, D and G. Lastly, Table 6 shows the instances of class T50, which are difficult to solve to optimality. However, our BR-ILS algorithm is able to consistently obtain high-quality solutions. Observe that its performance varies with the number of vehicles and the parameter p. The algorithm is particularly effective for a smaller vehicle count (|K|= 2), achieving more optimal solutions and lower average gaps. As the number of vehicles increases, achieving optimality becomes more 17 challenging, and the average gaps widen, especially when considering the upper bound comparisons. These results follow the trend analysed in the previous computational experiments. Lastly, it is worth noting that our BR-ILS was able to improve the lower bound solutions for 4 of the 60 class T50 instances. All instances with improved solutions involve scenarios with 4 vehicles, which highlights the limitation of the branch-and-cut algorithm for higher number of vehicles when compared with the BR-ILS algorithm. This shows that our approach is an effective and robust algorithm to solve the classic version of the TOARP. The detailed results obtained by our BR-ILS algorithm, including the updated upper and lower bounds, the best-found solutions, and the computational time required to achieve them, are available at: https://www.researchgate.net/publication/ 385913073_Benchmark_solutions_for_the_TOARP.The repository also includes the source code for the BR-ILS algorithm implementation. Table 6: Computational results for the sets of instances T50. p= 0 p= 0.5 # Solved 10 10 # Opt 0 5 |K|= 2 Av. Gap 0.83 0.38 Av. Gap (Archetti et al., 2015) 0.81 1.52 Av. Gap∗0.83 0.35 Max. Gap 1.70 1.05 Max. Gap (Archetti et al., 2015) 1.68 4.11 Max. Gap∗1.70 1.05 # Solved 10 10 # Opt 3 1 |K|= 3 Av. Gap 0.51 1.73 Av. Gap (Archetti et al., 2015) 0.78 3.15 Av. Gap∗0.51 1.51 Max. Gap 1.29 3.02 Max. Gap (Archetti et al., 2015) 3.13 5.69 Max. Gap∗1.29 3.02 # Solved 10 10 # Opt 1 0 |K|= 4 Av. Gap 4.54 2.46 Av. Gap (Archetti et al., 2015) 5.03 4.11 Av. Gap∗0.76 1.13 Max. Gap 7.61 5.40 Max. Gap (Archetti et al., 2015) 11.11 7.87 Max. Gap∗1.53 1.59 Figure 3 shows a summary of the performance of our algorithm across different numbers of vehicles, based on the data presented in Table 6. Similarly, the box plot displays the percentage gaps in those instances where the optimal solution is available. Observe that, our BR-ILS algorithm obtains percentage gaps of 0.60%, 0.80%, and 0.95% for class T50 instances. The average computational times needed to reach these solutions are 249.8 seconds, 285.1 seconds, and 217.4 seconds, respectively. Similar to the previous benchmark instances our algorithm consistently generates near-optimal solutions for a smaller number of vehicles. Furthermore, high-quality solutions are obtained for instances with a higher number of vehicles. Despite the high computational time, the results are still achieved well within the maximum time limit and underscore the scalability of the algorithm. This underscores the efficiency and quality of our BR-ILS algorithm in finding solutions even for the most challenging benchmark instances. Remarkably, it outperforms some of the best known solutions in the literature, making it a robust choice for solving TOARP problems. 18  | K |             Figure 3: Percentage gaps of our BR-ILS algorithm for the class T50. 7. Solving the TOARP with Different Origin and Destination To the best of our knowledge, there are no TOARP instances with different origin and destination depots. It would be possible to generate such instances from scratch; however, we would not be able to benchmark them against existing work. Thus, to validate the distinctive capability of our algorithm in solving scenarios where the start and end points are different depots, we have modified the set of TOP instances originally proposed by Chao et al. (1996). The adaptations made to align the TOP instances with the characteristics of the TOARP are as follows: •Starting from the nodes of the instances, we create a complete graph by generating pairs of arcs (i, j) and (j, i) with the same cost, corresponding to the Euclidean distance between nodes iand j. •For each arc (i, j) in the complete graph, we assign it to be either a target arc (required or profitable) or a traversing arc. Target arcs are assigned based on the optimal TOP solution, which is represented by a series of routes responsible for collecting rewards from the visited nodes. The arcs comprising the optimal routes will be assigned as target arcs. Arcs that are not target arcs are assigned as traversing arcs. •For each target arc (i, j), the corresponding arc is declared required (with probability p) or profitable (with probability 1 −p). The profit associated with the traversal of a profitable arc is defined as the reward of the ending node j. 19 By incorporating these modifications, we can compare the performance of our BR-ILS algorithm with the best-known solutions of the adapted TOP instances when p= 0. This is feasible because the aggregated reward of the profitable arcs has been computed based on the TOP optimal solutions. This process enables us to assess the effectiveness of our algorithm in solving problems that align with the original TOP definition, while considering the unique characteristics of the TOARP discussed in the previous section. Moreover, we can also conduct experiments by varying the probability pto control the ratio of required and profitable arcs in the instances. For our experiments, we introduce three different levels with p= 0, p= 0.25 and p= 0.5, which indicate the probability of target arcs being required or profitable. This allows us to examine how different ratios of required and profitable arcs impact the solution construction process and the resulting aggregated reward. The modified instances are available at: https: //www.researchgate.net/publication/385913073_Benchmark_solutions_for_the_TOARP. To illustrate this concept, we conducted an analysis using the p6.3.m instance. The instance was chosen randomly from one of the hardest sets to solve optimally in the benchmark. The optimal solution routes for the instance were obtained using the VNS approach proposed by Panadero et al. (2020), as there is no database available with the optimal solution routes. Initially, for p= 0, all target arcs are considered profitable, and the constructed routes traverse all profitable arcs, resulting in an aggregated reward of 1080.00. This solution aligns with the best-known solution for the TOP instance documented in the literature. As the probability pincreases to p= 0.25, some target arcs become required, leading to a reduction in the aggregated reward to 762.00 as fewer target arcs are profitable. The trend continues with p= 0.5, where additional target arcs are made required rather than profitable, resulting in an aggregated reward of 582.00. As the proportion of required arcs increases, the solution adapts by prioritising the required arcs and visiting the profitable arcs when possible. It is noteworthy that as the probability pincreases, the solution’s aggregated reward worsens as expected. However, the solution adapts to the changes in arc classification by collecting the highest possible reward from the profitable arcs within reach while ensuring required arcs are covered. Figure 4 shows the obtained solutions with p= 0 and p= 0.25. The required arcs are represented by red lines, while the profitable arcs are shown as blue lines. Moreover, the traversing arcs are depicted as black lines, and the origin and destination depots are marked as green points (which differentiates them from the other nodes). 8. Conclusions In this study, we proposed a novel BR-ILS algorithm for solving the TOARP, including both the classic single-depot version of the TOARP as well as an extended version allowing different origin and destination depots for the vehicles. Our algorithm incorporates a biased-randomised savings heuristic and an ILS framework to efficiently search for high-quality solutions. We evaluated the performance of the BR-ILS algorithm using benchmark instances from the TOARP and adapted instances from the TOP. The results demonstrated the effectiveness of our algorithm in finding competitive solutions for both problem domains. For the classic TOARP instances, our algorithm achieved noticeable results in very short computational times, with percentage gaps ranging from 0.00% to 1.79% compared to the optimal solutions. Notably, the algorithm’s performance was influenced by the number of vehicles, as the number of instances solved optimally decreased with an increasing number of vehicles. However, even in challenging instances, our algorithm consistently provided good-quality solutions. Specifically, our approach was able to outperform the best-known solution approaches in the literature 20 (a) Solution for the p6.3.m instance with p= 0. (b) Solution for the p6.3.m instance with p= 0.25. Figure 4: Solutions for the p6.3.m instance with different levels of p. 21 for 4 of the 60 hardest TOARP benchmark instances. It is important to note that in some cases, our approach was able to improve the lower bound while using only one-sixth of the computational time on a more powerful processor, which is between 5 to 11 times as powerful depending on the benchmark. Furthermore, by adapting TOP instances, we were able to demonstrate the algorithm’s ability to handle scenarios with different start and end points. This key difference allowed us to solve problems that closely resemble the original TOP definition while considering the unique characteristics of the TOARP. The results obtained when comparing with best-known solutions for the TOP instances confirmed the competitiveness and effectiveness of our algorithm. Some ideas for future work that can extend the current research are: (i) to consider the inclusion of uncertainty in travel times or rewards, which could involve extending the algorithm into a simulation-based heuristic (simheuristic) framework (Gruler et al., 2017); (ii) to utilise massively parallel execution leveraging one of the key advantages of biased-randomised algorithms – thus making it possible to obtain real-time or near-real-time solutions and enabling “agile” optimisation (do C. Martins et al., 2021); (iii) to introduce reinforcement learning components into the BRILS framework to handle dynamic scenarios where travel times or rewards may change based on contextual information (e.g., weather conditions, traffic congestion, resource availability); and (iv) to extend the BR-ILS algorithm to handle multiple conflicting objectives simultaneously, such as minimising travel times, maximising aggregated rewards, and reducing environmental impact. Declarations Funding: This work has been partially supported by the Spanish Ministry of Science (PID2022138860NB-I00, RED2022-134703-T) and the Horizon Europe program (SUN HORIZON-CL4-2022HUMAN-01-14-101092612). In addition, we would like to acknowledge the support provided by the Michael Smurfit Graduate Business School at University College Dublin. Conflicts of Interest: The authors declare no conflict of interest. References Agarwal, S. and Akella, S. (2022). The correlated arc orienteering problem. In Algorithmic Foundations of Robotics XV: Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics, pages 402–418. Springer. Archetti, C., Feillet, D., Hertz, A., and Speranza, M. G. (2010). The undirected capacitated arc routing problem with profits. Computers & Operations Research, 37(11):1860–1869. Archetti, C., Speranza, M. G., ´ Angel Corber´an, Sanchis, J. M., and Plana, I. (2014). The team orienteering arc routing problem. Transportation Science, 48(3):442–457. Archetti, C., ´ Angel Corber´an, Plana, I., Sanchis, J. M., and Speranza, M. G. (2015). A matheuristic for the team orienteering arc routing problem. European Journal of Operational Research, 245(2):392 – 401. Bianchessi, N., Corber´an, ´ A., Plana, I., Reula, M., and Sanchis, J. M. (2022). The profitable close-enough arc routing problem. Computers & Operations Research, 140:105653. Chao, I.-M., Golden, B. L., and Wasil, E. A. (1996). The team orienteering problem. European Journal of Operational Research, 88(3):464–474. 22 Corber´an, A., Eglese, R., Hasle, G., Plana, I., and Sanchis, J. M. (2021). Arc routing problems: A review of the past, present, and future. Networks, 77(1):88–115. de Armas, J., Keenan, P., Juan, A. A., and McGarraghy, S. (2019). Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics. Annals of Operations Research, 273(1):135–162. do C. Martins, L., Hirsch, P., and Juan, A. A. (2021). Agile optimization of a two-echelon vehicle routing problem with pickup and delivery. International Transactions in Operational Research, 28(1):201–221. Dominguez, O., Juan, A. A., De La Nuez, I. A., and Ouelhadj, D. (2016). An ils-biased randomization algorithm for the two-dimensional loading hfvrp with sequential loading and items rotation. Journal of the Operational Research Society, 67(1):37–53. Estrada-Moreno, A., Savelsbergh, M., Juan, A. A., and Panadero, J. (2019). Biased-randomized iterated local search for a multiperiod vehicle routing problem with price discounts for delivery flexibility. International Transactions in Operational Research, 26(4):1293–1314. Feillet, D., Dejax, P., and Gendreau, M. (2005). The profitable arc tour problem: Solution with a branch-and-price algorithm. Transportation Science, 39(4):539–552. Gruler, A., Quintero-Ara´ujo, C. L., Calvet, L., and Juan, A. A. (2017). Waste collection under uncertainty: A simheuristic based on variable neighbourhood search. European Journal of Industrial Engineering, 11(2):228–255. Ke, L. and Yang, W. (2017). Reformulation and metaheuristic for the team orienteering arc routing problem. In Advances in Swarm Intelligence: 8th International Conference, ICSI 2017, Fukuoka, Japan, July 27–August 1, 2017, Proceedings, Part II 8, pages 494–501. Springer. Magzhan, K. and Jani, H. M. (2013). A review and evaluations of shortest path algorithms. International Journal of Scientific & Technology Research, 2(6):99–104. Malandraki, C. and Daskin, M. S. (1993). The maximum benefit chinese postman problem and the maximum benefit traveling salesman problem. European Journal of Operational Research, 65(2):218–234. Panadero, J., Juan, A. A., Bayliss, C., and Currie, C. (2020). Maximising reward from a team of surveillance drones: a simheuristic approach to the stochastic team orienteering problem. European Journal of Industrial Engineering, 14(4):485–516. Reula, M. and Mart´ı, R. (2023). Heuristics for the profitable close-enough arc routing problem. Expert Systems with Applications, 230:120513. Riera-Ledesma, J. and Salazar-Gonz´alez, J. J. (2017). Solving the team orienteering arc routing problem with a column generation approach. European Journal of Operational Research, 262(1):14–27. Talbi, E.-G. (2009). Metaheuristics: from design to implementation. John Wiley & Sons. Vansteenwegen, P., Souffriau, W., and Van Oudheusden, D. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1):1–10. 23 Wang, K., Wu, Q., He, X., Hu, C., and Chen, N. (2022). Optimizing UAV traffic monitoring routes during rush hours considering spatiotemporal variation of monitoring demand. International Journal of Geographical Information Science, 36(10):2086–2111. Zhang, G., Jia, N., Zhu, N., Adulyasak, Y., and Ma, S. (2023). Robust drone selective routing in humanitarian transportation network assessment. European Journal of Operational Research, 305(1):400–428. 24