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 条
  • [31] Solving traveling salesman problem by using a local evolutionary algorithm
    Xuan, W
    Li, YX
    2005 IEEE International Conference on Granular Computing, Vols 1 and 2, 2005, : 318 - 321
  • [32] Integrating Local Search Methods in Metaheuristic Algorithms for Combinatorial Optimization: The Traveling Salesman Problem and its Variants
    Jeremiah, Isuwa
    Abdullahi, Mohammed
    Yusuf, Sahabi Ali
    Idris, Muhammad Nuruddeen
    Garko, Baffa Shuaibu
    Haruna, Muhammad Yusuf
    2022 IEEE NIGERIA 4TH INTERNATIONAL CONFERENCE ON DISRUPTIVE TECHNOLOGIES FOR SUSTAINABLE DEVELOPMENT (IEEE NIGERCON), 2022, : 388 - 392
  • [33] NeuralGLS: learning to guide local search with graph convolutional network for the traveling salesman problem
    Sui, Jingyan
    Ding, Shizhe
    Xia, Boyang
    Liu, Ruizhi
    Bu, Dongbo
    NEURAL COMPUTING & APPLICATIONS, 2023, 36 (17) : 9687 - 9706
  • [34] An iterated local search for the Traveling Salesman Problem with release dates and completion time minimization
    Archetti, Claudia
    Feillet, Dominique
    Mor, Andrea
    Speranza, M. Grazia
    COMPUTERS & OPERATIONS RESEARCH, 2018, 98 : 24 - 37
  • [35] Solving Traveling Salesman Problem by Using an Evolutionary Algorithm Based on the Local Search Strategy
    Wang, Xuan
    Zhang, Gan-nian
    Li, Yuan-xiang
    ADVANCES IN NEURAL NETWORKS - ISNN 2009, PT 2, PROCEEDINGS, 2009, 5552 : 564 - +
  • [36] A Learning-Based Iterated Local Search Algorithm for Solving the Traveling Salesman Problem
    Karimi-Mamaghan, Maryam
    Pasdeloup, Bastien
    Mohammadi, Mehrdad
    Meyer, Patrick
    OPTIMIZATION AND LEARNING, OLA 2021, 2021, 1443 : 45 - 61
  • [37] EFFICIENT LOCAL SEARCH WITH SEARCH SPACE SMOOTHING - A CASE-STUDY OF THE TRAVELING SALESMAN PROBLEM (TSP)
    GU, J
    HUANG, XF
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1994, 24 (05): : 728 - 735
  • [38] Fixed Set Search Applied to the Traveling Salesman Problem
    Jovanovic, Raka
    Tuba, Milan
    Voss, Stefan
    HYBRID METAHEURISTICS (HM 2019), 2019, 11299 : 63 - 77
  • [39] Group Search Optimization to solve Traveling Salesman Problem
    Akhand, M. A. H.
    Junaed, A. B. M.
    Hossain, Md. Forhad
    Murase, K.
    2012 15TH INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION TECHNOLOGY (ICCIT), 2012, : 72 - 77
  • [40] A Memetic Hunting Search Algorithm for the Traveling Salesman Problem
    Agharghor, Amine
    Riffi, Mohammed Essaid
    Chebihi, Faycal
    2016 4TH IEEE INTERNATIONAL COLLOQUIUM ON INFORMATION SCIENCE AND TECHNOLOGY (CIST), 2016, : 206 - 209
12345