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


Формализация задачи прикрепления тяговых ресурсов к поездам и ее программная реализация



страница10/24
Дата09.08.2018
Размер2.94 Mb.
#43463
ТипЗадача
1   ...   6   7   8   9   10   11   12   13   ...   24

1.10Формализация задачи прикрепления тяговых ресурсов к поездам и ее программная реализация


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

1.10.1Формирование функции полезности


Ключевым вопросом для формулировки задачи привязки поездов и тяговых ресурсов как задачи о назначениях и учета технологических ограничений является формирование функции полезности. Для всех подзадач аналогично уже описанному в разделе 1.1.1 алгоритму оценки расписания поездов были разработаны основные критерии оценки эффективности их решения.

Ниже приводятся критерии функций полезности для подзадач привязки тяговых ресурсов к поездам, разработанные в рамках создания модуля планирования расписания грузоперевозок. Каждому критерию ставится в соответствие нормированное численное значение uk, после чего вычисляется значение для функции полезности пары <ТПС(ЛБ),локомотивный(бригадный) слот> как



,

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


1.10.1.1Расчет функции полезности для задачи привязки локомотива к поезду


Общий подход

  1. Общая идея расчета состоит в следующем. Мы берем локомотивный слот и анализируем, насколько выгодно будет назначить тот или иной локомотив на этот слот. Выгода измеряется следующими критериями:

    1. Локомотив должен больше времени проводить в работе и меньше пересылаться резервом.

    2. Локомотив должен меньше простаивать на станции в ожидании работы.

    3. Если для локомотива подходит время ТО-2, то он должен заканчивать свою работу ближе к станции проведения ТО-2.

    4. У локомотива должно оставаться как можно меньше неиспользованного рабочего времени.

    5. Локомотив под тяжелые поезда лучше не назначать на легкие поезда. Легкий локомотив же вообще не может везти тяжелый поезд.

    6. Если локомотив не успевает прибыть на станцию ко времени отправления локомотивного слота, то локомотивный слот можно «отодвинуть» на нужное время, но эта операция не выгодна.

  1. После этого происходит анализ того, что может случиться с локомотивом после прибытия на конечную станцию слота:

    1. Для локомотива может найтись еще один слот для работы.

    2. Локомотиву может не хватить времени до ремонта для выполнения следующего слота.

    3. Для локомотива вообще может не быть следующего слота на конечной станции.

  2. В случаях 2.b и 2.c функция полезности считается вычисленной. В случае 2.a требуется найти все допустимые «будущие» слоты с конечной станции и для каждого из этих слотов посчитать новое значение функции полезности, учитывая то, что локомотив уже двигался по первому, исходному слоту. Таким образом, появится несколько значений функции полезности, соответствующие разным «веткам» - разным вариантам движения локомотива в будущем.

  3. После завершения вычисления по всем веткам (глубина расчета ограничена задаваемым параметром) получается набор из нескольких функций полезности, соответствующих разным вариантам движения локомотива (но все варианты начинаются с исходного локомотивного слота). Из этого набор требуется выбрать максимальное значение – оно и будет значением функции полезности для исходной пары <слот, локомотив>.

В Таблице 3.1 приведены сведения по расчету критериев функции полезности.

Таблица 3.. Сведения по расчету критериев функции полезности для задачи привязки локомотива к поезду



Номер

Название критерия

Порядок расчета

Знак коэффициента

1

Время работы

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

+

2

Ожидание слота локомотивом

Разность между временем отправления слота и временем прибытия локомотива на станцию отправления. Если эта разность отрицательная, то брать значение критерия = 0.

-

3

Ожидание локомотива слотом

Разность между временем прибытия локомотива на станцию отправления и временем отправления слота на первый участок. Если эта разность отрицательна, то брать значение критерия = 0.

-

4

Время до станции проведения ТО-2

Время хода от конечной станции слота до ближайшей станции проведения ТО-2.

-

5

Оставшееся время до ТО-2

Время работы до ТО-2, которое локомотив будет иметь на момент времени прибытия на конечную станцию слота с учетом возможной пересылки локомотива по критерию 7.

Если значение < 0, то значение критерия устанавливать (эквивалентно тому, что локомотив запрещено назначать на данный слот).



-

6

Весовые ограничения

1. Выбрать из сообщений loco_tonnage (см. Приложение 1) те, которые относятся к локомотивам той серии и с тем количеством секций, которые указаны для обрабатываемого реального локомотива, а также относящиеся ко всем участкам планирования на маршруте локомотивного слота. Из значений весовых ограничений для выбранных сообщений loco_tonnage надо выбрать минимальное значение WL – это будет максимально допустимый вес поезда, который данный реальный локомотив может провезти по данному маршруту. Пусть WT – вес поезда, соответствующего локомотивному слоту.

2. Если , то значение по критерию (эквивалентно тому, что локомотив запрещено назначать на данный слот). Дальнейших расчетов по этой ветке производить не требуется.

3. Если , то брать значение по критерию .

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



+

7

Время на пересылку локомотива резервом

Время хода между станцией, на которой находится локомотив на момент подсчета, и станцией, с которой начинается локомотивный слот.

-

8

Будущие планы




+

1.10.1.2Расчет функции полезности для задачи привязки бригады к локомотиву


Общий подход

  1. Общая идея расчета состоит в следующем:

    1. Бригада должна меньше пересылаться пассажирами, поэтому приоритетнее искать бригаду на той станции, с которой начинается бригадный слот.

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

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

    4. Бригаде, вышедшей с отдыха не в депо приписки, приоритетнее ехать в сторону депо приписки, а не в обратную.

    5. Крайне нежелательно, если локомотиву приходится ждать бригаду (бригада не готова к работе на время начала бригадного слота).

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

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

  2. В первом приближении для бригад нет нужды в расчете полезности с учетом будущих возможных слотов (расчет «в глубину» по времени). Однако для увеличения точности получаемого решения возможно включение указанного расчета возможных будущих слотов аналогично описанному выше расчету для локомотивов – см. раздел 1.10.1.1, пп.2-4.

В таблице 3.2 приведена информация по расчету критериев функции полезности.

Таблица 3.. Информация по расчёту критериев в функции полезности для задачи привязки бригады к локомотиву



Номер

Название критерия

Порядок расчета

Знак коэффициента

1

Время на перемещение бригады пассажиром

1. Если станция местоположения бригады совпадает со станцией отправления бригадного слота, то время на перемещение бригады = 0.

2. В противном случае время на перемещение бригады – это время хода между станцией местоположения бригады и станцией отправления слота.



-

2

Время ожидания бригадой локомотива

1. Если станция местоположения бригады совпадает с депо приписки, то время ожидания = 0.

2. В противном случае время ожидания – это значение , где TL – время начала бригадного слота, T0 – время готовности бригады к работе, TR – время на перемещение бригады пассажиром. Если вычисленное значение < 0, то время ожидания принимается равным 0.



-

3

Время ожидания локомотивом бригады

1. Значение , где T0 – время готовности бригады к работе, TR – время на перемещение бригады пассажиром, TL – время начала бригадного слота. Если вычисленное значение < 0, то время ожидания принимается равным 0.

-

4

Оставшееся рабочее время

1. Для бригады вычисляется «критическое» время – самое позднее допустимое время окончания ее работы по данному слоту. Вычисление ведется по формуле , где T1 – время отправления бригадного слота, – оставшееся рабочее время бригады, TR – время на перемещение бригады пассажиром, TW – время ожидания бригадой локомотива.

2. На маршруте бригадного слота определяются все участки, конечной станцией которых являются станции смены бригад (или конечная станция по маршруту) и которые принадлежат участку обкатки данной бригады.

3. Среди станций из п. определяется станция («критическая» станция), для которой время прибытия на нее по маршруту бригадного слота ближе всего к «критическому» времени, но не превышает его.

4. Разность между критическим временем и временем прибытия на такую станцию – это и есть значение по данному критерию.



-

5

Направление на депо

1. Если станция местоположения бригады совпадает с депо приписки, то значение по критерию = 0.

2. В противном случае если среди станций на маршруте бригадного слота (кроме станции отправления) присутствует депо приписки бригады, то значение по критерию = 0 (бригада будет двигаться к депо). Иначе значение по критерию = -2.



+

6

Процент совпадения маршрута с участком обкатки

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

2. Значение по критерию – это отношение количества таких участков к количеству участков в маршруте бригадного слота.

3. Если количество нужных участков = 0, то значение по критерию устанавливается (эквивалентно запрету назначения бригады на данный слот).


+

1.10.2Алгоритм построения модели планирования эффективного расписания грузоперевозок


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

На Рисунке 3.4 представлена общая структура алгоритма планирования.



Рисунок 3.. Общая структура алгоритма планирования

Опишем подпрограммы, решающие подзадачи планирования поездов, локомотивов и бригад.

1.10.2.1Планирование поездов


На Рисунке 3.5 показана блок-схема алгоритма планирования расписания поездов.

Рисунок 3.. Общий алгоритм планирования расписания поездов

Так как поиск станций смены локомотивов является, по сути, составлением локомотивных слотов, и оба этих алгоритма требуют прохода по всем участкам на маршруте поезда, то при реализации планирование поездов объединено с составлением локомотивных слотов (раздел 1.10.2.2).


  1. Поезда, для которых был передан факт train_depart (см. Приложение 1), требуется планировать в первую очередь. Их надо допланировать до первой по дальнейшему маршруту станции смены бригады (это станции, у которых нормативное время на смену бригады больше 0). Далее эти поезда должны участвовать в планировании на общих основаниях.

  2. Поезда следует назначать на нитки в соответствии с приоритетом категорий поездов, указанным в разделе 1.9.1.3.

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

  4. В планировании должны принимать участие как поезда, по которым переданы факты (train_info, train_depart, train_arrive, train_ready), так и поезда из объемных заданий на планирование (task) (см. Приложение 1). Для поездов из task категория должна браться равной низшей категории из раздела 1.9.1.3.

  5. Станция считается станцией смены бригады, если нормативное время на смену бригады по этой станции и данному тяговому плечу (norm_time, см. Приложение 1) больше 0.

1.10.2.2Планирование локомотивов


Составление локомотивных слотов

Общий алгоритм составления локомотивных слотов представлен на Рисунке 3.6. Исходя из ограничений из пункта 1.9, смена локомотивов может происходить только на граничных станциях тяговых плеч (ТП) или в непосредственной близости от них. Для того чтобы определить станцию смены локомотивов, мы должны определить, локомотив с какого тягового плеча должен везти поезд. Таким образом, задача сводится к определению тяговых плеч, локомотивы с которых должны последовательно везти поезд.



Рисунок 3.. Общий алгоритм составления локомотивных слотов

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


  • Пусть – набор участков планирования, составляющих неразмеченный маршрут поезда (см. обозначения к текущей главе), а – набор участков планирования, которые входят в тяговое плечо .

  • Больший приоритет получают такие тяговые плечи, локомотивы с которых могут провезти поезд по всему маршруту поезда (или близко ко всему). То есть все тяговые плечи надо отсортировать по параметру , где – пересечение соответствующих множеств, а - количество элементов в соответствующем наборе. Больший приоритет получают тяговые плечи, для которых значение минимально.

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

На шаге алгоритма, при котором происходит смена локомотивного слота (ветка блок-схемы «Среди этих ТП есть ТП, выбранное на предыдущем участке? – Нет»), требуется точно определить станцию смены локомотива следующим образом:

  • Если среди приоритетных станций смены локомотива есть конечная станция текущего локомотивного слота, то ничего дополнительно проверять не следует.

  • Если среди приоритетных станций смены локомотива нет конечной станции текущего слота, то требуется анализировать 5 предыдущих станций в локомотивном слоте. Если среди этих станций есть приоритетная станция смены локомотива, то:

    • В локомотивном слоте требуется отрезать «хвост» после этой приоритетной станции. Таким образом, слот должен заканчиваться на этой станции.

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

  • Таким образом, смена локомотива будет запланирована на приоритетной станции смены локомотивов.

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

Ручная привязка локомотивов, находящихся в пути на начало планирования



Рисунок 3.. Блок-схема алгоритма ручной привязки локомотивов, находящихся в пути на начало планирования



  1. Локомотивный слот ищется по следующим правилам:

    1. Для локомотивов, находящихся на перегоне, поиск локомотивного слота должен производиться по следующим условиям:

      1. Поезд, с которым связан локомотивный слот, должен быть указан в атрибуте train соответствующего сообщения fact_loco (см. Приложение 1).

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

      3. Если локомотивных слотов, соответствующих пунктам i-ii, найдено несколько, то требуется анализировать время T, которое указано в маршруте локомотивного слота для отправления на данным участок планирования. В качестве искомого требуется брать тот локомотивный слот, для которого это время Т ближе всего к времени отправления, указанном в атрибуте location  track  depart_time сообщения fact_loco.

    2. Для локомотивов, прибывших на станцию с поездом, поиск локомотивного слота должен производиться по следующим условиям:

      1. Поезд, с которым связан локомотивный слот, должен быть указан в атрибуте train соответствующего сообщения fact_loco.

      2. В маршруте локомотивного слота должна присутствовать станция, на которой находится локомотив (станция, указанная в атрибуте location соответствующего сообщения fact_loco).

      3. Тяговое плечо, с которым связан локомотивный слот, должно входить в список тяговых плеч данного локомотива.

      4. Если локомотивных слотов, соответствующих пунктам i-iii, найдено несколько, то требуется анализировать время T, которое указано в локомотивном слоте для отправления со станции, на которой находится реальный локомотив. В качестве искомого требуется брать тот локомотивный слот, для которого это время T ближе всего к времени прибытия, указанного в атрибуте location  arrive_time сообщения fact_loco.

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

  3. Алгоритм обновления состояния локомотива описан ниже.

Описание алгоритма планирования локомотивов для одной итерации планирования.

Рисунок 3.. Планирование локомотивов для одной итерации планирования

Составление списка локомотивных слотов для планирования


  1. Привязка локомотивов должна вестись отдельно по 6-часовым интервалам и отдельно по тяговым плечам (внутри каждого 6-часового интервала). Общий горизонт планирования локомотивов – 2 суток. Таким образом, всего должно быть 8 * N итераций планирования, где N – количество тяговых плеч на полигоне.

  2. На каждой итерации в список локомотивных слотов, к которым требуется подобрать локомотив, должны попадать слоты, для которых выполнены следующие условия:

    1. Тяговое плечо, с которым связан локомотивный слот, должно совпадать с тяговым плечом, для которого проводится данная итерация планирования.

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

      1. Если время отправления совпадает с левой границей интервала (начало интервала), то такой слот должен попадать в список. Если время отправления совпадает с правой границей (окончание интервала), то такой слот не должен попадать в список (он попадет в список на следующем интервале).

Составление списка локомотивов для планирования

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

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

Обновление состояния локомотива



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

    1. Станция местоположения – конечная станция локомотивного слота.

    2. Время доступности на станции местоположения – это время прибытия на конечную станцию локомотивного слота плюс время на обработку локомотива на станции (сообщение process).

    3. Оставшееся время работы до ТО-2. Вычисляется по формуле: , где Tprev – предыдущее оставшееся время работы до ТО-2, RT1 – время доступности, рассчитанное на шаге b, RTprev – предыдущее время доступности.

  2. Эти три атрибута должны рассчитываться одновременно и все вместе задают последнее актуальное состояние локомотива: локомотив доступен для планирования на станции местоположения, начиная с времени доступности, с вычисленным временем до ТО-2.

Отставка локомотивов на ТО-2

  1. После первого расчета матрицы полезности требуется составлять список локомотивов данного тягового плеча, которые на момент начала данной итерации планирования находились на станции в доступном состоянии, но для которых не удалось рассчитать значение функции полезности хотя бы для одного локомотивного слота. Такой локомотив не будет привязан ни к одному поезду во время данной итерации планирования – с большой вероятностью, этот локомотив можно отставить на ТО-2.

  2. Если на момент завершения временного интервала текущей итерации планирования оставшееся время работы локомотива до ТО-2 меньше некоего порогового времени, то для такого локомотива требуется регистрировать операцию проведения ТО-2:

    1. Время начала проведения ТО-2 – время начала текущей итерации.

    2. Длительность ТО-2 – время проведения ТО-2 из сообщения station на той станции, на которой находится локомотив.

      1. Если на данной станции невозможно проводить ТО-2 (время проведения равно 0), то требуется планировать передислокацию локомотива резервом на ближайшую станцию проведения ТО-2 и на этой станции регистрировать проведение ТО-2 (см. 2.c). В качестве времени начала ТО-2 в этом случае требуется брать время прибытия локомотива на станцию проведения.

    3. Отставку локомотива на ТО-2 следует фиксировать в возвращаемом сообщении slot_loco (см. Приложение 1) как участок маршрута движения локомотива. При этом станции отправления и станции прибытия на участок совпадают (и равны станции проведения ТО-2), время отправления – это время начала проведения ТО-2, время прибытия – время завершения ТО-2 (сумма времени начала и длительности), состояния локомотива State = 4, номер поезда TrainId = -1.

    4. После проведения ТО-2 требуется обновлять состояние локомотива: делать его доступным на станции проведения ТО-2, начиная со времени завершения ТО-2. Время до следующего ТО-2 – 92 часа.

Перемещение локомотивов резервом

  1. Если в результате привязки локомотива к локомотивному слоту оказалось, что локомотив доступен на станции, которая отличается от станции отправления слота, то требуется планировать пересылку локомотива резервом.

  2. Для этого требуется вычислить требуемое время прибытия локомотива – это время отправления локомотивного слота минус время на обработку локомотива на станции (из сообщения process для данной станции).

  3. Далее требуется вычислить ориентировочное время отправления локомотива со станции местонахождения: из требуемого времени прибытия вычесть время хода между данными станциями и временные допуски.

  4. Для резервного локомотива создать фиктивный поезд с уникальным номером в диапазоне от 3000 до 3999, запустить для этого поезда алгоритм планирования поезда (см. раздел 1.10.2.1), начиная от ориентировочного времени отправления.

  5. К этому фиктивному поезду вручную привязывать обрабатываемый локомотив.

  6. Возвращать сообщение slot_loco для обрабатываемого локомотива о следовании с этим фиктивным поездом.

Сдвиг поездов

  1. Если в результате привязки локомотива к локомотивному слоту оказалось, что локомотив доступен на станции позже времени отправления локомотивного слота, то требуется перепланировать поезд, с которым связан локомотивный слот на будущее время.

  2. Требуется удалить рассчитанный в разделе 1.10.2.1 план по поезду, начиная со станции отправления локомотивного слота (расписание поезда на маршруте до этой станции изменять нельзя).

  3. Далее требуется запустить алгоритм планирования этого поезда (раздел 1.10.2.1), начиная с времени готовности локомотива на станции отправления.

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

Учет заданий на регулирование

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

  2. Для всех таких заданий требуется рассчитать количество локомотивов, которые были запланированы к пересылке резервом (state = 0) через указанную в задании станцию в нужном направлении. Если количество запланированных локомотивов меньше указанного в задании, то требуется дополнительно запланировать пересылку резервом оставшегося количества локомотивов. Свободный локомотив ищется из расчета, что сумма последнего времени его доступности и времени хода между станцией местоположения и станцией стыка не должна превышать правую границу временного интервала из задания. А также с учетом всех ограничений из пункта 1.9.2.2.

1.10.2.3Планирование бригад


Общая схема алгоритма и описание алгоритма для одной итерации планирования представлены на следующих двух блок-схемах.

Рисунок 3.. Общая схема планирования бригад



Рисунок 3.. Планирование бригад (одна итерация)



Составление бригадных слотов

  1. Бригадный слот должен создаваться каждый раз после того, как локомотив привязан к локомотивному слоту.

  2. Бригадный слот представляет собой фрагмент маршрута локомотива, на который еще не назначены бригады.

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

  4. Отличие от привязки локомотивов к локомотивным слотам состоит в том, что бригады необязательно привязываются сразу на весь бригадный слот от начальной до конечной станции. После выполнения привязки бригады требуется определить станцию, до которой бригада будет следовать с этим локомотивом. После этого требуется обновить бригадный слот, оставив в нем лишь неразмеченный фрагмент маршрута. Обновленный бригадный слот снова должен участвовать в планировании.

Составление списка бригадных слотов для планирования

  1. Как было сказано выше, привязка бригад должна вестись отдельно по 3-часовым интервалам и отдельно по тяговым плечам локомотивов. Общий горизонт планирования бригад – 1 сутки. Общее количество итераций планирования определить невозможно, поскольку оно будет зависеть от конкретных бригадных слотов.

  2. На каждой итерации в список бригадных слотов, к которым требуется подобрать бригаду, должны попадать слоты, для которых выполнены следующие условия:

    1. Тяговое плечо, с которым связан бригадный слот, должно совпадать с тяговым плечом, для которого проводится данная итерация планирования.

    2. Время отправления на первый участок маршрута бригадного слота лежит во временном интервале данной итерации планирования.

      1. Если время отправления совпадает с левой границей интервала (начало интервала), то такой слот должен попадать в список. Если время отправления совпадает с правой границей (окончание интервала), то такой слот не должен попадать в список (он попадет в список на следующем интервале).

Составление списка бригад для планирования

  1. Список бригад должен определяться отдельно для каждого бригадного слота.

  2. Для бригадного слота требуется определить станцию отправления и станции, «соседние» со станцией отправления. Станция А считается «соседней» со станцией Б, если время хода от А до Б не превышает 6 часов.

  3. В список бригад, доступных для бригадного слота, должны попадать бригады, которые (по своему актуальному состоянию) находятся на станции отправления или на любой «соседней» к ней станции.

Определение станции смены бригады

  1. Станция смены бригады – это «критическая» станция на маршруте бригадного слота, определенная при вычислении критерия 4 («Оставшееся рабочее время», раздел 1.10.1.2) в расчете функции полезности для того бригадного слота, к которому в результате решения задачи о назначениях оказалась привязана бригада.

  2. После определения станции смены бригады требуется обновить бригадный слот, к которому привязана бригада.

    1. Из маршрута бригадного слота требуется удалить фрагмент от станции начала до станции смены текущей бригад.

    2. Обновленный бригадный слот должен снова поступать в пул слотов для планирования.

    3. Если «оставшийся» маршрут бригадного слота пустой (это эквивалентно тому, что станция смены бригады совпадает с конечной станцией на маршруте), то этот слот больше не должен участвовать в планировании.

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

