没有交通拥堵的城市

第二章
（ 第1章的链接 ）

道路网络设计的艺术

在计算机科学家眼中的城市交通问题

如果我被推荐一篇标题为“设计道路网络的艺术”的文章，我将立即询问在其作者的参与下建造了多少个道路网络。 我必须承认，我的专业活动远非道路建设，而且最近与微处理器的设计有关，在我的职责中，我负责处理数据交换的资源消耗。 那时，我的桌子正好站在全景窗户的对面，从那里可以欣赏到伏尔加格勒高速公路的长段和第三运输环的一部分的美丽景色，从早到晚，从地平线到地平线，无休止的交通拥堵。 有一天，我突然感到震惊：“我在芯片上处理的数据交换过程的复杂性可能类似于汽车在道路迷宫中流动时所面临的困难”。
也许是从外界的角度来看，以及该地区非传统方法的应用，这使我有机会了解交通拥堵的原因，并就如何在实践中解决问题提出了建议。

那么，这种方法的新颖性是什么？

从历史上看，公路的主要目的被认为是它们提供的长途快速行驶（罗马和各省之间）的机会。 对于联邦一级的城际公路网，这样的判断是合理的：它们连接的城市看起来像地图集上的稀有小点，而且在这些城市之间行驶的大多数汽车都通过了自己的路，却没有转弯。

但是，一旦我们翻了几页并打开了一个大城市的详细地图，情况就会立即发生变化：可以开始或结束旅程的地址数量大约达到一万，所有这些地址都非常密集地分布着，相对较小。 同时，成千上万辆汽车可以立即在这样的城市的街道上行驶，而且，每辆汽车的目标不仅是填补已经空荡荡的道路，还需要将人员或货物从一辆将具有特定地址X的点指向具有特定地址Y的点。综上所述，这意味着必须调整城市交通系统以有效解决多个并发寻址的问题。 因此，城市交通系统的功能变得比城市间的道路网络更类似于电话或计算机网络。

在信息传输技术领域中，将路网视为硬件开发人员或工程师的交换电路是一种讨论问题的完全自然的方式，但是据我所知，在研究运输问题的人们当中，新的。

信号交换理论是一门狭窄的工程科学，当然，仅凭信号交换理论还不足以规划单独的街道，路口或预测高速公路直行隔离段上的交通流行为。 幸运的是，上面列出的问题已经得到了很好的研究，解决这些问题的方法已经成功地付诸实践。 转换理论又使建筑师能够减轻风险，尽管道路网络的所有要素都得到了完美执行，但城市仍处于交通崩溃的状态。 之所以存在这种风险，是因为执行多个并发寻址是一项耗费资源和时间的任务，其有效解决方案的关键不在于街道的宽度和交通换乘的便利性，而是在于选择哪种特定交换方式的有效选择。拟议的公路网将实施的方案。

例如，从这项研究中，您将发现为什么仍在现代城市中经常使用的“动脉”型交通网络“很糟糕”，并且随着人口的增长必然会导致交通拥堵。 另一个有趣的结果与观察结果非常吻合，这说明了为什么仅在所有交通拥堵完全发生在换乘枢纽附近之前，仅道路扩展就不会以某种方式改善这种状况，即使这个城市保持不变。

当我写这篇文章时，对我来说至关重要的是，对于大多数普通的建筑师来说，这是可以理解的，并且可以通过他的工作而变得有用。 我试图向读者介绍一种简单的语言转换问题，以制定评估特定道路网络应对并发寻址任务的标准，并使用模型示例展示了如何在实践中使用此知识。

本文面向的读者群是一些对大学范围内的数学，算法理论稍有熟悉的读者，他们准备花1至5天的时间。

车流分离与合并

对于许多驾驶员而言，显而易见的是，交通困难主要发生在由于某些原因而不得不改道的汽车路段。 例子包括路岔，收窄，邻近高速公路出口和通道的区域，部分因事故或道路工程而被阻塞的高速公路路段。
在本节中，将尝试对这种情况下发生的过程进行定量描述，我们将从了解汽车如何切换车道开始。

切换到相邻行车道的两种策略
沿高速公路的交通具有自然的不平衡性：有人喜欢开快一点，有人慢一点，有些车之间的距离减小了，很难驾驶，而另一些车之间的距离增加得太多，以至于汽车适合在那附近的车道 直接在随机驾驶员一侧的相邻车道的气流中这种间隙的出现可能是频繁的或不是很频繁。 如果在需要进行操作时没有间隙，驾驶员可以采取至少两种行为策略：

策略1
几个合适的间隙可以简单地位于驾驶员位置附近。 如果运动足够密集，那么驾驶员不太可能能够提高速度并赶上必要的距离，但是通过放慢一点速度，驾驶员将让邻居流超越汽车，从而与该距离相等。原本落后-不会有什么大麻烦。 这种策略的成本显而易见：由于需要降低速度，驾驶员本人和在自己车道上落后的汽车会浪费一些时间。

策略2
为了等待，您需要有耐心并且有足够的时间进行此操作。 另一种选择是尝试在“这里”和“现在”执行必要的操作。 根据这个想法，驾驶员在他将要行驶的车道上向他后面的汽车发出信号。 反过来，那些响应他信号的人应该放慢速度并“让汽车在它们前面移动以前进”，从而在其流动中形成必要大小的间隙。 在这种情况下，时间成本在车道的车厢之间分配，驾驶员最终切换到这些车道上。

在现实生活中，这两种策略是同时涉及的：首先，驾驶员放慢速度，等待相邻车道中较大的间隙，然后才向行驶中的汽车发出信号关于他们打算进行切换的意图。

毫无疑问，通行道路，高速公路出口和道路狭窄并不是车道之间切换的唯一原因，这在设计道路时值得记住。 为了防止高速公路上的情况降级为以最慢的拖拉机速度爬行的一大排，高速公路上的汽车必须能够超越繁忙的交通，这是必要的。 然而，由于驾驶员不强制超车过程和车道之间的相应切换，因此以不同速度在道路上行驶的车辆的共存问题具有稍微不同的性质并且可以与所讨论的问题分开。 如果驾驶员不加快行动，根据概率论，自然会给驾驶员一个方便的操作机会，为此，他不需要打扰其他驾驶员的动作。

一次切换的成本
现实中的驾驶员行为可能非常复杂，但对我们而言至关重要的是，在模型条件下获得的结果仍然合理：每个车道之间的强制切换都会对交通参与者造成时间损失。

现在让我们评估损失的时间量如何取决于道路上的交通密度。

我们将沿每个车道的运动视为单独的流。 为了保持与同一车道上的汽车的舒适距离，驾驶员因此保留了一条具有一定特征长度d的路段。 让ρ车每单位长度落入一条小溪中。 我们同意将流量密度称为小，或者如果乘积ρ × d远小于1，则ρ很小。

在驾驶员意识到需要移至下一行时，驾驶员要占用的长度为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 _out =（ α / 2ν ） ⋅pq⋅ （1-1 / s ）

通道相邻路段的损失强度率
尽管有一些区别，但与进出道路相连的路段后面的高速公路上出现的情况在很大程度上重复了出口前路段的情况。 让少量能量为q的汽车通过侧向坡道倾泻在高速公路的主要交通中（图3）。


图3

匝道只有有限的长度，因此所有新到达的汽车都应切换到高速公路的右边缘车道。 结果，右边缘车道1上的交通密度局部高于道路上的平均车道密度，这就是为什么其中一些驾驶员决定切换到左侧较不繁忙的相邻车道，进而导致当地在第二车道上已经增加了密度。 在车道之间切换的过程将继续进行，直到在高速公路的整个宽度上流量密度趋于平衡为止。 假设所有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

为了方便起见，在前叉处向右行驶的汽车将被称为“蓝色”，在左侧向左行驶的汽车将被称为“红色”。 最初，两种“颜色”的汽车混合行驶，分散在高速公路的所有2 条车道之间。 当它们接近货叉时，红色的汽车开始缓慢向左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ν ） p q _i

总结所有i的最后一个公式，我们发现仅由蓝色汽车产生的损失：

