关于数据库:Paper-Time｜开放式时空大数据助力智能公交路线规划

城市化过程的放慢，带来了城市居民出行需要、城市公共交通规模的爆发式增长。如何更好地倒退与治理城市公交，实现社会和经济效益的最优化，始终是备受关注的问题。近年来大数据技术日渐成熟，其在交通畛域的利用也不断深入，如利用“时空大数据”技术帮忙公共交通进行线路优化，就是一个胜利的利用案例。

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.cityofnewyor…）等，建设好这些平台也能够进一步施展出数据的生产因素作用。

据统计，至多 60% 的开放式数据集含有地理信息，包含道路网数据、公交网数据、轨迹数据（车辆、行人）等，如时空数据平台 OpenStreetMap（https://www.openstreetmap.org/）就提供全世界的地图数据集，下图即是从 OpenStreetMap 平台下载的北京市地图数据。

下方表格来自于咱们发表于《ACM Computing Surveys》的论文《A Survey on Trajectory Data Management, Analytics, and Learning》，该表展现了几个现有的城市轨迹数据集，它们能够大抵分为三组：人、车辆（汽车、卡车、火车、公共汽车、有轨电车等）、其余（动物和飓风），大量轨迹数据集的凋谢下载为钻研提供了便当。咱们能够察看到人类衍生的轨迹数据（包含车辆）是轨迹数据的常见起源，也是目前最大的轨迹数据起源。例如，纽约市记录了从 2009 年 1 月至 2015 年 6 月间的 11 亿次集体出租车出行。

时空数据钻研的重要性

时空数据钻研在疫情防控、智能公交等民生畛域曾经有了较为成熟的利用，并日益施展关键作用。

在疫情防控畛域： 轨迹类似度可进一步使用于准确计算与病例时空随同工夫，判断感化危险，并疾速查问密切接触者；咱们也看到已研发的一些防疫手机应用程序，自动记录日常轨迹，智能映射到公共室内场合和公交班次，并可在手机端间接计算密接度，无需泄露用户隐衷。

在智能公交畛域： 评估公交网络连接度，布局新公交线路以不便换乘，已在纽约和芝加哥数据集上验证。同时，实时公交能够实现收集海量公交实时地位数据，评估公交准点率，预测达到工夫、智能布局行程安顿。

轨迹数据管理的难点

1. 数据体量大：如武汉机动车保有量已冲破 400 万，存储管理海量数据的难度也更大；
2. 差异性大：如车辆、行人、电动车等的轨迹特色不一，晋升了数据分析建模的难度；
3. 数据交融：需与路网、车道、公共场所等数据集成；
4. 查问品种多：波及时空随同、路口监控等多种场景；
5. 匹配难：类似度匹配模型复杂度高。

作者在时空数据管理畛域钻研总览

我在时空数据管理畛域的钻研次要包含三个方向：

一、推动大规模轨迹数据管理等基础理论钻研工作。 在轨迹数据预处理、存储、压缩、类似度度量、一体化索引等基础理论钻研方面提出创新性成绩；

二、钻研均以事实利用为驱动并提出关键技术解决方案，服务实在场景。 如推广轨迹数据在公共交通布局、实时交通监测、智慧游览路线布局方面等利用；

三、提倡根底钻研和原型零碎开发并重，构建并开源第一个车辆轨迹搜索引擎。 能高效反对多种查问和新鲜的轨迹度量形式，所提算法均利用于在线交互式零碎中进行展现。

时空数据钻研问题探析

接下来我会介绍时空数据钻研在理论生存中的具体利用，以纽约市公交路线从新布局为例。

公共交通是解决城市交通拥堵的无效伎俩，纽约有 56% 的人口应用公共交通出行。一方面，轨迹数据体现了新的出行需要，如为什么有人通勤时抉择打出租车而不是公交，是否存在供需不均衡的问题；另一方面，传统办法如人口普查和问卷调查无奈精确和及时地获取民众需要，利用轨迹数据布局新公交路线尤为重要。

咱们晓得，城市都会经验崛起和衰败，同样的，城市内的一个区域也会经验崛起和衰败，这一过程通常会随同着人口的大规模迁徙。此时，为过来设计的公交系统就会无奈满足最新的需要，呈现运力节约或者过载的状况。而通过时空数据分析，能够帮忙城市更正当地布局公交路线。

钻研问题 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 站路线的新公交路线，使得目标值（运力和换乘方便性）最大化。即新开通路线须要在满足公交网整体连通性的前提下，保障换乘的方便性。此时咱们也会关注到公共交通的另一个属性，即公平性：如果只谋求运力，则公交路线都会集中在人口密集区域，而市区路线的换乘会十分不便。作为数据迷信的研究者，我认为更多地关注普通人的利益是很有必要的。

一、问题定义和指标构建

咱们如何定义公交网络的连通性呢？首先，咱们能够把上图转化为连贯矩阵，并失去它的特征向量，来判断线路连贯的紧密性。此外，还要思考通行需要，即公交路线和通勤轨迹的重合度。

公交网络连通性计算：

通勤需要计算：

二、CT-Bus 问题

咱们将最佳公交路线优化问题命名为 CT-Bus：给定通勤轨迹数据和公交网络数据，布局一条至少 k 条边的新路线，使得目标值最大化。

线性组合优化指标：

咱们采纳线性组合来衡量上述两个指标，其中一个可配置的参数 w 为满足各种布局要求下的值。

三、公交网连通度掂量形式

如果大家对图论有过钻研，就会晓得“edge connectivity（边连通度）”这一概念，艰深来说，就是一个图起码要去掉多少条边，能够变成非连通图或者平庸图。那利用于公交线路中，比方一些通往市区的路边连通度就是 1，如果断开则整个网络就会不连通。

此时，咱们留神到在生物化学的蛋白质钻研畛域，有一个概念叫做 Natural connectivity（天然连通度），于是咱们将它引入到公交网络问题的钻研中，利用公交网邻接矩阵的特征值推算出 [0,1] 之间的连通度指数。能够说它是最适宜交通网络的一种属性，因为它不会因为代数连通性或边缘连通性扭转而产生激烈变动。

为了验证这一思路在实在交通网络中的枯燥性，咱们随机从芝加哥和纽约市交通网络中逐步移除现有路线，并察看到天然连通性简直线性降落，如下图所示。

办法思路总结

回顾咱们的钻研内容，首先咱们证实了 CT-Bus 问题是 NP-hard（NP：Non-deterministic Polynomial，非确定性多项式）问题。因为它是两个简单束缚优化问题（满足乘客通勤需要、最大公交网络连通性）的组合，没有近似比。

较为间接的解决方案是生成大量备选路线，并计算每个备选路线的连通性，抉择目标值最高的路线。因为 CT-Bus 的指标函数计算成本很高（连通性的计算须要计算邻接矩阵的特征值），因而咱们提出了一种通过在网络中扩大、排序和修剪候选门路的通用算法。

在改良算法的过程中，咱们采纳了预处理减速技术：先抉择一些种子门路，一直在它的两边减少边，继续预计需要，同时预计咱们新加的边或者路线的连通性。通过咱们对算法的不断改进优化，可能在保障后果准确性的同时，把计算速度从几天缩小到几十秒。

基于拓展的遍历算法

同时，在求解 CT-Bus 问题时，咱们采纳了一种基于拓展的图遍历办法。

一、初始化阶段

抉择拓展种子，按需要降序排列（从具备高需要的边开始拓展）；最短门路搜索算法连贯两个停靠站；累加该门路穿过的每条路网边的需要。

二、拓展阶段

增加相邻边作为新候选，采取广度优先搜寻；搜寻策略能够抉择全副或最佳街坊（best neighbor），后者能够无效缓解收敛问题；计算目标值，更新最佳门路，预计下限目标值。

三、查看阶段

计算候选的连通性，查看是否能进步目标值；若是，则进行几项查看，别离用于限度门路的转弯问题，以及防止一些反复拓展；通过查看后更新后果。

时空数据钻研布局公交路线成果展现

为了不便大家更直观地了解，咱们也应用可视化技术对最终布局成果进行展现。

数据集选取

数据集方面，咱们次要选取了纽约市和芝加哥市的三种数据：GTFS 公交数据、路网数据、出租车轨迹数据。

新布局路线展现与剖析

如下图所示，新布局路线用粗深红色线示意。通过算法有效性剖析，所提办法能够生成具备高目标值的无效门路，并在需要和连通性之间保持平衡；布局路线的状态在地图上也较为平滑，对于城市理论的公交布局是有参考价值。

对于纽约市，Queens 和 Brooklyn 之间须要建设更多的路线，这将进一步连贯更多通往 Staten Island 的路线；Manhattan 现有的地铁和公交系统曾经十分成熟，连通性的晋升不是很显著，不须要新布局的公交线路，而这也与纽约市正在从新设计除 Manhattan 以外的其余四个行政区的公交路线这一事实统一；不过还是倡议布局更多连贯 Manhattan 和 Staten Island 的线路，后者高度依赖公交系统，而岛上只有一条外部地铁线路；Bronx 还建设新路线来须要连贯南北，造成一个圆环来连贯 Yankee Stadium、Hunts Point Avenue 和 Kingsbridge，以显著缩小通勤者的换乘。

算法次要性能指标

咱们将算法优化前后的后果进行比拟，在工夫效率方面，下图中的 ETA 为咱们提出的数据库算法，基于预计算的估算技术（ETA-Pre）可能十分高效地找到最优路线。

纽约实时公交平台

咱们课题组近期研发的实时公交可视化交互平台（http://shengwang.site/bus/），数据也全副来源于实在的开放式数据集。将来咱们也将交融更多城市的数据集，特地是反对国内城市如武汉等。

写在最初

我认为利用公共时空数据集可无效助力智能公共交通倒退，时空数据驱动的智能路线布局通常非常复杂，但数据库技术可大幅度降低布局开销，随着更多的时空数据公开，将惠及更多民生畛域，如；实时公交轨迹数据管理和剖析、病例轨迹追踪、公交时刻表优化和达到工夫预测等。

以上为王胜老师上期直播的全副实录分享，心愿大家有所播种！