• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • О некоторых методах решения обобщенной задачи коммивояжера
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
April 30, 2026
HSE Researchers Compile Scientific Database for Studying Childrens Eating Habits
The database created at HSE University can serve as a foundation for studying children’s eating habits. This is outlined in the study ‘The Influence of Age, Gender, and Social-Role Factors on Children’s Compliance with Age-Based Nutritional Norms: An Experimental Study Using the Dish-I-Wish Web Application.’ The work has been carried out as part of the HSE Basic Research Programme and was presented at the XXVI April International Academic Conference named after Evgeny Yasin.
April 30, 2026
New Foresight Centre Study Identifies the Most Destructive Global Trends for Humankind
A team of researchers from the HSE International Research and Educational Foresight Centre has examined how global trends affect the quality of human life—from life expectancy to professional fulfilment. The findings of the study titled ‘Human Capital Transformation under the Influence of Global Trends’ were published in Foresight.
April 28, 2026
Scientists Develop Algorithm for Accurate Financial Time Series Forecasting
Researchers at the HSE Faculty of Computer Science benchmarked more than 200,000 model configurations for predicting financial asset prices and realised volatility, showing that performance can be improved by filtering out noise at specific frequencies in advance. This technique increased accuracy in 65% of cases. The authors also developed their own algorithm, which achieves accuracy comparable to that of the best models while requiring less computational power. The study has been published in Applied Soft Computing.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

О некоторых методах решения обобщенной задачи коммивояжера

С. 20–21.
Gordenko M.
Language: Russian
Full text
Text on another site
Keywords: задача коммивояжеразадача маршрутизации транспорта

