Введение 3
1 Задача маршрутизации транспорта при переменных значениях времени перехода на сети 7
1.1 Обзор литературы 7
1.2 Постановка задачи TD-MDVRP 13
1.3 Эвристические алгоритмы решения задачи MDVRP 17
1.4 Генетический алгоритм решения задачи MDVRP 20
1.5 Динамическая адаптация генетического алгоритма 28
2 Задача распределения транспортных потоков 32
2.1 Постановка задачи распределения транспортных потоков .... 32
2.2 Решение задачи распределения транспортных потоков на улично-дорожной сети г. Санкт-Петербурга 35
3 Эксперимент 38
3.1 Задача маршрутизации транспорта при переменных значениях
потоков между районами отправления и прибытия 38
3.2 Задача маршрутизации транспорта при переменных значениях
времени перехода между узлами сети 42
4 Заключение 49
Литература 51
Приложение 59
В настоящее время компании всё чаще сталкиваются с задачами разработки
прикладных моделей и методов управления цепями поставок, а так же оптимизации уже существующего аналитического аппарата. Значительную роль в
решении этих задач может играть прикладная математическая (интеллектуальная) логистика. В общем случае, логистика является наукой о планировании, организации, управлении и контроле движения материальных и информационных потоков в пространстве и во времени от их первичного источника
до конечного потребителя. Особое внимание исследователи уделяют транспортной логистике как инструменту, который позволяет при том же объёме
используемых ресурсов увеличить прибыль. Под транспортной логистикой понимают совокупность процессов погрузки-разгрузки, экспедирования и логистических операций. Транспортная логистика рассматривает задачи обеспечения технической и технологической сопряжённости участников транспортного процесса, совместного планирования производственного, транспортного и
складского процессов, а так же задачи определения рациональных маршрутов
доставки [1]. Центральное место в области транспортной логистики занимает
задача маршрутизации транспортных средств. Целью данной задачи является построение множества оптимальных маршрутов для набора транспортных
средств, расположенных в депо (на складе) и обслуживающих заданное множество клиентов. Выбор неудачного маршрута при планировании влечёт за
собой дополнительные накладные затраты.
Данная работа посвящена задаче маршрутизации транспортных средств
на сети мегаполиса. Разработанные к настоящему времени эвристические и
метаэвристические алгоритмы строят маршруты обхода клиентов, не учиты-
3вая текущую информацию о трафике. В большинстве математических моделей предполагается, что матрица временных затрат на перемещение между
узлами сети (матрица переходов) является постоянной, то есть время перехода
между каждой парой узлов неизменно в течение всего периода маршрутизации. Некоторые модели допускают зависимость времени движения на сети от
периода дня, однако выполнение данного свойства достигается приближенными методами: например, умножением матрицы переходов на коэффициент,
соответствующий периоду дня. Как результат, данная аппроксимация слабо
отражает реальную загруженность сети и может привести к решению задачи маршрутизации, которое не является оптимальным, а в некоторых постановках задач – к неявляющемуся допустимым (в случае ограничений типа
«временные окна» и других).
В данной работе была исследована задача маршрутизации транспорта с
несколькими депо (MDVRP) и задача маршрутизации транспорта с несколькими депо при переменных значениях времени перехода между узлами (TDMDVRP). Был дан подробный обзор математических моделей задачи маршуртизации транспорта на сети мегаполиса. Описывается опыт применения
данной концепции на улично-дорожных сетях городов Германии, Италии, Великобритании, США, Китая.
Была проведена классификация существующих эвристических методов
решения задач маршрутизации. Для вычислительных экспериментов был выбран и реализован на языке Java генетический алгоритм. Матрицы переходов,
соответствующие разным периодам дня, были получены двумя способами.
В первом из них алгоритмом Франка–Вульфа была решена задача нахождения равновесного по Вардропу распределения транспортных потоков
города с линейной BPR-функции задержки. Исходные данные в рассматриваемой задаче задавались модельно. Для получения действительного распределения транспортных потоков необходимо точно знать существующие матрицы корреспонденций транспорта. Второй способ использовал информацию
о трафике, полученную через сервис Яндекс.Пробки. Накопленная статистика о загруженности улично-дорожной сети содержала 2 недели наблюдений.
Матрицы переходов в обоих случаях были сформированы алгоритмом Дейкстры поиска кратчайшего пути на графе.
Для проведения вычислительных экспериментов была рассмотрена
транспортная сеть г. Санкт-Петербурга, состоящая из 109 узлов. Выбранные
узлы находились на пересечении главных улиц и магистралей города. Сгене-
49нированные случайным образом тестовые задачи для маршрутизации включали от 20 до 100 клиентов. Было проведено сравнение результатов маршрутизации согласно постановкам задач MDVRP и TD-MDVRP. Как итог, решения задачи MDVRP, полученные без учёта информации о загруженности
сети, существенно уступают во времени маршрутам TD-MDVRP, использующим её при генерации. Также наблюдается выход маршрутов движения за
горизонт планирования, т.е. имеет место опоздание транспортных средств по
сравнению со временем, запланированным перед началом движения.
Таким образом, фактор трафика в условиях загруженной уличнодорожной сети мегаполиса играет существенную роль и не должен быть проигнорирован в рамках построения маршрутных планов. При том же объёме
используемых ресурсов выбор правильной математической модели при решении задач маршрутизации позволит увеличить прибыль компании.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
