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

INITIAL TIMETABLING PROBLEM FOR DEMAND VECTORS

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 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 basic criteria for choice operations are demanded – criterion of vehicle workload and criterion of resource equability. The realizations are used on set of train scheduling tasks. A numerical example of timetabling visualization is given. The visualization of transport timetable shows arrivals/departs across stations and lines.
timetable
demand
activity
transport timetable
greedy algorithm
ranking methods

В большинстве случаев расписание множества независимых друг от друга векторов действий является транспортным расписанием [1]. «Одним из представителей транспортных систем с достаточно жесткими ограничениями является железнодорожный транспорт с постоянным сезонным расписанием пассажирских поездов» [4]. Задача формирования расписания поездов в европейских публикациях рассматривается в двух видах: цикличном [9] и нецикличном [7].

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

К нецикличным расписаниям относят расписания пассажирских поездов дальнего следования и расписания грузовых поездов. Большинство моделей формирования нецикличных расписаний основаны на процедурах линейного программирования и приводят к задачам большой размерности, для решения которых используют эвристики, такие как релаксация по Лагранжу [8], генерация колонок [6], задача цеха [5].

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

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

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

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

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

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

Операции выбора в представляемых алгоритмах являются многокритериальными и для их реализации привлечен аппарат методов ранжирования [2].

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

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

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

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

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

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

F = {(s, l), s ∈ S, l ∈ L} – множество инцидентных пар – станция s является одной из двух граничных станций перегона l. Количество элементов множества F составляет nf = 2•J;

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

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

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

pic_77.wmf

Рис. 1. Схема расписаний для векторов заявок: а – расписание (вектор) i-го маршрута; б – расписание (вектор) j-го маршрута: в – спиральные представления расписаний пунктов остановок; г – события периодов расписания пункта остановки

Klevanskiy04.wmf (1)

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

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

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

Interval = 24•nd – интервал расписания, часы;

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

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

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

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

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

Klevanskiy10.wmf (2)

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

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

Klevanskiy12.wmf (3)

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

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

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

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

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

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

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

nit – количество включенных в начальное расписание поездов;

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

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

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

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

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

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

Klevanskiy15.wmf (4)

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

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

Klevanskiy16.wmf Klevanskiy17.wmf (5)

оценка загруженности j-го перегона по проходящим через него поездам

Klevanskiy18.wmf Klevanskiy19.wmf (6)

скалярная оценка загруженности k-го маршрута по суткам расписания

Klevanskiy20.wmf Klevanskiy21.wmf (7)

оценка равномерности события расписания i-й станции k1k,i,j

Klevanskiy22.wmf Klevanskiy23.wmf

Klevanskiy24.wmf Klevanskiy25.wmf (8)

где tiprec и tisuc – времена прибытия на i-ую станцию поездов, предшествующих и последующих по отношению ко времени tik,i,j в интервале расписания (рис. 2);

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

Klevanskiy26.wmf (9)

где

Klevanskiy27.wmf

q ∈ Qs – множество булевых обозначений событий станций;

оценка равномерности события расписания i-го перегона k3k,i,j

Klevanskiy28.wmf Klevanskiy29.wmf Klevanskiy30.wmf Klevanskiy31.wmf (10)

где tiprec и tisuc – времена начала движения поездов на i-м перегоне, предшествующие и последующие по отношению ко времени tik,i,j;

оценка равномерности распределения события ek,i,j в периодах расписания i-го перегона на въезде/выезде со станции

Klevanskiy32.wmf (11)

где

Klevanskiy33.wmf

q ∈ Ql – множество булевых обозначений событий перегона.

pic_78.tif

Рис. 2. Расписание событий расписания i-й станции/i-го перегона (въезд/выезд)

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

Klevanskiy35.wmf (12)

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

Klevanskiy36.wmf (13)

Klevanskiy37.wmf

Klevanskiy38.wmf (14)

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

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

Klevanskiy39.wmf (15)

Klevanskiy40.wmf (16)

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

Klevanskiy41.wmf (17)

Klevanskiy42.wmf (18)

Обратная сортировка выражений (7) порождает множество рангов маршрутов по загруженности суток интервала расписания:

Klevanskiy43.wmf (19)

Ранги (17), (18), (19) формируют множество векторов маршрутов:

Klevanskiy44.wmf (20)

Старший по рангу маршрут, полученный многокритериальным ранжированием векторов (20), является самым загруженным и становится очередным кандидатом rni+1 на включение в начальное расписание.

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

для tini+1,1 = 0 с шагом = 0,1 ч до 24 ч определение значений оценок (8)–(11) для перегонов и станций маршрута с накоплением множеств векторов с учетом ограничений (13), (14)

Klevanskiy45.wmf (21)

Klevanskiy46.wmf (22)

Klevanskiy47.wmf (23)

Klevanskiy48.wmf (24)

Многокритериальные ранжирования векторов (21), (22), (23), (24) формируют множества векторов рангов для начальных времен движения поездов маршрута rni+1

Klevanskiy49.wmf (25)

Многокритериальное ранжирование векторов (25) определяет начальное время TIni+1 движения поездов маршрута rni+1 в начальном расписании.

Для проверки корректности предлагаемых решений было разработано тестовое задание для пассажирского железнодорожного транспорта. Структура железнодорожной сети тестового задания (рис. 3) содержит сетевидные, паутинообразные и магистральные фрагменты сети. Нумерация станций и перегонов осуществлена случайным образом, поэтому можно положить эти номера их идентификаторами в базе данных. Тестовое задание имеет следующие характеристики: количество станций – 100; количество перегонов – 128; общее количество маршрутов – 100; количество поездов маршрутов – 471 в неделю.

pic_79.wmf

Рис. 3. Железнодорожная сеть тестового задания

pic_80.tif

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

pic_81.tif

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

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

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

Заключение

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

осуществлена формализация задачи формирования транспортного расписания;

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