Введение 4
Постановка задачи 6
Глава 1. Краткий обзор задач маршрутизации с вывозом и доставкой товаров 7
§1.1. Задача маршрутизации 1-1 вывоза и доставки товаров 8
§1.2. Задача маршрутизации 1-M-1 вывоза и доставки товаров 9
§1.3. Задача маршрутизации M-M вывоза и доставки товаров 10
§1.4. Основные виды задачи 1-1 VRPPD 11
§1.5. Математическая постановка задачи 1-1 доставки и вывоза товаров с временными окнами 12
Глава 2. Муравьиный алгоритм в задачах маршрутизации автотранспорта с вывозом и доставкой товаров 18
§2.1. Разновидности алгоритмов для решения задачи маршрутизации с вывозом и доставкой товаров 18
§2.2. Биологическая интерпретация алгоритма муравьиной колонии 20
§2.3. Классический алгоритм муравьиной колонии при решении задачи коммивояжера 23
§2.4. Алгоритм муравьиной колонии для решения задачи 1-1 VRPPDTW 27
Глава 3. Решение задачи маршрутизации 1-1 доставки и вывоза товаров с одним транспортным средством 34
§3.1. Практическая постановка задачи 1-1 маршрутизации 34
§3.2. Математическая формулировка 35
§3.3. Решение задачи маршрутизации 1-1 доставки и вывоза товаров с одним транспортным средством и временными окнами с помощью муравьиного алгоритма 37
Выводы 42
Заключение 43
Список литературы 44
Приложение 52
Проблема маршрутизации транспорта (Vehicle Routing Problem — VRP) является одним из классов задач логистики. Целью решения VRP является построение маршрутов для одного или нескольких транспортных средств, которые будут считаться оптимальными по отношению к заданным критериям.
Впервые проблема маршрутизации была сформулирована Г. Дангицом и Дж. Рамсером в 1959 году как обобщенный случай задачи коммивояжера. Тогда ее постановка заключалась в поиске оптимального маршрута, по которому конкретно заданное количество однородных товаров должно было быть доставлено со склада заказчикам с использованием транспортных средств одинаковой грузоподъемности. Предполагалось, что стоимость транспортировки определяется только общим числом пройденного пути и не зависит от стоимости самого груза; также все транспортные средства должны были вернуться на склад.
В настоящее время вопрос оптимизации транспортной логистики является очень важным для большинства предприятий. От решения этой задачи напрямую зависит цена на товар, а в некоторых областях рынка расходы на доставку товара соизмеримы с его стоимостью. При правильной организации транспортировки можно существенно уменьшить экономические затраты. Именно поэтому сейчас стало важным иметь автоматизированное оптимальное решение данной проблемы.
В данной работе будет представлен алгоритм, решающий одну из постановок задачи маршрутизации автотранспорта.
В ходе научно-исследовательской работы была изучена литература по предметной области. Были рассмотрены различные виды задачи маршрутизации, множество методов их решения. Был полностью освоен принцип работы метаэвристических алгоритмов в NP-полных задачах. С помощью таких программных продуктов как MATLAB R2013b было реализовано три разновидности муравьиного алгоритма, результаты работы которых были впоследствии сравнены между собой. Получены таблицы, хранящие в себе среднее время работы алгоритмов, их лучшие и усредненные ответы. Уменьшена вычислительная стоимость одного из алгоритмов.
