Постановка оптимизационной задачи маршрутизации автотранспорта на транспортной сети

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

ПОСТАНОВКА ОПТИМИЗАЦИОННОЙ ЗАДАЧИ МАРШРУТИЗАЦИИ АВТОТРАНСПОРТА НА ТРАНСПОРТНОЙ СЕТИ
© Алпатов А. Н. *
Московский государственный университет приборостроения и информатики, г. Москва
В данной статье рассматривается постановка обобщённой задачи маршрутизации автотранспорта, показаны возможности применения такого типа задач на практике, рассмотрены основные разновидности задачи, рассмотрены основные подходы для решения задачи маршрутизации автотранспорта.
Ключевые слова: задача маршрутизации автотранспорта, VRP, автотранспорт, генетический алгоритм.
Проблема маршрутизации автотранспорта (Vehicle Routing Problems, VRP) является фундаментальной проблемой в области задач комбинаторной оптимизации с широким спектром применения в практике. Маршрутизация автотранспорта образует ядро планирования логистики предприятий, связанных непосредственно с грузоперевозками и доставкой товара конечным потребителям и, следовательно, представляет большой практический и теоретический интерес. Разработка и внедрение новых эффективных методов решения задач маршрутизации транспортных потоков обеспечивает автотранспортным предприятиям возможность уменьшения расходов, повышения качества обслуживания, сокращение времени ожидания транспортных средств и т. п. Задача маршрутизации автотранспорта впервые была сформулирована в 1959 году Джорджем Данцигом и Джоном Рамсером[1], но наибольшее развитие она получила в последние 10 лет. Маршрутизация автотранспорта находит своё применение во многих областях производства, таких как:
— доставка и приём почтовых отправлений-
— доставка различных материалов и оборудования предприятиям-
— доставка товаров клиентам магазинов-
— сбор мусора с улиц-
— маршрутизация автобусного сообщения.
Задача маршрутизации транспорта является комбинаторной задачей. Данная задача может быть представлена в виде графа G (V, E) [2]:
* Аспирант кафедры «Персональные компьютеры и сети» (ИТ-4).
76
ПЕРСПЕКТИВЫ РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
V = У уь …, Уи},
где Уо — депо-
VI.и — заказчики-
А — множество ребер {(у, V,) | V, V, — 6 V- г Ф-}-
С — матрица неотрицательных расстояний (стоимости пути) с, между заказчиками и V, — Яг — маршрут г-й машины (г = 1. т) — т — число транспортных средств-
Рис. 1. Пример решения задачи маршрутизации
Главная цель решения задачи маршрутизации автотранспорта заключается в минимизации затрат на проведение необходимых работ, связанных с доставкой товара, не нарушая ограничений, которые могут быть наложены (например, доставка должна быть сделана между 2 и 3 часами дня).
Задача маршрутизации автотранспорта является совокупностью двух задач:
1. Задача коммивояжера: задача маршрутизации автотранспорта приводится к решению задачи коммивояжера, если принять грузоподъемность автотранспортного средства бесконечной (достаточной).
2. Задача о ранце (рюкзаке): задача маршрутизации автотранспорта приводится к решению задачи о ранце, если принять расстояния между точками маршрута равными 0, либо постоянной величиной, то есть все подходящие решения будут одинаково эффективны.
Существует достаточно большое количество задач маршрутизации автотранспорта, которые отличаются друг от друга учётом тех или иных характеристик узлов, транспортных средств, а также введением дополнительных ограничений. Наличие различных ограничений зачастую определяется типом задач.
Информационные технологии в системе управления предприятием
77
Основные разновидности VRP:
— задача маршрутизации транспортных средств с подбором на маршруте-
— задача маршрутизации транспортных средств с ограничением по грузоподъемности транспортного средства-
— маршрутизация со случайными (стохастическими) компонентами-
— маршрутизация с использованием при доставке различного по конфигурации транспорта-
Наиболее распространенными методами решения задачи маршрутизации, являются эвристические методы и мета-эвристические [3]. Применение точных методов при решении задач позволяет получать точные решения, но их применение ограниченно, прежде всего тем, что точные методы решения задач при большом количестве входных данных, не дают точное решение за приемлемое время.
Основным является подход к решению задачи VRP, при котором решение строится два этапа: сначала генерируется первоначальное решение, а потом это решение улучшается методом обмена вершин [1]. К данным алгоритмам относятся:
— поиск с исключениями-
— детерминированный отжиг-
— алгоритм на основе муравьиных колоний-
— пчелиные алгоритмы-
— генетические алгоритмы.
Большинство публикаций по данному вопросу не уделяет внимание на первоначальное решение, а концентрирует внимание на этап улучшения. Но от первоначального результата, который получен при первом приближенном решении, зависит и общий результат.
В заключение, можно сказать, что на сегодняшний момент не существует алгоритма решения задачи маршрутизации, который давал бы точное решение при минимальных затратах времени. Также стоит отметить, что построить математическую модель для решения задачи довольно сложно, так как необходимо учесть всё многообразие условий перевозки.
Список литературы:
1. Guido Perboli, Roberto Tadei, Daniele Vigo: The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics // Transportation Science. — 2011. — № 45(3). — P. 364−380.
2. Vehicle Routing Problems [Электронный ресурс]. — Режим доступа: http: //neo. lcc. uma. es/vrp (дата обращения: 15. 09. 2013).
3. Задача маршрутизации транспорта [Электронный ресурс]. — Режим доступа: http: //rain. ifmo. ru/cat/view. php/theory/unsorted/vrp-2006 (дата обращения 15. 09. 2013).

Показать Свернуть
Заполнить форму текущей работой