Improving local search for the traveling salesman problem

被引：0

作者：

Misevicius, Alfonsas ^{[1
]}

Ostreika, Armantas ^{[1
]}

Simaitis, Antanas ^{[1
]}

Zilevicius, Vilius ^{[1
]}

机构：

[1] Kaunas Univ Technol, Dept Multimedia Engn, LT-51368 Kaunas, Lithuania

来源：

INFORMATION TECHNOLOGY AND CONTROL | 2007年 / 36卷 / 02期

关键词：

traveling salesman problem; heuristics; local search; fast descent-random ascent strategy;

D O I：

暂无

中图分类号：

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

学科分类号：

0812 ;

摘要：

The subject of this paper is the improving of local search for the traveling salesman problem (TSP). In particular, a so-called fast descent-random ascent (FDRA) strategy is proposed. The FDRA approach is based on the fast-modified 2-opt algorithm combined with certain perturbation (random ascent) procedures. The results obtained from the experiments demonstrate that the new improved local search strategy is better than the other local search algorithms. This approach may also be applied to other combinatorial optimization problems.

引用

页码：187 / 195

页数：9

共 50 条

[1] EXPERIMENTS WITH LOCAL SEARCH HEURISTICS FOR THE TRAVELING SALESMAN PROBLEM
Misevicius, Alfonsas
Blazinskas, Andrius
INFORMATION TECHNOLOGIES' 2010, 2010, : 47 - +
[2] Dynamics of Local Search Trajectory in Traveling Salesman Problem
Weiqi Li
Journal of Heuristics, 2005, 11 : 507 - 524
[3] Novel Local Search Method for the Traveling Salesman Problem
黄文奇
王磊
Journal of Southwest Jiaotong University, 2005, (01) : 1 - 4
[4] Dynamics of local search trajectory in traveling salesman problem
Li, WQ
JOURNAL OF HEURISTICS, 2005, 11 (5-6) : 507 - 524
[5] Modified Local Search Heuristics for the Symmetric Traveling Salesman Problem
Misevicius, Alfonsas
Blazinskas, Andrius
Lenkevicius, Antanas
INFORMATION TECHNOLOGY AND CONTROL, 2013, 42 (03): : 217 - 230
[6] Exponential neighbourhood local search for the traveling salesman problem
Gutin, G
COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (04) : 313 - 320
[7] BEE COLONY OPTIMIZATION WITH LOCAL SEARCH FOR TRAVELING SALESMAN PROBLEM
Wong, Li-Pei
Low, Malcolm Yoke Hean
Chong, Chin Soon
INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS, 2010, 19 (03) : 305 - 334
[8] Dynamics of local search heuristics for the traveling salesman problem
Li, WQ
Alidaee, B
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS, 2002, 32 (02): : 173 - 184
[9] Use of local search in the metric traveling salesman problem
Zhikharev S.A.
Kostyuk Yu.L.
Russian Physics Journal, 1999, 42 (3) : 351 - 355
[10] Breakout local search for the traveling salesman problem with job-times
Zou, Yuji
Hao, Jin-Kao
Wu, Qinghua
EXPERT SYSTEMS WITH APPLICATIONS, 2023, 225

← 1 2 3 4 5 →