?
Some approaches to solving the NP-hard Mixed Chinese Postman Problem
P. 272–290.
Задачи маршрутизации важны для логистической и транспортной сферы. В основном, задачи маршрутизации связаны с определением оптимального набора маршрутов в мультиграфе. Задача китайского почтальона (CPP) является частным случаем обобщенной задачи маршрутизации, решение которой имеет много потенциальных приложений. В работе приведены варианты CPP. Представлены математические формулировки некоторых задач CPP. Предлагается решить MCPP (NP-турдный случай CPP, определенный на смешанном мультиграфе), используя приведение исходной проблемы MCPP в эквивалентную задачу General Traveling Salesman (GTSP). Показан алгоритм приведения MCPP в мультиграфе в GTSP. Приводятся экспериментальные результаты решения MCPP в мультиграфе посредством приведения в GTSP.
Язык:
английский
Ключевые слова: задача коммивояжераTraveling Salesman Problemheuristic algorithmMixed Chinese Postman ProblemArc Routing ProblemСмешанная задача китайского почтальонаЗадача маршрутизации дугGeneral Routing ProblemVehicle Routing ProblemAsymmetric Traveling Salesman ProblemGeneralized Traveling Salesman Problem
В книге
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47–54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590–595
Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...
Добавлено: 16 февраля 2020 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067
Добавлено: 24 ноября 2019 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Бакланов А. П., Ченцов П. А., , in: CEUR Workshop Proceedings 48. Сер. "SoProMat 2017 - Proceedings of the 48th International Youth School Conference "Modern Problems in Mathematics and its Applications"".: CEUR Workshop Proceedings, 2017. P. 203–208.
Добавлено: 22 июля 2019 г.
Aleksander V. Belov, Загуменнов Ф. Д., , in: Proceedings of the 2018 IEEE International Conference "Quality Management, Transport and Information Security, Information Technologies" (IT&QM&IS).: IEEE, 2018. P. 308–311.
В данной работе основной целью ставится построение алгоритмов оценки эффективности применения системы передачи финансовых сообщений для систем ДБО. В работе рассматриваются два вида взаимодействий юридического лица с банком: «Банк - Клиент» и «Интернет – Клиент». Рассматриваемые взаимодействия осуществляются посредствам двух типов систем: Системы классического дистанционного банковского обслуживания и Системы передачи финансовых сообщений. Входными параметрами построенных ...
Добавлено: 27 ноября 2018 г.
Alexey Nikolaev, Mikhail Batsyn, , in: Combinatorial Algorithms. 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018. Lecture Notes in Computer ScienceVol. 10979.: Springer, 2018. P. 311–322.
Добавлено: 23 октября 2018 г.
Добавлено: 18 октября 2018 г.
Горденко М. К., Авдошин С. М., Proceedings of the Institute for System Programming of the RAS 2018 Vol. 30 No. 3 P. 221–232
Добавлено: 2 сентября 2018 г.
Добавлено: 30 августа 2018 г.
В статье приведены результаты статистического исследования сложности несимметричной задачи коммивояжера (NTSP), полученные в результате обработки специального сгенерированного пула матриц. Основная цель - вероятностной прогноз сложности индивидуальных задач, для больших значений размерности матрицы стоимостей. Показано, что нормальное распределение удовлетворительно приближает распределение логарифма сложности при фиксированной размерности задачи. Построено семейство вероятностных распределений, являющихся удовлетворительными приближениями распределения сложности ...
Добавлено: 16 июля 2018 г.
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev и др., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296–1310
Добавлено: 16 июля 2018 г.
Береснева Е. Н., Горденко М. К., Открытые системы. СУБД 2018 № 01 С. 40–42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Добавлено: 22 июня 2018 г.
Горденко М. К., Коротков Д. А., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского.: МИЭМ НИУ ВШЭ, 2018. С. 42–44.
В работе рассмотрен меметический алгоритм, являющий-ся комбинацией генетического алгоритма и алгоритмов ло-кального поиска решения ассиметричной задачи коммивоя-жера (A TSP). Приведена математическая постановка задачиA TSP . Кратко описан принцип работы меметического алгорит-ма. Проведено экспериментальное исследование временных и точностных характеристик меметического алгоритма на откры-той базе данных TSPLIB в зависимости от входных параметров с целью выявления оптимальных настроек алгоритма. ...
Добавлено: 5 июня 2018 г.
Горденко М. К., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского.: МИЭМ НИУ ВШЭ, 2018. С. 20–21.
В данной работе рассмотрены алгоритмы ближайшего соседа решения обобщенной задачи коммивояжера в качестве начальной инициализации для алгоритма LKH. Проведено экспериментальное исследование алгоритма LKH с целью сравнительной оценки рациональности полученных решений при различных начальных инициализациях. ...
Добавлено: 5 июня 2018 г.