@article {10.3844/jcssp.2012.1749.1758,
article_type = {journal},
title = {A Gaussian Process Regression Model for the Traveling Salesman Problem},
author = {Kongkaew, Wanatchapong and Pichitlamken, Juta},
volume = {8},
number = {10},
year = {2012},
month = {Aug},
pages = {1749-1758},
doi = {10.3844/jcssp.2012.1749.1758},
url = {https://thescipub.com/abstract/jcssp.2012.1749.1758},
abstract = {Problem statement: Traveling Salesman Problem (TSP) is a famous NP hard problem.  Many approaches have been proposed up to date for solving TSP.  We consider a TSP tour as a dependent variable and its corresponding distance as an independent variable.  If a predictive function can be formulated from arbitrary sample tours, the optimal tour may be predicted from this function.  Approach: In this study, a combined procedure of the Nearest Neighbor (NN) method, Gaussian Process Regression (GPR) and the iterated local search is proposed to solve a deterministic symmetric TSP with a single salesman. The first tour in the sample is constructed by the nearest neighbor algorithm and it is used to construct other tours by the random 2-exchange swap.  These tours and their total distances are training data for a Gaussian process regression model.  A GPR solution is further improved with the iterated 2-opt method.  In the numerical experiments, our algorithm is tested on many TSP instances and it is compared with the Genetic Algorithm (GA) and the Simulated Annealing (SA) algorithm.  Results: The proposed method can find good TSP tours within a reasonable computational time for a wide range of TSP test problems.  In some cases, it outperforms GA and SA.  Conclusion: Our proposed algorithm is promising for solving the TSP.},
journal = {Journal of Computer Science},
publisher = {Science Publications}
}