Как стать автором
Поиск
Написать публикацию
Обновить

Дешевый как автобус, удобный как такси: перспективный вид общественного транспорта для больших и средних городов. Часть1

Время на прочтение40 мин
Количество просмотров11K
Алгоритмы*Будущее здесьМатематика*ТранспортУрбанизм
Мнение

(Jean-Claude Mézières)

Ссылка на Часть1: «Предварительный анализ» (ру / eng )
Ссылка на Часть2: «Эксперименты на торе» (ру / eng )
Cсылка на «Часть3: Практически значимые решения» (ру / eng )
Cсылка на «Summary» (ру / eng )

1.1 Центральный результат


Если я только не допустил критической ошибки, то мне удалось обнаружить удивительную по своим характеристикам схему пассажирских перевозок. Представьте себе такую картину: вы находитесь в большом городе и вам нужно добраться из точки A в точку B. Все, что от вас требуется — это дойти до ближайшего перекрестка и на вашем смартфоне или установленном там специальном терминале указать точку назначения. Через несколько минут к вам подъедет небольшой, но просторный автобус. Автобус, в который можно войти, не пригибаясь, внести с собой детскую коляску, велосипед или даже виолончель, в котором всегда можно сесть и вытянуть ноги. Этот автобус довезет и высадит вас на ближайшем от точки B перекрестке. Вы доберетесь туда без каких-либо пересадок, а все путешествие, включая ожидание на остановке, займет всего на 25-50% времени больше, чем если бы совершили его на личном автомобиле. По моим оценкам в условиях современных мегаполисов такой вид транспорта будет достаточно массовым, чтобы цена одной поездки на нем была близка к стоимости билета на обычный городской автобус.

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

1.2 Изначальная задача


Забавна сама история того, как я взялся за это исследование и то, как я обнаружил самый ценный его результат. Позвольте мне об этом вкратце рассказать. Настоящая статья — не первая моя работа в области проблем городского транспорта: я уже публиковал две или три (№1, №2, №3) — смотря как считать. Иногда по их темам ко мне обращаются студенты и разной руки предприниматели. Примерно полгода назад мне поступил звонок от одного очень амбициозного молодого человека. Он спросил, не могу ли я ему помочь придумать способ, чтобы простым (и не очень) людям стало проще быстрее и удобнее добираться до работы и возвращаться оттуда домой. Его исходная идея была в том, что работников можно развозить чем-то вроде школьного автобуса и на этой основе создать новый более удобный вид общественного транспорта. Идея, как вы понимаете, была довольно грандиозной и звучала заманчиво, однако в тот момент я работал на своей книгой и мне хотелось избежать серьезной увлеченности какой-либо другой задачей. Все же я не мог совсем отказать и предложил этому молодому человеку свою помощь в том, чтобы формализовать его задачу и подыскать тех, кто был бы в состоянии ее решить. Правда, как это часто случается с предпринимателями (в чем я их нисколько не виню — сам был таким), автор этой замечательной идеи из общения куда-то пропал. Да… автор-то, может быть, и пропал, только вот его идея на тот момент уже овладела моими мыслями и, отложив все дела, я принялся ее изучать.

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

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

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

2. Модель города и модель внутригородских суточных миграции


2.1 Идеализация как исследовательский метод


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

2.2 Идеальный клеточный город


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

image


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

Еще одно упрощение, к которому я вскоре прибегну — это сворачивание плоского прямоугольного города в правильный тор. Дело в том, что у прямоугольника есть край и это делает положения точек на нем не равнозначными: какие-то точки расположены ближе к центу, а какие-то — к периферии. Из-за этой неоднородности рассуждения наполняются оговорками, а вычисления становятся излишне технически сложными. У тора нет края и все его точки находятся в абсолютно равных условиях. Так же, как и на сфере, подходящим “вращением” любую точку тора можно наложить (перевести) в любую другую его точку. Общественный транспорт в тороидальном клеточном городе во всем, что не касается особого поведения у края, встречается ровно с теми же проблемами, что и общественный транспорт в обычном “плоском” городе. Что еще более важно, эти проблемы в обоих случаях имеют похожие решения. Для тех читателей, которым понятие (плоского) тора в новинку, я добавил в статью две ознакомительных главы.

2.3 Миграционная модель. Город с равномерным доступом


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

Такую миграционную модель условимся называть “городом с равномерным доступом”.

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

3. Неустранимы недостатки некоторых традиционных видов общественного транспорта


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

3.1 Простой городской автобус


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

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

image

рис 2

Как вид транспорта простой автобус имеет немало приятных свойств:
1) простая логика построения маршрута;
2) от любой остановки до любой другой доехать можно всего с 1-ной пересадкой;
3) если вы уже находитесь на улице, то остановка в любом из направлений расположена от вас не далее, чем в половине длины квартала.
4) из наблюдений уже в небольших по населению городах среднее число пассажиров в салоне простых автобусов оказывается достаточно большим, чтобы сделать поездку на них относительно дешевой.

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

Пусть максимальная разрешенная скорость движения в городе равна стандартным 60 километрам в час ($17$ метров в секунду или $1$ километр в минуту). Отъезжая от предыдущей остановки, автобус не может развить максимальную скорость мгновенно, точно также он не может мгновенно остановиться перед следующей — в обоих случаях ему понадобится некоторое время двигаться с ускорением. Таким образом путь автобуса между соседними остановками можно разделить на три участка: участок ускорения, участок торможения и средний участок, который автобус проезжает с постоянной максимально разрешенной скоростью.

Гугл говорит, что комфортным для пассажиров является ускорение, при котором за секунду автобус увеличивает (или уменьшает) свою скорость на $0.7 - 1$ м/с. Примем для расчётов, что ускорение автобуса на участках разгона и торможения постоянно и равно $1$м/с за секунду. При таких вводных автобусу потребуется $17$ секунд, чтобы набрать полную скорость и столько же, чтобы сбросить ее до нуля. Постоянство ускорения автобуса во время разгона и торможения означает, что графики зависимости его скорости от времени в эти периоды будут наклонными прямыми линиями. Вычисляя площадь под этими графиками, мы находим, что участок разгона и участок торможения имеют длину $17 \cdot 17/2 = 144,5$ метра, в месте $289$ метров. Расстояние между соседними остановками мы приняли равным длине квартала, то есть $500$ метрам. Отсюда следует, что средний участок, на котором автобус имеет максимальную скорость, в длину равен $211$ метрам и будет преодолён им за $211/17 \approx 12$ секунд. В итоге мы получаем, что весь полукилометровый путь от остановки к остановке автобус проедет в лучшем случае за $17+17+12 = 46$ секунд. Даже если бы простой автобус не задерживался на самих остановках, его средняя скорость не превысила бы $500/46 \approx 11$ м/с.

image

рис 3

Теперь оценим, какой будет средняя скорость автобуса с учетом длительности его остановок. Разные источники говорят, что среднее время посадки или высадки одного пассажира находится в пределах $3-5$ секунд. Возьмем за оценку $4$. Пусть на каждой остановке входят и выходят в среднем $2$ человека, тогда процесс посадки-высадки в среднем потребует примерно $16$-ти секундной стоянки, а средняя скорость окажется не больше $500/(46 + 16) \approx 8$ м/с. Получается, что уже находясь внутри простого автобуса, вы будете перемещаться по городу в среднем более чем в два раза медленнее по сравнению личным автомобилем или персональным такси.

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

3.2 Автобусная сеть, которая включает в себя простые и транзитные маршруты


Можно ли сделать городские автобусы быстрее? Чтобы ответить на этот вопрос, давайте распишем, из чего складывается время путешествия автобуса между двумя достаточно удаленными точками $A$ и $B$ его маршрута.

image

рис 4

Как видно из рисунка 4 выше это время можно представить как сумму трех слагаемых:

$T_{tr} = |AB|/v $ — это слагаемое равно времени, которое ушло бы на то, чтобы проехать путь между $A$ и $B$ с максимально разрешенной скоростью $v$.
$T_a =$ “число остановок между $A$ и $B$” $\times$ “время однократного разгона/торможения”. Каждая остановка автобуса требует от него сначала торможения, в сумме они приводят к потере примерно $17$-ти секунд;
$T_w =$ “число пассажиров, которые между $A$ и $B$ вошли или вышли из автобуса” $\times$ “штраф посадки/высадки одного пассажира”.

В этих обозначениях средняя скорость автобуса на участке $A$-$B$ будет даваться выражением:

$\bar {v_{AB}} = |AB|/(T_{tr} + T_a + T_w) \ \ \ \ \ (1) $

Если мы хотим, чтобы $\bar {v_{AB}}$ была как можно выше, то должны сделать так, чтобы значения слагаемых $T_{tr}$, $T_a$ и $T_w$ стали как можно меньше.

На слагаемое $T_{tr}$ мы повлиять никак не можем: отрезок $AB$ и максимальная разрешенная скорость $v$ — такие, какие они есть.

Второе слагаемое $T_a$ получается произведением штрафа однократного разгона/торможения на число остановок, которое сделает автобус между точками $A$ и $B$. Поскольку максимально разрешенное ускорение является заданной величиной, однократный штраф разгона/торможения мы поменять не можем. Зато, можем уменьшить число остановок между точками $A$ и $B$, если расставим их пореже.

Третье слагаемое $T_w$ получается произведением времени посадки/высадки одного пассажира, величина которого есть константа на суммарное число людей, которые вошли или покинули автобус на участке $A-B$. Среднее число людей, которые входят или покидают автобусы маршрута $M$ за единицу времени на остановках между $A$ и $B$, почти никак не зависит от того, на какой дистанции расставлены эти остановки. Действительно, если альтернативного транспорта нет, то всем, кому надо уехать из $A-B$ маршрутом $M$, в конце концов сядут на свой автобус будь там хоть $10$ остановок, хоть $30$. То же самое верно и для тех, кто этим маршрутом в $A-B$ собирается приехать.

Пусть из участка $A-B$ маршрутом $M$ в среднем уезжает $x$ человек в минуту, а приезжает — $y$ человек в минуту. Если интервал движения автобусов маршрута $M$ равен $\Delta T$ минут, то на участке $A-B$ в каждый из них войдет и выйдет в среднем $(x+y) \times \Delta T$ пассажиров (докажите!). Уменьшая интервал $\Delta T$, мы можем уменьшить и время, которое автобусу придется потратить на посадку/высадку своих пассажиров между точками $A$ и $B$.

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

image

рис 5

От проблемы, что цена поездок растет при уменьшении интервала движения автобусов, избавится, по всей видимости, нельзя, а вот для проблемы редко расставленных остановок — напротив есть довольно очевидное и простое решение. Это решение заключается в том, чтобы на каждой улице иметь два дублирующих друг друга автобусных маршрута: один с часто расположенными остановками и как следствие “медленный”, а другой — с остановками, расположенными на большом удалении друга от друга, и поэтому потенциально достаточно “быстрый”. Медленные маршруты и курсирующие по ним автобусы мы будем называть локальными, быстрые — транзитными. Естественно потребовать, чтобы остановки локальных автобусов были расставлены на всех перекрестках по маршруту следования, а вот транзитные автобусы останавливались только на каждом $k$-том перекрестке вдоль их пути (рисунок 6).

image

рис 6

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

Если обе точки лежат на на одной улице и не занимают какого-то особого положения, то достаточно быстрый способ попасть из $A$ в $B$ будет таким:
Сперва от точки $A$ нужно дойти до ближайшего к ней перекрестка $P_1$ и сесть там на локальный автобус в сторону ближайшей остановки $P_2$, на которой останавливаются транзитные автобусы. Доехав до $P_2$ выйти и пересесть уже на транзитный автобус, который направляется в сторону точки $B$. На этом втором автобусе следует ехать до той его остановки $P_3$, которая ближе всех остальных расположена к точке $B$. В общем случае $P_3$ не является ближайшим к $B$ перекрестком, поэтому придется еще раз сесть на локальный автобус в сторону точки $B$ и выйти на ближайшем к ней перекрестке $P_4$. Оставшийся путь следует проделать пешком.

Схематично алгоритм такого путешествия можно описать как “л->т->л”.

Упражнение: является ли описанный выше алгоритм наибыстрейшим по средней длительности путешествия между случайными точками $A$ и $B$. Если нет, то как его нужно изменить, чтобы он таковым стал? Какую информацию о положении путешественника и автобусов использует ваше решение?

image

рис 7

В общем случае, когда $A$ и $B$ не лежат на одной улице и не занимают на них какого-то особого положения, путешествие из A в B может быть выполнено по схеме: “л->т->л->л->т->л” (рисунок 7). Как вы видите, сценарий путешествия выходит не самым простым и включает в себя целых 5 пересадок. В действительности, если немного подумать и расположить остановки транзитных автобусов немного иначе (рисунок ниже), то максимально количество пересадок, которое потребуется от пассажира, можно сократить до 4-рех.

image

рис 8

Всякую сеть автобусных маршрутов, выполненную по образцу рисунка 8 мы будем называть “(городским) автобусом с транзитными маршрутами”.

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

Давайте хотя бы грубо оценим, каким должно быть $k$, чтобы средняя скорость транзитных автобусов стала близкой к стандартным $60$ километрам в час (к $1$ км/мин).

На перегоне между соседними остановками транзитный автобус имеет один участок разгона и один торможения. Как мы посчитали выше, на этих участках он теряет в сумме $T_a = 17$ секунд. Пусть при каждой остановке транзитный автобус подбирает и высаживает x человек, тогда время стоянки $T_w \approx 2x \times 4$ секунд. Если остановки этого автобуса расположены на каждом $k$-том перекрестке, а длина кварталов равна половине километра, то $T_{tr} = 500 k/v$. Из всего сказанного следует, что формулу средней скорости автобуса можно записать как:

$\bar {v} = 500 k/ (T_{tr} + T_a + T_w) = v \frac {1}{1 + (T_a + T_w)/T_{tr}} \ \ \ \ \ \ (2)$

Близкой к максимальной средняя скорость транзитного автобуса будет только в том случае, если:

$\frac {T_a + T_w}{T_{tr}} \ll 1 \ \ \ \ \ \ (3)$

Следовательно мы можем воспользоваться приближением:

$\frac {1}{1+\varepsilon} \approx 1 - \varepsilon \ \ \ \ \ \ (4)$

и переписать $(2)$ как

$\bar {v} = v (1 - (T_a + T_w)/T_{tr}) \ \ \ \ \ \ (5)$.

Последняя формула показывает, что нет особого смысла время посадки-высадки пассажиров $T_a$ пытаться сделать сильно меньше, чем штраф разгона/торможения $T_w$ — все равно средняя скорость автобуса от этого сильно уже не увеличится. Для простоты будем считать интервал между транзитными автобусами подобранным так, что $T_w = T_a = 17$ секунд. Такая величина $T_w$ соответствует примерно $2$ вошедшим и вышедшим пассажирам на каждой остановке. Подставляя $T_w = T_a = 17$ сек, $T_{tr} = 500k/17 \approx 30 k$ сек в $(5)$ получаем неравенство на $k$:

$1 - \frac {17 + 17}{30k} \geq \bar {v}/v \ \ \ \ \ \ (6) $ или

$k \geq 1.13 \frac {1}{1 - \bar {v}/v} \ \ \ \ \ (7) $.

Если мы хотим, например, чтобы транзитные автобусы двигались со средней скоростью не меньше $45$ км/ч ($3/4$ от $v$), то $k$ должно быть равным по крайней мере $5$, то есть между соседними остановками транзитного автобуса должно быть порядка $2.5$ километров. Эта оценка позволяет указать минимальный размер города, в котором автобусы с транзитными маршрутами вообще имеют смысл: что-то около $3$ транзитных перегонов или $7.5 - 10$ км в длину. Квадратный город таких размеров при стандартной плотности в $5000$ жителей на квадратный километр будет иметь население примерно в $300$ тысяч человек.

По моим беглым оценкам, в городах размером $>20$км (населением $>2$ миллионов человек) большая часть маршрута типичных путешествий будет преодолеваться именно за счет транзитных автобусов, а среднюю скорость таких путешествий реально приблизить к $0.6v$ ( $13$м/с или $36$км/ч). Казалось бы, вот он — идеальный транспорт мегаполисов, но 4 пересадки — это все-таки не то, с чего бы я мечтал начинать свой день!

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

3.3 Персональное такси


Быстро, часто очень удобно, но при этом очень дорого. Занимает много места на дороге, выделяет много выхлопных газов в расчёте на $1$ пассажиро-километр.
—


4. Такси для совместных поездок между парами городских районов


4.1 Идея совместных поездок.


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

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

image

рис 9

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

4.2 Регламент работы


Пусть у нас есть клеточный город размера $L_H \times L_W$. Вертикальными и горизонтальными прямыми разобьем его на решетку одинаковых по размеру квадратных клеток $\{S_{h,w}\}$. Идея разделения на клетки состоит в том, чтобы попутчиками могли становиться только те люди, которые из одной и той же клетки направляются в одну и ту же другую. Для простоты можно даже считать, что перевозкой пассажиров между каждой конкретной парой клеток занимается свой отдельный небольшой парк машин, а посадка и высадка пассажиров производят только на перекрестках.

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

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

image

рис 10

Лемма о маршрутах машин межклеточного такси:
Предположим, что имеются n путешественников, которых нужно собрать в “стартовом” квадрате $S_{h’,w’}$ и развести по точкам их назначения в “финишном” квадрате $S_{h’’,w’’}$, причем машина такси, которая должна это сделать, уже находится в $S_{h’,w’}$. Для любого маршрута $\alpha$, который решает задачу совместной перевозки путешественников, существует такой маршрут $\beta$, что:
1) маршрут $\beta$ также решает задачу перевозки этих путешественников;
2) маршрут $\beta$ задает тот же самый порядок посадки и высадки путешественников, что и $\alpha$, но при этом является одним из самых коротких среди маршрутов с таким порядком;
3) при использовании машиной такси маршрута $\beta$ длина поездки каждого ее пассажира оказывается такой же или короче, чем при использовании маршрута $\alpha$;
4) весь маршрут $\beta$ можно разделить на три непрерывных участка: начальный, средний и конечный, так, что начальный участок будет целиком лежать в $S_{h’,w’}$, конечный — целиком лежать в $S_{h’’,w’’}$, а средний — являться кратчайшей ступенчатой кривой между концом начального участка и началом конечного.
5) если квадраты $S_{h’,w’}$ и $S_{h’’,w’’}$ не находятся друг с другом на одной горизонтали или на одной вертикали, то маршрут $\beta$ можно выбрать так, чтобы его средний участок представлял из себя $\Gamma$-образную кратчайшую, проведенную между ближайшими друг к другу (угловыми) перекрестками квадратов $S_{h’,w’}$ и $S_{h’’,w’’}$.

image

рис 11

Доказательство.
Идея доказательства 1)-4) состоит в том, чтобы каждый участок $\alpha$ между двумя остановками машины такси (точками посадки или высадки пассажиров) заменить $\Gamma$-образной кратчайшей. Теперь что касается 5). Последовательными вращениями карты на $90$ градусов добьемся, чтобы квадрат $S_{h’’,w’’}$ был строго выше и строго правее $S_{h’,w’}$. Пусть $\beta^*$ — это построенный по $\alpha$ маршрут из $\Gamma$-образных кратчайших, о котором мы говорили выше. Одним из звеньев маршрута $\beta^*$ является $\Gamma$-образная кратчайшая $\gamma^*$ между последней точкой $P$ посадки клиентов в клетке $S_{h’,w’}$ и первой точкой $Q$ высадки клиентов в клетке $S_{h’’,w’’}$. Заменим в $\beta^*$ участок $\gamma^*$ на ломаную $\gamma$, проведенную согласно правилу: по $\Gamma$-образной (возможно, вырожденной в отрезок или даже в точку) кратчайшей от $P$ до самого верхнего правого перекрестка в $S_{h’,w’}$, затем по $\Gamma$-образной (возможно, вырожденной) кратчайшей в самый нижний левый перекресток в $S_{h’’,w’’}$, и наконец оттуда снова по по $\Gamma$-образной (возможно, вырожденной) кратчайшей в точку $Q$. Легко видеть, что \gamma тоже кратчайшая между $P$ и $Q$, а получившийся после замены $\gamma^*$ на $\gamma$ маршрут $\beta$ удовлетворяет каждому из пунктов 1)-5).

4.3 Алгоритм обхода


Пусть $S_{h’,w’}$ и $S_{h’’,w’’}$ — это две произвольные клетки, выбранные из разных строк и разных столбцов решетки $\{S_{h,w}\}$. Последовательными поворотами карты на $90$ градусов добьемся того, чтобы клетка $S_{h’’,w’’}$ оказалась строго выше и правее $S_{h’,w’}$. Самый верхний правый перекресток в $S_{h’,w’}$ обозначим как $A$, в то время как самый нижний левый в $S_{h’’,w’’}$ — как $B$. Лемма о маршрутах позволяет считать, что все машины такси, курсирующие между $S_{h’,w’}$ и $S_{h’’,w’’}$, покидая $S_{h’,w’}$, проезжают через перекресток $A$, а прибывая в $S_{h’’,w’’}$, проезжают через перекресток $B$.

Представим теперь, что в указанной нами точке $S$ клетки $S_{h’,w’}$ появилась пустая машина, которая должна выполнить рейс между $S_{h’,w’}$ и $S_{h’’,w’’}$ и прибыть затем в указанную нами точку $F$ клетки $S_{h’’,w’’}$. Будущие пассажиры этой машины, пусть их число равно n, случайным образом разбросаны по всем перекресткам внутри $S_{h’,w’}$. Какого алгоритма обхода должна придерживаться машина такси, чтобы их всех подобрать? Аналогично, какого алгоритма она должна придерживаться, чтобы развести всех этих пассажиров по пунктам их назначения после того, как она достигнет клетки $S_{h’’,w’’}$. Понятно, что оба этих алгоритма должны по возможности минимизировать путь машины внутри клеток $S_{h’,w’}$ и $S_{h’’,w’’}$. Отыскать оптимальный алгоритм обхода мне не удалось (быть, может вы придумаете, как это сделать), но построить приемлемое решение не так уж сложно.

Чтобы упростить расчёты и рассуждения, предположим, что длина $\Delta l$ квадратов $S_{h,w}$, на которые поделен город, много больше длины кварталов. Если это предположение верно, то через каждый клетку $S_{h,w}$ пройдет сразу много как горизонтальных, так и вертикальных улиц, причем по сравнению с размером клетки расстояние между соседними улицами будет мало. Последнее позволяет приближенно считать, что горизонтальная и вертикальная дороги проходят через каждую точку клетки $S_{h,w}$ и каждая такая точка может быт местом посадки или высадки пассажиров такси. Еще одним следствием такого упрощения станет то, что перекресток $A$ будет находиться в самом правом верхнем углу $S_{h’,w’}$, а перекресток $B$ — в самом нижнем левом углу $S_{h’’,w’’}$.

Начнем с оценки асимптотики. Пусть число попутчиков n является квадратом целого числа. Расставим этих людей так, чтобы они заняли положение узлов правильной квадратной решетки с размером ячейки $\Delta l/ (\sqrt{n} - 1)$. Изображенная на рисунке “змейка” обходит все точки решетки и заканчиваются в верхнем правом углу в точке $A$, ее длина равна $(\sqrt{n} + 1) \Delta l$. Не трудно сообразить, что эта змейка является одним из кратчайших маршрутов обхода точек положения наших воображаемых путешественников. Действительно, какой бы маршрут не выбрала машина таки, самое малое расстояние, которое ей придется проехать между точкой посадки каждого предыдущего и каждого последующего пассажира равно $\Delta l/ (\sqrt{n} - 1)$, всего таких “перегонов” будет $n - 1$, поэтому весь обход в длину будет не меньше чем $(n - 1) \cdot \Delta l/ (\sqrt{n} - 1) = (\sqrt{n} + 1) \Delta l$.

image

рис 12

Построим теперь решение для общего случая, когда начальные положения n путешественников расположены внутри $S_{h’,w’}$ хаотическое. С этой целью поделим клетку $S_{h’,w’}$ на $(\sqrt{n} - 1)$ одинаковых полос. Суть алгоритма обхода состоит в том, чтобы объехать все эти полосы змейкой, начиная с самой левой, и подбирать пассажиров только внутри текущей полосы. Установим правило, что находясь внутри полосы, машина должна двигаться строго вдоль ее центральной линии до тех пор, пока очередной путешественник, которого она должна подобрать, не окажется от нее точно справа или слева. Всякий раз когда это будет случаться, таксист должен свернуть вбок, подобрать этого путешественника и тем же путем вернуться на среднюю линию текущей полосы. Если движение такси будет следовать такому регламенту, то длина той ее части маршрута, которая проходит по средним линиям полос, будет равна примерно $(\sqrt{n} + 1) \Delta l$. Каждый маневр отклонения за пассажиром обойдется в среднем $1/2\ \Delta l/(\sqrt{n} - 1)$ единицами дополнительного пути, что в сумме удлинит маршрут примерно на $\sqrt{n} \Delta l/2$. Таким образом средняя длина обхода стартовой клетки составит $\approx 3/2\ \sqrt{n} \Delta l$.

image

рис 13

Будем считать, что клетка $S_{h’’,w’’}$ разделена на такие же вертикальные полосы, что и клетка $S_{h’,w’}$. Должно быть очевидно, что когда машина межклеточного такси достигнет $S_{h’’,w’’}$, она сможет доставить своих пассажиров в нужные им пункты назначения, действуя по точно такому же алгоритму, что и во время их собора. После того, как эта машина высадит всех своих клиентов и доберется до точки $F$ в конце последней полосы, ее можно назначить на обратный рейс из $S_{h’’,w’’}$ в $S_{h’,w’}$.

4.4 Средняя длинна кратчайшего ступенчатого пути между двумя случайными точками прямоугольника


Пусть у нас есть прямоугольник $\Pi$ с горизонтальной стороной длины $L_W$ и вертикальной — длины $L_H$. Под ступенчатыми кривыми внутри $\Pi$ мы будем понимать ломанные линии (кусочно линейные кривые), каждый сегмент которых является либо горизонтальным, либо вертикальным отрезком. Возьмем внутри $\Pi$ две произвольные точки $А$ и $B$. Для дальнейшего исследования нам понадобится знать ответит на следующие два вопроса.

Первый состоит в том, чтобы описать, какие ступенчатые кривые из $A$ в $B$ будут иметь наименьшую длину. Второй — это, чему будет равна средняя длина таких кривых, если точки $A$ и $B$ выбираются внутри $\Pi$ случайно и независимо друг от друга, а вероятность, которая описывает этот выбор, равномерно распределена по $\Pi$.

Чтобы ответить на первый вопрос, на всякий ступенчатый путь из $A$ в $B$ будем смотреть как на цепочку векторов, в которой начало каждого следующего вектора совмещено с концом предыдущего. Пусть $A’$ и $B’$ — это проекции точек $A$ и $B$ на нижнюю сторону $\Pi$, а $A’’$ и $B’’$ — их проекции на левую сторону $\Pi$. Можно видеть, что если $\gamma$ — произвольный ступенчатый путь из $A$ в $B$, то проекции всех его горизонтальных звеньев в сумме дадут вектор $\vec {A’B’}$, а проекции всех вертикальных звеньев — вектор $\vec {A’’B’’}$.

image

рис 14

В том и только в том случае, когда все горизонтальные звенья $\gamma$ имеют одно и тоже направление сумма их длин будет равна длине вектора $\vec {A’B’}$. Аналогично, в том и только в том случае, когда все вертикальные звенья $\gamma$ имеют одно и тоже направление сумма их длин будет равна длине $\vec {A’’B’’}$. Ступенчатые пути, у которых и все горизонтальные, и все вертикальные звенья ориентированы одинаково, договоримся называть монотонными. Таким образом, ступенчатый путь будет кратчайшим в том и только в том случае, когда он является монотонным.

Займемся теперь вторым вопросом. Пусть точки $A$ и $B$ выбраны из прямоугольника $\Pi$ случайно и независимо друг от друга. Мы знаем, что длина любой кратчайшей ступенчатой кривой из $A$ в $B$ равна сумме длин проекций отрезка $AB$ на нижнюю и левую стороны $\Pi$. Следовательно, чтобы посчитать среднюю длину таких кривых, достаточно вычислить, чему равна средняя длина отрезков $A’B’$ и $A’’B’’$.

Можно показать, да и это почти очевидно, что равномерная распределенность и независимость выбора точек $A$ и $B$ внутри $\Pi$ влечет за собой равномерную распределенность и независимость случайного положения их проекций на каждой из сторон $\Pi$. Давайте тогда посчитаем, чему равно среднее расстояние между двумя случайно выбранными точками $P$ и $Q$ на отрезке $I$ длины $L$. Поскольку результат, очевидно, пропорционален $L$, достаточно рассмотреть случай, когда $L = 1$.

Пусть $x$ и $y$ — это то, насколько точки $P$ и $Q$ удалены от левого конца $I$. В таком случае пара $(x,y)$ полностью кодирует выбор $P$ и $Q$, а вероятность иметь ту или иную пару $(x,y)$ оказывается равномерно распределена внутри единичного квадрата декартовой плоскости.

image

рис 15

Расстояние между $P$ и $Q$ описывается функцией $F(x,y) = |x – y|$, ее график состоит из двух одинаковых пирамид высоты $1$ и площадью оснований $1/2$ у каждой. Среднее расстояние между $P$ и $Q$ равно среднему значению высоты графика $F(x,y)$, то есть суммарному объему пирамид, деленному на суммарную площадь их оснований. Объем пирамиды равна трети произведения площади основания на высоту, таким образом, среднее расстояние между двумя случайными точками отрезка длины $L$ равно $L/3$, а среднее расстояние между двумя случайными точками прямоугольника размера $L_H \times L_W$ равно $1/3\ (L_H + L_W)$.

Упражнение: покажите что в прямоугольнике размера $L_Н \times L_W$ средняя длина кратчайшей ступенчатой кривой, построенной между случайно выбранной точкой и центром прямоугольника равна $(L_H + L_W)/4$, а между случайно выбранной точкой и его углом — $(L_H + L_W)/2$.

4.5 Средняя продолжительность путешествия на межклеточном такси


Если все путешествия в городе совершаются на личных автомобилях, то маршруты большинства из них могут быть проложены по кратчайшей ступенчатой кривой. Средняя длина поездок в этом случае будет близка к $1/3\ (L_H + L_W)$, а продолжительность к $1/3\ (L_H + L_W)/v$. Какими окажутся средняя длина и средняя продолжительность путешествий, если все жители города будут совершать их на межклеточном такси?

Пусть некоторому путешественнику предстоит доехать на межклеточном такси от некоторого перекрёстка $P$ в квадрате $S_{h’,w’}$ до некоторого перекрестка $Q$ в квадрате $S_{h’,w’}$. Разделим его будущий маршрут на три участка: начальный — внутри $S_{h’,w’}$, средний — между ближайшими друг к другу углами $S_{h’,w’}$ и $S_{h’’,w’’}$, и финальный — внутри $S_{h’’,w’’}$. Начальный и финальный участки — это часть змеевидного пути, которым машина такси объезжает клетки $S_{h’,w’}$ и $S_{h’’,w’’}$. При случайном положении перекрестков $P$ и $Q$ путешественник проедет в среднем примерно половину каждой змейки, таким образом средняя длина начального и конечного участков его маршрута составит примерно $\approx 3/4\ \sqrt{n} \Delta l$ каждый. Это приближение будет работать, если число пассажиров n, которое за раз перевозит машина, достаточно велико.

Чтобы оценить среднюю длину среднего участка, предположим, что размер клеток на которые поделен город, много меньше размера самого города, то есть $\Delta l \ll (L_H + L_W)/2$. Если это так, то сами клетки $S_{h,w}$ в масштабе города выглядят как точки, а значит среднее расстояние между ними с точностью до величины порядка $\Delta l$ равно $1/3\ (L_H + L_W)$. Получается, что при сравнительно больших $n$ и сравнительно малых $\Delta l$ поездки по городу на межклеточном такси будут в среднем примерно на $3/2\ \sqrt{n} \Delta l$ длинней поездок на личном автомобиле.

Среднее время, которое займет путешествие по городу на межклеточном такси можно найти как “средняя длина поездки, деленная на среднюю скорость, плюс среднее время ожидания транспорта”. Среднюю длину поездки мы оценили как $1/3\ (L_H + L_W) + 3/2\ \sqrt{n} \Delta L$. Давайте пренебрежем временем разгона/торможения, временем посадки и высадки и прочими несущественными задержками в пути, с которыми сталкиваются пассажиры и будем считать, что средняя скорость машины такси близка к разрешенной в городе скорости v. Далее, мы будем предполагать, что машины такси, которые курсируют между парой клеток, следуют друг за другом с интервалом $\Delta T$. Если так, то то человеку, который только что решил из клетки $S_{h’,w’}$ поехать в клетку $S_{h’’,w’’}$, подходящей машины придется ждать в среднем примерно $\Delta T/2$ единиц времени. Собирая все вместе, получаем, что среднее время путешествия на межклеточном такси примерно равно

$1/3\ (L_H + L_W)/v + 3/2\ \sqrt{n} \Delta l/v + \Delta T/2 \ \ \ \ \ (1)$,

что на

$3/2\ \sqrt{n} \Delta l/v + \Delta T/2 \ \ \ \ \ (2)$

дольше среднего времени путешествия на личном автомобиле.

4.6 Среднее число пассажиров в салоне


Как много пассажиров перевозит машина межклеточного такси за раз? Пусть в области единичной площади за единичное время намерение совершить любое путешествие по городу возникает в среднем у $\sigma$ людей. За время $\Delta T$, то есть за время равное интервалу между машинами, курсирующими между $S_{h’,w’}$ и $S_{h’’,w’’}$, внутри клетки $S_{h’,w’}$ такое намерение появится в среднем у $\Delta T \sigma (\Delta l)^2$ человек. Однако путь не всех из них будет лежать в клетку $S_{h’’,w’’}$. Вероятность, что случайно взятое путешествие закончится в клетке $S_{h’’,w’’}$, равна $(\Delta l)^2/(L_HL_W)$, то есть отношению площади этой клетки к площади всего города. В итоге мы имеем, что на каждую машину, курсирующую между $S_{h’,w’}$ и $S_{h’’,w’’}$ будет стремиться попасть в среднем:

$n_{pass} = \Delta T \sigma (\Delta l)^4/(L_HL_W) \ \ \ \ \ (3)$

путешественников.

Написанная выше формула ожидаемо показывает, что чем на большего размера клетки мы поделим город и чем больший интервал движения установим для курсирующих между этими клетками машин такси, тем большее число пассажиров каждая из них будет перевозить за раз. Однако мы не можем размер клеток $\Delta l$ и интервал движения $\Delta l$ сделать чересчур большими, иначе поездка на межклеточном такси станет чересчур долгой. Потребуем, чтобы среднее время путешествий на межклеточном такси отличалось от среднего времени путешествий на личном автомобиле не более чем в $inline$(1 + \lamda)$inline$ раз. Это требование приводит нас к неравенству

$1/3\ (H + W)/v + 3/2\ \sqrt{n_{pass}} \Delta l/v + \Delta T/2 \leq (1 + \lambda) [1/3\ (L_H + L_W)/v]\ \ \ \ \ (4)$,

откуда

$3/2\ \sqrt{n_{pass}} \Delta l/v + \Delta T/2 \leq 1/3 \lambda (L_H + L_W)/v\ \ \ \ \ \ (5)$,

или в предельном случае

$3/2\ \sqrt{n_{pass}} \Delta l/v + \Delta T/2 = 1/3\ \lambda (L_H + L_W)/v \ \ \ \ \ (6)$.

Подставляя в $(6)$ выражение для $n_{pass}$, получаем уравнение связи параметров $\Delta l$, $\Delta T$ и $\lambda$:

$3/2\ \sqrt{\Delta T \sigma/(L_HL_W)} \cdot (\Delta l)^3/v + \Delta T/2 = 1/3\ \lambda (L_H + L_W)/v\ \ \ \ \ (7)$

Давайте найдем такие $\Delta l$, $\Delta T$, которые при заданном $\lambda$ максимизируют величину $n_{pass}$. Для простоты выкладок рассмотри только тот случай, когда город имеет квадратную форму и $L_H = L_W = L$.

Брать производные “в лоб” здесь слишком трудоемко, поэтому мы используем одну маленькую уловку. Заметим, что уравнение связи состоит из двух слагаемых. Возьмем произвольное $p$ и $q = 1 - p$ от нуля до единицы и распределим между слагаемыми уравнения $(7)$ их суммарное значение в отношении $p \div q$:

$3/2\ \sqrt{\Delta T \sigma/L^2} \cdot (\Delta l)^3/v = q [1/3\ \lambda (L + L)/v]\ \ \ \ \ (8)$

$\Delta T/2 = p [1/3\ \lambda (L + L)/v]\ \ \ \ \ \ (9)$

Откуда:

$\Delta T = 4/3\ p \lambda L/v\ \ \ \ \ (10)$,

$3/2\ \sqrt{4/3\ p \lambda \sigma L/v} \cdot (\Delta l)^3/(Lv) = 2/3\ q \lambda L/v\ \ \ \ \ \ (11)$,

$\Delta l = 2^{1/3} 3^{-1/2} q^{1/3} p^{-1/6} \lambda^{1/6} \sigma^{-1/6} L^{1/2} v^{1/6}\ \ \ \ \ \ (12)$,

$n_{pass} = \Delta T \sigma (\Delta l)^4/L^2 = 4/3\ p \lambda \sigma/(Lv) \cdot 2^{4/3} 3^{-2} q^{4/3} p^{-2/3} \lambda^{2/3} \sigma^{-2/3} L^{2} v^{2/3} =$

$= 8 \sqrt [3]{2}/27 \cdot p^{1/3}q^{4/3} \lambda^{5/3} L (\frac {\sigma}{v})^{1/3}\ \ \ \ \ \ (13)$

Теперь мы можем оптимизировать $n_{pass}$ по $p$ и $q$. Эти параметры будут оптимальны, когда

$d(p^{1/3}q^{4/3}) = (1/3\ dp/p + 4/3\ dq/q) p^{1/3}q^{4/3} = 0\ \ \ \ \ \ \ (14)$

при условии, что

$dp + dq = 0 \ \ \ \ (15)$.

Из двух написанных выше уравнений тут же следует, что:

$\frac {1}{p} - \frac {4}{q} = 0\ \ \ \ \ \ (16)$,

откуда $p = 0.2$, $q = 0.8$.

Подставляя оптимальные $p$ и $q$ в формулы для $n_{pass}$, $\Delta l$, $\Delta T$:

$n_{pass} = 0.16 \lambda^{5/3} L (\frac {\sigma}{v})^{1/3}\ \ \ \ \ \ (17)$,

$\Delta l = 0.88 \lambda^{1/6} L^{1/2} (\frac {v}{\sigma})^{1/6}\ \ \ \ \ (18)$,

$\Delta T = 0.27 \lambda L/v\ \ \ \ \ (19)$.

4.7 Оценка для реальных городов


Давайте посмотрим, какими будут $n_{pass}$, $\Delta l$ и $\Delta T$, если взять $\sigma$, $L$ и $v$ соответствующими настоящим городам, а $\lambda$ положить равной $1/2$. Величину населения $P$, плотность населения $\rho$ и разрешенную скорость $v$ возьмем из энциклопедических страниц. При населении $P$ и его плотности $\rho$ квадратный город будет иметь размер $L = \sqrt {P/\rho}$. Величину $\sigma$, то есть среднее число путешествий, которые стартуют из области единичной площади за единицу времени, мы оценим, исходя из следующих допущений:

Будем считать, что каждый житель города совершает в день в среднем $2$ поездки, причем вся миграционная активность в городе равномерно распределена по $4$ утренним и $6$ вечерним часам. В городе размера $L \times L$ проживает $\rho L^2$ человек, за $600$ минут они совершат $2\rho L^2$ путешествий, следовательно в периоды миграционной активности из 1-го квадратного километра в минуту должны начинать свое путешествие в среднем $\sigma = 2\rho L^2 / (600 L^2) = 2\rho/600$ человек. Перейдем к конкретным примерам.

Условный Нью-Йорк (Лондон, Москва):
население $P = 8$ мл чел,
плотность $\rho = 10 000$ чел/кв км,
эффективный диаметр $L = \sqrt {8M/10K} \approx 28$ км,
разрешенная скорость $v = 0.8$ км/мин
$\sigma \approx 2\cdot 10K/600 = 33$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.16 (1/2)^{5/3} 28 (33/0.8)^{1/3} \approx 4.9$ чел.
$\Delta l (\lambda = 1/2) \approx 0.88 (1/2)^{1/6} 33^{-1/6} 28^{1/2} 0.8^{1/6} \approx 2.2$ км,
$\Delta T (\lambda = 1/2) \approx 0.27\cdot 1/2 \cdot 28/0.8\approx 4.7$ мин

Условный Берлин:
население $P = 3.7$ мл чел,
плотность $\rho = 4000$ чел/кв км,
эффективный диаметр $L = \sqrt {3.7M/4K} \approx 30$ км,
разрешенная скорость $v = 0.8$ км/мин
$\sigma \approx 2 \cdot 4K/600 = 13$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.16 (1/2)^{5/3} 30 (13/0.8)^{1/3} \approx 3.8$ чел
$\Delta (\lambda = 1/2) \approx l 0.88 (1/2)^{1/6} 13^{-1/6} 30^{1/2} 0.8^{1/6} \approx 2.7$ км
$\Delta T (\lambda = 1/2) \approx 0.27\cdot 1/2 \cdot 30/0.8\approx 5$ мин

Условный Париж:
население $P = 2.1$ мл чел,
плотность $\rho = 21 000$ чел/кв км,
эффективный диаметр $L = \sqrt {2.1M/21K} = 10$ км,
разрешенная скорость $v = 0.5$ км/мин
$ \sigma \approx 2\cdot 21K/600 = 70$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.16 (1/2)^{5/3} 10 (70/0.5) \approx 2.6$ чел
$\Delta l (\lambda = 1/2) \approx 0.88 (1/2)^{1/6} 70^{-1/6} 10^{1/2} 0.5^{1/6} \approx 1.1$ км,
$\Delta T (\lambda = 1/2) \approx 0.27\cdot 1/2 \cdot 10/0.5 \approx 2.7$ мин

Условная Прага:
население $P = 1.3$ мл чел,
плотность $\rho = 2500$ чел/кв км,
эффективный диаметр $L = \sqrt {1.3M/2.5K} \approx 23$ км,
разрешенная скорость $v = 0.8$ км/мин
$\sigma \approx 2\cdot 2.5K/600 = 8.3$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.16 (1/2)^{5/3} 23 (8.3/0.8)^{1/3} \approx 2.5$ чел
$\Delta l (\lambda = 1/2) \approx 0.88 (1/2)^{1/6} 8.3^{-1/6} 23^{1/2} 0.8^{1/6} \approx 2.5$ км,
$\Delta T (\lambda = 1/2) \approx 0.27\cdot 1/2 \cdot 23/0.8 \approx 3.9$ мин

4.8 Критика


Оценки, которые мы получили выше, показывают, что идея совместных поездок в теории имеет право на жизнь (Uber таки сделать можно) и должна быть исследована лучше. Что касается межклеточного такси, то его схема хороша как отправная точка для исследований, однако для практической реализации подходит плохо. В качестве главных причин ее прикладной бесполезности можно назвать следующие:
1) только в очень больших городах попутчиков будет достаточно, чтобы наполнить какой-нибудь очень маленький автобус, а значит массовым транспортом межклеточное такси считать никак нельзя;
2) утверждение о том, что путешествовать по городу на межклеточном такси в среднем не более чем в $(1 + \lambda)$ времязатратнее, чем на личном автомобиле, справедливо только при условии, что пункт назначения выбирается каждый раз случайно. Если изо дня в день вы собираетесь ездить на межклеточном такси между соседними квадратами, то быстрее будет ходить пешком.

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

5. Совместное такси с одной пересадкой


5.1 Наводящие рассуждения


Пусть город имеет квадратную форму со стороной в $\sim 10$км и заселен с плотностью $\sim 5000$ человек на квадратный километр. С такими вводными в городе будут проживать примерно $500$ тысяч человек, то есть, его нельзя назвать маленьким. Средняя длина путешествия в нем составит $2/3\cdot 10 км = 6.6$, а максимальная — $20$км.

Если разрешенную скорость движения в этом городе установить равной $60$ км/ч ($1$ км/мин), то формула для оптимизированного количества попутчиков в межклеточном такси даст нам

$n_{pass} (\lambda = 1/2) \approx 0.16 (1/2)^{5/3} 10 (2 \cdot 5K/600)^{1/3} \approx 1.3$ чел.

Можем ли мы как-то увеличить это число?

Чтобы было проще догадаться, как это можно сделать, немного поменяем регламент движения машин такси. Во-первых будем считать, что через центр каждой клетки $S_{h,w}$ проходит вертикальная и горизонтальная уличные дороги и между клетками машины такси перемещаются только по ним. Во-вторых потребуем, чтобы от стартовой к финишной клетке машина двигалась по $\Gamma$ — образному пути, причем из двух таких путей она выбирала тот, который начинается с горизонтального участка.

Если мы будем наблюдать за машинами такси, которые везут пассажиров из клетки $S_{h’,w’}$ в клетки $w’’$-го столбца, то увидим, что у них у всех имеется общий участок пути: из центра $S_{h’,w’}$ к центру $S_{h’,w’’}$. Почему бы тогда путешественников, которые направляются из $S_{h’,w’}$ в клетки $w’’$-го столбца, не довезти до центра $S_{h’,w’’}$ одним общим автобусом, а там уже что-нибудь придумать. Давайте так и поступим.


image

рис 16

5.2 Регламент движения машин


И так, для каждой клетки $S_{h’, w}$ $h’$-той строки у нас есть отдельный парк машин, единственное назначение которого — собирать внутри этой клетки всех путешественников, чьи точки назначения лежат в $w’’$-том столбце, и отвозят их в центр клетки $S_{h’, w’’}$. Таким образом сейчас весь поток путешественников из $h’$-той строки в $w’’$-тый столбец, скапливается в центре клетки $S_{h’, w’’}$. Следующий шаг очевиден: в каждой клетке $S_{h, w’’}$ $w’’$-го столбца нужно завести в свой отдельный парк машин, единственной задачей которого будет забирать путешественников из центра $S_{h’, w’’}$ и развозить их змейкой по клетке $S_{h, w’’}$.

Если мы масштабируем описанные только что правила на все строки и все столбцы решетки $\{S_{h , w}\}$, то получим схему движения совместного такси, которая позволяет путешественнику добраться от любого перекрестка к любому перекрестку всего с одной промежуточной пересадкой. Однако эта схема движения еще не совсем эффективна.

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

Можем ли мы оптимизировать схему так, чтобы все машины ездили только заполненными? Оказывается, что да. Для этого установим взаимно-однозначное соответствие между множествами клеток $h’$-той строки и $w’’$-того столбца, положив, что клетке $S_{h’, k}$ соответствует клетка $S_{k, w’’}$. Далее, установим правило, что всякий раз, когда собирающая машина клетки $S_{h’, k}$ и столбца $w’’$ достигает центра $S_{h’, w’’}$, она высаживает своих пассажиров после чего превращается в доставляющую машину $h$-той строкой и клетки $S_{k, w’’}$. В своей новой роли эта машина может тут же загружать ожидающих ее здесь путешественников и везти их в клетку $S_{k, w’’}$. Аналогично установим правило, что всякий раз, когда доставляющая машина $h'$-той строки и клетки $S_{k, w’’}$ высаживает последнего своего клиента, она становится собирающей между этой клеткой и столбцом $k$.

Благодаря действию двух новых правил машины совместного такси будут ездить всегда заполненными. Маршрут каждой такой машины будет описывать “круг”: из “домашней” клетки $S_{h’, k}$ на пересадочную остановку в центре $S_{h’, w’’}$, оттуда во вторую “домашнюю” клетку $S_{k, w’’}$, далее на пересадочную остановку в центре $S_{k,k}$, после которой снова в $S_{h’, k}$ (рисунок 17).

image

рис 17

5.3 Задержка в пути и число пассажиров в салоне


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

$\approx 3/2\ \sqrt{n_{pass}} \Delta l/v\ \ \ \ \ (1)$,

а вот среднее время, проведенное на остановке в ожидании подходящей машины удвоилось (ждать нужно два раза) и равно теперь

$\approx \Delta T\ \ \ \ \ (2)$.

Подсчитаем теперь ожидаемое число пассажиров в салоне. Когда машина выполняет роль доставляющей между клеткой $S_{h’, w’}$ и столбцом $w’’$, то во время обхода $S_{h’, w’}$ должна собрать в среднем

$n_{pass} = \Delta T\sigma (\Delta l)^2 \cdot L\Delta l/L^2 = \Delta T\sigma (\Delta l)^3/L\ \ \ \ \ (3)$

Если мы хотим, чтобы путешествия на такси с одной пересадкой были дольше путешествий на личном автомобиле в среднем не более чем в $(1 + \lambda)$ раз, то должны написать неравенство:

$3/2\ \sqrt{n_{pass}} \Delta l/v + \Delta T \leq 2/3\ \lambda L/v\ \ \ \ \ \ (4)$.

Чтобы оптимизировать $n_{pass}$, положим

$\Delta T = p [2/3 \lambda L/v]\ \ \ \ \ (5)$,

$3/2\ \sqrt{n_{pass}} \Delta l/v = q [2/3 \lambda L/v]\ \ \ \ \ (6)$,

где

$n_{pass} = \Delta T\sigma (\Delta l)^3/L\ \ \ \ \ (7)$

$p + q = 1\ \ \ \ \ (8)$.

После преобразований имеем:

$(3/2)^{1/2} p^{1/2} \lambda^{1/2} \sigma^{1/2} (\Delta l)^{5/2} v^{-1/2} = 2/3\ q\lambda L\ \ \ \ \ (9)$,

откуда

$\Delta l = (2/3)^{3/5} p^{-1/5}q^{2/5}\lambda^{1/5}\sigma^{-1/5}L^{2/5}v^{1/5}\ \ \ \ \ (10)$

соответственно

$n_{pass} = 2/3\ p\lambda\sigma/v \cdot (2/3)^{9/5} p^{-3/5}q^{6/5}\lambda^{3/5}\sigma^{-3/5}L^{6/5}v^{3/5} = (2/3)^{14/5} p^{2/5}q^{6/5} \lambda^{8/5} L^{6/5} (\sigma/v)^{2/5}\ \ \ \ \ \ (11) $

На вскидку $p = 1/4$, $q=3/4$ должны максимизировать $n_{pass}$, если так, то окончательный вид формул будет таким:

$\Delta T = 1/6\ \lambda L/v\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (12)$,
$\Delta l = 0.92 \lambda^{1/5}L^{2/5}(v/\sigma)^{1/5}\ \ \ \ \ \ (13)$
$n_{pass} = 0.13 \lambda^{8/5} L^{6/5} (\sigma/v)^{2/5}\ \ \ \ (14)$

5.4 Оценки


Давайте посмотрим, какими будут значения $n_{pass}$, $\Delta l$ и $\Delta T$ у такси с одной пересадкой в уже знакомых нам городах при значении $\lambda = 1/2$.

Условный Нью-Йорк (Лондон, Москва):
эффективный диаметр $L \approx 28$ км,
разрешенная скорость $v = 0.8$ км/мин
$\sigma \approx 33$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.13 (1/2)^{8/5} 28^{6/5} (33/0.8)^{2/5} \approx 10.4$ чел.
$\Delta l (\lambda = 1/2) \approx 0.92 (1/2)^{1/5} 28^{2/5}(0.8/33)^{1/5} \approx 1.44$ км
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 1/2 \cdot 28/0.8 \approx 2.9$ мин

Условный Берлин:
эффективный диаметр $L \approx 30$ км,
разрешенная скорость $v = 0.8$ км/мин
$\sigma \approx 13$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.13 (1/2)^{8/5} 30^{6/5} (13/0.8)^{2/5} \approx 7.7$ чел
$\Delta l (\lambda = 1/2) \approx 0.92 (1/2)^{1/5} 30^{2/5}(0.8/13)^{1/5} \approx 1.9$ км
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 1/2 \cdot 30/0.8 \approx 3.1$ мин

Условный Париж:
эффективный диаметр $L \approx 10 км$,
разрешенная скорость $v = 0.5$ км/мин
$ \sigma \approx 70 $чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.13 (1/2)^{8/5} 10^{6/5} (70/0.5)^{2/5} \approx 4.9$ чел
$\Delta l (\lambda = 1/2) \approx 0.92 (1/2)^{1/5} 10^{2/5}(0.5/70)^{1/5} \approx 0.74$ км,
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 1/2 \cdot 10/0.5 \approx 1.7$ мин

Условная Прага:
эффективный диаметр $L\approx 23$ км,
разрешенная скорость $v = 0.8$ км/мин
$\sigma \approx 8.3$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.13 (1/2)^{8/5} 23^{6/5} (8.3/0.8)^{2/5} \approx 4.7$ чел
$\Delta l (\lambda = 1/2) \approx 0.92 (1/2)^{1/5} 23^{2/5}(0.8/8.3)^{1/5} \approx 1.75$ км,
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 1/2 \cdot 23/0.8 \approx 2.4$ мин

Условный стандартный полумиллионный город.
население $P = 500K$ чел,
плотность $\rho = 5000$ чел/кв км,
эффективный диаметр $L = 10$ км,
разрешенная скорость $v = 1$ км/мин
$\sigma \approx 17$ чел/мин кв км
$n_{pass} (\lambda = 1/2) \approx 0.13 (1/2)^{8/5} 10^{6/5} (17/1)^{2/5} \approx 2.1$ чел
$\Delta l (\lambda = 1/2) \approx 0.92 (1/2)^{1/5} 10^{2/5}(1/17)^{1/5} \approx 1.1$ км,
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 1/2 \cdot 10/1 \approx 0.83$ мин

5.5 Критика


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

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

Давайте начнем дискуссию, а через две-три недели я закончу редактировать и опубликую вторую и еще через две-три недели и третью части. Если у вас есть желание обсудить что-то детально, вы можете написать мне письмо на адрес [email protected].

Сергей Коваленко,
апрель 2023г.

Ссылка на Часть1: «Предварительный анализ» (ру / eng )
Ссылка на Часть2: «Эксперименты на торе» (ру / eng )
Cсылка на «Часть3: Практически значимые решения» (ру / eng )
Cсылка на «Summary» (ру / eng )
Теги:
Хабы:
Всего голосов 10: ↑9 и ↓1+12
Комментарии102
24
Карма
0
Рейтинг
@Sergey_Kovalenko

Пользователь

Отправить сообщение

Публикации

Истории

Ближайшие события

17 февраля – 24 марта
Конкурс «Снежный код» от Хекслета. Три гранта на бесплатное 10-месячное обучение
Онлайн
Больше событий в календаре
Разработка
6 марта
Вебинар: PR продукта как инструмент удержания
Онлайн
Больше событий в календаре
Другое
10 марта
DevOps Middle: открытый вебинар с экспертами СберТеха
Онлайн
Больше событий в календаре
Разработка
Администрирование
12 марта
Femtech Force Jam: конференция о технологиях в сфере женского здоровья
Онлайн
Больше событий в календаре
Другое
13 марта
Весенний Хабр Семинар: как синергия HR и PR помогает удерживать сотрудников
Москва
Больше событий в календаре
Менеджмент
Маркетинг
Другое
20 марта
Офлайн-конференция Хабр х K-team: как удерживать таланты в 2025 году
Москва
Больше событий в календаре
Другое
20 марта
IX HappyWorkForum | Аутентичность и ментальное здоровье персонала
Москва • Онлайн
Больше событий в календаре
Другое
24 марта
Серия вебинаров «DevOps Middle: AvitoTech vs X5 Tech»
Онлайн
Больше событий в календаре
Разработка
Администрирование
27 марта
Вебинар «Контент-маркетинг здорового человека: как привлечь внимание аудитории»
Онлайн
Больше событий в календаре
Маркетинг
Другое
10 апреля
«GoCloud 2025» — масштабная IT-конференция про облака и AI
Москва • Онлайн
Больше событий в календаре
Разработка
Администрирование
Менеджмент
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань
Больше событий в календаре
Разработка
Маркетинг
Другое

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr