Глава вторая.
(ссылка на первую главу)

Искусство проектирования дорожных сетей

Транспортные проблемы города глазами человека из «Computer Science»

Если бы мне порекомендовали статью с названием «Искусство проектирования дорожных сетей», я бы тот час поинтересовался, как много дорожных сетей было построено с участием ее автора. Должен признаться, моя профессиональная деятельность лежала далеко от дорожного строительства и была последнее время связанна с проектированием микропроцессоров, где я, в том числе, занимался ресурсоемкостью коммутации данных. Так получилось, что мой стол тогда стоял как раз напротив панорамного окна, открывавшего прекрасный вид на длинный участок Волгоградского шоссе и части ТТК с их нескончаемыми пробками с утра до вечера, от горизонта до горизонта. И тут, в один из дней меня вдруг осенило:«Черт возьми, ведь сложности процесса коммутации данных, с которыми я борюсь на кристалле, точь в точь должны быть похожи на те трудности, с которыми сталкивается поток автомобилей внутри паутины уличных дорог».
Вероятно, именно взгляд со стороны и применение нетрадиционных для исследуемой области методов дали мне шанс разобраться в причине возникновения пробок и выработать рекомендации, как преодолеть их проблему на практике.

Итак, в чем же заключается новизна подхода?

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

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

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

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

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

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

Статья рассчитана на широкий круг читателей, немного знакомых с общеуниверситетским курсом математики, теорией алгоритмов и готовых посвятить ей 1 — 5 дней.

Разделение и слияние автомобильных потоков

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

Две стратегии перестроиться в соседний ряд

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

Стратегия №1
Несколько подходящих зазоров попросту могут находиться недалеко от его местоположения. Если движение достаточно плотное, то прибавить скорости и догнать нужную брешь — у водителя вряд ли получится, а вот немного замедлить движение и дать соседнему потоку обогнать себя настолько, чтобы поравняться с зазором, который изначально находился позади, — больших хлопот не составит. Издержки у этой стратегии очевидны: сам водитель и едущие позади в его полосе машины теряют какое-то время из-за необходимости снижать скорость.

Стратегия №2
Чтобы ждать, нужно иметь терпение и располагать необходимым для этого количеством времени. Альтернативой может быть попытка выполнить необходимый маневр «здесь» и «сейчас». Согласно этой идее, водитель подает знак находящимся позади него автомобилям той полосы, на которую он собирается переместиться. Те, в свою очередь, в ответ на его сигнал должны немного сбросить скорость и «отпустить» вперед, движущиеся перед ними машины, давая тем самым возможность образоваться в их потоке зазору необходимой величины. Издержки времени в этом случае распределяются между машинами той полосы, куда в итоге перестроился водитель.

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

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

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

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

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

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

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

Интенсивность потерь на участке перед съездом
Уходящим на съезд машинам, прежде чем они доберутся до пандуса (рис 2), приходится, порою даже несколько раз, перестраиваться в соседний ряд справа. Каждый такой маневр затрудняет движение, и в результате на участке перед съездом средняя скорость оказывается заметно ниже, чем на «транзитных» (лишенных съездов, «въездов» и развилок) участках автострады.


рис. 2

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

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

Пусть, к тому же, плотность ?, и мощность потока уходящего на съезд q ( среднее количество автомобилей, попадающих на пандус в единицу времени) одновременно малы, а s — обозначает число полос на шоссе. Чтобы попасть на съезд, водитель сделает сделает от 1 до s маневров перестроения. Если плотность потока на пандусе значительно меньше ?, то только последний маневр обойдется ему практически «за бесплатно», остальные же — в любом случае вызовут потери величиной ???. В среднем придется совершить (0 + 1 + 2 +… + s ? 1)/s = (s ? 1)/2 «дорогих» маневров.

Учитывая затруднения вызываемые всеми автомобилями, уходящими на съезд, мы можем выписать формулу интенсивности временных потерь:

I_out = q ? ?? ? (s ? 1)/2 = (?/2?) ? q ? (s??) ? (1 ? 1/s)

Величина p = (s??) — есть ни что иное, как мощность потока всех машин, движущихся по шоссе в рассматриваемом направлении (среднее количество машин, проезжающих мимо столба за единицу времени). Последнее замечание дает нам возможность переписать формулу для I в более симметричном виде:

I_out = (?/2?) ? pq ? (1 ? 1/s)

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


рис. 3

Пандус имеет лишь конечную протяженность, поэтому все вновь прибывающие автомобили волей-неволей должны будут встроиться в крайний правый ряд шоссе. Как следствие — плотность движения в крайней правой полосе оказывается локально выше, чем в среднем на дороге, поэтому часть находящихся в ней водителей принимает решение перестроиться в менее загруженный соседний ряд слева, что, в свою очередь, ведет к локальному повышению плотности уже и во второй полосе. Такой процесс междуполосной миграции будет длиться до тех пор, пока плотность потоков выравняется по всей ширине автострады. Предполагая среднюю скорость движения ? одинаковой для всех n полос, мы можем ожидать, что по завершению процессов миграции мощность потока в каждой из них увеличится ровно на (1/s)?q.

Чтобы посмотреть, во сколько водителям обходятся такие «рокировки», подсчитаем для начала мощности всех миграционных потоков. Поток со стороны пандуса в первую полосу шоссе мы уже знаем: он равен q. Чтобы получить баланс в виде прибавки (1/s)?q, поток во вторую полосу со стороны первой должен составлять уже (1 ? 1/s)?q, со стороны второй в третью — (1 ? 2/s)?q, со стороны k-той в (k + 1)-ю — (1 ? k/s)?q. Согласно последней формуле, мощность миграционного потока в крайнюю левую полосу составит (1 ? (s ? 1)/s)?q = (1/s)?q, как и велит этому быть здравый смысл.

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

I_in = ???q + ???(1 ? 1/s)?q + ???(1 ? 2/s)?q +... + ???(1/s)?q =

??q (1 + 2 +... + s)/s =

??q (s + 1)/2 =

(?/2?) ? q ? (s??) ? (1 + 1/s).

Снова вспоминая, что s?? — есть мощность p потока всех машин вдоль шоссе, получаем формулу издержек в ее окончательном виде:

I_in = (?/2?) ? pq ? (1 + 1/s).

Интенсивность потерь на симметричной развилке
В предыдущих пунктах мы нашли потери от взаимодействия потоков, один из которых был обязательно велик, а другой — обязательно мал. Чтобы продемонстрировать подход к решению задач, когда мощности обоих потоков соизмеримы по величине, рассмотрим другую крайность: развилку, у которой оба «дочерних» направления являются одинаково популярными для водителей (рис 4).


рис. 4

Для удобства, автомобили, уходящие на развилке в правую сторону, будем называть «синими», а уходящие в левую — «красными». Изначально автомобили обоих «цветов» движутся вперемешку, рассредоточенные между всеми 2s полосами шоссе. По мере приближения к развязке красные автомобили начинают медленно дрейфовать в сторону левых n полос, а синие — в сторону s правых: между соседними полосами возникают потоки миграции в обоих направлениях. В отличие от примера с подъездной дорогой, эти потоки уже не являются «относительно малыми». К слову, только между двумя центральными полосами происходит вынужденный обмен трафиком, интенсивность которого в любом из направлений (слева направо, или справа налево) равна четверти от мощности всего потока, движущихся по шоссе машин. К счастью, и в этой ситуации есть достаточно хороший способ оценить генерируемые издержки. Сначала заметим, что процесс разделения автомобилей на «красных» и «синих», скорее всего, начинается задолго до развилки и протекает медленно, поэтому, с одной стороны, он должен мало влиять на плотность движения внутри отдельного ряда, а с другой — делать миграционные потоки растянутыми на большие расстояния, давая, тем самым, возможность представить каждый из них, как совокупность большого числа потоков малой мощности (рис 5).


рис. 5

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


рис. 6

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

p = 2s?v.

Обозначим, как q₁, q₂,... q_m, потоки синих автомобилей, перемещающиеся по воображаемым перемычкам в правую половину автострады. Предположим, что незадолго до участка разделения в каждой полосе автострады оба цвета представлены с одинаковыми долями в 50%, откуда следует, что в сумме
q₁ + q₂ +... + q_m равны s?v/2, что составляет p/4.

Потери, генерируемые потоком q_i, в силу его малости мы можем подсчитать по формуле:

I_i = I_out + I_in = (?/2?)?(p/2)?q_i(1 ? 1/s) + (?/2?)?(p/2)?q_i(1 + 1/s) = (? /2?) pq_i

Суммируя последнее выражение по всем i, находим потери, генерируемые только синими автомобилями:

I_blue = (?/2?)?p?(q₁ + q₂ +... + q_m) = (?/2?) p²/4.

Полные потери, как уже упоминалось, окажутся вдвое вдвое выше и составят:

I_div = (?/2?) p²/2.

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

i_in = I_in/q = (?/2?) ? p ? (1 + 1/s)

i_out = I_out/q = (?/2?) ? p ? (1 ? 1/s)

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

Второе, интересное и совсем неожиданное наблюдение касается крайне слабого влияния на интенсивность генерируемых потерь количества полос у шоссе непосредственно рядом с развязкой. Как Вы можете заметить, взглянув на формулу для I_out, съезд, вообще, обходится дешевле всего для однополосной дороги ( s = 1, i_out = 0 ), а затруднения, вызываемые примыканием подъездной дороги для трехполосного и шестиполосного шоссе отличаются всего лишь на

100% ? [(1 + 1/3) ? (1 + 1/6)] / (1 + 1/3) = 12,5%.

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

i_av = (i_in + i_in)/2 = (?/2?) ? p.

Несмотря на отсутствие в формуле для i_av явной зависимости от количества полос, нужно помнить, что ее вывод ( смотрите предположения для I_in и I_out) существенно опирается на предположение о малой плотности машин на дороге, поэтому вряд ли она даст удовлетворительные результаты, будучи примененной к слишком узкому шоссе со слишком интенсивным движением.

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

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

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

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

1. коммутационные потери пропорциональны мощности потока на шоссе — не стоит без надобности укрупнять дороги, два маленьких шоссе в два раза лучше, чем одно большое;
2. коммутационные потери пропорциональны мощности боковых потоков — стоит проектировать сеть так, чтобы в своем путешествии водителю приходилось как можно меньшее число раз сворачивать в сторону;
3. взаимные помехи, которые причиняют друг другу водители основного и бокового потоков, должны в масштабах города стать меньше, если постараться сделать так, чтобы в один поток не объединялись маршруты, перекрывающиеся всего лишь на коротком участке пути.

Экономические предпосылки существования городов.
Модель города с «равномерным доступом»

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

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

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

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

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

Чтобы лучше представлять миграционные потребности населения, стоит начать с фундаментального вопроса: «Для чего вообще нужны города и какую полезную функцию они выполняют?».

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

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

Для примера возьмем не самую редкую профессию школьного учителя литературы. По статистике потребность в них составляет: примерно 1 учитель на 1000 человек населения. В обычной школе литературу преподают 3-4 человека. Выбор места работы для учителя литературы можно назвать конкурентным, если в его городе имеется хотя бы 4-5 среднеобразовательных школ, что в пересчете на население составляет примерно 15 тысяч человек.

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

После всего сказанного достаточно мотивированными выглядят две гипотезы (справедливость которых, однако, никак не влияет на истинность основного содержания статьи):

1. самые частые путешествия среднестатистический взрослый человек имеет потребность совершать на расстояния, захватывающие 4-5 наиболее перспективных для него места работы;
2. для значительной части населения, владеющей редкими и наиболее ценными, с экономической точки зрения, профессиями, расстояние наиболее частых путешествий вполне могут быть сопоставимыми с радиусом города.

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

Дорожные сети с простейшей топологией

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

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


(обособленный район Рио-де-Жанейро, автор фото неизвестен )

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


рис. 7

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

Итак, пусть все кварталы имеют одинаковую форму и размеры, а их число увеличивается в ?(лямбда) раз. Очевидно, что

• длинна главной дороги увеличивается в ? раз.

В силу принятой модели «равномерного доступа», 50% путешествий, начавшихся в правой половине города, завершаться в его левой половине (ровно как и наоборот), поэтому при росте числа кварталов в ? раз мощность потока, проходящего через середину города, вырастет тоже в ? раз. Аналогичные рассуждения с тем же самым выводом будут справедливы, если вместо середины взять любую точку, делящую город в заданном отношении (1:3, 2:5), из чего следует, что

• мощность потока машин вдоль главной дороги увеличивается в ? раз.
• необходимое на каждом участке число полос главной дороги увеличивается в ? раз.

Более-менее очевидно, что средняя длина путешествия, а вместе с ней и

• чистое время в путешествии, затрачиваемое на преодоление расстояние, увеличивается в ? раз.

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

I = I_in + I_out = (?/2?) p?2,

где p — это мощность потока на главной дороге. Мы уже знаем, что количество кварталов и мощность потока на главной дороге растет, как ?, поэтому общие потери времени, генерируемые сетью, увеличиваются в ?&sup2 раз. С другой стороны, количество путешествий, порождаемых сетью, между которыми в итоге и распределятся все эти потери, увеличивается в ? раз, откуда получаем, что

• чистое время в путешествии, теряемое из-за коммутационных издержек увеличивается в ? раз.

Соберем все результаты в одну табличку:

Линейный топология
Число адресных точек (кварталов ) единичной мощности.................................n
Общая площадь дорог.......................................................................................O(n²)
Чистое время в путешествии,
затрачиваемое на преодоление расстояния...................................................O(n)
Чистое время в путешествии,
теряемое из-за коммутационных издержек.....................................................O(n)
Число узлов коммутации...................................................................................O(n)
Число узлов коммутации с учетом мощности боковых потоков.....................O(n)

Использованная нотация: "y = O(x)", означает, что величины x и y функционально зависимы, причем когда x неограниченно растет, отношение x/y стремится к конечному не равному нулю числу.

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

Такие города договоримся называть «Клеточными».


(Лос-Анджелес, фото: Степанов Слава)

На рисунке 8 изображена схема Клетчатого города, составленного из n (с учетом «половинок») кварталов, образующих вместе правильный квадрат. Друг от друга кварталы отделяются в общей сложности vn дорогами, идущими, условно, с запада на восток, и еще vn дорогами, простирающимися с юга на север. В сумме эти эти дороги образуют vn?vn пересечений, каждое из которых может быть либо выполнено как светофорный перекресток, либо реализовано посредством автомобильного моста и эстакад.


рис. 8

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

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

Если число кварталов увеличивается в ? раз, то:

• площадь города увеличивается в ? раз, а его линейные размеры при сохранении пропорций —
  в v?,
• средняя длина путешествия и чистое время на преодоление расстояния, будучи пропорциональными линейным размерам, увеличиваются в v? раз,
• число улиц и количество примыкающих к одной улице кварталов увеличивается в v? раз,
• мощность потока уличного движения, будучи пропорциональной числу кварталов, с которыми поток «соприкасается» (объяснение этому факту будет дано позднее), увеличивается в v? раз,
• необходимая площадь всех дорог растет как (число улиц )?( длинна одной улицы )?(мощность уличного потока ) = v??v??v? = ?v?

Боковые потоки делятся на те, что идут от или в сторону кварталов и потоки трафика, сворачивающие с одной улицы на другую в местах их пересечения. Первые, согласно условиям, всегда остаются равными единице, через вторые, если учитывать, что кварталов в городе намного больше, чем кварталов на отдельно взятой улице, приходит либо покидает уличное шоссе почти весь трафик, который по нему движется. Как следствие, оценить изменение величины боковых потоков второго можно формуле (изменение мощности уличного потока)/(увеличение числа перекрестков на отдельно взятой улице) = v? / v? = 1. Равенство последнего отношения константе позволяет предположить, что эти потоки особенно не меняются с ростом числа кварталов, поэтому рост коммутационных издержек, генерируемых сетью в целом составит: (увеличение общего числа кварталов + перекрестков)?(изменение величины потока на отдельно взятой улице ) = ?v?. Поскольку мощность потока путешествий, генерируемых всеми кварталами увеличилась в ?, то

• чистое время в путешествии, теряемое из-за коммутационных издержек увеличивается в v?

Представим результат в виде таблички:

«Клеточная топология»
Число адресных точек (кварталов ) единичной мощности.................................n
Общая площадь дорог...................................................................................O(nvn)
Чистое время в путешествии,
затрачиваемое на преодоление расстояния.................................................O(vn)
Чистое время в путешествии,
теряемое из-за коммутационных издержек...................................................O(vn)
Число узлов коммутации...................................................................................O(n)
Число узлов коммутации с учетом мощности боковых потоков.....................O(n)

Сравнивая между собой Линейную и Клеточную сети, трудно не заметить, что увеличение объема ресурсов, необходимых для строительства, и времени, затрачиваемого на одно путешествие, с ростом города для первой сети происходит куда быстрее, чем для второй. К примеру, Клеточный город из 100 кварталов требует в 10 раз меньше асфальта, а путешествие по нему — в среднем в 10 раз меньше времени, чем это необходимо в Линейном городе той же величины. Таким образом, дорожные сети с Линейной топологией имеет смысл применять разве что в очень маленьких городках.

Если на время забыть о существовании коммутационных издержек, То Клеточная топология может считаться идеальным способом проектирования дорожных сетей, поскольку она дает асимптотически оптимальную O-оценку как для средней длины поездки, так и для необходимой площади дорог. Действительно, при любом более-менее «компактном» расположении города (с равномерным доступом ) длина путешествия будет расти не медленнее, чем квадратный корень из его площади, которая обычно прямопропорциональна численности населения. В итоге, мы получаем все те же O(vn).

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

Нижнюю возможную границу затрат на строительство (и содержание ) сети можно получить, вспомнив, что каждый автомобиль во время своего движения резервирует для себя часть полосы, в результате общая площадь дорог оказывается пропорциональна произведению средней длительности путешествия (средней длине поездки) на количество автомобилей в городе: O(vn)?O(n) = O(nvn) (сравните с таблицей для Клеточного города).

Если говорить о количестве времени, которое теряется в путешествии из-за коммутационных издержек, то удивительным образом его отношение к количеству времени, уходящего на преодоление расстояния, асимптотически не зависит от числа единичных кварталов ни в Клетчатом ни в Линейном городе (O(vn)/O(vn) = O(1), O(n)/O(n) = O(1) ). Другими словами, процентная доля времени, теряемого в путешествиях из-за коммутационных явлений, что в большом городе, что в маленьком, — будет одной и той же. Отсюда можно заключить, что, если не было серьезных проблем с коммутационными издержками в маленьком городе (скажем, они составляли 10-20% ), то и в большом городе их по-прежнему не должно наблюдаться, а если были, — тогда сами собой они никуда не уйдут, как бы город не рос и не укрупнялся.

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

Полезные примеры нереалистичных сетей

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

1) Без надобности не укрупнять дороги.
— Да. Движение трафика распределено по многим дорогам (сравните с Линейным городом ).

2) Избегать создавать условия, когда требуется сделать большое число поворотов за одно путешествие.
— Да. Любое путешествие скорее всего будет выполнено по маршруту, требующему всего одного поворота на городских улицах.

3) Избегать ситуаций, когда когда по одному участку дороги должны проходить путешествия, маршруты которых имеют лишь незначительный участок общего пути.
— Здесь, возможно, есть над чем поработать. Несмотря на минимальное количество поворотов, приходящихся на одно путешествие, его маршрут в составе основного потока шоссе проходит через большое количество узлов коммутации (O(n) ), в каждом из которых теряется драгоценное время.

Последнее замечание мотивирует исследовать такой вопрос: «Каково минимальное значение среднего числа узлов коммутации, через которое должно пройти путешествие внутри дорожной сети, связывающей n кварталов?»

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


(автор не известен)

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


рис. 9

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

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

Очевидное (для программистов ) решение, напрашивающееся здесь само собой, — использовать сбалансированное бинарное дерево, при этом нужно поместить единственную стартовую точку в вершину дерева, а оставшиеся n финишных точек расположить по одной в каждом его листе (рис 10). Построенную описанным способом сеть будем называть прямым Адресным деревом.


рис. 10

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

В тех случаях, когда n является степенью двойки, любой маршрут внутри Адресного дерева проходит ровно через log₂n коммутационных узлов, что несомненно (асимптотически) меньше, чем этот же показатель у сети с Клетчатой (O(vn) ), или Линейной (O(n) ) топологией.

Два простейших типа логарифмических сетей
Используя «древовидные» сети в качестве строительных блоков, не трудно обобщить предыдущее решение на случай, когда стартовых точек не одна, а — k. Существует сразу два простых способа, как это можно сделать.

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


рис. 11

Если k и n — степени двойки, то, в итоге, любой маршрут пройдет ровно через log₂k + log₂n узлов коммутации. Сети, построенные согласно описанному только что алгоритму, договоримся называть (однонаправленными) Логарифмическими с предварительным слиянием.

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

Чтобы завершить построение сети, осталось только соединить теперь уже каждую финишную точку обратным Адресным деревом с k ее воображаемыми дубликатами (сеть снизу на рис 11).

Всякий раз, когда n и k будут являться степенями двойки, число узлов коммутации на пути у любого маршрута внутри только что построенной сети снова окажется равным log₂k + log₂n. Сети такого вида условимся называть (однонаправленными ) Логарифмическими с предварительным разделением.

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

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

В действительности между однонаправленными и симметричными сетями нет какой-либо идейной пропасти: каждую симметричную сеть можно использовать и в качестве однонаправленной, а каждую однонаправленную, изначально соединявшую равное число стартовых и финишных точек, — переделать в симметричную (рис 12).


рис. 12

На рисунке 13a и 13b изображены «симметричные» формы Логарифмической сети с предварительным слиянием и Логарифмической сети с предварительным разделением. Их примеры показывают принципиальную возможность соединить n кварталов таким типом сетей, внутри которых число посещаемых коммутационных узлов во время любого путешествия будет пропорционально логарифму количества кварталов в городе.


рис. 13 a


рис. 13 b

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

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

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

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

(число записей )?log₂n символов.

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

Альтернативой непосредственной передачи закодированных имен конечных точек может служить способ, при котором для каждого путешествия указывается, в какое из возможных направлений свернул его маршрут на очередной встретившейся развилке. Согласно принятым нами допущениям все развилки в сети могут быть только двойными, поэтому для указания направления в каждом случае потребуется ровно 1 бит. Любому, кто располагает картой города и знает точку старта, принятой цепочки битов будет вполне достаточно, чтобы чтобы проследить за каждым маршрутом и и восстановить исходную последовательность их пунктов назначения. Если среднее число развилок (узлов деления ), посещаемых в течении одного путешествия, равно x, то длина длина двоичного сообщения при новом способе кодирования составит: (число записей )?x.

Как было раннее сказано, новый способ кодирования не может быть эффективнее метода прямой передачи двоичных адресов, поэтому: (число записей )?x ? (число записей )?log₂n, откуда:

x ? log₂n.

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

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

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

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

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

Коммутационные издержки в Логарифмических сетях

Если сравнивать сети с предварительным слиянием и предварительным разделением, то первая выглядит намного привлекательнее из-за своей простоты. К сожалению, у этой простоты есть и обратная сторона монеты: объединение всех маршрутов в один поток противоречит рекомендации i1, тем самым становясь потенциальной причиной больших временны?х потерь. Сеть с предварительным разделением вроде бы рекомендациям i1 — i3 следует, однако, судя по рисунку 13b, она тяготеет к быстрому разрастанию количества используемых дорожных ребер и коммутационных узлов. Последнее качество может сделать сети этого типа слишком дорогими для применения на практике.

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

Потери в сети с предварительным слиянием
На рисунке 14 вы можете видеть диаграмму потоков, возникающих при указанных договоренностях внутри сети с предварительным слиянием.


рис. 14

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

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


рис. 15

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

Предположим, что потока единичной мощности уже достаточно, чтобы эффективно заполнить дорогу хотя бы в две полосы. В этом случае мы приходим к довольно неожиданному выводу: объединение автомобильных потоков внутри Логарифмической сети с предварительным слияние происходит абсолютно «бесплатно», не вызывая каких-либо временны?х потерь.

Вычислить издержки, возникающие в правой правой половине — не многим труднее. Эта часть сети представляет собой прямое Адресное дерево, каждый узел которой является уже нами изученной ранее симметричной развилкой дорог. При мощности набегающего потока p интенсивность возникающих на развилке потерь равняется (?/2?)?p²/2. Мощность потока, поступающего на корневую развилку равна: n, следовательно интенсивность потерь в корневом узле составляет: (?/2?)?n²/2. В каждом следующем поколении Адресного дерева количество развилок удваивается, а мощность потока, набегающего на них — уполовиневается. В результате формула потерь внутри всего дерева примет вид:

I_{t_div1} = (?/2?)?(1/2)?[ n² + 2 (n/2)² + 4 (n/4)² +… + (n/2)?2² ] =

(?/2?)?(n/2)² [ 1 + 1/2 + 1/4 +… + 2/n ] ? (?/2?)?n²

Поскольку мощность потока путешествий, порождаемых совместно всеми адресными точками, равна n, то временны?е издержки, приходящиеся на одно путешествие в среднем составляют (?/2?)?n, показывая тем самым линейную зависимость от величины города.

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

Внутри Логарифмической сети с предварительным слиянием боковые потоки присутствуют только в прямом Адресном дереве, причем их суммарная мощность для каждого поколения узлов одна и та же: n/2. Всего в дереве log₂n поколений узлов, таким образом новый способ оценки сложности дает оценку сложности: O(n log₂n ).

Логарифмическая сеть с предварительным слиянием
Число адресных точек единичной мощности....................................................n
Средне время в путешествии,
теряемое из-за коммутационных издержек:
асимптотика......................................................................................................O(n )
точное значение.............................................................................................(?/2? )?n
Число узлов коммутации.................................................................................O(n )
Число узлов коммутации с учетом мощности боковых потоков...................O(n log₂n )

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

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


рис. 16

Первым делом оценим интенсивность генерируемых фрагментом коммутационных потерь.
Величину издержек, порождаемых при разделении потоков, можно найти, если подставить в формулу I_{t_div1} = (?/2?)?n², выведенную для прямого Адресного дерева в прошлом примере, вместо n — единицу. Действительно, прямые Адресные деревья на рисунках 16 и 14 имеют одинаковую глубину и проводят вдоль себя подобные по мощности потоки (_{прим. подобие означает возможность получить одно множество значений умножив значения из другого множества на некоторое фиксированное число, для иллюстрации может быть использовано подобие между треугольников по их сторонам} ). В силу квадратичной зависимости между величиной коммутационных издержек, возникающих на отдельной развилке, и мощностью подводимого к ней потока одновременное уменьшение всех потоков в n раз снизит потери во всем дереве в n² раз, поэтому вместо былых (?/2?)?n² мы получаем значение равное:

I_{t_div2} = (?/2?).

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


рис. 17

Предполагая осведомленность водителя о предстоящем сужении заблаговременной, можно считать, что процесс миграции машин из тупиковой полосы происходит медленно, оказываясь растянутым на сотни метров вдоль шоссе. В таком случае мы имеем право прибегнуть к уловке, использованной нами раннее для вычисления потерь на симметричной развилке — разбить общий миграционный поток q на много маленьких частей q_i, а затем каждую из них интерпритировать как боковой поток со стороны пандуса. Потери, порождаемые каждым таким подпотоком вычисляются по формуле:
I_i = (?/2?) ? pq_i ? (1 + 1/s), однако здесь имеются две тонкости.

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

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

I_i = (?/2?) ? pq_i ? (1 + 1/s),
а:
I_i = (?/2?) p(i) ? q_i ? (1 + 1/s).
В случае, когда много мелких частей, на которые разбивался миграционный поток, были все выбраны равной величины, зависимость p(i) выражается линейным графиком (рис 18 )


рис. 18

Для вычисления интенсивности общих потерь нужно либо прибегнуть к интегрированию, либо (это позволяет сделать особо простой вид интегрируемой функции ) в качестве p(i) взять среднее значение на графике, равное 3P/4. Поскольку суммарный миграционный поток со стороны каждой крайней полосы равен P/2, интенсивность потерь в отдельном узле слияния составит:

I_merge = 2 ? (?/2?) ? (3P/4) ? (P/2) =

= (?/2?) 3P²/4.

Чтобы найти временны?е потери, порождаемые внутри фрагмента на обратном Адресном дереве, применим формулу для I_merge к каждому его узлу:

I_{t_merge} = (3/4) ? (?/2?) [ 1?(1/2)² + 2?(1/4)² + 4?(1/8)² +… + (n/2)?(1/n)² ] ?

? (3/4) ? (?/2?) [ 1/4 + 1/8 + 1/16 +… ] =

= (3/8) ? (?/2?) [ 1/2 + 1/4 + 1/8 +… ] =

= (3/8) ? (?/2?).

Суммарные издержки, возникающие внутри фрагмента из-за слияния и разделения потоков составят:

I_{t_merge} + I_{t_div2} = (?/2?) [ 1 + 3/8 ] = 11/8 (?/2?).

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

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

К сожалению, лидерство не обходится «бесплатно». Несмотря на исчезающе малую величину подавляющего числа потоков, каждое Адресное дерево, входящее в состав сети, содержит порядка 2n двухполосных дорожных ребер и примерно n полноразмерных узлов коммутации. Всего в сети 2n деревьев, а значит — O(n²) ребер и узлов, что делает ее не только самой экономичной по времени, но и самой дорогой в постройке сетью, среди всех рассмотренных примеров.

Что касается суммы боковых потоков, то ее величина, как нетрудно сосчитать, растет со скоростью O(nlog2n) и в данном случае не несет в себе большого смысла.

Логарифмическая сеть с предварительным разделением
Число адресных точек единичной мощности....................................................n
Средне время в путешествии,
теряемое из-за коммутационных издержек:
асимптотика......................................................................................................O(1)
точное значение...............................................................................................11/8 (?/2? ).
Число узлов коммутации.................................................................................O(n² )
Число узлов коммутации с учетом мощности боковых потоков...................O(n log₂n )

Сбалансированная сеть логарифмического типа

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

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


рис. 19

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

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

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

Возвращаясь к Адресному дереву i-той точки, мы видим, что поступающий в корневой узел поток разделяется в нем на два дочерних потока мощностью 1/2 каждый. Первый поток-пасынок составляют путешествия, адресованные к точкам из интервала [ 1; n/2 ], второй — путешествия, адресованные к точкам из интервала [ (n/2) + 1; n ].
Следуя намеченной выше идее, объединим однотипные потоки пасынки у каждой нечетной точки и следующей за ней по порядку адресной точке с четным номером. Такой прием позволяет для каждой выделенной пары точек иметь вместо четырех потоков с мощностью 1/2 только два потока единичной величины (рис 20 ). Полученному в результате фрагменту будущей сети дадим аббревиатуру BN₂[ i; i +1].


рис. 20

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

Зачем нарушать сложившуюся традицию, ведь после объединения мы располагаем все тем же набором типов потоков, что и до него, но только с меньшим числом представителей каждого типа? — применим к каждому из выходных потоков BN₂[ i; i +1] ровно то же правило разделение, которое применялось бы к потоку его типа внутри Адресного дерева.

Нет ни одной причины, почему описанную выше логическую конструкцию по объединению-разделению однотипных потоков нельзя было бы повторять индуктивно. На рисунке 21 показана схема объединения двух фрагментов
BN₂ в один фрагмент BN₄, а на рисунке 22 — каким образом выглядит алгоритм в общем случае.


рис. 21


рис. 22

В конце концов процесс укрупнения фрагментов завершится и приведет нас к единственному элементу BN_n[ 1; n ], его мы назовем Сбалансированной сетью логарифмического типа (рис 23).


рис. 23

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

nodes( BN_k ) = 2 nodes( BN_k/2 ) + 2k,

с граничным условием:

nodes( BN₁ ) = 0.

Решением этой системы уравнений будет функция:

nodes( BN_n ) = 2nlog₂n.

Поскольку для построения BN_n требуется log₂n шагов индукции, то каждое путешествие будет проходить через log₂n узлов разделения и еще столько же узлов слияния, чередуя их на своем пути (рис 24 ).


рис. 24

Потери, генерируемые внутри каждого узла разделения:
(?/2? )? (1)² /2.

Потери, генерируемые внутри каждого узла слияния:
(?/2? )? 3? (1/2)² /4 = 3/16 (?/2? ).

Учитывая, что и тех, и других в Сбалансированной сети — nlog₂n, мы получаем точную величину общих коммутационных потерь:
11/16 (?/2? ) nlog₂n,

что в расчете на одно путешествие составляет:
11/16 (?/2? ) log₂n

Сбалансированная сеть логарифмического типа
Число адресных точек единичной мощности....................................................n
Средне время в путешествии,
теряемое из-за коммутационных издержек:
асимптотика......................................................................................................O( log₂n )
точное значение...............................................................................................11/16 (?/2? ) log₂n
Число узлов коммутации.................................................................................O( n log₂n )
Число узлов коммутации с учетом мощности боковых потоков...................O( n log₂n )

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

Почему исторические города оказываются обречены на «пробки»

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

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


(дороги Москвы, фото: Степанов Слава )

Если говорить о длине пути, который в городе должен по дорогам проехать водитель, то реализации этого типа сетей показывают себя неплохо: пройденное расстояние зачастую мало отличается от расстояния по прямой, а его среднее значение по городу, как и положено для «приличных» транспортных систем, растет со скоростью O( vn ). Вся беда состоит в том, что с укрупнением города у Логарифмической сети с предварительным слиянием слишком быстро растут генерируемые ею коммутационные издержки: величина времени, на которое в среднем из-за них удлиняется путешествие, зависит от количества людей, проживающих в городе как O( n ). Понятное дело, что начиная с некоторого n, это время станет превалировать над чистым временем преодоления расстояния, иными словами, в городе появятся «пробки».

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


(ночной Берлин, фото: Vincent Laforet)

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

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


(обновленная дорожная сеть Барселоны, фото: Vincent Laforet)

Детальный взгляд на сети Линейного и Клеточного городов

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

Линейный город
В этот раз рассмотрим пример города, в котором имеется две улицы с односторонним движением: Западная с движением на север и Восточная с движением на юг (рис 25).


рис. 25

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

Определим для начала мощности боковых потоков на уличных шоссе. Западная
улица является единственным путем, которым можно попасть в квартал с номером i из
(n ? i) кварталов, лежащих от него к югу, и единственным путем, по которому от квартала i можно добраться до (i ? 1) кварталов, расположенных севернее него. Отсюда следует, что мощности потоков обмена трафиком между Западной улицей и i -тым кварталом равны:

q_{W_out} = (n ? i)/n — для бокового потока, покидающего Западную улицу,
q_{W_in} = (i ? 1)/n — для бокового потока, примыкающего к движению на ней. Понятное дело, что мощности боковых потоков на Восточной улице зависят от i симметричным образом:
q_{E_out} = (i ? 1)/n — мощность покидающего,
q_{E_in} = (n ? i)/n — мощность примыкающего к движению на Восточной улице бокового потока.

Разумеется, сумма покидающих i-тый квартал потоков:

q_{E_in} + q_{W_in} = (n ? 1)/n,
совпадает с суммой потоков, поступающих в него:
q_{E_out} + q_{E_out} = (n ? 1)/n,
и обе этих величины никак не зависят от i (у каждого квартала есть поток путешествий величины 1/n, которые как начинаются, так и заканчиваются внутри него самого ).

Чтобы найти мощности основных потоков, проведем поперек Западного шоссе воображаемую линию на одном уровне с i-тым кварталом. Всего эту линию будут пересекать:
(число кварталов снизу )?(число кварталов сверху ) = (n ? i)(i ? 1) маршрутов, создающих вместе поток величиной:

P_W(i) = (n ? i)(i ? 1)/n.

Той же самой формулой:
(число кварталов снизу )?(число кварталов сверху )/n,
должна выражаться и мощность P_E потока движения на Восточной улице, иначе говоря:

P_E(i) = P_W(i) = P(i).

Зная мощности всех основных и боковых потоков, мы можем вычислить интенсивность потерь, возникающих в сети на участке возле i-го квартала:

I(i) = (?/2?) ? P(i) ? [ (q_{E_in} + q_{W_in})?(1 + 1/s) + (q_{E_out} + q_{E_out})?(1 ? 1/s) ] =
= (?/2?) ? P(i) ? [ (1 ? 1/n) ? (1 + 1/s) + (1 ? 1/n) ? (1 ? 1/s) ] =
= (?/2?) ? 2P(i) ? (1 ? 1/n) =
= 2(?/2?) ? (1 ? 1/n) ? (n ? i)(i ? 1)/n =
= 2(?/2?) ? (1 ? 1/n) ? (n ? i) ? (i ? 1) ? (1/n).

Если просуммировать последнее выражение по i, то получится интенсивность потерь, генерируемых всей сетью в целом.

I = ?_i I(i)
= ?_i 2(?/2?) ? (1 ? 1/n) ? (n ? i) ? (i ? 1) ? (1/n) =
= 2(?/2?) ? (1 ? 1/n) ? n² ? ?_i (1 ? i/n) ? (i/n ? 1/n) ? (1/n) ?
? 2(?/2?) ? n² ? ?_i (i/n) ? (1 ? i/n) ? (1/n).

Сумму ?_i (i/n) ? (1 ? i/n) ? (1/n) при сколько-нибудь больших n с хорошей точностью можно заменить интегралом:

? t (1 ? t) dt (t?[0; 1] ) = 1/2 ? 1/3 = 1/6.

Откуда получаем, что интенсивность коммутационных потерь в Линейном городе с n кварталами единичной мощности составляет:

I = (?/2?) n²/3.

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

Возьмем город с m кварталами. Если бы кварталы порождали потоки мощности 1, то коммутационные потери составляли бы (?/2?) m²/3. Увеличение каждым кварталом мощности продуцирования путешествий в ? раз ведет к увеличению в ? и основных и боковых потоков одновременно, поэтому издержки на каждой развязке, а значит внутри сети в целом увеличиваются в ?² раз, и формула потерь приобретает вид:

I = (?/2?) m² ? ?²/3.

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

I = (?/2?) m²? ?²/3 =
= (?/2?) (m??)²/3 =
= (?/2?) n²/3.

Иначе говоря, коммутационные потери в Линейном городе от мелкости его разделения на кварталы никак не зависят.

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

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

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

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


рис. 26

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


рис. 27

Дабы избежать множества неудобных оговорок, будем считать, что ход, в котором ладья никуда не смещается, тоже допустим по нашим правилам. Маршрут движения ладьи, состоящий из двух ходов, один из которых совершается обязательно по вертикали, а другой — по горизонтали, назовем простейшим. Ход «на месте» разумно считать и вертикальным, и горизонтальным одновременно. В таком случае оказывается справедливым утверждение, что любые две клетки на доске соединены друг с другом ровно двумя различными простейшими маршрутами.

Для водителей «простейший» маршрут является самым легким способом доехать с минимальными помехами от одной территориальной зоны в другую, поэтому разумно предположить, что именно вдоль элементарных маршрутных линий и будут проходить реальные путешествия. Порождаемой адресной точкой (территориальной зоной) поток единичной мощности согласно модели «равномерного доступа» должен в равных долях распределятся между всеми n = d² адресными точками города, тем самым мощность проходящего по одной маршрутной линии потока путешествий составляет 1/(2n).

Подсчитаем, поток какой величины проходит через клетку ( i, j ) в направлении с юга на север. Простейший маршрут пересекает клетку ( i, j ) в направлении с юга на север исключительно в двух ситуациях. Первая из них (рис 28 слева):

1a) начальная клетка маршрута находится в одной из последних (d ? i) горизонталей (строк);
2a) конечной точкой маршрута является одна из первых (i ? 1) клеток j-той вертикали (столбца);
3a) маршрут начинается с горизонтального участка, либо целиком лежит внутри j-того столбца.


рис. 28

Условия, описывающие вторую ситуацию выглядят симметрично (рис 28 справа):

1b) начальной точкой маршрута является одна из последних (d ? i) клеток j-той вертикали;
2b) конечная клетка маршрута находится в одной из первых (i ? 1) горизонталей
3b) маршрут начинается с вертикального участка, либо целиком лежит внутри j-того столбца.

На шахматном поле имеется всего 2? [ d? (i ? 1) + 1? (i ? 1) ] ? (d ? i) подходящих под требования простейших маршрутов, которые вместе создают поток мощностью:

P_SN( i, j ) = (d + 1)?(i ? 1)?(d ? i) /n ( = P_SN( i ) ).

Зафиксировав j, мы получаем функцию

(P_SN)_j ( i ) = P_SN( i, j = Const ),

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

Начнем, пожалуй, с обстоятельства, которое было бы трудно упустить из виду: P_SN( i, j ) фактически не зависит от второго аргумента. Как следствие, функции (P_SN)_j ( i ) = P_SN( i ) имеют одинаковый вид при всех значениях j, иными словами, конкретное положение улицы внутри Клеточного города на величину ее загруженности никак не влияет. Формально, последнее утверждение доказано лишь для шоссе, ведущих на север, но из-за симметрий города оно автоматически распространяется и на шоссе остальных направления тоже.

Посмотрим теперь на саму формулу для P_SN( i ):

(d + 1)?(i ? 1)?(d ? i) /(2n).

Как мы видим, вся зависимость P_SN от i заключается в выражении (i ? 1)?(d ? i). Это выражение может быть интерпретировано как произведение длин правого и левого интервалов, на которые распадается целочисленный отрезок длины d после исключения из него i-го по счету элемента (рис 29a).


рис. 29a


рис. 29b

Понятное дело, что при изменении «право» на «лево», а «лево» на «право» (рис 29b) результат произведения останется прежним. Из такого простого по своей сути наблюдения следует два очень полезных для нас вывода:

1. функция P_SN( i ) симметрична относительно серединной точки улицы i = (d + 1)/2, иначе говоря, мощность потока на удалении ? от нижней границы города ровно такая же, как и на удалении ? от верхней границы.
2. В целом сам город вверх-вниз симметричен, поэтому чтобы получить функцию (P_NS)_j ( i ), описывающую мощность потока движения на j-том по счету шоссе, но в южном направлении, достаточно просто-напросто зеркально отразить график функции (P_SN)_j ( i ) в прямой i = (d + 1)/2. Поскольку (P_SN)_j ( i ) = P_SN( i ), а график P_SN( i ) относительно прямой i = (d + 1)/2 симметричен, то (P_NS)_j ( i ) = P_SN( i ) = P_vert( i ), другими словами, прямой и встречный потоки уличного движения имеют равную мощность в любой точке города. Приближенный график P_SN( i ) изображен на рисунке 30 (считается, что d >> 1, i >> 1, d ? i >> 1).

рис. 30

Мощности основных потоков вдоль горизонтальных шоссе легко находятся с помощью поворотных симметрий, формально этот процесс сводится к простой замене i на j в P_SN( i ) и небольшой редакции нижнего индекса.

Следующее, что нужно сделать — это найти мощности боковых потоков. Путешествия, вливающиеся или покидающие движение на вертикальном шоссе внутри клетки ( i, j ), удобно поделить на четыре категории:

1. поток q_{in_transit}: начальная — любая клетка i-той горизонтали, конечная — любая клетка j-той вертикали, кроме самой ( i, j) (рис 31a);
2. поток q_{out_transit}: начальная — любая клетка j-той вертикали, кроме самой ( i, j ), конечная — любая клетка i-той горизонтали (рис 31b);
3. поток q_in: начальная — сама клетка ( i, j ), конечная — любая клетка вне i-той горизонтали (рис 31c);
4. поток q_out: начальная — любая клетка вне i-той горизонтали. конечная — сама клетка ( i, j ) (рис 31d).

рис. 32: a b c d

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

q₀ = d? (d ? 1) /(2n)

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

I_vert( i, j ) = (?/2?)? P_vert( i )? [ (q_in + q_{in_transit})?(1 + 1/s) + (q_out + q_{out_transit})?(1 ? 1/s) ] =
= 4 (?/2?)? (d + 1)(i ? 1)(d ? i)? d(d ? 1) /2n² ?
? 2 (?/2?)? d⁵? (i/d)(1 ? i/d)? (1/d)⁴ =
= 2 (?/2?)? d²? (i/d)(1 ? i/d)? (1/d).

Чтобы найти издержки, порождаемые на вертикальных улицах внутри всего города, нужно просуммировать I_vert( i, j ) по обоим индексам:

I_vert = ?_ij I_vert( i, j ) =
= 2 (?/2?)? d²? ?_ij (i/d)(1 ? i/d)? (1/d).

Поскольку величина слагаемых никак не зависит от j, суммирование по второму индексу эквивалентно умножению на d:

?_ij (i/d)(1 ? i/d)? (1/d) = d? ?_i (i/d)(1 ? i/d)? (1/d).

Последнюю сумму можно приблизить уже знакомым нам интегралом:

?_i (i/d)(1 ? i/d)? (1/d) ? ? t (1 ? t) dt (t?[0; 1] ) = 1/2 ? 1/3 = 1/6.

Откуда получаем, что

I_vert = (?/2?)? d³ /3 = (?/2?)? nvn /3.

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

I_horiz = I_vert = (?/2?)? nvn /3.

Таким образом, интенсивность коммутационных потерь внутри всей сети Стандартного Клеточного города равна:

I = I_vert + I_horiz = 2/3? (?/2?)? nvn,

а на одно путешествие в среднем приходятся издержки величиной

2/3? (?/2?)?vn

Влияние размера клетки на величину коммутационных потерь
Кварталы, порождающие потоки единичной мощности — довольно искусственное ограничение условий задачи. Расширим полученные выше результаты на случаи, когда мощность порождаемого одной территориальной клеткой потока путешествий равна ?.
Пусть город состоит из m таких клеток. Если бы все клетки имели только единичную мощность, то интенсивность общих коммутационных потерь составляла бы I₁ = 2/3? (?/2?)? mvm. Увеличение количества совершаемых путешествий в ? раз в ? раз повысит мощности всех основных и боковых потоков уличных шоссе, что в свою очередь заставит в ?² раз вырасти все генерируемые внутри города коммутационные издержки. Новая формула для интенсивности потерь тем самым примет вид:

I = 2/3? (?/2?) ?²? mvm

Если считать, клетка состоит из ? адресных точек единичной мощности, то полное число таких точек составит: n = ?m. Давайте выразим I как функцию n и ?:

I = 2/3? (?/2?) ?²? mvm =
= 2/3? (?/2?) ? v?? (?v?)? (mvm) =
= 2/3? v? (?/2?)? (?m)v(?m) =
= 2/3? v? (?/2?)? nvn.

Средние издержки, приходящиеся на одно путешествие в новых условиях, составят 2/3? v? (?/2?)? vn, оказавшись в v? раза больше по сравнению с их величиной в городе, составленном из кварталов единичной мощности.

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


(Центр Нью-Йорка фото: Vincent Laforet)

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

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


(деловые кварталы Лос-Анджелеса днем, фото: Борис Шеин)

Применение светофорных развязок в сетях с Клеточной топологией имеет свои особенности. В главе 1 было показано, что при правильной синхронизации светофорных циклов автомобилям, пока они движутся вдоль одной и той же улицы, даже не придется останавливаться на перекрестках: в их сторону всегда будет гореть зеленый свет. Такого рода феномен обычно называют режимом зеленых волн. Чтобы его создать, потоки уличного движения нужно поделить на чередующие друг друга зоны двух типов: заполненные автомобилями и свободные от них. Далее подбирается такой режим работы светофоров, что в промежуток времени, когда очередная «порция» проезжает перекресток по одной из улиц, предыдущая порция машин, движущихся по перпендикулярной улице его уже миновала, а следующая — еще не подошла (рис 33).


рис. 33

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

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

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

Интересно заметить, что в режиме зеленых волн слегка меняются правила, по которым внутри сети происходит коммутация маршрутов путешествий. Например, присоединение еще одного автомобиля к основному потоку движения на уличном шоссе может быть выполнено в промежутках между заполненными зонами, не вызывая таким образом каких-либо серьезных коммутационных издержек (точка «1» рис 34a).


рис. 34

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

Совсем иначе обстоит дело, если автомобиль пытается покинуть движение на уличном шоссе (рис 34b). Здесь, по всей видимости, уже нет каких либо хитрых способов, как сделать создаваемые им коммутационные потери меньше. Более того, из-за удвоения локальной мощности потока внутри заполненных зон удаление из него произвольно выбранного автомобиля обходится по издержкам времени в два раза дороже, чем в городе с эстакадными развязкам. В сумме удешевленный «вход» и подорожавший «выход» из уличных потоков компенсирую друг друга, делая Светофорный Клеточный город в этом отношении ни чуть не лучше, но и не хуже Стандартного.

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


рис. 35

В результате таких изменений число улиц удвоится, все они станут односторонними, но самое главное — сильно упростятся развязки (рис 36).


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

Дорожные сети с продвинутой архитектурой

«Линейная» улица.

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

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

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

В таком случае вполне правдоподобно выглядит, что зародившийся внутри квартала ( i, j ) поток путешествий, покидая его, распределяется между ближайшими улицами следующим образом: 1/4 от него попадет на горизонтальную дорогу сверху, еще 1/4 — на горизонтальную дорогу снизу, 1/4 ?i/d утекает по вертикальному шоссе на север и еще
1/4 ?(1 ? i/d) — по второму вертикальному шоссе на юг (рис 37).

рис. 37

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

Что касается потока путешествий, направленных во внутрь ( i, j ), то правило его разделение относительно окружающих квартал шоссе, будет иметь симметричный характер ( рис 38).


рис. 38

Среди четырех смежных с кварталом ( i, j ) перекрестков рассмотрим отдельно боковые потоки на пересечении нижнего горизонтального шоссе и вертикальной улицы с движением на север (рис 38). Поток машин, въезжающих с горизонтальной улицы на вертикальную равен:
1/2? (число кварталов на горизонтали)?(число кварталов на вертикали не ниже ( i, j ))? 1/ d² =
= 1/2? d? i/d² =
= 1/2? i/d.
Величина бокового потока в противоположном направлении составляет:
1/2? (число кварталов на вертикали строго ниже ( i, j ))?(число кварталов на вертикали)? 1/d² =
= 1/2? (d ? i)? d/d² =
= 1/2? (1 ? i/d).

Давайте теперь переведем внимание с Клеточного города в целом на какую-либо его одну вертикальную улицу, назовем ее My_street. В силу симметрий мы ни сколько не ограничим своих рассуждений, ели будем считать, что движение по My_street направлено с юга на север (рис 39).


рис. 39

Рисунок 40 изображает графики мощности основного и боковых потоков на шоссе вдоль My_street, которые, как может заметить читатель, невероятно похожи на аналогичные графики для одностороннего шоссе Линейного города (рис 26).



рис. 40

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

Продвинутая сеть для Линейного города
И так, перед нами стоит задача, так улучшить Линейную сеть, чтобы при этом она не превратилась в «квадратную». Обстоятельством, вносящим самую большую неэффективностью в функционировании Линейной сети, является объединение ею всех маршрутов всего лишь в два очень крупных потока движения. В этой ситуации разумным шагом было бы разделить потоки вдоль обоих ее уличных шоссе на Q равных частей. Поскольку временные издержки, причиняемые каждым автомобилем, присоединяющимся или покидающем движение на дороге, пропорциональны интенсивности движения на ней, то в результате разделения уличных магистралей на Q изолированных частей ( рис 41a) коммутационные потери внутри Линейного города должны были бы снизится в Q раз.


рис. 41

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

Похожую идею вы можете увидеть в схеме движения лифтов внутри многоэтажных зданий. Там каждый лифт позволяет войти и выйти из него не на всех этажах, а на только в пределах определенного интервала высот. Принимая эту концепцию, давайте более детально рассмотрим дорогу r_k, открывающую доступ к отрезку ?_k = (x_k, x_{k +1} ] для путешествий начавшихся (нестрого) южнее x_k (считается, что нумерация кварталов выполнена снизу вверх). Со стороны каждого квартала, номер которого (нестрого) меньше x_k, на дорогу r_k поступает поток q_in мощностью |?_k|/n ( по 1/n в адрес каждого квартала внутри ?_k ), в то же самое время предполагается, что возможность свернуть с r_k в сторону любого из упомянутых кварталов отсутствует либо в силу установленных правил движения, либо из-за особой конструкции дорожной сети.

Накопленные на отрезке [1, x_k] автомобили в итоге поровну распределятся между кварталами из ?_k, поэтому, если бы не существовало путешествий, начало и конец которых лежат внутри ?_k, то боковые потоки q_out в направлении каждого из кварталов на этом участке имели бы мощность x_k/n (рис 42).


рис. 42

В действительности вклад «внутренних» путешествий в мощность боковых потоков также имеет место быть, однако величина этого вклада никогда не превышает |?_k|/n, поэтому в случае, когда x_k >> |?_k|, ею можно попросту пренебречь. Мощность p_k основного потока вдоль r_k при сделанных упрощениях будет представляться графиком из двух прямолинейных участков с максимумом P_k равным x_k? |?_k|/n. Приближенное значение коммутационные потерь на r_k можно найти по формуле формуле:

I_k = (?/2?)? ?_x[ q_in(x)? p_k(x)? (1 + 1/s) ] + (?/2?)? ?_x[ q_out(x)? p_k(x)? (1 ? 1/s) ] =

= (?/2?)? (1 + 1/s)?_x[ |?_k|/n? p_k(x) ] + (?/2?)? (1 ? 1/s)?_x[ x_k/n? p_k(x) ] =

= (?/2?)? (1 + 1/s)? (x_k? |?_k|/n)? (?_xp_k(x) )/x_k + (?/2?)? (1 ? 1/s)? (x_k? |?_k|/n)? (?_xp_k(x) )/|?_k|,

где первая сумма берется по участку x ? [1, x_k], а вторая — по x ? ?_k. Выражения:

(?_xp_k(x) )/x_k, x? [1, x_k] и

(?_xp_k(x) )/|?_k|, x? ?_k

есть не что иное, как средние мощности потока вдоль r_k внутри указанных промежутков. Поскольку график мощности в пределах этих промежутков имеет вид прямой, то средняя мощность в обоих случаях составляет P_k/2. Заменяя
x_k? |?_k|/n на
P_k,
мы наконец приводим формулу для интенсивности потерь к ее наиболее простому виду:

I_k = 2 (?/2?)? P_k? P_k/2 = (?/2?)? P_k²

Попытаемся теперь вычислить последовательность x_k номеров тех кварталов, по которым должно происходить разбиение Линейного города на отрезки. В качестве критерия выбора отрезков примем требование, чтобы максимальные мощности потоков движения P_k на подходящих к ним дорогах имели одинаковое значение, не зависящее от k, иначе говоря, выполнялось равенство:

x_k? |?_k| = Const.

Вспоминая, что |?_k| = x_{k + 1} ? x_k, мы приходим к разностному уравнению:

x_{k + 1} ? x_k = Const/x_k.

Считая x и k непрерывными переменными, и заменяя

x_{k + 1} ? x_k = x(k + 1) ? x(k)

на dx/dk? 1,

мы можем приблизить разностное уравнение дифференциальным:

dx/dk = Const/ x <=> xdx = Const? dk.

Откуда получаем для x_k решение в общем виде:

x_k = С₁ v( k + С₂).

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

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


рис. 43

Именно середину первого отрезка и стоит считать точкой x₁ в формуле для x_k. Отсюда мы получаем первое граничное условие:

x₂ = 2x₁ или

v( 2 + С₂) = 2? v( 1 + С₂) =>

С₂ = ? 2/3.

Второе граничное условие получается из того требования, что дорог и отрезков всего ровно Q, а значит x_{Q + 1} должен быть равен следующему за наибольшим по номеру кварталу в городе:

С₁ v( Q + 1 ? 2/3) = n + 1, откуда

С₁ ? (n + 1)/vQ.

Таким образом:

x_k ? (n + 1)? v(k ? 2/3)/vQ,

|?_k| ? dx/dk = (n + 1)/ 2v(k ? 2/3)?vQ

P_k = x_k? |?_k|/n =

= (n + 1)²/ 2n? Q ? n/ 2Q

I_k = (?/2?)? P_k² =

= (?/2?)? (n/ 2Q)².

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

I = 2Q? (?/2?)?(n/ 2Q)² = (?/2?)? n²/ 2Q.

Как вы видите, желаемое достигнуто: после разбиения главных шоссе на Q частей потери действительно сократились в Q раз ( если не считать возросшего по сравнению с формулой для обычного Линейного города от 1/3 до 1/2 постоянного коэффициента). Что же, полдела сделано, остается применить полученный результат для улучшения города с Клеточной архитектурой.

«Небоскребный лифт» в Клеточном городе
Для простоты будем довольствоваться примером города в котором все улицы односторонние. Используя аналогию между Линейным городом и отдельными улицами Клеточного города, поделим шоссе вдоль последних на Q частей. По умолчанию считается, что покидая квартал, вы можете попасть на любое проходящее рядом с ним шоссе. В то же самое время среди всех шоссе проложенных вдоль одной улицы поворот в сторону конкретного квартала имеется в точности с одной из них. В процессе установления правил исключительно важной является их однообразие и простота. Посмотрите на рисунок 44:


рис. 44

все улицы имеют одинаковый вид и одинаковые правила, какая из их дорог в какие по счету кварталы открывает доступ. На рисунке 45 изображена схема разрешенных поворотов между шоссе. Глядя на эту картину трудно не запутаться. Так же говорят часто и о схеме метро в каком-нибудь большом городе. Однако в обоих случаях все становится понятным и простым, если вы узнаете логику задумки. Логическое правило разрешенных поворотов звучит довольно просто: если проезжая по шоссе вы пересекаете перпендикулярные к вашему движению дороги и можете свернуть в квартал, находящийся прямо за ними, то имеете возможность свернуть и на любую из этих дорог.


рис. 45

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

О проблемах транспорта и работе математика

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

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

Надеюсь, все изменится к лучшему.

Благодарю за внимание и желаю удачи!
Сергей Коваленко.

2019 год
magnolia@bk.ru


(Фото: Vincent Laforet)