АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ЗАДАЧ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Хмелев Алексей Владимирович

• Хмелев Алексей Владимирович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Хмелев Алексей Владимирович

1.5 Гибридный УШ-БТБ метод

1.5.1 Общая схема алгоритма УКО-БТЯ

1.5.2 Метод чередующихся окрестностей

1.5.3 Стохастический поиск с запретами

1.5.4 Переключение процедур декодирования

1.6 Численные эксперименты

2 Гибридный алгоритм локального поиска для задачи маршрутизации разнородного ограниченного автопарка

2.1 Постановка задачи и предшествующие результаты

2.2 Метод Лагранжевых релаксаций для разбиения последовательности

2.3 Локальный поиск

2.3.1 Генерация стартового решения

2.3.2 Рандомизированный спуск по чередующимся окрестностям

2.3.3 Интенсификация поиска

2.3.4 Диверсификация поиска

2.3.5 Постоптимизация

2.4 Численные эксперименты

3 Трехфазный алгоритм оптимизации автопарка

и маршрутов транспортных средств

3.1 Постановка задачи

3.2 Математическая модель

3.3 Характеристики решений и окрестности

3.4 Алгоритм решения задачи

3.4.1 Построение допустимого решения

3.4.2 Минимизация числа маршрутов

3.4.3 Минимизация транспортных издержек

3.5 Численные эксперименты

Заключение

Литература

Введение

Введение диссертации (часть автореферата) на тему «АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ЗАДАЧ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ»

Актуальность темы.

Транспортная логистика становится все более важной составляющей многих сфер деятельности. В коммерции доля расходов на транспортировку продукта может составлять 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-трудными и требуют разработки сложных алгоритмов для нахождения качественных решений. На практике данные задачи имеют большую размерность. В такой ситуации одним из перспективных подходов является разработка методов локального поиска.

Цель данной работы состоит в разработке и исследовании алгоритмов локального поиска для решения задач маршрутизации с различными ограничениями: разделенными поставками, разнородным автопарком, рабочими сменами, временными окнами для доставки грузов клиентам и перерывами в работе водителей.

Методика исследований. В диссертации использованы современные методы исследования операций, включающие в себя построение математических моделей, теорию локального поиска и вычислительной сложности, а также методологию экспериментальных исследований с применением компьютерных технологий и коммерческих пакетов прикладных программ для решения задач целочисленного линейного программирования.

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Для задачи маршрутизации транспортных средств с распределенными поставками рассмотрена кодировка решений в виде перестановки клиентов. Показано, что существует оптимальное решение, которое соответствует некоторой перестановке. Установлено, что задача поиска наилучшего решения по заданной перестановке является КР-трудной.

2. Для задачи маршрутизации с разнородным автопарком разработан метод Лагранжевых релаксаций декодирования решения по последовательности клиентов. Представлена новая окрестность экспоненциальной мощности для локального поиска.

3. Для задачи маршрутизации транспортных средств с временными окнами и перерывами разработана математическая модель в терминах целочисленного линейного программирования. Получено выражение для оптимального времени начала перерыва при фиксированном обходе клиентов. Для расстановки перерывов в маршруте предложен метод динамического программирования.

4. Разработаны алгоритмы и комплексы программ, которые позволяют решать задачи с числом клиентов до 1000.

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Получены новые свойства различных задач маршрутизации, модифицированы известные и построены новые математические модели, разработаны численные методы решения. Разработанные методы реализованы в виде комплекса программ. Они показали свою эффективность и могут применяться при решении практических задач большой размерности. Получено свидетельство о регистрации программы №РШ5001 Фонда алгоритмов и программ СО РАН.

Результаты диссертации могут быть использованы при преподавании университетских курсов «Исследование операций» и «Теория принятия решений».

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

— Азиатская международная школа-семинар «Проблемы оптимизации сложны систем», Иссык-Куль, Киргизия, август 2009 г;

— Российская конференция «Дискретный анализ и исследование операций», Алтай, Россия, июнь 2010 г;

— Российская конференция «Дискретный анализ и исследование операций», Новосибирск, Россия, июнь 2013 г;

— Международная конференция по маршрутизации и логистики УеЯоЬ^, Саутгемптон, Великобритания, июль 2013 г;

— Всероссийская конференция «Методы оптимизаций и их приложения», о. Ольхон, Байкал, Россия, июнь 2014 г;

— Азиатская международная школа-семинар «Проблемы оптимизации сложны систем», Иссык-Куль, Киргизия, август 2014 г;

— Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, Россия, июль 2015 г;

— Международная конференция по исследованию операций 0И,2015, Вена, Австрия, сентябрь 2015 г;

Результаты неоднократно докладывались на научных семинарах Института математики им. С.Л. Соболева СО РАН и Института вычислительной математики и математической геофизики СО РАН.

Личный вклад. Результаты, представленные в диссертации, полу-

чены соискателем лично. Автор самостоятельно сформулировал цели и задачи в рамках предложенной темы, получил новые теоретические результаты. На основании проведенных исследований автор разработал программное обеспечение и провел численные эксперименты, подтверждающие эффективность предложенных методов.

Публикации. По теме диссертации автором опубликовано 12 работ, в том числе 5 статей в журналах из списка ВАК.

Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (64 наименования). Объем диссертации — 119 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении формулируются цель и задачи исследования, обосновывается актуальность выбранной темы и указываются основные методы решения поставленной задачи. Отмечена новизна полученных результатов и их практическая и теоретическая ценность. Приводятся сведения об апробации работы и публикациях. Кратко излагается содержание работы.

В первой главе рассматривается задача маршрутизации транспортных средств с разделенным обслуживанием (The split delivery vehicle routing problem, SDVRP). В отличии от базовой задачи, где каждый клиент должен быть обслужен ровно одним ТС, в задаче с разделенным обслуживанием данное ограничение снимается. Таким образом, часть груза может быть доставлена одним ТС, а часть — другим. Известно, что такая релаксация позволяет уменьшить суммарное пройденное расстояние

до двух раз (М. Эгог). Наибольший вклад в исследование данной задачи внесли С. АгсЬеШ, Ь. ВегЬо^о, М. Boudia, М. С. Брегама.

В данной главе исследуется возможность кодирования решений задачи БВУЯР в виде перестановки клиентов без повторений. Показано, что для любого оптимального решения можно перенумеровать клиентов таким образом, что все ТС будут всегда ехать от клиента с меньшим номером к клиенту с большим номером. Исследована сложность восстановления решения по заданной перестановке клиентов.

В разделе 1.1 приводится математическая постановка задачи маршрутизации с разделенным обслуживанием. Рассмотрим полный неориентированный граф О = (V, Е) на п +1 вершине. Вершина 0 соответствует складу. Оставшиеся вершины V' = V \ {0} соответствуют клиентам. Каждому клиенту % соответствует положительный запрос qi. Каждому ребру (%,2) из множества Е соответствует неотрицательная длина с^. Предполагается, что для всех вершин %, 2, к из множества V выполняется неравенство треугольника с^ + > ск. На складе находится автопарк из т одинаковых транспортных средств. Каждое ТС имеет положительную вместимость (. Маршрут каждого ТС начинается и заканчивается на складе. Необходимо найти такое множество маршрутов, чтобы все клиенты были обслужены и суммарная длина маршрутов была минимальной.

Опишем математическую постановку задачи маршрутизации с разделенными поставками. Введем следующие переменные: х^к £ {0,1} равняется 1, если и только если ТС к едет напрямую от клиента % к ]; у^ > 0 — количество единиц запроса, поставленного клиенту % транспортным

средством к; Щк > 0 вспомогательная целочисленная переменная, определяющая порядковый номер клиента г в маршруте ТС к. Используя эти переменные, запишем математическую постановку задачи:

п п т

г=0 !=0 к=1

при ограничениях:

^Х^'к > 1, 3 =0,...,П,

к=1 ¿=0

х!к = ^2 !, 3 = 0,..., п; к = 1,..., т,

¿=0 ¿=0

игк — щк + пЖук < п — 1, г, з = 1,..., п; к = 1,..., т,

Угк < Яг х%зк, г = 1,... ,п; к = 1,... ,т, !=0

п

^Угк < к = 1,..., т,

г=1

т

^Угк = Яг, г = 1,...,п, к=1

жг!-к е {0,1}, г,з = 0,..., п; к = 1,..., т, Игк ,Угк > 0, г = 1,..., п; к = 1,...,т.

В разделе 1.2 напоминаются некоторые известные свойства оптимальных решений задачи, а также доказываются новые. Пусть (х !к)(у*к)(и*к) оптимальное решение для задачи. Обозначим через Я * = (гЦ, ...,гт) соответствующее множество маршрутов, где гк = {(г,3) Е Е | = 1}, к = 1, . . . , т.

Определение 3 Пусть п = {%\,... ,%п} — перестановка клиентов. Цикл г соответствует п, если можно стартовать со склада и перемещаться по маршруту г без нарушения линейного порядка в п. Множество маршрутов Я соответствует п, если каждый маршрут в Я соответствует п.

Теорема 4 Если матрица расстояний (с^) удовлетворяет неравенству треугольника, то для множества оптимальных маршрутов Я* существует перестановка клиентов п такая, что Я* соответствует п.

