Journal of Computer Science

A Gaussian Process Regression Model for the Traveling Salesman Problem

Wanatchapong Kongkaew and Juta Pichitlamken

DOI : 10.3844/jcssp.2012.1749.1758

Journal of Computer Science

Volume 8, Issue 10

Pages 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.

Copyright

© 2012 Wanatchapong Kongkaew and Juta Pichitlamken. 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.