Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Клеванский Н.Н. 1 Антипов М.А. 1

---

1 ФГБОУ ВО «Саратовский государственный аграрный университет имени Н.И. Вавилова»

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

Статья в формате PDF

0 KB

расписание

заявка

событие

транспортное расписание

жадный алгоритм

среднеквадратичное отклонение

методы ранжирования

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].

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

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

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

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

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

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

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

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

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

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

– (1)

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

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

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

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

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

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

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

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

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

; (2)

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

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

, (3)

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

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

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

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

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

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

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

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

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

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

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

, (4)

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

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

, (5)

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

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

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

(6)

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

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

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

(7)

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

, (8)

. (9)

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

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

, (10)

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

, (11)

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

.

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

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

, (12)

. (13)

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

. (14)

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

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

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

, (15)

. (16)

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

. (17)

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

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

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