vesnat.ru страница 1
скачать файл
УДК 656.078
ОБ ОДНОМ МЕТОДЕ УПРАВЛЕНИЯ ТРАНСПОРТНЫМИ ПОТОКАМИ
П.П. Бобрик

Институт проблем транспорта им. Н.С. Соломенко РАН


Россия, 199178, Санкт-Петербург, 12-я линия В.О., 13

E-mail: commos@online.ru


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

Key words: system identification, control problems, transport, net flows, minimization of flow, decentralization of control systems

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



ABOUT A METHOD OF TRANSPORT FLOWS CONTROL / P.P. Bobrik (Transportation Problems Institute by N.S. Solomenko of RAS, 13, 12 line, Moscow, 119178, Russia, Belyi@ipt.nw.ru). In the paper analyzed modified task of determination of flow with minimized cost at weighted graph. Participants of flow can choose route themself, to minimize it’s cost. Central operator of net forces at route choosing process by imposing the additional weights on edges of graph. It is possible to choose such additional weights, that every participant of flow will be choose shortest route and total flow on net will have the minimal cost or near it.


1.Используемые обозначения

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

Для каждого ребра, где и - некоторые смежные вершины графа, заданы два положительных числа:


  • его длина или стоимость - ;

  • его пропускная способность .

Здесь использовано общее обозначение оператора длины или стоимости , которое может быть далее применено к объектам различного рода: ребру, маршруту, потоку и т.д.

В соответствии с постановкой задачи по ребру не может течь транспортный поток выше ее пропускной способности.



Каждая последовательность смежных ребер графа образует маршрут. Для каждого маршрута определена его стоимость.



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

Стоимость потока по маршруту с интенсивностью равна

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



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

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

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

Если для каждой пары вершин графа и задан поток , где , то в сети определен поток , удовлетворяющий корреспонденциям .

Пусть интенсивность потока на некотором ребре графа , обусловленного корреспонденцией равна . Здесь величина равна , если проходит по ребру и равна нулю, если не проходит.

Тогда условие ограничения на пропускную способность запишется в виде




2.Задача поиска потока минимальной стоимости

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

1. Суммарный поток по каждому ребру сети не превышал ее пропускной способности

здесь величина равна интенсивности потока по ребру , обусловленного корреспонденцией .

2. Суммарная стоимость потока по сети

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

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

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

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


3.Модификация задачи поиска потока минимальной стоимости

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

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

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

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

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

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

Здесь предполагается, что абсолютные значения некоторой неизвестной нам функция значительно меньше длины любого маршрута и даже длины любого ребра графа. Использование такой функции позволяет промоделировать различные и порой совершенно уникальные для каждого участника движения факторы, которые могут оказать влияние на выбор маршрута. Поскольку факторы могут быть совершенно неожиданными, то в данной записи принципиально не указаны переменные, от которой функция зависит, просто потому, что они не известны в большинстве случаев. Например, на выбор маршрута могут повлиять расположение на маршруте некоторых объектов: стоянок, магазинов, водоемов и даже просто приятный пейзаж. На выбор маршрута может повлиять вероятности возникновения пробок во время поездки. Число таких факторов может быть очень велико. Считается, что они не известны и даже может быть принципиально не могут быть идентифицированы, а раз так и не пытаемся даже разобраться в этом вопросе. Единственно, что утверждается по условию задачи, так это малость функции по абсолютному значению, или, по другому, незначительность этих факторов при выборе маршрута по сравнению с главным фактором – стоимостью маршрута.

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

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




4.Допущения по выбору маршрутов участниками движения

Таким образом, субъекты потока выбирают такой маршрут, который имеет минимальную стоимость или стоимость, близкую (в некотором смысле) к минимальной. Это означает, что система является децентрализованной по принятию решений. Однако предполагается, что у такой сети по прежнему есть центральный оператор, который по прежнему преследует цель минимизации суммарного потока по всей сети, что относит такой тип сети к частично децентрализованной.

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

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





Определение.

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

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

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

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

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

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

если , то

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

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

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

5.Постановка задачи и основная теорема


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

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



  1. все корреспонденции были бы удовлетворены

  2. все ограничения на пропускные способности ребер графа не нарушались бы.

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

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

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

Верна следующая

Теорема.

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



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



Список литературы

1.Бобрик П.П. Теоретико-графовое моделирование и возможности исследования автодорожной транспортной сети России // Транспорт: наука, техника, управление. 1995. №1.

2.Бобрик П.П. Моделирование распределения потоков в транспортных сетях по нескольким альтернативным маршрутам // Транспорт: наука, техника, управление. 1995. №9.

3.Бобрик П.П. Сравнение эффективности треугольной и квадратной регулярных транспортных сетей // Транспорт: наука, техника, управление. 2000. №7.

4.Бобрик П.П. О преимуществе треугольной топологии сети над квадратной // Транспорт: наука, техника, управление. 2005. №3. С. 32-34.

5.Гольц Г.А. Транспорт и расселение. М.: Наука 1981, 248 с.

скачать файл



Смотрите также:
Об одном методе управления транспортными потоками
111.63kb.
Доклад об одном из телеведущих ( например, В. Познер, У. Отт )
9.84kb.
Требования, предъявляемые к математическим моделям систем автоматического управления
553.07kb.
Методы оценки эффективности управления
212.8kb.
Реализация многометодных процедур оптимального управления
65.48kb.
Антаков М. А. (Миэт)
1019.47kb.
Создание pppoE-подключения в Windows Vista Нажимаем меню «Пуск», далее выбираем «Панель Управления»
17.24kb.
Программа дисциплины Управление транспортными системами (часть 1) для специальности 080506. 65 «Логистика и управление цепями поставок»
151.59kb.
Дисидентський рух плинув у СРСР трьома потоками, що часто зливалися
118.06kb.
Кожна держава розгортає свою мережу зовнішньополітичної комунікації, яка забезпечує її національні інтереси
44.15kb.
Программа дисциплины модели корпоративного управления направление подготовки 03470 Документоведение и архивоведение
364.51kb.
Спонтанность в творческом методе современной архитектуры
274.65kb.