Обновление состояния бригады



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

    1. Станция местоположения – станция смены бригады.

    2. Время доступности на станции местоположения – это время прибытия на станцию плюс время на смену бригады (атрибут norm_time из сообщения station).

    3. Оставшееся рабочее время:

      1. Если предыдущая станция местоположения являлась депо приписки бригады, то оставшееся рабочее время вычисляется по формуле , где Tprev – предыдущее оставшееся рабочее время, TR – время на перемещение локомотива до станции отправления бригадного слота, TT – время хода по бригадному слоту от станции отправления до станции смены бригады.

      2. Если предыдущая станция местоположения не являлась депо приписки бригады, то оставшееся рабочее время вычисляется по формуле , где Tprev – предыдущее оставшееся время работы, RT1 – время доступности, рассчитанное на шаге b, RTprev – предыдущее время доступности.

  2. Эти три атрибута должны рассчитываться одновременно и все вместе задают последнее актуальное состояние бригады: бригада доступна для планирования на станции местоположения, начиная с времени доступности, с вычисленным оставшимся рабочим временем.

Уход бригад на отдых в пунктах оборота

  1. Планирование ухода бригад на отдых в пунктах оборота должно выполняться после завершения очередной итерации планирования бригад.

  2. Бригада уходит на отдых, при выполнение условий описанных в разделе 1.9.3, а именно:

    1. В текущей итерации планирования бригада была доступной на какой-либо станции, но не была привязана к локомотиву.

    2. С момента доступности на станции и до времени завершения интервала текущей итерации планирования бригада находилась без работы больше некого порогового значения Т (изначально можно установить Т = 2 часа).

    3. Местоположение бригады не совпадает с ее депо приписки.

    4. Бригада еще не уходила на отдых.

  3. Если все условия выполняются, то должен фиксироваться уход бригады на отдых:

    1. Длительность отдыха должна рассчитываться в соответствии с указаниями, описанными в разделе 1.9.3.

    2. Отдых должен фиксироваться как участок маршрута в выходном сообщении slot_team (см. Приложение 1), в котором станция отправления и станция прибытия совпадают (и равны станции местоположения бригады), время отправления = времени доступности бригады на станции, время прибытия = время отправления + длительность отдыха, state = 4, loco = -1.

  4. Должно обновляться состояние бригады: станция местоположения меняться не должна, время доступности – это время прибытия из п. 3.b, оставшееся время работы – это нормативное время работы with_rest из сообщения team_work_region для участка обкатки бригады (см. Приложение 1).

Перемещение бригад пассажирами

Перемещение бригады пассажирами под локомотив



  1. Если в результате привязки бригады к бригадному слоту оказалось, что бригада доступна на станции, которая отличается от станции отправления слота, то требуется планировать пересылку бригады пассажирами.

  2. Для этого надо вычислить требуемое время прибытия бригады – это время отправления бригадного слота минус время на смену бригады на данной станции.

  3. Далее требуется вычислить ориентировочное время отправления бригады со станции местонахождения: из требуемого времени прибытия вычесть время хода между станциями.

  4. Получить маршрут бригады (список последовательных участков) между этими станциями.

  5. Составить фрагмент маршрута slot_team для пересылки пассажиром:

    1. В нем должны присутствовать все участки планирования между требуемыми станциями.

    2. Время отправления на первый участок должно совпадать с вычисленным в п.3 временем отправления, время прибытия – с вычисленным в п.2 временем прибытия.

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

    4. Время отправления с каждой следующей станции маршрута должно совпадать со временем прибытия.

    5. State = 0, loco = -1.

Перемещение бригады пассажирами в депо приписки

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

    1. В текущей итерации планирования бригада была доступной на какой-либо станции, но не была привязана к локомотиву.

    2. Местоположение бригады не совпадает с ее депо приписки.

    3. Бригада уже уходила на отдых.

    4. Бригада находилась на станции без работы (с момента доступности на станции и до времени завершения интервала текущей итерации планирования) больше времени отдыха.

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

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

1.10.3Сведение задачи прикрепления тяговых ресурсов к поездам к задаче оптимизации


В пункте 1.10.1 мы рассмотрели вид функций полезности для пар “i-й локомотивный (бригадный) слот – назначенный на него локомотив (бригада) xi.

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

Рассмотрим суммарную целевую функцию как многомерную функцию векторного аргумента X = [x1, x2, ... xm]Т, где вектор X - какое-либо решение задачи назначения локомотивов (бригад) на планы пересылки (с поездом или резервом), представленное в виде,

где (teami) – номер локомотива (бригады), назначенного на i-й слот, m — количество слотов на текущем участке планирования. Тогда для решения задачи оптимизации планирования железнодорожных перевозок необходимо решить общую задачу поиска экстремума вышеупомянутой функции с заданными ограничениями:





(3.)

где X* - искомое решение; – заданные ограничения; l – количество ограничений. Допустимым решением (планом) задачи называется такое решение задачи, которое удовлетворяет ее ограничениям для всех j = 1,…, l. Совокупность допустимых решений задачи называют областью допустимых решений (ОДР) D. Окончательным решением задачи является пара (X*, F*(X*)), состоящая из оптимального решения и оптимального значения целевой функции.

Поиск производится на множестве ограничений, связанных с технологическими особенностями в железнодорожном комплексе, например:



  • ограничение на количество локомотивов по дислокации

  • ограничение на пробег локомотива до ремонта

  • и др. (см. раздел 1.9)

Тогда необходимо найти такой вид итерационного оператора поиска экстремума функции F(X), чтобы итерационный процесс сходился к наилучшему решению или, другими словами, к экстремуму суммарной целевой функции.

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


1.10.3.1Сведение к задаче о назначениях


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

Имеется некоторое число работ (N) и некоторое число исполнителей (M) этих работ. Каждый исполнитель умеет выполнять некоторое количество P из этих работ (0≤P≤N), причем эффективность выполнения «своих» работ у исполнителя разная: некоторые работы он умеет выполнять лучше, некоторые – хуже. Требуется распределить работы между исполнителями так, чтобы суммарная эффективность назначения была максимальной.

Для каждой пары <работа, исполнитель> вводится «функция полезности» Uij – числовое выражение эффективности назначения данного исполнителя на данную работу. Таким образом, оптимизация в рамках данной задачи сводится к максимизации функции ΣUij по всем назначениям исполнителей на работы при условии, что каждый исполнитель назначен не более чем на одну работу.

Рассмотрим, как свести задачу привязки тяговых ресурсов (например, локомотивов) к поездам (локомотивным слотам) к задаче о назначениях:



  • В качестве «исполнителей» выберем ту сторону, предложение которой меньше на данной итерации планирования (например, на текущей итерации дефицит локомотивов, на которые требуется привязать локомотивные слоты). Тогда главным требованием задачи о назначениях будет обеспечение работами всех исполнителей (что будет эквивалентно привязки всех доступных локомотивов на локомотивные слоты).

  • В качестве «работ» возьмем оставшуюся сторону (в предложенном случае локомотивные слоты). Тогда условие, что «каждый исполнитель может выполнять некоторое количество работ» соответствует тому, что для каждого локомотива имеется выбор, к какому локомотивному слоту оказаться прикрепленным. При этом для некоторых пар <локомотивный слот, локомотив> прикрепление вообще невозможно (см. раздел 1.10.1.1 о формировании функции полезности).

Каталог: upload -> medialibrary
medialibrary -> Авиакомпания свяжет Хабаровск с приморским поселком Кавалерово Это направление включено в список субсидируемых государством маршрутов
medialibrary -> Число пассажиров региональной авиации Приморья приближается к 25 тысячам
medialibrary -> Россия выиграла разбирательство в международном арбитражном суде по иску немецкой компании Sana Consulting
medialibrary -> Перечень вопросов для подготовки к зачету по дисциплине «Операционные системы»
medialibrary -> 1. Рабочая программа Цели освоения дисциплины


Поделитесь с Вашими друзьями:
1   ...   6   7   8   9   10   11   12   13   ...   24




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница