Перевозка людей в целом - и во многих аспектах - аналогична перевозке грузов, однако она характеризуется дополнительными ограничениями, такими как регулирование ожиданий, поездок и времени обслуживания.
Такси, пожалуй, являются наиболее распространенными индивидуальными транспортными системами по требованию. Запросы содержат информацию о месте и времени получения, возможно, в сочетании с пунктом назначения.
Они могут быть известны заранее, например, когда клиент заказывает такси на следующий день, или они могут приехать динамически, в этом случае такси должно быть отправлено в кратчайшие сроки.
Когда клиенты не могут пользоваться транспортным средством совместно, бесплатное такси, как правило, находится в непосредственной близости, что оставляет ограниченное пространство для оптимизации.
Исследование Карамия посвящено многокабинной городской транспортной системе, в которой такси может перевозить более одного пассажира одновременно.
При этом он-лайн алгоритмы минимизируют общее пройденное расстояние, при назначении заявок на транспортные средства и расчете маршрутов такси. Эта многокабинная транспортная система может быть обобщена как транспортная система "по требованию" или "от двери до двери".
Многие области применения включают транспортировку детей, пожилых людей, инвалидов или пациентов из дома в школу, на работу или в медицинские центры.
Также были изучены ГПНР с изменяющейся скоростью движения, поломками транспортных средств и пробками изучали транспортные системы с учетом спроса.
Отдельное применение транспортных систем по требованию можно найти в крупных больницах, где услуги могут быть распределены по различным зданиям в нескольких филиалах.
В зависимости от медицинских процедур или возможностей учреждения, пациенту может потребоваться срочный перевод из одной службы в другую, что может потребовать наличия квалифицированного персонала или специального оборудования для его или ее ухода.
Воздушное такси
Воздушное такси разработано как гибкий ответ на ограничения традиционных авиакомпаний.
Воздушное такси предлагает пассажирам возможность путешествовать через небольшие аэропорты, избегая очередей на регистрацию и проверки безопасности.
Таксомоторные компании предлагают услугу по запросу: клиенты бронируют авиабилеты за несколько дней до вылета, уточняя, готовы ли они воспользоваться самолётом, остановиться в промежуточном аэропорту или имеют гибкий график полёта.
Затем компания удовлетворяет эти запросы, стараясь консолидировать полеты, когда это возможно.
Аналогичные проблемы возникают и в системах транспортировки вертолетов, обычно используемых нефтегазовыми компаниями для перевозки персонала между морскими нефтяными платформами.
Методы решения
Динамические и детерминированные проблемы маршрутизации
Подходы, которые были успешно применены к динамической маршрутизации в условиях отсутствия стохастической информации.
Информация раскрывается с течением времени, т.е. вся инстанция становится известной только в конце периода планирования.
Как следствие, точные методы обеспечивают оптимальное решение только для текущего состояния, но не гарантируют, что решение будет оставаться оптимальным, как только появятся новые данные.
Поэтому большинство динамических подходов основывается на эвристике, которая быстро рассчитывает решение текущей проблемы.
Подходы к динамическим и детерминированным проблемам маршрутизации транспортных средств можно разделить на две категории: подходы, основанные на периодической повторной оптимизации и подходы, основанные на непрерывной повторной оптимизации.
Периодическая оптимизация
Насколько известно, первый подход к периодической оптимизации связан, с разработкой динамического подхода к программированию. Исследования сосредоточены на ГПНР и заключаются в поиске оптимального маршрута каждый раз, когда появляется новый запрос.
В более общем плане, периодическая оптимизация начинается в начале дня с первой оптимизации, в результате которой создается начальный набор маршрутов.
Затем процедура оптимизации периодически решает статическую задачу, соответствующую текущему состоянию, либо при каждом изменении имеющихся данных, либо через фиксированные промежутки времени, называемые эпохами решения или временными срезами.
Периодическая оптимизация имеет то преимущество, что она может быть основана на алгоритмах, разработанных для статической маршрутизации, для которой были проведены обширные исследования.
Основным недостатком является то, что перед обновлением плана маршрутизации необходимо выполнить всю оптимизацию, что увеличивает задержки для диспетчера.