Hybrid pointer networks for traveling salesman problems optimization

Abstract

In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer’s encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.

About the Authors:

Ahmed Stohy

Roles Conceptualization, Data curation, Investigation, Methodology, Validation, Visualization, Writing – original draft

Affiliation: Department of Computer and Systems Engineering, Minya University, Minya, Egypt

Heba-Tullah Abdelhakam

Roles Conceptualization, Data curation, Formal analysis, Investigation, Writing – original draft

Affiliation: Department of Computer and Systems Engineering, Minya University, Minya, Egypt

Sayed Ali

Roles Conceptualization, Data curation, Methodology, Software, Visualization, Writing – original draft

Affiliation: Department of Computer and Systems Engineering, Minya University, Minya, Egypt

Mohammed Elhenawy

Roles Conceptualization, Data curation, Investigation, Methodology, Software, Supervision, Validation, Writing – review & editing

Affiliation: Centre for Accident Research and Road Safety, Queensland University of Technology, Brisbane, Australia

Abdallah A. Hassan

Roles Conceptualization, Data curation, Methodology, Supervision, Validation, Writing – review & editing

Affiliation: Department of Computer and Systems Engineering, Minya University, Minya, Egypt

Mahmoud Masoud

Roles Conceptualization, Investigation, Methodology, Supervision, Writing – review & editing

* E-mail: [email protected]

Affiliation: Centre for Accident Research and Road Safety, Queensland University of Technology, Brisbane, Australia

ORCID logo https://orcid.org/0000-0002-0130-4327

Sebastien Glaser

Roles Conceptualization, Methodology, Supervision, Validation, Writing – review & editing

Affiliation: Centre for Accident Research and Road Safety, Queensland University of Technology, Brisbane, Australia

ORCID logo https://orcid.org/0000-0003-0658-7765

Andry Rakotonirainy

Roles Conceptualization, Investigation, Methodology, Supervision, Writing – review & editing

Affiliation: Centre for Accident Research and Road Safety, Queensland University of Technology, Brisbane, Australia

Abstract

In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer’s encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.

Figures

Fig 8

Table 6

Table 7

Fig 1

Fig 2

Table 1

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Table 2

Table 3

Table 4

Table 5

Fig 8

Table 6

Table 7

Fig 1

Fig 2

Table 1

Citation: Stohy A, Abdelhakam H-T, Ali S, Elhenawy M, Hassan AA, Masoud M, et al. (2021) Hybrid pointer networks for traveling salesman problems optimization. PLoS ONE 16(12): e0260995. https://doi.org/10.1371/journal.pone.0260995

Editor: Seyedali Mirjalili, Torrens University Australia, AUSTRALIA

Received: October 21, 2021; Accepted: November 20, 2021; Published: December 14, 2021

Copyright: © 2021 Stohy et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Data Availability: All data, code and models files are available at https://github.com/AhmedStohy/Hybrid-Pointer-Networks.

Funding: The authors received no specific funding for this work.

Competing interests: he authors have declared that no competing interests exist.

I. Introduction

Combinatorial optimization problems have garnered substantial attention from the theory and algorithm design community in recent decades as fundamental challenges in computer science and operations research. TSP in one fundamental combinatorial optimization problem that have been explored in the disciplines of logistics transportation, genomics, express delivery, and dispatching. TSP is often defined on a graph with a number of nodes, and it is essential to search through the permutation sequences of nodes for finding an optimal one with the shortest traveling distance.

Due to the many applications of the travelling salesman problem (TSP) in many areas, it has received significant attention from the machine learning community in the past years. However, the developed neural combinatorial optimization models are still in the infantry stage. Generalization is still an unresolved problem when it comes to dealing with many points with high precision. The travelling salesman problem (TSP) is considered as one of the most significant and practical problems. Consider a salesman travelling to several areas; the salesman must visit each city just once while minimizing the total travel time. TSP is an NP-hard problem [1], which addresses the challenge of finding the optimal solution in polynomial time.

Exact algorithms, approximation algorithms, and heuristic algorithms are examples of traditional approaches for tackling NP-hard graph optimization problems [2]. Exact algorithms using the branch and bound framework can produce optimum solutions, but due to their NP-hardness, they are not suited for large-scale applications. Polynomial-time approximation algorithms can often produce quality-guaranteed solutions, although they have lower optimality guarantees than precise algorithms. The optimality guarantee may not exist at all for situations that are not amenable to a polynomial approximation approach. Furthermore, because of their high computing efficiency, heuristic algorithms are commonly employed, although they typically need adaptations and subject specialist understanding for a given situation. Heuristic algorithms frequently lack theoretical basis, all three groups of algorithms previously mentioned seldom take advantage of the common features among optimization problems, and thus frequently require the design of a new algorithm to solve a different instance of an even similar problem that is based on the same combinatorial structure, with the coefficient values in the objective function or constraints regarded as samples from the same basic distributions [3]. The use of machine learning methodologies has provided a silver lining in the form of a scalable solution for solving combinatorial problems with similar combinatorial structures.

Many approximation algorithms and heuristics, such as Christofides algorithm [4], local search [5], and the Lin-Kernighan heuristic (LKH) [6] have been developed to overcome the complexity of the exact algorithms which are guaranteed to yield an optimal solution but are frequently too computationally costly to be utilized in practice [7]. Many combinatorial optimization problems, such as a TSP has a graph structure [8], which may be easily described using the current graph embedding or network embedding techniques. The graph information is integrated in a continuous node representation in this method. Because of its great skills in information embedding and belief propagation of graph topology, the most recent development of graph neural network (GNN) may be applied in simulating a graph combinatorial problem [9]. This drives us to use a GNN model to handle combinatorial optimization problems, specifically TSP.

The pointer network [10], a seq2seq model [11], shows great potential for approximation solutions to combinatorial optimization problems such as identifying the convex hull and the TSP. It uses LSTM [12] as the encoder and an attention mechanism [13] as the decoder to extract features from city coordinates. It then predicts a policy outlining the next likely city by selecting a permutation of visited cities. The pointer network model is trained using the Actor-Critic technique [14].

Moreover, the attention model [15, 16], influenced by the Transformer architecture [13], tried to address routing problems such as the TSP and VRP. Graph pointer networks [17] extended the traditional pointer networks with an additional layer of graph embedding, this transformation achieved a better generalization for a large-scale problem, but the GPN model without 2-opt still struggling for finding the optimal solutions for small and large scale.

GPN has limited capabilities for tackling small-scale problems, and the suggested GNN employed in its architecture isn’t the ideal encoder for determining point-to-point relationships. The work proposed in this paper begins with how the performance of graph pointer networks can be improved without changing much of the architecture; an extra encoder layer is added alongside the graph embedding layer to act as a hybrid encoder, and this gives the model the ability to achieve good results; this will be discussed in greater detail in the HPN section.

Extensive experimental work results show that the proposed technique significantly outperforms previous DL-based methods on TSP. The learnt model is more successful than standard hand-crafted rules in guiding the improvement process, and they may be further strengthened by simple ensemble methods. Furthermore, HPN generalizes rather well to a variety of problem sizes, starting solutions, and even real-world datasets. It should be noted that the goal is not to outperform highly optimized and specialized traditional solvers but to present a generalized model that can automatically learn good search heuristics on different problem sizes, which has a great value when applied to real-world problems.

In this work, we propose a deep reinforcement learning model trained via Actor-critic. Our architecture is based on a pointer attention mechanism that outputs nodes sequentially for action selection. We introduce a reinforcement learning formulation to learn a stochastic policy of the next promising solutions using a hybrid architecture, incorporating the search’s history information by keeping track of the current best-visited solution. Our results show that we can learn policies for the Euclidean TSP that achieve the state-of-the-art solution compared with previous work in RL-based Models. Moreover, our approach can achieve state of the art results compared with previous deep learning methods based on construction [10, 15, 18–20] and improvement [21] heuristics.

II. Travelling salesman problem (TSP)

TSP is a classic example of a combinatorial optimization problem that has been used in data clustering, genome sequencing, as well as other fields. TSP problem is NP-hard, and several exact, heuristic and approximation algorithms have been developed to solve it. In this paper, TSP problems are assumed to be symmetric. The symmetric TSP is regarded as an undirected graph.

1. Asymmetric vs. symmetric TSP

The distance between two cities in the symmetric TSP is the same in each opposite direction, producing an undirected network. This symmetry cuts the number of alternative solutions in half. Paths may not exist in both directions in the asymmetric TSP, or the distances may be different, resulting in a directed graph.

2. Directed vs. undirected graphs

Edges in undirected graphs do not have a direction. Each edge may be travelled in both directions, indicating a two-way connection. The edges of directed graphs have a direction. The edges represent a one-way connection, as each edge may only be travelled in one direction.

A full undirected graph can be defined as C = (V,E)where V is the vector of vertices of graph C, and E is the vector of edges between these vertices. In this study, the TSP’s graph is complete, so every node has an edge to each of the other vertices in the graph.

In the context of this paper, eij equals the distance between the vertices i and j. Given a set V of cities n in a two-dimensional space, the objective is to find the optimal Hamiltonian path that minimizes the total tour length [20]:(0.1)

Where ‖.‖2 is ℓ2 norm and π denote as a tour.

III. Methods

In this section, we will describe the learning algorithm used to train the proposed model. Furthermore, we describe the statistical model used to test whether our proposed model outperforms the GPN.

1. Reinforcement learning (RL)

Reinforcement learning (RL) is the process of learning what to perform to increase the expected numerical reward signal. The agent isn’t instructed which actions to perform but must experiment to determine which acts offer the greatest expected reward. To begin, we will define the notation used to represent the TSP as a reinforcement learning problem. Let S be the state space and A the action space. Each state st∈S is defined as the set of all previously visited cities. Action at∈A is defined as the following selected city from the group of possible cities; our model is considered a sequential one that, given an instance at (selected input city) outputs a probability distribution over the next candidates from the remaining cities that have not been chosen. We can define our policy as:(0.2)

From which we can sample to obtain a tour π. In order to train our model, we define the loss [15]:(0.3)

Where L(π) is the cost of the tour that we are attempting to minimize. Recall the REINFORCE’s [22] equation with baseline which is an extension from policy gradient algorithm [23]:(0.4)

Where b(s) is the baseline subtracted from the cost to eliminate the policy gradient variance. The optimal baseline is one that lowers variation as much as possible while simultaneously speeding up the training process. As a result, we employ the approach given by [15]:

Algorithm 1. REINFORCE with Rollout Baseline []

1: input: number of epochs E, steps per epoch T, batch size B, significance α

2: init θ, θBL ← θ # initialize network parameters

3: for epoch = 1,…, E do

4: for step = 1,…, T do

5: si ← RandomInstance () ∀ i ∈ {1,…, B} # Generate Random Instances

6: πi← SampleRollout (si,pθ) ∀ i ∈ {1,…, B} # Sample from policy

7: ← GreedyRollout (si, ) ∀ i ∈ {1,…, B} # Greedy selection from policy

8: # Loss calulation((Sampling cost–BL cost)* logprob)

9: θ ← Adam (θ, ) # Optimizer step

10: end for

11: if OneSidedPairedTTest (pθ, ) < α then # Check if Actor is better than critic with margin α

12: θBL ← θ # Transfer Actor’s weights into Critic

13: end if

14: end for

2. Linear mixed effect models

Linear mixed effect models (LMEs) are tools used to test whether a significant relationship exists between the dependent variable (response) and independent variables (regressors). LMEs are developed to enable the analysis of dependent data by introducing random variables (i.e., random effects) at the lower levels of the model. For example [24], different algorithms returned solutions to the same instance. To capture the correlation between the solutions of the same instance, a random effect is introduced at the instance level. The formula of the mixed model is shown below

Where

y is the response vector

X is the design matrix for fixed factors

β is the coefficients of fixed effect regression

Z is the random effects design matrix for random factors

U is the vector of random effects

ε is the residuals

In the linear mixed model, the fixed factor xi’s null hypothesis is that xi does not significantly explain some of the variability of the response y (i.e., βi = 0). For the purposes of this paper, the significance level, α, is set at 0.05. To determine if a particular fixed factor significantly affects the response, the p-value corresponding to this fixed factor in the estimation table is compared with the 0.05 significance level.

IV. Hybrid pointer network (HPN)

HPN is inspired by the Graph pointer network (GPN). GPN is a modified variant of the classic pointer network (PN).

Graph pointer networks have been used to tackle TSP. Building on this approach, in this paper:

* The graph embedding layer is combined with the transformer’s encoder to produce multiple embeddings for the feature context.

* An extra decoder layer is added to operate as a multi-decoder structure network to improve the agent’s decision-making process throughout the learning phase.

* Finally, we switch our learning algorithm from a central self-critic [25] to an actor-critic one as suggested by Kool [15].

The GPN adds graph embedding layer above the pointer network, allowing the model to figure out the complicated relationships between graph nodes in large-scale problems. However, it still struggles to find a globally optimal strategy for TSP problems. This study proposes extending the network architecture to converge to a better policy for small, medium, and large sizes. The proposed HPN is shown in Fig 1. HPN consists of a mixture of several encoder’s architecture and multi decoder based on the attention concept.

[Figure omitted. See PDF.]

Fig 1. Architecture of HPN which combining a hybrid context encoder with a multi-attention decoder.

https://doi.org/10.1371/journal.pone.0260995.g001

1. Hybrid encoder

As illustrated in Fig 2, the proposed encoder consists of two parts: the hybrid context encoder, which encodes the Feature vector into two contextual vectors and the point encoder, which encodes the currently selected city by LSTM. Two different encoders are employed for the hybrid context encoder. The first encoder is a typical transformer encoder with multi-head attention and residual connection with batch normalizing layer, the transformer’s encoder equations with a single head are [26]:(0.5)(0.6)(0.7)(0.8)(0.9)

Where , and are learnable parameters, Henc is a matrix contains the encoded nodes, Ql, Kl and Vl are a query, key and value of the self-attention.

[Figure omitted. See PDF.]

Fig 2. Hybrid encoder consists of transformer’s encoder and graph embedding layer as a hybrid context encoder, (blue dotted box) for the hybrid context encoder and (red dotted box) for the point encoder.

https://doi.org/10.1371/journal.pone.0260995.g002

The second one is the graph embedding layer. The graph embedding layer context is acquired by directly encoding the context vector obtained from coordinates of cities. Because we are only considering symmetric TSP, the graph is full. As a result, the graph embedding layer can be written as [17]:(0.10)

Where is the aggregation function, γ is a trainable parameter, is trainable weight matrix and N(i) the adjacency set of node i.

For the point encoder which encodes the currently selected city, each city coordinates xi (i.e. (xi1, xi2)) is embedded into a higher dimensional vector , where d is the hidden dimension. An LSTM then encodes the vector for the current city xi. The hidden variable of the LSTM is passed to both the decoder of the current stamp and the encoder of the next time stamp.

2. Multi-decoder

To begin the decoding phase, a placeholder is added for the first iteration of the decoding to select the best location to start the tour, the decoder is based on the attention mechanism of a pointer network and outputs the pointer vector uI, which is then sent through a Softmax layer to build a distribution across the following candidate cities. The attention mechanism and the pointer vector uI are defined as follows [17]:

Where ui(j) is the j-th entry of the vector ui, Wr and Wq are trainable parameters, q is the query vector from the hidden state of the LSTM, is a reference vector containing the contextual information from all cities.

The encoded context from the transformer’s encoder is used as a reference for the first decoder layer and the context obtained from the graph embedding layer is used as the reference for the second decoder layer, as illustrated in Fig 1.

Then we’ll have an attention vector for each decoder layer, and we’ll need to figure out how to aggregate them. For the aggregator Function, four distinct procedures may be used to determine the distribution policy throughout the candidate cities:

* The first option is to add the two attention vectors from each decoder layer, which are provided by:

* The second option is to take the maximum value between these two vectors, which is indicated as follows:

* The third option is to take the mean as follows:

* The final option is to concatenate both of them and feed the concatenated vector into a single embedding layer, letting the model to decide how to aggregate them; we can describe this notion as follows:

Where ϑθ:RN×2→RN×1 is the aggregation function. In the result section, we displayed the outcome for each one of them.

Fig 1 illustrates the model operations. We feed the network a tensor of input nodes in this problem the input nodes contain four features as previously illustrated so the input dimeson will be (batch-size, problem-size, number-of-feature), we feed these nodes into the hybrid context and will get two contextual vectors one from the transformer’s encoder and the other from the graph encoder, then for the first decoding stamp we feed the placeholder to the pointer encoder for learning the best possible location. Finally, we feed the contextual vectors with the hidden states from the pointer encoder to our decoder, which is a simple attention layer, and aggerate the two-attention vectors using the sum operation. For clarity, we employ two decoder layers, one for the context vector of the graph and the other for the context vector of the transformer.

