Задача маршрутизации с разделенной доставкой (SDVRP): математическая оптимизация загрузки флота

Математическая модель SDVRP разрешает одному клиенту принимать несколько грузовиков. Таким образом, заказ клиента может быть разделен на любые произвольные доли. Это кардинально меняет пространство поиска решений. Во-первых, количество посещений клиента перестает быть бинарной переменной (0 или 1) и становится целочисленной переменной, зависящей от объемов разделения. Во-вторых, алгебраическая структура задачи теряет свойства простого графа, так как маршруты теперь могут пересекаться не только в депо, но и на узлах клиентов, образуя сложнейшие переплетающиеся транспортные циклы. Несмотря на кажущееся увеличение сложности, разрешение разделять доставку парадоксальным образом иногда упрощает упаковку грузов (преодолевая жесткость задачи о рюкзаке).

Строгий математический анализ SDVRP, проведенный Моше Дрором и Пьером Трюдо в 1989 году, доказал несколько контринтуитивных, но фундаментальных теорем. Во-первых, если функция транспортных издержек удовлетворяет правилу треугольника (прямой путь всегда короче объездного), то в оптимальном решении никакие два маршрута не могут иметь более одного общего клиента. Во-вторых, существует хотя бы одно оптимальное решение, в котором не существует ни одного k-цикла разделенных доставок (ситуации, когда клиенты передают друг другу доли поставок по замкнутому кругу). Эти топологические свойства позволили исследователям операций разработать мощные отсекающие плоскости для методов целочисленного программирования (Branch-and-Cut), существенно сужая гигантское пространство поиска.

Главный экономический эффект от применения SDVRP заключается в повышении коэффициента использования грузовместимости. В классической модели CVRP грузовики часто возвращаются в депо полупустыми, так как оставшееся место в кузове меньше объема заказа следующего по пути клиента. Разделенная доставка позволяет «досыпать» кузов до 100 процентов мелкими частями заказов других клиентов по пути следования, что радикально сокращает общее количество требуемых автомобилей в автопарке и суммарный пробег. Исследования доказывают, что экономия от применения SDVRP может достигать 50 процентов в случаях, когда средний размер заказа клиента немного превышает половину вместимости стандартного грузовика.

Для практического применения на сотнях клиентов используются передовые эвристические алгоритмы. Метод локального поиска с двумя фазами (Two-Phase Local Search) сначала строит гигантские нелегальные маршруты (игнорируя вместимость машин), а затем алгоритм динамического программирования оптимально «разрезает» эти маршруты на легальные куски, автоматически создавая разделенные доставки на стыках. Этот алгоритм стал абсолютным стандартом для дистрибуции топлива на автозаправочные станции (где бензовозы могут сливать топливо по частям в разные резервуары) и для оптимизации вывоза твердых бытовых отходов, обеспечивая бесперебойную экологическую и энергетическую безопасность современных агломераций.