Введение 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
Приложения
Данная работа посвящена математическому исследования задач оптимизации вопросов логистики. Под логистикой обычно понимают область деятельности предприятия, связанную с планированием, организацией, управлением и контролем движения материальных и информационных потоков в пространстве и во времени от их первичного источника до конечного потребителя, а также науку, изучающую эти процессы [1].
Одной из основных целей оптимизации логистики является, наравне с максимизацией прибыли, также минимизация расходов, связанных с затратами на логистические операции. Наиболее общими операциями логистики здесь являются планирование закупок, распределения и сбыта, организация складирования и управление запасами, планирование перевозок, планирование производства и управление производственными процессами [1].
Фокусом данной работы являются задачи, связанные с планированием маршрутов, поскольку задачи данного класса не только актуальны в практике, но также и являются математически сложными - они принадлежат классу NP вычислительной сложности задач. Это означает, что доказательство оптимальности решения требует полного перебора решений, и в случае даже простейшей задачи маршрутизации n точек этим числом решений будет n!.
С ростом предприятий и рынков сбыта растёт и размерность задач, которые требуется разрешить. Фактически, это означает, что требования к вычислительным ресурсам для решения этой задачи традиционным точным методом растут более чем полиномиально с ростом размерности задачи, и уже сегодня их зачастую не хватает для нахождения оптимального решения этим способом. Таким образом, на практике становятся всё более популярными приближённые (эвристические) методы, а класс задач маршрутизации становится актуальным для теоретического исследования.
В реальности, к тому же, с построением маршрута связаны и многие другие факторы, из-за которых даже отдельный оптимальный маршрут может дать плохое решение для в целом, поскольку в современной практике реальные задачи обычно содержат различные дополнительные условия, ограничения и возможности. В связи с этим в теоретических исследованиях возникает необходимость рассмотрения более сложных задач. Можно выделить четыре основных класса математических моделей маршрутизации, исследуемых в настоящее время: задача коммивояжёра (travelling salesman problem), задача маршрутизации транспорта (vehicle routing problem), задача маршрутизации и управления запасом (inventory routing problem) и задача сбора и доставки (Pickup and Delivery Problems).
Вкладом данной работы являются разработка и формализация общего вида алгоритма Динамической адаптации эвристических алгоритмов и его апробация на различных классах задач маршрутизации. Дополнительно, в ходе работы предложен, сформулирован и исследован новый класс задач маршрутизации - кооперативные игры маршрутизации, являющийся расширением стандартных задач с добавлением возможности кооперации перевозчиков, что позволяет получать более эффективные решения по сравнению со стандартными случаями. Исследованы проблемы, возникающие при решении таких задач и методы их разрешения.
Данная работа включает следующие части. Во второй части представлен обзор литературы по теме актуальных моделей маршрутизации и представлены математические постановки стандартных задач. В третьей части представлена аналогичная работа по теме алгоритмов нахождения решений задач маршрутизации, а также представлена схема с подробным описанием основного алгоритма, использующегося в данной работе - адаптирующегося алгоритма поиска в большой окрестности (Adaptive Large Neighborhood Search, ALNS). Четвёртая часть содержит описание проделанной работы над концепцией Динамической адаптации: основные идеи, метод применения, общая схема динамически адаптированного алгоритма и полученные результаты при применении к различным задачам. В пятой части предлагается концепция кооперативного расширения стандартных задач маршрутизации, рассматриваются проблемы таких постановок и представляются экспериментальные результаты улучшения качества решений и устойчивости коалиций в такой задаче.
Таким образом, была проведена работа по обширному исследованию различных математических моделей задач маршрутизации и был проведён сравнительный анализ экспериментальных показателей в разных задачах.
В ходе работы была разработана эффективная реализация на языке C++ современного алгоритма эвристической оптимизации ALNS, и была проведена адаптация этого алгоритма на широкий круг различных задач.
На базе созданной реализации была собрана обширная база экспериментальных данных по нескольким актуальным задачам маршрутизации. Был проведён анализ всех полученных данных, по результатам которого были сделаны выводы:
• об эффективности нового метода Динамической адаптации и актуальности его использования в тех или иных задачах, основываясь на новом методе экспериментальной оценки Состоятельности во времени;
• о существенных перспективах исследования и выгоде практического применения новой модели Кооперативной игры маршрутизации запасов;
• об устойчивости различных подходов к кооперации, основанных на различных методах дележа и различных методах построения характеристической функции игры;
• о важности вычисления характеристической функции по новому методу Прямой индукции коалиций для повышения устойчивости кооперации в задачах маршрутизации.
По результатам проведённой в совокупности научной работы были опубликованы работы «Dynamic adaptive large neighborhood search for inventory routing problem» в журнале Modelling, Computation and Optimization in Information Systems and Management Sciences издательства Springer, «Heuristic evaluation of the characteristic function in the Cooperative Inventory Routing Game» в Journal on Vehicle Routing Algorithms издательства Springer и подготовлена статья «Проблема формирования устойчивых коалиций в кооперативной игре маршрутизации и управления запасами» в журнал Математическая теория игр и её приложения.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
