接驳车：利用超大规模城市基础设施数据支持最后一公里交通

摘要

本文提出了一种公共交通服务接驳车以解决最后一公里问题，i.e.，乘客的目的地超出公共交通站点的步行距离。接驳车利用基于拼车的车辆（e.g.,小型巴士）将乘客从现有的交通站点运送至更靠近其目的地的选定站点。我们通过利用极端规模的城市基础设施数据来推断接驳车设计所需的实时乘客需求（e.g.,出站站点和时间），这些基础设施包括中国城市深圳的一千万部手机、2.7万辆车辆以及用于1600万张智能卡的1.7万台智能卡读卡器。我们将这些大量设备视为普适传感器，挖掘在线和离线数据以支持两端接驳车服务：后端feeder服务器用于计算服务时刻表；车辆前端定制的feeder设备用于实时时刻表下载。评估结果显示，与真实情况相比，接驳车平均将最后一公里距离减少了68%，出行时间减少了52%。

分类与主题描述符

H.4[信息系统应用]:杂项通用术语
算法、模型、实验、应用

关键词

最后一公里公共交通、城市基础设施

1 引言

公共交通对减少出行延误和燃油消耗具有显著作用[9], 例如，2013年，美国的公共交通减少了8.65亿小时的出行延误和4.5亿加仑的燃油消耗，节省了1420亿美元的拥堵成本[4]。然而，公共交通（例如火车或地铁）通常平均每隔一英里才设一站，以保持较高的运行速度，这意味着大多数城市区域距离公共交通站点超出了便捷的步行距离，如我们在第2节的大规模实证分析所示。这一问题被称为“最后一公里问题”，是提高公共交通利用率的关键障碍[3]。

本文提出了一种名为接驳车（Feeder）的实时公共交通服务，该服务利用基于拼车的车辆（例如小型巴士）将乘客从其出站的交通站点运送至称为服务站点的附近下车地点，从而减少前往目的地的步行距离。尽管接驳车在概念上适用于所有公共交通系统，但我们主要针对地铁和铁路网络进行设计，因为在这些系统中最后一公里问题更为严重。我们设想接驳车由城市交通管理部门运营，并具备以下显著特点：与自行车系统不同，接驳车仅使用灵活车辆，无需为固定停靠基础设施支付高额成本，也无需额外 effort 来搬运或停放自行车；与出租车不同，接驳车乘客只需支付更低的统一票价，且由于大量同乘乘客的存在，出行更加环保；与常规公交服务不同，接驳车专为最后一公里行程设计，采用从高需求车站出发的环线路线，具有动态发车时间和数据驱动的站点。

在接驳车系统中，乘客主要经历三个阶段：（i）等待feeder车辆发车；（ii）乘坐车辆到达服务站点；（iii）步行前往“最后一公里”目的地。对乘客而言，由于最后一公里行程的乘车时间较短，等待通常比乘车更难以忍受；步行所需付出的努力也远大于乘车。因此，接驳车系统有两个主要目标，以提升乘客在等待和步行方面的体验。（i）最小化乘客等待时间：如果乘客能够提供何时何地退出上游交通的信息（例如地铁站的出站时间），则可通过优化车辆发车时间轻松实现该目标。然而在现实中，乘客通常无法提前知晓未来的出站时间。（ii）最小化乘客步行距离：如果乘客愿意提供细粒度目的地（例如家庭住址），也可通过优化服务站点位置自然实现该目标。但乘客可能因额外操作或隐私顾虑而不愿提供此类信息。因此，我们面临一个关键的设计挑战：如何在无需乘客主动提供信息的情况下，推断出详细的乘客最后一公里出行需求（即出站站点、出站时间以及细粒度目的地），以支持接驳车系统的优化。

为了解决这一挑战，我们利用大规模城市基础设施来推断最后一公里交通需求，且对乘客完全透明。具体而言，我们利用现有基础设施中生成乘客位置数据的各种设备（例如手机和智能卡读卡器），以推断接驳车所需的乘客实时出站时间、车站以及目的地。因此，我们的接驳服务的关键创新在于：它是一种完全透明、自动且数据驱动的解决方案，既无需为部署临时需求采集系统产生边际成本，也无需乘客端额外付出任何努力。

从概念上讲，我们的核心方法提供了一种利用现有城市基础设施中的异构数据来提高城市效率的新可能性，与以往单一且封闭的临时系统不同。作为一项实际应用，我们通过整合中国最拥挤的城市深圳的四个基础设施的流数据来实现这一方法：（i）拥有1040万用户的蜂窝网络；（ii）1.4万辆出租车网络；（iii）1.3万辆公共汽车网络；以及（iv）一个服务于公共交通网络（即地铁和公共汽车）的自动收费系统，该系统包含1600万张智能卡。我们建立了对上述数据源的近实时访问，以支持在线分析。此外，我们存储了4亿条手机记录、320亿条GPS记录和60亿条智能卡记录，用于离线分析。本文的主要贡献如下：

• 我们利用多种基础设施实时推断乘客的末端出行需求。据我们所知，所使用的数据在城市研究方面迄今达到了最高标准，体现在两个方面：（i）数据最完整，包含同一城市的蜂窝网络、出租车、公共汽车和地铁数据；（ii）乘客覆盖率最大（即覆盖深圳1100万常住居民中的95%）。样本数据见[2]。
• 我们首次通过双端解决方案设计了一种针对最后一公里问题的实时数据驱动服务接驳车。在后端，我们提出并实现了一个云服务器（称为feeder服务器），该服务器基于集成的异构数据提供在线数据融合，用于两个关键组件：（i）发车时间计算，通过简单而高效的智能卡数据处理来最小化等待时间；（ii）服务站点选择，基于手机和出租车数据来最小化最后一公里步行距离。在前端，我们定制并部署了一款硬件设备（称为feeder设备）作为车载设备，用于实时从feeder服务器下载发车时间并向其上传状态。Feeder涵盖了数据驱动的应用设计的整个生命周期，从硬件设计、数据收集、清洗、离线分析、在线处理、实际应用到实地评估。
• 我们在深圳实施接驳车项目，开展实地研究以测试其实际性能。我们在塘朗站租用了3辆安装了我们硬件的汽车，在30天内每天早晨从车站接载12名乘客前往他们的工作场所。
• 我们通过使用4 TB深圳数据进行全面评估来测试接驳车。结果表明，与真实情况相比，接驳车将最后一公里距离减少了68%，行程时间减少了52%。

本文组织如下：第2节阐述我们的动机；第3节提供概述；第4节描述前端设备；第5、6和7节介绍后端服务器；第8和9节通过真实测试和大规模评估验证接驳车系统；第10节讨论实际问题，第11和12节分别介绍相关工作和结论。

2 最后一公里公共交通的动机

为了证明我们的研究动机，我们通过回答两个问题来探讨最后一公里行程的严重性和普遍性：基于我们收集的数据集，一次典型的最后一公里行程有多长，以及在所有行程中最后一公里行程的发生频率如何。数据的详细信息见第5节。

在图1中，我们展示了深圳兴东地铁站与推断出的乘客目的地之间的最后一公里行程长度，这些目的地比其他站点更靠近兴东站。平均长度如图2所示。平均距离1.4公里长于乘客愿意步行的距离[8], i.e.，400至800米。

在图3中，我们绘制了所有推断出的目的地到其最近车站的距离比例，i.e.，最后一公里行程。在对数‐对数尺度上，一个点，e.g., (1.6 km, 0.3%)，表示长度从1.59公里到1.6公里的最后一公里行程占我们研究的所有最后一公里行程的0.3%。分布的第一部分遵循均匀分布（i.e.，水平线），第二部分遵循幂律分布（i.e.，长尾）。有趣的是，边界大约在1.6公里处。这表明最后一公里行程的长度在一英里范围内呈均匀分布，而在此范围之外，行程越长，发生的频率越低。因此，我们确认了一英里范围内的行程具有显著的重要性。

我们研究了所有行程中最后一公里行程的频率。由于最后一公里行程通常通过步行完成，因此更有可能被手机数据捕捉到，而不是交通数据（包括出租车、公共汽车和地铁）。在图4中，我们研究了手机数据和交通数据捕捉到的行程长度的累积分布函数。我们发现，63%由手机数据捕捉到的行程短于1.6公里，而仅有12%由交通数据捕捉到的行程短于1.6公里（其中大部分为出租车行程）。由于手机的普及，手机数据捕捉到的行程可作为所有行程的代表，因此我们通过显示这些短行程（即短于1.6公里的行程）在所有行程中高达63%的频率，证实了最后一公里行程的普遍性。我们还验证了乘客通常不会使用现有公共交通进行最后一公里行程，因为这类行程仅占所有公共交通行程的12%。

3 接驳服务概述

我们首先基于图5介绍一种接驳服务的运营场景。在没有接驳服务的情况下，乘客会（i）在进站车站进入公共交通系统，（ii）在出站车站离开公共交通系统，然后（iii）步行前往其最终目的地。因此，最后一段步行距离是从出站车站到最终目的地的距离。

在本研究中，我们设想每个主要交通站点都设有一个接驳终点站，接驳服务在该终点站独立运营。因此，通过接驳车，乘客可以：（i）在其出站站点（即接驳服务的终点站）登上feeder车辆；（ii）根据最优计算得出的发车时间，在终点站等待该feeder车辆出发，该发车时间基于推断出的乘客出站站点和时间确定；（iii）在其中一个服务站点下车，这些服务站点由接驳车根据推断出的细粒度目的地进行最优选择；（iv）步行至最终目的地。因此，通过接驳车服务，步行距离被缩短为从接驳服务站点到目的地的距离。

根据上述场景，接驳服务面临的两个关键设计挑战是：（i）如何推断公共交通乘客的出站站点和出站时间，以优化车辆发车时间；（ii）如何推断细粒度目的地，以优化服务站点位置。这些挑战将在以下框架中得到解决，该框架包含三个关键组成部分，如图6所示。

城市基础设施。它们包括蜂窝网络、出租车、公共汽车和地铁网络，在我们的接驳车设计中发挥着重要作用。我们与多家服务提供商和政府机构合作，建立从基础设施数据源到feeder服务器的实时访问。因此，我们能够为不同类别的乘客（例如手机、出租车、公共汽车和地铁用户）提供关于城市区域中几乎所有居民的最后一公里出行需求动态的完整呈现。

后端feeder服务器。接驳车服务器位于调度中心，用于接收和处理来自城市基础设施的实时数据。其功能包括（i）数据管理（在第5节中介绍）：整合异构数据（即手机、出租车、公共汽车和智能卡数据），用于实时挖掘最后一公里出行需求，即乘客出站站点和时间以及目的地；（ii）出发时间计算（在第6节中介绍）：基于挖掘出的乘客出站站点和时间，在线计算有效的发车时间，以最小化乘客等待时间；（iii）站点位置选择（在第7节中介绍）：基于挖掘出的目的地，离线选择高效的站点，以最小化最后一公里步行距离。

前端feeder设备。feeder设备是安装在feeder车辆上的定制设备，用于感知并上传每辆feeder车辆的物理和逻辑状态（例如，位置和车载乘客数量），以及从feeder服务器下载发车时间和站点位置。这些功能由feeder车辆的三个子系统完成，详见第4节介绍。

4 feeder设备设计

在我们的项目[17],中，我们开发了一个前端数据传输原型，以支持接驳车的功能。图7展示了feeder设备的实际部署情况，包括三个子系统：（i）带有GPS模块、CDMA 1X模块和紧急按钮的外部设备系统；（ii）带有摄像头、连接到显示屏的麦克风以及一个 ± 2g三轴加速度传感器的传感系统；（iii）带有TPS54160电源模块和STM32F103 CPU模块的中央控制系统。基于这些子系统，我们对接驳车设备的能力讨论如下。

通过feeder设备，feeder服务器将全面了解接驳车辆的物理状态，e.g.，位置。因此，在此设计中，每辆接驳车定期感知并上传其物理状态至feeder服务器。逻辑状态，i.e.，车载乘客数量，也对接驳服务很重要，因为它会影响发车时间。在这项工作中，我们设想司机或收费设备将跟踪车载乘客数量，从而更改逻辑状态以通知feeder服务器。

feeder设备应具备高效的通信模块，以实现与feeder服务器之间的上传和下载。在现有的大多数车载网络（e.g.，深圳出租车网络）中，车辆与调度中心之间的通信通常使用GPRS。但在我们的接驳服务中，必须及时将发车时间和站点发送给feeder车辆，同时车辆状态也需要及时上传至feeder服务器。因此，我们采用CDMA 1X模块，利用独立信道替代GPRS，以获得更好的性能。

综上所述，所提出的feeder设备能够感知详细的车辆状态，并与后端feeder服务器高效通信，从而为接驳服务提供全面的前端支持。

5 接驳服务器：数据管理

在本节中，我们首先在第5.1节介绍数据输入，然后在第5.2节讨论数据清洗，最后在第5.3节描述数据融合。

5.1 数据输入

我们一直与深圳服务提供商和政府机构合作，以获取基础设施的访问权限。从概念上讲，在此参考实现版本中，我们使用四种设备作为传感器来感知现实世界中的乘客需求。

• 手机作为传感器 基于通话详单记录来检测手机用户在基站级别的位置。
• 出租车作为传感器 用于根据出租车状态（即，GPS和载客状态）检测出租车乘客的位置。通过出租车数据获得的位置比手机数据具有更高的空间准确性，因此提供了互补的视角，因为出租车下车地点通常是乘客想要下车的位置。
• 公交车作为传感器 通过交叉核对用于支付车费的车载智能卡读卡器的数据，来检测公共汽车乘客的位置。
• 智能卡读卡器作为传感器 用于检测乘客支付公共汽车和地铁票价所使用的总共1600万张智能卡。这些读卡器传感器平均每天捕捉1000万人次的出行和600万名乘客。具体而言，有两种类型的读卡器传感器：（i）安装在1.3万辆公共汽车上的共计14,270个车载移动读卡传感器，每小时捕捉16.8万名公共汽车乘客；（ii）分布在127个地铁站的共计2,570个固定读卡传感器，每小时捕捉6万名地铁乘客。

我们建立了一个安全可靠的传输机制，通过有线连接将深圳市交通委员会和服务提供商收集的上述传感器数据传输至我们的服务器，且不影响原始数据源。由于这些数据已被用于协助服务提供商在运营其服务时，我们的大规模传感器数据收集产生的边际成本极低。

为了实现全面的离线分析，我们已存储了大量如图8所示的流数据。

如此大量的数据需要在高效存储和管理方面投入大量努力。为此，我们在一个由11个节点组成的集群上使用了34TB Hadoop分布式文件系统（HDFS），每个节点配备32核和32GB内存。在日常管理中，我们使用了多种基于MapReduce的工具，例如Pig和Hive。

5.2 数据清洗

由于我们的数据量极大，我们发现了三种主要的错误数据。（i）具有逻辑错误的数据：例如，GPS坐标显示某车辆远离其之前的位置。此类具有逻辑错误的数据将在我们分析数据时被检测到。为了检测这些错误，我们利用深圳市数字地图来验证某个GPS位置是否合理。这是通过检查先前的位置以及这两条记录时间戳之间的时间段来实现的。（ii）重复数据：例如，智能卡数据集中显示同一张智能卡存在两条完全相同的记录。此类重复数据通过比较同一数据源（例如，同一张智能卡）每条记录的时间戳来识别。（iii）缺失数据：例如，一辆出租车在特定时间段内未上传GPS数据。此类缺失数据通过监控每个数据源（例如，一辆出租车）传入数据的时间一致性来发现。上述错误可能由多种现实原因导致，例如硬件故障、软件问题和数据传输问题。

为了解决这些错误，我们对所有输入数据首先过滤掉重复的记录以及属性缺失或错误的记录。然后，通过各种已知的上下文（例如，一天中的时间和数字地图）修正明显的数值错误。接着，按日期和类别存储数据。最后，通过比较数据的时间一致性来检测缺失的记录。诚然，缺失或被过滤掉的数据（占总数据的11%）可能会影响我们分析的性能，但鉴于较长的时间段，我们认为我们的分析仍然具有洞察力。

5.3 数据融合

我们整合和清理这些数据的工作，使得从不同角度进行前所未有的大规模居民感知成为可能，无论是在数量上还是质量上都是空前的。特别是，我们在图9中展示了三种数据在5分钟时间段内检测到的乘客数量，其中我们未区分地铁和公共汽车乘客，因为他们均通过智能卡读卡器作为传感器进行检测。

尽管上述数据足够全面，但其粒度和格式各不相同，因此需要进行数据融合流程。该数据融合流程旨在透明化上述数据的异构性，以便通过统一的表示来推断乘客需求。接下来，我们首先从乘客覆盖率以及空间和时间分辨率方面讨论所用传感器数据的异构性，如表1所示。

传感器 Name	居民 覆盖率 95%	时间 分辨率 稀疏	空间 分辨率
手机	4%	连续	17,859 个基站
出租车			GPS坐标
读者	55%	连续	10,448个站点

如表1所示，（i）手机传感器覆盖了1100万常住居民中的95%，但每个手机传感器仅在用户进行活动（例如打电话）时生成一条记录，且对应的位置仅以深圳的17,859座基站之一表示；（ii）出租车传感器仅覆盖占所有居民4%的每日出租车乘客，但在一天24小时内以精确GPS坐标记录乘客的出发地和真实目的地；（iii）读卡器传感器覆盖占所有居民55%的每日公共汽车和地铁乘客，并在乘客使用智能卡时将其位置记录为10,448个交通站点之一，即127个地铁站和10,321个公交站。

由于异构数据的大规模性，我们的融合流程针对简洁性和速度进行了优化。因此，我们采用统一元组（即数据记录）作为通用抽象，以实现异构传感器数据的透明化。

r=(i,S, T),

其中i是手机、出租车或智能卡用户的标识符；S是以站点、基站或出租车GPS坐标表示的位置；T是基于分钟粒度的关联时间。需要注意的是，尽管许多居民同时拥有手机和智能卡，且他们也可能乘坐出租车，但我们无法将这三种不同类型的数据进行合并，由于不同数据集之间缺乏统一标识符，在以下接驳服务器设计中的乘客。

6 接驳服务器：发车时间计算

我们首先在第6.1节讨论为何需要动态发车时间，并在第6.2节展示如何预测乘客出站站点和时间以实现动态发车时间，最后在第6.3节介绍如何优化发车。

6.1 动态发车时间的动机

我们提出动态发车时间的动机源于常规公交与接驳车在乘客到达模式上的关键差异。在常规公交中，乘客从各种出发地到达交通站点；然而，在接驳车系统中，乘客主要来自一个单一的出发地，即上游公共交通，例如地铁。因此，由于常规公交的乘客来源多样，其乘客到达情况难以准确预测，因而通常采用固定发车时间[9]；而接驳车的乘客到达情况则可以通过观察当前公共交通上的乘客来预测，这些信息基于实时智能卡交易数据是已知的。因此，我们受到启发，通过预测当前公共交通乘客的到达和出站（包括站点和时间）来预测接驳车乘客的到达。这种对公共交通乘客出站的预测被用作接驳车乘客到达的预测，以计算动态发车时间，从而实现短等待时间。

为了支持我们的研究动机，基于实证数据集，我们定位到一条现有的公交线路，该线路类似于具有地铁站终点站的最后一公里交通线路，但采用固定发车时间。在图10中，我们展示了（i）公共汽车在离开终点站时车载乘客数量（采用固定发车），以及（ii）出站地铁乘客的数量。如果不考虑出站地铁乘客的实时波动，采用固定发车时间的公交车上的乘客数量也会如图中所示出现波动。这种波动可能导致乘客等待时间变长。原因是，前一辆公交车若仅搭载少量乘客离站，可能会将大量乘客留给下一班车，而我们的中型接驳车辆可能无法容纳所有这些乘客同时离站。此外，我们针对同一条公交线路，根据出站地铁乘客数量，模拟了采用动态发车时的车载乘客数量。我们观察到，在动态发车时间下，车载乘客数量没有显著波动。简而言之，这表明通过准确预测公共交通出站站点和出站时间的乘客需求，动态发车时间可以减少乘客等待时间。

6.2 出站时间与站点

为了获得公共交通站点（也是Feeder的终点站）出站乘客的实时数量，一种简单的方法是使用历史需求。但这种方法假设乘客需求是稳定的，而在细粒度的时间段中情况往往并非如此。利用实时数据，一种直接的方法是在一段时间内收集乘客exit该站点的需求。然而，当这种需求变得可用时，再安排车辆发车已经太晚，因为乘客在此期间已经处于等待状态。接下来，我们将展示如何预测乘客的出站时间和站点。

6.2.1 出站时间

在本研究中，我们注意到公共交通系统在不同时段内相同两个站点之间的出行时间相对稳定，尤其是在地铁网络中。图11给出了基于我们数据的行程时间标准差的累积分布函数。我们发现，50%的行程时间偏差小于2.2分钟，87%的行程时间偏差小于5分钟。这一良好特性使我们能够利用乘客进站时的智能卡交易时间信息，而非出站时的信息。通过提前预测乘客将在何时从某个出站站点出站，我们有充足的时间来安排接驳车辆的发车时间。如评估所示，我们使用进站作为条件的出站时间预测比仅基于历史信息的预测更为准确。

6.2.2 出站站点

我们通过检查乘客在近期历史中实时上下文下的公共交通模式来推断其出站站点。这是因为大多数作为常规通勤者的乘客每天会在靠近家或工作场所的相同站点出站。例如，图12给出了乘客一周内不同出站站点的累积分布函数，我们发现67%的乘客仅在两个或更少的不同站点出站，e.g.，家和工作场所。如果我们引入更多上下文（一天中的时间），则不同出站站点的数量会更少。更严格地说，我们在图13中展示了在给定进站站点和时间条件下乘客出站站点的条件熵的累积分布函数，其中条件熵低于0.7，表明在总共127个站点中仅有 2^0.7 个可能的出站站点。该结果表明城市交通受到通勤行为的高度规律性影响，因此在给定实时进站上下文的情况下，我们可以对出站站点提供准确预测。

6.3 发车时间优化

车站 Sj的优化概览见图14。

假设当前时间段为 Tc，往返行程关于 Sj 的时间段编号为 τ，则我们的出发时段是从下一个时间段 Tc+1 到时间段 Tc+τ。在这些时间段中，我们旨在选择一个预期乘客等待时间最小的出发时间段 T∗d。因此，我们计算每个可能的出发时间段 Td（其中 d ∈ [c + 1, c + τ]）的预期平均乘客等待时间（记为 ATd）。A 是多个预期出站乘客数量（在 Td 及出发时段内其他时间段中记为 BTd 对于 Td）的函数。进一步地，BTd 基于乘客在时间段 Td 从车站 Sj 出站的概率（记为 C）的聚合。接下来，我们通过四个步骤说明如何获得 C、B、A，最终得到 T∗d。注意，我们以时间段为单位进行计算，而非精确时间，因为即使使用我们的大规模数据集，也很难找到许多具有完全相同精确时间的交易记录。为了表示简洁，我们将同一乘客的一对进站和出站记录匹配，生成一条如下格式的记录：(i, Si, Ti, Sj, Tj)，表示乘客 i 在时间段 Ti 进入车站 Si，并在时间段 Tj 从车站 Sj 出站。类似地，使用 ∗ 作为通配符，我们将关于乘客 i 的所有记录组成的记录集 {·} 表示为 {(i ∗, ∗, ∗, ∗)}。

步骤1： 对于 中的每一位当前 i，我们计算 i在 Ti进入 Si后，在 Td期间离开 Sj的 C(i, Si, Ti, Sj, Td)，计算方法如下。

C(i,Si, Ti,Sj, Td)= |{(i,Si, ∗,Sj, ∗)}| |{(i,Si, ∗, ∗, ∗)}| ·|{(∗,Si, Ti,Sj, Td)}| |{(∗,Si, Ti,Sj, ∗)}| ,

其中，第一个因子用于出站预测，表示在所有历史行程中，当i进入Si后，i从Sj出站的次数；第二个因子用于出站时间预测，表示在所有历史行程中，任意乘客在Ti期间进入Si并从Sj出站的情况下，其在Sj于Td期间出站的次数。这些子集均可通过对历史数据执行聚合操作获得。

例如，假设乘客 i = 1在时间段 Ti=1进入车站 Si=1。我们旨在计算在当前时间段为 Tc=3的情况下，乘客 1 在 Td=4 期间离开车站 Sj=0的概率。根据乘客 1 的历史交易记录，假定该乘客共 10 次进入车站 S1，其中有 9 次离开车站。因此，我们得到 |{(1, S1, ∗, ∗, ∗)}| = 10 和 |{(1, S1, ∗, S0, ∗)}| = 9。进一步地，基于所有乘客的历史交易记录，假设乘客在时间段 T1进入车站 S1并离开车站 S0,的总共 100 次中，有 80 次是在时间段 T4 离开的。因此，我们得到 |{(∗, S1 ,T1,S0, ∗)}| = 100 和 |{(∗, S1 ,T1,S0 ,T4)} | = 80。最后，根据步骤1中的公式，我们有 C (1, S1 ,T1,S0 ,T4) = |{( 1 , }| | {∗ 0 ∗ 1 , 1 ∗ ∗ ∗ S1, ,S , ) (∗,S , , , )}| ·|{(∗ ,S 1 ,T1 , }| | {0 , 4 1 , 1 , 0 ∗ S T )( ,S T S , )}| = 9 10 · 80 100 = 72 100。

步骤 2： 我们对系统中所有 N 名乘客的概率进行聚合，以计算在给定进站时段和站点的情况下，在 Td 期间从 Sj 出站的乘客预期数量 BSj ·Td。

BSj ·Td= ∑Ni=1 C(i,Si, Ti,Sj, Td).

在我们的示例中，假设系统中现在只有一位乘客 i = 1，即 N = 1，我们有 BS0·T4=∑N=1 i=1 C (i, Si, Ti, S0,T4) =C (1,S1,T1, S0,T4) = 72 步骤1 030：。

步骤 3： 以长度t，我们将从下一个时段Tc+1到Tc+τ的潜在出发时段划分为相等的时段。如果一辆车辆在给定时间间隔 Td之后立即从 Sj发车，其中 d ∈[c+ 1,c+τ]，我们计算在出发时段内到达的所有乘客的平均等待时间 ASj ·Td，公式如下

[∑dy=c+1 BSj ·Ty ·(d−y)· t]+[∑c+τz=d+1 BSj ·Tz ·(τ−(z−d))· t] ∑c+τx=c+1 BSj ·Tx,

其中 (i) 分母 ∑c+τx=c+1BSj ·Tx 是从 Tc+1到 Tc+τ的出发时段内的预期乘客数量。(ii) 分子中的第一项，即 ∑dy=c+1 BSj ·Ty ·(d −y) ·t，表示在车辆出发前到达（即从 Tc+1到 Td到达）并随当前车辆离开的乘客的总等待时间。在 Ty到达的乘客预期数量为 BSj ·Ty，预期等待时间为 (d −y) ·t。(iii) 分子中的第二项，即 ∑c+τz=d+1 BSj ·Tz ·( τ−(z −d)) · t，表示在车辆出发后到达（即从 Td+1到 Tc+τ到达）且必须等待车辆返回（但未来发车时间未知）的乘客的最小总等待时间。在 Tz 到达的乘客预期数量为 BSj ·Tz，最小预期等待时间为 (τ−(z −d)) ·t。

在我们的示例中，c= 3, τ= 2，t= 10，d= 4，j= 0，BS0 ·T4 =72100，并进一步假设BS0 ·T5 = 18 100，因此如果车辆在T4之后发车，则所有乘客的平均等待时间AS0 ·T4为

[∑40·Ty ·(4−y)· 10]+[∑50·Tz ·(2−(z−5))· 10] ∑5x=4 BS0·Tx.

因此，我们有 AS0 ·T4 = 72 100 · (4−4)·10+ 18 100 ·( 2− ·10 72 100 + 18 100 = 4. 5−5 ())

步骤 4： 我们让Td遍历从Tc+1到Tc+τ的所有可能的发车时间槽，比较所有对应的ASj ·Td，最终选择在所有ASj ·Td中具有最小ASj ·T∗d的那个时间槽T∗d之后的发车时间。

在我们的示例中，我们继续计算与另一个可能的出发时段相关联的平均等待时间 AS0 ·T5 ，即 T5 ,，然后比较 AS0 ·T5 与 AS0 ·T4 ，最后选择较小的一个来设定出发时间，以实现最小的预期平均等待时间。

作为一个直观的例子，在Sj处只有一辆车辆在等待，但在我们的评估中，我们考虑的是多车辆情况，即选择平均等待时间最小的前n个时隙作为n辆车的发车时隙。车辆的协调在出发时间计算中被隐式考虑。此外，时隙长度、车辆容量和数据历史长度也对接驳车性能产生影响，这些因素在第9节中进行了评估。

7 接驳服务器：停靠位置选择

我们首先在第7.1节介绍我们的研究动机，然后在第7.2节展示如何推断乘客的目的地，最后在第7.3节优化站点选择。

7.1 使用手机和出租车数据

与常规公交不同，最后一公里交通旨在减少乘客到目的地的步行距离 [3]。因此，我们需要采用以目的地为导向的站点选择来缩短步行距离。然而，大规模的细粒度目的地通常未知。在本研究中，我们受到启发：手机和出租车用户的细粒度目的地已被手机和出租车数据所捕捉，这些数据有望作为所有城市乘客目的地的代理。

由于几乎每个城市居民都拥有手机，因此可以利用手机用户的目的地来推断所有目的地，例如，在深圳，我们的手机记录覆盖了95%的常住居民。此外，总共17,859座基站将1,991 km2的深圳区域划分为细粒度的小区，平均覆盖面积为1,991 / 17,859 km2 ≈ 333 × 333 m2,，这些区域通常在步行距离内，因此足够精细，可作为目的地使用。

出租车乘客的目的地也是所有目的地的良好代理，提供了互补的视角。这是因为在城市区域中，居民居住在高密度的高层公寓中，因此大量居民会共享相同的细粒度目的地，e.g.，住宅小区的正门。因此，公共交通乘客的目的地常常与使用出租车的邻居相同，从而该公共交通乘客的目的地会被出租车数据捕捉到。

为支持我们的研究动机，图15 突出了深圳市中心区域的公交和地铁站、基站以及出租车目的地。我们发现：（i）基站的分布比公共交通站点更精细且更均匀；（ii）一小时内累积的出租车目的地覆盖了所有主要道路路段。需要注意的是，这两种出行方式（由手机和出租车捕捉）各自具有独特的优势，无法相互替代。

更严格地说，我们在图16中展示了全部17,859座基站的覆盖区域的累积分布函数，其中61%的基站覆盖区域小于0.2 km2。此外，我们在图17中展示了深圳216个城市区域内每100 m2每日出租车目的地数量的累积分布函数，其中91%的区域每100 m2,至少有一个目的地，通常处于步行距离范围内。

7.2 公共交通乘客的目的地 gers

基于上述讨论，我们通过结合手机用户的目的地集D、Dc以及出租车用户的目的地集Dt，推断出公共交通乘客的目的地集。

为了获得Dc，我们利用给定时间段（例如，一个月）的历史手机数据，在离线状态下推断每位手机用户在基站级别最常访问的两个位置，即家和工作场所。该过程通过在工作日的工作时间（上午9点至下午5点）和非工作时间（下午6点至上午8点）分别找出每位用户最常连接的两个基站来离线执行。根据先前的研究[11],，该方法在推断手机用户的重要地点方面具有高准确性。

为了获得Dt，我们利用离线出租车数据从最新的数据开始，将所有获取到的目的地累积到Dt中，直到Dt的大小等于Dc的大小。这种基于大小的累积的原因是，由于出租车元组中缺乏可识别的乘客ID，我们必须在一段时间（以天为单位）内累积Dt中的所有目的地，以追踪更多出租车乘客的目的地，从而可能发现更多公共交通乘客共享的目的地。为了避免Dt在数量上主导站点选择，当Dt的大小等于Dc的大小时，我们停止累积。

7.3 站点位置优化

我们将目的地集合 D 中的每个目的地根据其位置分配给最近的公共交通站点。这是因为乘客通常会从距离其目的地最近的公共交通站点出站。因此，对于交通站点 Sj，我们得到 D 的一个子集 Dj。接下来，我们为每个公共交通站点单独选择服务站点。我们首先介绍基于施瓦茨准则的服务站点选择方法，然后讨论上下文感知的站点更新。

7.3.1 基于Schwarz准则的部分

我们对K‐均值聚类应用于 中所有目的地，并选择集群的聚类中心作为车站Sj的停靠点。但一个关键问题是如何确定K，即停靠点的数量。停靠点越多，乘客步行至目的地的延迟就越少。但过多的停靠点可能导致过拟合问题，并且还会带来由于车辆频繁停靠，车载乘客的延误进一步增加。因此，为了平衡站点数量 K，我们采用如下所示的Schwarz准则 [13]。

∑M i=1 (li−c(li))2+ 2λKlogM,

其中，M表示Dj中目的地的总数；li表示某一目的地的 GPS位置；c(li)表示在K个聚类中心中距离li最近的聚类中心； λ为正则化因子。第一项∑Mi=1(li −c(li))2称为失真项，表示每个目的地到其最近聚类中心的欧氏距离之和。在我们的接驳车场景下，可将失真项理解为由于增加停靠站而减少乘客到最后一个目的地的平均最后一段步行距离所带来的平均延迟减少量。第二项 2λKlogM称为惩罚项，其中 K需通过与M相关的logM项进行正则化，因为增加K的惩罚程度同时取决于K本身和M。引入该惩罚项是为了避免过拟合。在我们的接驳车场景下，也可将惩罚项视为车辆因增加停靠站而导致的平均延迟增加量。

在上述准则中，值越低，聚类性能越好。然而，由于实际考虑，在较小的服务区域内设置过多的站点以最小化该准则并不可行。因此，对于覆盖区域为Ej的车站 Sj，我们将Kj的上限设为 Ej / (100×100) m2,，因为城市街区通常为 100× 100 m2。针对车站Sj的Kj通过在其取值范围从1到其上限之间选择，以最小化Schwarz准则，即寻找该准则随Kj变化曲线的“肘部”。

7.3.2 基于上下文的停靠点更新

我们探索基于上下文的站点更新，以缩短最后一公里距离。这是因为我们发现，在不同上下文下，乘客目的地存在显著差异，e.g.,工作日和周末，如评估结果所示。对于围绕车站Sj的所有目的地Dj，我们使用星期几作为上下文，将Dj划分为两个子集，i.e.，D1j到D2j，分别包含来自工作日和周末数据的目的地。我们使用每个子集来更新对应日期的站点位置。出于实际考虑，我们未使用其他上下文（e.g.,一天中的时间）进行更频繁的站点更新，因为频繁变更站点可能会使乘客不愿乘坐接驳车，因为他们可能无法提前知晓车辆的停靠位置。该更新方法的性能已在评估中进行了测试。

8 接驳车 实际应用

在本项目中，我们尝试了接驳车的商业化实施。设计的feeder设备已在深圳的98辆车辆上配置，我们的服务器具备充分的能力以高效执行feeder服务器功能。然而，通过深圳市交通委员会，我们获悉此类商业化的公共交通服务需要政府颁发的许可。作为替代方案，我们在深圳塘朗地铁站自行实施了小规模试验，以展示这一点

8.1 实施概述

Based on tax icab and cellphone d 数据方面，我们首先获取那些比其他站点更靠近塘朗站的推断目的地。接着，我们利用这些目的地确定八个服务站点，然后寻找连接这些站点与塘朗站的最短路线，这类似于经典的旅行商问题。我们开发了一种 3 2 基于最小生成树遍历的近似算法来获得连接所有站点的路线，但由于篇幅限制，我们将重点放在数据驱动组件上。站点和路线如图19所示。此外，由于地形特征，车辆在到达最后一个站点后必须沿原路返回车站。

我们在30天期间收集了12名乘客每天早晨乘坐地铁前往工作场所并在塘朗站出站的数据。出站后，根据他们的出站时间，这些乘客被单独或集中接载，然后送达各自的工作场所。我们基于他们的智能卡数据以在线方式计算发车时间，以便车辆出发。车辆会持续返回车站，直到所有预先安排的乘客都被接载并送达目的地。我们使用三部手机对服务过程进行录像，据此计算到达时刻、出发时刻、最后一公里距离和出行时间（等于等待时间加上乘车时间）。

8.2 实施评估

我们使用两个指标，即出行时间和最后一公里距离，将接驳车与固定发车的常规公交服务进行比较。我们还提供了步行时间作为参考。我们首先通过出行时间来评估接驳车，出行时间分为（i）从出站到乘车离开的等待时间；（ii）从乘车离开到抵达目的地的乘车时间。图20给出了30天内12名乘客的平均等待时间和乘车时间，相较于使用固定发车的常规公共汽车。与耗时38分钟的公交车行程相比，接驳车显著减少了出行时间。乘车时间稳定在约14分钟，但等待时间在约9分钟上下波动。

我们在图21中评估了12名乘客的平均出行时间。我们发现，一些乘客的等待时间比其他乘客短。这是因为对具有高度规律性模式的乘客的预测是准确的，从而产生了有效的发车时间。但对于具有不规律模式（e.g.，他们从不同的车站去上班）的乘客，预测不够准确，导致无效的发车时间，这可能会增加他们的等待时间。接驳车始终优于定班公交车，原因是公交站距离乘客的地铁站和最终目的地均比接驳站更远，同时接驳车拥有更好的发车时刻表。

最后，我们通过最后一公里距离来评估接驳车的效果。由于试验中的乘客数量有限，我们利用出租车和手机数据获取一天内该路线所有潜在目的地。然后，我们展示如果具有这些目的地的乘客使用接驳车并在最近的车站下车，八个车站的平均最后一公里距离将会是多少。我们还提供了从塘龙站到每个车站的步行距离作为参考。在图2中，车站2和车站4的效果更佳，因为在这些车站下车的乘客的最后一公里距离小于300米。对于其他车站，平均最后一公里距离约为500米，仍远短于常规公共汽车。

9 接驳车 数据驱动评估

利用图8中介绍的数据集，我们对深圳地铁线路全部五条线路上的127个站点进行了大规模数据驱动的评估，尽管接驳车也可应用于主要公交站。对于每个站点，我们首先根据手机和出租车用户的目的地确定停靠点；然后，找到连接这些停靠点与车站的最短路线；最后，利用流式智能卡数据，在给定时间段内确定出站乘客数量以模拟真实场景（包含意外出现的乘客），并基于在线数据的乘客到达预测计算发车时间。

我们设想只有一半出站的地铁乘客会乘坐接驳车服务。这些乘客的目的地被随机设置为现实世界中出租车和手机用户的真实目的地。我们采用两个关键指标：在不同逻辑背景下，与真实情况相比的减少的末端里程距离百分比和缩短的出行时间百分比，具体背景包括：(i) 一天中的时间； (ii) 星期几；(iii) 区域人口。此外，我们还研究了若干关键参数对系统性能的影响：(i) 发车时段长度t，即车辆从站点出发的时间单位（默认为4分钟）；(ii) 历史数据集长度h ，用于展示历史智能卡数据量的影响（默认为6个月）； (iii) 车辆状态，包括车辆数量n和车辆容量c，以研究接驳车辆的影响（默认值将在后文给出）。

我们将接驳车与其三种变体进行比较，以展示接驳车设计组件的有效性。

(i) 接驳车+DBSCAN在站点选择中利用DBSCAN聚类，用于展示接驳车使用基于Schwarz准则的站点选择的优势；
(ii) 接驳车+固定时刻表基于车辆数量和出行时间的固定发车，不使用任何智能卡数据，用于展示接驳车在发车计算中使用智能卡数据的优势；
(iii) 接驳车+离线仅利用历史智能卡数据集获取发车时间，用于展示接驳车使用实时在线数据及其到达预测的优势；
(iv) 接驳车+列车利用实时列车到站信息作为参考来设定发车时间，以此展示接驳车在使用个体智能卡方面的优势。

我们对接驳车进行了广泛的评估，但由于篇幅限制，我们仅报告接驳车+DBSCAN在减少的最后一公里距离方面的影响，以及其他方案在缩短的出行时间方面的影响。最后一公里距离和出行时间的真实情况通过目的地和车站的位置、平均步行速度5 km/h以及平均驾驶速度35 km/h获得。所有结果均基于三个月评估的平均值。

在可扩展性方面，我们通过概率分布来维护每位乘客在各车站出站时的公共交通出行模式，并每日更新。因此，在实时模式下，运行时间相较于出发时段可忽略不计。

9.1 逻辑上下文的影响

我们测试了三种逻辑上下文的影响 llo ws.

9.1.1 时间

我们在正常公共交通运营时间早上7点至晚上11点之间评估了不同时段的影响。图23绘制了深圳在16小时期间各评估地铁站在末端里程距离上的减少情况。两种服务均显著减少了最后一公里距离。但在高峰时段，接驳车比 Feeder+DBSCAN高出19%；而在非高峰时段，接驳车相比Feeder+DBSCAN性能提升26%。这显示了接驳车通过采用基于Schwarz的站点选择所具有的优势。在默认时间下午6点，接驳车实现了68%的末端里程距离减少的性能。

图24显示了平均缩短的出行时间。在非高峰时段，所有服务平均将出行时间减少了47%；在高峰时段，其性能下降至平均减少43%。但接驳车相比固定时刻表服务多减少了11%的出行时间，因为接驳车采用了基于收集数据的动态发车时间。此外，接驳车相比接驳车+离线版本多减少了21%的出行时间，这得益于实时数据集的使用。接驳车还比接驳车+训练版本多减少了14%，这归功于基于个体智能卡的预测。接驳车+训练版本无法准确预测到达乘客的数量，从而导致调度次优。接驳车在默认时间下午6点具有减少52%出行时间的性能。

请注意，由于不同地铁站的出行时间和最后一公里距离各不相同，我们以百分比形式展示接驳服务的性能，而非名义值。在图25和图26中，我们展示了深圳乘客到达量最大的车公庙地铁站的缩短的出行时间和减少的末端里程距离的名义值。在图25中，我们发现平均减少的末端里程距离有所波动，但接驳车的表现优于 Feeder+DBSCAN。在图26中，我们观察到与图24之前所示类似的趋势，i.e.，接驳车优于其他方法，且在非高峰时段性能更优。

9.1.2 星期几

接驳车+工作日以及接驳车+周末用于测试基于 Feeder在工作日和周末性能的上下文感知站点更新。图27和图28分别绘制了它们缩短的距离和时间。在这两幅图中，我们发现早晚高峰期间，接驳车+工作日的缩短距离高于接驳车+周末。这是因为居民在工作日的早晚高峰出行，而在周末则在正常的白天时段出行。

9.1.3 区域人口

Feeder+Urban给出了Feeder在深圳市三个高人口密度城区（i.e.，FuTian、LuoHu和NanShan）的性能表现，而 Feeder+Rural则展示了其在三个低人口密度郊区（i.e., Baoan、LongHua和LongGang）的性能表现。图27和图28绘制了它们缩短的距离和时间。我们发现，全天范围内， Feeder+Rural的缩短距离均高于Feeder+Urban。这是因为在郊区地铁站数量较少且分布稀疏，导致最后一公里距离较长。

9.2 系统参数的影响

我们测试了四个系统参数的影响，如下所示。

9.2.1 时隙长度t

在图29中，我们评估了时隙长度t的影响，该参数决定了Feeder在调度上的粒度。需要注意的是，t对固定时刻表和与列车到站时间协同设计的时刻表没有影响。随着 t的增加，Feeder和Feeder+Offline的性能先提升后下降。这是因为较小时间段内对出站乘客的预测不够准确；但当时隙过长时，乘客等待时间也会相应延长。

9.2.2 历史数据集长度h

我们在图30中研究了预测乘客出站站点所需的历史信息量。正如预期，时间越长，性能越好。但过长的时间段并没有太大帮助。即使使用6个月的历史数据集，接驳车仍可将乘客的出行时间减少52%。

9.2.3 车辆状态n与c

在接驳车系统中，由于不同车站的需求各异，我们为每个车站设置了不同的车辆数量n。对于车站Sj， 默认的nj= N(τ) / c，其中默认的c设为20，即小型巴士的正常容量；N(τ)表示在时间段 τ内，车站Sj的一辆接驳车在往返行程中服务的出站乘客数量（即所有乘客的一半）。图31绘制了不同倍数的n下时间减少的情况。随着车辆数量增加，接驳车的时间减少比例也随之提高，因为发车间隔缩短了。默认的n倍数为1.5。

我们研究了车辆容量c对图32中接驳车的影响。随着 c的增加，接驳车减少的时间也随之增加。这是因为大容量车辆可承载更多乘客，从而减少了等待时间。这意味着当车辆能承载更多乘客时，接驳车的功能更有效。

Feeder+Train的性能依赖于容量，因为它无法预测每列火车的乘客数量，而更大的车辆可以减少乘客到达的不确定性。

10 讨论

乘客参与。 接驳车被描述为一种自动且透明的服务，乘客无需提供任何额外信息，例如到达公共交通站点的时间或家和工作地址等真实目的地。但遗憾的是，由于手动操作和隐私等问题，大多数乘客不愿意提供详细的出行需求。仅抽样愿意提供请求的一部分乘客会引入对其他乘客的偏差。

首段出行及其他类型的出行。在本研究中，我们仅关注最后一公里问题，而不旨在解决普通出行或乘客从出发地到交通站点的首段出行。首段出行的情况有所不同，若没有乘客通过智能手机应用等方式积极参与，无法准确预测乘客从出发地开始出行的时间。如果乘客愿意通过提供详细的出行需求来参与，也可以基于智能手机应用的专用首段出行服务来解决最后一公里问题。

隐私保护。 我们采取了三个步骤来保护乘客隐私。（i）匿名化：所有数据均由提供商进行匿名化处理，数据中的所有可识别ID均被替换为序列标识符。（ii）最小暴露：我们仅存储和处理对我们的接驳服务有用的数据，并丢弃其他信息以实现最小暴露。（iii）聚合：我们的接驳服务使用聚合结果，不关注个体居民。

实际部署问题。 我们专注于接驳车的技术方面，此处讨论一些现实世界中的问题。接驳车的主要部署成本在于服务车辆，我们设想应采用基于拼车的载客车辆，例如客运面包车或小型巴士，而不是普通出租车。基于这种拼车特性，与出租车相比，接驳车将显著降低乘客费用。在接驳车系统中，大部分计算在服务器端执行，因为我们必须使用服务器上汇总的实时数据进行预测。如果前端车载设备可以访问实时智能卡数据，则计算也可分发到前端。

在不同城市中的实施。由于地理和人口特征，例如出行模式、城市密度和数据可获取性，公共交通服务在不同城市通常表现出不同的性能。因此，在不同城市中评估所提出的接驳车方案以验证其通用性极为重要。目前，我们已获得中国第二大城市上海的部分出租车和手机数据，并正在与其他服务商洽谈，以进行潜在的评估。

11 相关工作

除了引言中讨论的步行、自行车、出租车和个人车辆外，出租车合乘和小型巴士服务是解决最后一公里问题的两种主要方式。一些城市，例如，纽约市 [15],北京[12]和深圳 [18],引入了出租车合乘服务，使乘客可以共享出租车进行 临时的 乘车，但时间和地点均为预设，且不提供基础设施支持。一些城市，例如，香港[1],使用小型巴士将乘客运送至更接近其目的地的位置，但它们具有固定路线和班次。接驳车与合乘服务的关键区别在于，接驳车能够自动学习乘客需求，而合乘服务则假设需求已提前给出。此外，接驳车在低基础设施成本、灵活的网络覆盖率以及通过城市基础设施的在线数据由feeder服务器提供的实时支持方面，也不同于上述服务。

与接驳车相关的另一类研究是城市数据驱动应用。GPS的日益普及推动了城市数据驱动应用领域的大量研究。许多新颖的应用被提出以协助城市居民或城市管理者，例如，为司机寻找停车位[14],基于GPS数据推断现实地图[6],预测公交车到站时间[7],使乘客能够查询出租车可用性以做出知情的交通选择[5],预测出租车司机的乘客需求[10],城市交通建模[19],以及基于经验丰富的司机的GPS轨迹引导新司机[16]。然而，现有对这些系统的研究并未关注最后一公里问题，且通常仅使用一种类型的数据集。而接驳车利用来自多个城市基础设施的流数据，在不增加乘客端负担的情况下解决最后一公里问题。这种独特组合此前尚未被研究过。

12 结论

在本研究中，我们分析、设计、实现并评估了一项服务——接驳车，利用超大规模城市感知基础设施解决最后一公里问题，平均减少68%的最后一公里距离和52%的出行时间。我们的技术探索提供了若干有价值的见解，期望在未来能够有助于类似接驳车