V. Experiments

In our experiments, the city/node coordinates are independently and randomly drawn from a uniform distribution x ~ U(0, 1). In each epoch, the training data is generated on the fly. The hyperparameters provided in Table 1 are used in the following experiments.

[Figure omitted. See PDF.]

Table 1. Hyperparameters used for training.

https://doi.org/10.1371/journal.pone.0260995.t001

1. Small-scale experiments

We begin our experiments with a difficult barrier: which aggregator function between the previously described ones will assist our model in achieving better results? Indeed, it is difficult to answer this question without experimenting all of them; we examined the above-mentioned suggestions for this component and recorded the training performance results. Fig 3 illustrate these results.

[Figure omitted. See PDF.]

Fig 3.

Training performance for the actor (on Top) and the critic (on Bottom) where the total tour length on the y-axis and the number of epochs on x-axis indicating that when we apply the sum operation between the two attention’s vectors, the model converges a little fast compared with the others.

https://doi.org/10.1371/journal.pone.0260995.g003

We can conclude from the above figure that the summation has excellent performance at first, but by the middle of training, the average has caught it, the maximum and the single-layer aggregation have a little higher result, so we decide to stop examining them.

We use 50 nodes travelling salesman problem (TSP50) instances to train our HPN model to tackle the small-scale. TSP50’s average training time for each epoch is 19 minutes while utilizing one NVIDIA Tesla P100 GPU instance. We compare the performance of our model on small-scale TSP to earlier studies such as Graph pointer networks, the Attention Model, the pointer network, s2v-DQN [3], the Transformer Network [26] and other heuristics, e.g. 2-opt heuristics, Christofides algorithm and random insertion. The results are shown in Fig 4 which compares the approximate tour length to the optimal solution on 10k instances. A small number indicates a better result.

[Figure omitted. See PDF.]

Fig 4. Comparison of TSP50 results.

https://doi.org/10.1371/journal.pone.0260995.g004

As demonstrated in Fig 4 the optimal solution obtained from CONCORDE, LKH-3 heuristic is an extension of LKH-2 for solving constrained traveling salesman and vehicle routing problems, our HPN model surpasses the current existing models and achieves the state-of-the-art solution for TSP50. Our model outperforms the graph pointer network by a wide margin, enhancing its performance for TSP50 from 5.959 to 5.706 without utilizing 2-opt, which is a success for the hybridization concept.

2. Large-scale experiments

For achieving the best possible generalization out of our model, instead of just using the cities’ coordinates as a context for both the graph encoder and the transform encoder, we replace it with a feature context that accelerates the training convergence for the large-scale problems. The feature context includes the vector context previously used by [17] concatenated with the Euclidean distance, where the vector context is just a subtraction operation between the coordinates of the currently selected city with the others.

Our feature extractor component does this job as illustrated in Fig 5. It is essential in the proposed HPN model since, it extracts the most relative information and feeds it to the encoder as a context. “Suppose that is a matrix with identical N rows. We define as the vector context. The j-th row of Xi is a vector pointing from node i to node j and X is the matrix that contains coordinates of all cities. We expanded this notion by adding the Euclidean distance between the currently selected city and other cities to the vector context.

[Figure omitted. See PDF.]

Fig 5. The feature extractor architecture combines both vector context with the Euclidian distance and outputs a Feature vector.

https://doi.org/10.1371/journal.pone.0260995.g005

The Euclidean distance between two points (xi1, xi2) and (xj1, xj2) is shown in (0.11):(0.11)

Where xi1, xi2, xj1 and xj2are the coordinates of city i and city j respectively.

Using the feature extractor, we train our large model in TSP50, validate with TSP500, 10 epochs, 1e-3 learning rate with leaning rate decay 0.96 and 100 for tanh clipping. Due to memory constraints we only solve 1k instances, some sample tours are shown in Fig 6, in which we solve TSP50-250-500-1000 with HPN+2opt. Table 2 summarizes our result, which shows that our model generalizes better than GPN. For the sake of a fair comparison with the state-of-the-art (i.e., GPN), we used 2opt local search technique to fine-tune the HPN’s tours. As shown in Table 2 and Fig 7, our models outperform the GPN, GPN+2opt, PN, AM, and 2opt models. Moreover, HPN+2opt returns near-optimal tours and generalizes better than the GPN on a large-scale instance.

