An Exact Parallel Algorithm for Traveling Salesman Problem

被引：0
作者：
Burkhovetskiy, V. [1 ]
Steinberg, B. [1 ]
机构：
[1] Southern Fed Univ, Inst Math Mech & Comp Sci, Milchakova St 8, Rostov Na Donu 344090, Russia
来源：
CEE-SECR'17: PROCEEDINGS OF THE 13TH CENTRAL & EASTERN EUROPEAN SOFTWARE ENGINEERING CONFERENCE IN RUSSIA | 2017年
关键词：
parallel computing; tree traversal; branch-and-bound; traveling salesman problem;
D O I：
10.1145/3166094.3166108
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We describe an exact algorithm for traveling salesman problem based on simplified branch-and-bound algorithm developed by E. Balas and N. Christofides, parallelized with OpenMP on a multi-core processor. It has shown better performance than algorithms in preceding articles and works. Our article is intended for people who use parallel programming technologies, deal with mathematical optimization problems, have interest in perspective algorithms for bioinformatics or NP-hard problems.
引用
收藏
页数：5
相关论文
共 50 条
  • [31] An Efficient Genetic Algorithm for the Traveling Salesman Problem
    Sun, Guangfu
    Li, Chengjun
    Zhu, Jiacheng
    Li, Yanpeng
    Liu, Wei
    COMPUTATIONAL INTELLIGENCE AND INTELLIGENT SYSTEMS, 2010, 107 : 108 - 116
  • [32] An Efficient and Scalable Algorithm for the Traveling Salesman Problem
    Ye, Chen
    Yang, Zhongcheng
    Yan, Tianxing
    2014 5TH IEEE INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND SERVICE SCIENCE (ICSESS), 2014, : 335 - 339
  • [33] Discrete Bat Algorithm for Traveling Salesman Problem
    Jiang, Zhao
    2016 3RD INTERNATIONAL CONFERENCE ON INFORMATION SCIENCE AND CONTROL ENGINEERING (ICISCE), 2016, : 343 - 347
  • [34] A quantum heuristic algorithm for the traveling salesman problem
    Jeongho Bang
    Junghee Ryu
    Changhyoup Lee
    Seokwon Yoo
    James Lim
    Jinhyoung Lee
    Journal of the Korean Physical Society, 2012, 61 : 1944 - 1949
  • [35] A memetic algorithm for symmetric traveling salesman problem
    Ghoseiri, Keivan
    Sarhadi, Hassan
    INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE AND ENGINEERING MANAGEMENT, 2008, 3 (04) : 275 - 283
  • [36] Discrete komodo algorithm for traveling salesman problem
    Jati, Gilang Kusuma
    Kuwanto, Garry
    Hashmi, Tahir
    Widjaja, Herman
    APPLIED SOFT COMPUTING, 2023, 139
  • [37] An Improved Hybrid Algorithm for Traveling Salesman Problem
    Bai, Qiuying
    Li, Guizhi
    Sun, Qiheng
    2015 8TH INTERNATIONAL CONFERENCE ON BIOMEDICAL ENGINEERING AND INFORMATICS (BMEI), 2015, : 806 - 809
  • [38] A parallel immune algorithm for traveling salesman problem and its application on cold rolling scheduling
    Zhao, Jun
    Liu, Quanli
    Wang, Wei
    Wei, Zhuoqun
    Shi, Peng
    INFORMATION SCIENCES, 2011, 181 (07) : 1212 - 1223
  • [39] An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem
    Minh Anh Nguyen
    Hai Long Luong
    Minh Hoàng Hà
    Ha-Bang Ban
    4OR, 2023, 21 : 609 - 637
  • [40] A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency
    G. N. Zhukova
    M. V. Ul’yanov
    M. I. Fomichev
    Automation and Remote Control, 2019, 80 : 2054 - 2067
12345