下载掌阅APP，畅读海量书库
立即打开
预计到2050年，世界70%的人口将居住在城市中。市政规划师将面临一个日益城市化和受污染的世界，各个城市的道路交通网络都承受着过度压力。为了应对这一挑战，多方人员努力改善人们的驾驶体验，提升现有出租车系统的运营水平，以及建造更有效的公共交通系统，包括公交车、地铁和共享自行车计划。以下各小节将分别回顾上述努力对应的文献。
快速驾驶路线可以节省旅行时间和能源 [68，75] 。已有大量研究来学习历史交通模式 [16，63] ，估计实时交通流量 [63] ，以及基于浮动车辆数据 [110-111] [如车辆的GPS轨迹、Wi-Fi和全球移动通信系统（GSM）信号]预测个别道路的未来交通状况 [24] 。然而，对全市交通状况进行建模和预测的研究仍然很少。
T-Drive [156-157，159] 是一个提供个性化驾驶建议的系统，它能够适应天气、交通状况和个人的驾驶习惯。这个系统的第一个版本 [159] 仅基于出租车的历史轨迹数据来建议实际最快的路径。关键点包括两部分：（1）配备GPS的出租车可以作为移动传感器，不断探测路面上的交通模式；（2）出租车司机是经验丰富的驾驶员，他们可以根据自己的知识找到真正快速的路线，这不仅包括路线的距离，还包括交通状况和发生事故的概率，意味着出租车的轨迹暗示了交通模式和人类智慧。为了应对数据稀疏性（即许多道路段不会有出租车经过），全市的交通模式被建模为一个地标图，如图2.6a所示，其中节点是出租车频繁行驶的前 k 个道路段（称为地标），每条边表示出租车在两个地标之间的通勤聚合。每条地标边的通行时间是基于出租车数据使用VE（方差和熵）聚类算法进行估计的。T-Drive使用一个两阶段路由算法，首先在地标图中搜索粗略路线（由一系列地标表示），然后将这些地标与详细路线连接起来。
T-Drive的第二版 [156-157] 挖掘历史出租车轨迹和天气记录，构建了四个地标图，分别对应不同的天气和日子，如图2.6b所示。系统还根据最近收到的出租车轨迹计算实时交通，并基于实时交通和相应的地标图预测未来交通状况。用户通过配备GPS功能的手机提交查询请求，请求包括起点 q s 、终点 q d 、出发时间 t 和自定义因子 α 。在这里， α 是一个向量，表示用户在不同地标边通常的驾驶速度。 α 最初设置为默认值，并根据用户实际驾驶的轨迹逐渐更新。T-Drive为每个用户提供了更准确的估计，并且如果一个人的驾驶习惯随时间改变，它会调整其建议。因此，该系统每驾驶三十分钟可以节省五分钟的时间。
图2.6 T-Drive：基于出租车行驶轨迹的驾驶建议（见彩插）
VTrack [129] 是一个基于Wi-Fi信号进行通行时间估计的系统，它测量并定位时间延迟。该系统使用基于隐马尔可夫模型（HMM）的地图匹配方案，通过插值稀疏数据来识别用户最有可能驾驶的道路段，随后提出了一种通行时间估计方法，将通行时间的产生归因于这些路段。实验表明，VTrack能够容忍这些位置估计中的显著噪声和中断，并成功地识别出延迟易发的路段。
Wang等人 [135] 提出了一种覆盖全市范围的实时模型，用于估计在任何给定时间城市中任何路径的通行时间，该模型基于在当前时间槽和一段时间内接收到的车辆GPS轨迹以及地图数据。图2.7展示了一个例子，根据四条轨迹（Tr 1 、Tr 2 、Tr 3 和Tr 4 ）估计路径 r 1 → r 2 → r 3 → r 4 的通行时间。解决这个问题存在三个挑战。
图2.7 基于通行时间估计的稀疏轨迹（见彩插）
第一个挑战是数据稀疏性，也就是说，许多道路段（例如 r 4 ）可能在当前时间槽内没有配备GPS的车辆经过。在大多数情况下，我们也找不到一个能完全穿过查询路径（即 r 1 → r 2 → r 3 → r 4 ）的轨迹。
第二个挑战是，对于具有轨迹的路径片段（例如， r 1 → r 2 → r 3 ），有多种使用（或组合）轨迹（Tr 1 、Tr 2 和Tr 3 ）来估计相应通行时间的方法。例如，我们可以分别计算 r 1 、 r 2 和 r 3 的通行时间，然后将相应的时间成本相加来估计 r 1 → r 2 → r 3 的通行时间。我们也可以根据Tr 1 和Tr 2 计算 r 1 → r 2 的通行时间，根据Tr 1 、Tr 2 和Tr 3 计算 r 3 的通行时间，然后将这两部分的通行时间结合起来估计 r 1 → r 2 → r 3 的通行时间。找到一个最优的组合是一个具有挑战性的问题，需要在路径的长度和穿越路径的轨迹数量（即支持度）之间进行权衡。理想的情况是使用许多像Tr 2 这样覆盖整个路径的轨迹来估计 r 1 → r 2 → r 3 的通行时间。这样的轨迹反映了整个路径的交通状况，包括交叉口、交通信号灯和转向，因此无须单独和显式地建模这些复杂因素。
然而，随着路径长度的增加，穿越该路径的轨迹数量会减少。因此，由少数驾驶员生成的通行时间的置信度也会降低。例如，Tr 2 可能是由一个不常见的驾驶员在异常情况下生成的，比如行人过街。此外，若使用较短子路径的连接，则每个子路径上可以有更多轨迹（即每个子路径的通行时间有较高的置信度）。但这会导致更多的片段，这些片段之间上述复杂的因素难以建模。连接包含的片段越多，路径通行时间可能涉及的不准确度就越高。
第三个挑战是，我们需要即时回答用户可能在城市任何地方提出的查询。这需要一个高效、可扩展且有效的解决方案，以实现全市范围的实时通行时间估计。
为了应对这些挑战，Wang等人使用三维张量对不同驾驶员在不同道路段和不同时间槽的通行时间进行建模。结合从轨迹和地图数据中学习的地理空间、时间和历史背景，他们通过一种可感知背景的张量分解方法填补了张量的缺失值。然后，他们设计并证明了一个目标函数来建模上述权衡，通过动态规划解决方案得到最优的轨迹连接。此外，他们提出使用频繁出现的轨迹模式（从历史轨迹中挖掘）来缩小连接的候选者，并使用基于后缀树的索引来管理当前时间槽中接收到的轨迹。大量实验使用由超过32000辆出租车在两个月内生成的GPS轨迹，对所提出的解决方案进行了评估。结果表明，该方法在效率、有效性和可扩展性方面超过了基线方法，例如简单地将每个道路段的旅行时间相加。
出租车是公共和私人交通之间的重要通勤方式，提供几乎门到门的通行服务。在像纽约和北京这样的大城市中，人们通常需要等待一段时间才能乘坐空出租车，出租车司机则渴望找到乘客。有效地将乘客与空出租车联系起来对于减少人们的等待时间、增加出租车司机的利润以及减少不必要的交通和能源消耗非常重要。为了解决这个问题，已经进行了三类研究。
这类系统 [10，80，123，145] 接受用户的预订请求，并将出租车分配给用户。大多数系统要求人们提前预订出租车，从而降低了出租车服务的灵活性。一些实时调度系统，如Uber，根据距离和时间的最近邻原则在用户周围搜索车辆。系统面临的主要挑战是寻找出租车时出租车移动的不确定性 [112，145] 。如图2.8a所示，如果我们可以确定出租车 K 正在向用户移动，而其他车辆正在离开空间范围，那么出租车 K 可能比 X 、 Y 或 Z 更适合接载用户。在估计接载用户的通行时间时，也应考虑路线上的交通状况 [46] 。
图2.8 改善出租车服务的三类系统
这类系统从推荐的角度解决前述问题 [140，163] 。Ge等人 [55] 开发了一个移动推荐系统，可以为出租车司机推荐一系列接客点，或者为车辆推荐一系列潜在的停车位置。该系统的目标是最大化商业成功概率并减少能源消耗。
T-Finder [160，163] 为出租车司机提供了一些地点及到达这些地点的路线，这样更有可能让他们快速接到乘客（沿着路线或在这些地点），并最大化下一次行程的利润。T-Finder还向人们推荐一些地点（步行距离内），在那里他们可以轻松找到空出租车。如图2.8b所示，不同道路段上找到空出租车的概率用不同颜色表示。根据出租车的GPS轨迹检测出出租车的停车地点，并估计未来半小时内将有多少出租车到达。这类系统面临的主要挑战是数据稀疏性问题，例如在没有足够数据的情况下计算在道路段上找到空出租车的概率。
拼车对于在节约能源和缓解交通拥堵的同时满足人们的通勤需求非常重要。Furuhata等人 [50] 总结了拼车服务的三个主要挑战：设计吸引人的定价和激励机制、适当的行程安排，以及在使用在线系统的人之间建立信任。拼车服务可以分为两种类型： 静态 拼车和 动态 拼车。
· 静态拼车 静态拼车，通常称为拼车，已经在运筹学中被研究多年。静态拼车要求乘客在行程前用身份信息注册行程。给定一小群人，研究人员能够使用线性规划技术 [11，22] 来优化静态拼车。
· 动态拼车 与静态拼车中行程请求是提前已知的不同，动态拼车更具挑战性，因为行程请求是实时生成的，而且车辆的路线持续变化。Agatz等人 [3] 回顾了动态拼车系统的优化挑战。作为一种动态拼车类型，实时出租车共享更加具有挑战性，因为出租车的数量和行程请求远远超过一般的拼车服务。此外，还有其他需要考虑的约束，比如金钱方面的约束。如图2.8c所示，在出租车共享服务中，一辆出租车被安排依次接上 u 1 和 u 2 ，放下 u 1 ，接上 u 3 ，然后放下 u 2 和 u 3 ，其中“+”表示接客，“-”表示送客。
出租车共享问题可以看作一般性按需出行问题（Dial-a-Ride Problem，DARP）的一个特例。DARP起源于各种交通场景并已得到研究，特别是在货物运输 [42] 与为残疾人和老年人提供的辅助交通场景中 [15] 。关于DARP的现有工作主要集中在静态DARP上，其中所有客户的行程请求都是提前已知的。由于一般的DARP是NP困难的，因此只有小规模实例（涉及几辆车和几十个行程请求）才能得到最优解（通常通过使用整数规划技术 [34，69] ）。
大型静态DARP实例通常使用两阶段调度策略 [9，35，36，141] 并结合启发式方法来解决。具体来说，第一阶段将行程请求分割成一些组，并为每个组计算一个初始的送客安排。在第二阶段，交换不同组之间的行程请求，旨在找到新的调度方案以优化预定义的目标函数。然而，两阶段策略对于实时出租车共享并不可行。如果应用该策略，云服务将不会立即响应新的请求，它需要等待更多的请求以使第二阶段成为可能，这会延长请求的响应时间。此外，第二阶段的繁重计算负载将进一步增加响应时间，导致许多请求无法得到满足。
· 实时拼车 一些最近的研究努力探讨了实时出租车共享问题。早期的研究，如参考文献 [22，41，56，95] ，没有考虑拼车中时间和金钱的约束。T-Share [96-97] 是一个大规模的动态出租车共享系统，它接收乘客通过智能手机发送的实时行程请求，并调度出租车通过拼车来接乘客，同时受到时间、容量和金钱的约束。T-Share维护一个时空索引，用于存储每辆出租车的状态，包括当前位置、车上乘客数量以及计划的道路来送达这些乘客。当接收到行程请求时，T-Share首先在索引中搜索一组候选出租车，这些出租车可能在一些时间约束方面满足用户的要求。然后提出一个调度算法，将查询的行程插入每个候选出租车的现有行程中，找到增加行程距离最小的满足查询要求的出租车。
该系统创造了一个三赢的局面，带来了显著的社会和环境效益。根据一项基于北京3万辆出租车行驶轨迹的模拟，与传统的非拼车相比，这项技术每年能在北京节省1.2亿升汽油，这足以支持100万辆车行驶1.5个月，节省1.5亿美元，并减少2460万吨二氧化碳排放。此外，乘客的出租车费用节省了7%，且有高出300%的机会得到服务，而出租车司机的收入增加了10%。
实现这样的出租车共享系统面临两个挑战。一个是建模出租车行程中的时间、容量和金钱约束。另一个是由于乘客和出租车的动态性和大规模造成的沉重计算负载，需要高效的搜索和调度算法。
Santi等人 [124] 引入了共享网络的概念，将共享建模为乘客不便的集体效益函数。他们将这个框架应用于纽约市数百万次出租车行程的数据集，结果显示在相对较低的乘客不适水平下，累计行程长度可以减少40%或更多。还有一个研究分支在进行拼车时考虑用户隐私 [45，58] 和用户社会背景 [83] 。
公共交通系统，结合一体化的票务管理和先进的旅客信息系统，被视为改善移动性管理的关键推动因素。
为了吸引更多乘客，公交车服务不仅需要更频繁，还需要更可靠。Watkins等人 [136] 研究了将实时公交车到达信息直接发送到乘客手机上的影响，发现这不仅减少了已经在公交车站的乘客的感知等待时间，也减少了使用此类信息规划旅程的客户的实际等待时间。换句话说，移动实时信息能够通过在乘客到达站点之前提供信息来改善公共交通乘客的体验。
在公交车本身没有部署GPS接收器的情况下，已有其他解决方案以更便宜和侵入性更小的方式收集相同的信息。Zimmerman等人 [200] 首次开发、部署并评估了一个名为Tiramisu的系统，通勤者在其中分享从他们手机的GPS接收器上收集到的GPS轨迹，然后Tiramisu处理传入的轨迹并为公交车生成实时到达时间预测。由于GPS轨迹可能是不同交通方式的混合，例如先乘坐公交车然后步行，Zheng等人 [177，181，183] 提出了一种方法来推断轨迹每个部分中用户的交通方式（包括驾驶、步行、骑自行车和乘坐公交车）。对轨迹按照交通方式分类后，就可以更准确地估计公交车通行时间或驾驶时间预测。
随着不断地城市化，城市的公交服务必须随着时间的推移调整路线，以满足市民的出行需求。然而，公交线路的更新速度远慢于市民需求的变化速度。Bastani等人 [14] 提出了一种以数据为中心的方法来解决这个问题：他们开发了一种新的称为flexi的小型交通系统，通过分析大量出租车轨迹中的乘客出行数据，可以根据实际需求灵活地推导出路线。
同样地，Berlingerio等人 [18] 分析了阿比让的匿名化和聚合后的通话详细记录（CDR），旨在使用手机数据来指导该城市公共交通网络的规划。在这种情况下，西方国家普遍存在的资源密集型交通规划过程是负担不起的，利用手机数据来进行交通分析和优化对发展中国家来说是一个新的前沿，在这些国家，手机的使用很普遍，因此可以轻松挖掘匿名化的流量数据。
Chen等人 [28] 旨在利用出租车GPS轨迹规划夜间公交线路。他们提出了一个两阶段的方案来规划双向夜间公交线路。在第一阶段，将出租车乘客的上下车点聚集成一定大小的组，在每组中选择一个候选公交站点。在第二阶段，给定公交路线的起点、终点、候选公交站点以及公交运营时间限制，构建并迭代修剪公交路线图。最后，在给定条件下，选择乘客数量最多的最佳双向公交路线。
自动收费（AFC）系统在世界许多大城市中广泛采用，例如伦敦的Oyster卡、西雅图的Orca卡、北京的一卡通、香港的八达通等。除了简化城市地铁网络列车服务的接入外，这些智能卡在乘客每次乘车都会创建一个数字记录，可以追溯到个别旅客。挖掘旅客进出站时创建的行程数据可以深入了解旅客本身，包括他们的隐含偏好、乘车时间以及通勤习惯。
Lathia等人 [78] 挖掘了AFC数据，旨在构建更准确的旅行路线规划器。他们使用了从伦敦地铁系统收集的数据，该系统实施了基于RFID的电子票务，即无接触式智能卡（Oyster卡）。与某些AFC系统不同，Oyster卡必须在进出站时使用。对反映伦敦地铁使用情况的两个大型数据集进行的深入分析表明，乘客之间存在显著差异。基于这些洞察，他们自动从AFC数据中提取了特征，这些特征隐式地捕捉了关于用户对行程的熟悉程度、用户与其他乘客的相似性以及用户的行程上下文的信息。最后，他们使用这些特征开发了个性化的通行工具，其目标可以形式化为预测问题：（1）预测任何起点和终点之间的个性化行程时间，为用户准确地估计换乘时间；（2）根据每个乘客过去的行程数据对他们接收特定车站警报通知的兴趣进行预测及排名。
在后续工作中，Ceapa等人 [25] 对同一历史Oyster卡追踪数据进行了时空分析，发现拥挤在工作周内是一个高度规律的现象，高峰期发生在相当短的时间间隔内。他们继续构建拥挤水平预测器，这些预测器随后可以整合到乘客信息系统中，为乘客提供更个性化和高质量的规划服务。
Xue等人 [144] 试图根据智能卡中的行程数据在地铁系统中区分旅游者和普通通勤者。此外，Wu等人 [139] 进一步从智能卡数据中提取了每个旅游者的行程轨迹。这些轨迹暗示了旅游者的旅行模式和个性化兴趣，使得智能旅行推荐成为可能。
随着世界人口的增长，越来越多的人居住在城市中，设计、维护和推广可持续的城市交通模式变得至关重要。自行车共享计划 [125] 就是这样一个例子，它们在世界各大都市的普及清楚地表明了一种信念，即提供便捷的健康（且快速）的交通方式将引导城市摆脱目前面临的拥堵和污染困扰。共享自行车通常有详细的移动记录（从哪里/何时取车到哪里/何时还车），这使得研究人员能够分析这些数字痕迹来帮助终端用户，他们可能从理解和预测系统将如何使用中受益，进而规划自己的行程；帮助交通运营商，他们可能从更准确的自行车流量模型中受益，进而在一天中适当地平衡各个车站的负载；帮助城市规划者，他们可以在设计社会空间和政策干预措施时利用流量数据。
自行车共享系统的规划通常包括三个步骤：可行性研究、详细设计和商业计划 [54] 。Dell'Olio等人 [38] 进行了一项可行性研究，估计市民对自行车共享的需求以及支付使用该系统的意愿。为了建立一个新的系统，随后提出了一个位置模型来估计自行车共享站点的最优位置。Lin等人 [87] 提出了一种系统化的方法来估计所需自行车站点的数量及位置。他们还建议在自行车站点之间建设路径，并为给定起点和终点的用户推荐一条特定的路径。
Bao等人 [12] 建议在无站点自行车共享系统中，根据大量用户的骑行轨迹进行自行车道规划，同时考虑以下三个约束条件。第一，政府方面存在预算约束，而当前道路网络中存在空间约束。也就是说，不能在每一段道路上都建造自行车道。第二，可服务骑行者的数量与每个骑行者连续骑行长度之间存在权衡。若想尽可能地为单个骑行者提供服务，就可能无法同时服务尽可能多的人。第三，考虑到骑行体验，我们希望规划的自行车道能够局部（在某些区域）连接，而不是在城市不同部分零散分布。当然，我们也不能要求整个城市的所有自行车道都连接。因此，一个更合理的设定是在 k 个区域中建造总长度小于 x 千米（即预算）的自行车道，每个区域都有一个局部连接的自行车网络。鉴于这三个约束条件，这个问题变得NP困难。使用贪心扩张策略和目标函数，可以在合理的时间间隔内找到近优解。
Chen等人 [29] 采用回归和排序方法预测城市不同地点的潜在自行车需求。此外，他们提出了一种半监督特征选择方法，用于从异构的城市数据集中选择特征。García-Palomares等人 [53] 估计了潜在自行车需求的空间分布，根据位置分配模型确定站点的位置和容量。目前关于商业计划的研究非常罕见，主要集中在客户收费和运营成本（包括系统维护、重新分配、劳动报酬等 [54] ）之间的权衡上。
Froehlich等人 [46] 是最早采用以数据为中心的方法研究共享自行车系统的学者之一，他们应用了一系列数据挖掘技术来揭示城市数据中的时空趋势。他们对巴塞罗那Bicing系统（西班牙）13周的数据进行了深入分析，清晰地展示了一天中的时间、地理位置（特别是城市地理区域内的车站集群）与使用之间的关系。
Kaltenbrunner等人 [74] 对巴塞罗那的自行车共享系统进行了类似研究，而Borgnat等人 [19] 在法国里昂也进行了研究。在这些研究中，作者们关注自行车车站数据的时空特性，以训练和测试分类器，预测每个车站的状态（自行车的可用性）。Nair等人 [104] 分析了法国巴黎Vélib'的数据，将使用情况与火车站的接近度相关联，揭示了自行车使用与多模式旅行之间的关系，从而为车站布局政策提供了关键洞察。Lathia等人 [79] 分析了伦敦自行车租赁计划在两个不同的三个月期间的情况，得出了关于访问政策变化如何影响整个城市的自行车使用的定量证据。
受到多种复杂因素，如事件、天气以及附近车站的自行车需求等的影响，单个车站（例如图2.9a中的 S 1 和 S 2 ）的自行车使用量通常较小，并且随时间几乎随机波动（见图2.9b和图2.9c）。因此，准确预测单个车站层面的自行车使用量非常困难。
为了解决这个问题，Li等人 [86] 提出了一种二分聚类算法，根据自行车站的地理位置和自行车使用模式，将自行车站聚类成不同的组（例如，图2.9a中的 C 1 、 C 2 和 C 3 ）。像 C 1 这样的集群中的自行车使用量变得相当稳定，显示出一定程度的周期性（见图2.9d）。城市中将租出的自行车总数由梯度提升回归树（GBRT）预测，如图2.9e所示。然后，提出了一种基于多相似性的推理模型，用来预测跨集群的租车比例和集群间换乘，如图2.9f所示，根据这个模型可以轻松推断出从（向）每个集群租用（归还）的自行车数量。这个模型分别在纽约市和华盛顿特区的自行车共享系统中受到了评估，结果显示其性能优于基线方法。
图2.9 共享自行车系统中的交通预测（见彩插）
在Li和Zheng的研究 [86] 之后，Yang等人 [147] 提出了一种时空自行车移动模型和交通预测机制，用于预测每个车站在半小时内的自行车使用情况。对所提出的系统基于杭州市的自行车共享数据进行了评估，该市拥有超过2800个车站。
由于自行车使用的空间和时间分布不均，在不同车站之间重新分配自行车是必要的，以满足客户的自行车需求。目前，运营商通常通过监控每个车站的实时自行车使用情况，派遣卡车在不同车站之间重新分配自行车。一系列研究（例如参考文献 [17，27，33，91] ）将这个问题表述为受约束的优化问题，设计基于卡车容量和每个车站的不平衡分布的卡车重新分配路线。值得注意的是，Liu等人 [91] 提出了一种方法，将车站聚类成组，然后设计路线以最小化卡车在集群中的总行驶距离，使用混合整数非线性编程。