{'fraction_non_alphanumeric': 0.03609065973726, 'fraction_numerical': 0.012559549588566478, 'mean_word_length': 4.546437149719776, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Solving the clustered traveling salesman problem with d-relaxed priority rule

The Clustered Traveling Salesman Problem with a Prespecified Order on the Clusters, a variant of the well-known traveling salesman problem is studied in literature. In this problem, delivery locations are divided into clusters with different urgency levels and more urgent locations must be visited before less urgent ones. However, this could lead to an inefficient route in terms of traveling cost. This priority-oriented constraint can be relaxed by a rule called d-relaxed priority that provides a trade-off between transportation cost and emergency level. Our research proposes two approaches to solve the problem with d-relaxed priority rule. We improve the mathematical formulation proposed in the literature to construct an exact solution method. A meta-heuristic method based on the framework of Iterated Local Search with problem-tailored operators is also introduced to find approximate solutions. Experimental results show the effectiveness of our methods.


Introduction
The Traveling Salesman Problem (TSP) is one of the most studied optimization problems. Its objective is to find an optimal vehicle route in order to visit a given set of locations. In the TSP, random descent [19].
Nodes in TCTSP are now partitioned into two kinds of subsets: clusters and tabu node sets; exactly one node in each tabu node set has to be visited and the nodes within a same cluster are visited consecutively. The TCTSP can model a class of telemetry tracking and command (TTC) resources scheduling problem. Its goal is to efficiently schedule the TTC resources in order to enable the satellites to be operated normally in their designed orbits. Two metaheuristics combined with path relinking were proposed to solve the problem: Ant Colony Optimization (ACO) and GRASP.
Despite its potential importance, the number of studies on the CTSP-d is quite scarce. To the best of our knowledge, the first works on the problem are [4,5]. The CTSP-d was also mentioned in Chapter 14 of [6]. In [5], the authors introduced the problem and its applications. They also derived worst-case bounds for the CTSP-d with respect to the classical TSP and were able to show that the bounds are tight. The problem and its several extensions were formulated as mixed integer programs in [4] where HTSP instances with only 30 or so nodes were solved to optimality using CPLEX. The lack of efficient solution methods and further analysis on the d-relaxed priority rule on larger instances brings strong motivation for this research.
The contributions of this research are as follows. First, we improve the Mixed Integer Programming (MIP) model introduced in [4] to propose an exact method that can solve small and medium instances. We tested it on instances up to 50 nodes. Secondly, we propose the first metaheuristic to efficiently deal with large instances up to 200 nodes. Our metaheuristic combines the ideas of Greedy Randomized Adaptive Search Procedure (GRASP), Iterated Local Search (ILS) and Variable Neighborhood Descent (VND) proposed in [16] with problem-tailored operators. More precisely, we use additional structure data that allow to check the feasibility of local search moves w.r.t the d-relaxed priority rule in O (1). And finally, computational results on different types of instances give insights on the performance of the methods, as well as the trade-off between the traveling cost and the priority.
The remainder of the paper is organized as follows. We discuss Mixed Integer Programing (MIP) formulations for the problem in Section 2. A metaheuristic is developed in Section 3.
Computational experiments are presented in Section 4. And finally, Section 5 concludes our work.

Formulations
In this section, we formulate the CTSP-d as a Mixed Integer Programming (MIP). As proposed in the formulation of [4], we use two types of variables: (i) real variables s i representing the arrival time of the vehicle at node i; (ii) binary variables x ij equal to 1 if vehicle travels from i to j, to 0 otherwise. Then, the CTSP-d can be formulated as follows: In the following, we denote this formulation as (F1). The objective function (1) is to minimize the total traveling cost. Constraints (2) and (3) require that the vehicle must enter and leave each node exactly once. Constraint (4) initializes the service at the depot. Constraints (5) represent the relationship between variables s and x. More precisely, they compute the starting service time at a node j based on node i if the vehicle travels from i to j. Here, M is a very large number. Next, d-relaxed constraints are modeled by (6) and will be explained in the following. Finally, constraints (7) and (8) define the decision variables.
We also note that, in [4], the d-relaxed priority constraint was modeled by the following constraints: However, it can be observed that these constraints cannot model the d-relaxed rule defined in the last section. For example, consider a route with the sequence of priorities {1, 2, 1, 3, 2, 4, 7, 3, 5, 6} and d = 2. It is clear that this route satisfies the constraints (9) but does not satisfy the d-relaxed constraint because from priority 4, we can only go to priority at most 3 + 2 = 5.
In the following, we slightly modify the formulation (F1) to propose a formulation called (F2).
We replace the variables s i , i ∈ V in (F1) by the new variables u i representing the order of node v i in the solution and add constraints (15)- (18) to (F2).
Minimize (1) subject to u 1 = 0 (10) Constraints (2) Using u variables instead of s variables brings two advantages. First, it is easier to estimate the The formulations above can be strengthen by adding the following constraints to create two models denoted by (F1') and (F2'), respectively: i∈Vp j∈Vq i∈Vp j∈Vq Constraints (15) proposed in [4] ensure that the vehicle can never travel directly from a priority q node j to a priority p node i, when q ≥ p + 1 + d. Additionally, we propose three new constraints (16)- (18). Constraints (16) and (17) express the d-relaxed priority rule when we depart from and come back to the depot. Constraints (18) say that vehicle will travel at most once from a priority p node i to a priority q node j when q > p + d.

A metaheuristic
In this section, we propose an approximate method to solve the problem. We use the framework called GILS-RVND that brings together the components of Greedy Randomized Adaptive Search Procedure (GRASP), Iterated Local Search (ILS) and Random Variable Neighborhood Descent (RVND). The approach developed by [16] was used to successfully solve the Minimum Latency Problem. The pseudo-code of the algorithm is presented in Algorithm 1. Here, f (s) denotes the objective value of a solution s. The algorithm starts with I max initial solutions which are generated using a greedy randomized procedure Initialize(). Each initial solution s is then improved by means of a local search procedure LocalSearch(s) combined with a perturbation mechanism P ertubation(s) in the spirit of ILS. The local search procedure is designed according to the idea of RVND. It is important to note that the current best solution s ′ is always selected to perform the per-turbation at a given iteration (acceptance criterion). After I ILS iterations without improvements, the process is stopped and the search continues with another initial solution.
We now describe in more details the three main components of our algorithm: generation of an initial solution, local search, and perturbation: Initial solutions: The algorithm starts by generating initial solutions; each solution s is constructed by adding the depot as the first visited location. At each iteration, a randomly selected node of k nearest nodes with respect to the recently added node satisfying the d-relaxed priority rule, is inserted to the tour. To satisfy the d-relaxed priority rule, the candidate vertex must have a priority less than the summation of the minimum priority of unvisited vertices and d. The process is repeated until all the delivery locations are visited. The procedure is described in Algorithm 2.
Local search: The local search is performed by a method based on RVND. Let t be the number of neighborhood structures and N = {N 1 , N 2 , N 3 , ..., N t } be their corresponding set. Whenever a given neighborhood fails to improve the current best solution, RVND randomly selects another neighborhood to continue the search. The process stops if all the neighborhoods cannot improve the result. Preliminary tests revealed that this approach is capable of finding better solutions as compared to those that adopt a deterministic order. In our research, the set N is composed of the following five neighborhood structures, whose associated solutions are explored in an exhaustive fashion with a best improvement strategy.
• Relocate (1) −N (1) − One node is relocated to another position of the tour .
• Relocate (2) −N (2) − Two adjacent nodes are reallocated to another position of the tour.
Sort CL in ascending order according to their distance with respect to r; • There is no node with priority greater than p r[i] + d appearing from (i + 1) th location to j th • If j > i + 1: There is no node with priority smaller than p r[j] − d appearing from i th location and there is no node with priority greater than p r • If j < i: There is no node with priority smaller than p r and there is no node with priority greater than p r[j] + d appearing from (j + 1) th location to (i + 1) th location: Swap (2,2): Similarly, we can swap an adjacent edge (r[i], r[i + 1]) and an adjacent edge Relocate (1): we can relocate a node r[i] to right before j th location of a route r if Relocate (2): we can relocate an adjacent edge (r[i], r[i + 1]) to right before j th location of a route r if Perturbation: The role of the perturbation is to lead the search to escape from local optima,

Results on small and medium-size instances
We  Table 1 where columns "Sol" present the objective values of obtained solutions. Columns "Gap" present the distance between lower and upper bounds returned by CPLEX and columns 'Time" report the running time in seconds.
As can be seen from Tables 1 and 2 Another observation is that random instances seem to be harder to solve than clustered instances. Exact methods could solve to optimality more clustered instances than random instances.
More precisely, the exact method based on the best formulation F2' can successfully solve 30/32 clustered instances but can solve only 22 random instances.
Our metaheuristic provides promising results on the considering instances. It can retrieve all the optimal solutions in a shorter running time which is less than 15 seconds on all instances.
Moreover, it improves the results of exact methods on the instance berlin52R-5-1-a.

Results of GILS-RVND on larger instances
A set of CTSP-d instances with 100 and 200 nodes based on kroA, kroB, kroC, kroD in TSPLIB was generated to analyze the efficiency of the metaheuristic on larger instances. The metaheuristic is run 10 times on each instance with setting (I max , I ILS ) = (5, 1000). The notations used in Tables   3 and 4 are explained as follows: • Instance: the name of instance • AvgSol: the objective value of solutions on average over 10 runs.
• AvgTime: averaged running time over 10 runs • AvgGap: the gap on average of solutions to the best found solution over 10 runs.
• BKS: the best known solution found over 10 runs • GapTSP: the gap of the best found solution to the optimal TSP solution.
The results show the stability of our metaheuristic as the averaged gap AvgGap never exceeds 2%. Although there is no reference algorithm in the literature, we can still analyse the performance of our metaheuristic based on the results of instances with one group and d being set to 0; or in other words on classical TSP instances whose optimal solutions are known. Our algorithm can find all    Table 4: Results of GILS-RVND for instances with 200 deliveries TSP optimal solutions but one (instance kroB100-C-1-0) on instances with 100 deliveries. However, it cannot find any TSP optimal solution on instances with 200 delivery vertices. Its running time is acceptable, less than 2 minutes on 100-node instances and approximately 10 minutes on 200-node instances.
The objective value of solutions on the clustered instances tends to be smaller than on the random instances. This can be easily explained by the way the instances are generated. On the clustered instances, the delivery nodes in a group are closed to each other, and the d-relaxed priority constraint tends to enforce solution tours closed to TSP tours.
As can be seen in the result tables, the increase of d leads to significant reduction in the travel cost. The reduction on the random instances is larger than that on the clustered instances.

CONCLUSION AND FUTURE WORKS
In this paper, we study the clustered traveling salesman problem with d-relaxed priority rule (CTSP-d). We improve the MIP model proposed in [4] and propose the first approximate approach that uses a GILS-RVND framework introduced in [16] to solve this problem. The results show that our best formulation can solve instances up to 52 nodes. There are two indications of a good metaheuristic shown by the GILS-RVND. It can find all the optimal solutions and provide stable solutions in a reasonable running time on large instances.
Future research directions include improving the exact method by adding efficient valid inequalities in a branch-and-cut framework to solve larger instances. The metaheuristic based on larger neighborhoods such as Large Neighborhood Search (LNS) could be a good candidate for an improved approximate method. The capacitated version of the problem is also an interesting topic for future researches.