Research Article Open Access

A Gaussian Process Regression Model for the Traveling Salesman Problem

Wanatchapong Kongkaew1 and Juta Pichitlamken1
  • 1 Kasetsart University, Thailand

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 of Computer Science
Volume 8 No. 10, 2012, 1749-1758

DOI: https://doi.org/10.3844/jcssp.2012.1749.1758

Submitted On: 27 April 2012 Published On: 30 August 2012

How to Cite: Kongkaew, W. & Pichitlamken, J. (2012). A Gaussian Process Regression Model for the Traveling Salesman Problem. Journal of Computer Science, 8(10), 1749-1758. https://doi.org/10.3844/jcssp.2012.1749.1758

  • 3,201 Views
  • 3,038 Downloads
  • 9 Citations

Download

Keywords

  • Gaussian process regression
  • nearest neighbor
  • iterated 2-opt algorithm
  • genetic algorithm
  • simulated annealing
  • traveling salesman problem