Algorithm and software development to allocate locomotives for transportation of freight trains

Предлагается математическая модель назначения локомотивов для перевозки грузовых составов. Целью оптимизации в модели является минимизация числа задействованных для перевозки составов локомотивов за счёт выбора маршрутов составов и локомотивов. Предполагается, что составы могут перевозиться в определённые промежутки времени, которые называются нитками, для каждого локомотива установлены допустимые варианты передвижения, называемые плечами. Учитывается необходимость периодического проведения технического осмотра локомотивов. Для формулировки задачи используется аппарат теории графов и целочисленной оптимизации. Формализуются железнодорожные понятия плеча, нитки, рейса состава и маршрута оборота локомотива. Предлагается эвристический алгоритм поиска приближённого решения задачи. Основной идеей предлагаемого алгоритма является максимальное использование локомотивов с ранним началом движения. Алгоритм состоит из трех этапов, на каждом из которых улучшается предыдущее найденное решение. Улучшение решения осуществляется за счет перегонок локомотивов. Приводится описание разработанных программных средств для оптимизации данной модели. Проведены численные эксперименты на примере исторических данных Московской железной дороги.