Р. С. Рогулин

QUBO-формулировка двухэшелонной задачи маршрутизации с маршрутизацией обоих эшелонов: позиционное кодирование, валидация и вычислительный эксперимент

Предложена формулировка двухэшелонной задачи маршрутизации транспорта в форме квадратичной бинарной оптимизации без ограничений (QUBO), в которой маршрутизируются оба эшелона. Порядок обслуживания потребителей задан позиционным кодированием, что делает все слагаемые квадратичными и устраняет блок переменных Маккормика, составлявший в прежних постановках до 87 % размерности. Корректность подтверждена совпадением энергии QUBO с независимо вычисленной стоимостью. На макрорегиональном инстансе (65 потребителей, 8 узлов консолидации) показано, что широко используемая маятниковая аппроксимация второго эшелона завышает его стоимость в 2,7 раза, а планирование по ней увеличивает фактические затраты на 15,9 %.

КЛЮЧЕВЫЕ СЛОВА: двухэшелонная маршрутизация, QUBO, позиционное кодирование, квадратизация, лесопромышленная логистика.