Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,252

THE METHOD OF DETERMINING THE FUNCTIONS OF TRANSPORT COSTS FOR NODES TYPE «UNREGULATED CROSSING STREAMS REQUIREMENTS»

Naumova N.A. 1
1 Kuban State Technological University
Моделирование транспортных сетей с целью оптимизации распределения транспортных потоков – актуальная задача. Сложность численного решения оптимизационных задач на сети в основном зависит от аналитического задания функции транспортных затрат. Автором разработана математическая модель транспортной сети, базирующаяся на гипотезе о распределении интервалов по времени между требованиями по обобщенному закону Эрланга; предложена классификация узловых точек. Приведен вывод формулы для вычисления средней задержки требования в узловой точке сети, в которой происходит нерегулируемое пересечение многоканальных магистралей. В зависимости от целей оптимизации в качестве функции транспортных затрат в такой узловой точке предлагается брать вес вершины, суммарный вес вершины или среднюю задержку требований в вершине. Получены соответствующие аналитические реализации функции транспортных затрат.
Modeling of transport networks with the aim of optimizing the traffic flow distribution is a vital task. The complexity of the numerical solution of optimization problems on networks mainly depends on the analytical form of functions of transport costs. The mathematical model of the transport network based on the hypothesis about the distribution of intervals of time between the requirements of generalized Erlang law was developed. We introduced our classification of nodes as well as the criteria of efficiency of flows distribution. The formula for the calculation of the average latency requirements in the nodes, which is unregulated crossing multichannel highways, was deduced. Analytical implementation of the functions of the transport costs was obtained.
mathematical model
network
node
generalized Erlang distribution
function of transport costs
unregulated crossing streams
1. Ventsel E.S., Ovcharov L.A. Teoriya sluchaynyh protsessov i ee inzhenernye prilozheniya [Theory of random processes and their application in engineering],Vysshaya Shkola Publishing House, Moscow, 2000.
2. Gasnikov A.V., Klenov S.L., Nurminskiy E.A., Holodov Y.A., Shamray N.B. Vvedenie v matematicheskoe modelirovanie transportnyh potokov [Introduction to mathematical modeling of traffic flows]. Moscow, MPhTI,2010. 362 p.
3. Naumova N. А.Metod opredeleniya funktsii transportnyh zatrat v uzlovyh tochkah seti [The method of determining functions of transport costs at the nodal points in the network]. Fundamentalnye issledovaniya – Fundamental research, 2013, no 8 (part 4), pp. 853–857.
4. Cox D.R., Smith W.L., Queues, Methuen, London, 1961.
5. Naumova N.А., Problems of Optimisation of Flows Distribution in the Network, Applied Mathematics, Vol. 3 no. 1, 2013, pp. 12–19. doi: 10.5923/j.am.20130301.02.
6. Naumova N., Danovich L. «Modelling and Optimisation of Flows Distribution in the Network», Applied Mathematics, Vol. 2 no. 5, 2012, pp. 171–175. doi: 10.5923/j.am. 20120205. 04.

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

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

1. Граф-представление транспортной сети

Конкретизируем основные понятия, используемые в данной работе. Назовем сетевые потоки неконфликтными, если на данном участке сети они не пересекаются, и конфликтными – в противном случае. Вершинами графа будем считать узловые точки – точки, в которых либо расположены источники или потребители информации, либо происходит пересечение конфликтных потоков. То есть узловые точки образуются пересечением многоканальных магистралей. В работах [3, 5, 6] автор предлагает следующую ниже классификацию узловых точек (УТ).

Пусть одна часть потоков (назовем их главными) проходит через УТ беспрепятственно. Требования второй части потоков (второстепенных) ожидают возникновения достаточных интервалов по времени между требованиями главных потоков для пересечения УТ. Такая УТ названа узловой точкой первого типа или «нерегулируемое пересечение потоков требований».

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

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

2. Метод определения функции транспортных затрат для узловой точки сети типа «нерегулируемое пересечение потоков требований»

2.1. Обобщенный закон Эрланга распределения случайной величины

При обобщенном распределении Эрланга [4] интервал по времени между подряд идущими требованиями проходит k стадий T0, T1, ..., Tk–1, причем длительности этих стадий имеют показательные распределения с параметрами λ0, λ1, ..., λ k–1 соответственно. Преобразование Лапласа функции плотности распределения fk(t) имеет вид

Eqn49.wmf

Если все параметры λi различны, функция распределения обобщенного закона Эрланга имеет вид

Eqn50.wmf

где Eqn51.wmf причем Eqn52.wmf

Интегральная функция распределения

Eqn53.wmf

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

Eqn54.wmf

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

Eqn55.wmf

n-й начальный момент:

Eqn56.wmf

2.2. Расчет среднего значения времени обслуживания требований в узловой точке I типа при справедливости гипотезы о распределении интервалов по времени по обобщенному закону Эрланга

Пусть требованию второстепенного потока для продолжения движения требуется пересечь L главных потоков в условиях УТ I типа. Допустим, интервалы во времени в пересекаемых потоках распределены по обобщенному закону Эрланга k1, k2, ..., kL порядков с параметрами Eqn57.wmf Eqn58.wmf Eqn59.wmf соответственно. Учтем, что требование прибывает к УТ в случайный момент времени, независимо от требований остальных потоков. Обозначим через T0 минимальный временной интервал между подряд идущими требованиями в конфликтном потоке, который необходим требованию второстепенного потока для продолжения движения.

Пусть t – случайно выбранный нами момент времени и пусть Т* – интервал между двумя соседними случайными событиями, на который попала случайная точка t.

Т* = Q + R,

где R – время, оставшееся до наступления следующего события, а Q – время, прошедшее после последнего поступившего требования.

Тогда, согласно теории случайных процессов [1], вероятности того, что время Q, прошедшее после последнего прибытия требования, и время R, оставшееся до очередного прибытия, меньше некоторого наперед заданного значения Т0, выражаются формулами:

Eqn60.wmf

Следовательно, вероятность того, что за время Т0 не прибудет ни одно требование:

Eqn61.wmf

Числовые характеристики случайных величин Q и R: математическое ожидание:

Eqn62.wmf

Eqn63.wmf

Теорема. Пусть в узловой точке первого типа требованию в потоке второстепенного направления необходимо пересечь L потоков главного направления; Eqn64.wmf – параметры обобщенного закона Эрланга для j-го пересекаемого потока, j = 1, 2, ..., L; T0 – минимальный временной интервал между подряд идущими требованиями в конфликтном потоке, который необходим требованию второстепенного потока для продолжения движения. Тогда для первого требования во второстепенном потоке среднее время обслуживания равно

Eqn65.wmf

где Eqn66.wmf

Eqn67.wmf

Доказательство.

Рассмотрим величину Eqn68.wmf, где T1 = R1 – время, оставшееся до прибытия очередного требования в первом пересекаемом потоке главного направления (поток (1)); Ti, i = 2, 3, 4, ... – интервал между прибытиями (i – 1)-го и i-го требований в потоке (1); X – целочисленная случайная величина, равная числу требований потока (1), которые необходимо пропустить, прежде чем продолжить движение (очевидно, что X = m, когда первые m временных интервалов меньше необходимого времени, а следующий (m + 1)-й уже больше Т0).

Введем следующие случайные величины:

Eqn69.wmf

Eqn70.wmf i = 1, 2, 3, …

Здесь Eqn71.wmf – временной интервал в j-м потоке, оставшийся до прибытия (i + 1)-го требования в потоке (1). Функция распределения случайной величины Yj j = 1, 2, 3, ...имеет вид [1]:

Eqn72.wmf

где Fi(y) – функция распределения i-й случайной величины.

Следовательно, функция распределения случайной величины Eqn69.wmf:

Eqn73.wmf

Функции распределения случайных величин Eqn70.wmf i = 1, 2, 3, … совпадают и имеют вид:

Eqn74.wmf

Следовательно,

Eqn75.wmf

Eqn76.wmf.

То есть

Eqn77.wmf

Eqn78.wmf

Eqn79.wmf при m ≥ 2.

Продолжим вычисления:

Eqn80.wmf

Eqn81.wmf

Теорема доказана

Узловая точка I-го типа может быть представлена как система массового обслуживания с неограниченной очередью. Поток заявок – это поток требований второстепенного потока, прибывающий к узловой точке; время обслуживания – время, проведенное требованием в ожидании возможности продолжить движение. Ранее [6] автором с применением метода псевдосостояний было доказано, что средняя задержка требования второстепенного потока в узловой точке I-го типа

Eqn82.wmf

где Eqn83.wmf

2.3. Функция транспортных затрат для узловой точки I-го типа

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

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

1) Eqn84.wmf – вес вершины zn (узловой точки) для потока данного направления;

2) μ(zn) – суммарный вес вершины zn (узловой точки);

3) μM(zn) – средняя задержка требования выбранных направлений.

Для узловой точки I типа

1) Eqn85.wmf, где М – множество выбранных направлений;

2) Eqn86.wmf, где Ω – множество всех направлений движения требований через данную УТ;

3) Eqn87.wmfгде М – множество выбранных направлений.

Заключение

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

Работа выполнена при поддержке РФФИ, проект р-юг-а-13-08-96502.

Рецензенты:

Атрощенко В.А., д.т.н., профессор, декан факультета компьютерных технологий, ФГБОУ ВПО «Кубанский государственный технологический университет» Министерства образования и науки РФ, г. Краснодар;

Видовский Л.А., д.т.н., профессор, заведующий кафедрой вычислительной техники и автоматизированных систем управления, ФГБОУ ВПО «Кубанский государственный технологический университет» Министерства образования и науки РФ, г. Краснодар.

Работа поступила в редакцию 05.09.2013.