城市化进程的加快，带来了城市居民出行需求、城市公共交通规模的爆发式增长。如何更好地发展与管理城市公交，实现社会和经济效益的最优化，一直是备受关注的问题。近年来大数据技术日渐成熟，其在交通领域的应用也不断深入，如利用“时空大数据”技术帮助公共交通进行线路优化，就是一个成功的应用案例。
OceanBase Paper Time 第三期邀请到了武汉大学计算机学院副教授王胜，带来题为《开放式时空大数据助力智能公交路线规划》的分享。王胜教授从开放式时空数据的概念、研究方向、方法及研究成果的现实应用等四个方面展开，重点围绕城市开放的时空大数据，介绍了他基于开放式时空数据的公交运力估算和路线规划研究，分享了如何实现运力最大化和换乘方便两大目标，并在纽约公交网上得到验证的研究过程。本期分享的原论文《Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand》发表于 2021 SIGMOD （数据管理国际会议）。
今天为大家带来该场分享的文字版回顾，欢迎大家一起学习讨论并分享。
本文整理自直播内容以及分享嘉宾的相关论文：
感谢 OceanBase 邀请，非常荣幸能借此机会同大家分享我过去几年的研究内容。我于 2021 年在美国纽约大学结束博士后，回国入职武汉大学计算机学院担任副教授。我今天分享的内容是《开放式时空大数据助力智能公交路线规划》，包括研究背景、研究问题、研究方法、实验评估四个方面。
时空数据研究有什么用？
数据已成为新型生产要素
2021 年，国务院印发了《“十四五”数字经济发展规划》，其中指出，数据对提高生产效率的乘数作用不断凸显，成为最具时代特征的生产要素。规划中“智慧城市”也被提及五次，例如“结合新型智慧城市建设，加快城市数据融合及产业生态培育，提升城市数据运营和开发利用水平。”
举例来说，目前，国内外许多城市都建设了开放式政务数据平台，如武汉市的公共数据开放平台（https://data.wuhan.gov.cn/），纽约市的 NYC Open Data（https://opendata.cityofnewyork.us/）等，建设好这些平台也可以进一步发挥出数据的生产要素作用。
据统计，至少 60% 的开放式数据集含有地理信息，包括道路网数据、公交网数据、轨迹数据 （车辆、行人）等，如时空数据平台 OpenStreetMap（https://www.openstreetmap.org/）就提供全世界的地图数据集，下图即是从 OpenStreetMap 平台下载的北京市地图数据。
下方表格来自于我们发表于《ACM Computing Surveys》的论文《A Survey on Trajectory Data Management, Analytics, and Learning》，该表展示了几个现有的城市轨迹数据集，它们可以大致分为三组：人、车辆（汽车、卡车、火车、公共汽车、有轨电车等）、其他（动物和飓风），大量轨迹数据集的开放下载为研究提供了便利。我们可以观察到人类衍生的轨迹数据（包括车辆）是轨迹数据的常见来源，也是目前最大的轨迹数据来源。例如，纽约市记录了从 2009 年 1 月至 2015 年 6 月间的 11 亿次个人出租车出行。
时空数据研究的重要性
时空数据研究在疫情防控、智能公交等民生领域已经有了较为成熟的应用，并日益发挥关键作用。
在疫情防控领域：轨迹相似度可进一步运用于精确计算与病例时空伴随时间，判断感染风险，并快速查询密切接触者；我们也看到已研发的一些防疫手机应用程序，自动记录日常轨迹，智能映射到公共室内场所和公交班次，并可在手机端直接计算密接度，无需泄露用户隐私。
在智能公交领域：评价公交网络连接度，规划新公交线路以方便换乘，已在纽约和芝加哥数据集上验证。同时，实时公交可以实现搜集海量公交实时位置数据，评价公交准点率，预测到达时间、智能规划行程安排。
轨迹数据管理的难点
- 数据体量大：如武汉机动车保有量已突破400万，存储管理海量数据的难度也更大；
- 差异性大：如车辆、行人、电动车等的轨迹特征不一，提升了数据分析建模的难度；
- 数据融合：需与路网、车道、公共场所等数据集成；
- 查询种类多：涉及时空伴随、路口监控等多种场景；
- 匹配难：相似度匹配模型复杂度高。
作者在时空数据管理领域研究总览
我在时空数据管理领域的研究主要包括三个方向：
一、推动大规模轨迹数据管理等基础理论研究工作。在轨迹数据预处理、存储、压缩、相似度度量、一体化索引等基础理论研究方面提出创新性成果；
二、研究均以现实应用为驱动并提出关键技术解决方案，服务真实场景。如推广轨迹数据在公共交通规划、实时交通监测、智慧旅游路线规划方面等应用；
三、倡导基础研究和原型系统开发并重，构建并开源第一个车辆轨迹搜索引擎。能高效支持多种查询和新颖的轨迹度量方式，所提算法均应用于在线交互式系统中进行展示。
我们知道，城市都会经历崛起和衰落，同样的，城市内的一个区域也会经历崛起和衰落，这一过程通常会伴随着人口的大规模迁徙。此时，为过去设计的公交系统就会无法满足最新的需求，出现运力浪费或者过载的情况。而通过时空数据分析，可以帮助城市更合理地规划公交路线。
研究问题1：公交路线运力估算
对于公交路线规划，首要考虑的问题无疑是运力问题。建设一条公交线路，会有多少人乘坐，能否收回成本或者保证盈利？如何实现运力最大化，拥有尽可能多的乘客？
如下图所示，在规划公交路线时，我们需要综合考虑 Ridership（客流量）和 Coverage（覆盖范围）。如果只考虑 Ridership，则公交线路会运行于人口密集的道路，同时安排更频繁的车次，此时由于线路集中，大部分乘客需要步行更远才能到达公交车站；如果只考虑 Coverage，则公交路线会在更大区域的更多街道运行，乘客仅需步行很短的距离即可到达公交车站，但此时因为线路的分散会让车次减少，人们需要等待更久时间乘车。
因此，在规划一条新的公交路线时，我们要根据出行轨迹估算其运力，计算出多少乘客会选择其作为最近的路线出行，从而实现运力最大化。
研究问题2：如何使得新路线方便换乘
公交线路规划的另一个关键问题是换乘方便性。人们在前往目的地时，很少情况下可以通过单一线路抵达，大多数情况是需要换乘，包括换乘公交车、地铁、轮渡等。
如下图所示，Connections（换乘）和 One-Seat Rides（直达）是人们从出发抵达目的地的两种情况。Connections 情况下，公交线路更为集中和笔直，因此乘客需要额外的路程往返于车站和出发地/目的地，但等待时间会更短，整个行程将花费更短的时间；One-Seat Rides 情况下，公交路线较为迂回，乘客仅需乘坐一次即可从出发地到达目的地，但等待时间会更长，整体行程也需要更多时间。
因此，规划公交线路时也要充分考虑换乘方便性，该问题主要难点一是缺失形式化方法来定义换乘方便指数；二是如何满足运力最大化的同时实现换乘，即多目标路线优化。
我们提出了“反向 k 近邻查询”和“公交线路规划算法”两种研究方法，用于公交线路运力估算和重新规划。
反向 k 近邻查询
一、问题定义
在设计这一研究方法时，我们主要使用了两种数据：纽约出租车数据（NYC Taxi Data）和现有的公交网数据（如下图所示），研究的具体问题是：给定一条新公交路线 Q，查询其被多少条轨迹（出租车）作为最近邻。基本解决思路为：从每条轨迹找到其最近的 k 条线路，然后查看 Q 是否在其结果列表中。
该问题是我在读博时进行的研究，研究成果《Reverse k Nearest Neighbor Search over Trajectories》在 2018 年 4 月发表在《IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING》期刊上。
二、主要技术挑战和解决方案
研究这一问题主要面临两大技术挑战：一是复杂度过高；二是数据量庞大，例如纽约有800万人，2000余条公交路线。
因此，我们提出使用数据库索引技术解决技术挑战：提前预计算将相近的轨迹放到一块，实现批处理，从而避免一对一的匹配计算。同时，进一步延伸，利用该查询作为工具来规划公交线路，给定起点和终点后，准备一些 candidate（备选路线）进行公交线路运力的计算，最后通过图剪枝技术快速找到一条可最大化运力的路线。
如下图示，我们展示了 4 种路线：Original（原始路线）、Shortest（最短路线）、MaxRkNNT（吸引最多乘客的路线）、MinRkNNT（吸引最少乘客的路线），我们发现原始路线和 MaxRkNNT 路线几乎相同，区别在于 MaxRkNNT 多走了 10 米路程，但可以额外吸引 129 名乘客。
在计算公交运力的过程中我们遇到不少挑战很大的问题，我们都通过数据库查询技巧把挑战难度降低，快速解决了这些问题。
运力&换乘优化路线规划算法
在我到达纽约后，从纽约公交路线的优化工作中得到了新的启发，进一步完善了运力&换乘优化路线规划算法：数据来源除了原本的轨迹数据、公交网数据外，新增加了路网数据。
如下图所示，灰色圆圈表示路网节点，数字表示该边的需求（需要乘坐公交的人数）；黑色方块表示公交停靠点；蓝色线表示现有公交线路；红色线为出行人的轨迹数据，通过 map matching 映射到网络中。我们从该图中可以发现：出行人从 v5 路网节点到 7 号公交停靠点，中间有一段路因为公交未开通需要步行。轨迹代表了通勤需求，若其所在路径上不存在现有的公交路线，就可以是潜在的新的公交路线。
因此，我们需要规划一条至多k站路线的新公交路线，使得目标值（运力和换乘方便性）最大化。即新开通路线需要在满足公交网整体连通性的前提下，保证换乘的方便性。此时我们也会关注到公共交通的另一个属性，即公平性：如果只追求运力，则公交路线都会集中在人口密集区域，而郊区路线的换乘会非常不便。作为数据科学的研究者，我认为更多地关注普通人的利益是很有必要的。
三、公交网连通度衡量方式
如果大家对图论有过研究，就会知道“edge connectivity（边连通度）”这一概念，通俗来说，就是一个图最少要去掉多少条边，可以变成非连通图或者平凡图。那应用于公交线路中，比如一些通往郊区的路边连通度就是 1，如果断开则整个网络就会不连通。
此时，我们注意到在生物化学的蛋白质研究领域，有一个概念叫做 Natural connectivity（自然连通度），于是我们将它引入到公交网络问题的研究中，利用公交网邻接矩阵的特征值推算出[0,1]之间的连通度指数。可以说它是最适合交通网络的一种属性，因为它不会因为代数连通性或边缘连通性改变而产生剧烈变化。
为了验证这一思路在真实交通网络中的单调性，我们随机从芝加哥和纽约市交通网络中逐渐移除现有路线，并观察到自然连通性几乎线性下降，如下图所示。
方法思路总结
回顾我们的研究内容，首先我们证明了 CT-Bus 问题是 NP-hard（NP：Non-deterministic Polynomial，非确定性多项式）问题。因为它是两个复杂约束优化问题（满足乘客通勤需求、最大公交网络连通性）的组合，没有近似比。
较为直接的解决方案是生成大量备选路线，并计算每个备选路线的连通性，选择目标值最高的路线。由于 CT-Bus 的目标函数计算成本很高（连通性的计算需要计算邻接矩阵的特征值），因此我们提出了一种通过在网络中扩展、排序和修剪候选路径的通用算法。
在改进算法的过程中，我们采用了预处理加速技术：先选择一些种子路径，不断在它的两边增加边，持续估计需求，同时估计我们新加的边或者路线的连通性。经过我们对算法的不断改进优化，能够在保证结果准确性的同时，把计算速度从几天减少到几十秒。
一、初始化阶段
选择拓展种子，按需求降序排列（从具有高需求的边开始拓展）；最短路径搜索算法连接两个停靠站；累加该路径穿过的每条路网边的需求。
二、拓展阶段
添加相邻边作为新候选，采取广度优先搜索；搜索策略可以选择全部或最佳邻居（best neighbor），后者可以有效缓解收敛问题；计算目标值，更新最佳路径，估计上限目标值。
三、检查阶段
计算候选的连通性，检查是否能提高目标值；若是，则进行几项检查，分别用于限制路径的转弯问题，以及避免一些重复拓展；通过检查后更新结果。
如下图所示，新规划路线用粗深红色线表示。通过算法有效性分析，所提方法可以生成具有高目标值的有效路径，并在需求和连通性之间保持平衡；规划路线的形态在地图上也较为平滑，对于城市实际的公交规划是有参考价值。
对于纽约市，Queens 和 Brooklyn 之间需要建设更多的路线，这将进一步连接更多通往 Staten Island 的路线；Manhattan 现有的地铁和公交系统已经非常成熟，连通性的提升不是很明显，不需要新规划的公交线路，而这也与纽约市正在重新设计除 Manhattan 以外的其他四个行政区的公交路线这一事实一致；不过还是建议规划更多连接 Manhattan 和 Staten Island 的线路，后者高度依赖公交系统，而岛上只有一条内部地铁线路；Bronx 还建设新路线来需要连接南北，形成一个圆环来连接 Yankee Stadium、Hunts Point Avenue 和 Kingsbridge，以显著减少通勤者的换乘。
算法主要性能指标
我们将算法优化前后的结果进行比较，在时间效率方面，下图中的 ETA 为我们提出的数据库算法，基于预计算的估算技术（ETA-Pre）能够非常高效地找到最优路线。
我认为利用公共时空数据集可有效助力智能公共交通发展，时空数据驱动的智能路线规划通常非常复杂，但数据库技术可大幅度降低规划开销，随着更多的时空数据公开，将惠及更多民生领域，如；实时公交轨迹数据管理和分析、病例轨迹追踪、公交时刻表优化和到达时间预测等。
以上为王胜老师上期直播的全部实录分享，希望大家有所收获！
第四期 Paper Time 由蚂蚁技术研究院海贝实验室研究员、新加坡国立大学博士后徐泉清老师为大家带来 “ 一个 7.07 亿tpmC的分布式关系型数据库系统 ”的分享，本篇论文也是VLDB 2022 分布式数据库领域唯一获得"the artifact available badge"的工业论文。
