Алгоритм ветвей и цен (Branch and Price): генерация столбцов в целочисленной маршрутизации

Архитектура алгоритма ветвей и цен строится на строгой декомпозиции Данцига-Вулфа. Глобальная проблема разбивается на две независимые части. Мастер-задача (Master Problem) формулируется как задача о покрытии множества: мы должны выбрать из пула доступных маршрутов такой набор, который обслужит абсолютно всех клиентов при минимальных общих затратах. Переменными в мастер-задаче являются сами маршруты. Поскольку загрузить в решатель миллиард столбцов-маршрутов невозможно, мастер-задача изначально инициализируется крошечным, искусственным набором базовых путей (ограниченная мастер-задача). Решив ее симплекс-методом, алгоритм получает двойственные оценки (теневые цены) для каждого клиента, которые сигнализируют о том, насколько экономически выгодно включить данного клиента в новый маршрут.

Вторая часть системы — это Вспомогательная задача (Pricing Problem, или задача ценообразования). Вспомогательная задача принимает теневые цены от мастер-задачи и пытается сгенерировать хотя бы один новый, математически допустимый маршрут, приведенная стоимость (Reduced Cost) которого меньше нуля. Для задач маршрутизации эта вспомогательная проблема формулируется как поиск кратчайшего пути с ресурсными ограничениями на графе (Elementary Shortest Path Problem with Resource Constraints, ESPPRC). Используя алгоритмы динамического программирования, программа ищет путь по карте, строго соблюдая вместимость грузовика и временные окна клиентов. Если найден маршрут с отрицательной приведенной стоимостью, он оформляется как новый столбец и импортируется обратно в мастер-задачу. Этот цикл продолжается до тех пор, пока вспомогательная задача не сообщит, что улучшающих маршрутов в природе больше не существует.

Проблема заключается в том, что описанный процесс (генерация столбцов) решает только непрерывную задачу. Ответ мастер-задачи может оказаться дробным: алгоритм предложит отправить грузовик по маршруту номер один с вероятностью 0.5 и по маршруту номер два с вероятностью 0.5. В реальном мире грузовики не делятся пополам. Чтобы заставить решение стать строго целочисленным, генерация столбцов интегрируется в дерево метода ветвей и границ (Branch and Bound). Как только непрерывный оптимум становится дробным, алгоритм разделяет задачу на две ветви. Например, в одной ветви жестко запрещается проезд грузовика по дороге между клиентами А и Б, а в другой ветви этот проезд делается строго обязательным.

Вычислительная магия Branch and Price кроется в правильном выборе стратегии ветвления. Если ветвить напрямую по дробным переменным-маршрутам, структура вспомогательной задачи (поиска кратчайшего пути) разрушится. Поэтому аналитики применяют ветвление Райана-Фостера или ветвление по ребрам графа, которое легко транслируется в изменения матрицы весов для алгоритма Дейкстры. Совмещение генерации столбцов на каждом узле дерева поиска позволяет сверхмощным коммерческим решателям находить абсолютно точные, математически доказанные оптимумы для логистических сетей национального масштаба, экономя транснациональным корпорациям миллионы галлонов топлива и устраняя хаос из расписаний крупнейших мировых авиаперевозчиков.