Следствие 1 Если матрица (с^) удовлетворяет неравенству треугольника, то существует оптимальное решение задачи вБУЯР такое, что и*к = и*к для всех % £ V' и к\,к2 £ {1,... ,т}.

Теорема 5 Если матрица расстояний (с^) удовлетворяет неравенству треугольника, то задача ББУЯР является ЫР-трудной даже для заданной перестановки клиентов.

В связи с тем, что задача для фиксированной последовательности остается КР-трудной, то дальнейший ход исследований был направлен на разработку приближенных алгоритмов декодирования решения по последовательности.

В разделе 1.3 предлагается способ кодирования решения посредством расширенной перестановки клиентов с повторениями. Предлагается две эффективные процедуры декодирования таких перестановок. Одна из них — метод динамического программирования, другая — жадных алгоритм. Эти процедуры имеют трудоемкость 0(п2) и О(п) соответственно.

В разделе 1.4 определяются окрестности решений, представленных

как в виде перестановок, так и в виде набора маршрутов. Эти окрестности представляют из себя множество соседних решений полученных посредством применения к заданному решению различных операций. В зависимости от окрестности, множество соседних решений может иметь как полиномиальную так и экспоненциальную мощность.

В разделе 1.5 описывается гибридный алгоритм локального поиска, который сочетает в себе метод спуска по чередующимся окрестностям (пункт 1.5.2) и метод поиска с запретами (пункт 1.5.3). Для корректного переключения процедур декодирования вводятся дополнительные операции над перестановками (пункт 1.5.4).

В разделе 1.6 приведены результаты численных экспериментов для гибридного алгоритма. Эксперименты проводились на трех наборах известных тестовых примеров [10, 13, 22]. В общей сложность было 95 тестовых примеров размерностью до 288 клиентов. Проводилось сравнение с наиболее эффективными существующими эвристиками для данной задачи. Для 23 примеров были найдены новые рекордные значения целевой функции.

Во второй главе исследуется задача маршрутизации разнородных транспортных средств ограниченной грузоподъемности (The heterogeneous fixed fleet vehicle routing problem, HFFVRP). В данной задаче грузоподъемность транспортных средств различна, а число транспортных средств каждого типа ограничено. Предполагается, что каждый тип транспортного средства имеет фиксированную стоимость запуска на маршрут и удельную стоимость проезда. Обзоры по данной задаче представлены в работах R. Balldacci, M. Battarra, D. Vigo.

Исследуется КР-трудная подзадача декодирования последовательности клиентов. Для её решения предлагается метод Лагранжевых релаксаций. Для задачи ЫРРУЯР разработан алгоритм итеративного локального поиска с новой окрестностью экспоненциальной мощности. Разработаны новые процедуры интенсификации и диверсификации поиска, основанные на новой процедуре декодирования.

В разделе 2.1 представлена точная постановка задачи и приводится краткий обзор предшествующих исследований. Снова рассматривается граф О = (V, Л), где вершины соответствуют клиентам, и для каждой пары клиентов известно расстояние между ними. Автопарк состоит из разнородных транспортных средств. Множество типов ТС обозначим через К. Для каждого типа к £ К известно число тк доступных транспортных средств и их предельная вместимость (к. Использование ТС влечет единовременные затраты /к. Проезд из % в 2 стоит ск = ск, где ск — удельные затраты на единицу расстояния для ТС типа к.

Пусть г — некоторый маршрут в графе О. Будем говорить, что маршрут допустим для ТС типа к, если он образует цикл, проходящий через вершину 0, и сумма запросов клиентов не превышает вместимости транспортного средства. Стоимость маршрута г складывается из фиксированной стоимости /к для привлечения ТС и суммарной стоимости ребер этого цикла. Задача состоит в нахождении такого набора допустимых маршрутов и назначения им ТС, чтобы каждый клиент посещался ровно один раз, число привлекаемых ТС не превышало численности автопарка, а суммарная стоимость маршрутов была минимальной.

Введем следующие переменные:

€ {0,1} равняется 1, если ТС типа к от клиента г едет к клиенту 3; У! > 0 — количество груза в ТС при переезде от клиента г к клиенту 3.

С использованием введенных переменных, задача маршрутизации разнородных транспортных средств может быть сформулирована в терминах частично-целочисленного линейного программирования:

к€К кбКг^бУ

при ограничениях:

ЕЕ4 = l, з е ^

Л

"г!

кбК геУ

Е4 = Ехкг, 3 Е У,к е К,

г! / у !

геУ геУ

< тк, к Е К,

! еУ'

Е^-? ^^ У^г = ^ , 3 Е ^

г У г У

У0! < Е ^кХ^! , 3 Е V',

кеК

Уг! < Е(^к — Яг)4, г Е V,3 Е V, г = 3.

кЕК

.^к — Яг )Хк кЕК

