Задача динамической маршрутизации транспортного средства (ЗДМТС)

В целом ЗМТС решается статически, в обстоятельствах, где вся информация известна заранее и остается актуальной с течением времени. Однако на практике бывает, что одна или несколько непредвиденных случайностей могут нарушить ранее установленный маршрут. В таком случае задача должна решаться в режиме реального времени. Это и есть задача динамической маршрутизации транспортного средства (ЗДМТС) [DAN 59].

В [LAR 00] Ларсен обозначил ЗДМТС как статический вариант ЗМТС, отличающийся в силу следующих особенностей:

  • — информация о планировании маршрута не полностью известна планировщику в момент начала процесса планирования. Другими словами, некоторые из данных задачи являются зависимыми от времени. Новые запросы могут поступать в течение рабочего дня, и они должны быть включены в существующее расписание;
  • — некоторые события могут нарушить существующий план и должны быть рассмотрены, чтобы дать лучший ответ в соответствии с новым контекстом.

Очевидно, что такая задача динамической маршрутизации транспортного средства гораздо сложнее, чем статическая задача. Если класс проблем ЗМТС обозначим как Р(ЗМТС), а класс проблем ЗДМТС как Р(ЗДМТС), тогда Р(ЗМТС) п Р(ЗДМТС). Поскольку проблема статического ЗМТС является НП-полной задачей, то есть для нее невозможно найти оптимального решения в разумные сроки расчета, то проблема динамической маршрутизации транспортного средства ЗДМТС также принадлежит к классу НП-полных задач. Их можно обобщить путем поиска решений для каждого отрезка времени частично статической ЗМТС. На рисунке 4.1 мы имеем простой пример динамической ЗМТС, где два средства должны обслужить набор клиентов.

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

Рисунок 4.1. Задача динамической маршрутизации транспортных средств

Статические клиенты представлены белыми узлами, в то время как динамические клиенты (т.е. новые клиенты) представлены черными узлами. Дуги обозначают запланированный маршрут для каждого транспортного средства. Новые клиенты должны быть добавлены в уже запланированные маршруты. Новые маршрутные сегменты показаны в виде пунктирной линии.

В отличие от задачи статической маршрутизации транспортных средств, динамическое управление зависит не только от количества и пространственного распределения прошлых клиентов, но и от количества внезапных (динамических) событий и случаев, в тот момент, когда эти события происходят. Мерой для описания динамики системы является степень динамизма (dod). Она описывается следующим образом [LAR00]:

Задачу статической маршрутизации можно отличить по dod, равному нулю, в то время как у динамических задач dod равно 1.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >