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

Ключевые слова:
железнодорожный транспорт, расписание, локомотив, планирование, выполнение заказов, состояние, алгоритм склеивания вершин
Текст
Текст произведения (PDF): Читать Скачать

Введение

Функционирование железнодорожного транспорта горнодобывающих компаний непосредственно влияет на объем и непрерывность поставок полезных ископаемых. Сложность задачи оптимизации планирования загрузки железнодорожного транспорта зависит от размера железнодорожной сети, ее замкнутости, направлений перевозки грузов, наличия большого парка железнодорожного транспорта, необходимости перевозки различных типов материалов и пр. Инженерия управления в настоящее время является зрелой дисциплиной, однако она остается областью, в которой ведется большая исследовательская деятельность [1]. Оптимизация загрузки железнодорожного транспорта позволяет сократить издержки на перевозку грузов, создать резервы пропускной способности, доставлять грузы в установленные сроки, что повышает эффективность функционирования железнодорожной сети [2].

В отрасли железнодорожного планирования разрабатываются, внедряются и совершенствуются различные автоматизированные системы, например системы автоматизации диспетчерских центров управления перевозками, наращиваются возможности сети информационно-вычислительных центров [3]. Все это направлено на повышение эффективности использования парка железнодорожного транспорта, что влияет на объем и непрерывность поставок продукции. Задачи составления расписаний, решаемые в диспетчерских центрах, относят к категории NP-полных, для которых решение может быть получено полным перебором, но время, необходимое для этого, полиномиально зависит от объема исходных данных [4, 5]. Поэтому актуальным является поиск альтернативных методов решения задачи планирования работы железнодорожного транспорта, повышающих эффективность с точки зрения снижения трудоемкости, сокращения используемых вычислительных ресурсов.

В работе приведены две постановки задачи, первая включает проблему составления расписания для нескольких локомотивов одного типа, вторая – для локомотивов разных типов, а также алгоритм решения таких задач и его применение к частному случаю.

 

Постановка задачи с локомотивами одного типа

В работах [6, 7] представлены постановка задачи составления расписания и ее решение для случая, когда работу по перевозке грузов осуществляет один локомотив. В данной работе приведено развитие такой постановки задачи, в частности в этом пункте рассмотрен вариант составления расписания для нескольких локомотивов с одинаковыми характеристиками.

Введем следующие обозначения:

h – номер локомотива, h = 1, …, m, где m – общее количество локомотивов; – n – общее количество станций; –  – момент времени в расписании локомотива h;

 – станция расположения локомотива h;

  – вектор, каждый элемент которого    показывает количество доставленных локомотивом h заказов с i-й станции отправления на j-ю станцию назначения;

  – состояние локомотива h в соответствующий момент времени.

Количество груза – заказы, которые необходимо перевезти с i-й станции в j-ю, появляются в определенные моменты времени на станциях отправления и не могут быть выполнены заранее. Необходимо составить расписание движения локомотивов, которое позволит обеспечить выполнение всех заказов. Расписание задается состоянием локомотивов в каждый момент времени.

Целевой функцией для данной постановки задачи является суммарное время выполнения заказов всеми локомотивами в момент завершения выполнения всех заказов:

             (1)

Следует отметить, что в данном разделе рассматривается решение задачи с несколькими локомотивами одного типа. При этом состояние парка локомотивов перестает быть вектором [7] и становится матрицей, где h-я строка является состоянием h-го локомотива. В связи с тем, что рассматриваются локомотивы одного типа, будем считать состояния, включающие одинаковый набор строк, идентичными, как на рис. 1, и их также будем «склеивать».

Рис. 1. Пример одинаковых состояний локомотивов

Fig. 1. Example of similar locomotive states

 

Здесь состояния имеют формат (s, t, k12, k13, k23).

В работе [6] представлен алгоритм склеивания вершин для решения задачи формирования составов и расписания их движения для одного локомотива. В настоящей работе представлено развитие этого алгоритма для случая с несколькими локомотивами одного типа, а также с несколькими локомотивами разных типов. Далее представлен сам алгоритм и пример его использования.

 

Алгоритм решения задачи планирования оптимальной загрузки нескольких локомотивов одного типа

Дерево состояний строится перебором различных вариантов движения локомотивов. В каждый момент времени с учетом ограничений [6] локомотив может находиться в одном из четырех состояний. Если локомотив перевозит заказ со станции отправления на станцию назначения, то он находится в состоянии «доставка». Если локомотив находится на станции, не выполняя никаких заказов, то он находится в состоянии «ожидание». Несколько ожиданий подряд допустимо. Если локомотив движется с одной станции на другую, при этом не перевозя грузов, то он находится в состоянии «холостой ход». Два и более холостых ходов подряд недопустимы. Если локомотив не функционирует, его состояние – «простой».

В результате перебора всех возможных состояний размерность дерева сильно увеличивается, поэтому для его уменьшения используется следующий алгоритм склеивания вершин.

1. Добавляем новое состояние в дерево и фиксируем его как матрицу Sj, каждая строка которой является состоянием отдельного локомотива.

2. Ищем среди построенных состояний такое,
у которого набор строк совпадает с набором строк матрицы Sj, а именно сравниваем их построчно. Таким образом, для любой k-й строки в матрице
Sj существует аналогичная k-я строка в матрице Sj,  . Если такое состояние не нашлось, переходим к п. 1, иначе к п. 3.

3. Находим родительское состояние Si–1  , предшествующее состоянию Si , и состояние Sj–1  предшествующее Sj. Сравниваем их, для этого считаем их значения состояний Si   и Sj–1  по формуле

                                         (2)

где 𝑧 – номер состояния, равно (𝑖 − 1) или (𝑗 − 1); l – станция отправления; q – станция назначения.

Далее возможны два варианта.

3а. Если ci1 > cj1 , то прекращаем строить ветку, содержащую состояние Sj, , и удаляем ее. Переходим к п. 1.

3б. Если ci1   < cj1 , то удаляем ветку, содержащую состояние Si, до вершины Si  включительно, а вершины следующих уровней переносим к состоянию Sj Переходим к построению следующей ветки (п. 1).

Формула (2) представляет сумму выполненных заказов для заданного состояния. Будем считать более выгодным то расписание, в котором к заданному моменту времени выполнено больше заказов.

 

Пример решения задачи с тремя локомотивами одного типа для трех станций

Рассмотрим пример решения задачи построения расписания с тремя локомотивами одного типа для трех станций, расположенных по кругу. Используем обозначения, введенные выше. Схема расположения станций представлена на рис. 2.

Рис. 2. Схема расположения станций

 

Fig. 2. Diagram defining the location of stations

Заказы отправляются со станций 1 и 2 и следуют на станции 2 и 3. Заданы три маршрута следования – со станции 1 на станцию 2 (его обозначим 12), со станции 1 на станцию 3 (13) и со станции 2 на станцию 3 (23). Новые заказы размером 1 условная единица появляются на станциях отправления в моменты времени 1 и 3, грузоподъемность локомотива равна 2 единицам. Требуется найти расписание, при котором все заказы будут выполнены за наименьшее время.

Построим дерево состояний для заданной постановки задачи, используя алгоритм склеивания вершин. Результат представлен на рис. 3.

Рис. 3. Дерево состояний для трех локомотивов одного типа

Fig. 3. State tree for three locomotives of one type

 

Значение целевой функции вычислено по формуле (1) и представлено на рис. 3 после каждого расписания. Там же приведено количество доставленных заказов по каждому маршруту. Как видно из рис. 3, получено 16 возможных расписаний, при этом наименьшее значение критерия оптимальности равно 15 и достигнуто за счет ожидания заказов до полного заполнения локомотивов.

 

Постановка задачи с разными типами локомотивов

По сравнению с предыдущей постановкой, в случае, когда в задаче присутствуют локомотивы с разной грузоподъемностью, размерность задачи увеличивается и, как следствие, возрастает ее сложность.

Введем следующие обозначения: n – общее количество станций; L – количество типов локомотивов; m – общее количество локомотивов; hl – количество локомотивов типа    g-й локомотив типа l;   – момент времени в расписании g-го локомотива типа l;  – станция расположения g-го локомотива типа l;   количество доставленных локомотивом g типа l заказов с i-й станции отправления на j-ю станцию назначения,  ;   – состояние локомотива g типа l в соответствующий момент времени.

Кроме того, количество груза – заказы, которые необходимо перевезти с i-й станции в j-ю, появляются в определенные моменты времени на станциях отправления и не могут быть выполнены заранее. Необходимо составить расписание движения локомотивов, которое позволит обеспечить выполнение всех заказов.

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

                               (3)

где   – время завершения движения i-го локомотива,  .

Для приведенной постановки задачи следует отметить, что в ней состояние транспортной системы в каждый момент времени описывается трехмерным массивом, каждый срез которого является состоянием локомотивов соответствующего типа и представляет собой матрицу. Кроме того, алгоритм построения дерева состояний аналогичен предыдущей постановке задачи, отличаясь большой размерностью из-за ограничений, приведенных в [6]. Для разработанного алгоритма поиска оптимального расписания предлагается следующая модификация алгоритма склеивания вершин.

 

Алгоритм склеивания вершин

В дерево добавляется новое состояние, которое фиксируется текущим  . Состояние является трехмерным массивом. Двумерный срез массива определяет состояние локомотивов, относящихся к одному типу. Каждая строка среза соответствует конкретному локомотиву.

Проводится проверка для всех состояний   следующего условия:     для любого локомотива g,   и  . Фиксируем состояние, для которого данное условие выполняется как альтернативное,
и переходим на шаг 3. В случае отсутствия таких состояний осуществляется переход на шаг 1.

Проводится сравнение времен работы локомотивов при текущем и альтернативном состоянии.
Текущий маршрут удаляется и происходит возврат
к п. 1 (переход к другой ветке), если
  Удаляется маршрут, содержащий альтернативное состояние, если   
и происходит возврат к п. 1 (продолжается построение текущей ветки). В случае равенства времен
  отсев маршрутов происходит по суммарному времени работы всех локомотивов для состояний  . Выбирается маршрут с наименьшим значением, другой удаляется.

В итоге получаем, что в случае совпадения состояний на отдельных этапах разных веток дерева маршрутов выбирается лучший вариант из условия минимума времени перевозки такого же и большего количества заказов.

Далее рассмотрим пример сокращения вариантов маршрутов на примере железнодорожной сети (см. рис. 1). Пусть в данной сети для перевозки грузов используются локомотивы двух различных типов. Различие определяется их грузоподъемностью: у локомотива первого типа она составляет одну единицу, а у второго – две. Также определены станции, откуда груз отправляется – 1 и 2, и станции, куда груз доставляется – 2 и 3. Маршруты перевозки в данной сети следующие: 12 (перевозка с первой станции во вторую), 13 и 23. На станциях отправления появление грузов происходит в моменты времени 1 и 3. Каждый заказ на перевозку равен одной единице груза. Ставится следующая задача: составить расписание перевозки всего объема груза, позволяющее минимизировать время завершения полной доставки.

Ниже приводятся примеры склеивания вершин в соответствии с описанным алгоритмом и получаемые готовые маршруты. Склеивание вершин отражено на рис. 4.

 

Рис. 4. Примеры склеивания вершин:
а – склеивание вершин, соответствующее случаю
перевозки разного количества груза
за одинаковое время;
б – склеивание вершин с одинаковым состоянием,
 но достигнутым за равное время

 

Fig. 4. Examples of vertex gluing:
a – vertex gluing corresponding to the case
of transporting different amounts of cargo in equal time;

б – gluing vertices with the similar state,
but reached in equal time

 

Каждое состояние описывается набором данных следующего формата (t, s, k12, k13, k23) . Всего имеется три строки, первая из которых соответствует единственному локомотиву первого типа, а вторая и третья – двум локомотивам второго типа. Фрагмент итогового дерева расписаний, содержащий оптимальное расписание, приведен на рис. 5.

Рис. 5. Фрагмент дерева расписаний

Fig. 5. A fragment of a schedule tree

 

Для наглядности под каждым расписанием приводятся значения критерия оптимальности, вычисленного по формуле (3), и объем перевезенного груза по каждому из маршрутов. Минимальное значение критерия 7 достигается на нескольких расписаниях. В таком случае лучшим считается то, у которого меньше суммарное время работы локомотивов. Это расписание выделено на рисунке затененным прямоугольником. Всего в процессе сокращения вариантов были склеены 24 маршрута.

 

Заключение

В работе представлены два алгоритма планирования оптимальной загрузки железнодорожного транспорта – для однотипных локомотивов и для локомотивов разных типов. В таких постановках задачи состояние системы описывается в первом случае матрицей, каждая строчка которой соответствует отдельному локомотиву, а во втором случае трехмерным массивом, где матрицы описывают состояния локомотивов соответствующих типов. Добавление новых измерений в постановке задачи, таких как увеличение числа локомотивов и разделение локомотивов по характеристикам на различные типы, сильно увеличивает размерность задачи и усложняет решение перебором. Алгоритмы поиска оптимального расписания с применением процедуры «склеивания» состояний способны существенно сократить размерность дерева расписаний, что значительно облегчает процедуру поиска оптимального расписания. Представлен пример использования алгоритмов склеивания для решения частного случая описанной задачи. В дальнейшем планируется использовать предложенные алгоритмы в качестве основы для интеллектуальной системы планирования движения железнодорожного транспорта.

Список литературы

1. Baillieul J., Samad T. Encyclopedia of Systems and Control 2nd ed. 2021 Edition. Springer, 2021. PDF. 2497 p. 67 Mb. DOI: https://doi.org/10.1007/978-3-030-44184-5.

2. Матюхин В. Г., Шабунин А. Б. Интеллектуальные системы управления на железнодорожном транспорте // Интеллектуальные системы управления на железнодорожном транспорте (ИСУЖТ-2014): тр. Третьей науч.-техн. конф. М.: ОАО «НИИАС», 2014. С. 4-7.

3. Geiger M. J., Huber S., Langton S., Leschik M., Lin-dorf C., Tüshaus U. Multi-attribute assignment of trains to departures in rolling stock management // Annals of Operations Research. 2018. V. 271 (2). P. 1131-1163.

4. Цельсова А. Ю., Хоботов Е. Н. Разработка методики формирования маршрутов и расписаний движения грузовых поездов по железнодорожной сети // Интеллектуальные системы управления на железнодорожном транспорте (ИСУЖТ-2014): тр. Третьей науч.-техн. конф. М.: ОАО «НИИАС», 2014. C. 11-14.

5. Лазарев А. А., Мусатова Е. Г., Кварацхелия А. Г., Гафаров Е. Р. Теория расписаний. Задачи управления транспортными системами. М.: Изд-во МГУ им. М. В. Ломоносова, 2012. С. 160.

6. Елетин Е. В., Боровкова Г. С., Галкин А. В. Формализация задачи железнодорожного планирования для горнодобывающего предприятия // Прикладная математика и вопросы управления. 2022. № 1. С. 37-51.

7. Eletin E. V., Borovkova G. S., Galkin A. V. Solving the Task of Forming Trains and Their Schedule for Four Stations Using the Algorithm of Vertex Gluing // 3rd Inter-national Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA) (Lipetsk, 10-12 November 2021). New Jersey: IEEE, 2021. Pp. 1013-1016.


Войти или Создать
* Забыли пароль?