Двухэшелонная модель транспортной системы и муравьиный алгоритм: анализ масштабируемости вычислительных решений

В статье рассматривается двухэшелонная модель транспортной системы, предназначенная для описания и анализа распределительных логистических процессов с промежуточными хабами и конечными потребителями. Модель учитывает совместную оптимизацию маршрутов магистрального уровня и маршрутов распределения при наличии ограничений по вместимости транспортных средств и требований по удовлетворению спроса. Рассматриваемая задача относится к классу NP-трудных, что существенно ограничивает применение точных методов оптимизации при росте размерности транспортного графа. Для решения предложенной модели используется двухэшелонная модификация алгоритма муравьиной колонии (2E-ACO), в которой процессы формирования решений для первого и второго эшелонов формализованы раздельно, но согласованы через единую целевую функцию, включающую транспортные затраты и штрафы за необслуженный спрос. Основное внимание в работе уделено вычислительному эксперименту, направленному на анализ масштабируемости и устойчивости алгоритма при увеличении мощности множества потребителей, числа хабов и сложности транспортной инфраструктуры. Эксперименты проводятся в режиме масштабируемых ресурсов, что позволяет отделить влияние алгоритмических решений от эффектов ресурсных ограничений. Для оценки воспроизводимости используются многократные независимые запуски с фиксированными силами генератора случайных чисел. Полученные результаты демонстрируют предсказуемый рост вычислительных затрат при увеличении размерности модели и устойчивость качества решений. Сравнение с намеренно простой базовой жадной эвристикой, используемой в качестве нижней оценки качества решений, показывает, что алгоритм 2E-ACO обеспечивает сопоставимый уровень обслуживания спроса при более высоких вычислительных затратах, обусловленных итерационным характером поиска. Представленные результаты подтверждают применимость предложенной модели и алгоритма для исследования крупномасштабных двухэшелонных транспортных систем.