ReinforceNS: Reinforcement Learning-based Multi-start Neighborhood Search for Solving the Traveling Thief Problem

1 Introduction

The Travelling Thief Problem (TTP) is a challenging combinatorial optimization problem as it combines two NP-hard problems: the Traveling Salesman Problem (TSP) [Flood, 1956] and Knapsack Problem (KP) [Pisinger and Toth, 1998]. And it holds practical importance with varies applications in real-life scenarios, such as water tank transportation [Bonyadi et al., 2013], printed circuit board design [Reinelt, 1991], airport ground movement [Weiszer et al., 2014], wavelength assignment for mesh networks [Hu and Leida, 2004] and the routing problem with loading constraints [Iori and Martello, 2010].

∗Yan Jin is the corresponding author, jinyan@mail.hust.edu.cn.

Given its theoretical challenge and practical significance, TTP has attracted increasing research effort in the last decade [Wagner et al., 2018; El Yafrani and Ahiod, 2018; Namazi et al., 2023]. Existing research on TTP includes exact algorithms, heuristics and hyper-heuristics. Due to its intrinsic intractability, the research lies in the development of effective heuristics to find near-optimal solutions within a reasonable time limit. Compared to the close relative problems TSP and KP that have been intensively studied [Lienland and Zeng, 2015; Osaba et al., 2020; Cacchiani et al., 2022], TTP has received limited attention. Moreover, the TSP and KP algorithms integrating machine learning techniques have demonstrated remarkable performances [Afshar et al., 2020; Zheng et al., 2021; Pierotti et al., 2021; Xin et al., 2021; Tu et al., 2023; Pan et al., 2023], while few efforts have been dedicated to developing machine learning-based TTP algorithms [Namazi et al., 2023].

To the best of our knowledge, no study has been reported in the literature investigating the interest of the reinforcement learning technique for solving TTP. In this work, we fill the gap by introducing the first reinforcement learning-based multi-start neighborhood search algorithm ReinforceNS for TTP. ReinforceNS integrates pre-processing, initialization, reinforcement learning based neighborhood search and postoptimization. To ensure effective exploration of the search space, ReinforceNS employs a multi-start mechanism to escape local optima traps and the dedicated initialization to regenerate new high-quality initial solutions. The main contributions of the paper are summarized as follows.

• The proposed ReinforceNS algorithm integrates a preprocessing procedure and a reinforcement learningbased neighborhood search procedure to ensure an effective and efficient examination of promising neighboring solutions.
• ReinforceNS applies a post-optimization procedure to further improve the local optimal solutions. This is ensured jointly by an item flipping phase and a route refining phase.
• ReinforceNS is extensively tested on the commonly used 60 TTP benchmark instances. Experimental results show the proposed algorithm outperforms three state-of-

the-art algorithms within the same time limit. In particular, it finds 12 improved results for 18 instances publicly reported in a recent TTP competition.

2 RelatedWork

The TTP problem was first introduced in 2013 [Bonyadi et al., 2013] and has received increasing attention in recent years. The existing approaches for solving TTP can be mainly classified into three families: exact algorithms, heuristics and hyper-heuristics. In this section, we briefly review exact algorithms and hyper-heuristics, and then focus on heuristics.

Exact algorithms utilizing dynamic programming or mixed-integer programming [Polyakovskiy and Neumann, 2017; Wu et al., 2017] can find optimal solutions with theoretical guarantees, but face challenges when dealing with large instances within reasonable time due to the inherent exponential complexity.

In contrast, hyper-heuristic and heuristic algorithms can find near-optimal solutions for practical applications, but they lack optimality guarantees. The hyper-heuristic algorithms often utilize genetic programming to generate or select lowlevel heuristics for exploring routes or packing plans, such as [Mei et al., 2015], [Martins et al., 2017; El Yafrani and Ahiod, 2018], [Martins et al., 2017], [El Yafrani and Ahiod, 2018], [Ali and Mohamedkhair, 2021].

The heuristics are widely studied for solving TTP, which can be classified into the following three families [Namazi et al., 2023].

Constructive paradigm. The Chained Lin-Kernighan Heuristic (CLKH) [Applegate et al., 2003] is used to generate a route, and greedy packing strategies are designed while keeping this route unchanged, such as [Polyakovskiy et al., 2014; Bonyadi et al., 2014; Faulkner et al., 2015]. S5 applies them within its restart-based framework [Faulkner et al., 2015]. The constructive paradigm often serves as an initialization procedure for other TTP algorithms.

Cooperative paradigm. After the generation of an initial TTP solution through the constructive paradigm, two separate search procedures for TSP and KP are iteratively applied to improve the route and packing plans. Some notable algorithms in this family include the Cooperative Solver (CoSolver) [Bonyadi et al., 2014] and its improved versions: CoSolver with 2-opt and Simulated Annealing (CS2SA) [El Yafrani and Ahiod, 2016], CS2SA with offline instance-based parameter tuning (CS2SA*) [El Yafrani and Ahiod, 2018], CoSolver with Reverse-Weighted Selection (RWS) [Zhang et al., 2021], as well as a state-of-the-art heuristic Cooperation Coordination (CoCo) proposed most recently [Namazi et al., 2023].

Full-encoding paradigm. Full-encoding paradigm addresses TTP without segregating it into TSP and KP. Many algorithms adopt a hybrid evolutionary framework [El Yafrani and Ahiod, 2016; El Yafrani and Ahiod, 2017; Mei et al., 2014; Wuijts and Thierens, 2019], such as Memetic Algorithm with Two-Stage Local Search (MATLS) [Mei et al., 2014], Memetic algorithm with Edge Assembly and 2-Point crossover operator (MEA2P) [Wuijts and Thierens, 2019].

Additionally, a swarm intelligence algorithm MMAS [Wagner, 2016] based on the Max-Min Ant System [St¨utzle and Hoos, 2000] has been proposed for solving TTP.

Note that three best-performing algorithms, i.e., S5, CoCo and MATLS, from each family of heuristics are used for comparisons in the experiments.

3 ProblemDescription

The TTP problem is defined as follows. Let G = (N,E) be a complete graph, where N = {1, . . . , n} is the vertex set with 1 being the starting-ending city (depot) x1 and other vertices representing n-1 other cities and E is the set of edges. Let D = (di,j) be a non-negative distance matrix associated with E. A set of items M = {1, . . . ,m} is distributed among these cities except city x1. Suppose that each city xi (i ∈ {2, . . . , n}) contains mi distinct items, denoted as Mi = {i1, . . . , imi }, M = ∪ni=1Mi and Mi ∩Mj = ∅, i ̸= j. Each item ik (ik ∈ {1, . . . ,m}) positioned in the city xi has a profit value pik and weight wik . The thief starts from city x1, visits each of the cities exactly once, and returns back to the starting city x1. During the tour, the thief can pick up any item into his knapsack in any city until the total weight of items does not exceed the maximum weight W of the knapsack. A renting rate R is to be paid per each time unit being on the tour.

The vmin and vmax are the minimum and maximum speeds that the thief can move respectively. Suppose that vxi represents the speed of the thief in city xi. Eq. (1) gives the linear relationship between the thief's speed and the knapsack's weight.

where C = vmax-vmin W is a constant value, wxi indicates the knapsack weight of the thief in city xi, as shown in Eq. (2).

Let Π = (x1, . . . , xn) represent a route plan and P = (z1, . . . , zm) be a binary vector representing a packing plan, where zj equals to 1 when item j is picked up, and 0 otherwise. The objective of TTP is to find a route plan Π and a packing plan P of the maximal profit value as Eq. (3).

where g(P) represents the total profit values of all items packed in the knapsack, R · ψ(Π, P) represents the amount that the thief pays for the knapsack's rent.

One easily notices that TTP can be reduced to TSP by assigning zero to the profit values of all items. Similarly, TTP can be considered as KP by setting the renting value to zero. These observations also confirm the challenge of solving the TTP problem.

Algorithm 1 The proposed ReinforceNS algorithm

Input: A TTP instance

Output: The best solution (Π∗ , P ∗ )

• 1: Initialize Π∗ , P ∗ ← ∅,f ∗ ←-∞;
• 2: t ← 0;
• 3: Candidate edge sets ←A pre-processing procedure;
• 4: while t < Tmax do
• 5: An initial route Π←TSP solver CLKH;
• 6: An initial packing P ← An iterated greedy packing procedure IGP(Π);
• 7: (Π′ , P ′ ) ←RLNS(Π, P); /* The reinforcement learning based neighborhood search procedure */
• 8: P ′′ ←An Item Flipping Phase IFP(Π′ , P ′ ); /* Further improve P ′ */
• 9: Π′′ ←ARoutingRefining Phase RRP(Π′ , P ′′ ); /* Further improve Π′ */
• 10: if f(Π′′ , P ′′ ) > f ∗ then
• 11: f ∗ ← f (Π′′ , P ′′ );
• 12: Π∗ ←Π′′ ;
• 13: P ∗ ←P ′′ ;
• 14: end if
• 15: end while
• 16: return (Π∗ , P ∗ )

