Вкр. Факультет прикладной математики процессов управления Кафедра математического моделирования энергетических систем Широких Вячеслав Андреевич
 Скачать 1.83 Mb.
|
|
Санкт-Петербургский государственный университет Факультет прикладной математики – процессов управления Кафедра математического моделирования энергетических систем Широких Вячеслав Андреевич Выпускная квалификационная работа Динамическая адаптация эвристических алгоритмов в задачах маршрутизации транспорта Заведующий кафедрой, доктор физ.-мат. наук, профессор Захаров В. В. Научный руководитель, доктор физ.-мат. наук, профессор Захаров В. В. Рецензент, кандидат физ.-мат. наук Перцовский А. К. Санкт-Петербург 2018 2 Содержание Введение ........................................................................................................................ 3 Глава 1. Математические модели маршрутизации ................................................... 5 1.1. Классическая задача коммивояжёра ......................................................... 5 1.2. Задача маршрутизации транспорта ........................................................... 8 1.3. Задача сбора и доставки ........................................................................... 10 1.4. Задача маршрутизации запасов ............................................................... 13 1.5. Актуальные модификации задач маршрутизации ................................. 16 Глава 2. Алгоритмы решения задач маршрутизации ............................................. 20 2.1. Обзор и классификация актуальных алгоритмов .................................. 20 2.2. Adaptive Large Neighborhood Search........................................................ 23 Глава 3. Динамическая адаптация алгоритмов ....................................................... 26 3.1. Введение в динамическую адаптацию ................................................... 26 3.2. Оценка состоятельности во времени ...................................................... 27 3.3. Динамическая адаптация алгоритмов ..................................................... 28 3.4. Неустойчивая задача. Пример IRP .......................................................... 29 3.5. Устойчивая задача. Пример PDP ............................................................. 32 Глава 4. Кооперативные задачи маршрутизации .................................................... 35 4.1. Введение .................................................................................................... 35 4.2. Построение кооперативной модели IRP ................................................. 36 4.3. Характеристическая функция .................................................................. 39 4.4. Пример построения характеристической функции ............................... 40 4.5. Вычислительные эксперименты .............................................................. 43 4.6. Анализ устойчивости экспериментов ..................................................... 49 Заключение ................................................................................................................. 53 Список литературы .................................................................................................... 54 Приложения ................................................................................................................ 59 3 Введение Данная работа посвящена математическому исследования задач оптимизации вопросов логистики. Под логистикой обычно понимают область деятельности предприятия, связанную с планированием, организацией, управлением и контролем движения материальных и информационных потоков в пространстве и во времени от их первичного источника до конечного потребителя, а также науку, изучающую эти процессы [1]. Одной из основных целей оптимизации логистики является, наравне с максимизацией прибыли, также минимизация расходов, связанных с затратами на логистические операции. Наиболее общими операциями логистики здесь являются планирование закупок, распределения и сбыта, организация складирования и управление запасами, планирование перевозок, планирование производства и управление производственными процессами [1]. Фокусом данной работы являются задачи, связанные с планированием маршрутов, поскольку задачи данного класса не только актуальны в практике, но также и являются математически сложными – они принадлежат классу NP вычислительной сложности задач. Это означает, что доказательство оптимальности решения требует полного перебора решений, и в случае даже простейшей задачи маршрутизации n точек этим числом решений будет n!. С ростом предприятий и рынков сбыта растёт и размерность задач, которые требуется разрешить. Фактически, это означает, что требования к вычислительным ресурсам для решения этой задачи традиционным точным методом растут более чем полиномиально с ростом размерности задачи, и уже сегодня их зачастую не хватает для нахождения оптимального решения этим способом. Таким образом, на практике становятся всё более популярными приближённые (эвристические) методы, а класс задач маршрутизации становится актуальным для теоретического исследования. 4 В реальности, к тому же, с построением маршрута связаны и многие другие факторы, из-за которых даже отдельный оптимальный маршрут может дать плохое решение для в целом, поскольку в современной практике реальные задачи обычно содержат различные дополнительные условия, ограничения и возможности. В связи с этим в теоретических исследованиях возникает необходимость рассмотрения более сложных задач. Можно выделить четыре основных класса математических моделей маршрутизации, исследуемых в настоящее время: задача коммивояжёра (travelling salesman problem), задача маршрутизации транспорта (vehicle routing problem), задача маршрутизации и управления запасом (inventory routing problem) и задача сбора и доставки (Pickup and Delivery Problems). Вкладом данной работы являются разработка и формализация общего вида алгоритма Динамической адаптации эвристических алгоритмов и его апробация на различных классах задач маршрутизации. Дополнительно, в ходе работы предложен, сформулирован и исследован новый класс задач маршрутизации – кооперативные игры маршрутизации, являющийся расширением стандартных задач с добавлением возможности кооперации перевозчиков, что позволяет получать более эффективные решения по сравнению со стандартными случаями. Исследованы проблемы, возникающие при решении таких задач и методы их разрешения. Данная работа включает следующие части. Во второй части представлен обзор литературы по теме актуальных моделей маршрутизации и представлены математические постановки стандартных задач. В третьей части представлена аналогичная работа по теме алгоритмов нахождения решений задач маршрутизации, а также представлена схема с подробным описанием основного алгоритма, использующегося в данной работе – адаптирующегося алгоритма поиска в большой окрестности (Adaptive Large Neighborhood Search, ALNS). 5 Четвёртая часть содержит описание проделанной работы над концепцией Динамической адаптации: основные идеи, метод применения, общая схема динамически адаптированного алгоритма и полученные результаты при применении к различным задачам. В пятой части предлагается концепция кооперативного расширения стандартных задач маршрутизации, рассматриваются проблемы таких постановок и представляются экспериментальные результаты улучшения качества решений и устойчивости коалиций в такой задаче. Глава 1. Математические модели маршрутизации В данной главе проводится наиболее популярных моделей маршрутизации, предоставляются их подробные математические постановки, а также приводится систематический разбор наиболее актуальных модификаций этих моделей в литературе. 1.1. Классическая задача коммивояжёра Задача маршрутизации впервые предлагается как математическая проблема в первой половине 20 века. Первые известные исследования относятся к 1930 годам, и не имеют однозначного автора [2]. Первые математические публикации в данной области, посвящённые исследованию стандартной модели Задачи Коммивояжёра (Travelling Salesman Problem, TSP), появляются в середине 20 века и представлены, например, работами G.Dantzig, D.R.Fulkerson & S.M.Johnson 1954 года [3], или M.M.Flood 1956 года [4]. Одним из важнейших результатов исследования задачи является доказательство принадлежности задачи к классу NP-трудных в работе R.M.Karp 1972 года [5], что обосновывает сложность нахождения оптимального решения 6 на практике. Поскольку все дальнейшие развития модели маршрутизации являются либо обобщениями Задачи коммивояжёра, либо содержат её как подзадачу, этот результат так же позволят утверждать NP-трудность остальных моделей маршрутизации, рассматриваемых в данной работе. В простейшей постановке, Задача Коммивояжёра состоит в нахождение последовательности посещения клиентов с минимальным пройденным путём. Формально, эту задачу можно определить несколькими различными способами. 1. Постановка в форме задачи на графе Рассмотрим граф 𝐺 = (𝑁, 𝐴), где 𝑁 = {1,2, … , 𝑛} – множество вершин графа (множества клиентов), 𝐴 = {(𝑖, 𝑗) | 𝑖, 𝑗 ∈ 𝑁} – множество рёбер графа – путей между клиентами. Для каждого ребра 𝑎 = (𝑖, 𝑗) ∈ 𝐴 считается заданной стоимость посещения 𝑐 𝑎 , что также можно интерпретировать как расстояние или время перемещения между вершинами. Целью задачи ставится нахождение гамильтонова цикла (𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 ), 𝑎 𝑖 ∈ 𝐴 минимальной стоимости, то есть замкнутого пути, проходящего через каждую вершину графа ровно по одному разу и при этом имеющего минимальную суммарную стоимость рёбер среди всех возможных гамильтоновых циклов: min ∑ 𝑐 𝑎 𝑖 𝑛 𝑖=1 (1.1) При этом, в задаче коммивояжёра на граф могут налагаться следующие условия: Ориентированный или неориентированный граф; Полностью связный граф: ∀𝑖, 𝑗 ∈ 𝑁: (𝑖, 𝑗) ∈ 𝐴 (а также (𝑗, 𝑖) ∈ 𝐴, в случае ориентированного графа); Симметричность матрицы стоимостей: ∀(𝑖, 𝑗), (𝑗, 𝑖) ∈ 𝐴: 𝑐 𝑖𝑗 = 𝑐 𝑗𝑖 7 2. Постановка в форме задачи комбинаторной оптимизации Рассмотрим множество клиентов 𝑁 = {1,2, … , 𝑛}. Решением задачи коммивояжёра в комбинаторной форме будет являться перестановка 𝑝 = (𝑝 1 , 𝑝 2 , … , 𝑝 𝑛 ) множества клиентов, то есть биекция 𝑁 на себя: 𝑝: 𝑁 → 𝑁: 1) ∀𝑖, 𝑗 ∈ 𝑁, 𝑖 ≠ 𝑗: 𝑝 𝑖 ≠ 𝑝 𝑗 2) ∀𝑘 ∈ 𝑁 ∃𝑖 ∈ 𝑁: 𝑝 𝑖 = 𝑘. Для каждой пары клиентов (𝑖, 𝑗), 𝑖 ∈ 𝑁, 𝑗 ∈ 𝑁 задана стоимость 𝑐 𝑖𝑗 перемещения из 𝑖 в 𝑗. Целевой функцией в задаче является функция 𝑓(𝑝) = 𝑐 𝑝 1 𝑝 2 + 𝑐 𝑝 2 𝑝 3 + ⋯ + 𝑐 𝑝 𝑛−1 𝑝 𝑛 + 𝑐 𝑝 𝑛 𝑝 1 . Целью является нахождение оптимального решения 𝑝 ∗ , доставляющего минимум функции 𝑓 на множестве 𝑃 𝑛 всех перестановок 𝑁: 𝑝 ∗ : 𝑓(𝑝 ∗ ) = min 𝑝∈𝑃 𝑛 𝑓(𝑝) (1.2) Одним из вариантов постановки в данном случае является евклидова постановка: каждому клиенту 𝑖 ставится в соответствие пара координат на плоскости (𝑥 𝑖 , 𝑦 𝑖 ) , и стоимостью перемещения из 𝑖 в 𝑗 считается евклидово расстояние: 𝑐 𝑖𝑗 = √(𝑥 𝑖 − 𝑥 𝑗 ) 2 + (𝑦 𝑖 − 𝑦 𝑗 ) 2 3. Постановка в форме задачи целочисленного линейного программирования Для формализации задач маршрутизации зачастую используется форма линейного программирования. Рассмотрим множество клиентов 𝑁 = {1,2, … , 𝑛} и матрицу стоимостей 𝐶 = {𝑐 𝑖𝑗 | ∀𝑖, 𝑗 ∈ 𝑁}. Введём бинарные переменные 𝑥 𝑖𝑗 ∈ {0,1}, которые равны 1, если маршрут проходит через ребро (𝑖, 𝑗), и равны 0 иначе. Также введём вспомогательные целочисленные переменные 𝑠 𝑖 ∈ ℤ для каждого клиента 𝑖. 8 Тогда задача в форме целочисленного линейного программирования будет выглядеть следующим образом: min ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑛 𝑗≠𝑖,𝑗=1 𝑛 𝑖=1 ∶ (1.3) ∑ 𝑥 𝑖𝑗 𝑛 𝑗=1 = ∑ 𝑥 𝑗𝑖 𝑛 𝑗=1 = 1, ∀𝑖 ∈ 𝑁 (1.4) 𝑠 𝑖 − 𝑠 𝑗 + 𝑛𝑥 𝑖𝑗 ≤ 𝑛 − 1, 2 ≤ 𝑖 ≠ 𝑗 ≤ 𝑛 (1.5) Ограничения (1.4) гарантируют, что каждый клиент посещён, причём только единожды. Ограничения (1.5) гарантируют, что все клиенты посещены одним маршрутом. Вспомогательные переменные 𝑠 𝑖 могут быть заданы как номера клиентов в последовательности посещения. Достаточность условий (1.5) доказывается тем фактом, что в противном случае, при наличии цикла (𝑖 1 , 𝑖 2 , … , 𝑖 𝑘 ), не проходящего через клиента 1 группа ограничений вместе приведёт противоречию при суммировании: (𝑠 𝑖 1 − 𝑠 𝑖 2 + 𝑛) + (𝑠 𝑖 2 − 𝑠 𝑖 3 + 𝑛) + ⋯ + (𝑠 𝑖 𝑘 − 𝑠 𝑖 1 + 𝑛) = 𝑘𝑛 ≤ 𝑘(𝑛 − 1) 1.2. Задача маршрутизации транспорта Естественным развитием задачи коммивояжёра является Задача маршрутизации транспорта (Vehicle Routing Problem, VRP), которую также иногда называют «задачей k-коммивояжёров». Задача была предложена в конце 50-х годов 20 века, одной из первых работ, рассматривающих эту задачу, является исследование G.Dantzig & J.Ramster 1959 года [6]. В 1964 выходит статья G.Clarke & J.W.Wright [7], описывающая простой и эффективный алгоритм решения задачи, ставший очень популярным в дальнейшем. На сегодняшний день, большинство исследований в области задач маршрутизации посвящено именно задаче маршрутизации транспорта, включая её различные модификации. 9 Задача маршрутизации транспорта является модификацией и расширением задачи коммивояжёра. Основными особенностями задачи являются 1) отдельная определённая точка местоположения депо и 2) возможность обслуживания клиентов несколькими транспортными средствами – несколькими маршрутами. Зачастую, в задаче определяют так же дополнительные ограничения на отдельный маршрут, таких как ограничение на количество посещённых клиентов, на длину маршрута (или, что аналогично, на время посещения), или же ограничение на вместимость транспортного средства. Далее мы рассмотрим задачу маршрутизации транспорта со вместимостью (Capacitated Vehicle Routing Problem). Рассмотрим множество клиентов 𝑁 = {1,2, … , 𝑛} а также точку депо {0}. Обозначим общее множество точек 𝑉 = {0} ∪ 𝑁. Рассмотрим также матрицу стоимостей 𝐶 = {𝑐 𝑖𝑗 }, 𝑖 ∈ 𝑉, 𝑗 ∈ 𝑉. Предположим, что доступны 𝑚 идентичных транспортных средств, которые имеют ограниченную вместимость 𝑄. Также предположим, что каждому клиенту 𝑖 ∈ 𝑁 соответствует величина спроса 𝑑 𝑖 Дополнительно предположим, что ∀𝑖: 0 < 𝑑 𝑖 ≤ 𝐿. Введём переменные 𝑥 𝑖𝑗 ∈ {0,1}, равные 1, если какой-то из маршрутов проходит по пути (𝑖, 𝑗), и равные 0 иначе. Также, введём вещественные переменные 𝑠 𝑖 ∈ ℝ, выражающие суммарное количество доставленного груза в текущем маршруте, включая клиента 𝑖. Таким образом, задача в форме линейного программирования будет выглядеть следующим образом: min ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑛 𝑗≠𝑖,𝑗=0 𝑛 𝑖=0 ∶ (1.6) ∑ 𝑥 𝑖𝑗 𝑛 𝑗=1 = ∑ 𝑥 𝑗𝑖 𝑛 𝑗=1 = 1, ∀𝑖 ∈ 𝑁 (1.7) 10 ∑ 𝑥 0𝑗 𝑛 𝑗=1 = ∑ 𝑥 𝑗0 𝑛 𝑗=1 ≤ 𝑚 (1.8) 𝑠 𝑖 − 𝑠 𝑗 + 𝑄𝑥 𝑖𝑗 ≤ 𝑄 − 𝑑 𝑗 , ∀𝑖, 𝑗 ∈ 𝑁, 𝑖 ≠ 𝑗 (1.9) 𝑑 𝑖 ≤ 𝑠 𝑖 ≤ 𝑄, ∀𝑖 ∈ 𝑁 (1.10) Целевая функция (1.6) отличается от задачи коммивояжёра наличием дополнительной точки – депо 0. Первая группа ограничений (1.7) аналогична ЗК и гарантирует посещение каждого клиента, и только один раз. Вторая группа неравенств (1.8) ограничивает количество покидающих и возвращающихся в депо транспортных средств. Третья группа ограничений (1.9) задаёт динамику доставки грузов: для участка (𝑖, 𝑗) в маршруте 𝑥 𝑖𝑗 = 1 и тогда 𝑠 𝑗 ≥ 𝑠 𝑖 + 𝑑 𝑗 , в противном случае условие 𝑠 𝑖 − 𝑠 𝑗 ≤ 𝑄 − 𝑑 𝑗 всегда выполняется благодаря последней группе ограничений: 𝑠 𝑖 ≤ 𝑄 и 𝑠 𝑗 ≥ 𝑑 𝑗 . Последняя группа ограничений (1.10) также гарантирует, что суммарный спрос, обслуживаемый транспортным средством не превышает его запаса: 𝑠 𝑖 ≤ 𝑄. Дополнительно, ограничения (1.9) неявным образом исключают возможность образования замкнутых циклов в маршрутах, без соединения с депо, аналогично неравенствам (1.5) задачи коммивояжёра. 1.3. Задача сбора и доставки Принципиально новый класс Задач Сбора и Доставки (Pickup and Delivery Problem, PDP, также известная как Dial-a-Ride problem) возникает в 70-х годах 20 века, в таких работах, как N.H.M.Wilson 1971 года [8], или D.M.Stein 1978 года [9]. Отличительной чертой задач сбора и доставки, по сравнению с задачами маршрутизации транспорта, является то, что груз для доставки комплектуется не в депо отправления, а собирается в различных точках карты – задача 11 рассматривает уже не доставку груза отдельным клиентам, а обслуживание заказов в форме {объём, точка сбора, точка доставки}. Формально, предположим, что вместо множества всех точек-клиентов 𝑁 изначально задано множество заказов 𝑅 = {(𝑝 𝑖 , 𝑑 𝑖 )} 𝑖=1 𝑟 . Далее, положим множество всех местоположений клиентов 𝑁 = {𝑝 𝑖 } 𝑖=1 𝑟 ∪ {𝑑 𝑖 } 𝑖=1 𝑟 , а также 𝑛 = 2𝑟 = |𝑁|. Дополнительно, считаем что задана общая точка отправления – депо {0}. Аналогично задаче маршрутизации транспорта, считаем доступными 𝑚 транспортных средств из множества 𝑀 = {1,2, … , 𝑚}. Специальные условия сбора и доставки, отличающие PDP от других задач маршрутизации, можно формализовать в следующих условиях: Обе точки из заказа (𝑝, 𝑑) должны быть обслужены одним транспортным средством; Точка сбора 𝑝 из заказа (𝑝, 𝑑) должна быть посещена строго до посещения точки доставки 𝑑. Каждое транспортное средство обладает вместимостью запаса 𝑄 единиц, которая не может быть превышена по ходу реализации маршрута. Будем считать, что транспортные средства начинают движение из депо с нулевым запасом. Введём бинарные переменные 𝑥 𝑖𝑗 𝑘 ∈ {0,1}, равные 1, если маршрут транспортного средства 𝑘 проходит по пути (𝑖, 𝑗), и равные 0 в противном случае. Также, введём бинарные переменные 𝑦 𝑖 𝑘 ∈ {0,1}, равные 1, если маршрут 𝑘 проходит через точку 𝑖. Будем рассматривать вспомогательные переменные 𝑠 𝑖 ∈ ℝ, отражающие текущий объём запаса в текущем транспортном средстве после посещения точки 𝑖. Рассмотрим вспомогательные переменные 𝑣 𝑖 ∈ ℝ, отражающие суммарную стоимость текущего маршрута после посещения точки 12 𝑖. Дополнительно, введём константу 𝑈, ограничивающую сверху максимально возможную стоимость маршрута. Такой константой, например, может являться 𝑈 = ∑ ∑ 𝑐 𝑖𝑗 𝑛 𝑗=0 𝑛 𝑖=0 В заданных переменных, задача сбора и доставки в форме целочисленного линейного программирования будет иметь вид: min ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑘 𝑚 𝑘=1 𝑛 𝑗≠𝑖,𝑗=0 𝑛 𝑖=0 ∶ (1.11) ∑ 𝑦 𝑖 𝑘 𝑚 𝑘=1 = 1, ∀𝑖 ∈ 𝑁 (1.12) ∑ 𝑥 𝑖𝑗 𝑘 𝑛 𝑗=1 = ∑ 𝑥 𝑗𝑖 𝑘 𝑛 𝑗=1 = 𝑦 𝑖 𝑘 , ∀𝑖 ∈ 𝑁, 𝑘 ∈ 𝑀 (1.13) ∑ 𝑥 0𝑗 𝑘 𝑛 𝑗=1 = ∑ 𝑥 𝑗0 𝑘 𝑛 𝑗=1 ≤ 1, ∀𝑘 ∈ 𝑀 (1.14) 𝑠 𝑖 − 𝑠 𝑗 + 𝑄𝑥 𝑖𝑗 𝑘 ≤ 𝑄 − 𝑑 𝑗 , ∀𝑖, 𝑗 ∈ 𝑁, 𝑖 ≠ 𝑗, 𝑘 ∈ 𝑀 (1.15) 0 ≤ 𝑠 𝑖 ≤ 𝑄, ∀𝑖 ∈ 𝑁 (1.16) 𝑣 𝑖 − 𝑣 𝑗 + 𝑈𝑥 𝑖𝑗 𝑘 ≤ 𝑈 − 𝑐 𝑖𝑗 , ∀𝑖, 𝑗 ∈ 𝑁, 𝑖 ≠ 𝑗, 𝑘 ∈ 𝑀 (1.17) 𝑣 𝑝 ≤ 𝑣 𝑑 , ∀(𝑝, 𝑑) ∈ 𝑅 (1.18) 𝑦 𝑝 𝑘 = 𝑦 𝑑 𝑘 , ∀(𝑝, 𝑑) ∈ 𝑅, 𝑘 ∈ 𝑀 (1.19) 0 ≤ 𝑣 𝑖 ≤ 𝑈, ∀𝑖 ∈ 𝑁 (1.20) Аналогично, (1.11) задаёт целевую функцию задачи, отражающую суммарную стоимость всех маршрутов. Ограничения (1.12) устанавливают возможность посещения каждой локации только одним транспортным средством. Соблюдение левых частей ограничений (1.13) и (1.14) гарантирует связность маршрутов. Правая часть ограничений (1.13) устанавливает связь между входящими и исходящими путями в каждой локации и фактом посещения этой локации конкретным транспортным средством. Правая часть (1.14) задаёт 13 ограничения на количество маршрутов: 0, если транспортное средство 𝑘 не используется. Ограничения (1.15) задают динамику запаса при перевозках, а неравенства (1.16) – ограничения запаса транспортного средства, снизу и сверху. Отметим, что в отличие от VRP, неравенства (1.15) не могут быть использованы для исключения в маршрутах циклов, не проходящих через депо, поскольку в задаче PDP перевозимый запас изменяется немонотонно. Для того, чтобы исключить замкнутые циклы, вводятся дополнительные переменные 𝑣 𝑖 , выражающие монотонно изменяющийся показатель – накопленную маршрутом стоимость. Ограничения (1.17) задают динамику накопления стоимости маршрутами, а неравенства (1.20) – ограничения накопленной стоимости. Ограничения (1.18)-(1.19) гарантируют соблюдение условий сбора и доставки: (1.18) гарантируют правильный порядок посещения, а ограничения (1.19) – посещение локаций сбора и доставки одним транспортным средством. 1.4. Задача маршрутизации запасов Альтернативным развитием задачи маршрутизации транспорта является Задачи Маршрутизации Запасов (Inventory Routing Problem, IRP). В различных вариациях задачи маршрутизации транспорта присутствует запас в том или ином виде, например, учёт спроса или ограничение вместимости транспортного средства, но качественным отличием новой задачи является учёт динамики запаса и стоимости хранения в течение длительного времени. Задача маршрутизации запасов появляется в научной литературе в 80-х годах 20 века в практических исследованиях A.Assad, B.Golden, R.Dahl & M.Dror 1982 года [10], посвящённом разработке системы планирования дистрибьюции пропана, и W.J.Bell, L.M.Dalberto & M.L.Fisher 1983 года [11] посвящённом дистрибьюции промышленных газов. Задача является комбинацией задачи маршрутизации транспорта и задачи управления запасами, таким образом решением задачи являются как маршруты 14 посещения клиентов, так и объёмы доставки. Сложность задачи состоит в том, что оба аспекта решения влияют друг на друга: большой объём доставки увеличивает стоимость хранения запасов клиентами, но в тоже время сокращает транспортные издержки благодаря редким посещениям; с другой стороны, сложный маршрут и частые посещения повышают транспортные издержки, но позволяют клиентам снизить объём хранения сверх спроса до минимума, существенно сокращая связанные с этим затраты. Именно поэтому данную задачу невозможно оптимально разбить только на составляющие её части маршрутизации и управления запасами, и только рассматривая совместную Задачу маршрутизации запасов возможно получение наиболее эффективных на практике решений. В качестве базовой модели IRP будем рассматривать задачу построения маршрутов и планов доставки на 𝑇 периодов времени из одного депо 𝑛 потребителям с постоянным спросом, с использованием 𝑚 транспортных средств. Целью оптимизации является минимизация суммарных затрат на перевозку и хранение. Аналогично задаче VRP, будем рассматривать множество клиентов 𝑁 = {1,2, … , 𝑛} и также точку депо {0}. Обозначим общее множество точек 𝑉 = {0} ∪ 𝑁. Так же, рассмотрим матрицу стоимостей 𝐶 = {𝑐 𝑖𝑗 }, 𝑖 ∈ 𝑉, 𝑗 ∈ 𝑉. Рассмотрим горизонт планирования, состоящий из нескольких периодов времени 𝑡 = 1,2, … , 𝑇. Предполагаем, что каждый клиент 𝑖 имеет возможность хранить товар, затрачивая при этом ℎ 𝑖 стоимости за каждую единицу товара (что может выражать единицу товара, единицу объёма и т.п.). Максимальная вместимость склада клиента 𝑖 считается равной 𝑈 𝑖 . Спрос на товары для каждого клиента, аналогично ЗМТ, предполагается известным и постоянным, равным 𝑑 𝑖 15 Дополнительно, вводим новые переменные, связанные с управлением запасами: 𝑞 𝑖𝑡 ≥ 0, выражающие величину доставки клиенту 𝑖 в начале периода 𝑡, а также 𝐼 𝑖𝑡 ≥ 0, выражающие размер запаса клиента 𝑖 на начало периода 𝑡 после доставки. Предполагаем также, что величины начального запаса 𝐼 𝑖0 каждого клиента заданы и известны изначально. Для формулировки задачи маршрутизации запасов необходимо также расширить переменные маршрутов: 𝑥 𝑖𝑗𝑡 ∈ {0,1}, равные 1, если какой-то из маршрутов проходит по пути (𝑖, 𝑗) в период 𝑡, и равные 0 иначе; 𝑠 𝑖𝑡 ∈ ℝ, выражающие суммарное количество доставленного груза в начале периода 𝑡 в текущем маршруте, включая клиента 𝑖. Таким образом, задача маршрутизации запасов в форме линейного программирования будет выглядеть следующим образом: min (∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗𝑡 𝑛 𝑗≠𝑖,𝑗=0 𝑛 𝑖=0 𝑇 𝑡=1 + ∑ ∑ ℎ 𝑖 𝐼 𝑖𝑡 𝑛 𝑖=1 𝑇 𝑡=1 ) ∶ (1.21) ∑ 𝑥 𝑖𝑗𝑡 𝑛 𝑗=1 = ∑ 𝑥 𝑗𝑖𝑡 𝑛 𝑗=1 ≤ 1, ∀𝑖 ∈ 𝑁, ∀𝑡 = 1, … , 𝑇 (1.22) ∑ 𝑥 0𝑗𝑡 𝑛 𝑗=1 = ∑ 𝑥 𝑗0𝑡 𝑛 𝑗=1 ≤ 𝑚, ∀𝑡 = 1, … , 𝑇 (1.23) 𝐼 𝑖𝑡 = 𝐼 𝑖,𝑡−1 − 𝑑 𝑖 + 𝑞 𝑖,𝑡 , ∀𝑖 ∈ 𝑁, ∀𝑡 = 1, … , 𝑇 (1.24) 0 ≤ 𝐼 𝑖𝑡 ≤ 𝑈 𝑖 , ∀𝑖 ∈ 𝑁, ∀𝑡 = 1, … , 𝑇 (1.25) 𝑠 𝑖𝑡 − 𝑠 𝑗𝑡 + 𝑄𝑥 𝑖𝑗𝑡 ≤ 𝑄 − 𝑞 𝑗𝑡 , ∀𝑖, 𝑗 ∈ 𝑁, 𝑖 ≠ 𝑗, ∀𝑡 = 1, … , 𝑇 (1.26) 𝑞 𝑖𝑡 ≤ 𝑠 𝑖𝑡 ≤ 𝑄, ∀𝑖 ∈ 𝑁, ∀𝑡 = 1, … , 𝑇 (1.27) В целевой функции (1.21) по сравнению с VRP появляется новое слагаемое – затраты на хранение. Первая группа ограничений (1.22) гарантирует связность маршрута, причём посещение клиента в каждый период не гарантируется, если 16 клиент способен удовлетворить спрос при помощи имеющегося запаса. Вторая группа неравенств (1.23) ограничивает количество покидающих и возвращающихся транспортных средств в депо в каждом периоде. Третья группа ограничений (1.24) задаёт динамику запаса: начальный запас после доставки в каждом периоде составляют начальный запас в начале предыдущего периода, за исключением израсходованного спроса, с добавкой величины запаса, доставленного в начале текущего периода. Следующая группа неравенств (1.25) гарантирует отсутствие дефицита и ограничение вместимости склада каждого клиента. Последние ограничения (1.26) аналогичны постановке ЗМТ, за исключением того, что объемы доставки – 𝑞 𝑖𝑡 – переменные величины, а также дополнительного расширения количества ограничений на каждый период времени. Аналогично ЗМТ, можно показать, что ограничения (1.26)-(1.27) не позволяют нарушение вместимости транспортных средств. Для маршрута (𝑖 1 , 𝑖 2 , … , 𝑖 𝑘 ): 𝑥 𝑖 1 𝑖 2 𝑡 = 1 и неравенства (1.26) принимают вид 𝑞 𝑖 2 𝑡 ≤ 𝑠 𝑖 2 𝑡 − 𝑠 𝑖 1 𝑡 Суммируя данные неравенства для 𝑞 𝑖 2 𝑡 , 𝑞 𝑖 3 𝑡 , … , 𝑞 𝑖 𝑘 𝑡 , и используя (1.27) получаем: ∑ 𝑞 𝑖 𝑝 𝑡 𝑘 𝑝=2 ≤ 𝑠 𝑖 𝑘 𝑡 − 𝑠 𝑖 𝑘−1 𝑡 + ⋯ + 𝑠 𝑖 2 𝑡 − 𝑠 𝑖 1 𝑡 = 𝑠 𝑖 𝑘 𝑡 − 𝑠 𝑖 1 𝑡 ≤ 𝑄 − 𝑞 𝑖 1 𝑡 или же: ∑ 𝑞 𝑖 𝑝 𝑡 𝑘 𝑝=1 ≤ 𝑄 1.5. Актуальные модификации задач маршрутизации Различные модификации, добавляющие реалистичные характеристики в теоретические задачи маршрутизации, являются одним из самых актуальных направлений исследования в научной литературе. 17 Наиболее популярными такими характеристиками являются временные окна посещения клиентов, учёт пробок, недетерминированные модели спроса, дополнительные цели оптимизации, такие как минимизация числа маршрутов или поддержание экологии. Все упомянутые ограничения являются универсальными и могут быть применены в любой модели маршрутизации. Временные окна посещения клиентов [12, 13, 14, 15] накладывают ограничения на время посещения локации в форме (𝑎 𝑖 , 𝑏 𝑖 ). Введение данных ограничений необходимо для учёта часов работы, поддержания максимального времени доставки и согласования с расписаниями клиентов в общем случае. Для введения временных окон в модель необходимо введение дополнительных переменных, аналогично ограничениям (2.17), и самих ограничивающих неравенств: 𝑡 𝑖 − 𝑡 𝑗 + 𝑇 𝑚𝑎𝑥 𝑥 𝑖𝑗 ≤ 𝑇 𝑚𝑎𝑥 − 𝜏 𝑖𝑗 , ∀𝑖, 𝑗 ∈ 𝑁, 𝑖 ≠ 𝑗 (1.28) 𝑎 𝑖 ≤ 𝑡 𝑖 ≤ 𝑏 𝑖 , ∀𝑖 ∈ 𝑁 (1.29) где 𝜏 𝑖𝑗 – время в пути между 𝑖 и 𝑗, 𝑇 𝑚𝑎𝑥 – конечное время планирования. Одной из новых и актуальных модификаций является введение зависимости различных стандартных констант от реального времени посещения [16, 17, 18, 19]. Основным практическим применением данной идеи является учёт пробок на дорогах во время перевозок. В математической модели это означает, что константы 𝑐 𝑖𝑗 становятся функциями, в общем случае непрерывного времени: 𝑐 𝑖𝑗 (𝑡). Важной особенностью является то, что использование подобных функций не позволяет рассматривать постановки задач как задачи целочисленного линейного программирования, а также отдельных базовых предположений, используемых в эвристических алгоритмах, таких как правило треугольника для матрицы времени или линейность сдвига во времени. 18 В зависимости от используемой модели спроса, задачи можно разделить на три группы. Первая группа – это задачи с детерминированным спросом, то есть такие, в которых объём спроса на продукцию каждого клиента известен заранее и не изменятся в периоде планирования. К таким задачам, в том числе, относятся рассмотренные базовые модели CVRP, PDP и IRP. Второй группой задач являются задачи, в которых спрос является стохастическим [20, 21, 22]. В таких моделях обычно подразумевается, что для величин спроса нет известного заранее точного значения, но известно вероятностное распределение спроса клиентов или отдельные его параметры. В третью группу задач входят модели с динамическим спросом [23, 24, 25, 26] – в такой постановке считается, что как величина спроса, так и сам факт заказа доставки не известен заранее, либо они известны только на небольшое время вперёд. Одной из часто встречающихся модификаций в различных задачах является введение дополнительной приоритетной цели оптимизации – минимизации числа маршрутов, то есть минимизация числа необходимых транспортных средств [27, 28]. Стандартная целевая функция минимизации транспортных затрат в таком случае считается второстепенной и менее приоритетной. Основания данного подхода лежат в том факте, что на практике логистические затраты на доставку включают в себя не только переменные затраты, зависящие от расстояния или времени, но и постоянные затраты на каждое транспортное средство, такие как стоимость обслуживания, зарплата водителям и т.д. Важно отметить, что при подобном подходе минимизация переменной стоимости остаётся актуальной, т.к. при эффективном сокращении длины маршрутов удаётся компактнее распределять заказы на меньшее число транспортных средств. Наконец, весьма актуальными в последние годы являются задачи с дополнительной минимизацией влияния транспорта на окружающую среду [29, 19 30, 31]. Основными методами такой оптимизации являются дополнительный учёт суммарного времени как передвижения, так и простоя, а также добавления специфических ограничений, отражающих экологические нормы. Для дополнительной наглядности, все работы, связанные с представленными модификациями, представлены ниже в Таблице 1 для каждого класса задач маршрутизации. Таблица 1. Литература по модификациям Задач Маршрутизации Модель → TSP VRP PDP IRP Модификация ↓ Несколько маршрутов VRP + ∗ ∗ Учёт объёмов доставки − CVRP + + Несколько периодов − Periodic VRP − + Заказы сбора и доставки − PDP + − Временные окна TSPTW[12] VRPTW[13] PDPTW[14] IRPTW[15] Зависимость от времени TDTSP[16] TDVRP[17] TDPDP[18] TDIRP[19] Стохастический спрос − SVRP[20] SPDP[21] SIRP[22] Динамический спрос DTSP[23] DVRP[24] DPDP[25] DIRP[26] Минимизация маршрутов − [27] [28] − Оптимизация экологии − GVRP[29] GPDP[30] GIRP[31] « −» – задача никогда не формулируется с данной модификацией; « +» – задача всегда формулируется с данной модификацией; « ∗» – задача зачастую формулируется с несколькими транспортными средствами, но такая формулировка не обязательна; Курсив – задача крайне редко или неполноценно освещена в литературе. 20 |