[Figure omitted. See PDF.]

Fig 6. Sample tours for TSP250-500-750-1000 solved by HPN+2-opt.

https://doi.org/10.1371/journal.pone.0260995.g006

[Figure omitted. See PDF.]

Fig 7. Large-scale results from GPN, HPN, GPN+2opt, and HPN+2opt demonstrate that the gap between our model and GPN increases as the problem size increases.

https://doi.org/10.1371/journal.pone.0260995.g007

[Figure omitted. See PDF.]

Table 2. TSP’s result using hybrid pointer network model (HPN) vs baselines.

Each result is obtained by averaging on 1000 random TSP instances for larger instance and 10k instances for TSP50. Obj is the total tour length and the time reported is for solving 1k instances for larger TSP instances and 10k for TSP50.

https://doi.org/10.1371/journal.pone.0260995.t002

3. Benchmark instances results and statistical analysis

To validate our model against the standard benchmark instances, we employed varied-size instances from the public libraries TSPLIB [27] and World TSP. The benchmark dataset consists of 34 instances. The naming convention of instances consists of the first few letters of the instance location and the problem size n. For example, the instance eg7146 has 7146 points in Egypt. The instance sizes vary from 400 to 10639 nodes(cites). The normalized and actual tour length in km and the testing time in seconds are reported in Table 3.

[Figure omitted. See PDF.]

Table 3. Evaluation on real world TSPLIB dataset using HPN and HPN+2opt.

https://doi.org/10.1371/journal.pone.0260995.t003

To understand how HPN is performing compared to the GPN (the state-of-the-art network) in terms of the tour cost and testing time shown in Table 3, we did statistical comparison between these two networks. The statistical model should consider the dependency between the observations shown in Table 3.

In other words, we should realize that the tour cost of HPN and GPN for the same instance are correlated. Moreover, the testing times of same instance using the two networks are correlated as well. Therefore, we used LME regression to explain the variability in the tour cost and testing time (i.e. the responses) [24]. The LME regression model explains the variability of the tour cost and testing time as a function of the network used (i.e., HPN and GPN) and the size of the network. We used one indicator variable called “MODEL” to code the GPN and HPN.

In Table 4, we compared the tour cost for the HPN and GPN. A significance level of 0.05 was applied on all regression models. The p-value of the MODEL_1 indicator variable (i.e., GPN) is < .0001 and we conclude that the tour cost of the GPN is statistically significantly higher than the tour cost of the HPN. However, as shown in Table 5, the testing time of the HPN is statistically significantly higher than the testing time of the GPN.

[Figure omitted. See PDF.]

Table 4. The fixed effects coefficients of the model explaining the tour cost in terms of the HPN/GPN and the problem size.

https://doi.org/10.1371/journal.pone.0260995.t004

[Figure omitted. See PDF.]

Table 5. Fixed effects coefficients of the model explaining the testing time in terms of the HPN/GPN and the problem size.

https://doi.org/10.1371/journal.pone.0260995.t005

We repeat the same analysis for the tour cost and the testing time of the HPN+2opt and GPN+2opt. As shown in Tables 6 and 7, the HPN+2opt has statistically significantly lower testing time and tour cost. This is expected because HPN returns a better tour as an initial point in the solution space which helps 2opt to find a better final tour in less time. Finally, for the sake of completeness, we visualized four constructed tours using HPN + 2opt in Fig 8.

[Figure omitted. See PDF.]

Fig 8. Sample tours for benchmark instances.

https://doi.org/10.1371/journal.pone.0260995.g008

[Figure omitted. See PDF.]

Table 6. The fixed effects coefficients of the model explaining the tour cost in terms of the HPN+2opt/GPN+2opt and the problem size.

https://doi.org/10.1371/journal.pone.0260995.t006

[Figure omitted. See PDF.]

Table 7. The fixed effects coefficients of the model explaining the testing time in terms of the HPN+2opt/GPN+2opt and the problem size.

https://doi.org/10.1371/journal.pone.0260995.t007

VI. Conclusion and future work

In this work, a hybrid pointer network (HPN) is proposed for tackling both small-scale and large-scale problems. We demonstrate that the hybrid concept with a graph-based method is successful in improving the model performance for both scales. We used REINFORCE with Rollout Baseline to train our model. Our results show that our model outperforms the traditional graph pointer network with a significant margin, resulting in improved model generalization. Our model is still struggling to find the optimal solution for larger instances. Finding the optimal solution for larger instances is challenging so this will be our future direction.

Our future work, we will attempt to find a robust architecture to improve the quality and the time of solutions for large-scale problems, resulting in better model generalization. We also want to tackle combinatorial problems with constraints, which will be an important direction for future study.

Acknowledgments

This research was supported (partially or fully) by the Motor Accident Insurance Commission (MAIC) Queensland.The views expressed herein are those of the authors and are not necessarily those of the MAIC.

Citation: Stohy A, Abdelhakam H-T, Ali S, Elhenawy M, Hassan AA, Masoud M, et al. (2021) Hybrid pointer networks for traveling salesman problems optimization. PLoS ONE 16(12): e0260995. https://doi.org/10.1371/journal.pone.0260995

References

1. Garey M.R. and Johnson D.S., Computers and intractability. Vol. 174. 1979: freeman San Francisco.

2. Golden B., et al., Approximate traveling salesman algorithms. 1980. 28(3-part-ii): p. 694–711.

3. Dai H., et al., Learning combinatorial optimization algorithms over graphs. 2017.

4. Christofides N., Worst-case analysis of a new heuristic for the travelling salesman problem. 1976, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group. pmid:1069364

5. Voudouris C. and Tsang E.J.E.j.o.o.r., Guided local search and its application to the traveling salesman problem. 1999. 113(2): p. 469–499.

6. Helsgaun K.J.E.j.o.o.r., An effective implementation of the Lin–Kernighan traveling salesman heuristic. 2000. 126(1): p. 106–130.

7. Applegate D.L., et al., The traveling salesman problem. 2011: Princeton university press.

8. Bengio Y., Lodi A., and Prouvost A.J.E.J.o.O.R., Machine learning for combinatorial optimization: a methodological tour d’horizon. 2021. 290(2): p. 405–421.

9. Chen M., et al., Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search. 2020.

10. Vinyals O., Fortunato M., and Jaitly N.J.a.p.a., Pointer networks. 2015. pmid:26052514

11. Sutskever I., Vinyals O., and Le Q.V. Sequence to sequence learning with neural networks. in Advances in neural information processing systems. 2014.

12. Hochreiter S. and Schmidhuber J.J.N.c, Long short-term memory. 1997. 9(8): p. 1735–1780.

13. Vaswani A., et al. Attention is all you need. in Advances in neural information processing systems. 2017.

14. Mnih V., et al. Asynchronous methods for deep reinforcement learning. in International conference on machine learning. 2016. PMLR.

15. Kool W., Van Hoof H., and Welling M.J.a.p.a., Attention, learn to solve routing problems! 2018.

16. Kool W., van Hoof H., and Welling M., Buy 4 REINFORCE Samples, Get a Baseline for Free! 2019.

17. Ma Q., et al., Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. 2019.

18. Joshi C.K., Laurent T., and Bresson X.J.a.p.a., An efficient graph convolutional network technique for the travelling salesman problem. 2019.

19. Deudon M., et al. Learning heuristics for the tsp by policy gradient. in International conference on the integration of constraint programming, artificial intelligence, and operations research. 2018. Springer.

20. Bello I., et al., Neural combinatorial optimization with reinforcement learning. 2016.

21. Wu Y., et al., Learning Improvement Heuristics for Solving Routing Problems. 2021.

22. Williams R.J.J.M.l., Simple statistical gradient-following algorithms for connectionist reinforcement learning. 1992. 8(3): p. 229–256.

23. Sutton R.S. and Barto A.G., Reinforcement learning: An introduction. 2018: MIT press.

24. Lo S. and Andrews S.J.F.i.p., To transform or not to transform: Using generalized linear mixed models to analyse reaction time data. 2015. 6: p. 1171. pmid:26300841

25. Rennie S.J., et al. Self-critical sequence training for image captioning. in Proceedings of the IEEE conference on computer vision and pattern recognition. 2017.

26. Bresson X. and Laurent T.J.a.p.a., The Transformer Network for the Traveling Salesman Problem. 2021.

27. Reinelt G., TSPLIB—A Traveling Salesman Problem Library. INFORMS Journal on Computing, 1991. 3(4): p. 376–384.