?
Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа/ Probability distribution of the complexity of the individual traveling salesman problem (fixed number of nodes)
С. 304-310.
Головешкин В. А., Жукова Г. Н., Ulyanov M., Fomichev M.
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 sample. Borders of the interval, which contains 90% of the sample of the logarithm of the complexity, are also given.
In book
Vol. 1761: SITITO 2016. Modern Information Technologies and IT-Education. Selected Papers of the XI International Scientific-Practical Conference Modern Information Technologies and IT-Education (SITITO 2016). Moscow, Russia, November 25-26, 2016. , CEUR Workshop Proceedings, 2016
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
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
Головешкин В. А., Zhukova G., Ulyanov M. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Added: March 22, 2020
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
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
Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38-46
The resource efficiency of different implementations of the branch-and-bound method for the classical traveling salesman problem depends, inter alia, on ways to organize a search decision tree generated by this method. The classic «time-memory» dilemma is realized herein either by an option of storing reduced matrices at the points of the decision tree, which leads ...
Added: November 5, 2016
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
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
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
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
Ignatov A., Posypkin M., Communications in Computer and Information Science 2018 P. 511-522
The paper proposes an implementation of the Branch-and-Bound method for an enterprise grid based on the BOINC infrastructure. The load distribution strategy and the overall structure of the developed system are described with special attention payed to some specific issues such as incumbent updating and load distribution. The implemented system was experimentally tested on a ...
Added: October 18, 2019
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
Ignatov A., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112-116
The paper describes a simulator of parallel Branch and Bound (BnB) method. Several subdomain trees for benchmark functions are analyzed, a characteristic Gaussian-like distribution is discovered. An algorithm of artificial tree generation is formulated according to this criterion. The process of simulator modeling is described, several computational experiments are conducted. Their results show a hyperbolic ...
Added: June 11, 2020
Головешкин В. А., Zhukova G., Ulyanov M. et al., Современные информационные технологии и ИТ-образование 2015 Т. 2 № 11 С. 151-159
Сравниваются ресурсные характеристики модифицированного и классического МВГ для TSP. На основании экспериментальных результатов показано, что по величине затраченного на поиск решения времени модифицированный вариант МВГ эффективнее классического. Исследована стохастическая зависимость между временем работы каждого из двух исследуемых вариантов МВГ при фиксированном порядке матрицы стоимостей. Также описана зависимость затраченной памяти и времени работы алгоритма от порядка ...
Added: October 9, 2017
Chusovliankin A., Morozenko V. V., Вестник Пермского университета. Серия: Математика. Механика. Информатика 2016 Т. 4 № 35 С. 68-75
In this paper the new "anti-greedy" algorithm for the Traveling Salesman Problem is under investigation. The idea of "anti-greedy" algorithm is consequent elimination of the longest edges from graph according to two rules: every node of the graph should have two incident edges as a minimum; the graph should not have cycles with less than ...
Added: January 23, 2017
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
Fomichev M., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Added: March 22, 2020
Beresneva E., Gordenko M., Открытые системы. СУБД 2018 № 01 С. 40-42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Added: June 22, 2018
Fomichev M., Системы управления и информационные технологии 2017 № 3 С. 88-92
Branch-and-bound algorithm for solving Traveling Salesman Problem is one of the most applied accurate algorithms to solve it. Metaheuristic algorithms for solving asymmetric Traveling Salesman Problem do not assure finding optimal solution, although they work “fast”. The combination of such algorithms with the branch-and-bound algorithm is analyzed in this article. ...
Added: March 23, 2020
Irina E. Utkina, Mikhail V. Batsyn, Ekaterina K. Batsyna, International Journal of Production Research 2018 Vol. 56 No. 9 P. 3262-3273
The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its ...
Added: March 11, 2018
Alexey Nikolaev, Mikhail Batsyn, , in : Combinatorial Algorithms. 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018. Lecture Notes in Computer Science. Vol. 10979.: Springer, 2018. P. 311-322.
In this paper a branch-and-bound algorithm for the Symmetric Travelling Salesman Problem (STSP) is presented. The algorithm is based on the 1-tree Lagrangian relaxation. A new branching strategy is suggested in which the algorithm branches on the 1-tree edge belonging to the vertex with maximum degree in the 1-tree and having the maximum tolerance. This ...
Added: October 23, 2018
Borisova L. A., Логистика сегодня 2013 № 6 С. 338-347
The possibility of using approximate approaches for solving supply chain optimization problem with continuously accrued fines is discussed. The problem was investigated by numerical simulation for the case of exponentially growing fines, when a logistic operator must deliver the cargo to several points. The vehicle was allowed to move from any point to any other ...
Added: November 17, 2013