Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

ОПТИМИЗАЦИЯ НАЧАЛЬНЫХ ТРАНСПОРТНЫХ РАСПИСАНИЙ

Клеванский Н.Н. 1 Антипов М.А. 1
1 ФГБОУ ВО «Саратовский государственный аграрный университет имени Н.И. Вавилова»
В статье представлены основные концепции и подходы в реализации задач транспортных расписаний. Процедура транспортного планирования использует двухэтапный алгоритм, реализованный в среде СУБД. Получение начального расписания на первом этапе с использованием критерия наилучшего распределения ресурсов является базовым для следующего этапа оптимизации. Каждый этап включает две эвристические процедуры получения решений на базе идеологии жадных алгоритмов, использующих многокритериальное ранжирование. Предложены основные критерии в задачах выбора при формировании и оптимизации транспортных расписаний – критерии загруженности и равномерности. Последний критерий представлен среднеквадратичным отклонением от среднего интервала между событиями расписания. Представлены результаты численной реализации транспортного планирования на базе тестового задания для пассажирских поездов дальнего следования.
расписание
заявка
событие
транспортное расписание
жадный алгоритм
среднеквадратичное отклонение
методы ранжирования
1. Клеванский Н.Н. Основные концепции реализации задач формирования расписаний // Образовательные ресурсы и технологии. – М., 2014. – № 2 (5). – С. 9–21.
2. Клеванский Н.Н. Методы ранжирования в задачах формирования расписаний // Труды XII Всероссийского совещания по проблемам управления – ВСПУ-2014. Москва 16–19 июня 2014 г. С. 8040–8050.
3. Клеванский Н.Н., Антипов М.А. Формирование начальных расписаний для векторов заявок // Современные наукоемкие технологии – 2016. – № 10–1. – С. 79–85.
4. Клеванский Н.Н., Красников А.А., Антипов М.А. Когнитивная визуализация в задачах расписаний // Современные наукоемкие технологии – 2016. – № 3–2. – С. 246–251.
5. Лазарев А.А., Мусатова Е.Г., Гафаров Е.Р., Кварацхелия А.Г. Теория расписаний. Задачи управления транспортными системами. – М., Физический факультет МГУ, 2012. – 159 с.
6. Burdett R. and E. Kozan. A sequencing approach for creating new train timetables, OR Spectrum, 2010. 32 (1), pp. 163–193.
7. Caprara A., M. Fischetti and P. Toth. Modeling and solving the train timetabling problem, Operations Research, 2002, 50 (5) pp. 851–861.
8. Hansen I.A.; Pachl J. (eds.): Railway Timetabling & Operations. Analysis – Modelling – Optimisation – Simulation – Performance Evaluation. 2nd edition. Eurailpress 2014, 332 p.
9. Harrod S.S. A tutorial on fundamental model structures for railway timetable optimization, Surveys in Operations Research and Management Science, 2012, 17 (2), pp. 85–96.

Двухэтапный процесс формирования транспортного расписания включает определение начального расписания и последующую его оптимизацию [1]. Под начальным расписанием понимается программно сформированное расписание при соблюдении обязательных ограничений, а его реализация представлена в [3]. Для оптимизации транспортных расписаний (NP-полной задачи) и, в частности, железнодорожных используются различные подходы, прежде всего в форме эвристик [5–9].

Целью статьи является представление эвристических методов оптимизации начального расписания движения пассажирского железнодорожного транспорта дальнего следования.

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

Введем необходимые в математическом моделировании расписания обозначения.

Исходные данные задачи:

klev01.wmf – множество станций железнодорожной сети;

klev02.wmf – множество перегонов железнодорожной сети;

klev03.wmf – минимальный интервал времени между двумя поездами при выезде/въезде с j-го перегона на i-ую станцию;

klev04.wmf – количество платформ для высадки/посадки пассажиров i-ой станции;

klev05.wmf – множество инцидентных пар – станция s является одной из двух граничных станций перегона l. Количество элементов множества F составляет klev06.wmf;

nr – количество маршрутов железнодорожной сети;

klev07.wmf – множество векторов заявок маршрутов;

klev08.wmf – количество станций маршрута rk;

klev09.wmf – (1)

вектор заявок маршрута rk – последовательность пар перегон/станция от начальной станции до конечной;

nd – количество суток интервала расписания;

klev10.wmf – упорядоченный во времени вектор суток;

klev11.wmf – интервал расписания, часы;

nk – количество суток отправления поездов k-ого маршрута;

klev12.wmf – множество суток отправления поездов маршрутов;

klev13.wmf – количество поездов расписания;

klev14.wmf – множество инцидентных пар, частично формирующих заявки поездов маршрутов – поезд маршрута r отправляется с начальной станции в день day;

используя (1), получаем множество заявок поездов маршрутов:

klev15.wmf; (2)

klev16.wmf – заявка на прохождение маршрута k по i-ому перегону на i-ую станцию, где klev17.wmf – интервал времени движения от i-1-ой до i-ой станции;

заявка на прохождение поезда klev18.wmf по i-ому перегону на i-ую станцию

klev19.wmf, (3)

где klev20.wmf принимается равным дню отправления поезда маршрута.

Исходные расчетные данные задачи:

klev21.wmf – количество поездов, проходящих через i-ую станцию;

klev22.wmf – количество поездов, проходящих через j-ой перегон.

Переменные задачи:

klev23.wmf – количество оптимизированных (переставленных) маршрутов в расписании;

klev24.wmf – количество не оптимизированных маршрутов в расписании;

ti, tf – время прибытия/отправления поездов на станцию;

til, tfl – время выезда поездов на перегон и с перегона;

klev25.wmf – время отправления поездов маршрута rk с начальной станции, klev26.wmf;

событие расписания, порождаемое заявкой (3), по прохождению поезда klev27.wmf маршрута rk по i-ому перегону на i-ую станцию будет определяться следующим выражением:

klev28.wmf, (4)

klev29.wmf и klev30.wmf в (4) определяются на каждом шаге формирования расписания;

оценка равномерности распределения событий i-ой станции в интервале расписания

klev31.wmf, (5)

где klev32.wmf – среднее значение интервала между прибытиями поездов на i-ую станцию;

klev33.wmf – величина интервала между прибытиями на станцию двух ближайших по времени поездов. Для klev34.wmf;

оценка равномерности распределения событий i-ого перегона в интервале расписания

klev35.wmf (6)

где klev36.wmf – среднее значение интервала между началами движения поездов по i-ому перегону;

klev37.wmf – величина интервала между началами движения поездов по i-ому перегону двух ближайших по времени поездов. Для klev38.wmf.

Задача оптимизации начального расписания состоит в цикличном выборе очередного маршрута klev39.wmf и формировании расписания klev40.wmf, которое минимизирует векторы оценок равномерности событий станций и перегонов

klev41.wmf (7)

при обязательных ограничениях

klev42.wmf, (8)

klev43.wmf. (9)

Целевая функция (7) обеспечивает многокритериальную минимизацию оценок равномерности. Ограничения (8) предотвращают одновременное нахождение поездов на станции более количества путей с пассажирскими платформами. Ограничения (9) отражают соблюдение интервала между последовательными выездами/въездами поездов.

Оценки равномерности распределения событий станций (5) и перегонов (6) в интервале расписания сети формируют множество первых и вторых векторных компонент равномерности маршрутов на очередном шаге оптимизации начального расписания

klev44.wmf, (10)

где klev45.wmf – коэффициент важности оценки, klev46.wmf;

klev47.wmf, (11)

где klev48.wmf – коэффициент важности оценки,

klev49.wmf.

Необходимо отметить, что

klev50.wmf

Многокритериальное ранжирование векторов (10) и (11) порождает множества рангов маршрутов по равномерности станций и перегонов

klev51.wmf, (12)

klev52.wmf. (13)

Ранги (12, 13) формируют множество векторов (критериев равномерности) маршрутов

klev53.wmf. (14)

Старший по рангу маршрут, полученный многокритериальным ранжированием векторов (14), является самым неравномерным при принятых оценках и критериях равномерности. Он становится очередным кандидатом klev54.wmf на перестановку в расписании.

Для определения времени отправления с начальной станции klev55.wmf поездов маршрута klev56.wmf циклично выполняются следующие действия:

для klev57.wmf с шагом = 0,1 часа до 24 часов определение значений оценок (5, 6) для перегонов и станций маршрута с накоплением множеств векторов с учетом ограничений (8, 9):

klev58.wmf, (15)

klev59.wmf. (16)

Многокритериальные ранжирования векторов (15, 16) формируют множества векторов рангов для начальных времен движения поездов маршрута klev60.wmf:

klev61.wmf. (17)

klev1.tif

Рис. 1. Расписания въезда/выезда с перегона на граничные станции: klev1aa.wmf – выезд на перегон; klev1bb.wmf – въезд на станцию

klev2.tif

Рис. 2. Расписание въезда поездов на станцию: klev2aa.wmf – с одного перегона; klev2bb.wmf – двух поездов с разных перегонов

klev3.tif

Рис. 3. Расписания въезда/выезда с перегона на граничные станции

klev4.tif

Рис. 4. Расписание въезда поездов на станцию

Многокритериальное ранжирование векторов (17) определяет начальное время klev62.wmf движения поездов маршрута klev63.wmf в оптимизированном расписании железнодорожной сети.

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

На рис. 1 и 2 представлены визуализированные результаты формирования начального расписания железнодорожной сети для самого загруженного перегона и станции [3].

Для расписаний станций и перегонов использованы представления, в которых спираль является осью времени с отсчетом от ее начала, а длина спирали соответствует интервалу расписания [4]. Виток спирали – наименьший период расписания. Пометками на спирали фиксируется прибытие/отправление транспортного средства. На рис. 2 в верхнем правом углу указано среднеквадратичное отклонение событий расписания станции в %.

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

Сопоставление рис. 2 и 4 показывает более чем двукратное улучшение среднеквадратичного отклонения событий станции. Сопоставление рис. 1 и 3 менее оптимистично с визуальной точки зрения.

Авторы считают, что в данной работе новыми являются следующие положения и результаты:

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

Библиографическая ссылка

Клеванский Н.Н., Антипов М.А. ОПТИМИЗАЦИЯ НАЧАЛЬНЫХ ТРАНСПОРТНЫХ РАСПИСАНИЙ // Современные наукоемкие технологии. – 2016. – № 11-2. – С. 264-269;
URL: https://top-technologies.ru/ru/article/view?id=36397 (дата обращения: 28.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674