Branch-and-bound algorithm for Symmetric Travelling Salesman Problem

В докладе рассматривается статистическая зависимость числа порожденных вершин дерева решений и физического времени работы программной реализации метода ветвей и границ для задачи коммивояжера (TSP). На основе результатов вычислительного эксперимента получено приближенное соотношение между числом порожденных вершин (сложность индивидуальной TSP) и физическим временем. Предлагается использовать это эмпирическое соотношение для прогнозирования времени работы программы, решающей TSP с числом «городов» больше 40. ...

Добавлено: 22 марта 2020 г.

Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра

Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590–595

Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...

Добавлено: 16 февраля 2020 г.

Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности

Жукова Г. Н., Ульянов М. В., Фомичев М. И., Автоматика и телемеханика 2019 № 11 С. 155–172

Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...

Добавлено: 10 ноября 2019 г.

Implementation and Use of Coarse-grained Parallel Branch-and-bound in Everest Distributed Environment

Voloshinov V., Smirnov S., Сухорослов О. В., Procedia Computer Science 2017 Vol. 108 P. 1532–1541

Добавлено: 30 августа 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.

Задачи маршрутизации важны для логистической и транспортной сферы. В основном, задачи маршрутизации связаны с определением оптимального набора маршрутов в мультиграфе. Задача китайского почтальона (CPP) является частным случаем обобщенной задачи маршрутизации, решение которой имеет много потенциальных приложений. В работе приведены варианты CPP. Представлены математические формулировки некоторых задач CPP. Предлагается решить MCPP (NP-турдный случай CPP, определенный на ...

Добавлено: 18 ноября 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

Задачи маршрутизации важны для областей логистики и управления трансортом. Задачи маршрутизации в основном связаны с определением оптимального набора путей в мультиграфе. Задача китайского почтальона (CPP) является особым случаем задачи маршрутизации, имющим много потенциальных приложений. Мы предлагаем решение MCPP (специального NP-полного случая CPP на смешанном мультиграфе) с использованием редуцирования исходной задачи к обобщенной задаче коммивояжера (General ...

Добавлено: 27 сентября 2017 г.

Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера

Фомичев М. И., Ульянов М. В., Головешкин В. А. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131–137

На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...

Добавлено: 19 августа 2017 г.

Transformation of the Mixed Chinese Postman Problem in multigraph into the Asymmetric Travelling Salesman Problem

Maria K. Gordenko, Авдошин С. М., International Journal of Open Information Technologies 2017 Vol. 5 No. 6 P. 6–11

Добавлено: 1 июня 2017 г.

Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа/ Probability distribution of the complexity of the individual traveling salesman problem (fixed number of nodes)

Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., В кн.: CEUR Workshop ProceedingsVol. 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.

Добавлено: 30 марта 2017 г.

Анализ точности решения задачи коммивояжера с помощью «антижадного» алгоритма

Чусовлянкин А. А., Морозенко В. В., Вестник Пермского университета. Серия: Математика. Механика. Информатика 2016 Т. 4 № 35 С. 68–75

Предложен новый «антижадный» алгоритм для решения задачи коммивояжера, имеющий меньшую погрешность, чем известные приближенные полиномиальные алгоритмы. Идея «антижадного» алгоритма заключается в том, что из графа последовательно удаляются ребра наибольшей длины при одновременном соблюдении для оставшегося графа двух правил. Во-первых, из каждой его вершины должно выходить, как минимум, два ребра. Во-вторых, в нем не должно возникать ...

Добавлено: 23 января 2017 г.

Resource characteristics of ways to organize a decision tree in the branch-andboundmethod for the traveling salesmen problem

Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38–46

Добавлено: 5 ноября 2016 г.

The Theory of Set Tolerances

Jäger G., Гольденгорин Б. И., Пардалос П. О., , in: Learning and Intelligent Optimization. 8th International Conference, Lion 8, Gainesville, FL, USA, February 16-21, 2014. Revised Selected PapersVol. 8426.: Springer, 2014. P. 362–377.

The theory of single upper and lower tolerances for combinatorial minimization problems has been formalized in 2005 for the three types of cost functions sum, product and maximum, and since then shown to be rather useful in creating heuristics and exact algorithms for the Traveling Salesman Problem and related problems. In this paper for these ...

Добавлено: 26 октября 2014 г.