Ключевые слова: планарный граф, маршрутизация, комбинаторная оптимизация.
Введение
В современном мире с учетом большого количества информации, социального расширения, развития городов, маршрутов, сетей типа Интернет, всё больше встаёт вопрос об оптимизации их работы. К этой сфере относится проблема коммивояжёра (Travel Salesman Problem –– задача поиска наиболее оптимального (с наименьшими затратами) маршрута, проходящего через все вершины планарного графа, притом только один раз.
Для решения задач оптимизации на сетях больших масштабов (больших планарных графах) применяются в основном алгоритмы, не дающие точного решения. Графы больших масштабов — это графы с большим количеством вершин, для которых точные алгоритмы поиска оптимальных путей или других характеристик уже не работают за разумное время. Из-за огромного числа возможных вариантов большинство задач комбинаторной оптимизации невозможно решить за разумное время. С увлечением объемов данных, а также дорог, развития общества в целом появляется множество задач, которые невозможно в разумных временных рамках решить точными подходами, даже несмотря на все достижения вычислительной техники.
Основная часть
В эвристических алгоритмах как алгоритмах, не дающих точных решений, всегда есть некоторые допущения, вариативности. Часто эти вариации задаются некоторыми параметрами, которые нестрого определены и могут быть заданы произвольным образом. Возможность даже небольшого улучшения даёт огромные финансовые, временные и технологические преимущества.
Задачи на эффективное распределение маршрутов в графах больших масштабов встречаются как в Интернет сетях, так в распределенных системах, посылающие сигналы на множество приёмников или источников. Более того, данные задачи имеют логистический характер, который сложно недооценить: начиная от инкассации, FMSG (товары повседневного спроса), заканчивая нефтяной отраслью, транспортировкой опасных и вредных грузов. Во всех областях встречаются различные вариации задач CVRP (Capacitated Vehicle Routing Problem — задача маршрутизации с ограничением на вместимость транспортных средств), в зависимости от области.
С учётом временных ограничений, ограничений оборудования, задачи могут достаточно сильно различаться. С связи с этим различные методы решения могут давать разную эффективность. Поэтому применение для определенного типа задачи определенного метода и анализ его эффективности достаточно актуален в такой широкой сфере.
Сравним применение существующих алгоритмов на различных входных данных и возможность выбора оптимального способа использования алгоритма и входных данных. В классическом варианте требуется найти приемлемое решение с минимальной стоимостью.
Опишем основные методы решений, которые используются для задач маршрутизации и задачи маршрутизации с ограничением на вместимость.
- Точные подходы. Такой подход перебирает все возможные решения, пока не будет найдено оптимальное:
– метод ветвей и границ;
– метод ветвей с отсечением.
-
Эвристические методы. Производится относительно ограниченный поиск по пространству решений, и обычно находятся хорошие решения за приемлемое время.
- Конструктивные методы. Постепенно строят подходящее решение, принимая во внимание получающуюся общую стоимость:
– механизм сбережений;
– метод, основанный на совпадениях;
– эвристики улучшения многих маршрутов.
- Двухфазный алгоритм
Здесь задача разделяется на две части: организация вершин в группы, и построение маршрута по каждой группе.
- Мета-эвристика
В мета-эвристических методах упор делается на тщательном изучении наиболее перспективных частей пространства решений. Качество получаемых решений получается выше, чем у полученных классическими эвристиками.
Задачи комбинаторной оптимизации до сих пор требуют проверки пригодности имеющихся решений на практике. Напомним, что комбинаторная оптимизация — это область теории оптимизации в прикладной математике, связанная с исследованием операций (применения нахождения оптимальных решений посредством моделирования, статического моделирования и различных эвристических подходах), теорией алгоритмов и теорией вычислительной сложности.
По большому счёту, комбинаторная оптимизация есть выбор оптимального решения среди конечного числа объектов. Комбинаторная оптимизация больше направлена на эффективное распределение ресурсов для поиска оптимального решения. Задачи, решаемые за полиномиальное время (класс P), хоть и являются очень важными, для нас интереса не представляют. Степень полинома для большинства задач класса P не является достаточно большим (например, большинство задач по преобразованию матриц) за редким исключением [2] Считается, что не лежащие в классе Р задачи решать заметно сложнее, несмотря на проблему перебора — проблема равенства классов Р и NP. Задачи второй категории мы и будем рассматривать.
Множества задач класса NP представляют собой абсолютно различные области [3]: задача о выполнимости булевых формул: узнать по данной булевой формуле существует ли сертификат (набор переменных), обращающих её в единицу, существование целочисленного решения у данной системы линейных неравенств, задача о клике.
Задачи на планарных графах имеют наиболее широкий объём среди всех задач NP [3]: задача коммивояжёра (задача о нахождении самого эффективного маршрута, проходящего через указанные вершины хотя бы по одному разу с возвращением в начальную вершину), о раскраске графа (возможно ли раскрасить вершины графа определённым набором цветов, чтобы у смежных вершин были разные цвета), о вершинном покрытии (можно ли выбрать определённое значение вершин у данного графа, чтобы все рёбра содержали хотя бы одну вершину из этого множества) и т. д.
Все данные задачи относят к классу NP, non-deterministic polynomial. По определению, это задачи разрешимости (ответ да/нет), которые можно проверить на машине Тьюринга за время, не превосходящее значение некоторого многочлена от входных данных при наличии некоторых дополнительных сведений или ответа [1]. У задач из класса Р условия на дополнительные сведения (сертификата) нет. Притом без данного сертификата задача решается только экспоненциально для задач класса NP.
Более того, среди NP-задач выделяют NP-полные задачи, решив которые за полиномиальное время, можно решить и все остальные NP задачи также за полиномиальное время. Данное сведение вызывало и вызывает большой ажиотаж вокруг решения задачи такого класса. Однако до сих пор не было всемирно доказано равенство классов Р и NP, однако попытки были [4].
В результате при достаточно небольшом количестве входных данных известные методы дают точное решение за время, превышающее разумные пределы. Например, задача коммивояжёра при числе вершин больше 66, уже не может имеющимися на данный момент точными алгоритмами быть решена за время нескольких миллиардов лет. Поэтому сейчас все возникающие на практике задачи решаются эвристическими или метаэвристическими методами, которые дают достаточно эффективные результаты. Стоит отметить, что классы задач Р и NP совсем не охватывают все возможные виды задач.
Выводы
Практически всё в нашем мире ограничено временем. В связи с этим не учитывать его, а конкретно расписание агентов и их временные границы, некорректно с точки зрения практики. А именно рассмотрение задачи CVRP с временными окнами, которая наиболее часто используется на практике (в том числе в компании научного руководителя), давало бы результаты, ещё более приближенные к оптимальным.
Тем не менее, большинство реальных предприятия ввиду огромного числа данных и ограниченной инфраструктуры и кадров, используют решения, далёкие от тех, что достигла теория. Это, несомненно, мотивирует развивать, упрощать и внедрять алгоритмы в существующие комплексы. Однако стоит принять во внимание, что для каждого конкретного вида нужно принимать во внимание весь спектр возможных теоретических решений и искать оптимальное снова и снова для каждого конкретного случая, что открывает простор для дальнейших исследований.
Литература:
- Heitor S. LopesVilson L. Dalle MolleCarlos R. Erig Lima «An ant colony optimization system for the capacitatedvehicle routing problem», Av. 7 de setembro, 3165, 80230–901
- Гирш Э. А. Введение в структурную теорию сложностей [Электронный ресурс] URL: https://www.studmed.ru/speckurs-strukturnaya-teoriya-slozhnosti_6348559b3ff.html
- Бараш, Л. Ю. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел // Безопасность информационных технологий. — 2005. — № 2(46). — С. 27–38
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2011. — 1296 с.
