A novel GRASP solution approach for the Orienteering Problem

Abstract

The Orienteering Problem (OP) is a well-known variant of the Traveling Salesman Problem. In this paper, a novel Greedy Randomized Adaptive Search Procedure (GRASP) solution is proposed to solve the OP. The proposed method is shown to outperform state-of-the-art heuristics for the OP in producing high quality solutions. In comparison with the best known solutions of standard benchmark instances, the method can find the optimal or the best known solution of about 70 % of the instances in a reasonable time, which is about 17 % better than the best known approach in the literature. Moreover, a significant improvement is achieved on the solution of two standard benchmark instances.

1 Introduction

The Orienteering Problem (OP) is a well-known variant of the Traveling Salesman Problem (TSP). The problem is inspired from an outdoor game usually played in mountainous or forested areas, where a set of checkpoints (landmarks) is available. Each checkpoint is associated with a profit and can be visited at most once. Within a predefined time limit, a contestant starts from the origin, visits a subset of the checkpoints, and finishes at the destination. Since it may not be possible to visit all the checkpoints, the objective in the OP is to collect the maximum possible profit by visiting some preferred checkpoints.

The OP is an NP-hard problem (Laporte and Martello 1990), which was originally introduced by Tsiligirides (1984). This problem arises in many real-world applications, including athlete recruiting (Chao et al. 1996b), technician routing (Tang and Miller-Hooks 2005), and tourist trip planning (Vansteenwegen et al. 2009).

Due to its NP-hardness, the branch-and-bound (Laporte and Martello 1990; Ramesh et al. 1992) and branch-and-cut (Fischetti et al. 1998; Gendreau et al. 1998a) exact algorithms, which are proposed to solve the problem to optimality, are usually time consuming. Therefore, most researches have focused on heuristic approaches. Among these heuristics, the most successful approaches, which have been recently proposed, include the Tabu Search heuristic (TS) (Gendreau et al. 1998a), Ant Colony Optimization (ACO) (Schilde et al. 2009), 2-Parameter Iterative Algorithm (2-PIA) (Silberholz and Golden 2010), and GRASP¹ with Path Relinking (GRASP-PR) (Campos et al. 2014). For a comprehensive review of the OP and its solutions, the reader is referred to the recent surveys by Vansteenwegen et al. (2011), Archetti et al. (2014), and Gavalas et al. (2014).

GRASP is a metaheuristic algorithm commonly applied to combinatorial optimization problems. In this algorithm, successive constructions of greedy randomized solutions are followed by iterative improvements through a local search. In this paper, we reconsider the GRASP solution approach introduced by Campos et al. (2014) to develop a novel GRASP heuristic method for the OP, which is shown to be competitive with the state-of-the-art.

The paper is organized as follows. The formal definition of the problem and one of its mathematical integer linear formulations are described in Sect. 2. Section 3 is devoted to the description of the proposed GRASP method for solving the OP. Various experimental results are presented in Sect. 4, the paper ends with some concluding remarks in Sect. 5.

2 Problem description and formulation

The OP can be modeled on a complete graph $G=(V,E)$ where $V = \{0, 1, \cdots , n, {n+1}\}$ is the set of vertices in G, and $E = \{(u,v)|u$, $v \in V\}$ represents the set of edges. Vertices 0 and ${n+1}$ are the origin and the destination points, respectively, while vertices 1 to n are the potential checkpoints. $V_0 = V \setminus \{0,{n+1}\}$ represents the checkpoint set. A travel time, $t_{uv}$, between each pair of vertices $(u,v) \in E$ is given, and a profit $p_v$ is assigned to each vertex $v \in V$.

A solution to the problem is a path that begins from vertex 0, visit a subset of vertices in $V_0$, and ends at vertex $n+1$. Each vertex in the subset must be visited at most once, and the time taken to visit the vertices of the solution cannot exceed $T_{max}$. The aim of the OP is to collect the maximum profit from the visited vertices.

For a formal definition, the following integer programming formulation of the problem has been presented (Vansteenwegen et al. 2011).

$$\begin{aligned}&Maximize&&\nonumber \\&\qquad \qquad \qquad \sum _{i = 1}^{n}\sum _{j = 1}^{n+1} p_i x_{ij},&\end{aligned}$$

(1)

$$\begin{aligned}&Subject\ to&&\nonumber \\&\qquad \qquad \qquad \sum _{i = 1}^{n+1} x_{0i} = \sum _{i = 0}^{n}x_{i(n+1)} = 1,&\end{aligned}$$

(2)

$$\begin{aligned}&\sum _{i = 0}^{n} x_{iv} = \sum _{j = 1}^{n+1}x_{vj} \le 1;&v \in \{1,2,\cdots ,n\}, \end{aligned}$$

(3)

$$\begin{aligned}&\sum _{i = 0}^{n}\sum _{j = 1}^{n+1} t_{ij}x_{ij} \le T_{max},&\end{aligned}$$

(4)

$$\begin{aligned}&1 \le u_i \le n;&i \in \{1,2,\cdots ,n\}, \end{aligned}$$

(5)

$$\begin{aligned}&u_i - u_j + 1 \le (1-x_{ij})n;&i,j\in \{1,2,\cdots ,n\}, \end{aligned}$$

(6)

$$\begin{aligned}&x_{ij} \in \{0,1\};&i,j \in \{1,2,\cdots ,n\}, \end{aligned}$$

(7)

$$\begin{aligned}&u_i \in \mathbb {Z}^+;&i \in \{1,2,\cdots ,n\}. \end{aligned}$$

(8)

In this formulation, two sets of decision variables x and u are available. $x_{ij} = 1$ if a visit to vertex i is followed by a visit to vertex j, and 0 otherwise; $u_i$ is equal to the position of vertex i in the solution path.

The objective function (1) is to maximize the total profit of the visited vertices. Constraint 2 ensures that the path starts at vertex 0 and ends at vertex $n+1$. Constraint 3 ensures that the path is connected and each vertex is visited at most once. Constraint 4 ensures that the path meets the time budget. Finally, Constraints 5 and 6 ensure that there are no subtours.

3 A novel GRASP heuristic for solving the OP

GRASP (Feo and Resende 1995) is a multi-start metaheuristic commonly used for solving combinatorial optimization problems. In each iteration, a solution is generated by applying two phases: a construction and a local search. The best solution of all iterations is kept as the result.

The construction phase basically starts with an empty solution as its first partial solution. For each partial solution, a candidate list of elements that can extend the partial solution to another feasible solution is created. This list is then restricted to more eligible candidates by an evaluation function. Next, a random candidate is selected from the list and the partial solution is extended by that candidate. The candidate list is then updated for the new partial solution and when there are no candidate elements that can extend the last constructed partial solution, the construction phase stops. Finally, the quality of the constructed solution is improved through a local search.

Campos et al. (2014) proposed a GRASP with path relinking to solve the OP. In this section, we reconsider their work and propose a novel GRASP heuristic for the OP, which is competitive with GRASP using path relinking and also competitive with the state-of-the-art. In what follows the proposed heuristic approach is denoted by GRASP-SR (GRASP with Segment Remove).

In this section, we represent each OP solution path r as a sequence of vertices $<r[0]=0,r[1],\cdots ,r[l]=n+1>$, where $l+1$ is the number of visited vertices of the graph, denoted by |r|. In addition, the total profit and travel time of path r are denoted by $P_r$ and $T_r$, respectively.

The GRASP-SR algorithm is demonstrated in Algorithm 1. This algorithm consists of a construction phase (Lines 2–3) followed by a local search (Line 5), which are described in the following two subsections.

3.1 Our GRASP construction method

Our construction method starts with the path $r = <r[0]=0,r[l]={n+1}>$ ($l = |r|-1$), which goes directly from vertex 0 to vertex ${n+1}$. This path is considered as the current path and we try to improve its quality by successive insertion of new vertices into the path. New vertices are added by function AddVertex() as follows.

Consider CL as the candidate list of paths, which are better in quality than the current path. At the beginning, this list is empty (Line 12). Each vertex $w \notin r$ is inserted in the best position of r (i.e., the one that produces the minimum path travel time) without changing the relative order of the vertices in the current path (Lines 16–17). If the new path $r'$ is feasible, it is added to the candidate list (Lines 18–19); otherwise, for each position $0<i<l+1$ in $r'=<r'[0],\cdots ,r'[i],\cdots ,r'[j],\cdots ,r'[l+1]>$, the position $i \le j < l+1$ is found (if possible), such that $j-i$ is minimal and the path $r'' = <r'[0],\cdots ,r'[i-1],r'[j+1],\cdots ,r'[l+1]>$ obtained by removing the vertices from position i to j of $r'$ is feasible.² If $P_{r''} > P_r$, $r''$ is a better solution than r, and it is added to the candidate list, but if $P_{r''} = P_r$, $r''$ is added to the candidate list if its travel time is shorter than the travel time of r (Lines 21–30). The total time complexity of constructing the candidate list is $O((n-l)l)$.

If no improvement is possible, the CL becomes empty and the function returns False, showing no improvement is possible; otherwise, the maximum profit improvement of the paths is considered among the candidate list. The candidate list is restricted to the paths having an improvement within the fraction $\alpha = 0.2$ of this value. A discussion about the adjustment of this parameter is presented in Appendix 1.

$$\begin{aligned} best= & {} Max \{P_i - P_r | i \in CL\} \end{aligned}$$

(9)

$$\begin{aligned} RCL= & {} \{i | i \in CL ~and~ P_i - P_r \ge 0.2 \times best\} \end{aligned}$$

(10)

Next, an element of the RCL is randomly selected and considered as the new current path. To reduce the length of this path, the 2-opt improvement mechanism is applied to the path and then the function returns True (Lines 31–36).

The process of adding new vertices by calling AddVertex() is repeated until no improvement is possible (Lines 3–4). The total time complexity of each improvement is $O((n-l)l + l^2)$, which is proportional to the number of vertices in the path.

The proposed construction method is similar to that of Campos et al. (2014) with the difference that when it is not possible to directly insert a vertex into the path, we try to remove a segment of the path to make space for the insertion of the new vertex. Thus, the proposed construction method is more general than the construction method of Campos et al. (2014) with the same overall time complexity.

3.2 Local search

The construction method of Campos et al. (2014) is followed by a two-phase local search. The first phase is based on some sequential one-to-one exchanges between the vertices in the path and the not less profitable vertices outside the path. Since these one-to-one exchanges may make space for the insertion of some new vertices into the path, the second phase is devoted to the insertion of these new vertices.

The proposed construction method contains both aforementioned local searches in its process. One-to-one exchanges is equivalent to the insertion of a vertex along with the removal of a segment of length one and the second phase is equivalent to the insertion of a vertex without any segment removal.

We have implemented another simple local search to improve the constructed path. This local search is applied by the LocalSearch() function, which works as follows.

For each vertex $w \in r\setminus \{0,{n+1}\}$, remove the vertex from the path and apply the 2-opt optimization to the path. The resulting path is then improved by the construction method. In the construction method, w is excluded from the improved path (Line 15). If the best path constructed by this way is better than the original path, it is selected as the next path and the function returns True; otherwise, the function returns False, showing that no improvement is possible by the local search. This process is continued until no further improvement is possible.

Although this final local search increases the total time complexity of each improvement to $O((n-l)l^2 + l^3)$, our experimental results show that GRASP-SR is competitive with the state-of-the-art in terms of both performance and run-time.

3.3 Example

To clarify the proposed algorithm, the algorithm is traced on the first instance of the p64 benchmark instances described in Sect. 4.1. The coordinates and the profits of the vertices required for following the example are given in Table 1. In this example, $T_{max}$ is 15 and vertices 0 and 1 are the starting and the finishing points, respectively.

Table 1 The coordinates and the profits of the required vertices of the first instance of p64 benchmark instances

Since the proposed algorithm is a randomized algorithm, each run of the program may produce a different result. The following is an example run of the algorithm on this problem. At first, the paths constructed by inserting vertices 9, 41, 3 and 53 in their best positions are randomly selected in sequence. The constructed feasible path after these insertions is

$$\begin{aligned}&<0,\underline{3,9,41,53},1>&(T = 14.99,P = 60). \end{aligned}$$

Inserting vertex 33 in its best position, results in an infeasible path. However, removing the segment containing vertices 3 and 9, makes the path feasible and still more profitable. This path is the next randomly selected path from the candidates list pool.

Similarly, vertices 5 and 19 are added to the path as follows.

It is seen that the insertion of vertex 5 is immediately improved by its replacement with vertex 19, which is more profitable than vertex 5. Since there is not any new profitable insertion with segment removal, the construction phase is finished.

Next, vertices 19, 33, 41 and 53 are independently removed from the constructed path and the possibility of new profitable insertions is checked for each of them. For this run of the program, removing vertex 41 produced the best result as follows.

This path cannot be further improved by the local search. As the results in Table 2 show, this is the best solution path for this instance.

4 Experimental results

In this section, the experimental results on OP standard benchmark instances are presented. GRASP-SR was implemented in C++ and tests were run on an Intel Core i7 with a 3.4 GHz CPU.

Two configurations of GRASP-SR are used in subsequent sections. In the first configuration, GRASP-SR is replicated 10 times on each instance. In each replication, 500 solutions are generated and the best of these solutions is returned. Therefore, in this configuration we have 5000 iterations to generate 5000 solutions. The output of our method for this configuration is described as follows:³

Best $^n$	The best solution and the number of times it was obtained.
Avg.	The average of the solutions.
Worst $^n$	The worst solution and the number of times it was obtained.
Sec.	The time in seconds in which the best solution was found for the first time.
#Iter.	The iteration number in which the best solution was found for the first time.
size	The number of visited vertices in the best solution path.

For the second configuration, the best solution obtained during the time limit of 2 min is considered. Column 2-min. corresponds to this configuration in the result tables. This configuration is used to show that our approach is competitive with the state-of-the-art, even if the time is restricted.

The first benchmark instances for this problem was proposed by Tsiligirides (1984), which consists of instances with the number of vertices ranging from 21 to 33. Since most of the current methods are able to solve these small instances to optimality, the corresponding results are not presented.

GRASP-SR was tested versus the best methods proposed in the literature on two standard benchmark problem sets. The results are presented in the following subsections.

Table 2 GRASP-SR in comparison with the ACO and GRASP-PR approaches on p64 instances

4.1 Experimental results on p64 and p66 instances

The problems in the first set are graphs of size 64 and 66 vertices proposed in Chao et al. (1996a), called p64 and p66 instances, respectively. The two methods presented the best results for these instances are the ACO (Schilde et al. 2009) and GRASP with Path Relinking (GRASP-PR) (Campos et al. 2014), which were run on a Pentium 4D with a 3.2 GHz CPU and an Intel Core i5 with a 3.2 GHz CPU, respectively.

The results comparing our method with these methods on the p64 and the p66 instances are presented in Tables 2 and 3. The ACO, GRASP-PR, and there hereby proposed GRASP-SR method were repeated ten times on each instance, and for each method, the best and the worst results of the 10 runs (and only the best if both are the same), and the time in which the best result of the 10 runs was found are reported in columns Value and Sec., respectively.

Comparing the results of GRASP-SR with the ACO and GRASP-PR shows that GRASP-SR is the only method that was able to solve all the p64 instances to the best known solutions in all its runs. On the other hand, Table 3 shows that the ACO and GRASP-PR generated the best results on the p66 instances. Although there are two instances for which our method did not produce the best result in all its runs, the best result was obtained, in at least half of the runs.

The computation times needed for solving these instances show that all the three methods can easily find the best results for these instances and are competitive with each other.

4.2 Experimental results on TSP-based benchmark instances

A larger set of benchmark instances was proposed in Fischetti et al. (1998) based on the TSPLIB 2.1 instances (Reinelt 1991). In this set, the TSP problems with up to 400 vertices are considered and converted to OP instances as follows. For each instance, the distance time limit is selected as $\lfloor \dfrac{Opt(P)}{2} \rfloor$, where Opt(P) is the length of the shortest Hamiltonian tour for the problem. The first vertex is considered as the origin and destination point (vertex $0 =$ vertex ${n+1}$), and then according to the following rules each vertex of the TSP instance is assigned a profit value.

Generation 1:	$p_i = 1$	$i=0,..,n$, $p_{n+1}=0$
Generation 2:	$p_i = [1 + (7141 \times i+73)]~mod~(100)$	$i=0,..,n$, $p_{n+1}=0$
Generation 3:	$p_i = 1+\lfloor \dfrac{99 \times t_{0i}}{\theta } \rfloor$	$i=1,..,n$, $p_0 = p_{n+1} = 0$,
		$\theta = \max _{v \in V_0} t_{0v}$

To the best of the authors’ knowledge, there are only three methods that have been tested on these benchmark instances. Silberholz and Golden (2010) reported the results for the Tabu Search heuristic (TS) proposed by Gendreau et al. (1998b) and for their 2-Parameter Iterative Algorithm (2-PIA), running them on an Intel Pentium 4D with a 3.2 GHz CPU.

Table 3 GRASP-SR in comparison with the ACO and GRASP-PR approaches on p66 instances

The third method is GRASP-PR (Campos et al. 2014), which used a different distance function and also different rules for generating the profits for these benchmark instances in comparison with Fischetti et al. (1998). According to our experimental results, the differences are as follows: Both Fischetti et al. (1998) and Campos et al. (2014) used the time distances $t_{ij}$ as described in Reinelt (1991), but with different approaches to cast the real returned values to an integer. Campos et al. (2014) truncated the values while Fischetti et al. (1998) rounded the values. Additionally, the $t_{ij}$ values used for computing the profit values in Generation 3 of Campos et al. (2014) were not casted to integer values. According to the mentioned time distance evaluations, the following rules were used in Campos et al. (2014) to generate the profits for the benchmark instances.

Generation 1:	$p_i = 1$	$i=0,..,n$, $p_{n+1}=0$
Generation 2:	$p_i = [1 + (7141 \times (i+1)+73)]~mod~(100)$	$i=0,..,n$, $p_{n+1}=0$
Generation 3:	$p_i = 1+\lfloor \dfrac{99 \times t_{0i}}{\theta } \rfloor$	$i=0,..,n$, $p_{n+1} = 0$,
		$\theta = \max _{v \in V_0} t_{0v}$

Our detailed experimental results on these benchmark instances are presented in Appendix 2. The proposed GRASP-SR is compared with the TS and 2-PIA heuristics in Tables 7, 8 and 9 and is compared with GRASP and GRASP-PR heuristics in Tables 10, 11 and 12. In these tables, column BC corresponds to the exact Branch-and-Cut method proposed by Fischetti et al. (1998). The time limit of 5 h was considered for BC and for the instances that this time limit was exceeded before returning the optimal solution, the best available solution was reported. The value for running time of these instances was reported as “t.l.”.

Although our GRASP-SR method with the first configuration almost outperforms the solutions of other heuristic methods in the literature, it takes more time to reach its best result. Therefore, it was decided to consider our configuration with the time limit of 2 min to have a better comparison of the proposed method versus others. The results summary for this configuration is reported in Tables 4 and 5.

Table 4 GRASP-SR in comparison with the TS and 2-PIA approaches on the TSP-based benchmark instances

Table 5 GRASP-SR in comparison with GRASP and GRASP-PR approaches on the TSP-based benchmark instances

Each entry in the tables indicates the number of instances for which a better solution was found by the method associated with its row as compared with the method associated with its column. The row named Optimal corresponds to the number of instances for which each method could find the optimal solution or a solution equal or better than the best known solution. Finally, the last row, named optimal(5000), reports the number of instances for which our GRASP-SR method with the first configuration could find the optimal solution or a solution equal or better than the best known solution. As an example, considering the Generation 3 instances, the 2-PIA outperforms our GRASP-SR in 6 instances, while GRASP-SR outperforms 2-PIA in 22 instances. Furthermore, 2-PIA and GRASP-SR found 13 and 28 optimal or best known solutions, respectively.

The results show that GRASP-SR almost outperforms all the mentioned state-of-the-art heuristics. GRASP-SR with the time limit of 2 min outperforms the TS, 2-PIA, GRASP and GRASP-PR in 94, 71, 83 and 46 instances, respectively and performs worse in only 6, 10, 3 and 10 instances. In other words, the method outperforms the TS, 2-PIA, GRASP, and GRASP-PR in 75, 56, 69 and 38 percent of the instances and performs worse than them in only 5, 8, 3, and 8 percent of the instances.

Moreover, the proposed algorithm could find the optimal or best known solution of about 70 % of the instances with only 2 min of computation time for solving each instance. The TS, the 2-PIA, GRASP and GRASP-PR could find about 22, 37, 29 and 53 percent of the optimal or best known solutions, respectively.

According to Table 8, for problem pr226 of the Generation 2 instances, Silberholz and Golden (2010) found a solution of 6641, better than the solution of 6615 obtained within 5 h of computation by Fischetti et al. (1998). GRASP-SR improved the solution to 6662 in less than a second. For problem pr299 of this generation, we have obtained a solution of 9173 in about 100 min, which is better than the solution of 9,161 obtained within 5 h of computation by Fischetti et al. (1998). For this instance, the proposed algorithm could also find a solution of 9165 in less than 2 min of computation time, which is also better than the best know solution for the problem. The routes corresponding to these new solutions are reported in the footnote of Table 8.

5 Conclusions

In this paper, a novel GRASP solution was proposed for the OP. Being able to find the optimal or best known solution of about 70 % of the benchmark instances, which is about 17 % more than the achievement of the best known heuristic approach in the literature, the proposed algorithm outperforms the state-of-the-art heuristic methods. In addition, the method improved the solution quality of two standard benchmark instances. In future studies, the proposed method is expected to be rather simply and effectively applicable to similar routing problems.

Appendices

Appendix 1: GRASP-SR parameter selection

In the construction phase of GRASP-SR (Sect. 3.1), the candidate list was restricted to the paths having an improvement within the fraction $\alpha = 0.2$ of the profit gained through the most profitable path in the candidate list. Campos et al. (2014) presented some experiments to show that the value of 0.2 is a good choice for their work. In this appendix, we show that this value is also a good choice in this work.

We considered the 48 TSP-based problem instances of Fischetti et al. (1998) having no more than 100 vertices (16 instances in each Generation). GRASP-SR was run for different values of $\alpha$ (0, 0.2, 0.4, 0.6, 0.8, 1.0) 100 times on each instance and the best solution of these 100 runs were kept for each instance. All the results were obtained in less than 2 min. For each value of the parameter $\alpha$, Table 6 shows the average deviation of the solutions with respect to the optimal solutions (Dev.) and the number of optimal solutions that GRASP-SR with the given parameter has been able to find (Optimal).

The results show that when $\alpha$ is equal to 0 or 0.2, a larger number of instances can be solved to optimality. Additionally, when $\alpha$ is set to 0.2, the smallest average deviation of the results from the optimal solutions is obtained.

Table 6 Effect of different $\alpha$ values on the results of GRASP-SR

Appendix 2: Detailed results on the orienteering problem

In this section, detailed results for the TSP-based benchmark instances are presented (Tables 7,  8,  9,  10,  11 and  12). The description of the tables provided in this section was presented in Sect. 4. In addition, the values in bold indicate the best solution among the solutions of the reported exact and heuristic approaches.

Some additional notes should be considered. As Silberholz and Golden (2010) mentioned, herein the value of $T_{max}$ has been corrected for problem gr229 to 67,301, which was incorrectly listed as 1765 in Fischetti et al. (1998). The correct value of $T_{max}$ for problem lin318 is 21,015, but since the value of 21,045 has been used in other works, we also used this value for our experimental results. Moreover, the profit values produced by Campos et al. (2014) for the Generation 3 instances does not contain the profit value of 100 for the instances rat99, kroc100, kroe100, pr124, and krob150. Due to floating-point precision errors, for the farthest vertex from the origin of these instances, the value of 99 has been produced instead of 100. It influenced our results for instances rat99 and kroe100, resulting in a value one more than the optimal solutions reported by Campos et al. (2014). Therefore, the same profit values were used as used in Campos et al. (2014) for a fair comparison.

Table 7 Detailed results of GRASP-SR in comparison with the exact Branch-and-Cut (BC) (Fischetti et al. 1998), TS (Gendreau et al. 1998b), and 2-PIA (Silberholz and Golden 2010) approaches on Generation 1 of the TSP-based benchmark instances

Table 8 Detailed results of GRASP-SR in comparison with the exact Branch-and-Cut (BC) (Fischetti et al. 1998), TS (Gendreau et al. 1998b), and 2-PIA (Silberholz and Golden 2010) approaches on Generation 2 of the TSP-based benchmark instances

Table 9 Detailed results of GRASP-SR in comparison with the exact Branch-and-Cut (BC) (Fischetti et al. 1998), TS (Gendreau et al. 1998b), and 2-PIA (Silberholz and Golden 2010) approaches on Generation 3 of the TSP-based benchmark instances

Table 10 Detailed results of GRASP-SR in comparison with the exact Branch-and-Cut (BC) (Fischetti et al. 1998), GRASP and GRASP-PR(Campos et al. 2014) approaches on Generation 1 of the TSP-based benchmark instances

Table 11 Detailed results of GRASP-SR in comparison with the exact Branch-and-Cut (BC) (Fischetti et al. 1998), GRASP and GRASP-PR(Campos et al. 2014) approaches on Generation 2 of the TSP-based benchmark instances

Table 12 Detailed results of GRASP-SR in comparison with the exact Branch-and-Cut (BC) (Fischetti et al. 1998), GRASP and GRASP-PR(Campos et al. 2014) approaches on Generation 3 of the TSP-based benchmark instances