Введение 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

Купить

Данная работа посвящена математическому исследования задач оптимизации вопросов логистики. Под логистикой обычно понимают область деятельности предприятия, связанную с планированием, организацией, управлением и контролем движения материальных и информационных потоков в пространстве и во времени от их первичного источника до конечного потребителя, а также науку, изучающую эти процессы [1].
Одной из основных целей оптимизации логистики является, наравне с максимизацией прибыли, также минимизация расходов, связанных с затратами на логистические операции. Наиболее общими операциями логистики здесь являются планирование закупок, распределения и сбыта, организация складирования и управление запасами, планирование перевозок, планирование производства и управление производственными процессами [1].
Фокусом данной работы являются задачи, связанные с планированием маршрутов, поскольку задачи данного класса не только актуальны в практике, но также и являются математически сложными - они принадлежат классу NP вычислительной сложности задач. Это означает, что доказательство оптимальности решения требует полного перебора решений, и в случае даже простейшей задачи маршрутизации n точек этим числом решений будет n!.
С ростом предприятий и рынков сбыта растёт и размерность задач, которые требуется разрешить. Фактически, это означает, что требования к вычислительным ресурсам для решения этой задачи традиционным точным методом растут более чем полиномиально с ростом размерности задачи, и уже сегодня их зачастую не хватает для нахождения оптимального решения этим способом. Таким образом, на практике становятся всё более популярными приближённые (эвристические) методы, а класс задач маршрутизации становится актуальным для теоретического исследования.
В реальности, к тому же, с построением маршрута связаны и многие другие факторы, из-за которых даже отдельный оптимальный маршрут может дать плохое решение для в целом, поскольку в современной практике реальные задачи обычно содержат различные дополнительные условия, ограничения и возможности. В связи с этим в теоретических исследованиях возникает необходимость рассмотрения более сложных задач. Можно выделить четыре основных класса математических моделей маршрутизации, исследуемых в настоящее время: задача коммивояжёра (travelling salesman problem), задача маршрутизации транспорта (vehicle routing problem), задача маршрутизации и управления запасом (inventory routing problem) и задача сбора и доставки (Pickup and Delivery Problems).
Вкладом данной работы являются разработка и формализация общего вида алгоритма Динамической адаптации эвристических алгоритмов и его апробация на различных классах задач маршрутизации. Дополнительно, в ходе работы предложен, сформулирован и исследован новый класс задач маршрутизации - кооперативные игры маршрутизации, являющийся расширением стандартных задач с добавлением возможности кооперации перевозчиков, что позволяет получать более эффективные решения по сравнению со стандартными случаями. Исследованы проблемы, возникающие при решении таких задач и методы их разрешения.
Данная работа включает следующие части. Во второй части представлен обзор литературы по теме актуальных моделей маршрутизации и представлены математические постановки стандартных задач. В третьей части представлена аналогичная работа по теме алгоритмов нахождения решений задач маршрутизации, а также представлена схема с подробным описанием основного алгоритма, использующегося в данной работе - адаптирующегося алгоритма поиска в большой окрестности (Adaptive Large Neighborhood Search, ALNS). Четвёртая часть содержит описание проделанной работы над концепцией Динамической адаптации: основные идеи, метод применения, общая схема динамически адаптированного алгоритма и полученные результаты при применении к различным задачам. В пятой части предлагается концепция кооперативного расширения стандартных задач маршрутизации, рассматриваются проблемы таких постановок и представляются экспериментальные результаты улучшения качества решений и устойчивости коалиций в такой задаче.

Купить