?
Особый случай классического метода ветвей и границ для задачи коммивояжёра // Вестник Волжской государственной академии водного транспорта
Вестник Волжской государственной академии водного транспорта. 2017. № 49. С. 68-78.
Фомичев М. И.
-
Классический алгоритм, реализующий метод ветвей и границ для решения задачи коммивояжёра, предложенный в 1963 году Дж. Литл, К. Мурти, Д. Суини и К. Кэрол, остаётся по настоящее время самым востребованным алгоритмом при решении задачи нахождения гамильтонового цикла минимальной стоимости в полном графе. Существует много различных источников, в которых представлен псевдокод алгоритма с текстовыми комментариями. Однако в этих источниках не уделяется внимание некоторым особым случаям. Анализу одного из таких особых случаев и посвящена настоящая статья
Добавлено: 18 октября 2018 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054-2067
Добавлено: 24 ноября 2019 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Современные информационные технологии и ИТ-образование 2016 Т. 12 № 3-2 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.
<img /> ...
Добавлено: 5 октября 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Автоматизация. Cовременные технологии 2016 № 10 С. 22-29
Рассмотрено новое обобщённое представление для классов индивидуальных задач коммивояжёра - матрица номеров порядка, предназначенное для выделения классов задач, обладающих близкой сложностью. Полученный результат направлен на решение задачи прогнозирования сложности для индивидуальных задач коммивояжёра. Сформулированы две гипотезы относительно мощности предложенного обобщения. Приведены метод получения матрицы номеров порядка и ряд предварительных экспериментальных результатов, не противоречащих одной из ...
Добавлено: 5 октября 2017 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., В кн. : 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.
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 30 марта 2017 г.
Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590-595
Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...
Добавлено: 16 февраля 2020 г.
Фомичев М. И., Ульянов М. В., Головешкин В. А. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 19 августа 2017 г.
Ульянов М. В., Фомичев М. И., Головешкин В. А. и др., 2017 Т. 13 № 1 С. 19-24
Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра ...
Добавлено: 26 сентября 2017 г.
Береснева Е. Н., Горденко М. К., Открытые системы. СУБД 2018 № 01 С. 40-42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Добавлено: 22 июня 2018 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Игнатов А. Д., Посыпкин М. А., Communications in Computer and Information Science 2018 P. 511-522
Добавлено: 18 октября 2019 г.
Ekaterina N. Beresneva (Chirkova), Sergey M. Avdoshin, International Journal of Open Information Technologies 2017 Vol. 5 No. 5 P. 16-24
Добавлено: 29 мая 2017 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 7-12
Исследуется сложность индивидуальных задач коммивояжера, т.е. число порожденных вершин поискового дерева в классическом методе ветвей и границ. Вероятностное распределение логарифма сложности аппроксимируется нормальным распределением. На основе экспериментальных данных рассчитаны значения параметров линейного преобразования, обеспечивающих минимальное среднеквадратическое отклонение выборочных квантилей логарифма сложности от соответствующих квантилей стандартного нормального распределения, получена формула зависимости этих параметров от числа вершин ...
Добавлено: 5 октября 2017 г.
Жукова Г. Н., Ульянов М. В., , 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.
Добавлено: 15 июня 2021 г.
Игнатов А. Д., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112-116
Добавлено: 11 июня 2020 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Современные информационные технологии и ИТ-образование 2015 Т. 2 № 11 С. 151-159
Сравниваются ресурсные характеристики модифицированного и классического МВГ для TSP. На основании экспериментальных результатов показано, что по величине затраченного на поиск решения времени модифицированный вариант МВГ эффективнее классического. Исследована стохастическая зависимость между временем работы каждого из двух исследуемых вариантов МВГ при фиксированном порядке матрицы стоимостей. Также описана зависимость затраченной памяти и времени работы алгоритма от порядка ...
Добавлено: 9 октября 2017 г.
Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных ...
Добавлено: 11 декабря 2018 г.
Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38-46
Добавлено: 5 ноября 2016 г.
Фомичев М. И., Системы управления и информационные технологии 2017 № 3 С. 88-92
Алгоритм, реализующий метод ветвей и границ для решения задачи коммивояжёра - один из самых востребованных точных алгоритмов её решения. Метаэвристические алгоритмы решения этой задачи не гарантируют точного решения, но работают «быстро». В данной статье рассматривается комбинация таких алгоритмов с методом ветвей и границ. ...
Добавлено: 23 марта 2020 г.
Irina E. Utkina, Mikhail V. Batsyn, Ekaterina K. Batsyna, International Journal of Production Research 2018 Vol. 56 No. 9 P. 3262-3273
Добавлено: 11 марта 2018 г.
Борисова Л. А., Логистика сегодня 2013 № 6 С. 338-347
Впервые обсуждаются возможности использования приближенных подходов к решению задачи оптимизации цепей поставки с непрерывно начисляемыми штрафами за нарушение сроков доставки. Задача была исследована с помощью численного моделирования на примере экспоненциально нарастающих штрафов для примера, когда логистическому оператору необходимо доставить груз в несколько региональных пунктов, при этом транспортное средство может свободно перемещаться из одного пункта в ...
Добавлено: 17 ноября 2013 г.
Мищенко А. В., Ульянова Т. И., Логистика и управление цепями поставок 2010 № 5(40) С. 68-79
В работе рассмотрены количественные методы оптимизации управления различными видами ресурсов, используемых при выполнении инвестиционных проектов в разрезе их технической осуществимости. В частности, исследована проблема оптимизации длительности переналадок оборудования перед выполнением операций в ситуации, когда различные изделия производятся одним и тем же устройством, но в каждый момент времени вырабатывается лишь один из них. Показана детерминированная модель ...
Добавлено: 26 октября 2012 г.