Содержание к диссертации
Введение
1 Гибридный локальный поиск для задачи маршрутизации транспортных средств с разделенными поставками 23
1.1 Постановка задачи и обозначения 26
1.2 Свойства оптимальных решений 28
1.3 Процедуры декодирования
1.3.1 Метод динамического программирования для разбиения последовательности 35
1.3.2 Жадный алгоритм разбиения последовательности
1.4 Окрестности 37
1.5 Гибридный VND–STS метод
1.5.1 Общая схема алгоритма VND–STS 42
1.5.2 Метод чередующихся окрестностей 43
1.5.3 Стохастический поиск с запретами 43
1.5.4 Переключение процедур декодирования 45
1.6 Численные эксперименты 47
2 Гибридный алгоритм локального поиска для задачи марш рутизации разнородного ограниченного автопарка
2.1 Постановка задачи и предшествующие результаты 58
2.2 Метод Лагранжевых релаксаций для разбиения последовательности 62
2.3 Локальный поиск
2.3.1 Генерация стартового решения 69
2.3.2 Рандомизированный спуск по чередующимся окрестностям 70
2.3.3 Интенсификация поиска 71
2.3.4 Диверсификация поиска 71
2.3.5 Постоптимизация 72
2.4 Численные эксперименты 74
3 Трехфазный алгоритм оптимизации автопарка и маршрутов транспортных средств 80
3.1 Постановка задачи 81
3.2 Математическая модель 82
3.3 Характеристики решений и окрестности 88
3.4 Алгоритм решения задачи
3.4.1 Построение допустимого решения 95
3.4.2 Минимизация числа маршрутов 97
3.4.3 Минимизация транспортных издержек 99
3.5 Численные эксперименты 102
Заключение 109
Литература
- Метод динамического программирования для разбиения последовательности
- Переключение процедур декодирования
- Рандомизированный спуск по чередующимся окрестностям
- Построение допустимого решения
Введение к работе
Актуальность темы.
Транспортная логистика становится все более важной составляющей многих сфер деятельности. В коммерции доля расходов на транспортировку продукта может составлять 25-35% от его стоимости. В 2010-2014 гг. объем рынка коммерческих автомобильных грузоперевозок вырос более чем в два раза. Такая ситуация накладывает высокие требования как на представителей услуг грузоперевозок, так и на производителей товаров. Оптимизация перевозок становится серьезным конкурентным преимуществом.
Поиск оптимальных маршрутов транспортных средств является ключевой задачей в сфере логистики. Класс таких задач называют задачами маршрутизации транспортных средств (The vehicle routing problems). Эти задачи одни из наиболее сложных в области комбинаторной оптимизации. Математическая постановка базовой задачи впервые была предложена более 50 лет назад и связана с составлением оптимального набора маршрутов для автопарка транспортных средств (ТС) с целью обслужить заданное множество клиентов (G. B. Dantzig, J. H. Ramser). Интерес к таким задачам обусловлен не только их большим прикладным значением, но и сложностью решения. Опубликован ряд обзоров и монографий по данной теме. Из наиболее значимых следует отметить труды P. D. Christofides, G. Laporte, D. Vigo, B. Golden, Е. М. Бронштейн, Э. Х. Гимади, В. Г. Дейнеко.
В данной работе рассматриваются три разновидности задач маршрутизации. Постановки этих задач ближе к реальным требованиям, возникающим при развозке клиентам товаров со склада. Такие постановки включают в себя различные дополнительные ресурсные ограничения. Эти задачи являются NP-трудными и требуют разработки сложных алгоритмов для нахождения качественных решений. На практике данные задачи имеют большую размерность. В такой ситуации одним из перспективных подходов является разработка методов локального поиска.
Цель данной работы состоит в разработке и исследовании алгоритмов локального поиска для решения задач маршрутизации с различными ограничениями: разделенными поставками, разнородным автопарком, рабочими сменами, временными окнами для доставки грузов кли-3
ентам и перерывами в работе водителей.
Методика исследований. В диссертации использованы современные методы исследования операций, включающие в себя построение математических моделей, теорию локального поиска и вычислительной сложности, а также методологию экспериментальных исследований с применением компьютерных технологий и коммерческих пакетов прикладных программ для решения задач целочисленного линейного программирования.
Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.
-
Для задачи маршрутизации транспортных средств с распределенными поставками рассмотрена кодировка решений в виде перестановки клиентов. Показано, что существует оптимальное решение, которое соответствует некоторой перестановке. Установлено, что задача поиска наилучшего решения по заданной перестановке является NP-трудной.
-
Для задачи маршрутизации с разнородным автопарком разработан метод Лагранжевых релаксаций декодирования решения по последовательности клиентов. Представлена новая окрестность экспоненциальной мощности для локального поиска.
-
Для задачи маршрутизации транспортных средств с временными окнами и перерывами разработана математическая модель в терминах целочисленного линейного программирования. Получено выражение для оптимального времени начала перерыва при фиксированном обходе клиентов. Для расстановки перерывов в маршруте предложен метод динамического программирования.
-
Разработаны алгоритмы и комплексы программ, которые позволяют решать задачи с числом клиентов до 1000.
Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Получены новые свойства различных задач маршрутизации, модифицированы известные и построены новые математические модели, разработаны численные методы решения. Разработанные методы реализованы в виде комплекса программ. Они показали свою эффективность и могут применяться при решении практических задач большой размерности. Получено свидетельство о регистрации программы №PR15001 Фонда алгоритмов и программ СО РАН. Резуль-4
таты диссертации могут быть использованы при преподавании университетских курсов «Исследование операций» и «Теория принятия решений». Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:
Азиатская международная школа-семинар «Проблемы оптимизации сложны систем», Иссык-Куль, Киргизия, август 2009 г;
Российская конференция «Дискретный анализ и исследование операций», Алтай, Россия, июнь 2010 г;
Российская конференция «Дискретный анализ и исследование операций», Новосибирск, Россия, июнь 2013 г;
— Международная конференция по маршрутизации и логистики
VeRoLog, Саутгемптон, Великобритания, июль 2013 г;
Всероссийская конференция «Методы оптимизаций и их приложения», о. Ольхон, Байкал, Россия, июнь 2014 г;
Азиатская международная школа-семинар «Проблемы оптимизации сложны систем», Иссык-Куль, Киргизия, август 2014 г;
Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, Россия, июль 2015 г;
Международная конференция по исследованию операций OR2015, Вена, Австрия, сентябрь 2015 г;
Результаты неоднократно докладывались на научных семинарах Института математики им. С.Л. Соболева СО РАН и Института вычислительной математики и математической геофизики СО РАН.
Личный вклад. Результаты, представленные в диссертации, получены соискателем лично. Автор самостоятельно сформулировал цели и задачи в рамках предложенной темы, получил новые теоретические результаты. На основании проведенных исследований автор разработал программное обеспечение и провел численные эксперименты, подтверждающие эффективность предложенных методов.
Публикации. По теме диссертации автором опубликовано 12 работ, в том числе 5 статей в журналах из списка ВАК.
Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (64 наименования). Объем диссертации — 119 страниц.
Метод динамического программирования для разбиения последовательности
В разделе 2.4 приводятся результаты численных экспериментов. Эксперименты проводились на известных тестовых примерах из [29], основанных на реальных данных. Всего 96 тестовых примеров размерностью до 256 клиентов. Результаты первого эксперимента показывают эффективность метода Лагранжевых релаксаций для задачи о разбиении последовательности. Во втором эксперименте проверялась эффективность гибридного алгоритма. Разработанный алгоритм был реализован на языке Java и сравнивался с двумя наиболее эффективными из существующих эвристик. Для пятнадцати тестовых примеров удалось улучшить рекордные значения целевой функции. Средняя погрешность относительно наилучших известных решений составила 0,65%.
В третьей главе рассматривается прикладная задача минимизации затрат на доставку грузов заданному множеству клиентов. Эта задача исследовалась по заказу фирмы, разрабатывающей корпоративное программное обеспечение для развозки продуктов в г. Новосибирске. Предполагается, что каждый водитель работает в свою рабочую смену и периодически прерывается на отдых. Кроме того, каждый клиент имеет временное окно для его обслуживания. Наиболее значимые работы по
Введение задачам с временными ограничениями принадлежат J. F. Cordeau, M. Gendreau, J. Y. Nagata, T. Vidal. Задачи с перерывами исследовались в работах A. Goel, T. Vidal, J.-P. Gagliardi.
В данной задаче каждый клиент имеет временное окно, длительность обслуживания и объем доставляемого груза. Транспортные средства (ТС) имеют различную грузоподъемность. За каждым ТС закреплен водитель, который работает в определенную рабочую смену. В ходе работы водитель обязан делать перерывы на отдых. Для перерывов заданы длительность и временные окна. Требуется построить маршруты для ТС и доставить грузы всем клиентам так, чтобы суммарные затраты на привлеченный автопарк и перевозку были бы минимальными.
В разделе 3.1 описывается формальная постановка задачи. Как и в разделах 1.1 и 2.1, рассматривается граф G = (V, А). Для каждой дуги (i,j) Є А известно не только расстояние между ними dij но и время проезда tij. Для каждого клиента і Є V определена длительность обслуживания ТІ и требование на доставку qi единиц груза. Обслуживание клиента і должно начинаться внутри временного окна [е , Z«].
Автопарк состоит из различных ТС, их множество обозначим через К. Для каждого к Є К задана грузоподъемность Q} , удельные затраты Ck на перевозку грузов, единовременные фиксированные затраты fk, связанные с использованием ТС и рабочая смена и(к). Пусть U = {1,... , т} — множество рабочих смен. Каждая смена и имеет временное окно [Еи, Lu], в котором водитель должен начинать и заканчивать свой маршрут. Кроме того, в течении смены и водитель должен сделать tu перерывов Ри = {Pj,..., Рии} в работе. Каждый перерыв имеет свою
Введение длительность и временное окно. Перерывы не могут идти подряд, между ними должен обслуживаться хотя бы один клиент. Если в маршруте мало клиентов, то число перерывов должно быть сокращено. Задача состоит в минимизации суммарной стоимости маршрутов всех ТС при удовлетворении всех ограничений по времени и грузоподъемности.
В разделе 3.2 построена новая математическая модель в терминах целочисленного линейного программирования с произвольным числом перерывов. Для каждого клиента і Є V введем ueU tu фиктивных клиентов. Обслуживание такого клиента будет требовать перерыва в работе водителя. Перерыв может следовать сразу после обслуживания клиента, либо через некоторое время, но до посещения следующего клиента в маршруте.
Пусть Р — список всех перерывов, Р = (Pi,... , Pi1,..., i ,... , Рт1). Через i(Pl) обозначим позицию перерыва (Р1) в списке Р. Определим новый набор индексов W = V U Vi U U V\p\ U {0 }, где Vi = {in + і,..., (і + \)п + і} — множество вершин, связанных с перерывом і є P. Последняя вершина 0 с номером \W\ обозначает склад как конечный пункт любого маршрута. Через У (и) = {V i),..., Уир Л обозначим подмножество вершин с перерывами для заданной рабочей смены и.
Переключение процедур декодирования
В этой главе исследуется задача поиска оптимальных маршрутов разнородных транспортных средств ограниченной грузоподъемности. Предполагается, что каждый тип транспортного средства имеет фиксированную стоимость запуска на маршрут и удельную стоимость проезда (стоимость бензина на километр). Число транспортных средств каждого типа ограничено. Все транспортные средства находятся в депо (складе) и должны вернуться туда после обслуживания клиентов. Каждый клиент имеет определенный запрос на доставку грузов и обслуживается ровно одним транспортным средством. Склад и клиенты представлены точками на плоскости. Требуется найти маршруты транспортных средств для доставки грузов всем клиентам с минимальными суммарными затратами. Наряду с данной задачей (Heterogeneous Fixed Fleet Vehicle Routing
Гибридный алгоритм локального поиска для задачи HFFVRP Problem, HFFVRP) часто рассматривают вариант с неограниченным автопарком, смешанный вариант и вариант с идентичными транспортными средствами. Все они являются NP-трудными и активно исследуются как теоретически, так и эмпирически для получения эффективных алгоритмов. Обзор последних результатов можно найти, например, в [11].
При разработке алгоритмов решения задач маршрутизации часто возникает следующая подзадача. Задана последовательность клиентов. Требуется разбить её на маршруты и назначить им транспортные средства так, чтобы суммарная стоимость обслуживания клиентов была минимальной. Умение решать эту подзадачу дает возможность кодировать решения в виде одной последовательности клиентов и использовать хорошо зарекомендовавшие себя методы решения таких задач. При неограниченном автопарке такая подзадача решается за полиномиальное время [54]. При ограниченном автопарке она NP-трудна [56], но может быть решена точно методом динамического программирования. В настоящей работе используется приближённый метод Лагранжевых релаксаций, который дает верхнюю и нижнюю оценки оптимума. Этот метод применяется в схеме локального поиска с чередующимися окрестностями. Наряду с известными окрестностями вводится новая окрестность экспоненциальной мощности, позволяющая осуществлять глубокую перестройку решений с улучшением целевой функции. Новые процедуры интенсификации и диверсификации локального поиска применяются для повышения эффективности метода. Результаты экспериментальных исследований свидетельствуют о высокой конкурентоспособности нового гибридного метода. Для 15 тестовых примеров из широко используемых электронных
Данная глава построена следующим образом. В разделе 2.1 представлена точная постановка задачи и приводится краткий обзор предшествующих исследований. В разделе 2.2 рассматривается задача разбиения последовательности клиентов на маршруты транспортных средств и метод Лагранжевых релаксаций для ее решения. Раздел 2.3 посвящен локальному поиску, описанию окрестностей и процедурам интенсификации и диверсификации. В разделе 2.4 приводятся результаты численных экспериментов.
Рассмотрим полный неориентированный взвешенный граф G = (V, А) с множеством вершин V = {0,1,... ,п} и множеством ребер А = {(i,j) i,j Є V}. Вершина 0 соответствует складу, где расположены транспортные средства. Остальные вершины представляют клиентов, V = V\{0}. Все вершины представлены точками на плоскости. Для каждой пары вершин (i,j) известно расстояние dij между ними. Для каждого і Є V задано требование на доставку qi единиц груза. Автопарк состоит из разнородных транспортных средств (ТС). Множество типов ТС обозначим через К. Для каждого типа к Є К известно число rrik доступных транспортных средств и их предельная вместимость Qk. Использование ТС влечет единовременные фиксированные затраты /&. Проезд из і в j стоит с\, = dijCk, где Ck — удельные затраты на единицу расстояния для ТС типа к.
Гибридный алгоритм локального поиска для задачи HFFVRP Пусть г — некоторый маршрут в графе G. Будем говорить, что маршрут допустим для ТС типа к, если он образует цикл, проходящий через вершину 0, и сумма запросов клиентов не превышает вместимости транспортного средства. Стоимость маршрута г складывается из фиксированной стоимости fk для привлечения ТС и суммарной стоимости ребер. Задача состоит в нахождении такого набора допустимых маршрутов и назначения им ТС, чтобы каждый клиент посещался ровно один раз, число привлекаемых ТС не превышало численности автопарка, а суммарная стоимость маршрутов была минимальной.
Приведем точную математическую постановку задачи. Введем следующие переменные: Х\А = 1, если ТС типа к от клиента і едет к клиенту j, и Х\А = 0 в противном случае. Vij 0 количество груза в ТС при переезде от клиента і к клиенту j. С использованием введенных переменных задача HFFVRP может быть сформулирована в терминах частично-целочисленного линейного программирования:
Рандомизированный спуск по чередующимся окрестностям
В этой же работе содержатся рекордные решения для этих примеров. Эти решения легко представить в виде последовательности клиентов, так же как это делается в процедуре интенсификации. Для метода субградиентной оптимизации использовались следующие параметры: а = 0, 74; 0 = 1,8; UB = 1, 3ЬЯ(Хг). Величина делилась на 1,1 через каждые четыре итерации. Каждый пример решался 10 раз. Метод останавливался в случае нахождения первого допустимого решения, либо по достижению максимального числа итераций. Вычислялись среднее число итераций до получения первого допустимого решения Iteravg, средняя погрешность относительно нижней оценки LbEavg в процентах, среднее время работы tavg и суммарное время работы алгоритма Т в миллисекундах. Максимальное число итераций не превышало 2000.
В таблице 2.2 представлены результаты расчетов, разбитые на пять колонок: примеры с п 100, 100 п 150, 150 п 200, п 200 и итоговая колонка для всех примеров 19 п 255. Строка Erravg показывает среднюю погрешность полученного решения относительно рекордного решения в процентах. В этом эксперименте для 4 примеров из 96 удалось превзойти рекордное решение. В 54 случаях алгоритм нашел рекордное решение, а в остальных случаях проиграл, но средняя погрешность оказалась небольшой, всего 0,33%. Так как сравнение проводилось на известных тестовых примерах, где проверялись многие алгоритмы, применения методов субградиентной оптимизации можно считать целесообразным.
Как уже отмечалось выше, при неудачной последовательности алгоритм может не найти допустимого решения задачи. Задача может просто не иметь решений. В связи с этим был проделан эксперимент на других последовательностях для тех же примеров. В первом случае внутри каждого маршрута последовательность клиентов перемешивалась случайным образом. Во втором случае бралась произвольная последовательность всех клиентов. Заметим, что в первом случае допустимое решение всегда существует. Таблицы 2.3 и 2.4 представляют результаты этого эксперимента. Величина Erravg в таблице 2.4 показывает среднюю относительную погрешность финального решения по сравнению со стартовым решением. В первом случае только в 10 испытаниях из 960 не удалось найти допустимого решения. Для произвольной последовательности это число оказалось больше, но составило только 39, т. е. около 4% от общего числа испытаний. Средняя погрешность не превысила в среднем 4%, хотя при малом числе клиентов оказалось почти в два раза выше, точнее 6,94%. В итоге можно заключить, что для данных примеров редко не удается найти допустимое решение задачи, т.е. ограничения (2.4) не являются жесткими.
Во втором эксперименте проверялась эффективность гибридного алгоритма HLS. Для этих целей использовались те же тестовые примеры,
Гибридный алгоритм локального поиска для задачи HFFVRP параметры алгоритма: / = 100, lis = п. В процедуре Perturb переход в следующее соседнее решение осуществлялся \3I/ILS \ раз. Разработанный алгоритм сравнивался двумя наиболее эффективными из существующих эвристик: GRASP-ELS — адаптивная жадная эвристика с эволюционным локальным поиском [29] и MS-ILS-SFR — гибридная схема итеративного локального поиска с мультистартом и перераспределением ТС [51]. Первая эвристика тестировалась на ПК с процессором Opteron, 2,1 гр д /г ГГц. Вторая эвристика — на ПК с процессором IntelCore i7 2,9 ГГц, 8Гб ОЗУ. Все эксперименты проводились с использованием одного ядра процессора.
В таблицах 2.5-2.7 представлены результаты численных экспериментов. В первой колонке приводится название примера. Во второй колонке содержится размерность задачи. Для алгоритма HLS указано минимальное и среднее значение, стандартное отклонение и среднее время счета за 10 запусков алгоритма в секундах. Для других алгоритмов приводится значение целевой функции и время счета в секундах. В предпоследней колонке содержится значение целевой функции наилучшего известного решения, в последней колонке — относительная погрешность среднего значения zavg против известного рекорда в процентах. Жирным шрифтом выделены новые рекорды, полученные гибридным алгоритмом HLS.
В целом интеграция методов субградиентной оптимизации, локального поиска и новых процедур интенсификации и диверсификации показала свою эффективность. Для пятнадцати тестовых примеров удалось улучшить рекордные значения целевой функции. Средняя относительная погрешность на всех тестовых примерах составила 0,65%.
Построение допустимого решения
Общая схема алгоритма состоит из трех последовательных шагов. На первом шаге делается попытка найти допустимое решение задачи. Заметим, что проверка совместимости системы ограничений (3.2)-(3.23)
Трехфазный алгоритм маршрутизации транспортных средств является NP-трудной задачей даже при отсутствии временных окон у клиентов, рабочих смен и перерывов. Поэтому уже на первом шаге алгоритм может закончить работу. Если же допустимое решение получено, то на втором шаге минимизируется число используемых ТС. Предполагается, что величины fk,k K, определяющие стоимость привлечения ТС, существенно больше транспортных издержек. На третьем шаге при заданном автопарке минимизируются транспортные издержки для обслуживания всех клиентов.
Маршрут ТС называют допустимым, если он удовлетворяет ограничениям по временным окнам, содержит требуемое число перерывов и загрузка ТС не превышает предельной загрузки. В противном случае маршрут называют недопустимым. Допустимое решение задачи состоит из набора допустимых маршрутов, причем каждый клиент посещается только одним ТС. Под частичным решением будем понимать набор допустимых маршрутов, позволяющий обслужить некоторое подмножество клиентов, но каждый клиент из этого подмножества посещается только одним ТС.
Алгоритм построения допустимого решения будет состоять из двух этапов. На первом этапе строится частичное решение задачи и выделяется множество C необслуженных клиентов. На втором этапе делается попытка вставить необслуженных клиентов в маршруты, возможно, с нарушением ограничений по вместимости ТС и временным окнам, а затем сократить эти нарушения до нуля, используя штрафные функции и
Трехфазный алгоритм маршрутизации транспортных средств локальный поиск. Определим функцию штрафа Fpenalty(r,k,u) для k-го ТС, работающего в смену u на маршруте r как сумму штрафов за превышение длительности рабочей смены, вместимости ТС и наличия временных смещений: Fpenalty(r,k,u) = cd max{0,D(r) - Lu + Eu}+ +cQ max{0,Q(r) - Qk} + ctwTW(r). Значения штрафных коэффициентов cd,cQ,ctw подбираются в ходе локального поиска (раздел 3.4.3). Функция штрафа Fpenalty(s) для решения s определяется как сумма штрафных функций по всем маршрутам.
На первом этапе применяется жадный алгоритм с последовательным заполнением ТС [50]. При вставке очередного клиента проверяются условия по временным окнам и возможности для перерывов в течение смены. На втором этапе для полученного частичного решения s и множества C необслуженных клиентов применяется схема, впервые предложенная в работе [48]. Псевдокод этой процедуры представлен в алгоритме 4.
Алгоритм работает до тех пор, пока все клиенты не будут обслужены, либо не закончится отведенное ему время работы Tm1ax. Множество C хранится в виде очереди. На каждой итерации основного цикла (строки 4–21) из очереди извлекается первый элемент vin и делается попытка его вставки в частичное решение (строки 6–14). Если это удается сделать, т. е. множество Ninsert(vin,s) частичных решений, получающихся вставкой этого клиента, непусто, то случайным образом с равномерным распределением выбирается одно из таких решений и запоминается как текущее решение (строки 6–8). В противном случае клиент vin вставляется
Трехфазный алгоритм маршрутизации транспортных средств с минимальным штрафом и применяется процедура локального поиска RVND в надежде найти допустимое частичное решение (строки 9-10). Процедура RVND представляет собой спуск по чередующимся окрестностям и в данной случае минимизирует величину Fpenaity. Подробнее она описана в разделе 3.4.3. Если допустимое решение удалось найти, то оно сохраняется (строка 12). В противном случае из решения удаляется некоторое подмножество клиентов Vout для получения частичного решения (процедура EjectCustomers), вносятся случайные изменения (процедура Perturb) и клиенты из множества Vout добавляются в конец очереди (строки 17-18). Если по окончанию основного цикла очередь так и не оказалась пустой, то решение s возвращается в начальное состояние (строка 23).
Процедура EjectCustomers хранит статистику qv.n по числу неудачных вставок клиента г ш[48]. Величина qv.n обнуляется при удачной вставке и растет на единицу при каждой неудачной вставке. Множество Vout выбирается таким образом, что veV qv минимальна. Процедура Perturb выполняет заданное число случайных переходов по указанным выше окрестностям с сохранением допустимости решений.