Main menu

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

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

Подробнее

Соц. сети