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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2008
Автори:	Максимей, И.В., Сукач, Е.И., Гируц, П.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем реєстрації інформації НАН України 2008
Назва видання:	Реєстрація, зберігання і обробка даних
Теми:	Інформаційно-аналітичні системи обробки даних
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/7542
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона / И.В. Максимей, Е.И. Сукач, П.В. Гируц // Реєстрація, зберігання і оброб. даних. — 2008. — Т. 10, № 1. — С. 49-58. — Бібліогр.: 4 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-7542
record_format	dspace
spelling	irk-123456789-75422013-11-01T02:42:32Z Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона Максимей, И.В. Сукач, Е.И. Гируц, П.В. Інформаційно-аналітичні системи обробки даних Предложено использование обобщенной имитационной модели региональной транспортной сети, учитывающей влияние случайных внутренних потоков и вероятностное старение дорог, для нахождения максимального потока в сети и определения "узких мест" в сети. Запропоновано використання узагальненої моделі регіональної транспортної мережі, яка враховує вплив випадкових внутрішніх потоків i ймовірне старіння шляхів для пошуку максимального потоку в мережі та знаходження «вузьких місць» у мережі. Запропоновано використання узагальненої моделі регіональної транспортної мережі, яка враховує вплив випадкових внутрішніх потоків i ймовірне старіння шляхів для пошуку максимального потоку в мережі та знаходження «вузьких місць» у мережі. 2008 Article Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона / И.В. Максимей, Е.И. Сукач, П.В. Гируц // Реєстрація, зберігання і оброб. даних. — 2008. — Т. 10, № 1. — С. 49-58. — Бібліогр.: 4 назв. — рос. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/7542 681.3 ru Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Інформаційно-аналітичні системи обробки даних Інформаційно-аналітичні системи обробки даних
spellingShingle	Інформаційно-аналітичні системи обробки даних Інформаційно-аналітичні системи обробки даних Максимей, И.В. Сукач, Е.И. Гируц, П.В. Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона Реєстрація, зберігання і обробка даних
description	Предложено использование обобщенной имитационной модели региональной транспортной сети, учитывающей влияние случайных внутренних потоков и вероятностное старение дорог, для нахождения максимального потока в сети и определения "узких мест" в сети.
format	Article
author	Максимей, И.В. Сукач, Е.И. Гируц, П.В.
author_facet	Максимей, И.В. Сукач, Е.И. Гируц, П.В.
author_sort	Максимей, И.В.
title	Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона
title_short	Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона
title_full	Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона
title_fullStr	Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона
title_full_unstemmed	Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона
title_sort	использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона
publisher	Інститут проблем реєстрації інформації НАН України
publishDate	2008
topic_facet	Інформаційно-аналітичні системи обробки даних
url	http://dspace.nbuv.gov.ua/handle/123456789/7542
citation_txt	Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона / И.В. Максимей, Е.И. Сукач, П.В. Гируц // Реєстрація, зберігання і оброб. даних. — 2008. — Т. 10, № 1. — С. 49-58. — Бібліогр.: 4 назв. — рос.
series	Реєстрація, зберігання і обробка даних
work_keys_str_mv	AT maksimejiv ispolʹzovanieimitacionnogomodelirovaniâdlânahoždeniâintegralʹnogomaksimalʹnogopotokavtransportnojsetiregiona AT sukačei ispolʹzovanieimitacionnogomodelirovaniâdlânahoždeniâintegralʹnogomaksimalʹnogopotokavtransportnojsetiregiona AT girucpv ispolʹzovanieimitacionnogomodelirovaniâdlânahoždeniâintegralʹnogomaksimalʹnogopotokavtransportnojsetiregiona
first_indexed	2025-07-02T10:22:37Z
last_indexed	2025-07-02T10:22:37Z
_version_	1836530278388989952
fulltext	Інформаційно-аналітичні системи обробки даних ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 49 УДК 681.3 И. В. Максимей, Е. И. Сукач, П. В. Гируц Гомельский государственный университет им. Ф.Скорины ул. Советская, 104, 246019 Гомель, Республика Беларусь Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона Предложено использование обобщенной имитационной модели регио- нальной транспортной сети, учитывающей влияние случайных внут- ренних потоков и вероятностное старение дорог, для нахождения максимального потока в сети и определения «узких мест» в сети. Ключевые слова: имитационные модели, транспортная сеть, макси- мальный поток. Введение Резкое увеличение числа транспортных средств в региональной транспортной сети существенно повысило требования к рациональной организации транспорт- ных потоков и определило актуальность задачи их исследования с использовани- ем графовых структур. Сама сеть дорог может быть представлена в виде графа, состоящего из узлов и дуг. Каждое ребро графа, соответствующее участку дороги, характеризуется длиной, пропускной способностью и стоимостью проезда по не- му единицы транспортного средства. Пропускная способность ветви графа зави- сит от многих факторов, среди которых наиболее важными являются: загружен- ность участков пути и состояние дорожного покрытия. Загруженность на разных участках дороги бывает различной и зависит от наличия внутренних транспорт- ных потоков на данном участке, которые могут рассматриваться как помехи при передвижении транспортной единицы из начального пункта сети в конечный пункт. Состояние дороги определяется ее износом, условиями эксплуатации, вли- янием погодных условий. При организации транспортных потоков следует учи- тывать, что в реальной сети перечисленные факторы являются взаимосвязанными и изменяются во времени. Для рациональной организации транспортных потоков в региональной сети необходимо исследовать потоки перемещения транспорта в различных направле- ниях. При этом для каждого направления требуется определить интегральный максимальный поток и найти его распределение, обеспечивающее минимальные © И. В. Максимей, Е. И. Сукач, П. В. Гируц Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона 50 суммарные затраты на перемещение транспортных средств. Полученные результа- ты исследования позволят выявить «узкие места» в региональной сети с целью их устранения. Наличие случайных факторов, влияющих на состояние транспортной сети, не позволяет решать перечисленные задачи с использованием известного аппарата, основанного на использовании аналитических моделей [1]. В качестве вы- хода из положения исследователи вынуждены прибегать к имитационному модели- рованию [2] транспортных потоков в сети региона с учетом случайных факторов. Для определения вариантов организации транспортных потоков во времени, нахождения интегрального максимального потока и оценки интегральных затрат транспортных средств в динамике предлагается использовать имитационную мо- дель транспортных потоков региона (ИМ ТПР) [3], модифицированную с учетом изменения состояния дорог и параметров внешней среды. Обобщенная ИМ ТПP реализуется на основе комплекса взаимосвязанных имитационных моделей разного уровня детализации. Модели первого уровня по- зволяют исследовать процессы износа отдельных участков дорог транспортной сети, которые описываются стационарными поглощающими цепями Маркова. Вершины цепи Маркова соответствуют последовательным состояниям участков дорог, которые изменяются случайным образом и влияют на пропускные способ- ности этих участков и величину стоимости проезда транспортных средств. Мо- дель второго уровня, используя информацию первого уровня о текущем состоя- нии участков, позволяет найти значения интегрального максимального потока се- ти в выбранном направлении и определить «узкие места» в сети, устранение ко- торых позволит достичь оптимального распределения транспортных потоков ре- гиона с учетом текущей ситуации. Формальное описание региональной транспортной сети Объект моделирования представляет собой сеть дорог ограниченного регио- на, по которой движутся транспортные средства. Транспортная сеть описывается при помощи ориентированного графа G(N, U), состоящего из N вершин и множес- тва ребер U. Ветви графа имитируют дороги региона, а узлы графа — точки пере- сечения дорог либо населенные пункты. Поскольку граф представляет собой транс- портную сеть, то каждое его ребро описывается следующими характеристиками: — пропускной способностью дороги между узлами транспортной сети (cij); — длиной дороги между узлами транспортной сети (lij); — стоимостью перемещения одной транспортной единицы по дороге между узлами транспортной сети (qij); — величиной потока на дороге между узлами транспортной сети (xij). Под пропускной способностью дороги понимают максимально возможное ко- личество единиц транспорта, которое способна пропустить через себя ветвь за выб- ранную единицу времени. Длина дороги задается в условных единицах. Величина потока определяет количество единиц транспорта, движущегося по участку сети. Каждый ij-й отрезок транспортной сети характеризуется множеством состоя- ний S = {Sn} таким образом, что, во-первых, состояние дороги определяется зна- чением Sk, и, во-вторых, последовательность состояний S1, S2,...,Sn образует мар- ковскую цепь. Каждое из состояний характеризует степень износа дороги. Сос- И. В. Максимей, Е. И. Сукач, П. В. Гируц ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 51 тояние дорожного покрытия изменяется со временем (изнашивается), влияет на пропускную способность и стоимость проезда по нему единицы транспортного средства. Очевидно, что пропускная способность участка может уменьшаться, а затраты транспортных средств, движущихся по участку, увеличиваться. Состоя- ние дорожного покрытия определяется рядом параметров (ширина, вид покрытия, частота ремонта и др.). Каждое из состояний модели задается сочетанием выде- ленных параметров и учитывает износ дороги в процентах. Количество состояний модели определяется исследователем в ходе имитационного эксперимента. Уве- личение числа состояний приводит к более детальному рассмотрению участка сети. Для описания характеристик каждого участка дорог определяются слідую- щие матрицы размерности NN. Матрица вероятностей перехода ij-го участка сети из состояния в состояние Pij = \|\| ij klp \|\| определяется следующим образом:          .1,0 ,11 , klklпри klприp klприp p kl kl ij kl Каждому состоянию дорожного покрытия соответствует значение пропуск- ной способности и значение стоимости, которое изменяется случайным образом во времени. Матрица пропускных способностей дорог С(t) = \|\|cij(t)\|\| задается следующим образом:       ,),(),( ,),(0 )( UxxприxxC Uxxпри tc jiji ji ij где С(xi, xj) — количество транспортных средств, которое способна пропустить через себя дорога из i-го узла транспортной сети в j-й узел за единицу времени при рассмотрении момента времени t. Матрица затрат на передвижение Q(t) = \|\|qij(t)\|\| определяется следующим об- разом:       ,),(),( ,),(0 )( UxxприxxQ Uxxпри tq jiji ji ij где Q(xi, xj) — затраты на передвижение одного транспортного средства по дороге из i-го узла транспортной сети в j-й узел в момент времени t. Матрица длин дорог L = \|\|lij\|\| формируется следующим образом:       ,),(),( ,),(0 UxxприxxL Uxxпри l jiji ji ij Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона 52 где L(xi, xj) — длина дороги из i-го узла транспортной сети в j-й узел. Матрица распределения начального потока X0 = 0 ijx задается следующим об- разом:       ,),(),( ,),(0 0 0 UxxприxxX Uxxпри x jiji ji ij где Х0(xi, xj) — величина начального транзитного потока на ветви транспортной сети от i-го узла к j-му. Матрица времени перемещения T = \|\|tij\|\|, элементы которой задаются отноше- нием tij=lij/xij, определяется так:       ,),(),(/),(),( ,),(0 UxxприxxXxxLxxT Uxxпри t jijijiji ji ij где T(xi, xj) — время движения транспортных единиц потока от i-го узла к j-му. При движении по сети дорог транспортные средства образуют некоторый по- ток. Поток в сети характеризуется направлением движения транспортных сред- ств, входящих в него, которые совершают транзитное движение по транспортной сети. Направление движения транспортного средства и потока, в который оно входит, определяется точкой «входа» в транспортную сеть, называемой исток, а также точкой «выхода» из сети, называемой сток. Величина потока определяется количеством транспортных средств, которые движутся по сети в заданном напра- влении. В реальной транспортной сети существует несколько точек «входа» (крайних узлов сети, через которые транспортные средства попадают в заданную сеть), а также несколько точек «выхода» (крайних узлов сети, через которые транспортные средства покидают сеть). Очевидно, в транспортной сети региона могут существовать несколько транзитных потоков транспортных средств в за- данном направлении. Кроме этого, в сети существуют внутренние потоки, транспортные средства в которых движутся в направлении от некоторого внутреннего узла сети к другому внутреннему узлу сети. Внутренние потоки изменяют свою величину в зависимо- сти от случайных внешних воздействий на сеть. Внешние воздействия обычно связаны с изменением погодных условий, изменением времени суток и другими факторами. Внутренние потоки отнимают некоторую часть ресурсов транспорт- ной сети, уменьшая тем самым величину пропускных способностей участков се- ти. Разница между транзитными и внутренними потоками для рассматриваемой транспортной сети заключается в том, что величина внутреннего потока это слу- чайная величина, в то время как величина транзитного потока считается неизмен- ной в течение заданного периода времени. В транспортной сети региона все потоки разделяются по географическим на- правлениям. Потоки транспортных средств, движущихся в направлении с Севера на Юг, задают направление (С→Ю), с Юга на Север — направление (Ю→С), с И. В. Максимей, Е. И. Сукач, П. В. Гируц ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 53 Востока на Запад — направление (В→З), и с Запада на Восток — направление (З→В). Все граничные узлы сети разделяются на четыре группы: узлы северной границы сети, узлы южной границы сети, узлы западной границы сети и узлы во- сточной границы сети. Противоположными границами будем считать попарно границы Северная — Южная и Западная — Восточная. Для транзитного потока начальные и конечные пункты движения являются узлами двух противоположных границ. Так, например, все точки входа потока (С→Ю) лежат на Северной грани- це транспортной сети, а все точки выхода на Южной границе. Таким образом, под одним географическим направлением объединено несколько транзитных потоков транспортных средств. Соответственно для графа 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), представленный ма- трицей с элементами:       ,),(),( ,),(0 UxxприxxX Uxxпри x jiji ji ij где Х(xi, xj) — величина транзитного потока на ветви транспортной сети от i-го узла к j-му, описывается совокупностью следующих характеристик: — точкой начала движения транспортных средств x0, которой является неко- торая вершина одного из множеств граничных вершин графа; — точкой окончания движения транспортных средств xk, которой будем счи- тать некоторую точку из противоположного множества; — величиной потока φ, которая определяется формулой:    '' 0 ),(),( ' ui ki ui i xxCxxC , (1) где u' — множество номеров всех вершин, в которые выходят ветви из вершины x0; u" — множество номеров всех вершин из которых выходят ветви в вершину xk; — интегральным показателем эффективности потока F, где     N i N j ijfF 1 1 * . (2) Здесь * ijf — значение эффективности движения транспортных средств по ветви ij определяется из следующих выражений: Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона 54 * 3 * 2 * 1 * ))(( ijij ij ij ijij ltq x l lf            , (3) * 3 * 2 * 1 * ))(( ijij ij ij ijij xtq x l lf            . (4) Переменные ,10  i являются весовыми коэффициентами важности соот- ветственно: расстояния ( 1 ), времени ( 2 ), стоимости ( 3 ) движения по ветвям сети такие, что    3 1 1 i i . Верхний индекс у этих переменных означает операцию их нормирования соответственно максимальными величинами. Нормировка сос- тавляющих позволяет оценить затраты транспортного средства в виде скалярной величины, изменяющейся на интервале [0,1]. При показателе затрат (3) оценивае- тся стоимость передвижения по участку сети с учетом расстояния lij; для случая (4) оценивается стоимость передвижения с учетом скорости xij. Показатель F из (2) определяет величину затрат при перемещении транспорт- ного средства по сети в условиях максимального потока  . Как видим, с одной стороны  необходимо максимизировать, а с другой стороны F должно быть ми- нимальным. Эти два противоречивых критерия определяют область компромисса при заданном векторе важности ( 321 ,,  ) для исследователя, который необхо- димо достичь с помощью имитационного моделирования. Величины внутренних транспортных потоков для ij-х участков задаются мат- рицей внутренних потоков )(ij V ij V FxX  , (i, j = 1,…,N). Здесь Fij() — функ- ция распределения величины внутреннего потока на ветви из i-го узла транспорт- ной сети в j-й. Пропускные способности ij-ветвей графа с учетом внутренних по- токов изменяются и представляют собой случайные величины, определяемые с помощью функций распределения: )()()~( ijijij FtccF  . (5) Для исследуемой региональной сети G(N, U) возможно решение следующих задач: — определения интегрального максимального потока в заданном направле- нии ZY ( zy ); — определения интегрального показателя эффективности этого потока (Fzy); — нахождения распределения потока по ветвям сети Xzy = zy ijx в последо- вательные моменты времени t = 1,…,T. Случайный процесс износа дорожного покрытия и наличие внутренних транспортных потоков в графе обусловливает вероятностный характер пропуск- ных способностей на многих ветвях графа, что не позволяет решить эту задачу с И. В. Максимей, Е. И. Сукач, П. В. Гируц ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 55 помощью алгоритма Форда–Фалкерсона и определяет актуальность использова- ния обобщенной имитационной модели, основанной на сочетании процедуры Монте–Карло, теоремы Форда–Фалкерсона и методики динамического програм- мирования. Обобщенная имитационная модель транспортных потоков региональной сети На основе формализации региональной транспортной сети была реализована обобщенная двухуровневая имитационная модель, в которой были объединены алгоритм Форда–Фалкерсона и процедура Монте–Карло, а затем использовался принцип суперпозиции для независимых транспортных потоков в одном и том же графе. На первом уровне детализации организуется имитационное моделирование износа участков исследуемой транспортной сети региона, которая задается гра- фом G(N, U). Вся сеть представляется множеством моделей М = {Mij}, где Mij — модель ij-го участка сети. Каждая из моделей Mij описывает случайный процесс накопления повреждений, который имитируется цепью Маркова с параметрами, заданными матрицей Pij. Отдельные участки дорог могут иметь разные режимы технического обслу- живания, поэтому их можно рассматривать как невосстанавливаемые и как восс- танавливаемые объекты. Для восстанавливаемых участков дорог используется идентичная модель с возвратами в предыдущие состояния. Соответственно кор- ректируется матрица переходов Pij. В результате проведения имитационных экспериментов с моделями первого уровня исследователь получает выборки значений компонент векторов изменения состояний участков сети во времени ijkijk vsVS  , где k — номер реализации ими- тационного эксперимента. По выборкам формируются средние значения соответ- ствующих векторов ijkijk vsVS  , которые поступают в блок управления ИМ ТПР второго уровня. На втором уровне моделирования транспортной сети региона выбирается ис- следуемое направление движения ZY, которое определяется множеством началь- ных узлов — «входов» транзитных потоков  mZZZ ,...,, 21 и конечных узлов — «выходов» транзитных потоков  nYYY ,...,, 21 . Оба множества вершин расположены на границах региона. Различные сочетания «входов» и «выходов» определяют транзитные потоки для выбранного направления {ZiYj}, где i = m,1 , j = n,1 . Для формирования входных данных моделирования на этом уровне детализации ана- лизируется информация, полученная из блока управления ИМ ТПР. Блок управления содержит правила, задающие следующую информацию: — какими будут пропускные способности и стоимости проезда по участкам дорог в зависимости от их состояния; — выделяется группа состояний, которые являются критическими Sk = = {Sk1,…, Skn} (при этом пропускные способности ветвей, которые перешли в кри- тическое состояние считаются нулевыми); Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона 56 — как изменятся состояния одних участков сети в зависимости от изменений состояний других участков; — как модифицируется структура графа в зависимости от перехода отдель- ных участков сети в критическое состояние, а также при восстановлении отдель- ных участков сети. На основе правил, составляющих алгоритм блока управления, происходит управление процессом изменения модели во времени. Блок управления позволяет контролировать ситуацию в сети на уровне отдельных участков дорог. Как только состояние контролируемого отрезка сети приближается к критическому уровню, он исключается из сети и переходит в режим восстановления. Одновременно сра- батывают все правила, изменяющие нагрузку на альтернативные пути. Таким об- разом, итеративно на каждом шаге моделирования второго уровня происходит контроль состояния дорог и расчеты, связанные с процессом перераспределения транспортных потоков. Результатом работы блока управления являются следующие исходные дан- ные моделирования: граф G(N, U) c начальным потоком 00 ijxX  ; матрица про- пускных способностей )()( tctC ij графа; матрица расстояний между узлами сети ijlL  ; матрица стоимостей проезда транспортных средств по участкам се- ти )()( tqtQ ij ; матрица времени перемещения T = \|\|tij\|\|. Матрица пропускных способностей и матрица стоимостей формируются для определенных моментов времени в блоке управления на основании усредненных данных ijkijk vsVS  , сфо- рмированных в ходе имитационных экспериментов с моделями первого уровня. На втором уровне моделирования решается основная задача исследования региональной транспортной сети в заданные моменты времени. При этом для ка- ждого из транзитных потоков ZiYj, i = m,1 , j = n,1 , по отдельности решается транспортная задача путем сочетания метода Монте–Карло и алгоритма Форда– Фалкерсона [3]. В результате для каждого из потоков ZiYj, i = m,1 , j = n,1 , получа- ем следующие характеристики: величину максимального потока max ij направле- ния ZiYj, i = m,1 , j = n,1 ; величину эффективности Fij максимального потока на- правления ZiYj, i = m,1 , j = n,1 ; распределение транспортных потоков в сети ij kl ij XX  , k,l = 1,…, N, для направления ZiYj, i = m1, , j = n1, . С целью нахождения интегрального максимального потока транспортной се- ти в заданном направлении для выбранного временного интервала составляются матрицы величин максимальных потоков и эффективностей этих потоков, элеме- нтами которых являются значения максимальных потоков и эффективностей по- токов по каждому сочетанию входа и выхода. Матрицу величин потоков обозна- чим  = max ij , i = m1, , j = n1, . Матрицу эффективностей потоков обозначим F = Fij, i = m1, , j = n,1 . Полученные матрицы нормируются по максимальному эле- менту. В результате все элементы матриц , F удовлетворяют неравенствам И. В. Максимей, Е. И. Сукач, П. В. Гируц ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 1 57 0  * ij 1; 0   ijF  1. Если отметить точки ( * ij ;  ijF ) в прямоугольной системе ко- ординат 0F, то в силу того, что элементы матриц нормированы по максималь- ному элементу, все точки будут находиться в пределах единичного квадрата, ле- вый нижний угол которого совмещен с началом координат. Все точки единичного квадрата сравниваются при помощи некоторой метрики. Составляется список по- токов, в котором все элементы ранжируются от «наихудшего» по эффективности к «наилучшему» в соответствии с данными единичного квадрата. Одновременно составляется матрица достижимости D = \|\|dij\|\|, i = m1, , j = n1, , где 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, где встречается эта выбранная дуга, необхо- Использование имитационного моделирования для нахождения интегрального максимального потока в транспортной сети региона 58 димо уменьшить поток в n1 раз для того, чтобы после выполнения суперпозиции оставшихся потоков дуга dij оказалась насыщенной. Уменьшение производим для каждого потока Zi′Yj′ по всем путям, которые насыщали рассматриваемую дугу в ходе выполнения алгоритма Форда–Фалкерсона, пропорционально их вкладу в насыщение дуги. После этого множество DN перестраивается в силу того, что бы- ло произведено уменьшение каждого из транзитных потоков, что повлекло изме- нение величин n для тех ветвей сети, которые были задействованы при уменьше- нии потока. Описанные действия выполняются до тех пор, пока в множестве DN находит- ся хотя бы один элемент, у которого n больше нуля. Как только у всех элементов множества DN величины n станут отрицательными либо равными нулю, это будет означать, что после суперпозиции потоков, величины результирующего суммар- ного потока на дугах не будут превышать их пропускные способности, а, следова- тельно, дальнейшее уменьшение потоков прекращается. В качестве решения зада- чи берется результирующий суммарный поток. В результате выполнения алгоритма суперпозиции потоков в соответствии с теоремой Форда–Фалкерсона величина интегрального потока на любом разрезе сети будет максимальной, а сам суммарный поток будет состоять из уменьшен- ных транзитных потоков. Заключение Предложенный метод исследования региональной транспортной сети позво- ляет найти интегральный максимальный поток )(tzy для выбранного направле- ния ZY в определенный момент времени, имеющий место при распределении по- токов вдоль ветвей сети, задаваемых матрицей Xzy = zy ijx , при котором интеграль- ные затраты всех транспортных средств 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

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

Репозитарії

Схожі ресурси