Вкр. Факультет прикладной математики процессов управления Кафедра математического моделирования энергетических систем Широких Вячеслав Андреевич
 Скачать 1.83 Mb.
|
|
Глава 4. Кооперативные задачи маршрутизации 4.1. Введение В ситуации, когда несколько перевозчиков организуют доставку и обслуживание разных групп клиентов на одной территории, существует возможность их горизонтальной кооперации с целью выявления общего более эффективного плана посещений и доставки. Подобное сотрудничество может отрывать перспективы для существенной экономии, при правильной организации. В научной литературе, впрочем, этот вопрос рассматривается лишь отчасти. По большей части, работы в данной области посвящены либо разбору путей кооперации, что охватывает первоначальный процесс принятия решений и игнорирует сложности нахождения решений для задач маршрутизации [44], либо вопросам дележа выигрыша коалиций в кооперативной модели [45]. Существуют небольшое число работ, которые рассматривают задачи маршрутизации в совокупности с моделью кооперативной теории игр. Однако, в данных работах не принимается во внимание характер эвристических решений [46], либо же анализ ведётся непосредственно оптимальных решений [47]. На практике же, при использовании эвристических решений в общем случае не соблюдаются отдельные базовые предположения кооперативной теории, что иногда может приводить к неустойчивой структуре коалиций. На эту проблему было впервые обращено внимание в работе [40], и в данной работе проводится дальнейшее её исследование. В кооперативной теории игр существует множество различных методов дележа выигрыша внутри коалиции, однако их применение требует явного задания характеристической функции, обладающей свойством супераддивности (для задач максимизации выгоды) или субаддитивности (для задач минимизации 36 затрат). Наши исследования, в свою очередь, показывают, что эти условия нарушаются в общем случае, если для построения характеристической функции используются потенциально суб-оптимальные эвристические решения. 4.2. Построение кооперативной модели IRP Рассмотрим задачу маршрутизации запасов, и на её основе построим обобщение задачи на кооперативный случай, Кооперативную игру маршрутизации запаса. Предположим, что имеется направленный граф 𝐺 = ({𝑀, 𝑁}, 𝐴), в котором 𝑀 = {1, … , 𝑚} является множеством перевозчиков, представленных своими депо, 𝑁 = {1, … , 𝑛} – общее множество клиентов в задаче, и 𝐴 – набор всех путей между точками 𝑀 ∪ 𝑁 вида (𝑖, 𝑗). Каждому перевозчику 𝑖 ∈ 𝑀 соответствует подмножество его собственных клиентов 𝑁 𝑖 ⊆ 𝑁. Индивидуально, перед каждым перевозчиком стоит проблема нахождения решения в стандартной задаче маршрутизации запаса на частичном графе 𝐺 = ({𝑖} ∪ 𝑁 𝑖 , 𝐴 𝑖 ) . Мы предполагаем также, что множества клиентов не пересекаются: ∀𝑖 1 , 𝑖 2 ∈ 𝑀, 𝑖 1 ≠ 𝑖 2 ⇒ 𝑁 𝑖 1 ∩ 𝑁 𝑖 2 = ∅. Стоимости перемещения по путям (𝑖, 𝑗) ∈ 𝐴 считаются известными и заданными величинами 𝑐 𝑖𝑗 > 0. Горизонт планирования будем считать общим и равным 𝑇. В начале каждого периода в каждом депо 𝑖 производится 𝑟 𝑖 единиц продукции, а каждый клиент 𝑗 потребляет 𝑑 𝑗 единиц продукции из своего запаса, дефицит не допустим. Будем рассматривать задачу, в которой в распоряжении каждого перевозчика находится одно транспортное средство. В течение одного периода каждое транспортное средство может совершить один маршрут посещения 37 клиентов. При этом, максимальная вместимость запаса каждого ограничена 𝑄 единицами. Каждый клиент может хранить запас продукции для дальнейшего потребления. Объём хранимого клиентом 𝑗 запаса на конец периода 𝑡 выражается переменными 𝐼 𝑖𝑡 . Этот объём не может опускаться ниже нуля или превышать максимальную вместимость склада 𝑈 𝑗 . Хранение запаса между периодами планирования стоит ℎ 𝑗 за единицу продукции. Переменными в задаче являются маршруты посещения и объёмы доставки. Целью оптимизации является минимизация суммарных затрат на перевозку и хранение в течение всего горизонта планирования. Предположим, что перевозчики из 𝑀 могут объединяться в коалиции 𝑆 ⊆ 𝑀. Задачей каждой такой коалиции будет обслужить объединённое множество клиентов 𝑁 𝑆 = ⋃ 𝑁 𝑖 𝑖∈𝑆 с помощью доступных перевозчикам из 𝑆 транспортных средств. Отметим также, что при условии 𝑆 1 ∩ 𝑆 2 = ∅ множества клиентов также не будут пересекаться: 𝑁 𝑆 1 ∩ 𝑁 𝑆 2 = ∅. Задачей коалиции, таким образом, будет решение специального случая задачи маршрутизации запаса с несколькими депо и несколькими транспортными средствами на графе 𝐺 = (𝑆 ∪ 𝑁 𝑆 , 𝐴 𝑆 ). Построим специальный случай IRP в форме линейного целочисленного программирования. Для этого, введём переменные 𝑥 𝑖𝑗𝑡 , принимающие значение 1, если маршрут проходит по пути (𝑖, 𝑗), и значение 0 иначе; переменные 𝑞 𝑗𝑡 , равные объёму доставки клиенту 𝑗 в период 𝑡; и, также, вспомогательные переменные 𝑠 𝑖𝑡 , отражающие накопленный в текущем маршруте спрос на момент посещения клиента 𝑖 в периоде 𝑡, и необходимые для исключения замкнутых петель в маршрутах. Уровень запаса депо и складов в начале первого периода считается известным и заданным константами 𝐼 𝑖0 = 𝐼 𝑖 0 = 𝑐𝑜𝑛𝑠𝑡, ∀𝑖 ∈ 𝑀 ∪ 𝑁. 38 Таким образом, специальная задача IRP для коалиции 𝑆 может быть представлена в следующем виде: 𝑓(𝑆) = ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗𝑡 𝑗∈𝑆∪𝑁 𝑆 𝑖∈𝑆∪𝑁 𝑆 𝑇 𝑡=1 + ∑ ∑ ℎ 𝑖 𝐼 𝑖𝑡 𝑖∈𝑆∪𝑁 𝑆 𝑇 𝑡=1 → 𝑚𝑖𝑛 (4.1) При ограничениях: ∑ 𝑥 𝑖𝑗𝑡 𝑖∈𝑁 𝑆 = ∑ 𝑥 𝑗𝑖𝑡 𝑖∈𝑁 𝑆 ≤ 1, 𝑗 ∈ 𝑆 ∪ 𝑁 𝑆 , 𝑡 = 1, … , 𝑇 (4.2) 𝐼 𝑖𝑡 = 𝐼 𝑖,𝑡−1 + 𝑟 𝑖 − ∑ 𝑠 𝑗𝑡 𝑥 𝑗𝑖𝑡 𝑗∈𝑁 𝑆 , 𝑖 ∈ 𝑆, 𝑡 = 1, … , 𝑇 (4.3) 𝐼 𝑗𝑡 = 𝐼 𝑗,𝑡−1 − 𝑑 𝑗 + 𝑞 𝑗𝑡 , 𝑗 ∈ 𝑁 𝑆 , 𝑡 = 1, … , 𝑇 (4.4) 0 ≤ 𝐼 𝑖𝑡 ≤ 𝑈 𝑖 , 𝑖 ∈ 𝑆 ∪ 𝑁 𝑆 , 𝑡 = 1, … , 𝑇 (4.5) 𝑠 𝑖𝑡 − 𝑠 𝑗𝑡 + 𝑄𝑥 𝑖𝑗𝑡 ≤ 𝑄 − 𝑞 𝑗𝑡 , 𝑖, 𝑗 ∈ 𝑁 𝑆 , 𝑖 ≠ 𝑗, 𝑡 = 1, … , 𝑇 (4.6) 𝑞 𝑖𝑡 ≤ 𝑠 𝑖𝑡 ≤ 𝑄, 𝑖 ∈ 𝑁 𝑆 , 𝑡 = 1, … , 𝑇 (4.7) Целевая функция (4.1) представляет собой сумму общих затрат на перевозку и общих затрат на хранение. Равенства левых частей (4.2) гарантируют непрерывность маршрута в рассматриваемых переменных, а неравенства в их левой части представляют собой ограничения на количество посещений и количество маршрутов из каждого депо. Ограничения (4.3) и (4.4) задают динамику запаса в депо и на складах клиентов соответственно. Ограничения на вместимость складов представлены неравенствами (4.5). Неравенства (4.6) выполняют две функции. Во-первых, они задают динамику увеличения спроса по ходу маршрута: при 𝑥 𝑖𝑗𝑡 = 1 неравенства принимают вид 𝑠 𝑗𝑡 ≥ 𝑠 𝑖𝑡 + 𝑞 𝑗𝑡 . Во- вторых, они неявным образом исключают возможность образования замкнутых маршрутов, без соединения с депо. Последняя группа неравенств (4.7) задаёт, с одной стороны, отправное значение для спроса в маршруте, а с другой – ограничения на вместимость транспортных средств. 39 4.3. Характеристическая функция Формулировка кооперативной игры требует задания характеристической функции. Определение. Характеристической функцией называется функция 𝑐: 2 𝑀 → ℝ, заданная на множестве всех возможных коалиций 2 𝑀 , и удовлетворяющая условию 𝑐(∅) = 0. Основным условием формирования рациональной коалиции, т.е. коалиции, при объединении в которую каждый участник уменьшает свои затраты, является условие субаддитивности характеристической функции: ∀𝑆, 𝑇 ⊂ 𝑀: 𝑆 ∩ 𝑇 = ∅, 𝑐(𝑆 ∪ 𝑇) ≤ 𝑐(𝑆) + 𝑐(𝑇) (4.8) Очевидно, что для двух непересекающихся коалиций 𝑆, 𝑇 оптимальные значения 𝑓 𝑜𝑝𝑡 целевой функции (4.1) будут удовлетворять условию субаддитивности: 𝑓 𝑜𝑝𝑡 (𝑆 ∪ 𝑇) ≤ 𝑓 𝑜𝑝𝑡 (𝑆) + 𝑓 𝑜𝑝𝑡 (𝑇) (4.9) На практике же, получить оптимальное решение и точное минимальное значение целевой функции может быть проблематично, особенно для задач большого размера, что приводит к необходимости использования эвристических методов. При таком подходе, решая задачу (4.1)-(4.7) для коалиции 𝑆 можно получить эвристическое значение целевой функции 𝑓 ℎ (𝑆). Поскольку эвристические алгоритмы не гарантируют оптимальности решения, будет иметь место лишь следующее неравенство: 𝑓 𝑜𝑝𝑡 (𝑆) ≤ 𝑓 ℎ (𝑆) (4.10) Сочетая (4.9) и (4.10), можно получить неравенства: 40 𝑓 𝑜𝑝𝑡 (𝑆 ∪ 𝑇) ≤ 𝑓 ℎ (𝑆 ∪ 𝑇), 𝑓 𝑜𝑝𝑡 (𝑆 ∪ 𝑇) ≤ 𝑓 ℎ (𝑆) + 𝑓 ℎ (𝑇) (4.11) Поскольку невозможно предсказать заранее разницу между оптимальным и эвристическим решением, в некоторых случаях будет возникать ситуация: 𝑓 ℎ (𝑆 ∪ 𝑇) > 𝑓 ℎ (𝑆) + 𝑓 ℎ (𝑇) (4.12) Таким образом, можно заключить, что в общем случае функция эвристических значений 𝑓 ℎ не обладает свойством субаддитивности и не может быть использована как характеристическая функция для формирования устойчивых коалиций. Одним методом решения данной проблемы является использование специального алгоритма построения характеристической функции, берущего в основу эвристические значения – алгоритма прямой индукции коалиций (Direct Coalition Induction, DCI): 𝑐(𝑆) ≝ { 𝑓 ℎ (𝑆), |𝑆| = 1 min {𝑓 ℎ (𝑆), min 𝐿⊂𝑆 (𝑐(𝑆 ∖ 𝐿) + 𝑐(𝐿))} , |𝑆| > 1 (4.13) Теорема. (Захаров, Щегряев) Характеристическая функция, построенная на основе эвристических значений с помощью алгоритма DCI будет обладать свойством субаддитивности (4.8). 4.4. Пример построения характеристической функции Возьмём за основу уже использованные ранее тестовые примеры из библиотеки [42]. Из трёх примеров abs1n10, abs2n10 and abs3n10 составим постановку кооперативной игры маршрутизации запаса так, как это показано на 41 рисунке 1. Депо и соответствующие ему клиенты каждого отдельного примера представлены отдельными цветами. В полученном примере, возможны семь различных коалиций игроков, и для каждой из них было найдено эвристическое значение 𝑓 ℎ . Результаты вычислений, для двух алгоритмов – ALNS и DALNS – представлены в таблице 4 ниже. Таблица 4. Эвристические значения 𝑓 ℎ (𝑆), полученные с ALNS и DALNS Коалиция {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} Решение ALNS 10988.3 11443.5 9866.42 21135.3 22062.7 21567.3 30335.8 Решение DALNS 7885.53 8407.1 7588.8 15839.9 15702.4 15316.7 22735.3 Полученные решения проиллюстрированы на рисунках 2 и 3. В верхней части – комбинация индивидуальных решений игроков, а в нижней – кооперативное решение для полной коалиции {1,2,3}. Два рисунка отражают, соответственно, решения, полученные с помощью ALNS, на рисунке 2, и решения, полученные с помощью DALNS, на рисунке 3. Рис. 1. Кооперативная игра маршрутизации запаса 42 Рисунок 2. Решения ALNS Рисунок 3. Решения DALNS Основываясь на значениях таблицы 4 и используя алгоритм прямой индукции коалиций (4.13) построим характеристические функции для решений ALNS и DALNS. Согласно алгоритму прямой индукции коалиций, установим начальные значения по умолчанию: 𝑐({1}) ≝ 𝑓 ℎ ({1}), 𝑐({2}) ≝ 𝑓 ℎ ({2}), 𝑐({3}) ≝ 𝑓 ℎ ({3}). Для коалиции {1,2} имеем следующее неравенство: 𝑓 ℎ ({1,2}) = 21135.3 < 𝑐({1}) + 𝑐({2}) = 22431.8. Поэтому, устанавливаем 𝑐({1,2}) = 𝑓 ℎ ({1,2}) = 21135.3. 𝑓 ℎ ({1,3}) = 22062.7 > 𝑐({1}) + 𝑐({3}) = 20854.72 ⇒ 𝑐({1,3}) = 20854.72 43 𝑓 ℎ ({2,3}) = 21567.3 > 𝑐({2}) + 𝑐({3}) = 21309.92 ⇒ 𝑐({2,3}) = 21309.92 Наконец, для полной коалиции {1,2,3} имеем следующие неравенства: { 𝑓 ℎ ({1,2,3}) = 30335.8 < 𝑐({1,2}) + 𝑐({3}) = 31001.72 𝑓 ℎ ({1,2,3}) = 30335.8 < 𝑐({1}) + 𝑐({2,3}) = 𝑐({1,3}) + 𝑐({2}) = 32298.22 ⇒ 𝑐({1,2,3}) = 𝑓 ℎ ({1,2,3}) = 30335.8 Аналогичные выкладки проводятся и для решений DALNS: 𝑓 ℎ ({1,2}) < 𝑐({1}) + 𝑐({2}) = 16292.69 ⇒ 𝑐({1,2}) = 𝑓 ℎ ({1,2}) = 15839.9 𝑓 ℎ ({2,3}) < 𝑐({2}) + 𝑐({3}) = 15995.96 ⇒ 𝑐({2,3}) = 𝑓 ℎ ({2,3}) = 15316.7 𝑓 ℎ ({1,3}) > 𝑐({1}) + 𝑐({3}) ⇒ 𝑐({1,3}) = 𝑐({1}) + 𝑐({3}) = 15474.33 { 𝑓 ℎ ({1,2,3}) = 22735.3 < 𝑐({1}) + 𝑐({2,3}) = 23202.23 𝑓 ℎ ({1,2,3}) = 22735.3 < 𝑐({1,2}) + 𝑐({3}) = 23428.7 𝑓 ℎ ({1,2,3}) = 22735.3 < 𝑐({1,3}) + 𝑐({2}) = 23881.49 ⇒ 𝑐({1,2,3}) = 𝑓 ℎ ({1,2,3}) = 22735.3 Таким образом, для каждого отдельного алгоритма была построена субаддитивная характеристическая функция, и, по определению, задана постановка кооперативной игры. 4.5. Вычислительные эксперименты Для вычислительных экспериментов были использованы алгоритмы, реализованные для экспериментов главы 4, с отдельными модификациями под специальный случай задачи маршрутизации и хранения с несколькими депо и несколькими транспортными средствами. Вычисления также были проведены на HPC-кластере кафедры Моделирования Электромеханических и Компьютерных Систем, факультета Прикладной Математики – Процессов Управления, СПбГУ. 44 В качестве основы для построения тестовых примерах была взята использованная ранее библиотека примеров IRP [42]. Каждый пример кооперативной игры маршрутизации запасов был построен путём комбинирования трёх примеров стандартной IRP одного размера, аналогично предыдущему разделу. В итоге, было создано 18 тестовых примеров кооперативной задачи: для случая 3 периодов планирования – содержащие в сумме 90, 120 и 150 клиентов, каждый с вариацией с высокой и с низкой стоимостью хранения, для случая 6 периодов планирования – содержащие в сумме 30, 60, 90, 150, 300 и 600 клиентов, каждый с вариацией с высокой и с низкой стоимостью хранения. Для каждого примера и каждой подзадачи для каждой коалиции в примере было проведено от 100 до 2000 запусков DALNS (что одновременно даёт и статистику по решениям ALNS), в зависимости от размера примера и времени вычисления. Собранная статистика была агрегирована до минимального, максимального и среднего значений по выборке для каждой отдельной коалиции. Далее, для адекватного сравнения, полученные данные были просуммированы для отражения коалиционной ситуации с учётом всех участников, т.е., например, при отсутствии кооперации ситуация будет иметь вид (1,2,3), и значениями для сравнения будут суммы индивидуальных значений каждого игрока: 𝑓 ℎ ({1}) + 𝑓 ℎ ({2}) + 𝑓 ℎ ({3}), а при кооперации только игроков 1 и 3 ситуация будет иметь вид (2,13), и значением для сравнения будет 𝑓 ℎ ({2}) + 𝑓 ℎ ({1,3}). Пример агрегированных данных по одному примеру представлен ниже в Таблице 5, а полную статистику по всем полученным данным можно найти в таблице в Приложении 1. 45 Таблица 5. Пример агрегированных данных вычислительных экспериментов Размерность примера Примеры IRP в основе Алгоритм Минимум/Среднее/Максимум для ситуации: 1,2,3 1,23 2,13 3,12 123 (3,90, 𝑙𝑜𝑤) abs1n30 abs2n30 abs3n30 ALNS 9223.96 10308.5 13076.3 8203.18 9898.38 12090. 8117.86 10335.6 12763. 8030.97 9937.85 12102.6 7171.8 9284.36 10999.3 DALNS 9223.96 10305.5 12989.8 8203.18 9855.08 12053.7 8117.86 10290.5 12044.8 8030.97 9864.3 11992.6 7058.08 9239.98 10929. Для визуализации полученных данных, была дополнительно разработана специальная форма графиков, представленная на рисунках 4-9. Данные по каждой коалиционной ситуации представлены в виде отрезка от минимального до максимального значения, причём тёмная часть отрезка соответствует значениям от среднего до максимального значения, а светлая – от минимального до среднего. В дополнение, на графиках для каждой ситуации представлены два отрезка: красный отражает выборку решений ALNS, а синий – решений DALNS. Рисунок 4. (3,90, 𝑙𝑜𝑤) Рисунок 5. (3,120, ℎ𝑖𝑔ℎ) 46 Рисунок 6. (6,90, 𝑙𝑜𝑤) Рисунок 7. (6,30, ℎ𝑖𝑔ℎ) Рисунок 8. (6,300, 𝑙𝑜𝑤) Рисунок 9. (6,600, ℎ𝑖𝑔ℎ) Из полученных данных можно вывести следующие общие выводы. Во-первых, результаты показывают существенную выгоду при кооперации перевозчиков. Сравнивая ситуации индивидуальной работы и полной кооперации, можно видеть, что во всех случаях среднее статистическое значение расходов полной коалиции всегда строго меньше суммы средних значений индивидуальных значений. Расчёты показывают, что это улучшение лежит в 47 интервале от 1,1% до 25,1%, со средним значением равным 12,24%, для решений ALNS, и в интервале [2,18%, 20,65%], со средним 9,77%, для решений DALNS. Однако, рассматривая аналогичным образом лучшие (минимальные по стоимости) решения, значения улучшения уже будут лежать в интервале [- 17,88%, 27,78%], со средним значением равным 11,64%, при использовании ALNS, или в интервале [-3,7%, 24,13%], со средним значением 9,52%, при использовании DALNS. Отрицательные значения улучшения показывают, что полное кооперативное решение хуже совокупности индивидуальных решений, причём, в проведённых нами экспериментах, такое ухудшение может достигать 17,88%. Во-вторых, из полученных данных можно вывести меру необходимости использования алгоритма прямой индукции коалиций для последующего расчёта характеристической функции. Такой мерой может служить относительная величина пересечения интервалов решений в ситуации индивидуальной работы (1,2,3) и полной кооперации (123). Минимальное значение этой величины, 0%, означает, что любое кооперативное решение строго лучше совокупности любых индивидуальных решений, в то время как максимальное значение, 100%, означает, что один из интервалов лежит внутри другого. Последнее, в свою очередь может означать, либо что для любых индивидуальных решений существует ненулевая вероятность получить кооперативное решение хуже их совокупности, либо что существует возможность получения таких индивидуальных решений, что любое найденное кооперативное решение будет хуже. В общем случае, чем выше величина пересечения интервалов, тем выше вероятность того, что случайно выбранное кооперативное решение будет хуже, чем совокупность так же случайно выбранных индивидуальных решений. 48 Согласно полученным данных, в зависимости от рассматриваемого примера, величина относительно пересечения интервалов может достигать как 0%, так и 100%. Единственные два случая, в которых эта величина равна 0% – это примеры (6,150, 𝑙𝑜𝑤), при использовании как ALNS, так и DALNS, и (6,300, 𝑙𝑜𝑤), при использовании DALNS (рис.8). В среднем, среди рассмотренных примеров эта величина имеет среднее значение 71,06%, при использовании ALNS, и среднее значение 65,4%, при использовании DALNS, что указывает на существенную вероятность нарушения субаддитивности, и, соответственно, на необходимость использования алгоритма DCI для построения характеристической функции. Наконец, результаты экспериментов иллюстрируют выгоду использования метода динамической адаптации, в дополнение к экспериментам частей 4.3 и 4.4. Интервал улучшения исходных решений ALNS в данном случае составляет [0,014%, 43,95%], при среднем статистическом улучшении равном 15,25%. Для наглядности, все проанализированные характеристики экспериментальных данных также представлены в Таблице 6 ниже. |