Модель равновесного распределения потоков

ЛЕКЦИЯ 13

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

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

- все пути, соединяющие районы i и j, которые используются для движения представителями корреспонденции Fij, имеют одинаковую цену;

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

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

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

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

Имеют место также линейные соотношения, выражающие «закон сохранения пользователей в сети»

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

«Источниками» и «стоками» для участников движения являются районы прибытия/отправления:

(18)

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

- Сa(u) ценовая функция дуги a є A;

- Сa₁a₂(u) ценовая функция поворота с дуги a₁ є A на дугу a₂ є A.

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

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

при системе линейных ограничений (16)-(18).

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

Рассмотрим распределение потоков, доставляющее минимум этой функции. Точка минимума любой функции обладает следующим свойством: при всякой вариации аргумента в этой точке изменение функции в линейном приближении неотрицательно. Рассмотрим простую вариацию распределения, состоящую в том, что малая доля u потока снимается с одного из путей и перекладывается на альтернативный путь. Тогда изменение функции на каждой из дуг в линейном приближении равно C^`_a (u_a)(±δu). При этом на дугах исходного пути, где поток уменьшился, изменение отрицательно, а на дугах альтернативного пути положительно. Поскольку суммарное изменение должно быть неотрицательно, получаем, что сумма производных C0_a(u_a) по дугам альтернативного пути не меньше, чем сумма производных по дугам исходного пути. Подберем функции C_a(u_a) с тем расчетом, чтобы их производные давали значения цен дуг, как это сделано в (19)-(20). Тогда окажется, что в точке минимума суммарная цена альтернативного пути не меньше цены исходного пути, что и требуется условиями равновесного распределения.

Задача минимизации (16)-(21) может быть решена методом последовательных приближений, известном как метод Франка-Вульфа (Frank and Wolfe,). Метод состоит в следующем: пусть на очередном k-м шаге итераций достигнуто некотороераспределение потоков u^k={u^pq_a; u^pq_a1a2}^k. Линеаризуем целевую функцию в точке u^k и обозначим решение линеаризованной задачи u^k_L. Решение линеаризованной задачи используется для определения «направления смещения» при поиске очередного приближения, т.е. (k + 1)-е приближение ищется в виде

(23)

Величина λ определяет долю потоков, которая на очередном шаге итерации снимается с прежней системы путей и перекладывается на новую систему путей. Определение доли, которую следует перераспределить на каждом шаге, является отдельной задачей. Интересно отметить, что теоретически точное значение этой доли не важно для нахождения равновесного распределения. Именно, можно заранее задаться произвольной последовательностью долей λ_k, которые будут перераспределяться на каждом k-м шаге. Тогда, если выполнены простые условия

(24)

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

(25)

Задача (25) представляет собой общую задачу (21), «суженную» на одномерное направление, полученное на данном шаге итерации. Это — одномерная задача без ограничений, более того, целевая функция выпукла (это следует из монотонности ценовых функций), поэтому ее численное решение не составляет труда.

Рассмотрим теперь линеаризованную задачу (16)-(21). Дифференциал целевой функции в точке u^k имеет вид:

(26)

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

Первичными переменными в задаче являются потоки представителей отдельных корреспонденций u^pq_a; u^pq_a1a2, так как именно для этих переменных сформулированы ограничения. Однако целевая функция зависит только от суммарных потоков на дугах и поворотах u_a; u_a1a2. Далее, если для распределений u^k; u^k_L ограничения задачи выполнены, то они автоматически будут выполняться на решении одномерной задачи. Действительно, если перераспределяется фиксированная доля λ представителей каждой корреспонденции, то это приводит к перераспределению ровно той же доли суммарного потока на каждой дуге. Единственное место в алгоритме, где рассматриваются потоки представителей отдельных корреспонденций, это вычисление u^k_L путем наложения корреспонденций на кратчайшие пути. Сам способ такого вычисления гарантирует выполнение ограничений задачи. Таким образом, мы можем рассчитать равновесное распределение, оперируя только значениями суммарных потоков на дугах и поворотах, что значительно экономит оперативную память при компьютерных расчетах. Если для анализа свойств загрузки все же требуется знать полную раскладку корреспонденций по путям, можно организовать сохранение рассчитываемых путей на диске компьютера «по мере использования», т.е. не занимая оперативной памяти.

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

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

Последующие итерации алгоритма делаются следующим образом.

- Цены всех элементов сети пересчитываются в соответствии с полученными на данной итерации значениями потоков u^k.

- В соответствии с новыми ценами отыскивается система кратчайших путей между центрами въезда-выезда.

- Рассчитываются потоки u^k_L, которые получаются в результате наложения корреспонденций на кратчайшие пути (решение линеаризованной задачи).

- Новое распределение потоков рассчитывается по формуле

u^k+1 = (1 λ)u^k+ λ u^k_L,

где λ определяется решением одномерной задачи (25).

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

(27)

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

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