FORMALISING A RAIL PLANNING TASK FOR A MINING COMPANY

Abstract


The formalisation of the task of railway planning, namely, the formation of freight trains and their routes along the railway network of the mining company is considered. The statement of the problem including parameters of the problem, variables, system of constraints and target function is presented. An integer formulation of the problem, taking into account the constraints of a particular mining company, is proposed. The problem of railroad planning is relevant despite the various approaches and solutions available, since each case encounters different constraints. This formalisation differs from the others because there are different types of locomotives, and hence different capacities, and there are different types of materials to be transported. Four different categories of restrictions are presented. In addition, the existence of an extensive network of stations, a huge number of non-stationary constraints and other factors significantly increase the dimensionality of such problems, which increases the interest of researchers to them and contributes to the emergence of new and the development of existing methods and approaches to their solution. In the introduction, a description and features of the considered railway network of a mining company are presented. It then presents the formulation of the problem to be formalised, including parameters, variables, constraint system and target function. Then a numerical example with a solution is given. The integer linear programming method is used as a method for solving this problem. An example of scheduling freight trains for a network including four stations connected by double-track runs and having a star form is considered. The task of constructing routes is not considered in this example, as it is a separate complex task and is not required for this example, as there is a direct path from each departure station to each destination station.

Full Text