In book

Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского
МИЭМ НИУ ВШЭ, 2018.
Similar publications
Интеграция метаэвристических алгоритмов решения несимметричной задачи коммивояжёра с методом ветвей и границ
Fomichev M., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47–54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Added: March 22, 2020
Коррeляция сложности и времени решения TSP
Головешкин В. А., Zhukova G., Ulyanov M. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа порожденных вершин дерева решений и физического времени работы программной реализации метода ветвей и границ для задачи коммивояжера (TSP). На основе результатов вычислительного эксперимента получено приближенное соотношение между числом  порожденных вершин (сложность индивидуальной TSP) и физическим временем. Предлагается использовать это эмпирическое соотношение для прогнозирования времени работы программы, решающей TSP с числом «городов» больше 40. ...
Added: March 22, 2020
Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра
Ulyanov M., Fomichev M., Информационные технологии 2019 Т. 25 № 10 С. 590–595
The algorithm that implements the Branch and Bound method for solving the Traveling Salesman Problem is one of the common exact algorithms for solving it. Metaheuristic algorithms for solving this problem do not guarantee obtaining an exact solution, however they work "quickly". In order to reduce the nodes number of the generated decision tree in ...
Added: February 16, 2020
A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency
Zhukova G., Ulyanov M., Fomichev M., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067
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 ...
Added: November 24, 2019
Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности
Zhukova G., Ulyanov M., Fomichev M., Автоматика и телемеханика 2019 № 11 С. 155–172
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 ...
Added: November 10, 2019
Exact time-efficient combined algorithm for solving the asymmetric traveling salesman problem
Zhukova G., Ulyanov M., Fomichev M., Business Informatics 2018 Vol. 45 No. 3 P. 20–28
For practical, important tasks in the fi elds of economics and logistics, as well as in a number of technical applications, it becomes necessary to solve the traveling salesman problem (TSP). Quite often, the features of these problems lead to the traveling salesman problem in asymmetric formulation (asymmetric traveling salesman problem, ATSP). Moreover, in some practical applications it ...
Added: October 18, 2018
Вероятностный прогноз сложности индивидуальных задач коммивояжера на основе идентификации распределения сложности по экспериментальным данным // Автоматика и телемеханика
Ulyanov M., Zhukova G., Fomichev M. et al., Автоматика и телемеханика 2018 № 7 С. 149–166
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family ...
Added: July 16, 2018
Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev et al., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296–1310
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family ...
Added: July 16, 2018
Куда послать коммивояжера?
Beresneva E., Gordenko M., Открытые системы. СУБД 2018 № 01 С. 40–42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Added: June 22, 2018
Задача маршрутизации с ограничением по грузоподъемности
Beresneva E., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского.: МИЭМ НИУ ВШЭ, 2018. С. 17–18.
В материалах конференции студентов, аспирантов и молодых специалистов представлены тезисы докладов по следующим направлениям: математика и компьютерное моделирование; информационно-коммуникационные технологии; автоматизация проектирования, банки данных и знаний, интеллектуальные системы; компьютерные образовательные продукты; информационная безопасность; электроника и приборостроение; производственные технологии, нанотехнологии и новые материалы; инновационные технологии цифровой экономики; инновационные технологии в дизайне. Материалы конференции могут быть полезны для ...
Added: June 21, 2018
Экспериментальное исследование временных и точностных характеристик меметического алгоритма решения ассиметричной задачи коммивояжера в зависимости от входных параметров алгоритма
Gordenko M., Коротков Д. А., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского.: МИЭМ НИУ ВШЭ, 2018. С. 42–44.
В работе рассмотрен меметический алгоритм, являющий-ся комбинацией генетического алгоритма и алгоритмов ло-кального поиска решения ассиметричной задачи коммивоя-жера (A TSP). Приведена математическая постановка задачиA TSP . Кратко описан принцип работы меметического алгорит-ма. Проведено экспериментальное исследование временных и точностных характеристик меметического алгоритма на откры-той базе данных TSPLIB в зависимости от входных параметров с целью выявления оптимальных настроек алгоритма. ...
Added: June 5, 2018
Some approaches to solving the NP-hard Mixed Chinese Postman Problem
Maria Gordenko, Sergey Avdoshin, , in: Материалы пятой международной конференции «Актуальные проблемы системной и программной инженерии», сборник научных трудовVol. 1989: CEUR Workshop Proceedings.: M.: HSE, 2017. P. 272–290.
The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which ...
Added: November 18, 2017
Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP
Головешкин В. А., Zhukova G., Ulyanov M. et al., Современные информационные технологии и ИТ-образование 2015 Т. 2 № 11 С. 151–159
Сравниваются ресурсные характеристики модифицированного и классического МВГ для TSP. На основании экспериментальных результатов показано, что по величине затраченного на поиск решения времени модифицированный вариант МВГ эффективнее классического. Исследована стохастическая зависимость между временем работы каждого из двух исследуемых вариантов МВГ при фиксированном порядке матрицы стоимостей. Также описана зависимость затраченной памяти и времени работы алгоритма от порядка ...
Added: October 9, 2017
Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа
Zhukova G., Ulyanov M., Fomichev M. et al., Современные информационные технологии и ИТ-образование 2016 Т. 12 № 3-2 С. 131–137
It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the ...
Added: October 5, 2017
Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера
Zhukova G., Ulyanov M., Fomichev M. et al., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 7–12
The complexity of solving a particular travelling saleman problem is studied. Complexity is a number of nodes of the decision tree, when a particular problem is being solved by the branch and bound algorithm. A probability distribution of the logarithm of the complexity of a particular TSP is approximately normal. Parameters of the linear transformation ...
Added: October 5, 2017
Об одном обобщённом представлении классов индивидуальных задач коммивояжёра
Zhukova G., Ulyanov M., Fomichev M. et al., Автоматизация. Cовременные технологии 2016 № 10 С. 22–29
The article is devoted to a new generic representation of classes of particular travelling salesman problems (TSP), we call it "index number matrix". This representation is intended for a separation of problem classes of similar complicity. This result is destined to solve a problem of particular TSP’s complicity prediction. Two hypotheses are given regarding to ...
Added: October 5, 2017
The Mixed Chinese Postman Problem
M.K. Gordenko, S.M. Avdoshin, Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 4 P. 107–122
The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which ...
Added: September 27, 2017
ОЦЕНКА ПАРАМЕТРОВ РАСПРЕДЕЛЕНИЯ ЛОГАРИФМА СЛОЖНОСТИ ЗАДАЧИ КОММИВОЯЖЕРА
Ulyanov M., Fomichev M., Головешкин В. А. et al., 2017 Т. 13 № 1 С. 19–24
The complexity of the individual traveling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions ...
Added: September 26, 2017
Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера
Fomichev M., Ulyanov M., Головешкин В. А. et al., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131–137
It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the ...
Added: August 19, 2017
Особый случай классического метода ветвей и границ для задачи коммивояжёра // Вестник Волжской государственной академии водного транспорта
Fomichev M., Вестник Волжской государственной академии водного транспорта 2017 № 49 С. 68–78
The classical Branch and Bound algorithm for the travelling salesman problem, presented in 1963 by Little J.D.C., Murty K.G., Sweeney D.W., Karel C., is nowadays one of the most popular algorithms to find a minimum Hamiltonian cycle in a complete graph. There are many literature references having an algorithm pseudocode with comments. However, there are ...
Added: August 19, 2017
Transformation of the Mixed Chinese Postman Problem in multigraph into the Asymmetric Travelling Salesman Problem
Maria K. Gordenko, Avdoshin S. M., International Journal of Open Information Technologies 2017 Vol. 5 No. 6 P. 6–11
The Mixed Chinese Postman Problem (MCPP) is to find a minimum shortest tour of given graph or multigraph traversed each edge or arc at least once. The problem is NP-hard. However, mixed case of the problem has many potentially useful applications, including delivering of something, robot exploration, web site usability, etc. In this article, we ...
Added: June 1, 2017
Pareto-optimal Algorithms for Metric TSP: Experimental Research
Ekaterina N. Beresneva (Chirkova), Sergey M. Avdoshin, International Journal of Open Information Technologies 2017 Vol. 5 No. 5 P. 16–24
The Travelling Salesman Problem (TSP) is a fundamental task in combinatorial optimization. A special case of the TSP is Metric TSP, where the triangle inequality holds. Solutions of the TSP are generally used for costs minimization, such as finding the best tour for round-the-world trip or construction of very large-scale integration schemes. Since the TSP ...
Added: May 29, 2017
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit