В отличие от классического определения проблемы маршрутов транспортных средств, реальные приложения часто включают два важных аспекта: эволюцию и качество информации. Эволюция информации связана с тем, что в некоторых случаях информация, доступная планировщику, может меняться в процессе выполнения маршрутов, например, с приходом новых запросов клиентов.
Качество информации отражает возможную неопределенность в отношении имеющихся данных, например, когда спрос клиента известен только как диапазон оценки его реального спроса. Кроме того, в зависимости от проблемы и имеющихся технологий, маршруты движения транспорта могут быть спроектированы как статически (априори), так и динамически.
Например, ПДРД с стохастическим спросом (ПДРДР) можно рассматривать с обеих точек зрения. С статической точки зрения, задача состоит в том, чтобы спроектировать набор надежных маршрутов априори, которые претерпят незначительные изменения в ходе их выполнения .
С динамической точки зрения, проблема заключается в проектировании маршрутов транспорта в режиме онлайн, сообщая транспортное средство, которое клиент будет обслуживать следующим, как только оно перестанет работать. Исходя из этих параметров, определены четыре категории проблем с маршрутизацией.
Статические и стохастические задачи
Статические и стохастические задачи характеризуются вводом, частично известным как случайные величины, реализация которых выявляется только во время выполнения маршрутов.
Дополнительно предполагается, что маршруты проектируются априори, и только незначительные изменения допускаются после этого. Например, допустимые изменения включают в себя планирование поездки обратно на склад или пропуск клиента. Приложения в этой категории не требуют никакой технической поддержки. Неопределенность может повлиять на входные данные, но наиболее изученными примерами являются:
- стохастические клиенты, когда клиент нуждается в обслуживании с определенной вероятностью.
- стохастические времена, когда время обслуживания или время в пути моделируются случайными переменными.
- стохастические требования.
В динамических и детерминированных проблемах часть или все входные данные неизвестны и динамически раскрываются во время проектирования или выполнения маршрутов.
Для решения этих проблем маршруты движения транспорта постоянно пересматриваются, что требует технологической поддержки для обеспечения связи между транспортными средствами и директивным органом в режиме реального времени (например, мобильные телефоны и системы глобального позиционирования).
Аналогичным образом, динамические и стохастические проблемы частично или полностью неизвестны и динамически раскрываются при прокладке маршрутов, но в отличие от последней категории, эксплуатационные стохастические знания доступны на динамически раскрываемой информации. Как и прежде, маршруты движения транспортных средств можно постоянно пересматривать с помощью технологической поддержки.
Помимо проблем с динамической маршрутизацией, когда посещения клиентов должны быть четко упорядочены по маршрутам, существуют и другие проблемы, связанные с диспетчеризацией транспортных средств, такие как, управление парком аварийных транспортных средств или так называемые проблемы динамического распределения в области грузовых автоперевозок на дальние расстояния.
Динамические проблемы с маршрутизацией автомобиля
Первое упоминание по вопросу маршрутизации транспортного средства относится к Уилсону и Колвину . Они изучили единственный автомобиль DARP, в котором запросы клиентов - это поездки из пункта отправления в пункт назначения, которые появляются динамически.
Их подход использует эвристику вставки, способную хорошо работать с небольшими вычислительными усилиями.
Позднее ввели концепцию немедленного запроса: клиент, запрашивающий обслуживание, всегда хочет получить его как можно раньше, что требует немедленного перепланировки маршрута движения автомобиля.
Ряд технологических достижений привел к увеличению числа приложений маршрутизации в режиме реального времени. С внедрением в 1996 году Глобальной системы позиционирования (GPS), разработкой и широким использованием мобильных и смартфонов в сочетании с точными географическими информационными системами (ГИС) компании теперь могут эффективно отслеживать и управлять своим автопарком в режиме реального времени и с минимальными затратами.
Хотя традиционно это двухэтапный процесс (т.е. план-выполнение), теперь маршрутизация транспортных средств может осуществляться динамически, создавая дополнительные возможности для снижения эксплуатационных расходов, улучшения обслуживания клиентов и снижения воздействия на окружающую среду.
Наиболее распространенным источником динамизма в маршрутизации транспортных средств является онлайн-прибытие заявок клиентов во время операции. Точнее, запросы могут быть запросами на товары или услуги. Время в пути, являющееся динамическим компонентом большинства реальных приложений, было недавно учтено, хотя служебное время не было изучено (но может быть добавлено ко времени в пути).
Наконец, в некоторых недавних работах рассматриваются динамично растущие требования к комплексу известных заказчиков и доступности транспортных средств , в этом случае источником динамизма является возможная поломка транспортных средств.
Перед тем как транспортное средство покинет склад (время t0), по первоначальному маршруту планируется посетить известные в настоящее время пункты (A, B, C, D, E). Во время выполнения маршрута в момент t1 появляются два новых запроса (X и Y ), и первоначальный маршрут корректируется для их выполнения. Наконец, в момент времени tf выполняется маршрут (A, B, C, D, Y, E, X).
Этот пример показывает, как динамическая маршрутизация непрерывно регулирует маршруты, что требует коммуникации в режиме реального времени между транспортными средствами и диспетчерским центром.
Схема связи в реальном времени, где среда относится к реальному миру, в то время как диспетчер является агентом, который дает инструкции транспортному средству. Как только транспортное средство будет готово, диспетчер принимает решение и инструктирует транспортное средство для выполнения запроса А.
Когда транспорт начинает и заканчивает обслуживание по запросу А, оно уведомляет диспетчера, который в свою очередь обновляет имеющуюся информацию и сообщает транспортное средство о своем последующем запросе.