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 条
  • [41] A Novel Sparrow Search Algorithm for the Traveling Salesman Problem
    Wu, Changyou
    Fu, Xisong
    Pei, Junke
    Dong, Zhigui
    IEEE ACCESS, 2021, 9 : 153456 - 153471
  • [42] Discrete Differentiated Creative Search for traveling salesman problem
    Xu, Qi
    Xia, Kewen
    Chu, Xiaoyu
    APPLIED SOFT COMPUTING, 2025, 174
  • [43] An Investigation of Hybrid Tabu Search for the Traveling Salesman Problem
    Xu, Dan
    Weise, Thomas
    Wu, Yuezhong
    Laessig, Joerg
    Chiong, Raymond
    BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2015, 2015, 562 : 523 - 537
  • [44] A similarity-based mechanism to control genetic algorithm and local search hybridization to solve traveling salesman problem
    Marjan Kuchaki Rafsanjani
    Sadegh Eskandari
    Arsham Borumand Saeid
    Neural Computing and Applications, 2015, 26 : 213 - 222
  • [45] Hybridizing Different Local Search Algorithms with Each Other and Evolutionary Computation: Better Performance on the Traveling Salesman Problem
    Wu, Yuezhong
    Weise, Thomas
    Liu, Weichen
    PROCEEDINGS OF THE 2016 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'16 COMPANION), 2016, : 57 - 58
  • [46] A similarity-based mechanism to control genetic algorithm and local search hybridization to solve traveling salesman problem
    Rafsanjani, Marjan Kuchaki
    Eskandari, Sadegh
    Saeid, Arsham Borumand
    NEURAL COMPUTING & APPLICATIONS, 2015, 26 (01) : 213 - 222
  • [47] The balanced traveling salesman problem
    Larusic, John
    Punnen, Abraham P.
    COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (05) : 868 - 875
  • [48] Multi-restart iterative search for the pickup and delivery traveling salesman problem with FIFO loading
    Lu, Yongliang
    Benlic, Una
    Wu, Qinghua
    COMPUTERS & OPERATIONS RESEARCH, 2018, 97 : 18 - 30
  • [49] A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem
    Nikolakopoulos, Athanassios
    Sarimveis, Haralambos
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177 (03) : 1911 - 1929
  • [50] A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks
    Urrutia, Sebastian
    Milanes, Anolan
    Lokketangen, Arne
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2015, 22 (01) : 61 - 75
12345