Введение 4
Глава 1. Обзор задач транспортной маршрутизации с вывозом и доставкой товара (Vehicle Routing Problem with Pickups and Deliveries) ... 6
1.1. Задачи транспортной маршрутизации группы М-М с вывозом и
доставкой товара (Many-to-many Vehicle Routing Problem with Pickups and Deliveries) 7
1.2. Задачи транспортной маршрутизации группы 1-M-1 с вывозом и
доставкой товара (One-to-many-to-one Vehicle Routing Problem with Pickups and Deliveries) 7
1.3. Задачи транспортной маршрутизации группы 1-1 с вывозом и доставкой товара (One-to-one Vehicle Routing Problem with Pickups and
Deliveries) 8
1.4. Виды ограничений в задачах VRP 9
Глава 2. Методы решения задачи маршрутизации с вывозом и
доставкой 11
2.1. Метод k-средних 12
2.2. Метод поиска с запретами (Tabu Search) 14
2.3. Генетический алгоритм (Genetic algorithm) 16
Глава 3. Динамическая адаптация метода 18
3.1. Временная состоятельность алгоритма 18
3.2. Динамическая адаптация алгоритма 19
Глава 4. Решение задачи маршрутизации 1-1 вывоза и доставки товара с несколькими транспортными средствами одинаковой
грузоподъемности 21
4.1. Постановка задачи 21
4.2. Математическая модель задачи 21
4.3. Эксперимент: решение тестовых задач из библиотеки NEO 23
4.4. Сравнение метода поиска с запретами и генетического алгоритма 24
4.5. Динамическая адаптация метода поиска с запретами 26
4.6. Сравнение динамически адаптированного метода поиска с
запретами и генетического алгоритма 28
Выводы 30
Заключение 31
Литература 32
Приложение 35
Приложение 1. Функция метода k-средних 35
Приложение 2. Функция метода поиска с запретами 36
Приложение 3. Основные функции генетического алгоритма 40
Приложение 4. Функция жадного алгоритма 45
Приложение 5. Функция динамической адаптации метода поиска с запретами 47
Приложение 6. Таблица результатов работы алгоритмов 49
Комбинаторная оптимизация занимается поиском оптимального объекта в конечном множестве объектов. Одной из известных задач этой области является задача коммивояжера (Travelling salesman problem, TSP). Коммивояжер (от фр.commis voyageur) - разъездной посредник, торговый агент фирмы, передвигающийся с поручениями. Его задача объехать все заданные пункты. Необходимо составить наиболее выгодный маршрут, обходящий все точки и возвращающийся в исходную.
Основной целью в транспортной логистике является построение эффективных с точки зрения стоимости маршрутов объезда транспортными средствами пунктов-продавцов и пунктов-покупателей. В понятие стоимости в данном случае включаются любые затраты, возникающие в процессе объезда клиентов транспортным средством (ТС), которые могут определяться через длину маршрута, время в пути или количество потребляемого топлива. Правильная организация транспортировки может уменьшить экономические затраты на перевозку. Поэтому этот вопрос является одним из наиболее важных для многих предприятий.
Все задачи данного класса являются NP-трудными, поэтому в тестовых примерах большой размерности задача становится трудно вычисляемой, т.е. не может быть решена методами с полным перебором вариантов решений. Как правило, используют эвристические и метаэвристические алгоритмы. Они генерируют решения, приближенные к оптимальному, но за меньшее по сравнению с точными методами время.
В данной работе рассмотрен один из видов обобщения задачи коммивояжера - задача маршрутизации с вывозом и доставкой несколькими транспортными средствами. В главе 1 представлена классификация задач из данного класса, а в главе 2 - методы решения, и подробно разобраны метод поиска с запретами и генетический алгоритм для построения маршрутов. Глава 3 посвящена одному из критериев оценки эффективности эвристического алгоритма - временной состоятельности решений и методу модификации алгоритма, идея которого основана на временной несостоятельности решений, получаемых эристиками. В главе 4 приведена формулировка задачи маршрутизации 1-1 с вывозом и доставкой с несколькими транспортными средствами одинаковой грузоподъемности, а затем представлены решения задачи на тестовых данных и анализ полученных решений.
Целью работы является решение задачи 1-1 маршрутизации вывоза и доставки товара с несколькими транспортными средствами одинаковой грузоподъемности.
Задачи работы:
• Исследование решений задачи транспортной маршрутизации, генерируемых эвристическими методами;
• Программная реализация метода поиска с запретами и генетического алгоритма;
• Разработка динамической адаптации метода поиска с запретами;
• Сравнение результатов работы алгоритмов между собой.
В данной работе был рассмотрен класс задач транспортной маршрутизации и подробно исследована одна из задач - задача маршрутизации с вывозом и доставкой с несколькими транспортными средствами ограниченной грузоподъемности.
Были изучены подходы к решению данного типа задач. Был выбран двухэтапный метод решения задач: на первом этапе было распределение вершин по ТС, а на втором - формирование маршрутов для каждого ТС. На языке программирования Python был реализован метод k-средних для первого этапа. Для второго были выбраны метод поиска с запретами и генетический алгоритм, реализованные на том же языке. Далее на тестовых примерах произведено сравнение результатов алгоритмов: генетический алгоритм генерирует решения с меньшим значением целевой функции, в среднем на 7%, но за более длительное время.
Далее экспериментально определена оценка временной состоятельности метода поиска с запретами. Эксперимент показал, что всего треть решений являются динамически устойчивыми, а значит, решения могут быть улучшены. Поэтому далее метод модифицирован с помощью идеи динамической адаптации алгоритмов. Анализ экспериментов показал, что улучшение решения на тестах с различным количеством ТС и различной грузоподъемностью в большинстве случаев доходит минимум до 5%. Таким образом, использование на практике динамически адаптированного метода поиска с запретами позволяет генерировать маршруты меньшей стоимости.
На последнем этапы было произведено сравнение модифицированного метода поиска с запретами и генетического алгоритма. Результаты экспериментов позволили определить случаи, когда лучше использовать генетический алгоритм, а когда преимущество имеет модифицированный метод поиска с запретами.
