?
Об одном обобщённом представлении классов индивидуальных задач коммивояжёра
Автоматизация. 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 an appliance of the representation, that is proposed in the article. A method of index number matrix construction is also given. Some results are obtained by experiments, which didn’t interfere with one of our hypotheses.
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
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
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
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
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., Вестник Волжской государственной академии водного транспорта 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. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Added: March 22, 2020
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
Fomichev M., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Added: March 22, 2020
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. et al., Современные информационные технологии и ИТ-образование 2015 Т. 2 № 11 С. 151-159
Сравниваются ресурсные характеристики модифицированного и классического МВГ для TSP. На основании экспериментальных результатов показано, что по величине затраченного на поиск решения времени модифицированный вариант МВГ эффективнее классического. Исследована стохастическая зависимость между временем работы каждого из двух исследуемых вариантов МВГ при фиксированном порядке матрицы стоимостей. Также описана зависимость затраченной памяти и времени работы алгоритма от порядка ...
Added: October 9, 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
Beresneva E., Gordenko M., Открытые системы. СУБД 2018 № 01 С. 40-42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Added: June 22, 2018
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
Utkina I. E., Batsyn M. V., Программные продукты, системы и алгоритмы 2017 № 4 С. 1-10
The Cell Formation Problem (CFP) is an NP-hard optimization problem considered for cellular man- ufacturing systems. Because of its high computational complexity there have been developed a lot of heuristics and almost no exact algorithms for solving this problem. In this paper we suggest a branch- and-bound algorithm which provides exact solutions for the CFP ...
Added: October 18, 2017
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
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
Nikolskiy V., Stegailov V., Journal of Physics: Conference Series 2016 Vol. 681 No. 012049 P. 1-6
Supercomputing of the exascale era is going to be inevitably limited by power efficiency. Nowadays different possible variants of CPU architectures are considered. Recently the development of ARM processors has come to the point when their floating point performance can be seriously considered for a range of scientic applications. In this work we present the analysis of the flooating ...
Added: December 6, 2015
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. 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
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
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
Afanasyev A. A., Экономика и математические методы 2017 Т. 53 № 4 С. 26-35
This study is devoted to forecasting the Russian Gazprom natural gas production from the Tyumen region's fields and its production potential under in the context of the Russian economy crises and foreign economic restrictions that has been occurred since 2014, including a reduction in external and domestic demand for all Russian natural gas as well ...
Added: August 31, 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