Полный текст

Введение Железнодорожная транспортная сеть рассматриваемого горнодобывающего предприятия состоит из одиннадцати станций, между которыми осуществляются перевозки грузовых вагонов. На всех станциях существует параллельность движения, к примеру, есть возможность выхода порожнего поезда из выгрузочного тупика и одновременный заход груженого поезда в свободный тупик для выгрузки или, наоборот, выход груженого поезда с погрузочного тупика и одновременный заход поезда в свободный погрузочный тупик для очередной погрузки. На некоторых станциях одновременно может прибывать и отправляться три поезда. Имеется три вида горной массы - кварциты, рыхлая прямая вскрыша и богатая руда. Самый высокий приоритет у заказов на перевозку кварцитов. Количество поездов для перевозки каждого вида горной массы зависит от расстояния перевозки, вида погрузки и объема ковша экскаватора. Существуют временные нормы погрузки различных видов горной массы в зависимости от объема ковша, а также временные нормы выгрузки. Некоторые из станций осуществляют только загрузку или только отгрузку горной массы, на некоторых осуществляется и то, и другое. То же касается и типов горной массы. Заказы на перевозку грузов поступают постоянно с течением времени. Каждый вагон является отдельным заказом. Если нужно отгрузить несколько вагонов определенной горной массы, то на каждый оформляется отдельный заказ. В качестве характеристик заказа выступают: станция отправления, станция назначения, важность, заданный директивный срок выполнения. Расписание для каждого состава представляет собой определенные временны прибытия и отбытия для всех станций, расположенных на маршруте движения поезда. Задачами являются: формирование составов из отдельных заказов, построение маршрутов следования для каждого состава и составление расписания движения составов по маршрутам. Критерием сравнение результатов выступает общее время выполнения всех заказов [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] и прочих. Приведен пример решения задачи методами линейного программирования, учитывающий определенные ограничения. В дальнейших исследованиях планируется интеграция задачи формирования расписания с задачами поиска оптимальных маршрутов перевозок по графу железных дорог и формирования составов.

Об авторах

Е. В Елетин

Центр корпоративных решений

Г. С Боровкова

Липецкий государственный технический университет

А. В Галкин

Липецкий государственный технический университет

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

Статистика

Просмотры

Аннотация - 178

PDF (Russian) - 154

Ссылки

• Ссылки не определены.