Динамическая маршрутизация транспортных средств (Dynamic VRP) и диспетчеризация в реальном времени

Сложность динамической среды измеряется так называемой Степенью динамизма (Degree of Dynamism, DoD). Она вычисляется как отношение количества запросов, поступивших в реальном времени, к общему количеству запросов за день. Если DoD равно 0, это классическая задача. Если DoD стремится к 100 процентам, мы имеем дело с чистой диспетчеризацией вслепую (такси). Кроме того, учитывается Степень срочности (Urgency) — временной зазор между моментом поступления заказа и жестким дедлайном его выполнения. Чем выше эти два показателя, тем менее эффективными становятся методы пакетной статической оптимизации.

Базовым алгоритмическим подходом к решению DVRP является Периодическая переоптимизация (Re-optimization). Система собирает новые заказы в буфер в течение определенного тайм-слота (например, 5 минут). Каждые 5 минут алгоритм замораживает текущие позиции всех курьеров (превращая их в виртуальные депо) и запускает мощный статический решатель (например, ALNS — Адаптивный поиск в больших окрестностях), чтобы за миллисекунды перестроить остатки старых маршрутов с учетом новых заказов. Курьеры получают на свои смартфоны обновленные точки назначения. Критическим ограничением здесь является недопустимость изменения маршрута к тому клиенту, к которому курьер уже физически подъезжает в данный момент.

Более продвинутым и математически глубоким подходом является Предвосхищающая маршрутизация (Anticipatory Routing) на базе Марковских процессов принятия решений (MDP) или стохастического сэмплирования. В отличие от переоптимизации, которая реагирует только на свершившиеся факты, предвосхищающие алгоритмы используют нейронные сети и исторические данные для предсказания будущего. Алгоритм знает, что с вероятностью 80% через час в бизнес-центре возникнет срочный заказ. Вместо того чтобы направлять освободившегося курьера на дешевый заказ на окраине, система искусственно придерживает его (стратегия Idling) или принудительно отправляет в зону ожидания возле бизнес-центра (Relocation Strategy), максимизируя математическое ожидание будущей корпоративной прибыли.

Вычислительной вершиной современных диспетчерских систем является Непрерывная оптимизация (Continuous Optimization). Пока курьеры едут, сервер не простаивает: он непрерывно генерирует новые столбцы (маршруты) и улучшает текущее решение в фоновом режиме, используя параллельные вычисления. Как только в систему «вбрасывается» новый онлайн-заказ, алгоритм не начинает расчет с нуля, а мгновенно проверяет возможности вставки (Insertion Heuristics) этого заказа в уже рассчитанный пул субоптимальных маршрутов. Это позволяет платформам Ride-hailing (агрегаторам такси) и сверхбыстрой доставки (q-commerce) обеспечивать подбор машины для клиента за доли секунды, доказывая, что исследование операций способно управлять стохастической городской инфраструктурой быстрее человеческой реакции.