Вкр. Факультет прикладной математики процессов управления Кафедра математического моделирования энергетических систем Широких Вячеслав Андреевич
 Скачать 1.83 Mb.
|
|
Глава 2. Алгоритмы решения задач маршрутизации 2.1. Обзор и классификация актуальных алгоритмов Проблема решения задач маршрутизации заключается в том, что задачи данного класса являются вычислительно NP-трудными, т.е. не существует алгоритма нахождения оптимального решения не более чем за полиномиальное время. В связи с этим, не существует единственного наиболее эффективного подхода к решению задач маршрутизации. За годы, в исследованиях было рассмотрено множество различных алгоритмов решения, и новые продолжают рассматриваться до сих пор. В общем, алгоритмы решения можно разделить на две категории: точные методы, гарантированно приходящие к точному решения, но не ограниченные по времени вычисления, и, наконец, эвристические методы, которые способны находить качественное решение эффективно по времени, но не гарантирующие оптимальности этого решения. Сама задача маршрутизации представляет собой задачу комбинаторной оптимизации. Не существует аналитического метода решения задачи, поэтому для нахождения точного решения используются различные универсальные методы комбинаторной оптимизации. Наиболее популярными среди используемых точных методов являются методы ветвей и границ, включая метод ветвей и сечений (branch and cut) [32], метод ветвей, оценок и сечений (branch, price and cut) [33]. Так же популярными методами являются методы релаксации [11, 17]. Поскольку точные методы не имеют ограничений по времени вычисления, то в худшем случае это время будет эквивалентно n! от размерности n входных данных. При достаточно большом n, начиная уже с нескольких десятков, задачу 21 полного перебора n! решений невозможно решить за приемлемое время, даже на многопроцессорных суперкомпьютерах. На практике, правильно построенный метод может сократить пространство поиска во много раз, но, тем не менее, не понизить вычислительную сложность. Фактические ограничения на поиск точного решения зависят от исследуемой вариации задачи и от используемого метода. Так, наибольшая по размеру ЗК содержит 85900 узлов и была решена с помощью параллельных вычислений методом Concorde за 1,5 года [34]. Вместе с этим, представлены и более практические ограничения: за 1000 секунд наибольшая задача содержит 2392 точки [35]. С другой стороны, при исследовании более сложной и актуальной задачи маршрутизации запаса, максимальный размер задачи, для которой было найдено точное решение за ограниченное время в 7200 секунд составляет 50 точек с 3 периодами планирования и 30 точек с 6 шестью периодами планирования [33]. Альтернативным методом использования точных методов является использование полученной нижней границы как приближённого решения, что позволяет получать решения на бóльших задачах в пределах 1-5% оптимального [33]. В связи с этими ограничениями, особенно на более сложных задачах, возникает необходимость в более эффективных методах нахождения решения. Такой альтернативой точным методам являются эвристики, которые позволяют быстро находить решение, не гарантированно оптимальное, но как минимум близкое к нему, при правильно построенном алгоритме. В литературе, эвристические методы пользуются гораздо бóльшей популярностью, нежели точные методы, и за годы исследования было предложено и рассмотрено множество разнообразных алгоритмов. В связи с 22 существенным преимуществом в вычислительной эффективности по сравнению с точными методами, а также в связи с актуальностью исследования, данная работа использует эвристически для вычисления решений исследуемых задач. Условно, эвристические алгоритмы можно разделить на алгоритмы построения [13, 17], которые строят решение за одну итерацию, алгоритмы локального поиска [13], находящие лучшее решение в локальной окрестности, и алгоритмы глобального поиска, итеративно приближающие решение к оптимальному. Последние, в свою очередь, можно разделить по используемому подходу, основными из которых являются методы поиска в большой окрестности [15, 28, 36, 38], методы поиска с исключениями [37], а также генетические и популяционные методы [19, 23, 27]. Современные эффективные эвристики имеют тенденцию сочетать три различных подхода в одной схеме алгоритма, как, например, в работах [27, 36, 37, 38]. Так, эвристики построения используются для получения начального решения, причём зачастую качество начального решения имеет сильное влияние на окончательный результат: чем оно ближе к оптимальному, тем быстрее будет глобальный поиск и тем лучше будет результат поиска за ограниченное время. Алгоритмы локального поиска могут быть использованы для обобщения поиска, если глобальный алгоритм использует точечные переходы от одного решения к другому: локальная оптимизация позволяет рассматривать окрестность целиком, а не одну новую точку. При всём этом, алгоритм глобального поиска задаёт «направление» поиска в глобальном пространстве решений. В данной работе для нахождения решений различных задач используется концепция Адаптирующегося поиска в большой окрестности (Adaptive large neighborhood search, ALNS), которая была адаптирована в различных задачах, включая задачу маршрутизации транспорта [38], задачу маршрутизации запаса [36] и задачу сбора и доставки [28]. Основанием для выбора данного подхода 23 является значительная гибкость метода для адаптации к различным задачам маршрутизации, по сравнению с популяционными методами, а также экспериментально показанная существенная выгода в скорости вычисления, по сравнению с методами поиска с исключениями. 2.2. Adaptive Large Neighborhood Search Подробное описание алгоритма можно найти в работах [28, 36, 38]. Универсальная схема алгоритма содержит две основных составляющих: адаптирующийся рандомизированный поиск и моделирование отжига. Под окрестностью решения понимаются все возможные решения, которые можно получить из текущего решения с помощью заданного набора процедур модификации/изменения. Метод ALNS предполагает наличие большого количества нетривиальных процедур, что создаёт довольно большую окрестность для поиска. С одной стороны, в ALNS направление поиска, то есть выбор процедуры модификации, осуществляется случайным образом, так как в противном случае такой поиск на каждой итерации занимал бы слишком много времени. С другой стороны, вероятность выбора конкретной процедуры изменяется динамически, в зависимости от эффективности её применения, что позволяет алгоритму «запоминать» выгодные направления в зависимости в каждой конкретной решаемой задаче. Конкретный набор процедур зависит от типа решаемой задачи и может варьироваться. Обобщённо, они обычно включают процедуры исключения, добавления или перемещения точек в решении различно организованными группами, такими, например, как группы случайно выбранных точек, группы точек с наилучшим улучшением/наименьшим ухудшением, или локальных кластеров точек. 24 Метод моделируемого отжига применяется для того, что обходить так называемые «локальные минимумы» в пространстве решений – решения, оптимальные лишь в небольшой, локальной окрестности. Идея метода состоит в том, чтобы дать возможность продолжать поиск в некотором направлении, даже если поначалу это направление ведёт к ухудшению решения. Фактически, алгоритм симулирует физические процессы охлаждения и кристаллизации: начальная «температура решения» 𝜏 постепенно понижается в ходе вычисления, и вместе с ней понижается вероятность перехода к худшему решению, аналогично вероятности атома занять ту или иную позицию в кристаллической решётке. Эта вероятность также зависит и от удалённости решения от текущего, так что при большом удалении, вероятность перехода будет меньше. Обычно, для вычисления этой вероятность используются формулы следующего вида: Для текущего решения 𝑠 и нового решения 𝑠 ′ , если 𝑓(𝑠) < 𝑓(𝑠 ′ ) , то есть 𝑠 ′ хуже 𝑠, вероятность перехода к 𝑠 ′ будет равна 𝑝 = exp ( 𝑓(𝑠)−𝑓(𝑠 ′ ) 𝜏 ). Как можно заметить, степень экспоненты будет отрицательной, то есть при приближении сверху 𝑓(𝑠 ′ ) к 𝑓(𝑠), вероятность будет стремиться к единице, а при удалении – к нулю. Аналогично, при понижении температуры 𝜏, вероятность перехода к решениям на одинаковом заданном расстоянии будет понижаться. Алгоритм ALNS также подразумевает использование некоторой дополнительной эвристики построения для получения начального решения, а также некоторой процедуры локального поиска, для периодического улучшения новых решений в процессе вычисления. Формальная схема алгоритма в универсальном виде на естественном языке представлена далее, в форме Алгоритм 1. Процедура 𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛(∙) – некоторая эвристика построения начального решения. 𝑈𝑝𝑑𝑎𝑡𝑒 𝑖 (∙) – процедуры модификации, формирующие большую окрестность решения. Значения 𝑤 𝑖 , 𝑐 𝑖 , 𝑛 𝑖 – соответствующие каждой процедуре 𝑖 вес, или доля в вероятностном 25 распределении, очки улучшения, повышающиеся при нахождении нового решения 𝑠 или 𝑠 𝑏𝑒𝑠𝑡 и счётчик использований соответственно. 𝐿𝑜𝑐𝑎𝑙𝑂𝑝𝑡(∙) – некоторый быстрый алгоритм локальной оптимизации. Алгоритм 1: Adaptive Large Neighborhood Search 1: 𝑠 𝑏𝑒𝑠𝑡 = 𝑠 = 𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛(∙) 2: 𝑤 𝑖 = 1, 𝑐 𝑖 = 0, 𝑛 𝑖 = 0, для каждой процедуры 𝑖; 𝜏 = 𝜏 𝑠𝑡𝑎𝑟𝑡 3: Пока 𝜏 > 𝜏 𝑚𝑖𝑛 повторять: 4: 𝑠 ′ = 𝑠 5: Случайный выбор процедуры 𝑘 с учётом текущих весов 𝑤 𝑖 6: 𝑛 𝑘 = 𝑛 𝑘 + 1 7: Применение процедуры 𝑘 к 𝑠 ′ : 𝑠 ′ = 𝑈𝑝𝑑𝑎𝑡𝑒 𝑘 (𝑠 ′ ) 8: Если 𝑓(𝑠 ′ ) < 𝑓(𝑠) ∶ 9: 𝑠 = 𝑠 ′ 10: Если 𝑓(𝑠) < 𝑓(𝑠 𝑏𝑒𝑠𝑡 ) ∶ 11: 𝑠 𝑏𝑒𝑠𝑡 = 𝐿𝑜𝑐𝑎𝑙𝑂𝑝𝑡(𝑠) 12: 𝑐 𝑘 = 𝑐 𝑘 + 𝜎 1 13: Иначе ∶ 14: 𝑐 𝑛 = 𝑐 𝑛 + 𝜎 2 15: Иначе, если 𝑝 = 𝑟𝑎𝑛𝑑𝑜𝑚(0; 1) ≤ 𝑒𝑥𝑝 ( 𝑓(𝑠) − 𝑓(𝑠 ′ ) 𝜏 ) ∶ 16: 𝑠 = 𝑠 ′ 17: 𝑐 𝑛 = 𝑐 𝑛 + 𝜎 3 18: 𝜏 = 𝜑 ∗ 𝜏 19: Если число выполненных итераций кратно 𝑇 ∶ 20: Обновить веса: если 𝑛 𝑖 > 0, 𝑤 𝑖 = (1 − 𝜃)𝑤 𝑖 + 𝜃 𝑐 𝑖 𝑛 𝑖 21: Обнулить счётчики: 𝑐 𝑖 = 0, 𝑛 𝑖 = 0 Параметрами алгоритма являются начальная и минимальная температуры 𝜏 𝑠𝑡𝑎𝑟𝑡 и 𝜏 𝑚𝑖𝑛 , скорость «охлаждения» 0 < 𝜑 < 1, очки успеха 𝜎 1 , 𝜎 2 и 𝜎 3 , коэффициент реакции 𝜃, а также период обновления 𝑇. Ориентировочно, эти 26 параметры могут иметь следующие значения: 𝜏 𝑠𝑡𝑎𝑟𝑡 = 30000, 𝜏 𝑚𝑖𝑛 = 0.01, 𝜑 = 0,9994, 𝜎 1 = 10, 𝜎 2 = 5, 𝜎 3 = 2, 𝜃 = 0.3, 𝑇 = 200, впрочем возможна и специальная настройка этих значений для эффективного решения однотипных задач некоторой группы. Глава 3. Динамическая адаптация алгоритмов 3.1. Введение в динамическую адаптацию Принцип оптимальности сформулирован Беллманом в 1957 году [39]. Согласно его определению, «оптимальное решение обладает таким свойством, что независимо от начальных данных и начальной точки, оставшееся решение будет оптимальным, с учетом реализации первой точки». Таким образом, оптимальное решение сохраняет свойство оптимальности на любых подзадачах. Эвристические алгоритмы не гарантируют оптимальности решения, и, если полученное решение не оптимально, используя принцип оптимальности, можно заключить, что существует подзадача исходной задача, такая что соответствующее частичное решение также будет не оптимальным. Данный принцип лежит в основе предлагаемых далее идей устойчивости решений во времени и метода динамической адаптации алгоритмов. Так, выявление не-оптимальной подзадачи даёт возможность дополнительно улучшить решение с меньшими затратами вычислительных ресурсов и времени, поскольку подзадача по своей сути имеет меньшую размерность, чем исходная полная задача. Далее предлагается метод оптимизации, основанный на выявлении и улучшении частичных решений, названный Динамической адаптацией алгоритма. С другой стороны, исследуя подзадачи, возникающие в реальном времени при реализации решения, можно вывести экспериментальный критерий 27 возможности их улучшения, названный далее уровнем состоятельности во времени. 3.2. Оценка состоятельности во времени Рассмотрим следующую схему вычислительных экспериментов. Пусть дано множество тестовых примеров 𝑃 для некоторой модели задачи маршрутизации. Для каждого примера 𝑝 ∈ 𝑃 генерируем с помощью алгоритма множество 𝑁(𝑝) различных решений 𝑠(𝑝) ∈ 𝑁(𝑝). Пусть задан некоторый метод разбиения решения 𝑠(𝑝) на последовательность сегментов так, что это соответствует реальному ходу времени. Положим номера этих сегментов 𝑘 = 1, … , 𝐾(𝑠(𝑝)). Обозначим за 𝑠(𝑘, 𝑝) оставшуюся последовательность сегментов решения после шага 𝑘, то есть совокупность сегментов (𝑘 + 1, 𝑘 + 2, … , 𝐾(𝑠(𝑝))). Положим, что на шаге 𝑘 решение находится в момент времени 𝑡(𝑘). На шаге 𝑘 построим подзадачу 𝑝 ′ (𝑘) на интервале [𝑡(𝑘); 𝑇], причем сегменты, уже посещённые до момента 𝑡(𝑘), будем считать зафиксированными как часть начальных условий задачи 𝑝 ′ (𝑘). Далее, пользуясь тем же самым алгоритмом, получаем частичное решение 𝑠(𝑝 ′ (𝑘)) для построенной подзадачи. Определение. Решение 𝑠(𝑝) – состоятельное во времени, если для каждого 𝑘 = 1, … , 𝐾(𝑠(𝑝)) выполняется неравенство 𝑓(𝑠(𝑘, 𝑝)) ≤ 𝑓(𝑠(𝑝′(𝑘))), где 𝑓 – целевая функция текущей задачи. Очевидно, что оптимальные решения всегда будут состоятельными во времени, согласно принципу оптимальности Беллмана. Более того, если эвристический алгоритм является детерминированным, то в любой подзадаче частичные решения будут совпадать с исходным. Таким образом, данное понятие состоятельности во времени актуально только для рандомизированных эвристик, которые, впрочем, составляют основную массу исследуемых алгоритмов маршрутизации. 28 Отметим, что в зависимости от особенностей конкретного алгоритма и особенностей конкретной рассматриваемой модели, несостоятельность во времени может проявляться в большей или меньшей степени при анализе решений, как и может не проявляться совсем, даже если решения не являются оптимальными. Продолжая построение вычислительных экспериментов, положим что для каждого решения 𝑠 ∈ 𝑁(𝑝) проведено 𝑀(𝑠) экспериментов. Отдельный эксперимент состоит в проверке решения на состоятельность во времени. Обозначим за 𝑏(𝑠, 𝑘) число экспериментов, в которых временная состоятельность решения 𝑠 нарушается на шаге 𝑘. Если бы решение 𝑠 было бы оптимальным, то выполнялось бы равенство ∑ 𝑏(𝑠, 𝑘) 𝐾(𝑠) 𝑘=1 = 0. Но так как эвристики не гарантируют оптимальность, то можно утверждать лишь справедливость неравенства: ∑ 𝑏(𝑠, 𝑘) 𝐾(𝑠) 𝑘=1 ≤ 𝑀(𝑠). Определение. Экспериментальным уровнем временно́й состоятельности (𝑐𝑜𝑛𝐿) будем называть величину, вычисляемую как 𝑐𝑜𝑛𝐿 = 1 − 1 |𝑃| × ∑ 1 |𝑁(𝑝)| ∑ 1 𝑀(𝑠) ∑ 𝑏(𝑠, 𝑘) 𝐾(𝑠) 𝑘=1 𝑠∈𝑁(𝑝) 𝑝∈𝑃 (3.1) Отметим, что 0 ≤ 𝑐𝑜𝑛𝐿 ≤ 1. Высокий уровень временной состоятельности алгоритма указывает на то, что ожидаемые решения будут «более устойчивы» во времени, по сравнению с ожидаемыми решениями алгоритма с меньшим значением этого критерия. 3.3. Динамическая адаптация алгоритмов Итеративный метод улучшения решений для задачи маршрутизации транспорта (а точнее, кооперативной игры маршрутизации транспорта) был предложен в [40], и развит для случая задачи маршрутизации запасов в [41]. 29 Используя основную идею метода, мы адаптируем его для общего случая модели маршрутизации и абстрактного алгоритма решения. Фактически, метод представляет собой моделирование реализации решения во времени. Данная реализация на практике – это последовательное посещение точек маршрутов, последовательно перебирая их соответственно моментам времени. Элементарная единица решения (в рассматриваемой дискретной задаче) есть перемещение в следующую точку маршрута или переход в следующий период планирования, если задача подразумевает долгосрочное планирование В каждый момент времени мы всё ещё потенциально имеем возможность изменить план решения, но только для находящихся в будущем элементов, так как реализованные действия в прошлом становятся константами. Далее, используем следующие обозначения. Пусть 𝐴(∙) обозначает функцию адаптируемого алгоритма, 𝑠 – решение, полученное с помощью алгоритма, 𝑆 1 – последовательность посещенных сегментов решения, 𝑆 2 – последовательность оставшихся не посещённых сегментов, 𝐶 – константы задачи, 𝑓 – целевая функция. Общая схема Динамической адаптации представлена ниже в Алгоритме 2. Алгоритм 2. Динамическая адаптация алгоритма 0: Инициализация: начальное решение 𝑠 0 , 𝑆 1 = ∅, 𝑆 2 = 𝑠 0 1: Пока 𝑆 2 ≠ ∅ ∶ 2: 𝑠 = 𝐴 ( 𝑆 2 , 𝐶 ) 3: Если 𝑓(𝑠) < 𝑓(𝑆 2 ) ∶ 𝑆 2 = 𝑠 4: 𝐶 ← 𝑆 2 [1], 𝑆 1 ← 𝑆 2 [1], 𝑆 2 = 𝑆 2 ∖ 𝑆 2 [1] 3.4. Неустойчивая задача. Пример IRP. Для динамической адаптации был выбран алгоритм ALNS. Алгоритм адаптации был реализован на языке C++. Вычислительные эксперименты проводились на HPC-кластере кафедры Моделирования Электромеханических и 30 Компьютерных Систем, факультета Прикладной Математики – Процессов Управления, СПбГУ. Характеристики кластера: ОС Linux SLES 11 SP1, 12 узлов, каждый с двумя четырёхъядерными процессорами Intel Xeon 5335, 16 ГБ ОЗУ на узел. Для использования в данной работе была выбрана библиотека тестовых примеров для задачи маршрутизации запасов Coelho, так как представляет хорошую вариативность примеров и точно согласуется с рассматриваемой моделью. Примеры находятся в открытом доступе в интернете на ресурсе [42]. Тестовые пример выбранной библиотеки генерировались с помощью случайного механизма. Для проведения экспериментов было взято 20 тестовых примеров из библиотеки [42]. Выбранные примеры различаются по стоимости хранения (ℎ: высокая или низкая), числу периодов в рассматриваемом промежутке времени (𝑇: 3 или 6) и числу клиентов (𝑛: 10/20/30/40/50/100). Эти характеристики также представлены в Таблице 1 в столбце «пример». Для каждого примера в ходе эксперимента генерировалось 100 решений, среди которых для дальнейшего рассмотрения выбирались 𝑁(𝑝) различных. На каждом уникальном решении, как на начальном, Динамический алгоритм был запущен 𝑀 раз (единица для больших примеров: 6 × 50 и 6 × 100, десять для остальных). В качестве результатов собирались следующие данные: начальное значение целевой функции, конечное предполагаемое значение целевой функции (начальное значение минус сумма всех улучшений), конечное пересчитанное значение целевой функции (на собранном конечном решении), номера шагов, на которых получено улучшение, и величины этих улучшений. Из-за особенностей реализации, учитываются два значения конечной целевой функции, так как эти значения могут различаться: как предполагаемое значение может быть меньше, чем реальное, при ошибочном улучшении, так и реальное может быть меньше, 31 чем предполагаемое, из-за возможной дополнительной выгоды, при пересчёте решения. Полученные данные обрабатывались в среде Wolfram Mathematica. По результатам экспериментов, был подсчитан экспериментальный уровень временной состоятельности для задачи маршрутизации запасов с использованием алгоритма ALNS: 𝑐𝑜𝑛𝐿 = 0,545424 Далее используются следующие дополнительные обозначения. 𝑁1 – общее число нарушений временной состоятельности среди 𝑁(𝑝) × 𝑀 тестов. 𝑁2 – число несостоятельных во времени решений, т. е. несостоятельных в каждом из 𝑀 тестов. Аналогично, 𝑁3 – это число полностью состоятельных во времени решений. Отметим, что 𝑁2 + 𝑁3 ≤ 𝑁(𝑝). Указанные значения приведены в Таблице 2. В двух последних столбцах Таблицы 2 (ALNS и DALNS) приведено сравнение результатов обычного алгоритма ALNS и его динамической адаптации. Представлены средние значения и стандартные отклонения (𝜎) для выборки значений целевой функции в каждом случае. Как можно видеть, в большей части случаев применения динамический алгоритм показал улучшение обычного решения, за исключением разве что примеров малой размерности, в которых получаемые решения уже являются оптимальными или очень близкими к оптимальному. Суммарно, число экспериментов, в которых было получено улучшение, равно 5236, что составляет 46% от общего их числа (11360). На примерах большей размерности динамический алгоритм показывает растущую эффективность, так как при увеличении размерности эффективность базового алгоритма понижается и решения дальше отдаляются от оптимума, что оставляет больше возможностей для дополнительной оптимизации. В части экспериментов, динамический алгоритм показывает существенное улучшение, 32 до 22% от начального решения. В среднем же, улучшение начального решения находиться в пределах 0–6,8%, в зависимости от рассматриваемого примера. Таблица 2. Результаты реализации динамической адаптации пример N(p) M N1 N2 N3 ALNS DALNS h T n Сред. 𝑓 𝜎 Сред. 𝑓 𝜎 ни зк ая 3 10 7 10 0 0 7 1625,04 56,5964 1625,04 56,5964 20 26 10 0 0 26 2695,07 351,649 2695,07 351,649 30 72 10 18 1 67 3770,14 406,636 3770,07 406,12 40 74 10 73 5 61 4284,57 483,59 4267,39 448,406 50 92 10 38 2 85 4647,59 375,56 4638,27 347,246 6 10 51 10 323 25 10 3787,11 172,105 3716,21 152,237 20 100 10 783 68 13 6143,56 459,988 5922,44 384,808 30 100 10 827 61 4 8113,19 597,666 7807,11 471,044 50 100 1 90 90 10 10526,8 624,891 10209,2 709,574 100 100 1 75 75 25 16873 938,445 16507,2 912,191 вы сок ая 3 10 7 10 0 0 7 3663,97 55,3075 3663,97 55,3075 20 30 10 17 0 24 6040,8 266,576 6039,99 265,39 30 87 10 125 4 64 10140,3 361,031 10129,3 330,997 40 87 10 180 14 62 11398,7 445,25 11377 392,563 50 91 10 197 13 67 12360,4 305,425 12348,1 290,239 6 10 72 10 585 48 6 7574,81 191,467 7484,25 193,026 20 100 10 833 70 8 13045,5 361,751 12900,8 333,288 30 100 10 884 81 5 20357,3 527,622 20165,1 422,808 50 100 1 94 94 6 27358,4 656,647 27109,8 635,106 100 100 1 94 94 6 52188,2 780,861 51821,9 698,469 3.5. Устойчивая задача. Пример PDP. Аналогично с предыдущей задачей, для решения Задачи сбора и доставки был адаптирован алгоритм ALNS, вместе с методом динамической адаптации. Все алгоритмы были также реализованы на языке C++. Для проведения экспериментов, в отличие от предыдущего случая, был использован персональный компьютер – на ОС Windows 10, c двухъядерным процессором Intel Core i5 и 4Гб оперативной памяти. Для экспериментов была использована библиотека тестовых примеров Li & Lim [43], содержащая постановки задач сбора и доставки с временными окнами 33 (PDPTW). Со всеми 344 доступными примерами была проведена проверка состоятельности во времени. Примеры, в основном, различаются по количеству заказов: 100, 200, 400, 600, 800 и 1000. В отличие от предыдущего случая, для каждого отдельного примера был проведён 1 запуск алгоритма ALNS и 1 запуск динамической адаптации, с проверкой временной состоятельности. Во время экспериментов собирались аналогичные предыдущей группе экспериментов данные, плюс данные по времени работы алгоритмов, которые так же обрабатывались в среде Wolfram Mathematica. По результатам экспериментов, был подсчитан экспериментальный уровень временной состоятельности для задачи сбора и доставки с временными окнами с использованием алгоритма ALNS: 𝑐𝑜𝑛𝐿 = 0,395349 Агрегированные результаты экспериментов представлены ниже в Таблице 3. Следующие обозначения были использованы: 𝑛 – примерное количество пар заказов в группе примеров; 𝑀 – количество примеров в группе; 𝑁1 – число нарушений временной состоятельности в группе примеров. Улучшение DALNS вычислялось в каждом отдельном эксперименте как отношение суммарных улучшений на каждом шаге работы DALNS и начального решения, полученного ALNS. Статистические значения минимума, максимума и среднего значения улучшения по каждой группе также приведены в таблице ниже. В дополнение, в последнем столбце представлены среднего значения дополнительного времени, затраченного на выполнение динамически адаптированного алгоритма, по сравнению с исходным временем ALNS. 34 Таблица 3. Результаты динамической адаптации на PDPTW Примеры 𝑁1 Улучшение DALNS, % Доп. время DALNS, % 𝑛 𝑀 𝑀𝑖𝑛 𝑀𝑎𝑥 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 100 56 3 0,00 4,10497 0,085323 362,703 200 60 23 0,00 8,4197 0,289145 271,552 400 60 39 0,00 2,5684 0,318022 130,929 600 58 47 0,00 2,46471 0,407474 100,946 800 57 50 0,00 2,23131 0,43562 76,042 1000 53 46 0,00 3,24252 0,562285 56,5242 Аналогично экспериментам с задачей IRP, результаты показывают растущую временную неустойчивость с ростом размерности задач. Таким же образом, можно заключить, что с ростом размерности исходное решение становиться всё более удалённым от оптимального, что оставляет больше возможностей для дополнительного улучшения. Суммарно, количество случаев, в которых было найдено какое-либо улучшение составляет 60,5%, что больше, чем в случае задачи IRP. Однако, с другой стороны, величина улучшения в среднем гораздо меньше: 0-0,56% в среднем и до 8,45% максимально. Если предположить улучшения меньше 1% несущественными по сравнению с затраченным временем, доля неустойчивых решений резко снижается до 10,75%, что делает задачу сильно устойчивой в этом понимании: условный экспериментальный уровень состоятельности во времени 𝑐𝑜𝑛𝐿 ∗ будет равен: 𝑐𝑜𝑛𝐿 ∗ = 0,8925 |