A METHOD FOR ANALYZING SOLUTION SPACE OF TRAVELING SALESMAN PROBLEM BASED ON COMPLEX NETWORK

被引:0
作者
Rao, Weizhen [1 ,2 ]
Jin, Chun [1 ]
机构
[1] Dalian Univ Technol, Inst Syst Engn, 2 Linggong Rd, Dalian 116024, Peoples R China
[2] Shandong Univ Sci & Technol, Coll Econ & Management, Qingdao 266590, Peoples R China
来源
INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL | 2013年 / 9卷 / 09期
基金
中国国家自然科学基金;
关键词
Solution space; Traveling salesman problem; Complex network; Heuristic; Combinatorial optimization problems;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
In this paper, a complex network-based method for analyzing solution space of traveling salesman problem (TSP) is proposed. The aim is to analyze what properties the complex network corresponding to a good heuristic has and understand its behavior solving TSP from the new point of view. It is found that solution space of one heuristic for TSP is a classical complex system that can be analyzed by using complex network theory. The method framework includes two parts: constructing a complex network according to a specified heuristic and computing the related indexes of the complex network. Then the solution spaces of 2-opt, Or-opt, 3-opt and Lin-Kernighan are analyzed by using the method proposed in this paper. Our findings demonstrate that the complex networks corresponding to the good heuristics for solving TSP are similar to the small-world networks. According to the conclusion, three excellent heuristics are developed and evaluated to verify the effectiveness of the method.
引用
收藏
页码:3685 / 3700
页数:16
相关论文
共 50 条
[41]   A novel GRASP based on mixed k-opt method for the Traveling Salesman Problem [J].
Zheng Ming ;
Guo Hui ;
He Jie ;
Liu Guixia .
PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON EDUCATION, MANAGEMENT, COMPUTER AND SOCIETY, 2016, 37 :1808-1813
[42]   Optimization Models and Heuristic Method Based on Simulated Annealing Strategy for Traveling Salesman Problem [J].
Hao, Xu .
MECHANICAL ENGINEERING AND GREEN MANUFACTURING, PTS 1 AND 2, 2010, :1180-1184
[43]   Solution of the Job-Shop Scheduling Problem through the Traveling Salesman Problem. [J].
Anaya Fuentes, G. E. ;
Hernandez Gress, E. S. ;
Tuoh Mora, J. C. Seek ;
Medina Marin, J. .
REVISTA IBEROAMERICANA DE AUTOMATICA E INFORMATICA INDUSTRIAL, 2016, 13 (04) :430-437
[44]   An expanding self-organizing neural network for the traveling salesman problem [J].
Leung, KS ;
Jin, HD ;
Xu, ZB .
NEUROCOMPUTING, 2004, 62 :267-292
[45]   Solving Traveling Salesman Problem with Image-based Classification [J].
Miki, Shoma ;
Ebara, Hiroyuki .
2019 IEEE 31ST INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI 2019), 2019, :1118-1123
[46]   Improved Biogeography-Based Optimization for the Traveling Salesman Problem [J].
Wu, Jinping ;
Feng, Siling .
2017 2ND IEEE INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND APPLICATIONS (ICCIA), 2017, :166-171
[47]   Set-Based Differential Evolution for Traveling Salesman Problem [J].
Liu, Tao ;
Maeda, Michiharu .
2013 6TH INTERNATIONAL CONFERENCE ON INTELLIGENT NETWORKS AND INTELLIGENT SYSTEMS (ICINIS), 2013, :107-110
[48]   Enhancements to Patrolling Operations based on Dubins' Traveling Salesman Problem [J].
Ghadiry, Walaaeldin ;
Habibi, Lalal ;
Aghdam, Amir G. ;
Zhang, Youmin M. .
2016 WORLD AUTOMATION CONGRESS (WAC), 2016,
[49]   A CONVEX HULL BASED ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM [J].
Nuriyeva, F. ;
Kutucu, H. .
TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2025, 15 (02) :412-420
[50]   A distance matrix based algorithm for solving the traveling salesman problem [J].
Wang, Shengbin ;
Rao, Weizhen ;
Hong, Yuan .
OPERATIONAL RESEARCH, 2020, 20 (03) :1505-1542