4 The Proposed ReinforceNS Algorithm

The proposed ReinforceNS algorithm is a multi-start iterated neighborhood search heuristic reinforced by a reinforcement learning mechanism. After pre-processing, it explores the search space by repeating a dedicated solution construction, local optimization and post-optimization. The local optimization and post-optimization procedures apply neighborhood search by transitioning from the current solution to one of its neighboring solutions. Each iteration involves replacing the current solution with the best neighboring solution that offers an immediate improvement over the current solution.

Algorithm 1 provides the general scheme of ReinforceNS that relies on a multi-start iterated local search framework. Specifically, after the initialization of the optimal solution (Π∗ , P ∗ ) and its corresponding objective value f ∗ , ReinforceNS applies a pre-processing procedure to reduce the candidate edge sets, and then performs a series of iterations until reaching the maximum time limit Tmax. At each iteration, a solution Π is generated by the TSP solver CLKH [Applegate et al., 2003]. Subsequently, an iterated greedy packing procedure (IGP) is applied to Π to produce a packing plan P, thus initializing a high-quality solution (Π, P) for TTP. This solution is improved through the reinforcement learning based neighborhood search procedure. To help the search escape from the local optima, a post-optimization procedure including an item flipping phase and a route refining phase is employed for further improvement. The best-found solution (Π∗ , P ∗ ) is updated and finally returned as the output at the end of the ReinforceNS algorithm.

4.1 Pre-Processing

Before starting the search, we pre-process the input TTP instance G using a neighborhood reduction procedure. This is achieved by a subgradient optimization approach on the 1tree and α-nearness adopted from the well-known TSP algorithm Lin-Kernighan-Helsgaun (LKH) [Helsgaun, 2000].

Given a complete graph G, the neighborhood N (xi) of city xi is defined as the set of adjacent cities xj connected to xi by an edge (xi, xj). Initially, each vertex has n-1 neighbors. A 1-tree of G is a spanning tree for the graph of vertex set V \xi combined with two edges in E connected to vertex xi, an arbitrary special vertex in V . A minimum 1-tree T is the 1-tree with minimum length. The α-nearness of an edge (xi, xj) ∈ E is defined as α(i, j) = L(T +(xi, xj)) - L(T ), where L(T) is the length of T and L(T +(xi, xj)) is the length of minimum 1-tree that includes the edge (xi, xj).

To reduce the neighborhoods of each vertex, we use a subgradient optimization procedure that gradually adjusts the vertex degree towards 2 for a minimum 1-tree by introducing a penalty to each vertex. In our experiment, the size of N(xi) is set to 15. The ReinforceNS algorithm utilizes these reduced neighborhoods for the subsequent search.

4.2 Initialization

To ensure efficient search, the quality of initial solutions is crucial for guiding the search towards promising regions. We apply TSP and KP approaches separately to generate an initial TTP solution (Π, P ) with high-quality.

We employ Chained Lin-Kernighan Heuristic [Applegate et al., 2003] (CLKH) to generate a high-quality route Π. It is noteworthy that CLKH is one of the most widely used algorithms for solving TSP.

Based on the route Π, we design a dedicated Iterated Greedy Packing (IGP) procedure to attain a good packing plan P for constructing an initial solution (Π, P ) for TTP. We adopt the scoring function as Eq. (4) [Faulkner et al., 2015] to evaluate item k picked up from city xi.

where ξi = dxn,x1 + ∑n-1 j=i dxj,xj+1 represents the distance from city xi to the ending city (depot) of the route. Notice that there is a trade-off between weight and profit value, we also introduce exponents to Eq. (5) and the function becomes as the following Eq. (5).

Different from [Faulkner et al., 2015], we use three parameters κ, β and γ to adapt the impact of profit value, weight and distance respectively.