Введение Железнодорожная транспортная сеть рассматриваемого горнодобывающего предприятия состоит из одиннадцати станций, между которыми осуществляются перевозки грузовых вагонов. На всех станциях существует параллельность движения, к примеру, есть возможность выхода порожнего поезда из выгрузочного тупика и одновременный заход груженого поезда в свободный тупик для выгрузки или, наоборот, выход груженого поезда с погрузочного тупика и одновременный заход поезда в свободный погрузочный тупик для очередной погрузки. На некоторых станциях одновременно может прибывать и отправляться три поезда. Имеется три вида горной массы - кварциты, рыхлая прямая вскрыша и богатая руда. Самый высокий приоритет у заказов на перевозку кварцитов. Количество поездов для перевозки каждого вида горной массы зависит от расстояния перевозки, вида погрузки и объема ковша экскаватора. Существуют временные нормы погрузки различных видов горной массы в зависимости от объема ковша, а также временные нормы выгрузки. Некоторые из станций осуществляют только загрузку или только отгрузку горной массы, на некоторых осуществляется и то, и другое. То же касается и типов горной массы. Заказы на перевозку грузов поступают постоянно с течением времени. Каждый вагон является отдельным заказом. Если нужно отгрузить несколько вагонов определенной горной массы, то на каждый оформляется отдельный заказ. В качестве характеристик заказа выступают: станция отправления, станция назначения, важность, заданный директивный срок выполнения. Расписание для каждого состава представляет собой определенные временны прибытия и отбытия для всех станций, расположенных на маршруте движения поезда. Задачами являются: формирование составов из отдельных заказов, построение маршрутов следования для каждого состава и составление расписания движения составов по маршрутам. Критерием сравнение результатов выступает общее время выполнения всех заказов [1-12]. Постановка задачи 1. Параметры задачи. На заданном графе железнодорожной сети G = (N, E), вершины которого соответствуют станциям, N - их общее число, а ребра - перегонам между станциями, E - их общее число, каждой вершине (станции) ставятся в соответствие заказы (вагоны), которые необходимо перевести на другие станции. Введём следующие обозначения: - количество заказов для перевозки со станции i в j; - максимальное количество составов, которые могут быть одновременно обслужены на станции i; - k-й заказ, направляемый из i в j; - момент поступления заказа на станцию отправления; - директивный срок окончания обслуживания заказа ; - вес (значимость) заказа ; - масса заказа , где a - тип перевозимого материала, a = 1,2,3; - грузоподъемность поезда с локомотивом типа I (максимальная суммарная масса вагонов); - максимальная длина состава для локомотива типа b, b = 1,2, , . Отличием данной задачи от стандартной постановки, приведенной в [2], является наличие различных типов грузов, а также различных типов локомотивов, что приводит к увеличению числа ограничений и размерности задачи. Возникающие в связи с этим ограничения представлены далее. Далее дискретизируем время, задав определенный шаг - один час. Получаем набор возможных моментов времени T, ограниченных его верхней оценкой H, которая определяет максимальный срок выполнения всех заказов. Время движения по каждому ребру определяется по формуле , где - длина соответствующего ребра, а c - средняя скорость движения локомотива. Для каждого ребра задается величина интервала движения поездов . Величина интервала определяет, через какое время отправления поезда со станции i может начинать движение следующий поезд в том же направлении. Заданным должен быть и директивный срок выполнения заказа . Как правило, он определяется нормативно в соответствии с расстоянием между станцией отправления и станцией назначения: . В определенные моменты времени на отдельных путях могут проводиться технические работы, и тогда они являются недоступными. Эти моменты времени для путей задаются величинами интервалов недоступности . Задачей является определение маршрутов движения для каждого заказа и расписания прибытий и отбытий заказов со станций, располагающихся на маршруте движения, так, чтобы общее время выполнения всех заказов было минимальным. 2. Переменные. Введём следующие переменные. Пусть: (1) (2) Связь переменных x и y задаётся следующим образом: (3) где . Опишем основные ограничения задачи. 3. Ограничения. Естественные требования, предъявляемые к задачам маршрутизации, приведены в данной группе ограничений. Эти требования обеспечивают передвижение состав по путям железнодорожной сети Ограничения на передвижение по графу дорог Заказ не может быть отправлен раньше времени его поступления на станцию: . (4) Заказ может войти в вершину не более одного раза: . (5) Заказ может выйти из вершины не более одного раза: . (6) Все заказы должны быть доставлены в пункты назначения: . (7) Если заказ пришел на промежуточную станцию, он должен из неё выйти: . (8) При этом заказ начинает прохождение следующего ребра не раньше, чем через время, требуемое на прохождение предыдущего: (9) . Следующая группа ограничений относится к характеристикам используемого транспорта. Ограничения по составам Использование разных типов локомотивов и перевоз разных типов грузов задается следующими ограничениями. Ограничение по длине состава (одновременно по ребру может быть отправлено не более вагонов): . (10) Ограничение по массе состава: . (11) Ограничения по сортировочным станциям На сортировочной станции v не может одновременно обслуживаться более cоставов: (12) Величина зависит от количества погрузочных и разгрузочных тупиков станции (её продуктивности). Ограничения по путям Поезда отправляются по ребру (u,v) c интервалом δuv: . (13) Одновременно на одном пути между двумя станциями может находиться несколько поездов. Причем это количество поездов соответствует участкам, разделенным семафорами. Такие участки называются блок-участками. В формуле (13) величина δuv определяет время прохождения максимального из таких блок-участков, расположенных на пути между станциями u и v. Движение в запрещённые моменты времени невозможно: . (14) На практике данные ограничения возникают в случае временного закрытия тех или иных путей на ремонт. 4. Целевая функция. Для каждого заказа Jijk расчет времени прибытия на станцию отправления осуществляется по формуле . (15) Будем считать, что затраты на перевозку пропорциональны расстоянию, которое проходят все поезда. В этом случае суммарные издержки можно рассчитать по формуле . (16) Получаем оптимизационную задачу с критерием оптимальности , (17) где φ(C) определяет сроки доставки для всех заказов. При минимизации суммарного времени доставки всех грузов эта функция определяется по следующей формуле, определяющей для заказов среднее время их движения . (18) В этом случае целевая функция (17) принимает линейный вид, как и все ограничения. Таким образом, данная задача относится к классу задач линейного программирования. Учитывая, что переменные могут принимать только целые значения, задача является целочисленной. Вычислительный пример Рассмотрим пример постановки упрощенной задачи и ее решение методом математического программирования, приближенные к реальным условиям. Пусть рассматриваемая железнодорожная сеть имеет форму звезды, каждая из четырех станций которой соединена с соседними двухпутными перегонами (рисунок). На каждой станции отправления в начальный момент времени находятся по одному составу с 10 вагонами и по одному с 13 вагонами. Требуется перевезти со станций 1, 2 и 3 материалы трех типов - кварциты, вскрыша и богатая руда - на станции 2, 3, 4 за минимальное время. При этом данная постановка не требует построения маршрутов, поскольку поиск оптимального маршрута является отдельной сложной задачей и рассматривается в [13]. Рис. Расположение станций Параметры Введем следующие обозначения: в качестве перевозимых материалов обозначим кварциты как a = 1, вскрышу как a = 2, богатую руду как a = 3; локомотивы с разной грузоподъемностью и длинной состава: b = 1 - состав с 10 вагонами и маневровым тепловозом типа ТЭМ18 (1200 л.с.), b = 2 - состав с 13 вагонами и маневровым тепловозом типа ТЭМ7 (2000 л.с.); k - порядковый номер заказа, k = {1, 2}; станции отправления - 1, 2, 3; станции назначения - 2, 3, 4; ; i = 1,...,4; , ; - время выполнения заказа по перевозке состава из u в v задано данными табл. 1, из которой видно, что время выполнения заказов на составах, включающих 13 вагонов, длиннее, чем на составах с 10 вагонами; значимость заказов положим у всех одинаковой; , . Таблица 1 Время выполнения заказов Маршрут (u,v) (1,2) (2,3) (3,4) (1,2) (2,3) (3,4) Тип составов, b 1 1 1 2 2 2 Время выполнения заказа, d 3 4 5 4 5 6 Переменные Пусть в рамках данной задачи: , где l - число перевозимых из u в v вагонов; Ограничения В качестве ограничений будем использовать соотношения (7) - все заказы обязательно должны быть выполнены, (10) - локомотив определенного типа не может перевозить больше заданного количества вагонов, (12) - ограничение на одновременное нахождение нескольких составов на сортировочной станции. Будем считать, что ограничение по массе состава выполняется за счет ограничения по длине. Используются не все ограничения, поскольку такую задачу решить готовыми программными средствами не представляется возможным. Целевая функция В качестве целевой функции рассмотрим функцию минимизации времени выполнения заказов: Решение Решение данной задачи представлено в табл. 2. Это решение получено с помощью функции «Поиск решений» Microsoft Excel. При этом целевая функция приняла значение F = 254. Таблица 2 Решение (u,v) (1,2) (2,3) (3,4) (1,2) (2,3) (3,4) (1,2) (2,3) (3,4) (1,2) (2,3) (3,4) t 1 1 1 2 2 2 1 1 1 2 2 2 b 1 1 1 1 1 1 2 2 2 2 2 2 d(u,v) 3 4 5 3 4 4 5 6 5 4 5 6 x(u,v)t 0 10 0 10 10 10 5 0 0 0 0 0 a 1 1 1 1 1 1 1 1 1 1 1 1 y(u,v)t 0 1 0 1 1 1 1 0 1 0 0 0 t 1 1 1 2 2 2 1 1 1 2 2 2 b 1 1 1 1 1 1 2 2 2 2 2 2 x(u,v)t 4 2 4 4 2 2 3 3 1 4 13 3 a 2 2 2 2 2 2 2 2 2 2 2 2 y 1 1 1 1 1 1 1 1 1 1 1 1 t 1 1 1 2 2 2 1 1 1 2 2 2 b 1 1 1 1 1 1 2 2 2 2 2 2 x(u,v)t 1 3 1 4 0 4 7 6 2 3 11 3 a 3 3 3 3 3 3 3 3 3 3 3 3 y(u,v)t 1 1 1 1 0 1 1 1 1 1 1 1 t 3 3 3 4 4 4 3 3 3 4 4 4 b 1 1 1 1 1 1 2 2 2 2 2 2 x(u,v)t 0 10 0 0 10 1 3 0 5 12 0 4 a 1 1 1 1 1 1 1 1 1 1 1 1 y(u,v)t 0 1 0 0 1 1 1 0 1 1 1 1 t 3 3 3 4 4 4 3 3 3 4 4 4 b 1 1 1 1 1 1 2 2 2 2 2 2 x(u,v)t 6 5 4 3 7 0 3 4 2 3 4 4 a 2 2 2 2 2 2 2 2 2 2 2 2 y(u,v)t 1 1 1 1 1 0 1 1 1 1 1 1 t 3 3 3 4 4 4 3 3 3 4 4 4 Окончание табл. 2 (u,v) (1,2) (2,3) (3,4) (1,2) (2,3) (3,4) (1,2) (2,3) (3,4) (1,2) (2,3) (3,4) b 1 1 1 1 1 1 2 2 2 2 2 2 x(u,v)t 2 10 1 4 2 1 8 4 0 1 4 8 a 3 3 3 3 3 3 3 3 3 3 3 3 y(u,v)t 1 1 1 1 1 1 1 1 0 1 1 1 Заключение В статье представлена формализация задачи железнодорожного планирования для железнодорожной сети горнодобывающей компании, учитывающая дополнительные параметры, возникающие на практике, такие как различные типы вагонов и перевозимых грузов, что приводит к возникновению дополнительных ограничений. На практике большое количество ограничений приводит к увеличению размерности задачи, что значительно усложняет решение. Поэтому перспективным направлением исследований является разработка различных методов решения подобных задач, например таких, как различные эвристические подходы [4; 8; 10; 12], методы теории игр [7], комбинаторной оптимизации [6], с использованием динамических моделей [9; 11], различные подходы целочисленного программирования [2; 5; 6] и прочих. Приведен пример решения задачи методами линейного программирования, учитывающий определенные ограничения. В дальнейших исследованиях планируется интеграция задачи формирования расписания с задачами поиска оптимальных маршрутов перевозок по графу железных дорог и формирования составов.

