Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

ЗАДАЧИ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕНИЯ ПОТОКОВ В УЗЛАХ СЕТИ

Наумова Н.А. 1
1 ФГБОУ ВПО «Кубанский государственный технологический университет» Министерства образования и науки РФ
Предложена вероятностная модель транспортного потока, базирующаяся на гипотезе о распределении интервалов по времени между подряд идущими автомобилями по закону Эрланга, который позволяет описывать потоки высокой плотности. Разработано граф-представление модели, а также приведена структура матриц, хранящих всю необходимую информацию о потоках на сети для аналитической реализации модели. Приведена классификация узловых точек сети. Предложены критерии оптимизации распределения потоков в узлах сети. Разработан алгоритм численного решения задачи определения оптимальных параметров регулирования для узловой точки II типа. С учетом граф-представления модели предложен методы определения оптимальной (из числа заданных) схемы распределения потоков по сети. Предлагаемая модель, ее граф-представление и методы решения оптимизационных задач могут быть применены не только к автотранспортной сети, но и к любой сетевой структуре при надлежащем выборе способа определения параметров распределения Эрланга.
транспортная сеть
сетевые потоки
математическая модель
граф-представление
узловая точка
оптимизация
1. Наумова Н.А. Моделирование и программная реализация движения автотранспортных средств по улично-дорожной сети: монография / Н.А. Наумова, Л.М. Данович. – Краснодар: Издательский Дом – Юг, 2011. – 80 с.
2. Домбровский А.Н. Транспортные потоки на улично-дорожной сети городов: моделирование и управление: монография / А.Н. Домбровский, Н.А. Наумова; – Краснодар: Издательский Дом – Юг, 2012. – 124 с.
3. Cox D.R., Smith W.L., Queues, Methuen, London, 1961.
4. Drew D.R. Traffic Flow Theory and Control, McGraw-Hill Book Company. – New York, 1968.
5. Inose H., Hamada T., Road Traffic Control, University of Tokyo Press. – Tokyo, Japan, 1975.

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

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

Представление транспортной сети в виде графа

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

Eqn18.wmf (1)

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

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

Рассмотрим узловую точку (УТ), в которой пересечение конфликтных потоков происходит следующим образом: одна часть потоков (назовем их главными) проходит через УТ беспрепятственно; требования второй части потоков (второстепенных) ожидают возникновения достаточных интервалов по времени между требованиями главных потоков для пересечения УТ. Назовем такую УТ узловой точкой первого типа (УТ I типа).

Узловую точку (УТ), в которой для возможности ее пересечения поочередно перекрывается движение для одной из групп неконфликтных потоков на фиксированное время Ti, назовем узловой точкой второго типа (УТ II типа).

Пусть {li} – множество дуг графа, {zi} – множество вершин (узловых точек). Дуга представляет собой часть многоканальной магистрали, заключенную между двумя вершинами (узловыми точками). Присвоим магистралям сети идентификационные номера WAY_i, i ∈ N. В этом случае

Eqn19.wmf.

Тогда можно представить граф с помощью следующих связанных матриц:

I. Eqn20.wmf

1) № – номер строки матрицы ASTREETS соответствует номеру дуги графа, соединяющей узловые точки I и II; количество строк соответствует количеству дуг графа;

2) S1 и S2 – пересекающиеся магистрали, образующие вершину I графа;

3) S3 и S4 – пересекающиеся магистрали, образующие вершину II графа;

4) Contr – тип узловой точки;

5) Pr – наличие приоритета (главная или второстепенная магистраль);

6) Len – длина дуги между узловыми точками;

7) Col – количество потоков на дуге;

8) AL – допустимость поворота налево из направления А в вершине II;

9) AS – допустимость движения прямо из направления А вершине II;

10) AR – допустимость поворота направо из направления А вершине II;

11) λА1, λА2 и т.д. – параметр λ в направлении А;

12) kA1, kA2 и т.д. – параметр k в направлении А;

13) BL – допустимость поворота налево из направления В вершине I;

14) BS – допустимость движения прямо из направления В вершине I;

15) BR – допустимость поворота налево из направления В вершине I;

16) λВ1, λВ2 и т.д. – параметр λ в направлении В.

17) kB1, kB2 и т.д. – параметр k в направлении В.

II. Eqn21.wmf

1) № строки совпадает с номером дуги графа, соединяющей узловые точки I и II в матрице ASTREETS ;

2) S1 и S2 – пересекающиеся магистрали, образующие вершину I графа;

3) λCline1, λCline2 и т.д. –параметр λ потоков, входящих в вершину I в направлении С магистрали, пересекающей данную дугу графа в узловой точке I;

4) kC line1, kC line2 и т.д. – параметр k потоков, входящих в вершину I в направлении С магистрали, пересекающей данную дугу графа в узловой точке I;

5) λD line1, λD line2 и т.д. – параметр λ потоков, входящих в вершину I в направлении D магистрали, пересекающей данную дугу графа в узловой точке I;

6) kD line1, kD line2 и т.д. – параметр k потоков, входящих в вершину I в направлении D магистрали, пересекающей данную дугу графа в узловой точке I.

Определение оптимального распределения потоков в узловой точке

Рассмотрим следующую задачу: определить оптимальное (из множества

Eqn22.wmf

известных способов) распределение потоков для данной вершины Eqn23.wmf

Критерием оптимизации, в зависимости от преследуемой цели, может служить:

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

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

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

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

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

2) Eqn26.wmf где Ω – множество всех направлений;

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

Здесь принято обозначение: Wн – средняя задержка (в секундах) в УТ одного требования второстепенного направления в потоке с параметрами распределения λ и k:

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

1) Eqn28.wmf где М – множество выбранных направлений, a ∈ {1; 2};

2) Eqn29.wmf

3) Eqn30.wmf где М – множество выбранных направлений, a ∈ {1; 2}.

Здесь приняты обозначения:

Eqn31.wmf (треб.∙с.) – суммарная задержка всех требований данного потока за один цикл регулирования T = T1 + T2;

H(t) – число требований, прибывающих к данной точке дороги за интервал времени (0; t).

Пусть задана вершина Eqn23.wmf (с точностью до порядка Str1 и Str2). Информация о входящих потоках содержится в матрицах ASTREETS и BINTERSECTION.

Лемма 1. Параметры распределения Эрланга, входящих в вершину Eqn23.wmf потоков, заданы:

1) в матрице ASTREETS в строке

Eqn32.wmf – направление В;

2) в матрице BINTERSECTION в строке (BINTERSECTION)i в направлениях С и D;

3) в матрице ASTREETS в строке

Eqn33.wmf – в направлении А.

Оптимальное распределение потоков в узловой точке является решением задачи (в зависимости от преследуемой цели):

1) Eqn34.wmf

2) Eqn35.wmf

3) Eqn36.wmf

Выбор оптимальных параметров регулирования для узловой точки II типа

Поставим следующую задачу оптимизации функционирования узловой точки II типа: минимизировать суммарную часовую задержку μ(zn) всех требований в данном узле. При этом для каждого потока должно выполняться условие отсутствия затора:

Eqn37.wmf i = 1, 2, ..., n1; (2)

Eqn38.wmf j = 1, 2, ..., n2, (3)

где n1 – число потоков магистрали № 1; n2 – число потоков магистрали № 2. Кроме этого необходимо выполнение условия: T ≥ 2M, где М – минимальное время (в секундах), необходимое требованию для пересечения узловой точки II типа.

Задача математического (нелинейного) программирования имеет вид:

Eqn39.wmf (4)

Eqn40.wmf (5)

В результате следует получить оптимальные значения параметров регулирования T1, T2.

Алгоритм численного решения задачи (4–5) зададим как релаксационный процесс – процесс построения последовательных приближений M1, M2, ..., Mk, ... таких, что Mi ∈ Ω и Z(Mk+1) < Z(Mk).

1-й шаг. Задаем начальные значения:

Eqn41.wmf

и 

Eqn42.wmf

и значения для завершения алгоритма εp = 0,01; εT = 0,5; εZ = 0,1.

2-й шаг. Находим численно (например, методом половинного деления) решение уравнения Eqn43.wmf, соответствующего условию Eqn44.wmf

3-й шаг. Проверяем выполнение остальных неравенств системы ограничений:

Eqn45.wmf i = 1, 2, ..., n1;

Eqn46.wmf j = 1, 2, ..., n2.

4-й шаг. Если условия шага 3 выполнены, вычисляем Eqn47.wmf и переходим к шагу 5.

Если условия шага 3 не выполнены, то находим численно (например, методом половинного деления) решение T*1 уравнения Eqn48.wmf соответствующего условию Eqn49.wmf; проверяем выполнение остальных неравенств системы ограничений:

Eqn50.wmf i = 1, 2, ..., n1;

Eqn51.wmf j = 1, 2, ..., n2.

Затем вычисляем Eqn47.wmf и переходим к шагу 5.

5-й шаг. Приняв T = T*1 (начальное значение Eqn52.wmf) находим численно решение Eqn53.wmf уравнения:

Eqn54.wmf

Тогда новое значение Eqn55.wmf.

6-й шаг. Повторяем шаги 2–4 до тех пор, пока ΔZ < εz, Δp < εp, ΔT < εT.

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

Eqn56.wmf

Определение критических значений параметров распределения Эрланга для узловой точки II типа

Как отмечено выше, «затор» в УТ II типа не образуется при выполнении условий (2‒3). В случае распределения интервалов по времени по закону Эрланга (1) данные условия равносильны следующей системе неравенств:

Eqn57.wmf (6)

Так как

Eqn58.wmf,

то приближенное решение системы относительно параметра λ (при известном параметре k) следующее:

Eqn59.wmf (7)

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

Eqn60.wmf

или

Eqn61.wmf (8)

Определение оптимальной (из числа заданных) схемы распределения потоков по сети

Пусть задан подграф {zn}n∈V, подлежащий реорганизации. Возможные варианты реорганизации распределения потоков на сети должны быть отражены в матрицах (ASTREETS)i и (BINTERSECTION)i , i ∈ K.

Если цель реорганизации – сведение к минимуму задержек в узловых точках, то критерий оптимизации – сумма весов узловых точек:

Eqn62.wmf

Оптимальная схема распределения потоков по сети является решением задачи:

Eqn63.wmf

Если цель реорганизации – оптимизация движения потоков по данному маршруту (V, D) сети, то в качестве целевой функции следует взять

Eqn64.wmf

– вес маршрута, то есть время, затраченное на прохождение данного маршрута.

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

μi(lj) – вес дуги lj для потока данного направления;

D – множество дуг маршрута;

V – множество вершин маршрута.

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

Eqn66.wmf

Заключение

Рассмотренные выше оптимизационные задачи базируются на гипотезе о распределении интервалов по времени между следующими подряд требованиями по закону Эрланга. Для транспортных потоков адекватность данной гипотезы проверена автором экспериментально. В работах [1–2] подробно рассматривается построение математической модели, построенной на гипотезе об эрланговском распределении интервалов по времени и ее аналитической реализации. Одной из положительных сторон модели является минимальное количество исходных данных, требующихся для расчетов показателей качества функционирования сети. Предложенное в данной работе граф-представление транспортной сети позволяет решать задачи по оптимизации распределения сетевых потоков. При наличии базы данных для конкретного участка улично-дорожной сети, построенной в соответствии со структурой матриц ASTREETS и BINTERSECTION, нетрудно осуществить компьютерную реализацию алгоритмов решения этих задач, например, в среде DELPHI.

Рецензенты:

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

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

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


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

Наумова Н.А. ЗАДАЧИ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕНИЯ ПОТОКОВ В УЗЛАХ СЕТИ // Фундаментальные исследования. – 2012. – № 11-4. – С. 936-941;
URL: http://www.fundamental-research.ru/ru/article/view?id=30687 (дата обращения: 21.11.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074