В разделе 2.2 рассматривается задача разбиения последовательности клиентов на маршруты транспортных средств и предложен метод Лагранжевых релаксаций для ее решения. Представим задачу разбиения последовательности п = (п1,... , пп), пг Е V' на маршруты в терминах поиска кратчайшего пути в ориентированном взвешенном мультиграфе на множестве вершин V' и {п + 1}. Вершина п1 будет единственным источником, вершина п + 1 — единственным стоком. Для каждой пары

(%, 2), 1 < % < 2 < п + 1 определим набор дуг (%, 2)к,к £ К, соответствующих проезду ТС типа к со склада к клиенту п', затем к клиенту п'+1 и т.д. до клиента Пj-1 и затем возвращению обратно на склад. Стоимость Ьк такой дуги определим следующим образом:

гк =

Ьч =

( j-2 \ j-1 /к + ГЦ (оп + + , если qпt < Як;

то,

г=г

в противном случае.

Оптимальное разбиение последовательности получается нахождением пути минимальной стоимости из источника в сток при ограничении на число используемых дуг каждого типа (рис. 1).

Запишем эту задачу в терминах целочисленного линейного программирования. Пусть булева переменная гк принимает значение 1, если и только если дуга (%,])к входит в оптимальное решение. Тогда требуемый путь может быть получен из решения следующей задачи:

Ш1П

п п+1

1п£ Е Е Ь

к£К '1=1 j=i+1

к к

(1)

при ограничениях:

п+1 ' —1

Е Е - Е Е

к£К Ч='+1 к£К Ч=1

1, если % = 1,

= < -1, если % = п + 1,

0, если 1 < % < п + 1,

(2)

п п+1

Е Е гк ^ тк, к £ К. (3)

'=1 ч='+1

Ограничение (3) устанавливает верхнюю границу на количество используемых ТС каждого типа.

О

n + 1

Рис. 1: Мультиграф для последовательности п

Задача (1)-(3) NP-трудна, но удаление ограничений (3) делает ее полиномиально разрешимой. Введем неотрицательные множители Лагран-жа Ak для каждого из неравенств (3) и добавим в целевую функцию (1) слагаемое ^keK AkГ=1 ZlJ+i+i Zj — m). Приводя подобные члены, получаем релаксированную задачу:

n n

LR(Ak) = min ЕЕ Е(4 + Ak — E Ak

keK ¿=1 j=i keK

при ограничениях (2).

Эта задача о нахождении кратчайшего пути в мультиграфе для по-

следовательности п (рис. 1) с ребрами весом = Ьк + Ак. Она легко решается точно динамическим программированием и дает нижнюю оценку целевой функции (1). Поиск наилучшей такой оценки по множителям Лагранжа приводит к двойственной задаче:

В = шахАк>о ЬЯ(Ак).

Для её решения используется метод субградиентной оптимизации.

Раздел 2.3 посвящен гибридному алгоритму локального поиска. Основными элементами этого алгоритма являются процедуры локального поиска с чередующимися окрестностями (пункт 2.3.2), интенсификации поиска (пункт 2.3.3), диверсификации поиска (пункт 2.3.4) и постопти-

мизации (пункт 2.3.5). Предложенные процедуры интенсификации и диверсификации основаны на методе Лагранжевых релаксаций. Процедура постоптимизации использует новую окрестность экспоненциальной мощности типа ejection chains. Эта окрестность выбирает набор маршрутов и разбивает каждый маршрут на две части. Эти части склеиваются в новые маршруты так, чтобы минимизировать суммарную стоимость проезда.

В разделе 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,A). Для каждой дуги (i,j) G A известно не только расстояние между ними dij но и время проезда tj. Для каждого клиента i G V1 определена длительность обслуживания Ti и требование на доставку qi единиц груза. Обслуживание клиента i должно начинаться внутри временного окна [ei,li].

Автопарк состоит из различных ТС, их множество обозначим через K. Для каждого k G K задана грузоподъемность Qk, удельные затраты Ск на перевозку грузов, единовременные фиксированные затраты fk, связанные с использованием ТС и рабочая смена u(k). Пусть U = {1,... ,m} — множество рабочих смен. Каждая смена u имеет временное окно [Eu, Lu], в котором водитель должен начинать и заканчивать свой маршрут. Кроме того, в течении смены u водитель должен сделать tu перерывов Pu = {P1,..., PUu} в работе. Каждый перерыв имеет свою

длительность и временное окно. Перерывы не могут идти подряд, между ними должен обслуживаться хотя бы один клиент. Если в маршруте мало клиентов, то число перерывов должно быть сокращено. Задача состоит в минимизации суммарной стоимости маршрутов всех ТС при удовлетворении всех ограничений по времени и грузоподъемности.

В разделе 3.2 построена новая математическая модель в терминах целочисленного линейного программирования с произвольным числом перерывов. Для каждого клиента г € V' введем ^ и фиктивных клиентов. Обслуживание такого клиента будет требовать перерыва в работе водителя. Перерыв может следовать сразу после обслуживания клиента, либо через некоторое время, но до посещения следующего клиента в маршруте.

Пусть Р — список всех перерывов, Р = (Р/,... , Р*1,..., Р^,... , РтТ). Через г(Ри) обозначим позицию перерыва (Р^) в списке Р. Определим новый набор индексов W = V и V и • • • и V?| и {0'}, где V = {гп + г,..., (г + 1)п + г} — множество вершин, связанных с перерывом г € Р. Последняя вершина 0' с номером |W | обозначает склад как конечный пункт любого маршрута. Через V (и) = {^(^1),..., ^р^«)} обозначим подмножество вершин с перерывами для заданной рабочей смены и.

Введем расширенную матрицу }, г, 7 € W следующим образом:

, 0, при 3 = г + кп + к, ^ = ^ г € V, 7 € V и... и ^р |,к = 1,..., |Р |;

то, иначе,

, оо, при 3 = г — кп — к,

^ = ^ г € V и...и^р |,7 € ^к = 1,..., |Р |;

¿г-кп-л,^, иначе,

dj = оо, i е Vi и ... и V\P\,j е Vi и ... и V\P\;

di+kn+k,\w | = dio, i е V', k = 0,1,..., \P |;

d'\wj = O j е W.

Для каждого фиктивного клиента определим его временное окно как окно соответствующего перерыва. Длительность обслуживания такого клиента будет равна длительности перерыва. Введем переменные задачи: xijk е {0,1} равняется 1, если и только если k-е ТС едет из i в j, tjk > 0 — время проезда из i в j для k-го ТС, sik > 0 — начало обслуживания k-м ТС клиента i, yik е {0,1} равняется 1, если и только если k-е ТС посещает клиента

i.

Тогда целевая функция задачи записывается следующим образом: min fkyok + Е ck Е ddijj Xijk

k£K k£K i,j&W

Показано, что при такой трансформации входных данных задачи, все ограничения можно записать в линейном виде.

В разделе 3.3 описываются характеристики решений. Предлагается использовать штрафы за нарушение ограничений по вместимости ТС, длительности маршрутов и временным окнам. Если ТС приходит позже временного окна к клиенту i (sik > li), то будем считать, что опоздания не было, время прибытия совпадает с окончанием временного окна, sik = li, но появляется временное смещение twi-1^i, равное величине опоздания. Тогда общее временное смещение для последовательности обхода

клиентов а определяется как сумма смещений: TW(а) = ^ iwi-1;i. Длительность обхода D последовательности а с учетом временного смещения получается равной D(a) = S|a|k — s0k + TW(r). Также вводятся характеристики E(а) и L(a), соответствующие наиболее раннему и позднему временам приезда к первой вершине в последовательности, допустимым для расписания с минимальной длительностью.

Далее определяются окрестности, используемые в локальном поиске: Swap, Relocate, 2-opt, 2-opt*. Переход по любой из введенных окрестностей можно представить как разбиение маршрутов на подпоследовательности и их склейку в новые маршруты. В случае вставки одного перерыва между последовательностями а1 = (а1,..., а1) и а2 = (а2,..., а2,) при их склейке получено точное значение времени начала перерыва:

Теорема 6 Оптимальное время проезда до перерыва определяется формулой = min{max{ev — D^1) + TW(а1) — Да1), 0},taia2}.

p p 3 i!

Для расстановки перерывов при склейке последовательностей применяется метод динамического программирования. Обозначим через аиj последовательность а, содержащую внутри себя перерывы {pU,... ,pU}, 1 < i < j < для смены u. Для подпоследовательности а0 с одним клиентом v получаем: ) = т^ TW(а°у) = ^ E(а°у) = ^ ) = 0

для любых 1 < i < j < , u G U. Для склейки (а1 0 а2) расстановку перерывов будем выбирать из следующего множества:

Suij = {а1 0 а2у-} U {а^ 0 а2,к+ц|i < k < j} U {а^- 0 а2}U {а1 0

Pi 0 } U К^-1 0 0 а2,к+1 j|i < k < j} U K^— 0 pj 0 а2}.

Тогда (а1 0 а2)mj = argminCTe£ D(а).

Теорема 7 Пусть а1 = (а1,... ,аЦ) и а2 = (а2,... ,/7?,) — две последовательности клиентов. Трудоемкость вычисления расстановки перерывов {Р^,..., Р1ии} рабочей смены и для склейки а1 0 а2 с помощью процедуры динамического программирования равна 0((|а 1|2 + |а2|2)£Ц).

В разделе 3.4 описывается трехфазный алгоритм локального поиска для решения задач большой размерности. Ключевой процедурой данного алгоритма, является процедура распределения клиентов, которая позволяет добавлять клиентов в решение без привлечения новых ТС. На первом этапе строится допустимое решение жадным алгоритмом. На стадии оптимизации автопарка происходит последовательное сокращение числа привлекаемых ТС. На третьей стадии минимизируются затраты на доставку грузов для фиксированного автопарка методами локального поиска.

В разделе 3.5 приводятся численные эксперименты, подтверждающие эффективность данного алгоритма. В качестве тестовых примеров использовались два набора данных реальных поставок продукции в Новосибирске. В первом эксперименте показано влияние числа перерывов в смене на трудоемкость локального поиска. Во втором эксперименте исследованы возможности сокращения автопарка и влияние перерывов на этот процесс. Число ТС удалось сократить минимум на 20%.

Глава 1

Гибридный локальный поиск для задачи маршрутизации транспортных средств с разделенными поставками

Список литературы диссертационного исследования кандидат наук Хмелев Алексей Владимирович, 2016 год

Литература

[1] Кочетов Ю.А., Сивых М. С., Хмелёв А. В., Яковлев А. В. Методы локального поиска для одной задачи о перестановке столбцов бинарной матрицы // Вестник НГУ. Серия: Математика, механика, информатика. — 2011. — Т. 11, вып. 4. — С. 30-41.

[2] Сивых М.Г., Хмелёв А.В., Яковлев А.В. Метаэвристики для задачи о перестановке столбцов 0-1 матрицы. // Труды ИВМиМГ СО-РАН. Материалы пятой международной школы-семинар "Проблемы оптимизации сложных систем"Новосибирск. — 2009. — Серия: Информатика. Выпуск 9. — с. 202 — 209.

[3] Стецюк П.И. Методы эллипсоидов и г-алгоритмы.// Кишинэу: Эврика. — 2014. — С. 285-289.

[4] Кочетов Ю. А., Хмелев А. В. Гибридный алгоритм локального поиска для задачи маршрутизации разнородного ограниченного автопарка // Дискрет. анализ и исслед. операций. — 2015. — Т. 22, вып. 5. — С. 5-29.

[5] Хмелев А.В. Трехфазный алгоритм оптимизации автопарка и маршрутов транспортных средств // Дискрет. анализ и исслед. операций. — 2015.— Т. 22, вып. 6. — С. 55-77.

[6] Aleman R.E., Hill R.R. A tabu search with vocabulary building approach for the vehicle routing problem with split demands. // Int. J. Metaheuristics. - 2010. - Vol. 1, № 1. - P. 55-80.

[7] Archetti C., Bianchessi C., Speranza M.G. A column generation approach for the split delivery vehicle routing problem. // Networks.

- 2011. Vol. 58, № 4. - P. 241-254.

[8] Archetti C., Savelsbergh M., Speranza M.G. Worst-case analysis for split delivery vehicle routing problems. // Transportation Science. -2006. - Vol. 40, № 2. - P. 226-234.

[9] Archetti C., Speranza M.G., The split delivery vehicle routing problem: A survey.// New York: Springer-Verlag. - 2008. - P. 103-122.

[10] Archetti C., Hertz A., Speranza M.G. A tabu search algorithm for the split delivery vehicle routing problem.// Transportation Science.

- 2006. - Vol. 40, №.1. - P. 64-73.

[11] Baldacci R., Battarra M., Vigo D. Routing a Heterogeneous Fleet of Vehicles.// The vehicle routing problem: latest advances and new challenges. - Springer. - 2008. - P. 3-27.

[12] Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems. // Mathem. Programming. - 2009.

- Vol. 120. - P. 347-380.

[13] Belenguer J., Martinez M., Mota E. A lower bound for the split delivery vehicle routing problem. // Operations Research. - 2000. Vol. 48, № 5. - P. 801-810.

[14] Bent R., Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows// Transportation Science.

- 2004. - Vol. 38. - P 515-530.

[15] Berbotto L., Garcia S., Nogales F.G. A randomized granular tabu search heurstic for the split delivery vehicle routing problem. // Annals of Operations Research. - 2014. - Vol. 222. - P. 153-173

[16] Bostel N., Dejax P., Guez P., Tricoire F. Multiperiod planning and routing on a rolling horizon for field force optimization logistics.// In Bruce Golden, S. Raghavan, & Edward Wasil (Eds.). The vehicle routing problem: Latest advances and new challenges. - 2008. New York: Springer. - Vol. 43. - P. 503-525.

[17] Boudia M., Prins C., Reghioui M. An effective memetic algorithm with population management for the split delivery vehicle routing problem.// Hybrid Metaheuristics, Lecture Notes in Computer Science.

- 2007. Vol. 4771. - P. 16-30.

[18] Brandao J. A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem.// Eur. J. Oper. Res. - 2009. - Vol. 195.

- P. 716-728.

[19] Brandao J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem // Comp. Oper. Res. - 2011. - Vol. 38. - P. 140-151.

[20] Braysy O., Gendreau M. Vehicle routing problem with time windows, Part I: Route constraction and local search algorithms //Transportation Science. - 2005. - Vol. 39. - P. 104-118.

[21] Braysy O., Gendreau M. Vehicle routing problem with time windows, Part II: Metaheuristics //Transportation Science. - 2005. - Vol. 39.

- P. 119-139.

[22] Chen S., Golden B., Wasil E. The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results.// Networks. - 2007. - Vol. 49, № 4. - P. 318-329.

[23] Clarke G., Wright J. Scheduling of vehicles from a central depot to a number of delivery points. //Operations Research. - 1964. Vol. 12, № 4. - P. 568-581.

[24] Desaulniers G. Branch-and-price-and-cut for the split delivery vehicle routing problem with time windows. // Operations Research. - 2010.

- Vol. 58. - P. 179-192.

[25] Desrocher M., Laporte G. Improvements and extentions to the Miller-Tucker-Zemlin subtour elimination constraints. // Operation Research Letters. - 1991. Vol. 10. - P. 27-36.

[26] Desrosiers, J., Soumis, F, Desrochers, M., and Sauve, M. Methods for routing with time windows.// Eur. J. Oper. Res. - 1986. Vol. 23. - P. 236-245.

[27] Duhamel C., Gouinaud C., Lacomme P., Prodhon C. A multi-thread GRASPxELS for the heterogeneous capacitated vehicle routing problem //In Hybrid Metaheuristics, Talbi E-G. (Ed). - 2013. Vol. 434 of Studies in Computational Intelligence. - P. 237-269.

[28] Duhamel C., Gouinaud C., Lacomme P., Prodhon C. Efficient frameworks for greedy split and new depth first search split procedures for routing problems. // Comp. Oper. Res. - 2011. - Vol. 38, № 4. -P. 723--739.

[29] Duhamel C., Lacomme P., Prins C., Prodhon C. A GRASPxELS with depth first search split procedure for the hvrp.// LIMOS. - Research Report LIMOS/RR-10-08. - 2010.

[30] Dror M., Trudeau P. Savings by split delivery routing. //Transportation Science. - 1989. Vol. 23, № 2. - P.141-145.

[31] Dror M., Trudeau P. Split delivery routing. // Naval Research Logistics. - 1990. - Vol. 37, № 3. - P.383-402.

[32] Frizzell P., Giffin J.. The bounded split delivery vehicle routing problem with grid network distances. //Asia-Pacific Journal of Operational Research. - 1992. - Vol. 9. - P.101-116.

[33] Gagliardi J.-P., Renaud J., Ruiz A., Coehlo C. L. The Vehicle Routing Problem with Pauses.// Technical report 2014-22. CIRRELT. Montreal. QC. Canada.

[34] Gehring H., Homberger J. Parallelization of a two-phase metaheuristic for routing problems with time windows. // Asia-Pacific Journal of Operational Research. - 2001. - Vol. 18. - P. 35-47.

[35] Gendreau M., Dejax P., Feillet D., Gueguen C. Vehicle routing with time windows and split delivery.// Technical Report 2006-851. Laboratoire Informatique d'Avignon. France.

[36] Glover F, Laguna M. Tabu Search. // Kluwer Academic Publishers. -1997.

[37] Glover F. New ejection chain and alternating path methods for traveling salesman problems. /// Comput. Sci. Oper. Res. - 1997 - P.449-509.

[38] Goel A. Vehicle scheduling and routing with drivers' working hours. // Transportation Science. - 2009. - Vol. 43, № 1. - P. 17-26.

[39] Goel A., Archetti C., Savelsbergh M. Truck driver scheduling in Australia.// Computers and Operations Research. - 2012. - Vol. 39, № 5. - P. 1122-1132.

[40] Goel A., Vidal T. Hours of service regulations in road freight transport: An optimization-based international assessment. // Transportation Science. - 2013. - Vol. 43, № 3. - P. 391-412

[41] Johnson D.S., McGeoch L.A. The traveling salesman problem: a case study. In: Aart E, Lenstra JK (Eds) Local Search in Combinatorial Optimization.//Jonh Wiley & Sons Ltd. - 1997. - P. 215-310.

[42] Khmelev A., Kochetov Y. A hybrid local search for the split delivery vehicle routing problem. // International Journal of Artificial Intelligence. - 2015. - Vol. 13, № 1. - PP. 147-164.

[43] Khmelev A., Kochetov Y. A hybrid VND method for the split delivery vehicle routing problem. // Electronic Notes in Discrete Mathematics. - 2015. - Vol. 47. - P. 5-12.

[44] Lee C.G., Epelman M.A., White C.C., Bozer Y. A shortest path approach to the multiple-vehicle routing problem with split pick-ups.//Transp. Res. Part B. - 2006. - Vol. 40, № 4. - P. 265-284.

[45] Li F., Golden B., Wasil E. A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. // Comp. Oper. Res. - 2007. - Vol. 34. - P. 2734-2742.

[46] Mladenovic N., Hansen P. Variable neighborhood search. // Comput. Oper. Res. - 1997. - Vol. 24, № 11. - P. 1097-1100.

[47] Mota E., Campos V., Corberan A. A new metaheuristic for the vehicle routing problem with split demands. // Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science. -Springer, Berlin/Heidelberg. - 2007. Vol. 4446. - P.121-129.

[48] Nagata Y., Braysy O. A powerful route minimization heuristic for the vehicle routing problem with time windows. //Operations Research Letters. - 2009. - Vol. 37. - P. 333-338.

[49] Nagata, Y., Braysy, O., Dullaert, W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. // Comp. & Oper. Res. - 2010. - Vol. 37. - P. 724-737.

[50] Penna P.H.V., Subramanian A., Ochi L.S. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. // J.Heuristics. - 2013. - Vol. 19. - P. 201-232.

[51] Penna P.H.V., Vidal T., Ochi L.S., Prins C. New compound neighborhoods structures for the heterogeneous fixed fleet vehicle

routing problem.// Conference Proceedings: Simpysio Brasileiro de Pesquisa Operacional. 2013. Natal/RN. — P. 3623-3633.

[52] Poljak B.T. Subgradient Methods: A Survey of Soviet Research In Nonsmooth Optimization, C. Lemarechal and R. Mifflin (Eds.)// IIASA Proceedings Series. — 1977. — Vol. 3.

[53] Potvin J.Y., Naud M.A. Tabu Search with ejection chains for the vehicle routing problem with private fleet and common carrier.//Journal of the Operations Research Society. — 2011. — Vol. 62. — P.326-336.

[54] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. // Computers and Operations Research. — 2004. Vol. 31. — P. 1985-2002.

[55] Prins C. Eficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case. //J. Mathem. Modelling and Algorithms. — 2002. — Vol. 1. — P. 135-150.

[56] Prins C. Two memetic algorithms for heterogeneous fleet vehicle routing problems. // Engineering Applications of Artificial Intelligence. — 2009. — Vol. 22, № 6. — P. 916-928.

[57] Sahoo S., Kim S., Kim B.-I., Kraas B., Popov A. Jr. Routing optimization for waste management. // Interfaces. — 2005. — Vol. 35, N 1. — P. 24-36.

[58] Subramanian A., Penna P. H. V., Uchoa E., Ochi, L. S. A hybrid algorithm for the heterogenous fleet vehicle routing problem.// Eur. J. Oper. Res. — 2012. — Vol. 221. — P. 285-295.

[59] Taillard E. D. A heuristic column generation method for heterogeneous fleet VRP. // RAIRO - Operations Research. - 1999. - Vol. 33. - P. 1-14.

[60] Tarantilis C. D., Kiranoudis C. T., Vassiliadis V. S. A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. // J.Operat. Res. Society. — 2003. — Vol. 54. — P. 65-71.

[61] Tarantilis C. D., Zachariadis E. E., Kiranoudis C. T. A guided tabu search for the heterogeneous vehicle routeing problem// J.Operat. Res. Society. — 2008. — Vol. 59. — P. 1659-1673.

[62] Tarantilis C. D., Kiranoudis C. T., Vassiliadis V. S. A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. // Eur. J. Oper. Res. — 2004. — Vol. 152. — P. 148—158.

[63] Vidal, T., Crainic, T. G., Gendreau, M., Prins, C. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows.// Computers and Operations Research. — 2013. — Vol. 400, — P. 475-489.

[64] Vidal T., Crainic T.G., Gendreau M., Prins C. A Unified Solution Framework for Multi-Attribute Vehicle Routing Problems.// Eur. J. Oper. Res. — 2014. — Vol. 234, N 3. — P. 658-673.