The IGP procedure is composed of four steps. First, we randomly sample the values of κ, β and γ from a uniform distribution between 0 and 1. Second, iteratively choose an item with the highest score, calculated by Eq. (5), and pack it into the knapsack. When the total weight of items does not exceed the maximum weight W of the knapsack multiplied by a randomly selected factor δ between 0.5 and 1, a feasible packing P0 is obtained. Third, repeat the above two steps for 10000 log(n·m) times to determine a best-found packing P ′0 . Finally, starting with the parameters κ, β, γ and δ that attains P ′0 , we further explore the search for optimizing the packing by adjusting κ and β, such as (κ - θ, β - θ), (κ + θ, β + θ), (κ - θ, β + θ), and (κ + θ, β - θ), where θ is a parameter set to 5 and will progressively decreases by 0.75 times during the search. This process repeats 20 times, ultimately yielding a high-quality initial packing solution P. Consequently, an initial solution (Π, P) is effectively constructed.

4.3 Reinforcement Learning-Based Neighborhood Search

Neighborhood search is a powerful local optimization approach, we apply a reinforcement learning mechanism to speed up neighborhood examination, and propose a Reinforcement Learning-based Neighborhood Search (RLNS) procedure to discover better solutions.

Recall that L(T) is the length of the minimum 1-tree, and the α-nearness α(i, j) of an edge (xi, xj) is the extra length of the L(T) to include this edge, we define the Q-value for city xi and city xj as shown in Eq. (6), where the parameter τ is set to 0.5 and b is set to 1e-6 .

The pseudocode of our RLNS is shown in Algorithm 2. After initializing the Q-value for each edge using Eq. (6), RLNS performs a series of iterations, with the maximum number of iterations Itermax set to 1000. At each iteration, RLNS employs the ϵ - greedy strategy for each city xi (excluding the depot) to select a neighboring city xj for 2-opt exchange. More precisely, it selects the best neighboring city xj with the highest Q-value from the neighborhoods N(xi) with a probability of 1 - ϵ, and randomly selects xj with a probability of ϵ = 0.2. Note that, the items of the sub-route from xi to xj should be removed from the knapsack of P , since the subroute between xi and xj is changed. For the cities located along the new sub-route from xj to xi, RLNS adds an item with the highest score (Eq. (5)) among the items from these cities into the knapsack and repeats until the total weights exceeds the maximum weight of knapsack W multiplied by δ. The best local optimal solution is updated once a better objective value is found. Afterwards, the Q-value of (xi, xj) is updated using Eq. (7). Here, the parameter λ and ϕ are set to 0.1 and 0.9 respectively, and the state st, action at, and reward r(st, at) are defined as follows.

• State st: The state at the current iteration t is a city xi that is going to select a neighboring city for applying the 2-opt exchange operator.
• Action at: Select a neighboring city xj of city xi at the current iteration t.
• Transition: The next state after performing the action is the next city that needs to select a neighboring city for the 2-opt exchange operator.

Algorithm 2 The pseudocode of the RLNS procedure

Input: The initial solution (Π, P ), the best objective value f ′ Output: The local optimal solution (Π′ , P ′ )

• 1: Initialize Q-value of each edge by Eq. (6);
• 2: for iter ← 0 To Itermax do
• 3: Initialize the local objective value flocal = -∞;
• 4: for xi ← 2 To xn do
• 5: xj = ϵ-greedy(N(xi)) /* Select xj of the highest Q-value with a probability 1 - ϵ and select xj at random with a probability ϵ */
• 6: Remove items of P from the sub-route that begins at city xi and ends at city xj from the knapsack;
• 7: Π←Apply 2-opt exchange on Π at city xi and xj;
• 8: P ←Iteratively add the items with the highest score as Eq. (5) of the sub-route from city xj to city xi into the knapsack without exceeding W × δ;

• 11: end if
• 12: Update Q-value of (xi, xj) according to Eq. (7)
• 13: end for
• 14: if flocal > f ′ then
• 15: Π′ ←Πlocal, P ′ ←Plocal, f ′ ← flocal
• 16: end if
• 17: Π←Πlocal, P ←Plocal
• 18: end for
• 19: return local optimal solution (Π′ , P ′ )
• Reward r(st, at): Suppose that the current solution (Π0, P0), after performing the 2-opt exchange operator at city xi and xj, the neighboring solution is (Π1, P1). The difference between the objective values of the neighboring solution and the current solution is denoted as r(st, at) = f (Π1, P1) - f (Π0, P0).

