Avtomatika i Telemekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Avtomatika i Telemekhanika, 2019, Issue 11, Pages 155–172
DOI: https://doi.org/10.1134/S0005231019110096
(Mi at15165)
 

This article is cited in 4 scientific papers (total in 4 papers)

Optimization, System Analysis, and Operations Research

A hybrid exact algorithm for the asymmetric traveling salesman problem: construction and a statistical study of computational efficiency

G. N. Zhukovaa, M. V. Ul'yanovbc, M. I. Fomicheva

a National Research University Higher School of Economics, Moscow, Russia
b Moscow State University, Moscow, Russia
c Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
Full-text PDF (851 kB) Citations (4)
References:
Abstract: We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin–Kernighan–Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show that using an approximate solution found with the Lin–Kernighan–Helsgaun algorithm can significantly reduce the search time for the exact solution to the traveling salesman problem using the branch-and-bound method for problems from a certain class. We construct a prediction of the search time for the exact solution by the branchand- bound method and by the hybrid algorithm. A computational experiment has shown that the proportion of tasks solved faster by the hybrid algorithm than by the branch-and-bound method grows with increasing problem dimension.
Keywords: traveling salesman problem, branch-and-bound method, approximation of a probability distribution, quantile of a probability distribution, probabilistic forecasting of time.
Funding agency Grant number
Russian Science Foundation 17-19-01665
This work was supported by the Russian Science Foundation, project no. 17-19-01665.

Received: 14.12.2018
Revised: 04.04.2019
Accepted: 25.04.2019
English version:
Automation and Remote Control, 2019, Volume 80, Issue 11, Pages 2054–2067
DOI: https://doi.org/10.1134/S0005117919110092
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: G. N. Zhukova, M. V. Ul'yanov, M. I. Fomichev, “A hybrid exact algorithm for the asymmetric traveling salesman problem: construction and a statistical study of computational efficiency”, Avtomat. i Telemekh., 2019, no. 11, 155–172; Autom. Remote Control, 80:11 (2019), 2054–2067
Citation in format AMSBIB
\Bibitem{ZhuUlyFom19}
\by G.~N.~Zhukova, M.~V.~Ul'yanov, M.~I.~Fomichev
\paper A hybrid exact algorithm for the asymmetric traveling salesman problem: construction and a statistical study of computational efficiency
\jour Avtomat. i Telemekh.
\yr 2019
\issue 11
\pages 155--172
\mathnet{http://mi.mathnet.ru/at15165}
\crossref{https://doi.org/10.1134/S0005231019110096}
\elib{https://elibrary.ru/item.asp?id=41710600}
\transl
\jour Autom. Remote Control
\yr 2019
\vol 80
\issue 11
\pages 2054--2067
\crossref{https://doi.org/10.1134/S0005117919110092}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000496295400009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85074986424}
Linking options:
  • https://www.mathnet.ru/eng/at15165
  • https://www.mathnet.ru/eng/at/y2019/i11/p155
  • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Avtomatika i Telemekhanika
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024