Introduction

The Orienteering Problem (OP) is a routing problem with profits inspired by the outdoor sport Orienteering. In a particular variant of Orienteering, the participants are given a set of locations, each associated with a reward. The participants aim to collect as many rewards as possible by visiting the defined locations within the given time budget. Similarly, the OP stands to maximize the sum of the collected rewards associated with the locations such that the tour cost does not exceed the given travel budget. The OP has been formally introduced in [1], although, the first approaches to solve the orienteering have been presented in [2], and since that, several approaches have been proposed [3][4][5][6].

The OP is a suitable problem formulation for data collection missions, where the utilized vehicles have a limited travel budget. Because visiting all locations is not feasible, the problem is to determine a subset of the most rewarding locations that can be visited within the given travel budget. Furthermore, we can exploit a non-zero communication range in a case where data can be retrieved from the locations remotely. Thus, we can save travel costs by col-Figure 1: Example of the CEOP solutions, where the color of the disk-shaped neighborhoods indicates the value of reward (low rewards are in the blue and highly rewarding locations are in the red). lecting data distantly and utilize the travel budget to collect more rewards. Because the reward can be collected arbitrarily within a disk-shaped neighborhood of each target locations, such a variant of the OP is referred to as the Close Enough OP (CEOP) [7,8], albeit it can also be found as the OP with Neighborhoods (OPN) [9][10][11]. An example of the CEOP instances is depicted in Fig. 1.

In this paper, we propose a new approach to the solution of the CEOP based on the Hopfield Neural Network (HNN) for the OP presented in [12] that is combined with the convex optimization approach of the Second-Order Cone Programming (SOCP). The recurrent HNN is usually used in the data reconstruction tasks, although it has been adapted to various routing problems [13,14]. The HNN for the CEOP is studied in [15], where an approach based on the discretization of the continuous neighborhoods is proposed, and the problem is solved as a variant of the Set OP [11,16].

The drawback of the Set OP based approach is in the pre-determination of the points of visits to the neighborhoods of the target locations that are determined independently on the final tour. We propose a generalization of the HNN, where the locally optimal data collection points are determined using the SOCP. Based on the empirical evaluation using the existing benchmarks for the CEOP, the proposed approach exhibits improved solutions quality compared to the previous HNN approach based on the solution of the discrete Set OP. Besides, the proposed SOCP-based HNN is compared with the state-of-the-art Greedy Randomized Adaptive Search Procedure (GRASP) [8]. The proposed HNN-based method seems to provide solutions with the competitive solution quality to the GRASP, but it is more computationally demanding.

The rest of the paper is organized as follows. A brief overview of the existing approaches to the CEOP is presented in Section 2. The CEOP is formally defined in Section 3. The utilized baseline HNN for the OP is described in Section 4 and the proposed SOCP-based improvements are introduced in Section 5. The evaluation results are reported in Section 6. The concluding remarks are discussed in Section 7.

Related Work

The Orienteering Problem (OP) belongs to the class of routing problems with profits motivated by data collection missions. The OP can be considered a combination of the two NP-hard problems, the Traveling salesman problem in finding the most cost-efficient tour, and the Knapsack problem in determining the most rewarding subset of the target locations. Thus finding an optimal solution is computationally demanding, and therefore, heuristics have been proposed, such as the S-algorithm, D-algorithm, and route improvement heuristic in [2], the Center of gravity heuristic in [1], the Four-phase heuristic [3], the Fivestep heuristic [4]. Besides, combinatorial meta-heuristics have been adopted to solve the OP, such as the Variable Neighborhood Search (VNS) [17] and the Greedy Randomized Adaptive Search (GRASP) [5]. Moreover, two sets of benchmark instances have been established based on the problems studied in [2,4]. In contrast to that, only a few approaches to the CEOP are reported in the literature: the Growing Self-Organizing Array (GSOA) [7], the VNSbased approach [11], and the GRASP-based method [8], that are overviewed in the rest of this section.

The GSOA [7,18] is an unsupervised learning method based on the Self-Organizing Map (SOM) [6,9,10]. The GSOA stands for an array of nodes representing the requested route. It is iteratively adapted towards the target locations by determining the closest point of the route to a randomly selected target. The node is added to the array at the closest point position, and it is adapted with its neighboring nodes towards the target location. The GSOA addresses the continuous optimization (of determining locations of visits to the neighborhoods) during the insertion of the node into the array when a point from which the data can be obtained is determined using the communication range.

