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 条
  • [21] Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem
    Karapetyan, D.
    Gutin, G.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 219 (02) : 234 - 251
  • [22] Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem
    Martinovic, Goran
    Bajer, Drazen
    ADVANCES IN ELECTRICAL AND COMPUTER ENGINEERING, 2012, 12 (01) : 25 - 32
  • [23] Local elimination in the traveling salesman problem
    Cook, William
    Helsgaun, Keld
    Hougardy, Stefan
    Schroeder, Rasmus T.
    MATHEMATICAL PROGRAMMING COMPUTATION, 2024, : 599 - 628
  • [24] A 2opt-DPX genetic local search for solving symmetric traveling salesman problem
    Ghoseiri, K.
    Sarhadi, H.
    2007 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT, VOLS 1-4, 2007, : 903 - 906
  • [25] Discrete Differential Evolution with Local Search to Solve the Traveling Salesman Problem: Fundamentals and Case Studies
    Sauer, Joao Guilherme
    Coelho, Leandro dos Santos
    PROCEEDINGS OF THE 2008 7TH IEEE INTERNATIONAL CONFERENCE ON CYBERNETIC INTELLIGENT SYSTEMS, 2008, : 299 - 304
  • [26] A Random Restart Local Search Matheuristic for the Flying Sidekick Traveling Salesman Problem
    Dell'Amico, Mauro
    Montemanni, Roberto
    Novellani, Stefano
    2021 THE 8TH INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND APPLICATIONS-EUROPE, ICIEA 2021-EUROPE, 2021, : 205 - 209
  • [27] A Greedy-Genetic Local-Search Heuristic for the Traveling Salesman Problem
    Rashid, Mohammad Harun
    Mosteiro, Miguel A.
    2017 15TH IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING WITH APPLICATIONS AND 2017 16TH IEEE INTERNATIONAL CONFERENCE ON UBIQUITOUS COMPUTING AND COMMUNICATIONS (ISPA/IUCC 2017), 2017, : 868 - 872
  • [28] Composite Algorithm Based on Clarke - Wright and Local Search for the Traveling Salesman Problem
    Komarudin
    Parhusip, Sandiego F.
    2019 5TH INTERNATIONAL CONFERENCE ON INDUSTRIAL AND BUSINESS ENGINEERING (ICIBE 2019), 2019, : 87 - 90
  • [29] An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs
    Rey, Carlos
    Toth, Paolo
    Vigo, Daniele
    2020 39TH INTERNATIONAL CONFERENCE OF THE CHILEAN COMPUTER SCIENCE SOCIETY (SCCC), 2020,
  • [30] AN IMPROVED ARTIFICIAL BEE COLONY ALGORITHM WITH LOCAL SEARCH FOR TRAVELING SALESMAN PROBLEM
    Kocer, Hasan Erdinc
    Akca, Melike Ruhan
    CYBERNETICS AND SYSTEMS, 2014, 45 (08) : 635 - 649
12345