About the authors

E. V Eletin

Corporate solutions center

G. S Borovkova

Lipetsk State Technical University

A. V Galkin

Lipetsk State Technical University

References

  1. Теория расписаний. Задачи железнодорожного планирования / А.А. Лазарев, Е.Г. Мусатова, Е.Р. Гафаров, А.Г. Кварацхелия. - M.: ИПУ РАН, 2012. - 92 c.
  2. Лазарев А.А., Мусатова Е.Г. Целочисленные постановки задачи формирования железнодорожных составов и расписания их движения // Управление большими системами. - М.: ИПУ РАН, 2012. Вып. 38. - С. 161-169.
  3. Теория расписаний. Задачи управления транспортными системами / А.А. Лазарев, Е.Г. Мусатова, А.Г. Кварацхелия, Е.Р. Гафаров. - М.: Физический факультет МГУ им. М.В. Ломоносова, 2012. - С.160.
  4. Петров К.В., Низов А.С. Математическое обоснование современной концепции планирования и управления транспортным обеспечением // Вестник Военной академии материально-технического обеспечения им. генерала армии А.В. Хрулева. - 2018. - № 1 (13). - С. 15-21.
  5. Комплексный подход к интеллектуальным системам управления горным производством / А.В. Варичев, С.И. Кретов, Р.И. Исмагилов, Б.П. Бадтиев, Д.Я. Владимиров // Горная промышленность. - 2016. - № 3 (127). - С. 4.
  6. Гайнанов Д.Н., Рассказова В.А. Математическое моделирование в задаче оптимального назначения и перемещения локомотивов методами теории графов и комбинаторной оптимизации // Труды МАИ. - 2017. - № 92. - С. 31.
  7. Карпухин В.Б., Биленко Г.М. Выбор оптимальной стратегии грузоперевозок транспортного предприятия на основе решений игровых задач // Наука и техника транспорта. - 2019. - № 4. - С. 18-23.
  8. Разработка алгоритма, обеспечивающего качественное планирование оперативного графика движения железнодорожного транспорта / А.Л. Золкин, М.С. Чистяков, Т.Н. Буштрук, Б. Ли // Вестник Донецкой академии автомобильного транспорта. - 2021. - № 2. - С. 10-20.
  9. Терещенко О.А. Оперативное планирование местной работы железнодорожных участков и узлов с использованием динамической модели перевозочного процесса // Транспортні системи та технології перевезень. - 2016. - № 12. - С. 80-89.
  10. Антонова Е.И., Васильев И.А. Задачи планирования в работе железнодорожного транспорта на контейнерном терминале. Описание методов решения // Информационные технологии в науке, образовании и управлении / под ред. проф. Е.Л. Глориозова. - 2015. - С. 108-113.
  11. Терещенко О.А. Динамическая модель перевозочного процесса для решения задачи оперативного планирования местной работы железнодорожных участков и узлов // Вестник Белорусского государственного университета транспорта. Наука и транспорт. - 2017. - № 1 (34). - С. 68-71.
  12. Карпухин В.Б., Биленко Г.М. Математическая модель задачи оптимального планирования объемов вагонопотоков на предприятии железнодорожного транспорта // Наука и техника транспорта. - 2016. - № 4. - С. 27-30.
  13. Eletin E., Borovkova G., Galkin A. Solving the Task of Forming Trains and Their Schedule for Four Stations Using the Algorithm of Vertex Gluing // 3rd International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA). - Lipetsk, 2021. - P. 1013-1016.

Statistics

Views

Abstract - 1

PDF (Russian) - 1

Refbacks

  • There are currently no refbacks.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies