Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

INITIAL TRANSPORT TIMETABLE OPTIMIZATION

Klevanskiy N.N. 1 Antipov M.A. 1
1 Saratov State Agrarian University named after N.I. Vavilov
In the paper basic concepts for transport scheduling problem are presented. The visualization of transport timetable shows arrivals/departs across stations and lines. The transport scheduling procedure can be solved efficiently by two-stage algorithm developed in database system. The first, a set of demands must be developed as initial timetables. A set of local and global resources are available for carrying out the activities of the systems. The solutions obtained by the first stage algorithm with the best resource allocation rule are used as a baseline to compare those obtained by the latter. The second, the initial timetables must be optimized. Each stage consists of two heuristic solution-finding procedures based on greedy ideology. The greedy algorithms use multi-criteria ranking of decision support theory. The algorithm introduces the concept of an adjustable resource allocation factor which can be used to produce schedules. The realizations are used on set of train scheduling tasks. The basic criterion for optimization operations is demanded – criterion of resource equability. The latter is equal a root-mean-square deviation from a middle value between timetable events. A numerical example of timetabling visualization is given.
timetable
demand
activity
transport timetable
greedy algorithm
root-mean-square deviation
ranking methods

Двухэтапный процесс формирования транспортного расписания включает определение начального расписания и последующую его оптимизацию [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 менее оптимистично с визуальной точки зрения.

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

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