
Тип работы:	Предмет:	Язык работы:

Задача маршрутизации вывоза и доставки товара с несколькими транспортными средствами

Работа №	129749
Тип работы	Бакалаврская работа
Предмет	математика
Объем работы	51
Год сдачи	2019
Стоимость	4700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	67

Не подходит работа?

Узнай цену на написание

Содержание

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

Литература

1. Dantzig G. B., Ramser J. H. The Truck Dispatching Problem // Management Science. 1959. Vol. 6, No 1. P. 80-91.
2. Berbeglia G., Cordeau J., Laporte G. Dynamic pickup and delivery problems // European journal of operational research. 2010. No 202. P. 8-15.
3. Berbeglia G., Cordeau J., Gribkovskaia I., Laporte G. Static pickup and delivery problems: classification scheme and survey // Springer. 2007. No 15. P. 1-31.
4. Psaraftis Harilaos N. Analysis of an O(N2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem // Transpn Res.-B. 1983. Vol. 17B, No 2. P. 133-145.
5. Harilaos N. A dynamic programming solution to the single vehicle many-to- many immediate request dial-a-ride problem // Transportation science. 1980. Vol. 14. No. 2. P. 385-392.
6. Gribkovskaia I., Laporte G. One-to-one Single Vehicle Pickup and
Delivery Problems // Single Vehicle Pickup and Delivery Problems. 2008. P. 359-377.
7. Cordeau J., Laporte G., Ropke S. Recent Models and Algorithms for One-to- One Pickup and Delivery Problems // The vehicle routing problem: latest advances and new challenges. 2008 P. 329-359
8. Hernandez-Perez H., Salazar-Gonzalez J. The multi-commodity one-to-one pickup-and-delivery traveling salesmen problem // European journal of operation research. 2009. Vol. 196. P. 987-995.
9. Anily S, Hassin The swapping problem // Networks. 1992. No. 22. P. 419433.
10. Gribkovskaia I., Laporte G., Shlopak A. A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms // Journal of the operational research society. 2008. No 59. P. 1449-1459.
11. Cordeau J., Laporte G. A tabu search heuristic for the static multi-vehicle
dial-a-ride problem // Transportation research. 2003. Part B. Vol. 37. P.579594.
12. Powell W.B., Bouzanene-Ayari B., Simpo H.P. Dynamic models for freight transportation // Handbooks in operation research and management science: transportation. 2007. Vol. 14. P.285-365.
13. Abdulkader M., Gajpal Y., ElMekkawy T. Hybridized ant colony algorithm for the Multi Compartment Vehicle // Applied Soft Computing. 2015. No 37. P. 196-203.
14. Grandinetti L., Guerrieo F., Pezzella F., Pisacane O. The multi-objective multi-vehicle pickups and delivery problem with time windows // Procedia- social and behavioral sciences. 2014. Vol. 111. P. 203-212.
15. Nagy G., Salhi S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries // European Journal of Operational Research. 2005. Vol. 162. No. 1. P. 126-141.
16. Dror M., Laporte G., Trudeau P. Vehicle routing with split deliveries // Discrete applied mathematics. 1994. Vol. 50. No. 3. P.239-254.
17. Vidal T., Crainic T.C., Gendreau M. A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems // Operations Research. 2012. Vol. 60. No. 3. P. 721-738.
... Всего источников – 32.