ОПРЕДЕЛЕНИЕ ФУНКЦИИ ТРАНСПОРТНЫХ ЗАТРАТ В УЗЛАХ СЕТИ

Наумова Н.А.

Кандидат технических наук, доцент ФГБОУ ВПО «Кубанский государственный технологический университет»

Работа выполнена при поддержке РФФИ

ОПРЕДЕЛЕНИЕ ФУНКЦИИ ТРАНСПОРТНЫХ ЗАТРАТ В УЗЛАХ СЕТИ

Аннотация

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

Ключевые слова: сетевые потоки, функция транспортных затрат, обобщенное распределение Эрланга

Naumova N.A.

PhD in engineering, assosiate professor, Kuban State Technological University

THE DEFINITION OF THE FUNCTIONS OF TRANSPORT COSTS AT NODES

Abstract

A mathematical model of the transport network was developed. We introduced our classification of nodes as well as the criteria of efficiency of flows distribution.   A method for determining the function of transport costs in the case of the hypothesis on the distribution of time intervals between the requirements of the law by the generalized Erlang was deduced.

Keywords: transportation network, function of transport costs, generalized Erlang distribution.

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

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

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

В работах [2-4] автор предлагает следующую классификацию узловых точек (УТ).  Пусть одна часть потоков (назовем их главными) проходит через УТ беспрепятственно. Требования второй части потоков (второстепенных) ожидают возникновения достаточных интервалов по времени между требованиями главных потоков для пересечения УТ. Такую УТ названа узловой точкой первого типа.

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

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

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

Найдем среднее значение величины N_t – числа требований, прибывающих к данной точке дороги за интервал времени (0; t).  - функция восстановления  (математическое ожидание числа прибывающих за время t требований).

Функция распределения обобщенного закона Эрланга имеет вид:

  Преобразование Лапласа  функции плотности распределения  имеет вид  (причем, даже в случае совпадения некоторых из параметров ). Тогда преобразование функции простого процесса восстановления имеет вид [1]:

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

Таким образом,  можно разложить на простые дроби, содержащие члены:

1)  от полюса s = 0;

2)  от ненулевых полюсов в точках, являющихся корнями уравнения . Причем это уравнение кроме действительных  может иметь только попарно сопряженные комплексные корни, действительная часть которых  [1].

Рассмотрим вид функции  в случае обобщенного закона Эрланга порядков .

I случай)

II cлучай) .

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

III cлучай) .

 

Левая часть последнего уравнения представляет собой многочлен третьей степени, корни которого могут быть найдены с помощью формулы Кардано.

Таким образом, изображение функции восстановления имеет вид:

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

       Каждому простому действительному корню  соответствует  дробь  (слагаемое в ),  а ей, в свою очередь, соответствует оригинал  (слагаемое в ).

       Действительному корню кратности 2 соответствует в разложении сумма  (слагаемые в ). Следовательно, оригинал имеет вид:  (слагаемые в ).

       Каждой паре комплексно-сопряженных корней  соответствует дробь в разложении  (слагаемые в ). В этом случае оригинал имеет вид:  (слагаемые в ).

Таким образом функция восстановления в случае обобщенного закона Эрланга имеет вид:

Введем ряд обозначений, принятых автором при разработке математической модели функционирования сети.  Дуга представляет собой часть многоканальной магистрали, заключенную между двумя вершинами (узловыми точками). Обозначим  - множество дуг графа,  - множество вершин (узловых точек). Для определения показателей эффективности распределения потоков по сети и решения оптимизационных задач введем следующие понятия:

1) - средняя задержка в узловой точке  требования выбранного направления;

2) - вес  вершины (узловой точки) для  потока данного направления, то есть средняя суммарная задержка всех требований потока данного направления в узловой точке  в единицу времени;

3)  - вес  вершины (узловой точки), то есть средняя суммарная задержка всех требований   в узловой точке  в единицу времени.

Под задержкой в УТ второго типа будем понимать время простоя в случае, если движение в данном направлении запрещено.

  (треб.∙с.) - суммарная задержка требований рассматриваемого потока за  Т_i секунд - время, в течение которого запрещено движение в рассматриваемом направлении. Простое аналитическое задание функции в случае обобщенного распределения Эрланга позволяет элементарно получить значение функции .

Суммарная задержка всех требований данного потока за единицу времени – один час, выражается следующим образом :

 (треб.∙ч.), где    .

       Уточним параметры качества распределения потоков для узловой точки  II типа, которые представляют собой функции транспортных затрат:

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

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

3) .

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