第12卷第6期 智能系统学报 Vol.12 No.6 2017年12月 CAAI Transactions on Intelligent Systems Dec.2017 D0:10.11992/tis.201706071 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20171109.1255.026.html 出租车数据的城市道路网路段通行时间估计方法 黄顺伦，杜春，宋宝泉，李军，陈浩 (国防科技大学电子科学与工程学院，湖南长沙410073) 摘要：城市路段通行时间估计能够更好地运营和管理城市交通。针对包含起点-终点位置，行程时间和距离信息的 GPS行程数据，提出了一种城市道路网短时通行时间的估计模型。首先将城市道路网按照交叉路口分解为多个路 段，并基于k最短路径搜索方法分析司机行进路线。然后针对每一个路段，提出了双车道通行时间多项式关联关系 模型，既能提升道路网通行时间精细度，又能避免因训练数据不足导致的路网通行时间过拟合问题。最后以最小化 行程期望时间和实际行程时间之间的均方误差为优化目标，拟合道路网通行时间。在纽约出租车数据集上的实验结 果表明.所提模型及方法相对于传统单车道估计方法能够更准确地估计城市道路网路段的通行时间。 关键词：通行时间估计；GPS-出租车；城市道路网；双车道模型 中图分类号：TP311文献标志码：A文章编号：1673-4785(2017)06-0790-09 中文引用格式：黄顺伦，杜春，宋宝泉，等.出租车数据的城市道路网路段通行时间估计方法.智能系统学报，2017,12(6)：790-798 英文引用格式：HUANG Shunlun,DU Chun,SONG Baoquan,.etal.Urban link travel time estimation using taxi dataJ.CAAI transactions on intelligent systems,2017,12(6):790-798. Urban link travel time estimation using taxi data HUANG Shunlun,DU Chun,SONG Baoquan,LI Jun,CHEN Hao (School of Electronic Science and Engineering,National University of Defense Technology,Changsha 410073,China) Abstract:The accurate estimation of urban link travel time plays a significant role in urban traffic monitoring and su- pervision.Using taxicab GPS trip data,which contains origin and destination locations,travel time,and distances,this paper establishes a model to estimate average short-term urban link travel times.Firstly,the urban road network is di- vided into many segments based on crossings,and the running route of the driver was analyzed using the k-shortest path search algorithm.Then,for each road segment,a polynomial incidence relation model of the travel time in double lanes is proposed;this increases precision and avoids the overfitting of the travel time of the road network caused by insuffi- cient training data.Finally,by minimizing the mean square error between the expected path travel time and the ob- served path travel time as the optimization objective,the travel time of the road network is fitted.The results of experi- ments conducted on New York taxi datasets show that,relative to the traditional single-lane estimation method,the pro- posed model and method more efficiently estimate the travel time of the road segments in urban road networks. Keywords:travel time estimation;GPS-enabled taxicab;urban road networks;two-lane model 城市道路通行时间的准确估计和预测对于改善 的车辆速度和位置信息，具体的时空轨迹信息难以 城市交通状况是至关重要的，其目标在于计算准确 实时获取。因此，必须开发适当的方法来估计道路 的道路网通行时间信息，以便选择道路网中更好的 网路段通行时间。 路线使通行时间最小。若欲准确评估路段通行时 目前，针对城市道路通行时间估计和预测的研 间，最核心的就是从道路传感器中获取良好的车辆 究主要包括两类方法，即基于传感器数据的预测以 实时信息。然而，在大多数情况下，只能获得离散 及基于城市全球定位系统(global positioning sys- tem,GPS)数据的预测方法。 收稿日期：2017-06-22.网络出版日期：2017-11-09. 基金项目：国家863”计划项目(2015AA123901). 第一类方法的研究主要依赖于各种类型传感器 通信作者：陈浩.E-mail:hchen@nudt.edu.cn, 采集的数据进行预测，主要包括：环形线圈检测
DOI: 10.11992/tis.201706071 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20171109.1255.026.html 出租车数据的城市道路网路段通行时间估计方法 黄顺伦，杜春，宋宝泉，李军，陈浩 （国防科技大学 电子科学与工程学院，湖南 长沙 410073） 摘 要：城市路段通行时间估计能够更好地运营和管理城市交通。针对包含起点–终点位置，行程时间和距离信息的 GPS 行程数据，提出了一种城市道路网短时通行时间的估计模型。首先将城市道路网按照交叉路口分解为多个路 段，并基于 k-最短路径搜索方法分析司机行进路线。然后针对每一个路段，提出了双车道通行时间多项式关联关系 模型，既能提升道路网通行时间精细度，又能避免因训练数据不足导致的路网通行时间过拟合问题。最后以最小化 行程期望时间和实际行程时间之间的均方误差为优化目标，拟合道路网通行时间。在纽约出租车数据集上的实验结 果表明，所提模型及方法相对于传统单车道估计方法能够更准确地估计城市道路网路段的通行时间。 关键词：通行时间估计；GPS-出租车；城市道路网；双车道模型 中图分类号：TP311 文献标志码：A 文章编号：1673−4785(2017)06−0790−09 中文引用格式：黄顺伦, 杜春, 宋宝泉, 等. 出租车数据的城市道路网路段通行时间估计方法[J]. 智能系统学报, 2017, 12(6): 790–798. 英文引用格式：HUANG Shunlun, DU Chun, SONG Baoquan, et al. Urban link travel time estimation using taxi data[J]. CAAI transactions on intelligent systems, 2017, 12(6): 790–798. Urban link travel time estimation using taxi data HUANG Shunlun，DU Chun，SONG Baoquan，LI Jun，CHEN Hao (School of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China) Abstract: The accurate estimation of urban link travel time plays a significant role in urban traffic monitoring and supervision. Using taxicab GPS trip data, which contains origin and destination locations, travel time, and distances, this paper establishes a model to estimate average short-term urban link travel times. Firstly, the urban road network is divided into many segments based on crossings, and the running route of the driver was analyzed using the k-shortest path search algorithm. Then, for each road segment, a polynomial incidence relation model of the travel time in double lanes is proposed; this increases precision and avoids the overfitting of the travel time of the road network caused by insufficient training data. Finally, by minimizing the mean square error between the expected path travel time and the observed path travel time as the optimization objective, the travel time of the road network is fitted. The results of experiments conducted on New York taxi datasets show that, relative to the traditional single-lane estimation method, the proposed model and method more efficiently estimate the travel time of the road segments in urban road networks. Keywords: travel time estimation; GPS-enabled taxicab; urban road networks; two-lane model 城市道路通行时间的准确估计和预测对于改善 城市交通状况是至关重要的，其目标在于计算准确 的道路网通行时间信息, 以便选择道路网中更好的 路线使通行时间最小。若欲准确评估路段通行时 间，最核心的就是从道路传感器中获取良好的车辆 实时信息。然而，在大多数情况下，只能获得离散 的车辆速度和位置信息, 具体的时空轨迹信息难以 实时获取。因此，必须开发适当的方法来估计道路 网路段通行时间。 目前，针对城市道路通行时间估计和预测的研 究主要包括两类方法，即基于传感器数据的预测以 及基于城市全球定位系统 (global positioning system，GPS) 数据的预测方法。 第一类方法的研究主要依赖于各种类型传感器 采集的数据进行预测，主要包括:环形线圈检测 收稿日期：2017−06−22. 网络出版日期：2017−11−09. 基金项目：国家“863”计划项目 (2015AA123901). 通信作者：陈浩. E-mail：hchen@nudt.edu.cn. 第 12 卷第 6 期 智 能 系 统 学 报 Vol.12 No.6 2017 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2017
第6期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·791· 器)、自动车辆识别1、摄像机、远程通信微波传 同时段路段通行时间的实验，验证了本文所提双车 感器和自动化牌照识别等。通常，这些数据需要 道预测方法相比于单车道方法能够更准确地估计道 相应精度级别的传感器来获取。然而由于传感器的 路网路段的通行时间。 安装和维护费用高昂，导致基于传感器获取数据的 道路通行时间预测方法的应用难以普及。 1道路网路段通行时间估计模型 第二类方法是基于GPS数据估计城市地区交 本节将介绍估计道路网路段通行时间模型，该 通动态需求和道路网动态变化，因其具有极大的应 模型的总体框架如图1示，主要包括以下4个步 用价值而引起国内外学者的广泛关注。通过车辆或 骤：1)地图匹配。GPS数据中的起点和终点映射到 移动手机中的GPS设备获取的数据可以成为监测 道路网中，以减小GPS误差带来的影响，将原始数 城市交通量的可行来源⑧。随着从车辆和手机中获 据转化为可用数据。2)路径选择。采用k-最短路 得的GPS数据越来越多，基于这些大规模分散数据 径算法16，构建每段行程的路径集合，并根据MNL 估计路段通行时间已变为现实。因为手机数据涉及 (multinominal logit model)模型计算司机选择不同 个人隐私等问题，大量研究主要以车辆GPS数据 路径的可能性，最后筛选合理的路径集合作为估计 为主。Zhan等基于轨迹数据估计城市交通流量； 路段时间过程的基础。3)双车道通行时间模型构 Zheng等基于稀疏车辆数据提出了估计城市路段 建。为精细刻画道路网通行时间程度，提出双车道 通行时间的ANN模型；Hunter等利用GPS车辆 通行时间多项式关联关系模型。4)路段通行时间 数据统计路段通行时间；Herring等2认为出租车相 估计。将步骤2)中筛选出的多条路径作为出租车 比普通车辆在城市中具有更高渗透率，利用出租车 某次行程的可能发生事件以计算每次行程的期望时 GPS数据可以更好表现道路网情况，因此他们基于 间，最后将路段通行时间估计问题转换为行程观测 500辆出租车的GPS数据，估计和预测了I旧金山城 时间与期望时间均方误差最小问题。 市范围内离散的交通状况。然而，所有上述方法仅 开始 适用于GPS轨迹数据。但是，现实世界中大量出租 车GPS数据仅含起点终点(origin-destination,OD) 地图匹配 信息，如纽约公布的出租车行驶数据集)等。由于 全球定位系统起，点终点(GPS-OD)数据中，仅包含 合理路径选择 出租车一次运营过程的起点和终点，而不包含本次 双车道模型构建 运营的路线信息，于是基于GPS-OD数据进行路网 道路网路段通行 通行时间估计，不仅需要拟合路段时间，还需要分 时间估计 析出租车运行路线，给城市道路网路段通行时间估 计问题带来了新的挑战。Zhan1等利用纽约出租 结束 车GPS-OD数据，估计道路网路段通行时间。但 图1模型总体框架 是，他只考虑了道路单车道对车辆行驶的影响，当 Fig.1 General framework for model 路段较宽时，车道数可能更多，单车道不能很好地 下面将详细介绍地图匹配、路径选择模型、路 刻画道路网精细化程度。 段双车道通行时间间多项式关联关系模型，道路网 为了克服上述的问题，本文基于出租车数据提 路段通行时间估计方法。 出了一种城市道路网路段通行时间估计方法，主要 贡献在于 1.1地图匹配 1)建立了基于出租车GPS-OD数据集的双车 GPS数据因接收设备老化，信号传播延迟等原 道道路网通行时间估计模型。假设道路网每条路段 因存在一定定位误差，需要预先对原始GPS数据进 为双车道，能够更准确地描述道路网通行情况，为 行地图匹配，其具体作用将起点和终点映射到道路 了避免训练数据量不足而导致的过拟合问题，建立 网中，将原始数据转换为可用数据，便于道路网分析。 了双车道间通行时间多项式关联关系模型。 图2说明了数据地图匹配过程，其中端点(41， 2)采用优化非线性最小二乘方法估计路段每小 A2,B1,B2)为路径相交节点，首先将原始起点和终 时平均通行时间，从而实现路网通行时间拟合。 点(A,B)匹配到最近路段的垂足上(A',B),匹配后 3)设计多组实验，分析双车道通行时间之间不 的点的位置用路段两个端点(A1和A2,B,和B2)和 同多项式关系对道路网路段通行时间估计结果的影 a1,a2(a=d/d,a=d/d)表示。对于位于单向街道 响，确定效果最优的多项式关系。通过多组估计不 的起点和终点，两个端，点在给定路段的方向信息情
器 [1-3] 、自动车辆识别[4-5] 、摄像机、远程通信微波传 感器[6]和自动化牌照识别[7]等。通常，这些数据需要 相应精度级别的传感器来获取。然而由于传感器的 安装和维护费用高昂，导致基于传感器获取数据的 道路通行时间预测方法的应用难以普及。 第二类方法是基于 GPS 数据估计城市地区交 通动态需求和道路网动态变化，因其具有极大的应 用价值而引起国内外学者的广泛关注。通过车辆或 移动手机中的 GPS 设备获取的数据可以成为监测 城市交通量的可行来源[8]。随着从车辆和手机中获 得的 GPS 数据越来越多，基于这些大规模分散数据 估计路段通行时间已变为现实。因为手机数据涉及 个人隐私等问题，大量研究主要以车辆 GPS 数据 为主。Zhan 等 [9]基于轨迹数据估计城市交通流量； Zheng 等 [10]基于稀疏车辆数据提出了估计城市路段 通行时间的 ANN 模型；Hunter 等 [11]利用 GPS 车辆 数据统计路段通行时间；Herring 等 [12]认为出租车相 比普通车辆在城市中具有更高渗透率，利用出租车 GPS 数据可以更好表现道路网情况，因此他们基于 500 辆出租车的 GPS 数据，估计和预测了旧金山城 市范围内离散的交通状况。然而，所有上述方法仅 适用于 GPS 轨迹数据。但是，现实世界中大量出租 车 GPS 数据仅含起点终点 (origin-destination，OD) 信息，如纽约公布的出租车行驶数据集[13]等。由于 全球定位系统起点终点 (GPS-OD) 数据中，仅包含 出租车一次运营过程的起点和终点，而不包含本次 运营的路线信息，于是基于 GPS-OD 数据进行路网 通行时间估计，不仅需要拟合路段时间，还需要分 析出租车运行路线，给城市道路网路段通行时间估 计问题带来了新的挑战。Zhan[14-15]等利用纽约出租 车 GPS-OD 数据，估计道路网路段通行时间。但 是，他只考虑了道路单车道对车辆行驶的影响，当 路段较宽时，车道数可能更多，单车道不能很好地 刻画道路网精细化程度。 为了克服上述的问题，本文基于出租车数据提 出了一种城市道路网路段通行时间估计方法，主要 贡献在于: 1）建立了基于出租车 GPS-OD 数据集的双车 道道路网通行时间估计模型。假设道路网每条路段 为双车道，能够更准确地描述道路网通行情况，为 了避免训练数据量不足而导致的过拟合问题，建立 了双车道间通行时间多项式关联关系模型。 2）采用优化非线性最小二乘方法估计路段每小 时平均通行时间，从而实现路网通行时间拟合。 3）设计多组实验，分析双车道通行时间之间不 同多项式关系对道路网路段通行时间估计结果的影 响，确定效果最优的多项式关系。通过多组估计不 同时段路段通行时间的实验，验证了本文所提双车 道预测方法相比于单车道方法能够更准确地估计道 路网路段的通行时间。 1 道路网路段通行时间估计模型 本节将介绍估计道路网路段通行时间模型，该 模型的总体框架如图 1 所示，主要包括以下 4 个步 骤:1) 地图匹配。GPS 数据中的起点和终点映射到 道路网中，以减小 GPS 误差带来的影响，将原始数 据转化为可用数据。2) 路径选择。采用 k-最短路 径算法[16] ，构建每段行程的路径集合，并根据 MNL (multinominal logit model)[17]模型计算司机选择不同 路径的可能性，最后筛选合理的路径集合作为估计 路段时间过程的基础。3) 双车道通行时间模型构 建。为精细刻画道路网通行时间程度，提出双车道 通行时间多项式关联关系模型。4) 路段通行时间 估计。将步骤 2) 中筛选出的多条路径作为出租车 某次行程的可能发生事件以计算每次行程的期望时 间，最后将路段通行时间估计问题转换为行程观测 时间与期望时间均方误差最小问题。 下面将详细介绍地图匹配、路径选择模型、路 段双车道通行时间间多项式关联关系模型，道路网 路段通行时间估计方法。 1.1 地图匹配 GPS 数据因接收设备老化，信号传播延迟等原 因存在一定定位误差，需要预先对原始 GPS 数据进 行地图匹配，其具体作用将起点和终点映射到道路 网中，将原始数据转换为可用数据，便于道路网分析。 α1,α2(α1 = d ′ k /dk ,a2 = d ′ k /di) 图 2 说明了数据地图匹配过程，其中端点 (A1， A2，B1，B2 ) 为路径相交节点，首先将原始起点和终 点 (A，B) 匹配到最近路段的垂足上 (A′，B′)，匹配后 的点的位置用路段两个端点 (A1 和 A2，B1 和 B2 ) 和 表示。对于位于单向街道 的起点和终点，两个端点在给定路段的方向信息情 ᐬ పࡥ䙹 ऴ⤲䌛ᒰ䔵᠕ 䕿䌛㑽䌛⃡䕆㵸 ᬢ䬠ќ䃍 ㏿ ࣸ䒒䕿ὍಷᲰᐦ 图 1 模型总体框架 Fig. 1 General framework for model 第 6 期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·791·
·792· 智能系统学报 第12卷 况下很容易被识别。对于位于双向街道上的点，这 假设每个司机在同一起，点终点的行程下，更偏 个路段的两个端点都可用，不同端点组合的1、2 好选择行程时间和距离更短的路径，那他们就能够 也可能是同样的记录。 行驶更多行程数量，获得更多收益。在建立合理的 瑞点A 路径集合时，设置阈值用于排除违反上述选择行为 假设的路径。路径距离在行程观测距离一定比例内 的才会被使用。因为数据中记录的行程距离不精 起点A 匹配点A 确（只到160m),设置工作日行程距离阈值为 15%~25%,周末为20%~25%，消除那些偏离记录 中行程距离太多的不合理路径。阈值设定取决于一 个小时内可用的行程数据量。 端点B2 根据城市出租车计价规则：开始行程收取基本 匹配点B 费用，超过基本乘车距离和时间，按相应比例收取 终点B 叠加费用。考虑到实际情况下票价计算的复杂，采 用行程时间和距离的线性模型表示行程成本，如式 (2)所示。 瑞点41 瑞点B fare =Bo+Btime+B2.distance (2) 式中：fare表示行程成本，P。为常数，B、B2是行程时 图2地图匹配示例 间和距离的成本系数。根据文献14]，B、B2的估计 Fig.2 Illustration of data mapping 值为0.275/min和2.516/km。 1.2路径选择模型 Cm(t,dm)=B1gm(t)+B2.dm (3) 将GPS-OD数据进行地图匹配后，得到了道路 式中：dm是路径m的距离，路径m的通行时间 网中每次行程的起，点终点数据。由于路径选择信息 &m(t)定义为 的缺失，在估计城市道路网时间时需要推断实际的 g-l0=ao+ao+∑4 (4) 路径。但在城市的道路网中，对于某一确定的出租 式中：。是起点所在路段的通行时间，o是终点所在 车行程，所有路径的集合是非常大的。考虑到交通 路段的通行时间，L是道路网的路段集合，1，是路段 网中观测数目过于庞大，对整个空间进行路径搜索 I的通行时间，6是路径与路段的关系值，取值为0、 非常耗时，减少路径数目是很有必要的。这里，采 1,1表示路径m经过路段1,0则相反，12是距离 用k-最短路径搜索算法生成最初的路径集合，然后 比例。 利用数据中记录的行程距离来排除不合理的路径。 13路段双车道通行时间之间多项式关联关系模型 计算每段行程的可选路径集合后，由于缺少司 在城市道路网中许多道路分为左侧车道、直行 机社会和行为特征，不能用传统的计量经济学模型 车道和右侧车道。左侧和直行车道在行驶过程中会 来估计司机所选择的路径。因为司机做出决策之前 出现等待红绿灯的情况，右侧车道则可以直接通 不可能知道实际的路径时间。但是，他们可以通过 行。若只考虑单车道情况，将会忽略左侧和直行车 经验推测道路网通行时间，因此本文基于MNL模 道上等待红绿灯的时间。若加入多车道，但不考虑 型利用可选路径集合中的路径时间和距离表示路径 车道间关系，可能导致待估变量数目太多，拟合效 成本Cm求不同路径的选择概率。为降低复杂性， 果较差，或样本数不足的情况。假定同一路段上左 定义路径选择模型为 侧车道和直行车道上的车辆通行时间服从相似的分 exp[-0C(t,dm)] 布，并根据路段车道间车流量会相互影响的实际情 P(t,d,0)= (1) expl-0C(t.d)] 况，我们认为路段上为双车道，且存在一定的多项 式中：Pm表示某一行程中可选路径m的选择概率与 式关系，如式（⑤）所示。 道路网路段通行时间t、行程中各个可选路径的距 y=∑+x+%k=23,… (5) 离d、参数O有关。Cm表示路径m的成本与道路网 式中：x是路段上一条车道的通行时间，y表示与 路段通行时间t和路径距离dm有关，参数0用于表 x相关的另一条车道的通行时间，多项式？为待估 示司机感知不同时间段道路网通行时间不同时的路 参数。 径成本变化，0大表示感知错误小，司机倾向于选择 1.4道路网路段通行时间估计 成本小的路径，而0小意味着感知错误较大，成本 道路网路段通行时间估计是最小化行程观测时 越大的路径越有可能被选择。在此模型中，0和道 间与期望时间之间的均方差，将出租车实际路径选 路网通行时间都是待估参数。 择作为隐含变量，路段通行时间t、双车道之间的多
α1、α2 况下很容易被识别。对于位于双向街道上的点，这 个路段的两个端点都可用，不同端点组合的 也可能是同样的记录。 1.2 路径选择模型 将 GPS-OD 数据进行地图匹配后，得到了道路 网中每次行程的起点终点数据。由于路径选择信息 的缺失，在估计城市道路网时间时需要推断实际的 路径。但在城市的道路网中，对于某一确定的出租 车行程，所有路径的集合是非常大的。考虑到交通 网中观测数目过于庞大，对整个空间进行路径搜索 非常耗时，减少路径数目是很有必要的。这里，采 用 k-最短路径搜索算法生成最初的路径集合，然后 利用数据中记录的行程距离来排除不合理的路径。 计算每段行程的可选路径集合后，由于缺少司 机社会和行为特征，不能用传统的计量经济学模型 来估计司机所选择的路径。因为司机做出决策之前 不可能知道实际的路径时间。但是，他们可以通过 经验推测道路网通行时间，因此本文基于 MNL 模 型利用可选路径集合中的路径时间和距离表示路径 成本 Cm 求不同路径的选择概率。为降低复杂性， 定义路径选择模型为 Pm(t,d, θ) = ∑ exp[−θCm(t,dm)] j∈Ri exp[−θCj(t,dj)] (1) 式中：Pm 表示某一行程中可选路径 m 的选择概率与 道路网路段通行时间 t、行程中各个可选路径的距 离 d、参数 θ 有关。Cm 表示路径 m 的成本与道路网 路段通行时间 t 和路径距离 dm 有关，参数 θ 用于表 示司机感知不同时间段道路网通行时间不同时的路 径成本变化，θ 大表示感知错误小，司机倾向于选择 成本小的路径，而 θ 小意味着感知错误较大，成本 越大的路径越有可能被选择。在此模型中，θ 和道 路网通行时间都是待估参数。 假设每个司机在同一起点终点的行程下，更偏 好选择行程时间和距离更短的路径，那他们就能够 行驶更多行程数量，获得更多收益。在建立合理的 路径集合时，设置阈值用于排除违反上述选择行为 假设的路径。路径距离在行程观测距离一定比例内 的才会被使用。因为数据中记录的行程距离不精 确 (只到 160 m)，设置工作日行程距离阈值为 15%～25%，周末为 20%～25%，消除那些偏离记录 中行程距离太多的不合理路径。阈值设定取决于一 个小时内可用的行程数据量。 根据城市出租车计价规则:开始行程收取基本 费用，超过基本乘车距离和时间，按相应比例收取 叠加费用。考虑到实际情况下票价计算的复杂，采 用行程时间和距离的线性模型表示行程成本，如式 (2) 所示。 fare = β0 +β1 ·time+β2 · distance (2) 式中：fare 表示行程成本，β0 为常数，β1、β2 是行程时 间和距离的成本系数。根据文献[14]，β1、β2 的估计 值为 0.275/min 和 2.516/km。 Cm(t,dm) = β1 · gm(t)+β2 · dm (3) gm(t) 式中：d m 是路径 m 的距离，路径 m 的通行时间 定义为 gm(t) = a1tO +a2tD + ∑ l∈L tl (4) δml α1、α2 式中：t0 是起点所在路段的通行时间，tD 是终点所在 路段的通行时间，L 是道路网的路段集合，tl 是路段 l 的通行时间， 是路径与路段的关系值，取值为 0、 1, 1 表示路径 m 经过路段 l，0 则相反， 是距离 比例。 1.3 路段双车道通行时间之间多项式关联关系模型 在城市道路网中许多道路分为左侧车道、直行 车道和右侧车道。左侧和直行车道在行驶过程中会 出现等待红绿灯的情况，右侧车道则可以直接通 行。若只考虑单车道情况，将会忽略左侧和直行车 道上等待红绿灯的时间。若加入多车道，但不考虑 车道间关系，可能导致待估变量数目太多，拟合效 果较差，或样本数不足的情况。假定同一路段上左 侧车道和直行车道上的车辆通行时间服从相似的分 布，并根据路段车道间车流量会相互影响的实际情 况，我们认为路段上为双车道，且存在一定的多项 式关系，如式 (5) 所示。 y = ∑k i=2 γix i +γ1 x+γ0, k = 2,3,··· (5) 式中：x 是路段上一条车道的通行时间，y 表示与 x 相关的另一条车道的通行时间，多项式 γ 为待估 参数。 1.4 道路网路段通行时间估计 道路网路段通行时间估计是最小化行程观测时 间与期望时间之间的均方差，将出租车实际路径选 择作为隐含变量，路段通行时间 t、双车道之间的多 䊣◥A ࡥ䙹◥A΄ ㏴◥B ࡥ䙹◥B΄ 〛◥A1 〛◥B1 〛◥A2 〛◥B2 图 2 地图匹配示例 Fig. 2 Illustration of data mapping ·792· 智 能 系 统 学 报 第 12 卷
第6期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·793· 项式关系参数？和比例参数0作为待估参数，观测 Ji= of(Ri.t.Y.0) l=1,2,…,W (14) i的期望时间E(YR)可写成 ot ECR)=∑-8，P.L.Ydm of(Ri:t,y,0) (6) p=N+1,…,W+k+1 (15) 式中：Y,是观测i的时间变量，R是根据观测i的 of(Ri,t.y,0 OD行程记录建立的可能路径集，t是道路网路段通 J= ,q=N+k+2 (16) 00 行时间向量，？是双车道间多项式关系参数，d是 Jacobian矩阵是一个Np*(W+k+2)的矩阵，其 R的所有路径距离，8m(t,y)是路径m的行程时间， 中N。是数据集中行程观测数目，W是道路网中路段 Pm(*)是选择路径m的可能性，0是比例参数。 数目，k是双车道间多项式关系的阶次。 对于一条路径，其距离是确定的，道路网路段 路段通行时间1，车道间多项式关系参数，比 通行时间向量·，双车道间多项式关系参数？和比例 例参数0在第v次迭代更新为 参数0是待估参数，那么E(YR)可以表示为一个与 t≈f+1=P+9 R,t,y,0有关的函数： y≈y1=y'+u,0 (17) 0≈0+1=F+u6 E(YR)=f(Ri,t.Y.0) (7) 得到待估参数在第ⅴ次迭代求解增量正规方程 进一步，行程观测时间y,与行程期望时间 时的更新方向为=(u,,u,,u。),增量正规方程为 E(YR)之间的误差可以定义为 (JDu)=Jnr (18) ri=yi-f(Ri.t.y,0) (8) 当迭代结束后，式(17)所得t值即为所估计的 则误差平方定义为 道路网路段通行时间，？为双车道间多项式关系参 St.x0=∑广=∑e-fR.4x.P (9) 数，0为表示司机对道路网感知程度的比例参数。 由此，所估计的道路网路段通行时间为 通过分析可以发现，上述函数非凸，可能有多 t=arg minS(t.y,0) 10) 个局部最优点。在具体求解时，考虑将初始值默认 为整个道路网当前时段下的平均速度，能较快较好 2 道路网路段通行时间求解 地收敛到合适的最优的值。 利用Levenberg-Marquardt(LM)I方法解决非 线性最小二乘问题。该方法是一种广泛用于求解最 3 实验结果与分析 小二乘拟合和非线性规划问题的优化算法。在各种 我们采用纽约出租车行程数据集，数据由城市 问题上，它优于一般的梯度下降方法和著名的高斯- 牛顿(GN)方法1。传统的高斯-牛顿法是计算代 出租车豪华轿车委员会(New York City Taxi and Li-- mousine Commission,NYTLC)收集。其特点是每 价高的线性搜索法。更新的高斯-牛顿法类似于牛 顿法，当近似的Hessian矩阵近似奇异时变成了数 个出租车都安装了GPS设备采集数据。纽约有北 学问题。如果利用不恰当的初始值，则容易不能收 美最大的出租车市场，12779(2006年)辆黄色纪念 敛到最优。另一方面，Levenberg-Marquardt方法利 章出租车每年大约服务2.4亿人次。在曼哈顿，乘 用信任域策略而不是线性搜索方法，在更新步骤前 坐出租车人数是所有出行人数的25%20。数据集包 确定步长。在LM中利用不同的Hessian近似方法 含2010一2015年出租车行程数据，其中包括行程开 也有助于确保每次迭代时矩阵的正定性，具有更好 始和结束(OD数据)的地理位置、行程距离、时间 的鲁棒性，这意味着在许多情况下，即使初始值远 和票价等信息，而缺少出租车的确切轨迹。但是， 离最终优值，Levenberg-Marquardt法也能找到一个 大量的数据（一天450000~550000的记录数量） 近似解。在Bonnans和Gilbert中表明Levenberg- 可以推断出租车可能路线，并进一步估计道路网的 Marquardt具有快速局部收敛性能。 路段通行时间。 本文中，利用LM算法求解的目标函数为行程 基于Python语言编程实现前面部分讨论的模 型。硬件配置为i5处理器，3.2 GHz CPU,4GB内 期望时间： 存。在实验中利用均方根误差(root mean square er- Eg)=f.x0=∑8-G,9 S&(t.Y,0) (11) ror,RMSE)和平均绝对百分比误差(mean absolute 简单起见，定义 percentage error,MAPE)来评估估计结果： Pm(t.Y.0)=exp0(-Bi-8m(t.Y)-B2dm) (12) RMSE 1- (19) 式(1)的分母写成 n Sx0=∑epg8-)-房d)I3) MAPE= 1|T-T ×100% (20) 求解Jacobian矩阵为 nT
E(Yi |Ri) 项式关系参数 γ 和比例参数 θ 作为待估参数，观测 i 的期望时间 可写成 E(Yi |Ri) = ∑ m∈Ri gm(t,γ)Pm(t,γ,d, θ) (6) gm(t,γ) Pm(∗) 式中：Yi 是观测 i 的时间变量，Ri 是根据观测 i 的 OD 行程记录建立的可能路径集, t 是道路网路段通 行时间向量，γ 是双车道间多项式关系参数，d 是 Ri 的所有路径距离， 是路径 m 的行程时间， 是选择路径 m 的可能性，θ 是比例参数。 E(Yi |Ri) Ri , t,γ, θ 对于一条路径，其距离是确定的，道路网路段 通行时间向量 t，双车道间多项式关系参数 γ 和比例 参数 θ 是待估参数，那么 可以表示为一个与 有关的函数： E(Yi |Ri) = f(Ri , t,γ, θ) (7) E(Yi |Ri) 进一步，行程观测时间 y i 与行程期望时间 之间的误差可以定义为 ri = yi − f(Ri , t,γ, θ) (8) 则误差平方定义为 S (t,γ, θ) = ∑ i∈D r 2 i = ∑ i∈D (yi − f(Ri , t,γ, θ))2 (9) 由此，所估计的道路网路段通行时间为 t = arg min t S (t,γ, θ) (10) 2 道路网路段通行时间求解 利用 Levenberg-Marquardt(LM)[18]方法解决非 线性最小二乘问题。该方法是一种广泛用于求解最 小二乘拟合和非线性规划问题的优化算法。在各种 问题上，它优于一般的梯度下降方法和著名的高斯– 牛顿 (GN) 方法[18]。传统的高斯–牛顿法是计算代 价高的线性搜索法。更新的高斯–牛顿法类似于牛 顿法，当近似的 Hessian 矩阵近似奇异时变成了数 学问题。如果利用不恰当的初始值，则容易不能收 敛到最优。另一方面，Levenberg-Marquardt 方法利 用信任域策略而不是线性搜索方法，在更新步骤前 确定步长。在 LM 中利用不同的 Hessian 近似方法 也有助于确保每次迭代时矩阵的正定性，具有更好 的鲁棒性，这意味着在许多情况下，即使初始值远 离最终优值，Levenberg-Marquardt 法也能找到一个 近似解。在 Bonnans 和 Gilbert[19]中表明 LevenbergMarquardt 具有快速局部收敛性能。 本文中，利用 LM 算法求解的目标函数为行程 期望时间： E(Yi |Ri) = f(Ri , t,γ, θ) = ∑ m∈Ri gm(t,γ) Pm(t,γ, θ) S Ri (t,γ, θ) (11) 简单起见，定义 Pm(t,γ, θ) = expθ(−β1 · gm(t,γ)−β2 · dm) (12) 式 (1) 的分母写成 S Ri (t,γ, θ) = ∑ j∈Ri expθ(β1 · gm(t,γ)−β2 · dm) (13) 求解 Jacobian 矩阵为 Jil = ∂ f(Ri , t,γ, θ) ∂tl ,l = 1,2,··· ,N (14) Jip = ∂ f(Ri , t,γ, θ) ∂γ , p = N +1,··· ,N +k+1 (15) Jiq = ∂ f(Ri , t,γ, θ) ∂θ ,q = N +k+2 (16) Jacobian 矩阵是一个 ND ∗ (N +k+2) 的矩阵，其 中 ND 是数据集中行程观测数目，N 是道路网中路段 数目，k 是双车道间多项式关系的阶次。 路段通行时间 t，车道间多项式关系参数 γ，比 例参数 θ 在第 v 次迭代更新为 t ≈ t v+1 = t v +ut (v) γ ≈ γ v+1 = γ v +uγ (v) θ ≈ θ v+1 = θ v +uθ (v) (17) u (v) = (ut (v) ,uγ (v) ,uθ (v) ) 得到待估参数在第 v 次迭代求解增量正规方程 时的更新方向为 ，增量正规方程为 (J (v)T J (v) +λI)u (v) = J (v)Tri (18) 当迭代结束后，式 (17) 所得 t 值即为所估计的 道路网路段通行时间，γ 为双车道间多项式关系参 数，θ 为表示司机对道路网感知程度的比例参数。 通过分析可以发现，上述函数非凸，可能有多 个局部最优点。在具体求解时，考虑将初始值默认 为整个道路网当前时段下的平均速度，能较快较好 地收敛到合适的最优的值。 3 实验结果与分析 我们采用纽约出租车行程数据集，数据由城市 出租车豪华轿车委员会 (New York City Taxi and Limousine Commission，NYTLC) 收集。其特点是每 个出租车都安装了 GPS 设备采集数据。纽约有北 美最大的出租车市场，12 779(2006 年) 辆黄色纪念 章出租车每年大约服务 2.4 亿人次。在曼哈顿，乘 坐出租车人数是所有出行人数的 25%[20]。数据集包 含 2010—2015 年出租车行程数据，其中包括行程开 始和结束 (OD 数据) 的地理位置、行程距离、时间 和票价等信息，而缺少出租车的确切轨迹。但是， 大量的数据 (一天 450 000～550 000 的记录数量) 可以推断出租车可能路线，并进一步估计道路网的 路段通行时间。 基于 Python 语言编程实现前面部分讨论的模 型。硬件配置为 i5 处理器，3.2 GHz CPU，4 GB 内 存。在实验中利用均方根误差 (root mean square error，RMSE) 和平均绝对百分比误差 (mean absolute percentage error，MAPE) 来评估估计结果： RMSE = vt 1 n ∑n i=1 (T Pr i −T Ob i ) 2 (19) MAPE = 1 n ∑n i=1 T Pr i −T Ob i T Ob i ×100% (20) 第 6 期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·793·
·794· 智能系统学报 第12卷 式中：T是模型估计的通行时间，T是实际观测的 1400 通行时间，n是通行观测数目。 1200 3.1测试数据和道路网 1000 实验中利用纽约出租车两周(3/2/2015一3/15/ 800 2015)的OD行程数据测试所提出的方法。实验区 600 400 域位于曼哈顿中央公园东南部一块1508m的范围， 200 相关道路网如图3所示，包含208个节点和386条 0 边。道路网中有348条道路是单向街道，38条是双 ESEAAEEOAEERERARE 向街道。图4、5分别展示了在该范围内工作日 时段 (3/2/2015和3/9/2015，周一)和周末(3/7/2015和 (a)研究区域日期为2015.3.7 3/14/2015,周六)的行程频数。通过统计和观察图 1600 4、5可以发现，该区域内工作日（周一）一小时内将 1400 近1200条行程数，周六大约1000条的行程数。且 1200 1000 每周同一天行程观测数近似服从同一分布。 800 600 400 200 时段 (b)研究区域日期为2015.3.14 (a)曼哈顿市中心地图b)曼哈顿道路网图 图5研究区域内周六每小时观测数目直方图 图3研究区域测试道路网：曼哈顿市中心 Fig.5 Histogram for number of hourly observations in the Fig.3 Test network of study region:midtown Manhattan study region on Saturday 1200 若实验数据以分钟为单位采样，行程数和信息 1000 量太少不能保证良好的统计意义。若以天为单位采 800 样，不具有良好的代表性和研究意义。因此实验以 600 小时为单位采样，从相应的数据中估计道路网通行 400 时间。 200 3.2结果与分析 为了验证提出的算法性能，在实验中引入了 w Zhan提出的单车道道路通行时间估计模型进行比 时段 (a)研究区域日期为2015.3.2 较。设计了两组实验，第一组实验分析单车道与双 1400 车道间不同多项式关系对估计道路网路段通行时间 1200 结果的影响，并确定效果最优的多项式关系，第二 1000 组为不同时段估计路段通行时间的实验。 800 3.2.1双车道间通行时间多项式关联关系模型下 600 的估计误差实验 400 为了验证2.3节所提双车道模型的有效性，以 200 3/2/2015-3/15/2015中9：00-10：00为研究时段分别 计算不同车道关系下的模型估计误差，实验结果如 时段 表1所示。通过观察可以发现，双车道模型整体上 (b)研究区域日期为2015.3.9 RMSE和MAPE相比Zhan等I提出的单车道方法 要低：当转换模型为二阶、三阶、四阶多项式时，一 图4研究区域内周一每小时观测数目直方图 Fig.4 Histogram for number of hourly observations in the 周中有半数以上的时间段双车道模型误差低于单车 study region on Monday 道模型：当转换模型为五阶、六阶多项式时，一周中
T Pr i T Ob 式中： 是模型估计的通行时间， i 是实际观测的 通行时间，n 是通行观测数目。 3.1 测试数据和道路网 实验中利用纽约出租车两周 (3/2/2015—3/15/ 2015) 的 OD 行程数据测试所提出的方法。实验区 域位于曼哈顿中央公园东南部一块 1 508 m2 的范围， 相关道路网如图 3 所示，包含 208 个节点和 386 条 边。道路网中有 348 条道路是单向街道，38 条是双 向街道。图 4、5 分别展示了在该范围内工作日 (3/2/2015 和 3/9/2015，周一) 和周末 (3/7/2015 和 3/14/2015，周六) 的行程频数。通过统计和观察图 4、5 可以发现，该区域内工作日 (周一) 一小时内将 近 1 200 条行程数，周六大约 1 000 条的行程数。且 每周同一天行程观测数近似服从同一分布。 若实验数据以分钟为单位采样，行程数和信息 量太少不能保证良好的统计意义。若以天为单位采 样，不具有良好的代表性和研究意义。因此实验以 小时为单位采样，从相应的数据中估计道路网通行 时间。 3.2 结果与分析 为了验证提出的算法性能，在实验中引入了 Zhan[14]提出的单车道道路通行时间估计模型进行比 较。设计了两组实验，第一组实验分析单车道与双 车道间不同多项式关系对估计道路网路段通行时间 结果的影响，并确定效果最优的多项式关系，第二 组为不同时段估计路段通行时间的实验。 3.2.1 双车道间通行时间多项式关联关系模型下 的估计误差实验 为了验证 2.3 节所提双车道模型的有效性，以 3/2/2015—3/15/2015 中 9:00–10:00 为研究时段分别 计算不同车道关系下的模型估计误差，实验结果如 表 1 所示。通过观察可以发现，双车道模型整体上 RMSE 和 MAPE 相比 Zhan 等 [14]提出的单车道方法 要低:当转换模型为二阶、三阶、四阶多项式时，一 周中有半数以上的时间段双车道模型误差低于单车 道模型;当转换模型为五阶、六阶多项式时，一周中 (a) ᰨ৴䶫ጮ͙ᓯప (b) ᰨ৴䶫䕿䌛㑽ప 图 3 研究区域测试道路网:曼哈顿市中心 Fig. 3 Test network of study region: midtown Manhattan 1 200 1 000 800 600 400 200 0 1 400 1 200 1 000 800 600 400 200 0 2:00 4:00 6:00 8:00 10:00 12:00 14:00 16:00 18:00 20:00 22:00 more 2:00 4:00 6:00 8:00 10:00 12:00 14:00 16:00 18:00 20:00 22:00 more ᬢ⃡ ᬢ⃡ (a) ⵀ⾢ࡦഋᬑͦ 2015.3.2 (b) ⵀ⾢ࡦഋᬑͦ 2015.3.9 䶽 䶽 图 4 研究区域内周一每小时观测数目直方图 Fig. 4 Histogram for number of hourly observations in the study region on Monday 1 600 1 400 1 200 1 000 800 600 400 200 0 1 400 1 200 1 000 800 600 400 200 0 2:00 4:00 6:00 8:00 10:00 12:00 14:00 16:00 18:00 20:00 22:00 more 2:00 4:00 6:00 8:00 10:00 12:00 14:00 16:00 18:00 20:00 22:00 more ᬢ⃡ ᬢ⃡ (a) ⵀ⾢ࡦഋᬑͦ 2015.3.7 (b) ⵀ⾢ࡦഋᬑͦ 2015.3.14 䶽 䶽 图 5 研究区域内周六每小时观测数目直方图 Fig. 5 Histogram for number of hourly observations in the study region on Saturday ·794· 智 能 系 统 学 报 第 12 卷
第6期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·795· 的RMSE和MAPE全都低于单车道模型结果。当 39.8%,11.7%,1.75%,2.6%,1.5%,5.4%。上述分析 双车道通行时间之间多现实转换模型取为六阶多项 证明，高阶多项式的双车道模型能够更好地刻画道 式时，周一到周六实验所得的RMSE和MAPE分别 路网的精细化程度，相比单车道模型能够更准确地 比单车道低3.45,5.33,0.21,0.13,0.06,0.41和 估计道路网通行时间。 表1不同车道关系下的模型估计误差 Table 1 Model estimation error in different lane conditions 两车道之间的关系 时间 误差 单车道间 二阶多项式 三阶多项式 四阶多项式 五阶多项式 六阶多项式 周一 RMSE 6.82 4.45 3.69 4.18 4.12 337 MAPE/% 40.00 36.50 31.40 35.20 34.70 30.20 周二 RMSE 9.15 4.29 4.3 4.27 3.86 3.82 MAPE/% 44.00 34.80 37.40 34.50 32.70 32.30 周三 RMSE 3.90 3.72 3.91 3.81 3.74 3.69 MAPE/% 32.65 31.60 32.60 31.60 31.40 30.90 周四 RMSE 3.65 3.65 3.63 3.63 3.64 3.52 MAPE/% 33.90 33.10 33.00 33.00 33.00 31.30 周五 RMSE 3.42 3.33 3.29 3.09 2.94 3.36 MAPE/% 32.10 30.90 30.60 106.0 105.0 30.60 周六 RMSE 2.71 3.09 2.31 3.09 2.38 2.30 MAPE/% 37.70 37.70 31.90 37.90 33.40 32.30 3.2.2单车道模型与双车道六阶多项式关联关系 中每周同一天数据的80%作为训练样本，剩下 模型估计道路网通行时间的实验 20%第2周的数据作为测试样本，估计一天中4个 该实验分为训练和测试两个阶段，首先基于第 时间段(9：00一10：00,13：00一14：00,19：00-20：00， 3节训练求出道路网路段通行时间t,双车道间六阶 21:00一22：00)的道路网路段通行时间。分别采用 多项式参数？、03个值，然后在测试阶段输入新的 Zhan单车道模型和本文双车道为六阶多项式关系 OD行程记录，并根据式(6)求出该行程记录的期望 的模型对道路路段通行时间进行估计，通过观察表 时间和误差。 2可见，双车道模型在更多数据情况下结果都优于 基于两周的GPS数据(3/2/2010-3/15/2010)，其 单车道模型。 表2模型估计误差 Table 2 Model estimation error 时间段 日期 误差 9:00-10:00 13:00-14:00 19:00-20:00 21:00-22:00 单车道双车道六阶多项式单车道双车道六阶多项式单车道双车道六阶多项式单车道双车道六阶多项式 周 RMSE/min 6.82 3.37 4.97 4.88 3.95 3.14 3.90 3.58 MAPE/%40.00 30.20 47.10 38.90 39.10 36.00 38.20 35.20 周二 RMSE/min 9.15 3.82 5.50 4.76 5.34 5.60 3.52 2.87 MAPE%44.00 32.30 44.50 37.40 50.80 45.90 36.10 30.20 周三RMSE/min3.90 3.69 4.75 4.41 5.46 5.31 35.80 4.13 MAPE/%32.65 30.90 41.34 39.50 45.80 40.80 22.00 135.00 周四RMSE/min3.65 3.52 4.79 4.05 5.37 2.62 3.93 2.56 MAPE/%33.90 31.30 39.50 34.50 44.90 29.60 43.50 31.50 周五RMSE/min342 3.36 4.00 3.54 5.49 3.80 7.15 2.42 MAPE%32.10 30.60 37.90 31.40 43.40 32.00 52.60 31.60 周六 RMSE/min 2.71 2.30 3.57 3.34 10.70 3.88 7.50 4.48 MAPE/%37.70 32.30 38.80 36.30 50.90 33.00 51.00 39.30 周日RMSE/min293 2.38 17.20 4.27 3.30 2.79 12.90 2.92 MAPE/%38.50 33.40 80.40 37.10 46.10 36.30 62.80 34.30
的 RMSE 和 MAPE 全都低于单车道模型结果。当 双车道通行时间之间多现实转换模型取为六阶多项 式时，周一到周六实验所得的 RMSE 和 MAPE 分别 比单车道低 3.45，5.33，0.21，0.13，0.06，0.41 和 39.8%，11.7%，1.75%，2.6%，1.5%，5.4%。上述分析 证明，高阶多项式的双车道模型能够更好地刻画道 路网的精细化程度，相比单车道模型能够更准确地 估计道路网通行时间。 3.2.2 单车道模型与双车道六阶多项式关联关系 模型估计道路网通行时间的实验 该实验分为训练和测试两个阶段，首先基于第 3 节训练求出道路网路段通行时间 t，双车道间六阶 多项式参数 γ、θ 3 个值，然后在测试阶段输入新的 OD 行程记录，并根据式 (6) 求出该行程记录的期望 时间和误差。 基于两周的 GPS 数据 (3/2/2010-3/15/2010)，其 中每周同一天数据的 80% 作为训练样本，剩下 20% 第 2 周的数据作为测试样本，估计一天中 4 个 时间段 (9:00—10:00，13:00—14:00，19:00—20:00， 21:00—22:00) 的道路网路段通行时间。分别采用 Zhan[14]单车道模型和本文双车道为六阶多项式关系 的模型对道路路段通行时间进行估计，通过观察表 2 可见，双车道模型在更多数据情况下结果都优于 单车道模型。 表 1 不同车道关系下的模型估计误差 Table 1 Model estimation error in different lane conditions 时间 误差 两车道之间的关系 单车道[14] 二阶多项式 三阶多项式 四阶多项式 五阶多项式 六阶多项式 周一 RMSE 6.82 4.45 3.69 4.18 4.12 3.37 MAPE/% 40.00 36.50 31.40 35.20 34.70 30.20 周二 RMSE 9.15 4.29 4.3 4.27 3.86 3.82 MAPE/% 44.00 34.80 37.40 34.50 32.70 32.30 周三 RMSE 3.90 3.72 3.91 3.81 3.74 3.69 MAPE/% 32.65 31.60 32.60 31.60 31.40 30.90 周四 RMSE 3.65 3.65 3.63 3.63 3.64 3.52 MAPE/% 33.90 33.10 33.00 33.00 33.00 31.30 周五 RMSE 3.42 3.33 3.29 3.09 2.94 3.36 MAPE/% 32.10 30.90 30.60 106.0 105.0 30.60 周六 RMSE 2.71 3.09 2.31 3.09 2.38 2.30 MAPE/% 37.70 37.70 31.90 37.90 33.40 32.30 表 2 模型估计误差 Table 2 Model estimation error 日期 误差 时间段 9:00—10:00 13:00—14:00 19:00—20:00 21:00—22:00 单车道 双车道六阶多项式 单车道 双车道六阶多项式 单车道 双车道六阶多项式 单车道 双车道六阶多项式 周一RMSE/min 6.82 3.37 4.97 4.88 3.95 3.14 3.90 3.58 MAPE/% 40.00 30.20 47.10 38.90 39.10 36.00 38.20 35.20 周二RMSE/min 9.15 3.82 5.50 4.76 5.34 5.60 3.52 2.87 MAPE/% 44.00 32.30 44.50 37.40 50.80 45.90 36.10 30.20 周三RMSE/min 3.90 3.69 4.75 4.41 5.46 5.31 35.80 4.13 MAPE/% 32.65 30.90 41.34 39.50 45.80 40.80 22.00 135.00 周四RMSE/min 3.65 3.52 4.79 4.05 5.37 2.62 3.93 2.56 MAPE/% 33.90 31.30 39.50 34.50 44.90 29.60 43.50 31.50 周五RMSE/min 3.42 3.36 4.00 3.54 5.49 3.80 7.15 2.42 MAPE/% 32.10 30.60 37.90 31.40 43.40 32.00 52.60 31.60 周六RMSE/min 2.71 2.30 3.57 3.34 10.70 3.88 7.50 4.48 MAPE/% 37.70 32.30 38.80 36.30 50.90 33.00 51.00 39.30 周日RMSE/min 2.93 2.38 17.20 4.27 3.30 2.79 12.90 2.92 MAPE/% 38.50 33.40 80.40 37.10 46.10 36.30 62.80 34.30 第 6 期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·795·
·796· 智能系统学报 第12卷 除了时间段(3月9日周三21：00-22：00)，双车 我们用道路网路段通行速度而不是道路网路段 道模型路段通行时间估计结果的MAPE低于40%.可 通行时间直观表示估计结果，图6表示周一、周二 以观察到单车道模型和双车道模型在周三21：00一 9:00一10：00，路段估计时间直方图和行程观测时间 22:00误差值最大。可发现周三(3/11/2015)有纽约 与估计时间之间的关系图，其中X轴表示路段通行 洋基对战巴尔的摩金莺的橄榄球比赛，比赛结束后 速度，Y轴表示该速度的路段数目。子图中X轴为 可能导致大量拥堵以及密集人群流动，该事件可能 行程观测时间，Y轴为模型估计时间。图7表示周 与误差结果有较大关系。且双车道模型遇到异常情 三，周六13：00一14：00的关系。其他时间段的关系 况时，效果更加稳健，其结果比单车道模型低94%。 与其相似，不多作赘述。 30 2 05 15 、 5 5 24681012141618202224262830 5 101520 2530 行程观测时间/min (a)周一9：00-10：00 b)周一行程观测时间与估计时间关系 30 。 35 25 3 20 10 51 24681012141618202224262830 101520 2530 行程观测时间/min (c)周二9：00-10：00 (@周二行程观测时间与估计时间关系 图6周一、周二路段估计时间直方图和行程观测时间与估计时间之间的关系 Fig.6 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Monday,Tues- day 30 35 25 20 15 0 5 5 024681012141618202224262830 0 101520 2530 行程观测时间min (a)周三13：00-14：00 6)周三行程观测时间与估计时间关系 40 30 35 25 0 25 20 20 10 10 5 24681012141618202224262830 101520 2530 行程观测时间/min (c)周六13：00-14：00 ()周六行程观测时间与估计时间关系 图7周三，周六路段估计时间直方图和通行观测时间与估计时间之间的关系 Fig.7 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Wednesday, Saturday
除了时间段 (3 月 9 日周三 21:00—22:00)，双车 道模型路段通行时间估计结果的 MAPE 低于 40%，可 以观察到单车道模型和双车道模型在周三 21:00— 22:00 误差值最大。可发现周三 (3/11/2015) 有纽约 洋基对战巴尔的摩金莺的橄榄球比赛，比赛结束后 可能导致大量拥堵以及密集人群流动，该事件可能 与误差结果有较大关系。且双车道模型遇到异常情 况时，效果更加稳健，其结果比单车道模型低 94%。 我们用道路网路段通行速度而不是道路网路段 通行时间直观表示估计结果，图 6 表示周一、周二 9:00—10:00, 路段估计时间直方图和行程观测时间 与估计时间之间的关系图，其中 X 轴表示路段通行 速度，Y 轴表示该速度的路段数目。子图中 X 轴为 行程观测时间，Y 轴为模型估计时间。图 7 表示周 三，周六 13:00—14:00 的关系。其他时间段的关系 与其相似，不多作赘述。 30 25 20 15 10 5 㻮≷Ⱊ (a) ঔ̬ 9:00−10:00 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 (b) 周一㵸⼷㻮≷ᬢ䬠̺ќ䃍ᬢ䬠ڟ㈧ 30 25 20 15 10 5 0 5 10 15 20 25 30 㹼〻㿲⍻ᰦ䰤/min 㹼〻ՠ䇑ᰦ䰤/min 40 35 30 25 20 15 10 5 㻮≷Ⱊ (c) ঔθ 9:00−10:00 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 (d) 周θ㵸⼷㻮≷ᬢ䬠̺ќ䃍ᬢ䬠ڟ㈧ 㹼〻㿲⍻ᰦ䰤/min 㹼〻ՠ䇑ᰦ䰤/min 0 5 10 15 20 25 30 30 25 20 15 10 5 图 6 周一、周二路段估计时间直方图和行程观测时间与估计时间之间的关系 Fig. 6 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Monday, Tuesday 40 35 30 25 20 15 10 5 㻮≷Ⱊ (c) ঔڙ 13:00−14:00 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 30 25 20 15 10 5 0 5 10 15 20 25 30 (d) ঔڙ㵸⼷㻮≷ᬢ䬠̺ќ䃍ᬢ䬠ڟ㈧ 㵸⼷㻮≷ᬢ䬠/min 㵸⼷ќ䃍ᬢ䬠/min 45 40 35 30 25 20 15 10 5 㻮≷Ⱊ (a) ঔ̵ 13:00−14:00 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 30 25 20 15 10 5 0 5 10 15 20 25 30 (b) ঔ̵㵸⼷㻮≷ᬢ䬠̺ќ䃍ᬢ䬠ڟ㈧ 㵸⼷㻮≷ᬢ䬠/min 㵸⼷ќ䃍ᬢ䬠/min 图 7 周三，周六路段估计时间直方图和通行观测时间与估计时间之间的关系 Fig. 7 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Wednesday, Saturday ·796· 智 能 系 统 学 报 第 12 卷
第6期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·797· 30 20 10 10 5 5 24681012141618202224262830 0 101520 2530 行程观测时间min (a)周五21：00-22：00 (b)周五行程观测时间与估计时间关系 30 25 20 10 24681012141618202224262830 101520 2530 行程观测时间min (c)周日21：00-22：00 (@周日行程观测时间与估计时间关系 图8周五、周日路段估计时间直方图和通行观测时间与估计时间之间的关系 Fig.8 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Friday,Sunday 由于路段通行时间是以小时为单位估计的，所 899-917. 以一小时内道路的变化也会导致模型的误差(Fos [2]ZHANG X,ZHANG B,LIU L,et al.Estimating foliar nitro- gerau和Fukuda2。司机之间的选择偏好（例如， gen concentration with hyperspectral remote sensing 一些司机驾驶速度快，偏好选择短路径，一些司机 image[C]//Third International Asia-Pacific Environmental 驾驶速度慢，偏好采取相对较长的路径等)也可能 Remote Sensing Remote Sensing of the Atmosphere,Ocean. 导致误差。观察到某些行程在测试的道路网中长 Environment,and Space.Beijing,2003:187-193. 达20min,这使得在路径选择中有很多不确定性， [3]WU CC,LEE W M G.Control of vaporous naphthalene by 从而导致了一些误差。 scrubbing with surfactants[J].Journal of environmental en- gineering,2004,130(3):276-281. 4结束语 [4]PARK D,RILETTL.Forecasting multiple-period freeway 本文提出了一种基于出租车GPS-OD数据来 link travel times using modular neural networks[J].Trans- 估计城市道路网通行时间的新模型。为了更精细地 portation research record:journal of the transportation re- search board.1998(1617):163-170 刻画道路网，该模型基于双车道估计行程期望时 [5]LI R,ROSE G.Incorporating uncertainty into short-term 间，为了避免训练数据量不足而导致的过拟合问 travel time predictions[J].Transportation research part c: 题，建立了双车道间通行时间多项式关联关系模 emerging technologies,2011,19(6):1006-1018. 型，并通过最小化行程期望时间和行程观测时间之 [6]YEON J,ELEFTERIADOU L,LAWPHONGPANICH S. 间的误差来估计道路网通行时间。实验结果表明本 Travel time estimation on a freeway using discrete time 文提出的方法能够有效地估计道路网每小时通行时 Markov chains[J].Transportation research part B:methodo- 间。为充分利用城市出租车数据估计道路网时间提 1 ogical,2008,42(4:325-338. 供新的可能性。在下一步工作中，我们将利用GPS [7]HASAN S,CHOUDHURY C,BEN-AKIVA M,et al.Mod- 数据进一步研究城市交通流量的估计问题。 eling of travel time variations on urban links in London[J]. 参考文献： Transportation research record:journal of the transportation research board,2011(2260):1-7. [1]COIFMAN B,CASSIDY M.Vehicle reidentification and [8]HERRERA J C,WORK D B,HERRING R,et al.Evalu- travel time measurement on congested freeways[J].Trans- ation of traffic data obtained via GPS-enabled mobile portation research part a:policy and practice,2002,36(10): phones:the mobile century field experiment[J].Transporta-
由于路段通行时间是以小时为单位估计的，所 以一小时内道路的变化也会导致模型的误差 (Fosgerau 和 Fukuda[21] )。司机之间的选择偏好 (例如， 一些司机驾驶速度快，偏好选择短路径，一些司机 驾驶速度慢，偏好采取相对较长的路径等) 也可能 导致误差。观察到某些行程在测试的道路网中长 达 20 min，这使得在路径选择中有很多不确定性， 从而导致了一些误差。 4 结束语 本文提出了一种基于出租车 GPS-OD 数据来 估计城市道路网通行时间的新模型。为了更精细地 刻画道路网，该模型基于双车道估计行程期望时 间，为了避免训练数据量不足而导致的过拟合问 题，建立了双车道间通行时间多项式关联关系模 型，并通过最小化行程期望时间和行程观测时间之 间的误差来估计道路网通行时间。实验结果表明本 文提出的方法能够有效地估计道路网每小时通行时 间。为充分利用城市出租车数据估计道路网时间提 供新的可能性。在下一步工作中，我们将利用 GPS 数据进一步研究城市交通流量的估计问题。 参考文献： COIFMAN B, CASSIDY M. Vehicle reidentification and travel time measurement on congested freeways[J]. Transportation research part a: policy and practice, 2002, 36(10): [1] 899–917. ZHANG X, ZHANG B, LIU L, et al. Estimating foliar nitrogen concentration with hyperspectral remote sensing image[C]//Third International Asia-Pacific Environmental Remote Sensing Remote Sensing of the Atmosphere, Ocean, Environment, and Space. Beijing, 2003: 187–193. [2] WU C C, LEE W M G. Control of vaporous naphthalene by scrubbing with surfactants[J]. Journal of environmental engineering, 2004, 130(3): 276–281. [3] PARK D, RILETT L. Forecasting multiple-period freeway link travel times using modular neural networks[J]. Transportation research record: journal of the transportation research board, 1998(1617): 163–170. [4] LI R, ROSE G. Incorporating uncertainty into short-term travel time predictions[J]. Transportation research part c: emerging technologies, 2011, 19(6): 1006–1018. [5] YEON J, ELEFTERIADOU L, LAWPHONGPANICH S. Travel time estimation on a freeway using discrete time Markov chains[J]. Transportation research part B: methodological, 2008, 42(4): 325–338. [6] HASAN S, CHOUDHURY C, BEN-AKIVA M, et al. Modeling of travel time variations on urban links in London[J]. Transportation research record: journal of the transportation research board, 2011(2260): 1–7. [7] HERRERA J C, WORK D B, HERRING R, et al. Evaluation of traffic data obtained via GPS-enabled mobile phones: the mobile century field experiment[J]. Transporta- [8] 20 15 10 5 30 25 20 15 10 5 㻮≷Ⱊ 㻮≷Ⱊ (a) ঔπ− 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 (c) ঔᬑ 21:00−22:00 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 30 25 20 15 10 5 0 5 10 15 20 25 30 0 5 10 15 20 25 30 (b) ঔπ㵸⼷㻮≷ᬢ䬠̺ќ䃍ᬢ䬠ڟ㈧ (d) ঔᬑ㵸⼷㻮≷ᬢ䬠̺ќ䃍ᬢ䬠ڟ㈧ 30 25 20 15 10 5 㵸⼷㻮≷ᬢ䬠/min 㵸⼷㻮≷ᬢ䬠/min 㵸⼷ќ䃍ᬢ䬠/min 㵸⼷ќ䃍ᬢ䬠/min 图 8 周五、周日路段估计时间直方图和通行观测时间与估计时间之间的关系 Fig. 8 Histogram of estimated link speed and correlation plot of observed and estimated path travel time for Friday, Sunday 第 6 期 黄顺伦，等：出租车数据的城市道路网路段通行时间估计方法 ·797·
·798· 智能系统学报 第12卷 tion research part c:emerging technologies,2010,18(4): [C]//Transportation Research Board 91st Annual Meeting. 568-583 Washington DC.USA.2012(12-2097) [9]ZHAN X,ZHENG Y,Yi X,et al.Citywide traffic volume [21]FOSGERAU M,FUKUDA D.Valuing travel time variab- estimation using trajectory data[J].IEEE transactions on ility:Characteristics of the travel time distribution on an knowledge and data engineering,2017,29(2):272-285. urban road[J].Transportation research part c:emerging [10]ZHENG F,VAN ZUYLEN H.Urban link travel time es- technologies,2012,24(0):83-101. timation based on sparse probe vehicle data[].Transporta- [22]孙锋，黄玲，叶盈，等.混行条件下直线式公交站点停靠车 tion research part c:emerging technologies,2013,31(0): 辆数优化J].哈尔滨工程大学学报，2015,36(2)：152- 145-157. 155. [11]HUNTER T,HERRING R,ABBEEL P,et al.Path and SUN Feng,HUANG Ling,YE Ying,et al.Optimizing the travel time inference from GPS probe vehicle data[J].NIPS number of buses stopping at on-line stops under mixed analyzing networks and learning with graphs,2009,12(1). traffic conditions[J].Journal of Harbin Engineering Uni- [12]HERRING R,HOFLEITNER A,ABBEEL P,et al.Estim- versity,2015,36(2:152-155. ating arterial traffic conditions using sparse probe data [23]徐程，曲昭伟，陶鹏飞，等.动态交通数据异常值的实时筛 [C]//13th International IEEE Conference on Intelligent 选与恢复方法[J.哈尔滨工程大学学报，2016,37(2)： Transportation Systems.Madeira Island,Portugal,2010: 211-217. 929-936 XU Cheng,QU Zhaowei,TAO Pengfei,et al.Methods of [13]Taxi data from new york taxi and limousine commission. real-time screening and reconstruction for dynamic traffic [2016-05-14]http://www.nyc.gov/html/tlc/html/home/ abnormal data[J].Journal of Harbin Engineering Uni- home.shtml. versity,2016,37(2):211-217. [14]ZHAN X,HASAN S,UKKUSURI S V,et al.Urban link 作者简介： travel time estimation using large-scale taxi data with par- 黄顺伦，女，1993年生，硕士研究 tial information[J].Transportation research part c:emer- 生，主要研究方向为交通数据分析、机 ging technologies,2013,33(0):37-49. 器学习。 [15]ZHAN X,UKKUSURI S V,YANG C.A Bayesian mix- ture model for short-term average link travel time estima- tion using large-scale limited information trip-based data[J].Automation in construction,2016,72:237-246. 16]YEN J Y.Finding the k shortest loopless paths in a net- 杜春，男，1983年生，讲师，博士 work[J].Management science,1971,17(11):712-716. 主要研究方向为机器学习、模式识别、 [17]DAGANZO C.Multinomial probit:the theory and its ap 图像处理。 plication to demand forecasting[M].Elsevier,2014. [18]CHEN Y,OLIVER D S.Levenberg-Marquardt forms of the iterative ensemble smoother for efficient history match- ing and uncertainty quantification[J].Computational geosciences,.2013,17(4):689-703. 宋宝泉，男，1980年生，讲师，博 [19]BONNANS J F,GILBERT J C,LEMARECHAL C,et al. 土，主要研究方向为大数据管理、智能 信息处理。 Numerical optimization:theoretical and practical aspects [M].Springer Science and Business Media,2013 20]KING D A,PETERS J R,DAUS M W.Taxicabs for im- proved urban mobility:are we missing an opportunity
tion research part c: emerging technologies, 2010, 18(4): 568–583. ZHAN X, ZHENG Y, Yi X, et al. Citywide traffic volume estimation using trajectory data[J]. IEEE transactions on knowledge and data engineering, 2017, 29(2): 272–285. [9] ZHENG F, VAN ZUYLEN H. Urban link travel time estimation based on sparse probe vehicle data[J]. Transportation research part c: emerging technologies, 2013, 31(0): 145–157. [10] HUNTER T, HERRING R, ABBEEL P, et al. Path and travel time inference from GPS probe vehicle data[J]. NIPS analyzing networks and learning with graphs, 2009, 12(1). [11] HERRING R, HOFLEITNER A, ABBEEL P, et al. Estimating arterial traffic conditions using sparse probe data [C]//13th International IEEE Conference on Intelligent Transportation Systems. Madeira Island, Portugal, 2010: 929–936. [12] Taxi data from new york taxi and limousine commission. [2016-05-14] http://www.nyc.gov/html/tlc/html/home/ home.shtml. [13] ZHAN X, HASAN S, UKKUSURI S V, et al. Urban link travel time estimation using large-scale taxi data with partial information[J]. Transportation research part c: emerging technologies, 2013, 33(0): 37–49. [14] ZHAN X, UKKUSURI S V, YANG C. A Bayesian mixture model for short-term average link travel time estimation using large-scale limited information trip-based data[J]. Automation in construction, 2016, 72: 237–246. [15] YEN J Y. Finding the k shortest loopless paths in a network[J]. Management science, 1971, 17(11): 712–716. [16] DAGANZO C. Multinomial probit: the theory and its application to demand forecasting[M]. Elsevier, 2014. [17] CHEN Y, OLIVER D S. Levenberg–Marquardt forms of the iterative ensemble smoother for efficient history matching and uncertainty quantification[J]. Computational geosciences, 2013, 17(4): 689–703. [18] BONNANS J F, GILBERT J C, LEMARÉCHAL C, et al. Numerical optimization: theoretical and practical aspects [M]. Springer Science and Business Media, 2013. [19] KING D A, PETERS J R, DAUS M W. Taxicabs for improved urban mobility: are we missing an opportunity [20] [C]//Transportation Research Board 91st Annual Meeting. Washington DC, USA, 2012 (12-2097). FOSGERAU M, FUKUDA D. Valuing travel time variability: Characteristics of the travel time distribution on an urban road[J]. Transportation research part c: emerging technologies, 2012, 24(0): 83–101. [21] 孙锋, 黄玲, 叶盈,等. 混行条件下直线式公交站点停靠车 辆数优化[J]. 哈尔滨工程大学学报, 2015, 36(2): 152– 155. SUN Feng, HUANG Ling, YE Ying, et al. Optimizing the number of buses stopping at on-line stops under mixed traffic conditions[J]. Journal of Harbin Engineering University, 2015, 36(2): 152–155. [22] 徐程, 曲昭伟, 陶鹏飞,等. 动态交通数据异常值的实时筛 选与恢复方法[J]. 哈尔滨工程大学学报, 2016, 37(2): 211–217. XU Cheng, QU Zhaowei, TAO Pengfei, et al. Methods of real-time screening and reconstruction for dynamic traffic abnormal data[J]. Journal of Harbin Engineering University, 2016, 37(2): 211–217. [23] 作者简介： 黄顺伦，女，1993 年生，硕士研究 生，主要研究方向为交通数据分析、机 器学习。 杜春，男，1983 年生，讲师，博士， 主要研究方向为机器学习、模式识别、 图像处理。 宋宝泉，男，1980 年生，讲师，博 士，主要研究方向为大数据管理、智能 信息处理。 ·798· 智 能 系 统 学 报 第 12 卷