A similar approach to address the continuous neighborhoods as in the GSOA is utilized in the GRASP-based solution of the CEOP proposed in [8]. The GRASP consists of two steps: construction and local search. In the construction step, a route is constructed by iteratively adding new locations according to an insertion heuristic until the route is unchanged. Afterward, the route is improved in the local search step, where data collection points are iteratively refined to shorten the travel cost allowing insertion of new target locations into the final route. The VNS-based approach [11] addresses the continuous optimization of the CEOP by discretizing the disk-shaped neighborhoods into a finite set of locations and solving the problem as the Set OP [16].

All the methods are reported to provide solutions of high quality, although they have particular drawbacks. The GSOA is a fast constructive heuristic utilized in many routing problems; however, once it converges to a stable state, the solution does not further improve. On the other hand, the VNS provides better quality solutions than the GSOA, but it is more computationally demanding. So far, the GRASP provides the solutions to the CEOP of the best quality in the shorter computational time than the GSOA.

In the current work, we investigate the Hopfield Neural Network (HNN) for the OP [12] in the solution of the CEOP. The first attempt to solve the CEOP by the HNN is presented in [15], where the disk-shaped neighborhoods are discretized, and the problem is solved as a variant of the Set OP, albeit the problem is referred as the OPN in [15]. The network is represented as the threedimensional matrix, where the third dimension represents discretized locations within the neighborhood. The objective of the network is to minimize a complex energy function that addresses the constraints of the CEOP. Once the network converges to a local minimum, a route is constructed from the network and further improved. Although the quality of the obtained solutions is relatively weak compared to the GSOA, VNS, and GRASP based heuristics, the expected advantage of the HNN is in the possible parallelization of the energy function computation and also in the potential to address sequence-dependent generalization of the routing problems. Therefore, we propose to address the solution quality of the HNN-based solutions of the CEOP by the deployment of the Second-Order Cone Programming (SOCP) in determining locally optimal distant locations of visits to the target locations. The HNN for the OP and the employed SOCP are thoroughly described in Section 4 and Section 5, respectively.

Problem Statement

The CEOP is a variant of the OP motivated by data collection missions, where the goal is to collect the most rewarding data from a set of target locations S, starting and ending at the predefined targets, while the traveled tour remains within the given travel budget T max . The targets S are rewarded by a score r i depending on the importance of the particular target, and data can be remotely collected within δ distance from the particular target location; thus, forming a disk-shaped neighborhood with the radius δ . The CEOP can be defined as follows.

Let S = {s s s 1 , . . . , s s s n } be a set of n target locations, where s s s i ∈ R 2 , and δ be a communication radius associated with every location s s s i ∈ S, except the start and end locations that are denoted s s s 1 and s s s n , respectively, since it is requested to visit precisely these locations. Each location is associated with the reward r i > 0, except s s s 1 and s s s n that are assigned with zero reward r 1 = r n = 0. The CEOP stands to determine a tour maximizing the sum of the collected rewards R, while the tour length does not exceed the given travel budget T max . Since the tour length is limited, only a subset of k locations S k ⊆ S can be visited. The tour visiting the subset S k of the targets can be described as a sequence of visits Σ = (σ 1 , . . . , σ k ), where 1 ≤ σ i ≤ n, ∀i = j : σ i = σ j , and σ 1 = 1, σ k = n, together with a set of waypoint locations P = (p p p 1 , . . . , p p p k ), p p p i ∈ R 2 , where each p p p i is within the communication radius δ of the corresponding location s s s σ i , i.e., p p p i − s s s σ i ≤ δ . The CEOP is defined as the optimization Problem 1, where p p p i − p p p j denotes the Euclidean distance between the locations p p p i and p p p j .

Problem 1 Close Enough Orienteering Problem (CEOP). maximize k,Σ,P R = ∑ k i=1 r σ i s.t. ∑ k−1 i=1 p p p i − p p p i+1 ≤ T max 2 ≤ k ≤ n p p p i − s s s σ i ≤ δ p p p 1 = s s s 1 , p p p k = s s s n

Hopfield Neural Network for OP

The herein proposed solution to the CEOP is based on the Hopfield Neural Network (HNN) for the OP presented in [12] that is briefly described in this section to keep the paper self-contained. The HNN consists of three main parts: the problem representation, the energy function, and the improvement heuristics, such as 2-Opt [19], the insertion and deletion heuristics. The HNN is conceptualized as a state matrix Φ ∈ R n,n+1 , where each cell denotes the continuous activation level Φ i, j ∈ [0, 1]. Each activation level Φ i, j is updated by the sigmoid activation function

Φ i, j = 1 1 + e −α(1)

with

α = ln(Φ i, j ) − ln(1 − Φ i, j ) − ∂ E ∂ Φ i, j ∆t (2)

where E is the energy function and ∆t is the time step. Each activation level Φ i, j is referred to as a state, and it denotes that the location s s s i is visited at the j-th position of the tour. If the value of Φ i, j is close to 1, then it is likely that the location s s s i is selected to be visited at the jth position. The start and end locations are requested to visit; hence the states Φ 1,1 and Φ n,n are forced to 1. The last column of Φ i,n+1 is used to calculate the reward of the tour. Thus, if the location s s s i is to be included in the route, the last column is set to 1, Φ i,n+1 = 1, otherwise Φ i,n+1 = 0.

The essential part of the HNN is the complex energy function E for which the second derivative w.r.t. the current state is used as the weights of the network. The aim of the network is to minimize the energy function designed to meet the constraints of the OP. The energy function for the OP [12] is

E = a 2 n ∑ i=1 n ∑ j=1 n ∑ h=1 h =i Φ i, j Φ h, j(3)+ b 2 n ∑ i=1 n ∑ j=1 Φ i, j − n 2(4)+ c 2 Γ n ∑ i=1 n−1 ∑ j=1 n ∑ h=1 s s s i − s s s h Φ i, j Φ h, j+1 − T max(5)+ d (2 − Φ 1,1 − Φ n,n )(6)+ e n ∑ i=1 Φ i,n+1 (1 − n ∑ j=1 Φ i, j )(7)− f n ∑ i=1 r i Φ i,n+1 ,(8)

where a, b, c, d, e, f are parameters of the network and

Γ(x) = x 2 if x ≥ 0 0 otherwise .(9)

The energy function E consists of six terms; each term is associated with the multiplication parameter and ensures a given constraint of the OP is met. The first term (3) associated with the parameter a penalizes multiple activated states in the same column to ensure only one location can be visited at the time. The second term (4) associated with the parameter b ensures the maximal number of activated states is less or equal to n. If the number is less than n, the activated states are consecutively repeated. The third term (5) penalizes routes that their traveled length exceeds the travel budget T max . The term (6) associated with the parameter d ensures that route starts and ends at the start location s s s 1 and end location s s s n , respectively. The next term (7) associated with the parameter e sets Φ i,n+1 = 1 if the location s s s i is included in the route. Finally, the last term ( 8) is used to maximize the sum of collected rewards.

Having the network representation and the energy function, the states of Φ are iteratively updated according to the activation function (1). A brief overview of how the representation and energy function is utilized in the solution for the OP follows.

First, the state matrix is initialized to random values, and parameters are initialized to predefined values. Then, a random row of Φ is selected, and all states of the row are updated according to the activation function (1). The selection and update are repeated until a local minimum is reached. The local minima occur when for any state Φ i, j the value of − ∂ E ∂ Φ i, j ∆t is less than a predefined threshold ϑ three times in succession. When a local minimum is reached, a route is constructed from the state matrix by selecting a state with the largest value for each column. Afterward, the local improvement by the 2-Opt [19] is applied to the route. If the traveled route does not violate the travel budget T max , the parameter f of the network is increased; otherwise, f is decreased to satisfy the length constraint. The locally improved route is further tweaked by utilizing the cheapest insertion heuristic as in Definition 1 and the deletion heuristic as in Definition 2, and thus more locations can be visited and more rewards can be collected. Definition 1. Location s s s insert to be inserted into the route at position j. s s s insert , j = argmax s s s i ∈S\S k ,s s s j ∈S k s s s i − s s s j + s s s i − s s s j+1 − s s s j − s s s j+1 r i .

Definition 2. Location s s s remove to be removed from the route s s s remove = argmax s s s i ∈S k s s s i − s s s i+1 r i .

The state matrix is then adjusted according to the improved route, and the process of finding a local minimum of the adjusted network is repeated for the predefined number of repetitions. Then, the parameters and the state matrix are reinitialized, and the process starts again. The whole process is repeated for the predefined number of iterations.

In [12], the authors state that the promise of the HNN is in combination with the traditional heuristics; hence we follow the combination of the HNN and heuristics in the solution of the CEOP. The proposed extensions of the HNN are described in the following Section 5.

Proposed Method

The essential modification of the HNN to solve the CEOP is the term (5) of the energy function associated with the parameter c. The original term penalizes routes that exceed the travel budget and considers the Euclidean distance between two target locations. Since we aim to solve the CEOP, the disk-shaped neighborhoods need to be considered in (5), and the proposed form of ( 5) is highlighted in the modified energy function:

E = a 2 n ∑ i=1 n ∑ j=1 n ∑ h=1 h =i Φ i, j Φ h, j + b 2 n ∑ i=1 n ∑ j=1 Φ i, j − n 2 (10)+ c 2 Γ n ∑ i=1 n−1 ∑ j=1 n ∑ k=1 n ∑ h=1 D(s s s k , s s s i , s s s j ) Φ k, j−1 Φ i, j Φ h, j+1 − T max (11) + d (2 − Φ 1,1 − Φ n,n ) + e n ∑ i=1 Φ i,n+1 (1 − n ∑ j=1 Φ i, j )(12)− f n ∑ i=1 r i Φ i,n+1 .(13)

The function D(s s s k , s s s i , s s s j ) denotes the estimate of the minimal distance between three locations s s s k , s s s i , s s s j using a determined waypoint location p p p i for the location s s s i as depicted in Fig. 2. We utilize the exact locations s s s j and s s s k instead of the waypoint locations p p p j and p p p k , since the HNN is robust, the effect of the term (11) in the energy function can be influenced by the parameter c. Furthermore, the estimate between three exact locations can be precomputed, and thus the computational demands are lower than using the waypoint locations.

s k p i s i s j

Figure 2: Estimation of the distance between three locations s s s k , s s s i , s s s j using the waypoint location p p p i of the location s s s i (dark gray).

The value of the function D can be determined by various approaches, such as a geometric approach, or an approach based on the solution of the Second-Order Cone Programming (SOCP). In the geometric approach, we can consider already established waypoint locations instead of the target locations. Then, the value function becomes D(p p p k , p p p i , p p p j ), and p p p i can be determined as the closest point to the line segment (p p p k , p p p j ). The geometric approach may seem conceptually suitable; however, it does not scale to more than three locations. Since we aim to utilize the studied HNN in the sequence-dependent problems with various lengths of the sequences in the future, we utilize a more general formulation of the SOCP. Thus the value of the function D together with the partial waypoint location is determined by the solution of the corresponding SOCP that is a convex optimization Problem 2 with affine constraints solved optimally by an optimization solver.

Problem 2 Second-Order Cone Programming (SOCP). min m−1 ∑ i=0 f f f i (14) s.t. f f f 2 i ≥ w w w T i • w w w i ∀i = 0, . . . , m(15)w w w i = x x x i+1 − x x x i ∀i = 0, . . . , m − 1 (16) x x x i − s s s i ≤ δ 2 ∀i = 0, . . . , m(17)x x x 1 = s s s 1 , x x x m = s s s m (18) x x x i ∈ R 2 ∀i = 0, . . . , m(19)

Problem 2 stands to determine a set of m waypoint locations x x x i such that the tour formed by the locations is of the minimal length. The objective function of Problem 2 is a linear function that stands to minimize the variable f f f (14), while the constraints represented by Equations ( 15) to (18) are met. The optimization problem consists of three variables f f f ∈ R m , w w w ∈ R m,2 , x x x ∈ R m,2 represented as vectors, where the variable x x x represents the set of waypoint locations x x x i ∈ R 2 . The variable w w w is an auxiliary variable that denotes the difference in coordinates between two consecutive waypoint variables (16), and it is used to calculate the length of the line segment between two waypoint locations (15). (17) ensures that each waypoint location x x x i is within the given communication radius δ from the respective location s s s i . ( 18) is employed to ensure the start and end waypoint locations correspond to the start and end locations, respectively.

Besides, the solution of the SOCP is also utilized in the improvement of the route after the application of the 2-Opt heuristic [19]. The proposed HNN-SOCP solver to the CEOP is overviewed in Algorithm 1.

Results

The proposed HNN with the SOCP-based modifications denoted as the HNN-SOCP has been empirically evaluated and compared with the Set OP based HNN [15] (further referred as the HNN) to observe how the continuous optimization affects the performance of the HNN-based solution of the CEOP. In addition, the GRASP method [8] is also considered in the herein reported evaluation study to show the performance of the HNN-based approaches in comparison to the currently best (to the best of the authors' knowledge) performing solver to the CEOP. The approaches are evaluated on five datasets: Set 64, and Set 66 of Chao sets [4] and Set 1, Set 2, and Set 3 of Tsiligirides sets [2]. Chao sets contain 40 problem scenarios with budgets ranging from 5 to 130, and Tsiligrides sets contain 49 problem scenarios with budgets varying from 5 to 110. For each problem instances, the communication radius δ is selected from δ ∈ {0.5, 1.0, 1.5, 2.0}. Due to the excessive number of problem instances, detailed results are reported only for five selected instances with the particular budget T max . The selected instances are with budgets slightly above the median value of budget ranges for a particular scenario because low budgets are quite constraining, and high budgets usually allow covering all locations.

The evaluated HNN-SOCP is implemented in C++1 using CPLEX solver [20] for the solution of the SOCP and the computational environment is a single-core of the Intel Core i5-4460 CPU running at 3.2 GHz. The results for the HNN are adopted from [15] and have been obtained by a different computational environment. Therefore, the computational times of the HNN [15] are adjusted by the factor 0.81 according to [21] to take into account different environments.

Since all the algorithms are randomized, the evaluation is performed among several trials, and results are reported using two performance indicators, %PDB and %PDM, and the maximal sum of collected rewards R obtained among the performed trials. The %PDB indicates the quality of solutions measured as the percentage deviation of the best solution R best obtained among performed trials to the reference solution R

ref , i.e., %PDB = R best −R ref R ref • 100%.

The %PDM measures the robustness of the found solutions determined as the percentage deviation of the mean of the sum of collected rewards R avg over the trials to the reference solution R ref , and it is computed as %PDM

= R avg −R ref R ref • 100%.

The reference value R ref is selected as the best solution found among all methods and performed trials. Due to the high number of instances, the reported results in Table 1 are aggregated values, where %PDB and %PDM denote the average value of %PDB and %PDM for the particular scenario with all selected travel budgets.

The particular methods have been parameterized as fol- the results is presented in Fig. 3 and Fig. 4. The reported results indicate that the proposed HNN-SOPC provides competitive results in almost half of the presented problems, and in one case, the HNN-SOCP even outperforms the GRASP. However, the computational demands of the HNN-SOCP are significantly higher than of the GRASP, as depicted in Fig. 4. Overall, the proposed HNN-SOCP provides higher quality solutions for the problems with larger radii since the neighborhoods overlap, and we can collect rewards from multiple locations by one visit.

The SOCP-based modifications overall improve the performance of the HNN-based approach in comparison to the original HNN to the CEOP [15] based on the explicit discretization of the disk-shaped neighborhoods. However, the HNN-SOCP struggles to address problems with small communication radii. The computational times of both HNN-based approaches are similar, although the HNN-SOCP is run with five times more iterations and two times more repetitions, and thus more solutions are processed. It is because the HNN-SOCP has less complex problem representation, and the network converges faster.

In this paper, we report the study of solving the Close Enough Orienteering Problem (CEOP) by the Hopfield Neural Network (HNN). The original HNN for the OP has been combined with the convex optimization approach of the Second-Order Cone Programming (SOCP) to tackle the continuous neighborhoods of the CEOP. The proposed HNN-SOCP has been empirically evaluated and compared with the GRASP-based approach and the former HNNbased approach with the explicit discretization of the diskshaped neighborhoods utilized as the baseline method. Although the HNN-SOCP does not outperform the GRASPbased solver, it significantly improves the existing HNN approaches to the CEOP in terms of the solution quality that becomes competitive to the GRASP.

In our future work, we aim to study the influence of the HNN parameters on the performance since the parameters are an essential part of the HNN. Besides, we also aim to utilize the HNN, particularly the possibility of the parallelization of the energy function, in the solution of the multi-vehicle and sequence-dependent routing problems.