?
Особый случай классического метода ветвей и границ для задачи коммивояжёра // Вестник Волжской государственной академии водного транспорта
Вестник Волжской государственной академии водного транспорта. 2017. № 49. С. 68-78.
Fomichev M.
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 some special cases which are not discussed in these references. One of these cases is an-alyzedin this article.
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. 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., Автоматизация. 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
Головешкин В. А., Жукова Г. Н., Ulyanov M. et al., В кн. : CEUR Workshop Proceedings. 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. С. 304-310.
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: March 30, 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
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., Головешкин В. А. 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
Beresneva E., Gordenko M., Открытые системы. СУБД 2018 № 01 С. 40-42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Added: June 22, 2018
Головешкин В. А., Zhukova G., Ulyanov M. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Added: March 22, 2020
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
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
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
Fomichev M., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Added: March 22, 2020
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., , in : Modern Information Technology and IT Education: 12th International Conference, SITITO 2017, Moscow, Russia, November 24–26, 2017, Revised Selected Papers. Vol. 1204.: Springer, 2021. P. 261-270.
This article is about the probability distribution of the maximum of the logarithm of the complexity of an individual travelling salesman problem. The complexity is defined as a number of nodes of the decision tree, which was created by the branch and bound algorithm. We applied our earlier results that the distribution of the logarithm ...
Added: June 15, 2021
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
Zhukova G., Ulyanov M., Fomichev M., Бизнес-информатика 2018 Т. 45 № 3 С. 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 ...
Added: December 11, 2018
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 № 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
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
Mishchenko A. V., Ульянова Т. И., Логистика и управление цепями поставок 2010 № 5(40) С. 68-79
Author describes quantitative methods of optimization in management of different kinds of resources, which can be used within investment projects buildup on the stage of feasibility studies. Particulary, the issue of optimization of re-adjustment time duration is investigated (on the example of cases, when different goods are produced by one tool, but in each discrete ...
Added: October 26, 2012