I _blue =（ α / 2ν ） ⋅p⋅ （ q ₁ + q ₂ + ... + q _m ）=（ α / 2ν ） p 2/4。

如前所述，总损失将是原来的两倍，达到：

I _div =（ α / 2ν ） p 2/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. 如果我们试图防止仅在道路的一小段重叠的路线合并，那么在整个城市范围内，由干流和支流的驱动程序引起的相互干扰应该较小。

城市生存的经济前提。
具有“随机访问权”的城市模型²

（注2：该术语取自RAM概念，指的是随机性，甚至概率，甚至时间消耗。）
设计（或重新设计）城市交通系统的任何项目的第一步可能是试图确定城市现在真正需要的转换方式以及未来需求的变化。

如果我们先将城市划分为不太大但又不太小的区域，然后针对每对这样的区域，指出其居民在一侧或另一侧的大概旅行次数，则可以进行这种分析。一天中的某个时间或另一时间。 通过将所做的预测放在一个矩阵中，您将因此获得城市居民的移民需求矩阵。

正是对于这个矩阵，我们应该搜索一个网络，该网络允许驾驶员和乘客在单独的旅行中花费尽可能少的时间，而从城市当局那里需要尽可能少的资源来实现网络。

说到现有的城市，重要的是在这里不要犯错误，不要用人们在历史上受当时障碍或困难影响而确定的出行次数来代替人们真正需要的出行次数。设计工作。 柏林隔离墙倒塌之前和之后的运输网络可能可以最清楚地说明上述观点。

本部分将主要处理我不是专家的人道主义问题，但我认为，以业余人员的身份进行讨论比仅仅避免问题更为正确。

为了更好地反映人口的迁移需求，值得从以下基本问题开始：“城市是做什么的，其有用功能是什么？”

让我们尝试不以城市（和村庄）的普通居民的身份来回答这个问题，而是从负责某个大型发达国家的城市化进程的人的角度来回答。 从这个角度来看，历史动机曾经使这么多人挤在一块很小的土地上，或者他们为什么现在继续这样做的原因，不再重要，城市的经济影响是至关重要的。一个或另一个大小，以及通过什么机制可以达到这种效果。

我认为，存在大城市的主要原因是，一方面，技术公司有机会找到稀有职业的雇员；另一方面，掌握了稀有职业的人有出售他们的机会。为有竞争力的公司提供服务。 在一个小城市（非专业化城市），根本不可能生产许多商品和服务，或者使技术公司及其员工处于相互为人质的位置，而彼此之间没有任何选择。

例如，以学校文学老师的不太专业的职业为例。 据统计，他们的需求大约是每1000人中有1名老师。 在正规学校中，有3-4位导师教授文学。 如果城市中至少有4-5所中学，就人口而言，相当于约1.5万人，那么文学老师的工作选择就可以称为竞争性的。

显然，具有工程专业知识的人在人口至少十万的城市的劳动力市场上感到自在。 当然，也有这样的职业，仅在人口超过100万人的城市才出现对这些职业的需求，但是拥有数百万个城市对我来说没有任何经济意义。

综上所述，以下两个假设看起来很合理（但是，其有效性并不影响本文主要内容的真实性）：

1. 普通成年人需要最频繁地出差旅行，才能为他们找到4-5个最有前途的工作；
2. 对于代表稀有且最具经济价值的职业的很大一部分人口来说，最频繁出行的距离可能与他们所在城市的半径相当。

为了更好地反映假设1和2，在我的示例中，我经常使用具有“随机访问权”的城市模型，假设所需旅行流量的力量在城市的任何四分之二之间相同，或者，换句话说，在迁移需求矩阵的所有单元中都有相同的正数。 如果您随机查看白天在这样一个城市进行的旅行记录，那么对于下一个标记的旅行，所有季度都有相同的可能性作为该旅行的开始或结束，并且位置之间没有关系应注意“初始”和“最终”区域。

具有最简单拓扑的道路网络

让我们尝试将前几段中描述的思想应用于从生活中获取的某些类型的城市规划。

线性城市

最初的大型定居点主要起源于沿海地区，海洋与悬崖之间的一小片土地地区或繁忙的道路，因此在发展过程中，它们获得了狭窄的细长边界。 这些定居点中的许多都幸存至今，保留了其细长的形状并变成了现代城市（请参见下图）。


（里约热内卢的禁区，作者不详）

在这样的城市中，通常只有一条宽阔的道路可以建造。 假设每个四分之一（地域划分带）均产生功率为1的旅行流，所有这些四分之一的数量等于n ，并且城市本身遵循“随机访问”迁移模型。


图7

让我们尝试为上面列出的参数查找平均行驶时间和所需道路面积随n的增加如何变化。

因此，让所有四分之一具有相同的形状和大小，并且它们的数目乘以λ （λ）倍。 很明显

• 主干道的长度增加了λ倍。

由于公认的“随机访问”模式，始于城市右半部分的旅程中有50％将在其左半部分结束（相反的情况也将是正确的），因此，宿舍数量会增加通过λ因子，穿过城市中心的流量也将乘以λ倍。 如果我们以任意点将城市划分为给定比例（1：3、2：5），而不是中间，则具有相同推论的类似讨论将是正确的。

• 沿干道的流动功率增加了λ倍;
• 每个路段所需的主要道路的车道数乘以λ倍。

平均行程的长度或多或少很明显

• 花费在该距离上的净旅行时间增加了λ倍。

剩下要计算的是一次旅行中由于转换成本而浪费的时间增加的次数。 功率为1的横向流进入和流出每个四分之一，它们共同产生时间损失，强度为：

I = I _输入 + I _输出 =（ α / 2ν ） p⋅2 ，

其中p是主要道路上的流量的动力。 我们已经知道，主要道路上的路口数量和流量增加了λ倍，因此，网络产生的总时间损失乘以λ2倍。 另一方面，由网络生成的行程数（所有这些损耗均分配在这些行程之间）增加了λ倍，这就是为什么

• 由于转换成本而导致的净旅行时间损失增加了λ倍。

让我们在一张表中展示所有结果：

线性拓扑
功率为1的地址点数（四分之一）................................. n
总道路面积............................................... .................................. O（ n ² ）
净旅行时间
用于覆盖距离................................................... ...................... O（ n ）
净旅行时间
因更换成本而损失............................................. ........................ O（ n ）
交换节点数.............................................. ..................... O（ n ）
给定侧流的功率，交换节点的数量.............. O（ n ）

使用的符号“ y = O（ x ）”表示参数x和y在功能上是相关的，并且当x不受限制地增长时，比率x / y趋向于一个有限的，不同于零的数字。

蜂窝城市

第二种相当普遍的计划方法是按照矩形矩阵的形式布置四分之一部分，类似于将分块放置在巧克力棒中的方式。

我们同意称这类城市为“蜂窝”。”


（洛杉矶，照片：Slava Stepanov）

图8显示了一个蜂窝城市的模式，该城市由n个 （考虑到“一半”）四分之一组成，一起组成一个规则的正方形。 这些街区彼此隔开，共有√n条道路，有条件地从西向东延伸，有√n条道路从南至北延伸。 总体而言，这些道路形成√n×√n 个交叉口，每个交叉口都可以实现为交通信号灯十字路口或通过路桥/天桥来实现。


图8

无论是单向还是双向交通，在蜂窝城市中从A点到B点的任何旅程都可以沿着一条不超过两条街道且在一个交叉路口不超过一弯的路线来实现。

假设像前面的示例一样，每个季度产生的乘幂为1的旅行流，并且人口的迁移需求遵循“随机访问”模型，那么我们现在可以为一个蜂窝城市计算出定律。 average travel time and the resource intensity of road network construction will change with increasing quantity of quarters.

如果四分之一的数量增加λ，则：

• 城市面积乘以λ倍，其线性尺寸乘以√λ，
• 与线性尺寸成正比的平均行进距离和经过它的净时间乘以√λ倍，
• 街道数和与某条街道相邻的街区数乘以√λ倍，
• 流量的力量与“接触”的季度数成正比（稍后将对此术语进行说明）乘以√λ倍，
• the required area of ​​all roads grows as (number of streets) × (length of one street) × (power of street flow) = √ λ ⋅ √ λ ⋅ √ λ = λ √ λ

Lateral flows are divided into those that go from or towards the quarters and those that turn from one street to another at intersections. The power of first flows, according to the conditions, always remain equal to unity. Through the second ones, almost all traffic is moving, coming or leaving the highway, if we take into account that there are much more quarters in the city than quarters on one given street. As a result, the change in the power of the second flows can be estimated by the formula (change in the power of the flow) / (increase in the number of intersections on a particular street) = √ λ / √ λ = 1. Equality of the last ratio to the constant suggests that these flows do not significantly change with an increase in the number of quarters, therefore, the increase in switching costs generated by the network as a whole will be: (increase in the total number of quarters + intersections) × (change in the value of the flow on a single street) = λ √ λ . Since the power of the migration flow generated by all quarters increased by a factor of λ , then

• net travel time lost due to switching costs increases by a factor of √ λ

让我们在一张表中展示所有结果：

蜂窝拓扑

功率为1的地址点（四分之一）的数量……............... n
总道路面积............................................... .................................... O（n√n）
净旅行时间
用于覆盖距离................................................... ................... O（√n）
净旅行时间
因更换成本而损失............................................. .................... O（√n）
交换节点数.............................................. ......... O（ n ）
给定侧流的功率，交换节点的数量..... O（ n ）

比较线性和蜂窝网络，很难不注意到，随着城市的发展，建设所需的资源强度和一次旅行所花费的时间随着城市的增长而比第一个网络要快得多。第二个。 例如，与相同规模的线性城市相比，一个由100个四分之一小区组成的蜂窝城市所需的沥青少10倍，而穿越该城市所需的时间平均少10倍。 因此，仅在非常小的城镇中使用具有线性拓扑的道路网络才有意义。

如果有一段时间我们忘记了转换成本的存在，那么蜂窝拓扑可以被认为是设计道路网络的理想方法，因为它为平均行程长度和所需道路面积提供了渐近最优的O估计。 确实，对于城市的任何“紧凑”位置（具有随机访问权限），行程的长度不会比城市面积的平方根慢，而这反过来通常与人口成正比。 结果，我们得到所有相同的O（√n）。

原则上，在蜂窝城市中，一条典型路线沿“角”而不是一条直线运行，这一事实意味着有机会寻找最佳的城市规划方法，但可节省20％的费用（即如果有一天汽车学习如何穿越墙壁，我们将赢得的最大胜利）不太可能会迫使建筑师放弃街道和道路的矩形布置。

通过记住每辆车保留一部分车道用于其移动，可以获得网络建设（和维护）成本的最低可能限制。 结果，道路的总面积与平均行驶时间（平均行程长度）和城市内汽车数量的乘积成正比：O（√n）×O（ n ）= O（n√ n ）（与移动城市的表格比较）。

如果我们讨论由于转换成本而导致的旅行损失时间，那么令人惊讶的是，它与覆盖距离的时间关系并不渐近取决于蜂窝或线性城市的宿舍数量（O（√ n ）/ O（√n）= 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为2的幂的情况下，地址树内的任何路由都准确地通过log ₂ n个交换节点，这无疑（渐近地）小于蜂窝网络（O（√n））的相同指标，或者线性（O（ n ））拓扑。

两种最简单的对数网络

使用“树状”网络作为构建块，可以很容易地将先前的解决方案推广到有k个起点的情况。 有两种简单的方法可以做到这一点。

第一种方法是使用反向地址树首先将所有行程的路由收集到一个公共流中，然后使用直接地址树将该流分为子流以寻址其目的地（图11，顶级方案） ）


图11

如果k和n为2的幂，那么最后，任何路由都将精确地通过log ₂ k + log ₂ n个交换节点。 我们同意将根据刚才描述的算法设计的网络称为具有初步合并的 （单向） 对数网络 。

解决同一问题的第二种方法可以通过在第一种解决方案中颠倒合并和分割操作的顺序来实现。 它的实现可以描述如下：对于每个起点，我们创建所有结束点的一组唯一的虚构副本，然后，使用直接的地址树将其连接到这些副本（不再虚构）。

为了完成网络设计，现在仅需通过应用反向地址树（图11，底部方案）将每个终点与其k个虚构副本连接起来即可。

每当n和k为2的幂时，新建网络内任何路由上的交换节点数将再次等于log ₂ k + log ₂ n 。 我们同意将这样的网络称为带预除法的 （单向） 对数网络 。

将单向网络转换为对称网络
通常，如果将与之相连的地址点严格划分为起点和终点，则我们将其称为单向网络。 默认情况下，对于单向网络，将假定它提供了从任何起点到任何终点的至少一条可行路线。

除了一生的旅程，很难找到示例，其中某些地址仅作为路线的起点，而其他地址仅作为路线的终点。 如果我们还包括通过两个方向上的路由将任意两个地址点连接在一起的网络，我们将使推理更接近现实。 我们同意将此类网络称为对称网络。

实际上，单向和对称网络之间没有意识形态上的差距：每个对称网络也可以用作单向网络，并且每个单向网络最初连接相等数量的起点和终点，转换为对称的一个（图12）。


图12

图13a和13b显示了具有初步合并的对数网络和具有初步划分的对数网络的“对称”形式。 他们的例子证明了通过这种类型的网络连接n个季度的根本可能性，其中在任何行程中交换节点的数量将与城市中季度的对数成正比。


图13 a


图13 b

准确的下限估算

到目前为止，已经积累了各种各样的网络，每个网络都包含自己的功能，该功能描述了沿途的交换节点的平均数量对城市中地址点数量的依赖性。 然而，我们仍然不知道在给定的季度数中，这个数字原则上可以有多小。 下限估计可以使用信息方法获得。

实际上，让一些道路网络将n个地址点相互连接，人口的迁移需求使得无论旅程从何处开始，任何旅行都有同等机会在城市中的任何地方结束。

为了解决上述问题，我们将按照此配方生成一条辅助信息消息：很长一段时间，我们将收集所有具有固定起点的旅程的记录，并随机写下这些旅程的地址结束了。 结果消息将是一个随机序列，其中包含城市的n个地址点的名称。

将消息发送到火星的一种方法是，首先将所有名称编码为相同长度的二进制字，从而将原始消息转换为0和1的序列，其次，通过数字通信通道发送结果序列。 由于要对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可以看出，它倾向于迅速增加所使用的路段和交换节点的数量。 后者的质量可能会使这种类型的网络对于实际使用而言过于昂贵。

我们将更详细地分析这些问题。 首先，我们同意该城市遵循“随机访问”的迁移模型，并且其任何地址点生成的流量都具有幂1。

初步合并导致网络损失

在图14中，您可以看到具有上述合并条件的网络中上述条件引起的流量图表。


图14

在我看来，以单向形式描述网络本身似乎很方便，这意味着在图表中用相同数字签名的每个起点和终点实际上都表示城市中的相同地址点。

根据该图，我们可以计算网络中生成的交换成本强度。 让我们从左半部分开始，通过反向地址树，所有路由都集中在一个流中。 网络此部分中的每个交换节点代表两个单向高速公路合并为一个的地方（图15）。


图15

如果最初有效地加载了每条道路，则在合并之后，无需减少车道数量，因此，不应有任何相应的转换成本。

假设功率为1的流已经足以有效地沿至少两个车道加载道路。 在这种情况下，我们将得出一个非常出乎意料的结论：对数网络内部的车流与初步合并的合并是绝对“免费”发生的，不会造成任何时间损失。

计算右半部分产生的成本并不难。 网络的这一部分是直接的地址树，其每个节点都是我们已经研究过的对称分支。 当输入功率为p时 ，在前叉处产生的损耗强度为（ α / 2 v ） ⋅p 2/2 。 进入根叉的流的功率为： n ，因此，根节点中的损失强度为：（ α / 2ν ） ⋅n 2/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 ）。

初步合并的对数网络

功率为1的地址点数................................................... .......... n
平均旅行时间
因转换成本而损失：
渐进性................................................. ................................................... ... O（ n ）
准确值................................................ ................................................... .....（ α / 2ν ） ⋅n
交换节点数.............................................. ................................ O（ n ）
给定侧流的功率，交换节点的数量....................... O（ n log ₂ n ）

预先划分网络中的损失

现在，我们再次进行对数网络的初步划分分析，再次假设该网络用于通过“随机访问”将城市中电源为1的地址点连接起来。
图16显示了它的一个片段，该片段由一个地址点以及与该点相邻的直接和反向地址树组成。


图16

首先，我们可以估计碎片产生的开关损耗的强度。
通过以下等式I _{t_div1} =（ α / _2ν）⋅n 2可以找到在流划分过程中产生的成本，该等式是在上一示例中针对直接地址树推导的，而不是n 。 确实，图16和14中的直接地址树具有相同的深度，并且涉及幂次相似的流（注意：相似性是指通过将另一组值乘以某个固定数来获得一组值的能力。 ，以说明三角形之间的相似性）。 由于在单个分叉处发生的交换成本的值与其输入流的功率之间存在二次关系，因此所有流的同时减少n次将使整个树中的损失减少n ²倍。对旧的（ α / 2ν ） ⋅n ² ，我们得到一个等于：

I _{t_div2} =（ α / _2ν ）。

现在，我们可以在片段的左半部分中计算成本值。
由于反向地址树内的道路合并流的价值很小，因此这次修建比两条车道宽的道路是不合理的。 在这种情况下合并不再是免费的：与前面的示例相反，高速公路上的狭窄区域（图17）将必然产生转换成本。


无花果 17

假设驾驶员提前意识到即将出现的变窄，我们可以假设从死角车道切换的过程很慢，沿着高速公路延伸了数百米。 在这种情况下，我们有权诉诸我们先前使用的技巧来计算对称叉处的损失-将总迁移流量q分成许多小部分q _i ，然后将它们解释为来自坡道。 每个此类子流产生的损失可通过以下公式计算：

I _i =（ α / 2ν ） ⋅p q i⋅ （1 +1 / s ），但是，这里有两个微妙之处。

第一个是汽车不会比下一行迁移得更多。
实际上：由于明显的对称性，两个中央车道中的流量应始终具有大致相同的密度，因此驾驶员将没有太多理由越过中线。 从所观察到的结果可以推断，在由部分侧向流动引起的损失的公式中， s等于1。

随着汽车离开边缘车道，切换为两个中央车道，中央车道内的流动功率逐渐增加，在每种情况下都从P / 2变为P。 因此，第二个微妙之处是p对子流i数量的显着依赖性，这使我们写道：

不
I _i =（ α / 2ν ） ⋅p q i⋅ （1 +1 / s ），
但是：
I _i =（ α / 2ν ） p （ i ） ⋅q i⋅ （1 +1 / s ）。

当迁移流被划分成许多小部分的大小都相等时，相关性p （ i ）用线性图表示（图18）。


图18

要计算损耗强度比率，我们必须求助于积分，或者（这可以使可积分函数的形式特别简单）将等于3 P / 4的图的平均值作为p （ i ）。 由于来自每个边缘通道一侧的总迁移流量为P / 2，因此在单独的合并节点中的损失强度将为：

我 _合并 = 2⋅ （ α / 2ν ） ⋅ （3 P / 4） ⋅ （ P / 2）=

＝（ α / 2ν ）3 P 2/4。

为了找到反向地址树上一个片段内部产生的时间损失，我们可以将_合并的公式应用于其每个节点：

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个功率为1的流是通过其地址点生成的，因此我们刚刚发现的值恰好等于平均行程的开关损耗。

实际上，对于我们来说甚至更重要的是，甚至没有一个特定的数字，它等于特定的转换成本，但是随着n的增加，这些成本保持不变。 就我们之前研究的所有类型网络中的切换损耗而言，后者使渐进式对数网络渐近渐近地变得最经济。

不幸的是，领导不是免费的。 尽管绝大多数流量的值几乎消失了，但网络中包含的每个地址树都包含约2 n个双车道路段和约n个全尺寸交换节点。 网络中有2 n棵树，这意味着O（ n ² ）个分支和节点，这使得它不仅在时间效率方面最经济，而且在考虑的所有示例中，它也是构建成本最高的网络。

至于横向流量的总和，可以很容易地计算出它的值，它以速度O（ n log2 n ）增长，在这种情况下意义不大。

带有预除法的对数网络

功率为1的地址点数................................................... ............ 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的四个流，而不是四个幂为1/2的流（图20）。 我们将获得的未来网络的片段命名为BN ₂ [i; 我+1]。


图表20

如果子流未合并，但仍位于地址树中，则在下一代节点中，每个子节点将再次分为两部分，即功率和地址点集大小相等。旅行的方向。

为什么要打破既定的传统，因为在合并过程之后，我们仍然具有与以前相同的流类型集，但是每种类型的代表较少。 来自BN ₂ [i; [i +1]，我们可以将完全相同的除法规则应用于地址树中其类型的流。

没有理由不归纳地重复上述用于合并-分裂相同流的逻辑构造。 图21显示了组合两个片段的方案
另一方面，将BN ₂分成BN _4的一个片段，图22显示了一般情况下的相同算法。


图21


图22

最后，片段的放大过程将完成，并将我们引向唯一元素BN _n [1; n ]。 我们将其称为平衡对数网络（图23）。


图23

让我们检查该网络的复杂性和所产生的开关损耗的价值。
基于平衡网络设计的归纳性质，其结构中包含的交换节点数可以用递归公式描述：

节点 （BN _k ）= 2个节点 （BN _{k / 2} ）+ 2 k ，

有以下限制：

节点 （BN ₁ ）= 0。

此方程组的解决方案是函数：

节点 （BN _n ）= 2 n log ₂ n 。

由于BN _n的设计需要对数₂ n的归纳步骤，因此每个旅程将经过对数₂ n个划分节点和相同数量的合并节点，并在其途中交替进行（图24）。


图24

每个分割节点内产生的损耗：
（ α / 2ν ） ⋅ （1） 2/2 。

每个合并节点内产生的损失：
（ α / 2ν ） ⋅3⋅ （1/2）2/4 = 3/16（ α / 2ν ）。

考虑到两者在平衡网络中的数量均为n log ₂ n ，我们可以得出总开关损耗的准确值：
11/16（ α / 2ν ） n log ₂ n ，

每一趟是：
11/16（ α / 2ν ）log ₂ n

平衡对数网络

功率为1的地址点数................................................... .......... n
平均旅行时间
因转换成本而损失：
渐进性................................................. ................................................... ... O（log ₂ n ）
准确值................................................ ................................................... .... 11/16（ α / 2ν ）log ₂ n
交换节点数.............................................. ............................... O（ n log ₂ n ）
给定侧流的功率，交换节点的数量....................... O（ n log ₂ n ）

上面获得的数据使我们可以将平衡网络视为引入的时间损失量与总体结构复杂性之间的良好折衷。 原则上可以将其用作真实城市的道路网络，但在经济上几乎不可行。 在我看来，使用平衡网络实际上可以带来很多好处，这是对信号延迟量有严格要求的大规模信息系统，例如蜂窝通信，Internet，分布式计算和多处理器计算机。 。 对我们而言，平衡网络的最大价值在于其设计方法。 稍后，使用此方法的修改，我们将能够改善从实际意义上来说至关重要的线性和蜂窝城市网络。

为什么历史城市注定要塞车

我的发言似乎是出乎意料的，但是在前面的段落中，我们已经找到了为什么自然发展的城市通常遭受交通拥堵的问题的答案。 那么它的本质是什么？

The fact is, many historical cities that survived after the era of medieval fortresses (for example, almost all the capitals of the “Old World”) inherited from this time the radial structure of the streets. Unfortunately (for their modern residents), a road network with a similar topology does not scale well: the dense arrangement of radial roads near the center is becoming too rare on the periphery. As a result, in the process of population growth, the streets that were initially located on the sidelines of the few roads leading to the fortress became larger and the streets that appeared on the periphery were short and did not acquire sufficient transit significance to grow in breadth. As a result, the road network that we see now in large historical cities most often refers to Arterial-type transport systems, and in our terminology, to the Logarithmic networks with (incomplete) preliminary merging.


(Moscow roads, photo: Slava Stepanov)

If we talk about the length of the roads that a driver should drive along, the implementation of this type of network is not bad: the distance traveled often differs little from the straight line distance, and its average value in the city, as it should be for “decent” transport systems, grows at a rate of O(√ n ). The trouble is that with the enlargement of the city at the Logarithmic network with preliminary merging, the switching costs generated by it increase too quickly: the amount of time for which, on average, the trip is extended because of them, depends on the number of people living in the city like O( n ). It is clear that starting from some n , this time will prevail over the net time to overcome the distance, in other words, traffic jams will appear in the city.

Undoubtedly, the reorganisation of the transport system in large historical cities is a task that can be solved. However, it is important to understand that the construction of another one, two or five large transport arteries, albeit slightly improve the situation in the city, but will not eliminate the root cause of traffic jams. Apparently, the only way to overcome the drawbacks of the Logarithmic network with preliminary merging is to use another network. A good candidate here may be a network with cellular topology, within which the time to cover the distance is growing, at least, at the same rate as switching losses are growing.


(night Berlin, photo: Vincent Laforet)

Perhaps that is why modern Berlin, although with large arterial highways, is already distinguished by a clearly visible cellular structure.

There are many interesting solutions in the world on how to make residents of historical cities more mobile, but the main prize in the struggle for transport accessibility should probably be given to the engineers of Barcelona.


(Barcelona's updated road network, photo: Vincent Laforet)

A closer look at the networks of Linear and Cellular cities

After the methods of analysis were found and honed on abstract networks, now it is time to apply them to more realistic cases of cities with Linear and Cellular topology. In this section we will try to analyse in all details the features of their transport networks, establish the numerical value of the switching losses intensity rate, find how its value depends on the size of the quarters, and discuss possible variations and improvements.

Linear city
This time, we will consider an example of a city in which there are two one-way highways: Western highway with a traffic towards the north and Eastern highway with a traffic towards the south (Chart 25).


Chart 25

Let each quarter generate a flow with power 1. In this case, the power of one route heading from one quarter to another one amounts to 1/ n .

To begin with, we will define the power of side flows in the highways. Western highway is the only way to get to the quarter i from the quarter ( n − i ) located southwards, and the only way to get from the quarter i is to the quarter ( i − 1) located northwards. It means that the power of traffic exchange flows between Western highway and the quarter i are:

q _{W_out} = ( n − i )/ n — the power of the side flow leaving Western highway,
q _{W_in} = ( i − 1)/ n — the power of the incoming side flow.

It is clear that the power of side flows in Eastern highway depends on i in a symmetrical way:
q _{E_out} = ( i − 1)/ n — the power of the side flow leaving Eastern highway,
q _{E_in} = ( n − i )/ n — the power of the incoming side flow.

Of course, the sum of the flows leaving the i -th quarter:
q _{E_in} + q _{W_in} = ( n − 1)/ n ,

coincides with the sum of the flows entering it:
q _{E_out} + q _{E_out} = ( n − 1)/ n ,

and both of these values ​​do not depend on i (each quarter has a flow with power 1/ n , this flow consists of trips which begin and finish within the given quarter).

To calculate the power of the main flows, we will draw an imaginary line across the Western highway on the same level with the i -th quarter. In total, this line will cross:
(the number of quarters southwards) × (the number of quarters northwards) = ( n − i )( i − 1) of routes that together create a flow with the power:

P _W ( i ) = ( n − i )( i − 1)/ n .

The same formula:
(number of quarters southwards) × (number of quarters northwards)/ n ,
should express the power of the traffic flow in the Eastern highway P _E , in other words:

P _E ( i ) = P _W ( i ) = P ( i ).

Knowing the power of all the main and side flows, we can calculate the losses intensity rate that occur in the network in the area near the i -th quarter:

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 ν ) ⋅ 2 P ( 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 ).

If we summarise the last expression across i , we will get the losses intensity rate generated by the entire network as a whole.

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 ).

The sum ∑ _i ( i / n ) ⋅ (1 − i / n ) ⋅ (1/ n ) for any large n can be replaced with good accuracy by the integral:

∫ t (1 − t ) d t ( t ∈[0; 1] ) = 1/2 − 1/3 = 1/6.

Based on this, we can obtain that the intensity of switching losses in a Linear city with n quarters with power 1 amounts to:

I = ( α /2 ν ) n ² /3.

Up to this point, we considered only examples in which quarters always generated flows with power 1. Let's consider if the formula for switching losses of a Linear city will change if for each quarter there is not one source of flow with power 1, but — λ (the quarters will become λ times larger).

Let us take a city with m quarters. If quarters generated flows with power 1, then the switching losses would be ( α /2 ν ) m ² /3.

An increase in trip production power by every quarter by a factor of λ leads to an increase in both the main and side flows by a factor of λ . As a result, the costs at each junction, and therefore inside the network as a whole, increase by a factor of λ ² times, and the losses formula transforms into:

I = ( α /2 ν ) m ² ⋅ λ ² /3.

To a large extent, it doesn't matter how the switching losses depend on the number of quarters in the city, the main thing for us is how they depend on the flow power of all the trips generated inside it, or in other words, on the number n of sources with power 1. In this case, n is equal to m ⋅ λ , therefore:

I = ( α /2 ν ) m ² ⋅ λ ² /3 =
= ( α /2 ν ) ( m ⋅ λ ) ² /3 =
= ( α /2 ν ) n ² /3.

In other words, switching losses in a Linear city do not depend on how small the fragmentation of its territory into quarters is chosen.

Cellular city

Imagine a Cellular city in which the highways of perpendicular streets are allocated at different heights/levels. This would be possible, for example, if all highways heading from north to south were raised on bridges, and highways stretching from west to east were built on the earth's surface. If, in addition, all highways have two-way traffic, then the road network in such a city will be referred to the standard Cellular topology (Chart 26).

The point here, of course, is not to bring the network described above seriously into practice: it would not look too aesthetically pleasing against the background of the city landscape and, moreover, due to the need for multi-level interchanges, it would eat up the better half of the street space. Nevertheless, this purely hypothetical network is a good way to get the necessary estimates, which later can be easily extended to road networks that are really interesting from the point of view of their applicability in real cities.

As usual, we will assume that the migration needs of residents are described by the 'random access' model, and we will start our consideration with the case when the power of all the flows generated by a given quarter is 1.

In the example of the standard Cellular city, it is convenient to step aside from the established tradition and consider as the address point not a separate quarter, but a territorial zone of a square shape within the intersection of highways and 1/4s of all quarters adjacent to it. Chart 27 shows the relative positioning of several such zones and shows a traffic pattern inside one of them. This chart clearly demonstrates that any driver, leaving the quarter, has the opportunity to enter in the highway, moving in the direction of any of the four sides of the world.


Chart 26

To calculate the value of switching costs generated by the city, we will calculate the power of all the main and side flows within each of its territorial zones. The shape and mutual positioning of the zones allow us to resort to a chess analogy to solve the problem in question, considering the zones as field cells, and the movement of cars between them — as movements of the rook (Chart 27). In a general case, the rook can be moved from one cell to another in two moves; if both cells are on the same horizontal or vertical line, then — in one move.


Chart 27

In order to avoid many inconvenient reservations, we assume that the move in which the rook does not move anywhere is also allowed according to our rules. The rook's movement route, consisting of two moves, one of which is necessarily performed vertically, and the other -horizontally, will be called the simplest. It is reasonable to consider the move 'standstill' as vertical and horizontal at the same time. In this case, it turns out to be true that any two cells on the board are connected to each other by exactly two different simplest routes.

For drivers, the simplest route is the easiest way to get, with minimal interference, from one territorial zone to another, so it's reasonable to assume that real trips will take place along elementary route lines. According to the 'random access' model, the flow with power 1 generated by the address point (territorial zone) should be equally distributed between all n = d ² address points of the city. Therefore, the power of the flow passing along one route line is 1/(2 n ).

We can calculate the flow with what power passes through the cell ( i , j ) in the direction from the south to the north. The simplest route crosses cell ( i , j ) from the south to the north in only two situations. The first of them (Chart 28 on the left):

1a) the start cell of the route is located in one of the last ( d − i ) horizontal lines (rows);
2a) the finish point of the route is one of the first ( i − 1) cells of the j -th vertical line (column);
3a) the route starts with a horizontal section, or lies entirely inside the j -th column.


Chart 28

The conditions describing the second situation look symmetrical (Chart 28 on the right):

1a) the start point of the route is one of the last ( d − i ) cells of the j -th vertical line;
2a) the finish cell of the route is located in one of the first ( i − 1) horizontal lines;
3a) the route starts with a vertical section, or lies entirely inside the j -th column.

On the chessboard there is only 2× [ d ⋅ ( i − 1) + 1⋅ ( i − 1) ] × ( d − i ) simplest routes suitable for the requirements, which together create a flow with the power:

P _SN ( i , j ) = ( d + 1) ⋅ ( i − 1) ⋅ ( d − i ) / n ( = P _SN ( i ) ).

Fixing j , we will obtain the function

( P _SN ) _j ( i ) = P _SN ( i , j = Const ),

describing the dependence of the power of the flow moving northwards along the j -th vertical highway on the distance to the upper boundary of the city, measured in cells.
There are several more or less obvious observations regarding the functions ( P _SN ) _j ( i ), let's discuss them.

Let us start with a circumstance that would be difficult to overlook: P _SN ( i , j ) practically independent on the second argument. As a result, the functions ( P _SN ) _j ( i ) = P _SN ( i ) have the same form for all values ​​of j , in other words, the specific position of the highway inside the Cellular city does not affect its load. Formally, the last statement is proved only for the highway heading to the north, but due to the symmetries of the city it automatically applies to the highway of other directions too.

Now let us look at the formula for P _SN ( i ) itself:

( d + 1) ⋅ ( i − 1) ⋅ ( d − i ) /(2 n ).

As we see, the whole dependence of P _SN i on i lies in the expression ( i − 1) ⋅ ( d − i ). This expression can be interpreted as the product of the lengths of the right and left stretches into which the integer section of length d splits after the i-th element is excluded from it (Chart 29a).


Chart 29a


Chart 29b

It is clear that if you change “right” to “left” and “left” to “right” (Chart 29b), the result of the product will remain the same. Based on such a simple observation, we can draw two inferences that are, in essence, very useful for us:

1. the function P _SN ( i ) is symmetric with respect to the midpoint of the street i = (d + 1)/2, in order words, the flow power at a distance Δ from the lower boundary of the city is exactly the same as at a distance from the lower boundary of the city is exactly the same as at a distance Δ from the upper boundary.
2. On the whole, the city itself is symmetrical up and down, therefore, to get the function ( P _NS ) _j ( i ), which describes the power flow on the j -th highway, but in a southward direction, it's enough to simply mirror the function graph ( P _SN ) _j ( i ) in the line i = ( d + 1)/2. Since ( P _SN ) _j ( i ) = P _SN ( i ), and the graph P _SN ( i ) with respect to the line i = ( d + 1)/2 is symmetric, then ( P _NS ) _j ( i ) = P _SN ( i ) = P _vert ( i ),, in other words,
3. direct and oncoming traffic flows have equal power at any point of the city. A closer graph of P _SN ( i )is shown in Chart 30 (it is believed that d >> 1, i >> 1, d − i >> 1).

Chart 30

The powers of the main flows along horizontal highways are easily found using rotational symmetries; formally, this process can be implemented through a simple replacement of i by j in P _SN ( i ) and a small correction of the lower index.

The next step to take is to find the power of the side flows. Trips that enter or leave traffic on a vertical highway inside the cell ( i , j ), can be conveniently divided into four categories:

1. the flow q _{in_transit} : start point is in any cell of the i -th horizontal, finish point is in any cell of the j -th vertical, except for the ( i , j ) itself (Chart 31a);
2. the flow q _{out_transit} : start point is in any cell of the the j -th vertical, except for the ( i , j ) itself, finish point is in any cell of the i -th horizontal (Chart 31b);
3. the flow q _in : start point is the ( i , j ) itself, finish one is any cell outside the i -th horizontal (Chart 31c);
4. the flow q _out : start point is in any cell outside the i -th horizontal, finish point is the ( i , j ) itself (Chart 31d);

Chart 32: abcd

Having recounted the number of route lines belonging to each separate category, we can conclude that the powers of all four flows are the same and equal:

q ₀ = d ⋅ ( d − 1) /(2 n )

Having the values ​​of the powers of the main and side flows in a vertical highway, it is not difficult to calculate the value of the respective switching costs. Inside a single cell ( i , j ) the switching costs will be equal to:

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) /2 n ² ≈
≈ 2 ( α /2 ν ) ⋅ d ⁵ ⋅ ( i / d )(1 − i / d ) ⋅ (1/ d ) ⁴ =
= 2 ( α /2 ν ) ⋅ d ² ⋅ ( i / d )(1 − i / d ) ⋅ (1/ d ).

To find the costs incurred in all the vertical streets within the whole city, we need to sum I _vert ( i , j ) for both indices:

I _vert = ∑ _ij I _vert ( i , j ) =
= 2 ( α /2 ν ) ⋅ d ² ⋅ ∑ _ij ( i / d )(1 − i / d ) ⋅ (1/ d ).

Since the value of the summands does not depend on j in any way, summing over the second index is equivalent to multiplying by d :

∑ _ij ( i / d )(1 − i / d ) ⋅ (1/ d ) = d ⋅ ∑ _i ( i / d )(1 − i / d ) ⋅ (1/ d ).

The last amount can be approximated by the integral that we already know:

∑ _i ( i / d )(1 − i / d ) ⋅ (1/ d ) ≈ ∫ t (1 − t ) d t ( t ∈[0; 1] ) = 1/2 − 1/3 = 1/6.

Based on this, we can obtain:

I _vert = ( α /2 ν ) ⋅ d ³ /3 = ( α /2 ν ) ⋅ n √ n /3.

We can answer the question what is the value of costs I _horiz , arising in the horizontal highways, using the symmetry of the city:

I _horiz = I _vert = ( α /2 ν ) ⋅ n √ n /3.

Therefore, the switching losses intensity rate within the entire network of the Standard Cellular city is equal to:

I = I _vert + I _horiz = 2/3 ⋅ ( α /2 ν ) ⋅ n √ n ,

and per trip, on average, the switching costs will be

2/3 ⋅ ( α /2 ν ) ⋅ √ n

The effect of cell size on the value of switching losses

Quarters generating flows with power 1 are a rather artificial limitation of the conditions of the problem. We can extend the results obtained above to the cases when the power of the flow generated by one cell is equal to λ .
Let the city consist of m such cells. If all cells were power 1, then the intensity of the total switching losses would be I ₁ = 2/3 ⋅ ( α /2 ν ) ⋅ m √ m . An increase in the number of trips by a factor of λ will multiply by λ times the powers of all the main and side flows in the highways, which in turn will cause the increase by a factor of λ ² in all the switching costs generated within the city. The new formula for the losses intensity rate will thus take the form:

I = 2/3 ⋅ ( α /2 ν ) λ ² ⋅ m √ m

If we assume that the cell consists of λ address points with power 1, then the total number of such points will be: n = λm . Let's express I as a function of n and λ :

I = 2/3 ⋅ ( α /2 ν ) λ ² ⋅ m √ m =
= 2/3 ⋅ ( α /2 ν ) ⋅ √ λ ⋅ ( λ √ λ ) ⋅ ( m √ m ) =
= 2/3 ⋅ √ λ ( α /2 ν ) ⋅ ( λ m )√( λ m ) =
= 2/3 ⋅ √ λ ( α /2 ν ) ⋅ n √ n .

The average cost per trip under the new conditions will be 2/3 ⋅ √ λ ( α /2 ν ) ⋅ √ n , being √ λ higher than their value in a city made up of quarters with power 1.

The last formula tells us that for the same population, population density and total area of ​​all roads, the larger the size of the quarters chosen by its architect, the higher the switching costs. In the case when the city's population is unevenly distributed over its territory, of course, we need to pay attention not to geometric dimensions, but first of all to the average number of people inside the quarter and their migration activity.


(New York City Center photo: Vincent Laforet)

The remark made above is especially important when designing areas with skyscraper buildings. Due to the combination of high population density and its high mobility, it is crucial to design quarters in high-rise areas several times smaller in size than is usual for standard buildings. In civilizations, where skyscraper construction has a long history, the practice of isolating even separate large buildings as a quarter is widespread.

A cellular city with traffic light regulations
In each case, when the lines of two busy highways intersect on the map, the architect must make a choice: either lift one of these roads to the bridge, allowing the flow of the other to pass freely below, or realise the intersection in the form of an intersection, and resolve the flow conflict by traffic light regulation. The second option is often chosen in cities as it is attractively simple, does not imply the need to build large-scale engineering structures, and in addition it provides pedestrians with an easy way to cross the road.


(business quarters of Los Angeles in the afternoon, photo: Boris Shein)

The use of traffic lights in networks with cellular topology has its own characteristics. In Chapter 1, it was shown that with proper synchronisation of traffic lights, cars, while they are moving along the same street, do not even have to stop at intersections: a green light will always light in their direction. This kind of phenomenon is usually called the green wave traffic management. To create it, traffic flows need to be divided into two alternating: filled with cars and free of them. Next, such a mode of traffic lights operation is selected that in the period of time when the next “portion” passes the intersection along one of the streets, the previous portion of cars moving along the perpendicular street has already passed it, and the next one has not yet arrived (Chart 33).


Chart 33

Green wave traffic management carries its own costs and imposes certain restrictions on the layout of city streets.

Looking again at Chart 33, it is easy to see that at any given time exactly half of the area of all roads is not actually used. To compensate this downtime, in the actively used half, the local power of car flows and the number of lanes necessary for them should be twice as large as in a city with overpasses.

The second most important circumstance associated with the use of green waves is the strict regulation of the permissible size of quarters: their length (for two-way streets) should be a multiple of the length of the filled green wave (a section of the flow within which unhindered movement is possible), amounting to about 500 metres. As noted in the previous paragraph, areas with a high population density require an increased frequency of location of roads, so the restriction on the distance between highways (the permissible size of quarters) can potentially cause traffic difficulties.

It is interesting to note that in the green wave traffic management, the switching rules inside the network slightly change. For example, the addition of one more car to the main traffic flow can be performed in the intervals between the filled zones, without thereby causing any serious switching costs (point 1 in Chart 34a).


Chart 34

Of course, this car itself will have to lose some time waiting for the nearest empty zone before getting into the highway, and after that stand at the traffic light until the next filled zone hits it (point 2, Chart 34a), however the value of these losses does not depend either on the size of the city or on the busyness of traffic in the street, therefore, they can be neglected on a large scale.

The situation is completely different if a car tries to leave the highway traffic (Chart 34b). Here, apparently, there are no longer any tricky ways how to make the switching losses created by the driver less. Moreover, due to the doubling of the local power of the flow inside the filled zones, leaving of a randomly selected car from it causes time costs twice as much as in a city with overpasses. In total, the cheaper “entry” and more expensive “exit” offset each other, making the Traffic Light Cellular city in this respect almost no better, but no worse than Standard one.

Flyover Cellular city with one-way traffic

In addition to the use of traffic lights, there is at least one more opportunity to avoid the monstrous interchanges of the Standard city. It implies dividing spatially two-way highways (Chart 35).


Chart 35

As a result of such changes, the number of streets will double, they will all become one-way streets, but most importantly, the interchanges will be greatly simplified (Chart 36).


Chart 36

Since the number of highways heading to each of the sides of the world and the number of journeys passing along them remained the same, the powers of all flows together with the switching costs in the One-way Cellular city and the Standard city with 2 times larger (linearly) quarters, should coincide. If we compare the Standard and the One-way cities with the same quarter sizes, then the switching losses in the second one will be twice as high.

Advanced Road Networks

«Linear» street

How could switching losses be reduced in a Cellular network? The answer to this question can be find by selecting a correct analogy, with the help of a little savvy.

Let us consider a somewhat unusual modification of the Cellular network, which implies that all highways stretching from west to east are two-way, while the perpendicular to them highways are only one-way: either north or south, and these directions alternate from street to street.

As always, we will assume that the city follows the random access model, and each quarter of it generates a flow with power 1.

In this case, it seems quite plausible that the flow originated inside the quarter ( i , j ) is distributed between the nearest streets as follows: 1/4 of it will go to the horizontal road northwards, 1/4 — to the horizontal road southwards, 1/4⋅ i / d — to the vertical highway to the north and 1/4 ⋅ (1 — i / d ) — to the second vertical highway to the south (Chart 37).

Chart 37

Indeed, according to the previously discussed route algorithms, according to statistics, half of the journeys will start from a horizontal section, and for drivers who would prefer this half, it should to a large extent not matter whether their path lies northwards or southwards of the quarter ( i , j ). The remaining half of the journeys will start from a vertical section of traffic and will be divided between highways heading to the south and north as a ratio of the number of quarters lying southwards from the quarter ( i , j ) to the number of quarters lying northwards from it.

As to the flow of trips heading inward the quarter ( i , j ), the rule of its division with respect to the highways surrounding the quarter will be symmetrical (Chart 38).


Chart 38

Among the four intersections adjacent to the quarter ( i , j ), we can consider separately the lateral flows at the intersection of the lower horizontal highway and the vertical street with traffic to the north (Chart 38). The flow of cars entering into the intersection and heading from the horizontal street to the vertical one is:
1/2⋅ (number of quarters on the horizontal)×( number of quarters on the vertical not lower than ( i , j )) ⋅ 1/ d ² =
= 1/2 ⋅ d ⋅ i / d ² =
= 1/2 ⋅ i / d .

The power of lateral flow in the opposite direction is:
1/2⋅ (the number of quarters on the vertical is strictly lower than ( i , j ))×(the number of quarters on the vertical) ⋅ 1/ d ² =
= 1/2 ⋅ ( d − i ) ⋅ d / d ² =
= 1/2 ⋅ (1 − i / d ).

Let's now turn our attention from the Cellular city as a whole to any one of its vertical streets, let's call it My_street. By virtue of symmetries, we will not limit our reasoning in any way, if we assume that the movement along My_street is directed from south to north (Chart 39).


Chart 39

Chart 40 depicts the power of the main and side flows on the highway along My_street, which, as the reader may notice, are incredibly similar to similar graphs for the one-way highway of a Linear city (Chart 26).



Chart 40

In these examples, the flow diagrams coincide completely if inside My_street the lateral flows relating to each pair of opposing quarters and the horizontal highway below them are formally assigned to one imaginary territorial cell. As can be seen from the earlier tables, the road network of a Linear city generates some of the largest switching losses among the networks we have already studied. From this point of view, the traffic pattern within the boundaries of a single street of a Cellular city looks extremely inefficient and is an element that should be improved in the first place.

Advanced Linear City Network

So, we are facing the task of improving a Linear network so that it does not turn into a «square» one. The circumstance that represents the greatest inefficiency in the operation of the Linear Network is the merging of all routes into only two very large traffic flows. In this situation, a reasonable step would be to divide the flows along both of its street highways into Q equal parts. Since the time costs caused by each car joining or leaving traffic are proportional to the traffic intensity on it, as a result of dividing the street lines into Q isolated parts (Chart 41a), the switching losses inside a Linear city should have decreased Q times.


Chart 41

Even after the construction of ten roads nearby we can't hope that the drivers themselves will be equally distributed between them — unfortunately, it does not seem to have a chance of success. A much more thoughtful decision would be to design the network so that each road does not lead to all quarters, but only to a small “segment” of the city, where it would be difficult to get to without using the given road (Chart 41b).

You can see a similar idea in the scheme of movement of elevators inside multi-storey buildings where each elevator allows you to enter and exit it not on all floors, but only within a certain range of heights. Accepting this concept, let us take a closer look at the road r _k , which gives access to the segment Δ _k = ( x _k , x _{k +1} ] for trips that started (not strictly) southwards from xk (it is believed that the numbering of the quarters is performed from the bottom up).

From each quarter which number is fewer (not strictly) than x _k , a q _in stream with a power of Δ _k |/ n ( 1/ n to each quarter inside Δ _k ) enters the road r _k , at the same time it is assumed that there is no possibility to turn from r _k towards any of the mentioned quarters either due to established traffic rules, or due to a special design of the road network.

The cars accumulated on the segment [1, x _k ] will eventually be evenly distributed between the quarters inside Δ _k , therefore, if there were no trips whose start and finish points lie inside Δ _k , then the side flows q _out in the direction of each of the quarters in this section would have the power x _k / n (Chart 42).


Chart 42

In fact, the contribution of “internal” trips to the power of side flows does exist, however, the value of this contribution never exceeds | Δ _k |/ n , therefore, in the case when x _k >> | Δ _k |, it can be simply neglected. The power p _k of the main stream along r _k with simplifications made will be represented by a graph of two straight sections with a maximum P _k equal to x _k ⋅ | Δ _k |/ n . The approximate value of switching losses in the road r _k can be found by the formula:

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 ) ⋅ ( ∑ _x p _k ( x ) )/ x _k + ( α /2 ν ) ⋅ (1 − 1/ s ) ⋅ ( x _k ⋅ | Δ _k |/ n ) ⋅ ( ∑ _x p _k ( x ) )/| Δ _k |,

where the first sum is taken over a segment x ∈ [1, x _k ], and the second over x ∈ Δ _k . The expressions:

( ∑ _x p _k ( x ) )/ x _k , x ∈ [1, x _k ] and

( ∑ _x p _k ( x ) )/| Δ _k |, x ∈ Δ _k

are nothing other than the average power of the flow along r _k inside the indicated intervals. Since the power graph within these intervals has the form of a straight line, the average power in both cases is P _k /2. Replacing

x _k ⋅ | Δ _k |/ n by
P _k ,

we finally present the formula for losses intensity rate in its simplest form:

I _k = 2 ( α /2 ν ) ⋅ P _k ⋅ P _k /2 = ( α /2 ν ) ⋅ P _k ²

Let us now try to calculate the sequence x _k of numbers of those quarters by which a linear city should be divided into segments. As a criterion for the selection of segments, we can take the requirement that the maximum power of the traffic flows P _k in the roads approaching them should have the same value, independent of k , in other words:

x _k ⋅ | Δ _k | = Const.

Remembering that | Δ _k | = x _{k + 1} − x _k , we can infer the difference equation:

x _{k + 1} − x _k = Const/ x _k .

Assuming x and k are continuous variables, and replacing

x _{k + 1} − x _k = x ( k + 1) − x ( k )

by d x /d k ⋅ 1,

we can approximate the difference equation by the differential one:

d x /d k = Const/ x <=> x d x = Const ⋅ d k .

from which we can infer a solution for x _k in the general form:

x _k = ₁ √( k + ₂ ).

It remains for us to determine the value of the constants ₁ and ₂ based on their boundary conditions, however, there is an important subtlety in this matter. Unlike the situation in other segments, all the cars arriving from the western highway to the quarters of the segment with number 1, began their trips inside the same segment. As a result, the graph of the flow power in the first highway to the north will have the form of a regular inverted parabola.

At the same time, the a priori conditions from which the formula for x _k was obtained essentially assumed that the flow power graphs on all highways should be close to a triangular view, and the trips themselves should begin mainly outside the segment where they are directed to. These requirements can be fulfilled with reasonable accuracy if we formally divide the first segment into two equal parts, without increasing the number of roads. Most of the trips that take place along the first highway begin in its southern half, and end in the northern half. Considering only them, we thereby do not make a big mistake in calculating the switching losses, but now the power diagram of the main flow will have just a triangular shape (Chart 43).


Chart 43

It is the middle of the first segment that should be considered the point x ₁ in the formula for x _k . This allows us to get the first boundary condition:

x ₂ = 2 x ₁ or

√( 2 + ₂ ) = 2 ⋅ √( 1 + ₂ ) =>

₂ = − 2/3.

The second boundary condition can be obtained from the requirement that the roads and segments of everything are exactly Q , which means x _{Q + 1} should be subsequent to the quarter with the largest number in the city:

₁ √( Q + 1 − 2/3) = n + 1, whence

₁ ≈ ( n + 1)/√ Q .

Therefore:

x _k ≈ ( n + 1) ⋅ √( k − 2/3)/√ Q ,

| Δ _k | ≈ d x /d k = ( n + 1)/ 2√( k − 2/3) ⋅ √ Q

P _k = x _k ⋅ | Δ _k |/ n =

= ( n + 1) ² / 2 n ⋅ Q ≈ n / 2 Q

I _k = ( α /2 ν ) ⋅ P _k ² =

= ( α /2 ν ) ⋅ ( n / 2 Q ) ² .

Since all 2 Q highways generate losses of the same intensity, the value of switching costs within the entire network will be:

I = 2 Q ⋅ ( α /2 ν ) ⋅ ( n / 2 Q ) ² = ( α /2 ν ) ⋅ n ² / 2 Q .

As you can see, the desired result has been achieved: after dividing the main highways into Q parts, the losses indeed decreased by a factor of Q (except for the increased from 1/3 to 1/2 constant coefficient, compared to the formula for the usual Linear city). Well, we are halfway there, it remains only to apply this result to improve the city with Cellular architecture.

'Skyscraper Elevator' in a Cellular city

For simplicity, we will consider an example of a city in which all the streets are one-way. Using the analogy between a Linear city and the individual streets of a Cellular city, we can divide the highway along the latter into Q parts. By default, it is believed that leaving the quarter, the driver can choose any highway passing near it. At the same time, among all the highways laid along one street, there is a turn towards a specific quarter from exactly one of them. In the process of establishing rules, their uniformity and simplicity are extremely important. Let's take a look at Chart 44:


Chart 44

all the streets have the same view and the same rules as to which of the roads opens access onto which quarter. Chart 45 shows a diagram of permitted turns between highways. Looking at this picture, it is hard not to get confused. The same is often said about the underground scheme in some large city. However, in both cases, everything becomes clear and simple if you know the logic of the idea. The logical rule of permitted turns sounds quite simple: if driving along a highway, you cross roads perpendicular to your movement and you can turn into a quarter located directly behind them, you can turn into any of these roads.


Chart 45

The 'Skyscraper elevator' topology is compatible with both traffic light intersections and overpasses. It is difficult, but possible to generalise it to networks not necessarily of a cellular or linear structure. The latter is really important for historical cities, where it is unlikely that it would be a right decision to demolish half of the historical monuments in order to design many small straight streets, but in which there are already quite large streets that can accommodate several two- or three-lane highways.

About the transport problems and the work of a mathematician

It is pleasant to complete the 6 months laborious work. The work I wrote, of course, does not solve all the problems and difficulties of road design — this issue requires a large number of very versatile and multi-skilled people. Nevertheless, its results provide an opportunity to see important errors in already built cities and provide methods of how to avoid such errors in the future. This article was not intended as a reference book covering all possible cases that an engineer can face in practice — I considered my main aim is to give a new point of view, to develop a new way to reason and talk about the problem, to provide the reader with the necessary minimum of simple model examples which could be expanded by the reader further.

It becomes sad when you realise how much time was lost by city residents in traffic jams just because at the right time there was no mathematician who could spend the evening on a completely solvable problem. How many such problems still surround our life or hide in your profession? Is a person sitting near you at work whose tools are a pencil and a sheet of paper?

I hope everything will change for the better.

I would like to express my sincere gratitude to Janine Lacroix (pseudonym) for her work on translating this text from its original Russian to English.
Thank you for your attention and good luck!
Sergei Kovalenko

2019年
magnolia@bk.ru


( Photo: Vincent Laforet)