A Method to Search the Optimal Hamiltonian Cycle with a Set of Approximations for Travelling Salesman Problem

被引：0

作者：

Wang, Y. ^{[1
]}

机构：

[1] North China Elect Power Univ, Sch Renewable Energy, Beijing 102206, Peoples R China

来源：

PROCEEDINGS OF THE 2015 INTERNATIONAL CONFERENCE ON ELECTRICAL, AUTOMATION AND MECHANICAL ENGINEERING (EAME 2015) | 2015年 / 13卷

关键词：

travelling salesman problem; optimal hamiltonian cycle; frequency graph; sparse graph; depth-first graph search algorithm; OPTIMIZATION;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The objective of travelling salesman problem (TSP) is to find the optimal Hamiltonian cycle (OHC) and it has been proven to be NP-complete. A heuristic method is proposed for TSP. It is realized with four steps. A set of approximations are computed with the 2-opt move algorithm firstly. Secondly, a frequency graph is computed with the set of approximations. A sparse graph with small number of edges is generated in the third step. At last, the depth-first graph search algorithm is used to find the OHC or a better approximation with the sparse graph. The experimental results show that the OHC of most of the TSP instances are searched within an acceptable computation time.

引用

页码：671 / 674

页数：4

共 14 条

[1]

Applegate David L, 2006, TRAVELING SALESMAN P

[2] Cut-and-solve: An iterative search strategy for combinatorial optimization problems [J].

Climer, Sharlee ;

Zhang, Weixiong .

ARTIFICIAL INTELLIGENCE, 2006, 170 (8-9) :714-738

[3] A METHOD FOR SOLVING TRAVELING-SALESMAN PROBLEMS [J].

CROES, GA .

OPERATIONS RESEARCH, 1958, 6 (06) :791-812

[4] A comparison of lower bounds for the symmetric circulant traveling salesman problem [J].

de Klerk, Etienne ;

Dobre, Cristian .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (16) :1815-1826

[5] Approximation algorithms for TSP with neighborhoods in the plane [J].

Dumitrescu, A ;

Mitchell, JSB .

JOURNAL OF ALGORITHMS, 2003, 48 (01) :135-159

[6]

Eppstein David, 2007, Journal of Graph Algorithms and Applications, V11, P61, DOI 10.7155/jgaa.00137

[7]

Helsgaun K., 2012, EFFECTIVE IMPLEMENTA

[8]

Jia L., 2005, P 37 ANN ACM S THEOR, P386, DOI [DOI 10.1145/1060590.1060649, 10.1145/1060590.1060649.1,5,28,29, DOI 10.1145/1060590.1060649.1,5,28,29]

[9]

Johnson D. S., 2004, COMBINATORIAL OPTIMI, V12, P445

[10]

Levine M.S., 2000, ACM J EXP ALGO RITHM, V5, P1

← 1 2 →