During Itermax consecutive iterations, the best-found solution (Π′ , P ′ ) is updated if an improved solution has been found, and the best-found solution (Π′ , P ′ ) is returned as the final output of RLNS.

4.4 The Post-Optimization Procedure

In addition to the RLNS procedure described above, the proposed ReinforceNS algorithm develops a post-optimization procedure to further improve the quality of the best-found solution (Π′ , P ′ ) obtained by RLNS. This post-optimization is ensured jointly by an item flipping phase and a route refining phase.

The item flipping phase is devised to optimize the packing solution P ′ while keeping the route solution Π′ unchanged. The flipping operator for an item involves removing it from the knapsack if it is already included or including it if not. During each iteration, the item flipping phase pseudoperforms the flipping operator for each item i. If this operation leads to a new objective value, the item i is flipped using the itemflipping operator. If no improvement is achieved, the item i remains unchanged. This process repeats until no new objective value is discovered during an iteration.

From the problem definition of TTP, one easily notices that as the thief approaches the ending city (depot), the weight of the knapsack increases, leading to a decrease in speed. We introduce a route refining phase to try to move the cities with heavy yet valuable items included in the knapsack to the last positions of the route, for further optimization of the TTP solution.

Figure 1 provides an illustrated example of efficiently calculating the time cost ψ(Π, P) in Eq. (3) when adjusting the position of a city in the route. Suppose that the route solution is Π and the packing solution is P, the lengths of edges (xi, xi+1), (xj-1, xj), and (xj, xj+1) are 7, 4, and 3 respectively, and the speed of the thief in city xi is 5 and in city xj-1 is 2. City xj is moved to a position between cities xi and xi+1 of the route, resulting in a new path Π′ . The lengths of the new edges (xi, xj), (xj, xi+1) and (xj, xj+1) are 5, 6, and 5 respectively. As city xj has no picked-up items, the speed of the thief remains unchanged. Using Eq. (8), the time increment △ψ is calculated as 5+6 5 + 52 -( 75 + 3+4 2 ) = -0.2, which can be efficiently computed in O(1) time complexity. One observes that adjusting the position of a city in the route makes the new path Π′ longer (16 vs. 14), but reduces the time cost (-0.2), resulting in a better route solution.

To clarify the route refining phase, a path Πx is defined as a route that starts from the depot and ends at city x. For each city xi without items included in the knapsack, we pseudoinsert it into each edge of Πxi and efficiently calculate the time cost using Eq. (8). If several improved objective values are discovered, city xi will be inserted into the edge with the best objective value. If no improved objective values are found for any of these cities, the route refining phase stops.

5 Experiments

To evaluate the effectiveness of the proposed ReinforceNS algorithm, we present computational results in comparison with the best publicly reported results from the TTP competition at the Genetic and Evolutionary Computation Conference (GECCO) 2023 on three sets of 18 instances. Additionally, we compare the performance of ReinforceNS with that of the best-performing algorithms in the literature using three sets of 60 widely used benchmark instances.

ReinforceNS was implemented in C++ and compiled using GNU g++ 9.4.0 with '-O3' optimization flag. The experiments were conducted on the AutoDL server with an Intel(R) Xeon(R) Platinum 8255C CPU @ 2.50 GHz and a memory limit of 40 GB. The maximum runtime limit Tmax was set to 600 seconds, which is a common stopping condition for evaluating TTP algorithms. Given the stochastic nature of ReinforceNS, each instance was executed 10 times. Note that the source code of the reference algorithm CoCo [Namazi et al., 2023] is publicly available, we re-ran CoCo on our platform to ensure a fair comparison.

Benchmark instances. The TTP benchmark library 1 , proposed by Polyakovskiy et al. [2014], comprises a total of 9720 instances with city counts ranging from 76 to 85900. In our experiments, we used a subset of 60 benchmark instances selected from this library, ranging from 76 to 33810 cities. These instances are widely used in previous studies and are categorized into three sets: CatA, CatB and CatC, each containing 10 specific instance files. We use suffixes to denote the specific selected instance files.

• CatA: The maximum weight of knapsack is relative small. Each city has only one item. The weights and profits of the items are bounded and strongly correlated.
• CatB: The maximum weight of knapsack is moderate. Each city has five items. The weights and profits of the items are uncorrelated, and the weights of all items are similar.
• CatC: The maximum weight of knapsack is high. Each city has ten items. The weights and profits of the items are uncorrelated.

Comparison with the best results from TTP competition. We compare our ReinforceNS algorithm with the results of the most recent TTP competition organized by Markus Wagner et al. at the GECCO conference in 2023. Table 1 provides the comparative results for a total of 18 instances with the same time limit. These 18 instances are also classified into three sets: CatA, CatB and CatC. They are randomly selected from 10 instance files of each category, indicated by the suffix "-r". The column "Competition∗ " presents the best average results among 5 top-performing algorithms publicly reported on the website of GECCO 2023. The next column "ReinforceNS" reports our best average results over 10 runs. Note that we truncate the decimal of all results for brevity. The better results between Competition∗ and our ReinforceNS are indicated in bold. One easily observes that our proposed algorithm outperforms the best results publicly reported on the website by 12 out of 18 instances. Upon closer examination of ReinforceNS' performance, it is observed that it achieves more new results as the maximum weight of the knapsack and the items in each city increase.

Comparison with three best-performing TTP algorithms. Then we compare ReinforceNS with three top-performing TTP algorithms from the literature: MATLS [Mei et al., 2014], S5 [Faulkner et al., 2015] and CoCo [Namazi et al., 2023]. Table 2 lists the best average results of these algorithms, consistent with previous studies. These 60 instances are selected from the first instance file of each category, typically used for comparing results of the TTP algorithms, indicated by the suffix "-1". One easily observes that our ReinforceNS consistently dominates MATLS and S5 in terms of the best average result for all 60 instances. Additionally, ReinforceNS outperforms CoCo for 38 out of the 60 instances, especially for the two benchmark sets CatA and CatB with small and medium sizes.

1 The TTP instances are available at https://cs.adelaide.edu.au/ ∼optlog/CEC2014COMP InstancesNew/

The 95% confidence intervals based on the best average results in Table 2 are further introduced for a statistical evaluation of these algorithms. They are calculated using Eq. (9).

Here, µ represents the mean of the Relative Deviation Index RDI = res-min max-min × 100 [Kim and Kim, 1996], where res is the result of the reference algorithm, min and max are the minimum and maximum results among all the algorithms, respectively. The σ denotes the standard deviation of results, and z represents the number of instances. Figure 2 illustrates the 95% confidence intervals for these algorithms, highlighting that ReinforceNS outperforms the three comparison algorithms and demonstrates stable performance with the lowest variance.

Ablation study. To demonstrate the effectiveness of incorporating Reinforcement Learning (RL), we conduct an ablation study comparing ReinforceNS with RL against ReinforceNS without RL, denoted as ReinforceNS w/o RL. The comparative results are summarized in Table 3. From the table, we can observe that ReinforceNS achieves superior performances, surpassing ReinforceNS w/o RL by 12, 12 and 15 instances in CatA, CatB and CatC, respectively. This suggests that the RL mechanism can indeed select promising neighboring solutions and facilitate an efficient search, leading to better results in most instances. Moreover, ReinforceNS with RL demonstrates competitive performance against ReinforceNS w/o RL, particularly on the large TTP instances. Additionally, Figure 3 shows that both ReinforceNS and ReinforceNS w/o RL demonstrate greater stability than the three top-performing TTP algorithms. Among them, ReinforceNS stands out as the most stable with the lowest variance.

6 Conclusion

In this paper, we propose the first learning-based algorithm utilizing the great power of reinforcement learning mechanism to combine with an effective neighborhood search heuristic for TTP. The proposed ReinforceNS algorithm incorporates a dedicated initialization procedure to identify promising regions, a neighborhood search procedure reinforced by a Q-learning strategy to find high-quality local optima, a post-optimization procedure for further improvement, and a multi-start mechanism to overcome deep local optima traps. We perform extensive experiments of the ReinforceNS on three sets of 60 benchmark instances. The comparisons with three state-of-the-art algorithms demonstrate the high competitiveness of our ReinforceNS in terms of solution quality and stability. In particular, ReinforceNS achieves improved results for 12 out of the 18 instances that were publicly reported in the recent TTP competition at GECCO 2023. This work provides supporting evidence for using reinforcement learning to improve the efficiency of heuristics. As such it would be interesting to investigate other machine learning or deep learning techniques for solving TTP for future work.

Acknowledgements

This work was supported in part by CCF-Huawei Populus Grove Fund and the National Natural Science Foundation of China (No. 62302174).