Любое строительство, будь то сарай для дров или новый микрорайон огромного мегаполиса, требует тщательного планирования. В противном случае можно получить результат, далекий от желаемого. В аспекте урбанизма, который распространяется по миру с небывалой скоростью, планирования много не бывает, ведь разумный градостроитель должен учесть все нюансы, от расположения домов и улиц до расположения автомобильных дорог и пешеходных тропинок. Если с дорогами для машин все более-менее понятно, то вот с дорогами для велосипедистов порой возникают трудности. Чаще всего это связано с тем, что о велосипедистах думают в последнюю очередь, не учитывая их нужды в начале проектирования района или города в целом. Ученые из Дрезденского технического университета (Германия) разработали алгоритм для построения сети велодорожек на основе спроса, т. е. пожеланий и нужд самих велосипедистов. Как работает алгоритм, какие факторы он учитывает, и насколько хороши построенные им маршруты? Ответы на эти вопросы мы найдем в докладе ученых.

Основа исследования

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

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

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

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

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

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

Остовное дерево графа* — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа.

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

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

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

Результаты исследования

Польза велосипедных дорожек в основном зависит от их использования и, в свою очередь, от маршрутов велосипедистов. Выбор маршрута велосипедистом был сопоставлен с задачей поиска кратчайшего пути на графе предпочтений G = (V, E) с N = ∣V∣ числом узлов (перекрестков) и M = ∣E∣ числом ребер (отрезков улицы). В итоге был получен граф предпочтений G из физической сети улиц G^street. Оба графа имеют один и тот же набор узлов V. Каждое ребро e_ij ∈ E в графе предпочтений велосипедистов представляет собой сегмент улицы, соединяющий перекрестки i, j ∈ V, и ему присваивается воспринимаемое расстояние:



где l^street_ij обозначает физическую длину соответствующего участка улицы e^street_ij в уличной сети, а p_ij ∈ {p^B_ij, p⁰_ij} — штрафной коэффициент, суммирующий предпочтения велосипедистов против движения по участку e_ij.

Массив участков улиц, оборудованных велосипедными дорожками E_B ⊆ E, содержит участки улиц e_ij ∈ E_B без штрафа за расстояние (p^B_ij = 1). Сегменты улиц, не входящие в это множество, e_ij ∉ E_B имеют штрафные коэффициенты p⁰_ij > 1.

Учитывая этот граф предпочтений велосипедистов, можно предположить, что велосипедисты выбирают свой маршрут на основе кратчайшего пути Π*_i→j = argmin [L_i→j(Π_i→j)] между пунктом отправления i и пунктом назначения j, сводя к минимуму расстояние:



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


Изображение №1

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

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

Сеть велодорожек города была описана как подграф G_B = (V, E_B) ⊆ G^street сети улиц города, в котором каждый отрезок улицы e_ij ∈ E может (e_ij ∈ E_B) или не может (e_ij ∉ E_B) быть оборудован велосипедной дорожкой. Даже в этой простой двоичной модели количество возможных сетей велосипедных дорожек G_B экспоненциально увеличивается с количеством ребер (M) в уличной сети, поскольку каждый сегмент улицы может быть оборудован велосипедной дорожкой, а может и не быть оборудован (таким образом, существует 2^M возможных подграфов).

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

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


Изображение №2

В частности, создается последовательность {G_B(M′)}_M′ сетей велосипедных дорожек, где M′ ∈ {0, 1, …, M} сегментов улиц снабжены велосипедными дорожками (изображение №2): процесс начинается с оптимальной сети велосипедных дорожек, в которой каждый сегмент улицы оборудован велосипедной дорожкой (E_B(M) = E) такой, что не имеет штрафа ни для одного сегмента улицы (p_ij = p^B_ij = 1 для всех ребер). Затем вычисляется выбор велосипедистами маршрута в их графе предпочтений G (как описано выше) на основе распределения спроса n_i→j, которое обозначает количество велосипедистов, путешествующих из узлов i в j.

Чтобы построить семейство сетей велосипедных дорожек, производилось поэтапное удаление наименее важных дорожек e*_ij(M′) из сети, E_B(M′ − 1) = E_B(M′) ⧵ {e*_ij(M′)}, корректируя штраф для этого сегмента улицы от p⁰_ij = p^B_ij = 1 до p_ij = p⁰_ij > 1 в графе предпочтений велосипедистов (G).

Важность велодорожки e_ij ∈ E_B(M′) количественно определялась в текущем состоянии сети велосипедных дорожек (с оставшимися велосипедными дорожками M′) как произведение p⁰_ijn_ij(M′) штрафа p⁰_ij (если на улице не было велосипедной дорожки) и количества велосипедистов, использующих этот участок улицы n_ij(M′).

После каждого изменения графа предпочтений велосипедистов (G) решения велосипедистов о выборе маршрута обновлялись. Это гарантировало, что алгоритм постоянно адаптировался к спросу велосипедистов с учетом доступного в настоящее время набора велосипедных дорожек E_B(M′).

Процесс завершался пустой сетью велосипедных дорожек G_B(0) = (V, ∅), когда все велосипедные дорожки были удалены.

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

Входными данными для алгоритма являются:

• сеть улиц G^street;
• штрафные коэффициенты p⁰_ij для каждого участка улицы, не оборудованного велосипедной дорожкой;
• распределение спроса n_i→j;
• модель выбора маршрута велосипедистами.

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


Изображение №3

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

Эти два города были выбраны не случайно, так как относятся к двум разным архетипам локального спроса: пространственно однородного (велосипедами пользуются по всему городу в равной степени) и пространственно неоднородного (велосипедами пользуются в одних районах больше, чем в других). В Гамбурге наблюдается первый архетип (3c и 3d), а в Дрездене — второй (поездки на велосипеде, к примеру, от дома к университету и обратно; 3a и 3b).

Используя имеющиеся входные данные, алгоритм генерировал семейство сетей велодорожек ({G_B(M′)}_M′) для обоих городов. Была выбрана сеть, в которой все основные и второстепенные (P + S) сегменты улиц (согласно их классификации в OpenStreetMap) оборудованы велосипедными дорожками. Затем эту сеть сравнили со сгенерированной сетью с той же общей длиной Λ(M′) = Σ_{e ∈ EB(M′)} l^streetstreet_e велосипедных дорожек так, что Λ(M′) = Λ_P+S.

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


Изображение №4

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

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

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

Для количественного сравнения семейств велосипедных дорожек для обоих городов длина велосипедных дорожек λ = Λ(M′)/Λ(M₀) была нормализована по отношению к длине Λ(M₀) после удаления всех неиспользуемых велосипедных дорожек (2b). Общее воспринимаемое расстояние определялось на графе предпочтений (спроса) велосипедистов как:



где L_i→j(Π, λ) = Σ_e∈Πl_e(λ). l_e(λ) обозначает эффективную длину сегмента улицы e в графе предпочтений велосипедистов G для заданного набора велосипедных дорожек E_B(M′) с нормализованной длиной λ (то есть включая штрафы только для тех улиц, с которых были убраны велосипедные дорожки). Π*_i→j(λ) обозначает кратчайший путь в этом графе предпочтений велосипедистов и, следовательно, маршрут, выбранный велосипедистами из точки i в точку j.

Чтобы сравнить общее воспринимаемое расстояние между обоими городами, была измерена общая производительность b(λ) результирующей сети:



где была выполнена нормализация лучших (λ = 1) и худших (λ = 0) сценариев, b(0) = 0 описывает сеть без велосипедных дорожек, а b(1) = 1 — оптимальную сеть с велосипедными дорожками вдоль всех кратчайших путей.


Изображение №5

Выше показана производительность (эффективности) сгенерированной последовательности сетей велосипедных дорожек. Интересно, что небольшой доли велосипедных дорожек с небольшой относительной длиной λ > 0.1 достаточно для достижения более 50% максимальной эффективности в обоих городах.

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

Сравнение с эффективностью сети основных и вспомогательных велосипедных дорожек с той же относительной длиной (λP+S) подчеркивает лучшую адаптацию к структуре спроса в данном алгоритме. Эффективность уже достаточно высока, когда велодорожки имеются на всех крупных улицах: 0.87 для Дрездена и 0.82 для Гамбурга. Тем не менее алгоритму удается еще больше увеличить это значение примерно до 0.97 для Дрездена и 0.95 для Гамбурга (улавливая более 70% оставшегося потенциала оптимальной сети b(1) = 1).

Более того, адаптируя сеть к поведению человека при выборе маршрута, велосипедисты остаются на улицах, оборудованных велодорожками, на протяжении более 89 % от общего расстояния поездки по сравнению с примерно 60 % в P+S сети (5b и 5d).

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


Изображение №6

Сравнение кривых эффективности b(λ) и b_hom(λ) в условиях эмпирического и однородного спроса, соответственно, позволяло обнаружить сравнительно большую разницу для Дрездена и гораздо меньшую разницу для Гамбурга (6b и 6c).



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

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

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

Эпилог

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

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

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

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

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

Немного рекламы

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Maincubes Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?