面向城市轨道交通的启发式疫情密接人群追溯方法

谢良惠，张真继，宫大庆*

（1.北京交通大学，经济管理学院，北京 100044；2.北京物流信息化研究基地，北京 100044）

0 引言

根据国务院应对新型冠状病毒感染肺炎疫情联防联控机制综合组印发的《新冠肺炎聚集性疫情处置指南（修订版）》要求，“对同时段暴露于通风不良和相对密闭的同一空间内的所有人群均纳入密接范围”。城市轨道交通具有内部空间半封闭，人群高度密集，客流高速流动及换乘站点不确定等特点[1]，感染者乘坐城市轨道交通后可能导致同乘的密接乘客感染，流调工作人员需迅速掌握密接乘客信息并采取相关措施，因此，密接乘客追溯成为城市轨道交通疫情防控工作的重中之重。目前，深圳和西安等城市采取车厢二维码的方式建立“同乘信息系统”，通过广播等形式提醒乘客扫码，以实现乘客行程轨迹的有效跟踪，但该手段主要依赖于乘客的主动配合，且在高峰拥堵时段扫码的可实施性不强；北京等大多数城市则采用新闻发布会等形式，发布感染者的活动轨迹以提醒市民对照自查，但部分市民并不会主动关注疫情通报信息。因此，在应用层面，尚没有便捷高效的城市轨道交通密接人群追溯手段。

谢驰等[2]提出一套包括公共交通在内的综合城市交通系统疫情防控的基本原理、分析框架和技术方法，指出疫情追溯应以交通网络层面的出行人群时空分布作为输入数据，构建接触网络并开发与应用基于接触网络的潜在病例搜索算法，但并未深入研究具体数学模型和计算方法。掌握乘客出行链信息是追溯密接乘客的基础，在公交下车站点匹配算法[3-4]的基础上，李健等[5]利用AFC数据构建公交乘客出行链和查询匹配感染者出行链，实现了公交密接乘客的追溯。然而，由于AFC 数据仅记录乘客的进出站点和进出站时间信息，乘客在轨道交通系统内部的出行轨迹是一个“黑匣子”，乘客出行链的提取比地面公交系统更为复杂，尚没有学者针对城市轨道交通密接乘客识别展开具体的算法研究工作。

值得借鉴的是，国内外学者以了解乘客出行特征，获取客流时空分布和运营清分清算等为目的，对城市轨道交通乘客出行轨迹识别有关问题展开了一系列研究。石俊刚等[6]利用典型乘客的AFC数据估计各出行阶段的时间概率分布，基于乘客实际旅行时间估计乘客选择各路径的比例。ZHOU等[7]基于剩余行程时间最小化的假设，计算乘客与各路径的匹配度，将乘客匹配到最可能的路径。WU 等[8]利用聚类方法将OD 对间的乘客出行时间划分为不同的聚类，并采用相似性度量方法匹配路径。ZHU等[9]考虑车厢拥挤可能导致的乘客留乘，建立乘客留乘模型估计乘客在起点站和换乘站的留乘概率，结合路径推理模型计算乘客每一种可能行程的概率。以上研究的共同点是先建立起各阶段的出行时间分布，结合时刻表数据构建乘客的可能出行链，利用极大似然法、贝叶斯推理及聚类等方法估计乘客的出行轨迹。然而，早高峰、晚高峰及平峰等时间段乘客出行的急迫程度并不相同，且乘客的步行速度会受到通道和扶梯的实时人流影响，使得不同时间段的出行时间分布存在巨大差异，甚至每一天相同时间段的出行时间分布也不相同。在面向不同路径的乘客比例估计问题时，对个体乘客出行链的准确度要求不高，以固化的出行时间分布为基础的算法具有一定的适用性。但是，当面向疫情追溯的个体乘客出行链识别问题时，要求算法在保证查全率的前提下提高查准率，以上算法不再适用，尤其是当某密接乘客的实际出行时间不满足密接路径固化的出行时间时，该乘客将被误认为非密接乘客，造成密接乘客识别遗漏。

因此，本文的目的是开发一套适用于城市轨道交通的疫情密接人群追溯方法。构建不同时间各阶段的出行时间分布不仅复杂，且难以保证准确度。实际上，即使在极其复杂的网络中，也有某些乘客的出行行程是确定的。这些乘客以实际出行构建出各个站点每一天每一时刻的实时出行场景，可以作为启发式的“证人”为其他乘客提供某种证明，即当“证人”在某一时间某一地点完成某一阶段的出行时，其他乘客也可能在此时此地完成此阶段的出行。这种启发式的“证人”证明了某一乘客某一行程的可能性，从而在保证查全率的前提下，准确地找出潜在的密接乘客。

1 问题描述

若1名感染者X在时刻进入站，于时刻在站出站，共换乘l次，分别乘坐车次的列车，和为感染者X乘坐车次的发车和到达时间（其中，1 ≤m≤l+1，m为整数），则感染者X的行程可表达为

乘客P在时刻进入站，于时刻在站出站，共换乘k次，分别乘坐车次的列车，和分别为乘客P乘坐车次的发车和到达时间（其中，1 ≤n≤k+1，n为整数），则P的行程为

若乘客P乘坐的车次与感染者X乘坐的在乘坐车次和乘车时间上有交集，则乘客P为密接乘客。乘客P和感染者X均经过A站乘车至B站，若乘客P乘坐的车次车次与感染者X乘坐的车次一致，则乘客P为密接乘客，如图1所示。

图1 密接乘客行程轨迹示意Fig.1 Diagram of the trip of a close contact

在上述情景中，感染者X的行程可以通过流行病学调查和AFC 数据相结合确定。对于其他乘客，仅能通过AFC 数据获取乘客的进出站点和时间，其所乘坐的路线和车次是未知的。因此，如何找到在感染者X乘车期间与感染者同车次的乘客P，是本文要解决的问题。

2 模型构建与算法设计

2.1 模型构建

2.1.1 部分乘客的出行链复原

一次典型的城市轨道交通出行链由①进站刷卡、②步行至站台候车、③乘车、④换乘并候车、⑤乘车、⑥步行至闸机、⑦刷卡出站构成，出行行程构成如图2 所示。确定各阶段的出行时间是复原出行链的重要基础。①和⑦的时间可以直接从AFC数据中获得并确定；③和⑤的时间可以通过列车时刻表得到可选的乘车车次，但不能确定到底是哪个车次；由于每位乘客步行速度不同，并且下车车厢位置不同，导致出站步行距离不同，⑥的时间无法直接确定；②和④的时间实际上由步行时间和候车时间组成，其中，步行时间与⑥的特性相同，均存在差异性，而候车时间则由于存在车厢拥挤导致乘客滞留无法乘车的情形，因此，也存在不确定性。

图2 典型城市轨道交通出行行程构成Fig.2 Typical urban rail transit trip composition

一般来说，乘客的出行链是难以复原的。庆幸的是，即使是在极为复杂的城市轨道交通网络中，也有某些乘客的出行路径是简单而清晰的。其中，可分为直达乘客和换乘乘客。

（1）直达乘客

乘客在选择路径时，会考虑旅行时间和换乘次数等因素，选择广义费用最小的路径[10]。当乘客的出发站和到达站间有唯一直达的路径，且直达路径是最短路径时，该路径的旅行时间和换乘次数较其他路径均有着明显的优势，可认为乘客以该路径出行。若能找到该路径上唯一的车次，则乘客唯一可乘坐的车次为

式中：为前一车次在乘客出发站的发车时间；为后一车次在乘客到达站的到达时间。

由此，一部分直达乘客的出行链先被复原出来，其进站时间（从闸机步行走向站台和候车）、上车时间、下车时间及出站时间（从站台步行走向闸机）被确定，并得到在O站进站的上述乘客的最小进站时间和在D站出站的上述乘客的最小出站时间。

当车厢拥挤导致乘客主动或被动留乘时，乘客的实际旅行时间增加，无法满足式（1）。一般来说，乘客在下车后会尽快出站。一班车次的乘客如潮汐般出站，有着明显的间隔，根据乘客进出站时间可判断其乘坐的车次，即

典型出站客流情况如图3所示。

图3 典型出站客流情况Fig.3 Typical outbound passenger flow

（2）换乘乘客

当乘客的出发站和到达站之间没有直达路径，但有唯一的单次换乘路径，且该路径为最短路径时，该路径的旅行时间和换乘次数较其他路径均有着明显的优势，可认为乘客以该路径出行。假设乘客由线路M在H站换乘至线路N，根据乘客出站时间可判断其换乘后乘坐的车次，设为，发车时间为。若能找到唯一的换乘前车次，则乘客唯一可乘坐的车次为

式中：为前一车次在乘客出发站的发车时间；为后一车次在乘客到达站的到达时间。

由此，一部分换乘乘客的出行链先被复原出来，其进站时间（从闸机步行走向站台和候车）、上车时间、下车时间、换乘时间及出站时间（从站台步行走向闸机）等被确定，并得到由线路M在H站换乘至线路N的最小换乘时间。

对于发生留乘的换乘乘客，很难判断其是在换乘前还是换乘后发生留乘。因此，换乘前车次

均作为换乘乘客的可能车次，即

2.1.2 目击者模型

复原部分乘客的出行链之后，在每一个乘车环节，这些乘客像“证人”一般证明了在某时刻刷卡进站是否可能乘坐某个车次的列车，在某天从某个车次下车后是否可能换乘至另一个车次，从某站进站至少要花费多长时间才能到达站台及从某站出站至少要花费多长时间等。为验证其他乘客的出行提供了丰富的信息，这些乘客仿佛“目击”了目标乘客一般，将这些乘客称为“目击者”。

式中：为时间范围内进入O站的所有一类目击者的集合（为车次的发车间隔）；为乘客P第n次换乘时的所有二类目击者的集合（1 ≤n≤k，n为整数）；为时间范围内从D站出站的所有一类目击者的集合（为车次的发车间隔）。

若目标乘客的目标行程为真且与感染者行程有交集，则目标乘客为密接乘客。由此，疫情密接人群追溯问题，可转化为搜索目标乘客的可能行程，并验证是否与感染者行程有交集的问题。

2.2 算法设计

在城市轨道交通网络中，每天有数以百万计的乘客，其中，大部分乘客的出行时间和出行路径与感染者的行程是不存在交集可能的，首先，排除该部分乘客以减少计算量。其次，利用目击者模型生成目标乘客可能的出行链。最后，验证目标乘客的出行链是否与感染者行程存在交集。方法流程如图4所示。具体步骤如下。

图4 算法流程Fig.4 Algorithm flowchart

（1）目标乘客的初步筛查

当乘客的进出站时间与感染者的进出站时间不重叠时，乘客的任何行程不可能与感染者行程有交集。因此，排除符合以下条件的乘客，即

当乘客的所有可能出行路径与感染者的出行路径不重叠时，乘客的任何行程不可能与感染者行程有交集。因此，排除符合以下条件的乘客，即

式中：RP为乘客OD间所有的可能出行路径经过的站点集合（通过地图软件推荐的公共交通线路获取）；RX为感染者X经过的站点集合。

（2）基于目击者的启发式树搜索

通过目击者模型反推目标乘客的可能行程。

Step 2 将在第k个换乘站换乘至车次的二类目击者的换乘前车次作为；将在第k-1 个换乘站换乘至车次的二类目击者的换乘前车次作为；以此类推，将在第1 个换乘站换乘至车次的二类目击者的换乘前车次作为，若且，则该车次为叶节点。

基于目击者的启发式树搜索以图5所示为例。

图5 基于目击者的启发式树搜索Fig.5 Witness-based heuristic tree search

通过出站的一类目击者确定车次a为根节点，通过二类目击者确定车次a的换乘前车次为车次b或车次c，并依次确定车次b的换乘前车次为车次d和车次c的换乘前车次为车次e和车次f。假设仅车次e满足且∈的条件，则乘客可能乘坐的车次为e→c→a，即=e，

（3）验证目标乘客是否为密接乘客

若目标乘客行程中有任意车次与感染者行程中的车次一致，且目标乘客在该车次的乘坐时间与感染者乘坐时间有交集，即存在，使以下条件满足，则目标乘客为密接乘客，即

式中：1 ≤n≤k+1，1 ≤m≤l+1，n和m为整数。

3 实验与分析

3.1 数据来源

本文使用北京市2020年9月29日和10月9日的城市轨道交通AFC 数据，共16614939 条。由于AFC相关设备厂商的多样性以及AFC实时数据传输过程复杂等原因，导致数据异常。经过清洗重复数据和进出站点相同等异常数据后，剩余数据12668267条。

3.2 实验1

为验证方法的准确性，征集志愿者按照设定的路线乘坐北京地铁，其中，一部分与假定的感染者同行程，一部分与假定的感染者不同行程。随后，在AFC 系统中提取志愿者乘车信息，根据本方法验证其是否为密接乘客。

（1）实验设计

时间：2020年9月29日7:00-21:00 和2020年10月9日7:00-21:00

志愿者人数：17名

乘坐路线：北海北-永安里（6号线转2号线转1号线）往返，北海北-永安里（6 号线转5 号线转1 号线）往返，车公庄西-崇文门（6 号线转2 号线）往返，车公庄西-崇文门（6 号线转5 号线）往返，如图6所示。

图6 志愿者乘车路线Fig.6 Trip routes of volunteers

乘坐规则：志愿者按照指定时间进入指定车站，根据指定路线乘车往返，进站和出站均刷卡。整个过程模拟真实出行，步行速度保持正常，如遇到车厢拥挤的情况，可根据个人偏好选择乘坐本趟列车或等待下一趟列车，并记录滞留次数。出行过程中如遇突发或异常事件，例如，上厕所和坐过站等，本次出行标记为非正常出行。志愿者记录出行信息如表1所示。

表1 乘车实验记录表Table 1 Record sheet of experiment

感染者假设：假设在志愿者乘车期间，5号线灯市口站-东单站，东单站-灯市口站的每一班列车均有感染者。

（2）样本分析

17名志愿者中，男性为7名，女性为10名，均为青年，年龄介于20～31岁之间。1～4号志愿者乘坐6号线转2 号线转1 号线往返于北海北-永安里，5～8号志愿者乘坐6号线转5号线转1号线往返于北海北-永安里，9～12 号志愿者乘坐6 号线转2 号线往返于车公庄西-崇文门，13～16号志愿者乘坐6号线转5 号线往返于车公庄西-崇文门，17 号志愿者乘坐以上所有路线。志愿者按照设定的路线不停地往返，乘车时间覆盖早晚高峰及平峰时间，记录156次出行。其中，13次为非正常出行，143次正常出行。

在相同乘车路线的条件下，男性志愿者平均行程时间普遍小于女性志愿者，各路线下志愿者的平均行程时间如表2所示。

表2 志愿者平均行程时间Table 2 Average trip time of volunteers

北海北-永安里的两条线路平均行程时间分别为25 min 33 s 和31 min 53 s，差值为6 min 20 s；车公庄西至崇文门的两条线路平均行程时间则较为接近，分别为28 min 22 s 和29 min 43 s，差值为1 min 21 s。

由于志愿者的步行速度不同和候车时间存在随机性，且不同时段的列车发车间隔和拥挤情况不同，同一路径的志愿者行程时间表现出差异化。志愿者行程时间分布如图7所示（17号志愿者与其他志愿者不同，其乘坐了所有路线，未在图中显示）。

图7 志愿者行程时间分布Fig.7 Distribution of volunteers'trip time

乘坐6 号线转2 号线转1 号线往返于北海北-永安里的1～4号志愿者最大行程时间为35 min 6 s，最小行程时间为21 min 59 s；乘坐6 号线转5 号线转1 号线往返于北海北-永安里的5～8 号志愿者最大行程时间为39 min 54 s，最小行程时间为25 min 57 s；乘坐6号线转2号线往返于车公庄西-崇文门的5～8 号志愿者最大行程时间为37 min 14 s，最小行程时间为23 min 44 s；乘坐6 号线转5 号线往返于车公庄西-崇文门的13～16号志愿者最大行程时间为36 min 44 s，最小行程时间为25 min 7 s。样本行程时间的差异化使得相同OD 的不同路径行程时间存在重叠区间，为精准地验证密接乘客带来挑战。

（3）实验结果

通过本方法验证不同路径正常出行的志愿者是否为密接乘客，结果表明：

在有感染者乘车的线路上，从北海北乘车至永安里（6号线转5号线转1号线）的志愿者共18人次，全部被识别为密接乘客；从永安里乘车至北海北（1号线转5号线转6号线）的志愿者共17人次，全部被识别为密接乘客；从车公庄西乘车至崇文门（6号线转5 号线）的志愿者共20 人次，全部被识别为密接乘客；从崇文门乘车至车公庄西（5号线转6号线）的志愿者共21人次，全部被识别为密接乘客。

在没有感染者乘车的线路上，从北海北乘车至永安里（6 号线转2 号线转1 号线）的志愿者共20 人次，1人次被误识别为密接乘客；从永安里乘车至北海北（1号线转2号线转6号线）的志愿者共19人次，0 人次被误识别为密接乘客；从车公庄西乘车至崇文门（6号线转2号线）的志愿者共15人次，1人次被误识别为密接乘客；从崇文门乘车至车公庄西（2号线转6号线）的志愿者共13人次，4人次被误识别为密接乘客。

综合看，76 人次的密接乘客全部被准确识别，查全率为100%，有6人次被误识别为密接乘客，查准率为92.7%，密接乘客识别结果如表3所示。

表3 密接乘客识别结果Table 3 Identification result of close contacts

从结果可以看出，北海北-永安里（永安里-北海北）的密接乘客查准率较高，其原因可能有两个：一是路径⑥↔⑤↔①乘坐共6站，而路径⑥↔②↔①乘坐共5 站，两者平均行程时间存在明显差异；二是北海北-永安里（永安里-北海北）需换乘2 次，换乘次数越多，目击证据链越长。因此，当志愿者乘坐非密接路径⑥↔②↔①时，难以在密接路径⑥↔⑤↔①形成有效的目击证据链，从而实现更精准地识别。

车公庄西-崇文门（崇文门-车公庄西）的志愿者中，有5 人次被误识别为密接乘客，实际上，5 人次均为同一名志愿者，即12 号志愿者。该名志愿者的平均行程时间（32 min25 s）较其他同路径志愿者的平均行程时间（26 min 45 s）显著更长，甚至长于密接路径上志愿者的平均行程时间（29 min 43 s）。车公庄西-崇文门（崇文门-车公庄西）的两条路径行程时间接近，假设该志愿者在密接路径上出行时，可以找到完整的目击者证据链，使其被误识别为密接乘客。表明在遇到出行节奏（步行速度和拥挤忍受程度等）与其他乘客明显不同的乘客时，本文方法的查准率可能下降，但查全率依旧保持稳定。

3.3 实验2

在城市轨道交通日常运营中，不仅有青年乘客，还包括学生、中年和老年乘客等。为进一步验证方法的有效性，假定2020年9月29日18:04:03进入灯市口站，乘坐地铁5 号线后于18:09:43 从东单站出站的一名乘客为感染者，并在全网所有乘客中排查密接乘客。

按照本文提出的方法，经初步筛查得到9300条乘客信息，利用基于目击者的启发式树搜索生成目标乘客的可能行程并进行验证后，最终，有1896名乘客被识别为密接乘客。由于假定的感染者仅乘坐了1 站，密接乘客人数实际上等于灯市口站-东单站的断面客流量。在疫情期间，北京地铁控制满载率为100%，鉴于感染者出行时段为晚高峰时段，估计列车满载率为100%，即实际密接乘客人数约等于北京地铁5 号线列车的荷载人数，即1440人。方法识别出的密接乘客人数约为实际密接乘客人数的1.3 倍，从侧面说明该方法可大大缩小疫情追溯的范围。

4 结论

本文得到的主要结论如下：

（1）在城市轨道交通网络中，可利用部分乘客的确定性信息，为其他乘客的行程可行性做出实时证明，从而最大限度的排除不可能行程和保留可能行程，以保证密接乘客识别的查准率和查全率。

（2）采用启发式树搜索生成目标乘客可能的出行链，可将疫情密接人群追溯问题，转化为判断两个集合中是否有相同元素的问题，从而快速判断目标乘客是否为密接乘客。

（3）在实验场景下，面对不同备选路径属性的OD 对和不同出行节奏的乘客，本文提出的疫情密接人群追溯方法的查全率一直保持稳定，而查准率会受到备选路径行程时间相似性和部分乘客出行节奏特殊性等因素的影响。从对志愿者的疫情密接人群追溯结果看，方法查全率达100%，查准率达92.7%；从对全网所有乘客的疫情密接人群追溯结果看，方法识别出密接乘客的人数约为实际密接乘客人数（估计）的1.3 倍。实验表明本方法具备一定可行性，在公交卡实行实名制（或绑定联系方式）后，有关部门可向识别出的密接乘客精准推送防疫政策或采取居家隔离和限制乘车等防疫措施，为城市轨道交通常态化及非常规疫情防控工作提供支撑。