Інформаційно-аналітичні системи обробки даних И. В. Максимей, Е. И. Сукач, П. В. Гируц - shikardos.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Інформаційно-аналітичні системи обробки даних И. В. Максимей, Е. И. Сукач, П. В. - страница №1/1


Інформаційно-аналітичні системи

обробки даних

УДК 681.3
И. В. Максимей, Е. И. Сукач, П. В. Гируц

Гомельский государственный университет им. Ф.Скорины

ул. Советская, 104, 246019 Гомель, Республика Беларусь

Использование имитационного моделирования

для нахождения интегрального максимального потока

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

Ключевые слова: имитационные модели, транспортная сеть, максимальный поток.
Введение

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

Для рациональной организации транспортных потоков в региональной сети необходимо исследовать потоки перемещения транспорта в различных направлениях. При этом для каждого направления требуется определить интегральный максимальный поток и найти его распределение, обеспечивающее минимальные
© И. В. Максимей, Е. И. Сукач, П. В. Гируц

суммарные затраты на перемещение транспортных средств. Полученные результаты исследования позволят выявить «узкие места» в региональной сети с целью их устранения. Наличие случайных факторов, влияющих на состояние транспортной сети, не позволяет решать перечисленные задачи с использованием известного аппарата, основанного на использовании аналитических моделей [1]. В качестве выхода из положения исследователи вынуждены прибегать к имитационному моделированию [2] транспортных потоков в сети региона с учетом случайных факторов.

Для определения вариантов организации транспортных потоков во времени, нахождения интегрального максимального потока и оценки интегральных затрат транспортных средств в динамике предлагается использовать имитационную модель транспортных потоков региона (ИМ ТПР) [3], модифицированную с учетом изменения состояния дорог и параметров внешней среды.

Обобщенная ИМ ТПP реализуется на основе комплекса взаимосвязанных имитационных моделей разного уровня детализации. Модели первого уровня позволяют исследовать процессы износа отдельных участков дорог транспортной сети, которые описываются стационарными поглощающими цепями Маркова. Вершины цепи Маркова соответствуют последовательным состояниям участков дорог, которые изменяются случайным образом и влияют на пропускные способности этих участков и величину стоимости проезда транспортных средств. Модель второго уровня, используя информацию первого уровня о текущем состоянии участков, позволяет найти значения интегрального максимального потока сети в выбранном направлении и определить «узкие места» в сети, устранение которых позволит достичь оптимального распределения транспортных потоков региона с учетом текущей ситуации.


Формальное описание региональной транспортной сети

Объект моделирования представляет собой сеть дорог ограниченного региона, по которой движутся транспортные средства. Транспортная сеть описывается при помощи ориентированного графа G(N, U), состоящего из N вершин и множества ребер U. Ветви графа имитируют дороги региона, а узлы графа — точки пересечения дорог либо населенные пункты. Поскольку граф представляет собой транс-портную сеть, то каждое его ребро описывается следующими характеристиками:



    — пропускной способностью дороги между узлами транспортной сети (cij);

    — длиной дороги между узлами транспортной сети (lij);

    — стоимостью перемещения одной транспортной единицы по дороге между узлами транспортной сети (qij);

    — величиной потока на дороге между узлами транспортной сети (xij).



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

Каждый ij-й отрезок транспортной сети характеризуется множеством состояний S = {Sn} таким образом, что, во-первых, состояние дороги определяется значением Sk, и, во-вторых, последовательность состояний S1, S2,...,Sn образует марковскую цепь. Каждое из состояний характеризует степень износа дороги. Состояние дорожного покрытия изменяется со временем (изнашивается), влияет на пропускную способность и стоимость проезда по нему единицы транспортного средства. Очевидно, что пропускная способность участка может уменьшаться, а затраты транспортных средств, движущихся по участку, увеличиваться. Состояние дорожного покрытия определяется рядом параметров (ширина, вид покрытия, частота ремонта и др.). Каждое из состояний модели задается сочетанием выделенных параметров и учитывает износ дороги в процентах. Количество состояний модели определяется исследователем в ходе имитационного эксперимента. Увеличение числа состояний приводит к более детальному рассмотрению участка сети.

Для описания характеристик каждого участка дорог определяются следующие матрицы размерности NN.

Матрица вероятностей перехода ij-го участка сети из состояния в состояние Pij = || || определяется следующим образом:



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

Матрица пропускных способностей дорог С(t) = ||cij(t)|| задается следующим образом:



где С(xi, xj) — количество транспортных средств, которое способна пропустить через себя дорога из i-го узла транспортной сети в j-й узел за единицу времени при рассмотрении момента времени t.

Матрица затрат на передвижение Q(t) = ||qij(t)|| определяется следующим образом:



где Q(xi, xj) — затраты на передвижение одного транспортного средства по дороге из i-го узла транспортной сети в j-й узел в момент времени t.

Матрица длин дорог L = ||lij|| формируется следующим образом:


где L(xi, xj) — длина дороги из i-го узла транспортной сети в j-й узел.

Матрица распределения начального потока X0 = задается следующим образом:

где Х0(xi, xj) — величина начального транзитного потока на ветви транспортной сети от i-го узла к j-му.

Матрица времени перемещения T = ||tij||, элементы которой задаются отношением tij=lij/xij, определяется так:



где T(xi, xj) — время движения транспортных единиц потока от i-го узла к j-му.

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

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

В транспортной сети региона все потоки разделяются по географическим направлениям. Потоки транспортных средств, движущихся в направлении с Севера на Юг, задают направление (С→Ю), с Юга на Север — направление (Ю→С), с Востока на Запад — направление (В→З), и с Запада на Восток — направление (З→В). Все граничные узлы сети разделяются на четыре группы: узлы северной границы сети, узлы южной границы сети, узлы западной границы сети и узлы восточной границы сети. Противоположными границами будем считать попарно границы Северная — Южная и Западная — Восточная. Для транзитного потока начальные и конечные пункты движения являются узлами двух противоположных границ. Так, например, все точки входа потока (С→Ю) лежат на Северной границе транспортной сети, а все точки выхода на Южной границе. Таким образом, под одним географическим направлением объединено несколько транзитных потоков транспортных средств. Соответственно для графа G(N, U) определены четыре множества граничных вершин: множество северных граничных вершин S; множество южных граничных вершин M; множество западных граничных вершин Z; множество восточных граничных вершин V. Противоположными множествами граничных вершин будем считать S и M, а также множества Z и V.

Таким образом, региональная транспортная сеть представляется совокупностью параметров <G, P, C(t), Q(t), L, X0, S, M, Z, V>.

Каждый транзитный поток X = ||xij|| (i = 1,...,N, j = 1,…,N), представленный матрицей с элементами:



где Х(xi, xj) — величина транзитного потока на ветви транспортной сети от i-го узла к j-му, описывается совокупностью следующих характеристик:

    — точкой начала движения транспортных средств x0, которой является некоторая вершина одного из множеств граничных вершин графа;

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

    — величиной потока φ, которая определяется формулой:


, (1)

    где u' — множество номеров всех вершин, в которые выходят ветви из вершины x0; u" — множество номеров всех вершин из которых выходят ветви в вершину xk;

    — интегральным показателем эффективности потока F, где



. (2)


    Здесь — значение эффективности движения транспортных средств по ветви ij определяется из следующих выражений:

, (3)
. (4)
Переменные являются весовыми коэффициентами важности соответственно: расстояния (), времени (), стоимости () движения по ветвям сети такие, что . Верхний индекс у этих переменных означает операцию их нормирования соответственно максимальными величинами. Нормировка составляющих позволяет оценить затраты транспортного средства в виде скалярной величины, изменяющейся на интервале [0,1]. При показателе затрат (3) оценивается стоимость передвижения по участку сети с учетом расстояния lij; для случая (4) оценивается стоимость передвижения с учетом скорости xij.

Показатель F из (2) определяет величину затрат при перемещении транспортного средства по сети в условиях максимального потока . Как видим, с одной стороны необходимо максимизировать, а с другой стороны F должно быть минимальным. Эти два противоречивых критерия определяют область компромисса при заданном векторе важности () для исследователя, который необходимо достичь с помощью имитационного моделирования.

Величины внутренних транспортных потоков для ij-х участков задаются матрицей внутренних потоков , (i, j = 1,…,N). Здесь Fij() — функция распределения величины внутреннего потока на ветви из i-го узла транспортной сети в j-й. Пропускные способности ij-ветвей графа с учетом внутренних потоков изменяются и представляют собой случайные величины, определяемые с помощью функций распределения:
. (5)
Для исследуемой региональной сети G(N, U) возможно решение следующих задач:

— определения интегрального максимального потока в заданном направлении ZY ();

— определения интегрального показателя эффективности этого потока (Fzy);

— нахождения распределения потока по ветвям сети Xzy = в последо-вательные моменты времени t = 1,…,T.

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

Обобщенная имитационная модель транспортных

потоков региональной сети

На основе формализации региональной транспортной сети была реализована обобщенная двухуровневая имитационная модель, в которой были объединены алгоритм Форда–Фалкерсона и процедура Монте–Карло, а затем использовался принцип суперпозиции для независимых транспортных потоков в одном и том же графе.

На первом уровне детализации организуется имитационное моделирование износа участков исследуемой транспортной сети региона, которая задается графом G(N, U). Вся сеть представляется множеством моделей М = {Mij}, где Mij — модель ij-го участка сети. Каждая из моделей Mij описывает случайный процесс накопления повреждений, который имитируется цепью Маркова с параметрами, заданными матрицей Pij.

Отдельные участки дорог могут иметь разные режимы технического обслуживания, поэтому их можно рассматривать как невосстанавливаемые и как восстанавливаемые объекты. Для восстанавливаемых участков дорог используется идентичная модель с возвратами в предыдущие состояния. Соответственно корректируется матрица переходов Pij.



    В результате проведения имитационных экспериментов с моделями первого уровня исследователь получает выборки значений компонент векторов изменения состояний участков сети во времени , где k — номер реализации имитационного эксперимента. По выборкам формируются средние значения соответствующих векторов , которые поступают в блок управления ИМ ТПР второго уровня.

На втором уровне моделирования транспортной сети региона выбирается исследуемое направление движения ZY, которое определяется множеством начальных узлов — «входов» транзитных потоков и конечных узлов — «выходов» транзитных потоков . Оба множества вершин расположены на границах региона. Различные сочетания «входов» и «выходов» определяют транзитные потоки для выбранного направления {ZiYj}, где i = , j = . Для формирования входных данных моделирования на этом уровне детализации анализируется информация, полученная из блока управления ИМ ТПР.

Блок управления содержит правила, задающие следующую информацию:



    — какими будут пропускные способности и стоимости проезда по участкам дорог в зависимости от их состояния;

    — выделяется группа состояний, которые являются критическими Sk =


    = {Sk1,…, Skn} (при этом пропускные способности ветвей, которые перешли в критическое состояние считаются нулевыми);

    — как изменятся состояния одних участков сети в зависимости от изменений состояний других участков;

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


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

Результатом работы блока управления являются следующие исходные данные моделирования: граф G(N, U) c начальным потоком ; матрица пропускных способностей графа; матрица расстояний между узлами сети ; матрица стоимостей проезда транспортных средств по участкам сети ; матрица времени перемещения T = ||tij||. Матрица пропускных способностей и матрица стоимостей формируются для определенных моментов времени в блоке управления на основании усредненных данных , сформированных в ходе имитационных экспериментов с моделями первого уровня.

На втором уровне моделирования решается основная задача исследования региональной транспортной сети в заданные моменты времени. При этом для каждого из транзитных потоков ZiYj, i = , j = , по отдельности решается транспортная задача путем сочетания метода Монте–Карло и алгоритма Форда–Фалкерсона [3]. В результате для каждого из потоков ZiYj, i = , j = , получаем следующие характеристики: величину максимального потока направления ZiYj, i = , j = ; величину эффективности Fij максимального потока направления ZiYj, i = , j = ; распределение транспортных потоков в сети , k,l = 1,…, N, для направления ZiYj, i = , j = .

С целью нахождения интегрального максимального потока транспортной сети в заданном направлении для выбранного временного интервала составляются матрицы величин максимальных потоков и эффективностей этих потоков, элементами которых являются значения максимальных потоков и эффективностей потоков по каждому сочетанию входа и выхода. Матрицу величин потоков обозначим = , i = , j = . Матрицу эффективностей потоков обозначим F = Fij, i = , j = . Полученные матрицы нормируются по максимальному элементу. В результате все элементы матриц *, F* удовлетворяют неравенствам


0  1; 0   1. Если отметить точки (; ) в прямоугольной системе координат *0F*, то в силу того, что элементы матриц нормированы по максимальному элементу, все точки будут находиться в пределах единичного квадрата, левый нижний угол которого совмещен с началом координат. Все точки единичного квадрата сравниваются при помощи некоторой метрики. Составляется список потоков, в котором все элементы ранжируются от «наихудшего» по эффективности к «наилучшему» в соответствии с данными единичного квадрата. Одновременно составляется матрица достижимости D = ||dij||, i = , j = , где dij = 1, если есть поток из i-го входа в j-й выход и dij = 0, если потока из i-го входа в j-й выход нет.

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

Таким образом, получаем, что текущий поток из i-го входа в j-й выход исключается из списка в том случае, если после его исключения и модификации матрицы достижимости D, в i-й строке будет хотя бы одна единица, и в j-м столбце также будет хотя бы одна единица. Если же исключение потока ведет к тому, что в матрице достижимости i-й столбец либо j-я строка будут состоять из нулей, то поток из списка потоков не исключается, и в списке переходим к следующему потоку.

В результате отбраковки потоков, получаем множество наиболее эффективных потоков ZYэ = {ZiYj}, таких, что каждый из «входов» связан транзитным потоком, по крайней мере, с одним «выходом». То есть каждый из «входов» транспортной сети имеет, по крайней мере, один исходящий из него поток, а каждый из «выходов» сети имеет, по крайней мере, один входящий в него поток.

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

С этой целью формируется общее множество дуг DN = {<dij, n>} следующим образом. Элементом множества является пара: номер насыщенной дуги и число превышений пропускной способности (<dij, n>), здесь dij — дуга из i-го узла в j-й, а n — величина, показывающая, на сколько единиц суммарный поток для этой дуги превышает ее пропускную способность. Суммарный поток описывается матрицей интегрального транзитного потока по выбранному направлению, которая является суммой матриц потоков из множества ZYэ.

Из множества DN насыщенных дуг выбирается элемент, у которого величина n максимальная. Этот элемент списка <dij, n1> описывает дугу, для которой величина n1 суммарного потока, построенного из оставшихся транзитных потоков, больше всего превышает пропускную способность дуги. Поэтому в каждом из транзитных потоков множества DN, где встречается эта выбранная дуга, необходимо уменьшить поток в n1 раз для того, чтобы после выполнения суперпозиции оставшихся потоков дуга dij оказалась насыщенной. Уменьшение производим для каждого потока ZiYj по всем путям, которые насыщали рассматриваемую дугу в ходе выполнения алгоритма Форда–Фалкерсона, пропорционально их вкладу в насыщение дуги. После этого множество DN перестраивается в силу того, что было произведено уменьшение каждого из транзитных потоков, что повлекло изменение величин n для тех ветвей сети, которые были задействованы при уменьшении потока.

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

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

Предложенный метод исследования региональной транспортной сети позволяет найти интегральный максимальный поток для выбранного направления ZY в определенный момент времени, имеющий место при распределении потоков вдоль ветвей сети, задаваемых матрицей Xzy = , при котором интегральные затраты всех транспортных средств Fzy являются минимальными; определить «узкие места» в сети с учетом динамического изменения ситуации в транспортной сети; указать способ корректировки сети с целью исключения «узких мест».





  1. Задачи и модели ИСО. Ч. 1. Аналитические модели исследования операций: Учеб. пособ. / И.В. Максимей, С.И. Жогаль / Под общ. ред. И.В. Максимея. — Гомель: БелГУТ, 1999. — 109 с.

  2. Максимей И.В. Имитационное моделирование на ЭВМ / И.В. Максимей. — М.: Радио и связь, 1988. — 232 с

  3. Максимей И.В. Исследование вероятностных транспортных потоков региона с использованием метода имитационного моделирования / Максимей И.В., Сукач Е.И., Гируц П.Л., Пикуль А.В. // Информационные системы и технологии (IST`2006): Материалы Ш Международной конференции. — Минск, 1–3 ноября 2006 г. / Академия управления при Президенте Республики Беларусь. — Минск, 2006. — Ч. 2. — С. 178–183.

  4. Сукач Е.И. Использование логического моделирования для исследования сложных систем // Известия Гомельского гос. ун-та им. Ф. Скорины, 2004. — № 4(25). — С. 60–64.

Поступила в редакцию 20.07.2007



ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 49