Nature 杂志︱城市交通的灭霸响指已经出现，真相就是…
《Nature 杂志︱城市交通的灭霸响指已经出现，真相就是…》的文章是傻大方资讯网小编转载于网络，如有侵权请联系删除。
本网新增内容合作媒体炫6网www.xuan6.com 只为给您提供更多更优质的热门资讯。
点击阅读原文报名
更多沙龙信息请参考文末海报
编辑团队
原文/
M. M. Vazifeh、Helen Knight翻译/
文献/ 校核/
编辑/ 排版/
一
城市
交通
览
译者导读
以最小车队数满足出行需求，以共享出行代替私家车，有如城市交通领域被复仇者联盟3里的灭霸，打了一个响指，将有一半车辆消失一样…这种场景是否会如愿实现？今天介绍的这篇文章就致力于解读按需分配车辆的场景。来自于月初《Nature》杂志封面文章所介绍的MIT团队的最新研究，确定在一定出行需求下所需要的最小车辆数/车队规模。
本文引入车辆共享网络图，将出行视为节点，边代表两次出行可由一辆车完成，从而将最小车队问题转化为有向图中的最短路径问题。
经纽约数据集测试表明其当前出租车数量规模至少可减少30%。博弈论中Price of Anarchy度量用户均衡与系统最优与的成本/效率，其差值即为1/3。
这不禁令人感叹数学优化与实践碰撞之美。尽管研究仅考虑了自动车的场景，人工驾驶车辆下司机服从度可能有所不同，仍表明当前按需出行服务尚有很大的优化空间。同时随着自动车、网联车的普及，研究结果将更贴近实际。
图一、出租车传统接客模式与共享接客模式的比较，图来源于MIT可感知城市实验室。
一、共享出行趋势
自动驾驶汽车的增多，将会极大地改变我们未来在城市周围通勤的方式。尤其是私家车的现状将转变为共享出行服务，而汽车由车队运营商按需提供。这样会帮助减少城市区域内的交通量，还能减少温室气体排放。
但是对于这些要增长的业务来说，计算模型的正确性及效率需要得到保证，才能准确高效的对接个人和按需分配的车辆。这对于每天都有成百上千按部就班通勤出行的大城市来说显得尤为重要。
在面对特定程度的个人出行需求，研究者们还没有解决关于车队最佳规模和运营方式的问题。
但在今天出版的《自然》杂志上，MIT 可感知城市实验室的Carlo Ratti组织了一群研究者，他们在论文里提供了一个“最小车队问题”的高效计算解决办法。
（参考文献1，如需下载请后台留言索取）
MIT城市研究和规划学院的Ratti教授说：“我们之所以对这个问题产生兴趣，是因为共享出行的趋势愈演愈烈，并且这种趋势很有可能最后会演变成自动驾驶。如果出行需求由共享车辆车队来提供，那么一个基本问题就是：我们到底需要多少辆车来满足一个城市的需求，比如纽约。”
视频一、MIT新研究纽约需要的最小车队尺寸
二、“旅行商”思路的失败
研究者们之前尝试通过“旅行商” 的方式来解决这个问题。 “旅行商”思路是为了给去数个地方的推销员提供一个最小总出行距离的解决办法。
然而，即使是借助今天强大的电脑来计算，他们也发现了要通过“旅行商”来找到优化方案极其困难。“结果就是，良好的车队管理的解决办法严重地被规模所限制，也就是说他们只能计算拥有几十辆车的车队，”可感知城市研究室的研究科学家Paolo Santi说道。作为研究小组主管的他，也是意大利国家研究评议会（CNR）的高级研究者。
Santi说：“这种情况不能满足像纽约这种大城市的需求，如果我们考虑把纽约现有的出租车系统替换成更优化的车队体系，我们就必须要找到能够支持现在由1.35万出租车所服务的每天大约50万次出行的最佳方式。”
与之相反的是，研究者们用一个基于网络的模型替代了先前的模型——他们称之为“车辆共享网络图”——来解决这个问题。他们之前用了类似的方法，叫“可共享网络”，用来寻找大城市中共享出行的最佳方式，这记载于2014的一篇论文中。
三、可共享网络的算法逻辑
这个算法将出租车车队的可共享性做成一个图表，将两个要素以节点（或圆圈）以及边界（节点之间的线）用数学形式抽象化。在这个案例中，节点代表每次出行，边界代表两次特定的出行可以通过一个车辆服务。算法可通过这个图表来找到车队共享的最佳方法。
1、数据来源
在这项工作中使用的数据集是2011年在纽约市所有的出租车数据，包括13586辆出租车和超过1.5亿次出行。数据集有许多字段，我们使用了以下几个字段：出发时间、起点经纬度、终点经纬度。时间的测量精度以秒为单位。数据提供者通过GPS位置跟踪技术收集位置信息。城市峡谷处（即两侧高层建筑物的街道）可能产生定位偏差，这可能在收集过程产生略有偏移的GPS位置。所有个人身份验证信息均以匿名形式提供，起始值和目的地值分别指出行的起点和终点。数据来源：http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml
2、原理
节点不相交路径覆盖
（参考文献2，如需下载请后台留言索取）
。接下来我们会提供一组定义，并给出了相关定理与证明，来系统地阐述如何将减少车辆规模转化为一个车辆可共享网络上的路径覆盖问题。
我们注意到，在传统的假设下，允许单个节点对应零长度路径，节点不相交的路径覆盖总是存在。在下文中，为了简化表示，我们放弃术语“节点不相交”而只使用定义1中的“路径覆盖”来表示“节点不相交路径覆盖”。
定理1：设集合C = {P1,…,Ph}为车辆可共享网络V=(N,E)的路径覆盖。所有的T旅行都可以由h个车辆来完成。
证明：考虑车辆可用性网络V中的路径P={e1=(n11,n12),…, ek=(nk1，nk2)}。根据可共享车辆网络的定义，对应于n11和n12（我们称他为T1和T2），可以由单个车辆服务。此外，执行行程T1的车辆保证在时间t2p内到达T2的上车位置；也就是说，车辆共享不会延迟第二次出行的开始时间。
此外，连接时间的上限δ不受车辆可共享网络定义的影响。因此，由于行程T2的起始时间不会由于共享而改变，所以服务于T1和T2的车辆可用于服务与节点n22对应的行程T3，这意味着能够确保T3和T2的共享性的条件仍然能够实现。通过在N(P)中的所有节点上迭代参数，我们可以得出结论，其相应节点在N(P)中的所有行程可由单个车辆服务。因此，如果存在大小为h的路径覆盖，我们可以得出结论，T中的所有行程都可以由h个车辆服务。推论1：T中行程所需车辆的最小数量等于车辆可共享网络V =（N，E）的最小路径覆盖范围的大小。
确定任意有向网络的最小路径覆盖大小是NP-hard问题，因此对于大图而言，在计算力上是不可行的。然而，如果网络是非循环的，这意味着网络中没有形成闭环的有向路径，最优解可以在多项式时间内找到。
定义2（有向非循环网络）：
如果有向网络V=(N,E)没有有向循环，则它是非循环的，即它不包含从某个顶点n∈N开始并最终返回n的有向路径。
如上定义的所有车辆可共享网络是有向非循环网络。为证明非循环性质如何产生，我们通过反证法证明。假设一个循环路径存在于V中。为简单起见，假设路径的最小长度为2。令P={(n1,n2), (n2,n1)}为循环路径，并且令n1和n2为对应的出行分别为T1和T2。通过车辆可共享网络的定义，我们有以下一系列不等式：
3、模型运行手段
这篇论文在方法论上的主要贡献是将一个最小车辆规模问题精确地归化为汽车共享网络建模，变成一个在有向图上的最小路径覆盖问题，从而将最小车辆规模问题与丰富的应用数学和计算机科学中的图论算法领域建立起联系。
除了反映了汽车共享网络的结构属性，这层联系能够建立高效算法来实现最佳的车辆部署和调度。尽管最优化解决最小车辆规模问题需要离线数据以了解出行需求，但我们随后提出了一种近似最优的在线版本的算法，能够在只知道一小部分出行需求的情况下实时实现最佳的车辆部署与调度。
在特定的时间间隔内，例如一天，我们收集代表城市交通需求一部分的个体出行的集合T.
图二、建立车辆共享网络方式。
四、出行连接时间影响交通效率
为了避免所建网络中出现车辆连续两次出行服务之间空驶时间过长的情况，引入一个出行连接时间上界：参数δ，用以平衡车队规模和交通效率。
当δ减少到0时，每个出行需求都会被一辆专用的车辆服务。这种情景假设车辆会在乘客出行起点突然出现，然后在出行终点直接消失，此时车辆的利用率最高（每个需求都需要一辆车，每辆车都得以运营），对于交通来说是一种最优方案，但会使出行运营商承受过高的成本压力（需要过多车辆）。相反，当δ增长过大时，车队规模减少，但会出现前文讨论过的运营和交通效率问题（一些车辆空驶时间过长）。因此，参数δ的设定是一个重要的设计选择，我们把这个问题留给出行运营商、相关交通部门和政策制定者们来深入探讨。不同δ取值影响结果见图三a。本文中我们将δ设定为15min（图三b可知，δ>15min时，空驶率持续增加，但车队规模基本保持不变）。
图三、参数 δ影响分析。
a.不同相邻出行服务时间间隔上限参数 δ下的车队规模与空驶比例函数。若提高 δ，车队规模减小但是车辆空驶率上升。此处为14天数据的均值。b. δ=10min和 δ=20min下的每日车队规模变化与日出行量。
图四、最小车队规模分析。
a．日出行量和所需的最小车队规模间的相关性。不同颜色点代表了一周不同天，同一种颜色点的聚集表明以周为单位的循环出行模式（weekly patterns）。（这种模式是通过分析年度报告确定的，详见拓展数据图2）。本图显示了两变量间的相关性，然而当日出行量在350000到550000（线性插值得到，实际值未到550k）间时，这种相关性变得很弱，车队规模维持在6000辆左右（详见图a中放大窗）。
图五、2011年日出行量和车辆数细节。
该图显示了纽约市2011年每天的日出行量（蓝线）和通过该出行量计算所得的最小车队规模（绿线）。两个变量均遵循明显的以周为单位的循环模式：日出行量（蓝）从周一到周五持续增长但在周末快速下降，而工作日时服务这些出行量的最小车队规模（绿）稳定在6200辆左右，周日大幅下降至4000辆左右。日出行量变化较大，但车队规模具有一定的鲁棒性，可以处理更多的出行量而不增加额外的车辆。
图四展示了本文模型计算满足纽约市单日出租车出行需求车辆数情况。从图四a中可以看出，满足出行需求的最小车辆数与日出行量（见图四a）线性相关，此时R2为0.74（R2=1时，线性相关；R2=0时，线性无关）。然而，当出行量升至300000到550000时，两者的相关性大大减弱，R2值仅为0.18（见图四a插图），（进一步解释详见图八）。不难看出，不仅出行密度是影响车队规模的主要因素，人们出行的时空模式也会很大程度影响车队规模。图六更进一步解释了车辆利用模式。为探究该问题，我们在图七里进一步分析每日车辆使用量。
研究可以通过用每日车辆的使用时间来衡量车队规模从而确定车队规模与日出行量间的关系。我们定义了一种一天24小时不间断运营的“全职”车辆（对于需要驾驶员的车辆——智能/无人驾驶不涉及该问题，可以认为该车是以三个8h的班次运营的）。图四b显示，改用“全职”车辆（车队总运营时间）衡量其与出行量间的联系比用车队规模（车辆数）更加准确，能够将R2从0.74提高到0.91，内插图中出行量密集日的R2从0.18提高到0.7。
图六、2011年小时单位下车队规模细节。
每日各时段内，所有活跃车辆可能处于以下三种运营模式：①空车，在接乘客的路上；②空车，在接乘客地点等待乘客；③载客上路服务中。每分钟处于上述三种运营模式的车辆数服从日周期性及以周为单位的循环规律（详见图中3种颜色曲线）。路上所有车辆的车队规模有一定鲁棒性：最小车队规模下的大多数车辆全天处于活跃状态。
图七、最小车队规模下车辆层面使用情况。
a.图中采用每月的第二周相应周一~周日的数据。除2011年3月的第二个星期六数据有较大差异外，该图展现了高效率的运营模式：大多数出租车于早间早早开始运营，直到当天结束。
b．柱形高度代表了车辆总运营时间（纵轴数据值大小），柱越低，运营时间越长。周末与部分工作日的模式略有特殊：大量车辆只在较少时间内服务少数出行需求。由于接送时间和地点的分散（时空性），这种周末特殊需求需要附加车辆。
c．Q-Q图（一种统计图：比较两个变量概率分布，将其分位数放在一起比较）比较了被车辆（最小车队规模下）服务了的出行量占比和车辆使用量比例分布。车辆按总运营时间排序：运营时间越长的车辆出现在运营时间短的车辆的左边（横轴）。周中曲线代表一年中的所有周一。从周六、日图中可以看出，约5%-10%的车辆仅服务<1%的出行（通过曲线顶部尖头处可以看出）。
通过图七中对出租车使用数量的分析结果显示，5%~10%的车辆未被充分使用，仅服务了约一成的出行量。低利用率的现象多发生在周末，这很可能与额外的夜间需求（订单时空分布不均，需要附加车辆满足需求）有关。该分析结果同时表明了车队规模具有明显的以周为单位的循环规律，每年的车队规模总值相对稳定。这种稳定可以用一个简单的交通分配模型来解释，同时符合出行运营商的投资原则：针对最优车队规模进行投资，寻求稳定的年回报。同时，周末时车队规模下降意味着有机会每周来进行车辆常规维护。
图八、不同最小车队规模衡量尺度与日出行量间关系。
从上图四和图八中我们可以发现，当日出行量处于35万到55万时，最小车队规模数量仅有很小的变化。这种一定范围内的具有的车队规模的鲁棒性可以用一个简单的装箱模型来解释。假设N辆固定时空能力的车辆每天服务k个出行需求。k的取值取决于一天中给定时段内的每次出行平均时间，且严格受限于最大运营时间：24h。我们从一个基本场景开始：有Nx个出行需求（x<=k）以泊松分布随机出现。之后在某时刻添加一个出行需求，随机选出n辆车（n为模型超参数，可随机设为1或2）作为备选集。此时会有两种可能情景：①备选车辆集仍有能力服务更多出行需求，随机选取一辆车满足该出行需求；②所有车辆都没有时空能力来满足新的出行需求，则增加一辆新的车辆。重复该过程，并以这种方式建立车辆数量和出行量关系的模型。
该模型现象了一个有趣的稳定-上升模式：
对于一些中间区域，车队规模再呈现一定鲁棒性，如本文图四。这个简单的模型表明，仍有余力服务新出行需求的车辆比例依旧较高，出行量较小时，有大量车辆的时空能力未被利用。最小车队规模维持范围是由理论上车辆能够服务的最大出行量决定的。
该值取决于出行需求的时空分布，尤其是单次出行持续时间。例如，假设一天中的平均出行持续时间为10-15min，则一辆出租车可以服务3-4次出行（假设出行需求间平均间隔5min）。该情景下车辆一天活跃服务出行量上界为100次，那么6000左右辆出租车可以承担约600000次出行，图四及图八中的d图正好支持了该假设。
尽管该模型过于简单，未考虑到决定车辆可服务出行的复杂时空约束，但仍描述出了图四中的饱和情况。图九支持了车队规模受车辆现有能力影响的观点，该图通过与车辆利用率相关的指标显示，在出行量增多时，车辆利用量持续增加。出行量更高的日子，车辆使用量更高，车辆平均载客时间更长（a图），车辆在接客点等待乘客的平均时间更短
（一览众山小-可持续城市与交通译者注：此处原文有误）
（b图），车辆利用率更高。
图九、日出行量下的车辆平均利用时间（最小车队分配情景下）。
五、令人振奋的研究结果
这个团队还包括Moe Vazifeh（论文的第一作者，可感知城市实验室的前研究员组长），Giovanni Resta （CNR的信息和电信学研究员），Steven Strogatz （康奈尔大学的数学教授）。他们用了一年时间，在纽约15亿出租车出行数据库中测试了这个解决方案。
1、全局最优化
图十、车队效率对比。
如图十所示，通过上文简述的模型进行模拟分析，实验结果显示了最优状况下，出租车运营以及整体交通的效率得到了显著提升；相比现有的出租车运营系统，最小车队规模减少了40%，与此同时，该优化模式没有牺牲乘客的便利，没有延长乘客的等待时间，也没有考虑拼车状况（如其他研究）。据我们所知这样的结果从未在之前的发表中出现过，这也是本文讨论的算法的重点。
在当日的所有需求同时提交至优化系统的前提下，
由系统最优化算法进行出行配置，仅需原先60%的出租车队就可以充分满足每日的出行需求
，然而现实情况下，在按需相应（on-demand mobility service）运营出行方式下，只有小部分的出行需求是事前统计的，大部分出行需求是实时提交至系统，我们仍然可以使用改进算法来进行出行模式优化。本文提出了两种改进方式，直接算法(on-the-fly)和批次算法(batch).
在直接算法（on-the-fly）中，系统依次处理请求，每个新的出行请求发出时系统自动指派最小距离的车辆进行响应，在一定距离内进行路径优化；而批次处理（batch）则选择在一定时间间隔中批次处理请求，比如以一分钟为时间间隔，整合该时间间隔内的所有出行请求进行批次整体路径优化，如图十一模拟结果显示，通过批次路径优化的方式，
只需原有规模70%的出租车队即可满足超过90%的出行需求
，即使效率不如理想状况下的最优解高效，该算法也能显著地提升出租车系统的运营效率，提高用户满意度。
图十一、连续15日即时算法和批次算法完成的服务比率变化情况。
在我们的算法中，我们集中处理了所有的出行请求和指派命令，解决了单一出行模式、单一车队的优化问题，相比传统出租车，我们更类似于Uber,Lyft一类的网约车，我们优化算法的优势在于将出租车原本单一车辆运营分散经营的模式转化为集中处理出行需求订单同时指派车辆的模式，以更类似于网约车的单一集中系统来进行整合处理，优化出行以提高效率达到最优解。在某种程度上，我们的模型可视作对出租车问题博弈论最优解的量化分析，以达到理论演绎上得到的1/3优化；从机动车市场的角度而言，是从多终端个体独立运营转化为单一中心统筹运营的模式。即使从环境和运营效率的角度考虑，单一中心整合是出租车车队问题最优解，实际上由于多种原因，主要为了保障消费者利益，单一的出行垄断市场是难以实现的。
即便如此，该算法中补充分析也体现了在少数垄断的条件下，中心模式仍然拥有多种优势。
2、局部最优化
正如在正文中简要讨论的那样，考虑这么一种情况，即有多个出行运营商，每个出行运营商只有权访问一部分出行需求数据，并假定运营商将其车队中的车辆分配给他们有权访问的旅行需求，并且没有与其他出行运营商共享信息。但问题在于，在这些出行运营商之间缺乏信息共享的情况下，车队规模会受到多大程度的影响。这相当于从全局最优化到局部最优化，每辆车只能接收到有关临近行程的有限信息并试图最大化其车辆利用率。当出行运营商特别多时车辆利用率会受到限制，只能实现局部最优。在下文中，我们尝试使用简化模型来解决两个和三个出行运营商公平享有出行市场。
为此，我们随机抽样了每个特定时间点的行程需求数据，并将行程集划分为多个子集。对于每个行程子集，我们建立一个车辆共享网络，并按本文所述进行最小车队优化。每个优化都会为每个出行运营商带来最小的车队规模。通过比较多出行运营商情况下的车队规模总和与全局最小车队规模，我们可以发现我们与全局最优方案的差距。
图十二与图十三选取了纽约市出租车100天的样本行程数据，展示出这些样本天数的车队总和情况。为了获得对车队规模总和的较好估计，我们通过随机采样将每天的行程集划分为三个大小相同的子集。我们重复了几次随机采样，每次我们对车辆共享网络优化以找出每个子集的车队规模。将这几个子样本的平均车队规模展示出来，如图十二和图十三。如图十三所示，从垄断市场向寡头市场的转变导致运营效率下降，具体来说有两位出行运营商的寡头市场相较于垄断市场车队数量增长约4％-6％，有三位出行运营商的寡头市场相较于垄断市场车队数量增长约6%–10%。随着运营商数量的进一步增加，距垄断市场的全局最优性结果越来越远，导致了车队规模的效率降低。如果出行运营商的数量增加，即使在每个运营商试图根据其收到的出行需求信息优化其车队规模，但由于移动运营商之间缺乏沟通，车队的总规模也会继续增加。事实上两个或三个运营商公平享有出行市场的情况只会导致车队规模运营效率的小幅下降，离全局最优相差不大。
图十二、分别1,2,3家运营商在100天样本中最小车队规模变化情况
图十三、 2,3家运营商与1家运营商相比车队数量增长百分比
六、讨论
这个解决手段没有假设每个人都必须共享一段行程。反而只是简单的将出租车调度机制重组——这通过一个简单的智能手机软件就能完成。
“最小车队问题”放到今天，实际上是一种网约车集中供应模式，通过中央调度系统来提升出租车运行效率，以更高效的方式消化出行需求。反观历史，人们对汽车出行的需求从没有消停过——建设道路导致了需求膨胀，而无论是通过提高汽车的投资成本（摇号），还是运行成本（停车费上涨，限号限行等），都无法降低人们对车辆的热情。中央调度系统如今被证实可以减小交通车辆的规模。研究者们也正计划深化工作，探讨城市所需的最小停车空间数量。未来自动驾驶车辆的普及化，同样需要与中央调度系统联网，为按需出行提供最优方案。
以上的三个情景如果能够逐步实现，则会形成以中央信息系统主导调度和停车，及获取车辆行驶信息的格局，从而形成控制引导“按需出行-按需停车”一条龙模式。
“这显示出未来与出行相关的城市问题能通过更多智慧来解决，建设更多基础设施的方式将不是必需的。形象的说就是：增加硅的利用（制芯片），减少沥青的使用（筑路）。” Ratti说道。
另外，一览众山小-可持续城市与交通还为本文提供两份重要的相关参考报告。
（参考文献3、4，如需下载请后台留言索取）
点击阅读原文报名沙龙
一览众山小●为本文提供
资料
下载
索取请电邮
Daizongliu@qq.com
或微信号 SustainableCity 后台留言
1、《解决按需出行的最小车队问题》
2、《利用网络共享力量化合乘车辆的效益》
3、《基于动态出行车辆分配的按需大容量共享出行》
4、《城市共享出行的尺度规律》
资料
免费索取英文原文资料：
联系微信公众号 SustainableCity
或电邮 Daizongliu@qq.com
我们帮助
中国
可持续发展
城市规划|城市交通|非机动交通
|活力街区与公共交通|
|量化城市与大数据|
我们作为专业志愿者团体
秉承理想，
帮助中国可持续发展，
并为之贡献
? 理念与传播 ?
? 培训与教育 ?
? 实践与孵化 ?
欢迎加入我们
2014-2018 ? 转载请注明：
源自公众号“一览众山小-可持续城市与交通”
- 杨洋新杂志封面也太撩了吧
- 木村拓哉女儿光希首登中国时尚杂志，被称为“亚洲最强新人”！
- “黑名单”第四十七弹 |《财经》杂志反侵权公告
- “黑名单”第四十六弹 |《财经》杂志反侵权公告
- 媒体负面报道影响医患关系？权威杂志BMJ发文了……
- 一本情色杂志倡导的高尚生活
- NATURE重大突破：世界首例长寿基因编辑猴模型在中科院诞生
- 影响因子越高就越好？投稿杂志你得这么挑
- 【杂志专访】王戈宏：我要让年轻人住回城里
- 想轻松刷论文？这里有全年无休的 Nature、Science 中文导读