【面向公共交通的路径匹配与轨迹重建分析案例13000字】

面向公共交通的路径匹配与轨迹重建分析案例目录TOC\o"1-3"\h\u30366面向公共交通的路径匹配与轨迹重建分析案例 1125911.1路径匹配 169271.1.1公交、地铁路线匹配 1331.1.2出租车地图匹配 6231781.2行程划分 1065001.2.1轨迹时间-里程表达 10291261.2.2核密度计算 12277181.2.3驻留点检测 13272651.2.4轨迹段语义化 14318811.3轨迹重建 15241811.3.1启发式优化问题 15302331.3.2搜索策略选择 1698921.3.3轨迹点位置优化模型 17244601.3.4数据模拟与模型精度评定 186151.3.5轨迹重建结果分析 20路径匹配公交、地铁路线匹配基站扇区映射方法对轨迹和公共交通路线进行匹配，首先要对轨迹点和路线点的相似性进行度量。在本研究中，为了准确反映蜂窝网络中的移动台（即持有手机设备）在对应基站领域内可能位置以及位于这一位置的概率，首先根据天线朝向确定各基站对应的信号覆盖范围，再根据二维正态分布假设计算覆盖范围内不同位置的概率，作为轨迹点相似性的度量。手机信令轨迹中每个记录点以基站位置来近似代替终端设备的实际位置，这意味着手机设备只是位于相应手机基站的地理覆盖范围内。在实际情况中，一个基站可能服务多个区域，一个区域也可能被多个基站服务，不同的基站的覆盖范围有所重叠，根据不同物理条件和环境有所变化。目前的研究通常假设基站的服务范围为固定的区域，如六边形假设、泰森多边形假设、圆形假设和扇形假设ADDINCNKISM.Ref.{CB26D4A659CF4f32BAD52C382CEE9267}(宋璐，2015)，如图4.1。考虑到手机基站数据中包含天线的航向角，在本文中采用扇形假设。通常情况下，每个基站包含3根朝向不同的发射天线，覆盖以基站为中心的不同方向范围，基站天线的朝向字段可以从基站工参表中直接获取。将基站朝向为中心轴线，向两侧各延伸60度，以给定半径r确定天线对应的基站扇形区域，其中r取一般城区内的基站覆盖半径500m。1）六边形假设2）泰森多边形假设3）圆形假设4）扇形假设图4.1不同基站覆盖范围假设Figure4.1DifferentCoverageofbasestationshypnosis扇区内匹配度计算基站覆盖范围能够确定手机用户可能出现的位置，但考虑到信号传输和负载平衡，手机有更大的概率连接与之空间上更接近的基站；同样，对于每一个基站来说，距离其所在位置越近越有可能是与之交互手机的实际位置。对手机信令轨迹中的每一个轨迹点，其基站位置可视为含有系统误差的设备实际位置观测值，这一观测值在真实位置附近的散布满足二维空间的正态分布。基站对应的平面位置(X,Y)是一个二维随机变量，可以认为它服从一个二元正态分布，其中Xp其中，x0,y0为基站位置，p(图4.2基站邻域内的点匹配度变化Figure4.2VariationofmatchingdegreeintheneighborhoodofBTS按照定义，(X,Y)落在以sim其中，σ为点分布的标准差。类似地，我们给出点匹配度的定义：sim其中p0,p1分别属于道路位置点集合轨迹时空点集，d(p0,p1)表示两点的欧几里得距离。sim图4.3扇区内匹配度随距离的衰减Figure4.3TheattenuationofmatchingdegreewithdistanceinBTSsector周期最长公共子序列传统的最长公共子序列（longestcommonsubsequence，LCSS）是针对字符串序列匹配的方法，是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。给定一条手机信令轨迹序列T和公交路线序列RT=R=其中,tni,ptni为T在时刻tni的第i个轨迹点ptni,prsimPntSectorptni在确定轨迹点匹配规则后，定义一个递归函数LCSSTn,Rm来求解两条轨迹LCSS从起始时刻i=1,j=1到终止时刻i=n,j=m逐个计算LCSST动态规划求解方法求解LCSS方式包括穷举法和动态规划。对于长度分别为n和m和手机信令轨迹序列T和公交路线序列R来说穷举法就是针对T的每一个子序列T'，检测它是否能和R的某条子序列R'相匹配从而判断T',R'是否是T和R的公共子序列。当穷举完T和R动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。表4.1周期最长公共子序列匹配算法流程Table4.1Crossvalidationresultsofclassificationmodel算法周期最长公共子序列匹配输入:手机信令手机信令轨迹T和公交路线序列R输出:最长公共子序列OPA1:row=LenT2:foreachentryD[i,j]inDdo3:D4:foriin1torowdo5:ifj+ext>colthen6:col+=Len7:forjin1tocoldo8:AccSim=D9:D10:OPA=∅,i=Len11:whilei>0andj>0do12:ifDi,j=D13:Insert(T.Pnti,R.Pntj%LenR14:elseifDi,j=D15:Insert(T.Pnti−1,"−")to16:elseifDi,j=D17:Insert("−",R.Pnt(j−1)%LenR)18:whilej>0do19:Insert("−",R.Pnt(j−1)%LenR)20:whilei>0do21:Insert(T.Pnti−1,"−")to出租车地图匹配与公交、地铁等沿固定路线运动的公共交通模式不同，出租车辆的活动范围在整个城市路网区域，而非局限于特定路线上。因此，用于公交、地铁模式匹配的序列方法并不直接适用于出租车轨迹匹配。因此，本节针对手机数据的低时空精度特点，以及城市复杂路网匹配准确率较低的问题，采用隐马尔科夫模型（HiddenMarkovModel,HMM）对出租车模式的个体轨迹进行地图匹配。HMM模型描述了在已知模型参数的情况下，寻找产生某个观测序列的最优隐藏状态序列的过程。结合轨迹数据而言，观测序列即为个体对象的移动轨迹，最优隐藏状态序列即为个体对象真实的移动路径。地图匹配的主要过程包括以下步骤：确定HMM模型隐藏状态空间，得到候选路段集；利用轨迹点和路段的信息及空间关系，计算发射概率和转移概率等HMM模型参数；利用动态规划算法解算HMM模型，将移动轨迹匹配到路网，得到用户在城市路网中的移动路径。搜索空间选择路径匹配实质是从研究区域内路网道路线的隐藏状态空间查找具有拓扑联通性的最优道路序列。但考虑到城市路网复杂的复杂性给模型时间复杂度的影响，需要先对参与匹配的道路集进行初筛选。一般采用设置搜索区域的方式确定初选路段，搜索区域主要用于解决在智能交通领域任意两个节点间最短路径算法过程中算法复杂度较高而设计，选择正确的搜索区域有助于减少算法计算量，同时提高算法的匹配效率。本文中选择椭圆限制搜索区域作为搜索区域。椭圆限制搜索区域能够将搜索节点限制在一定范围内，大幅度减少地图匹配的搜索规模，将相邻的手机信令轨迹点pntsx[其中，a和b分别为椭圆中心位置的x和y坐标，a=xs+xd2，b=ys+y图4.4中为相邻两手机信令轨迹点构造的椭圆限制搜索区域。两轨迹点分别视为地图匹配的源节点和目标节点，可以看出椭圆限制搜索区域范围覆盖了从源节点到目标节点潜在的最优路径；同时，椭圆搜索区域内网络节点与边的数量相较于整个道路网络仅占很小的部分，能够有效压缩地图匹配最优路径的搜索时间。图4.4基于椭圆搜索空间的备选路径选择Figure4.4Candidaterouteselectionbasedonellipsesearchspace路段发射概率发射概率Ppntiϕ因此，我们采用中的相似度算子simpnt0,pnt1来度量基站位置位于pnt0的轨迹点，其实际位置落在候选路径上pnt1P其中，bts为手机基站的位置，并有sim式中，Ppntiϕi的值越高，则轨迹点图4.5基站扇区与路段发射概率Figure4.5BTSsectorandroutetransmissionprobability如图4.5中所示，当基站的覆盖扇区与路网中的候选路段存在交集时，该候选路段的发射概率为simpnt0,pnt1沿候选路段路段转移概率状态转移概率表示前一个手机信令轨迹点的候选点转移至下一个手机信令轨迹点候选点的可能性，记为pcp其中，对参数α和Dα=DXii+1表示两个手机信令轨迹点pnti动态规划路径匹配如果最优路径在t时刻经过结点𝑖𝑡∗，则从结点𝑖𝑡∗到终点𝑖𝑇∗的后半部分路径必须相对从其它结点到𝑖𝑇∗的所有路径为最优路径。本文使用动态规划方法对马尔科夫模型进行解码(Bloitetal.2008)，在每一步的所有选择都保存了前续所有步骤到当前步骤当前选择的最小总代价（或者最大价值）以及当前代价的情况下前继步骤的选择。依次计算完所有步骤后，通过回溯的方法找到最优选择路径。给定落入椭圆搜索空间的备选路段集ϕj={rt1,…引入矩阵CM×N，其元素为Cin表示第n个轨迹点在待选路段ϕi对于首个轨迹点pnt1C当2≤n≤N时：CD递推结束后，确定最后一个轨迹点的最优匹配路段：x从该最优匹配开始，依次从DM×N中回溯出前一个轨迹点的最优匹配路段xN−1直至首个最优匹配路段x1行程划分轨迹行程段划分（TrajectorySegmentation）是个体移动行为研究的关键问题，其主要目的是把原始轨迹分割成多条子轨迹，使得子轨迹在其内部保持轨迹特征和语义上的一致性。针对使用Cell-ID定位的手机信令数据，大多数已有研究通过对数据中高频重复的基站和持续长时间的停留进行检测并设定阈值来划分轨迹的行程段，此外部分研究采用空间聚类的方式来探测行程的划分点。以上方法关注与轨迹点的聚集模式，但没有对划分行程段的“停留点”赋予特定的语义信息。面向上一章从海量手机信令轨迹数据集中提取的司乘人员手机信令轨迹，本章提出了一种基于时空核密度估计的轨迹行程分段方法。首先将二维平面坐标表达的手机信令轨迹映射到时间-里程系中，再进行非参数核密度估计检测密度曲线波峰波谷位置的停留点，最后结合公共交通站点数据和基于规则对停留点进行语义判别，并进行手机信令轨迹的行程段划分。轨迹时间-里程表达时空轨迹数据一般以“时间-坐标”的形式进行存储与表达，常以时空棱柱体的形式来体现个体位置随时间的变化，并反映起点、终点、出发时刻、结束时刻、运动速度和活动范围等个体运动特征。但是移动轨迹的高维组织结构不利于提取移动对象的移动行为统计特征，尤其是在轨迹大数据的范畴下，更是会降低数据分析和处理的效率；同时手机信令轨迹本身的空间不确定性也会将误差传递到后续的时空分析中。因此，本研究针对司乘人员轨迹数据，采用高效的移动对象轨迹表示方式，即时间-里程表达。移动轨迹的时间-里程表达，是对个体对象相对于给定参考点沿公交路线的向前运动的表示。首先设定轨迹的起始时刻（首条记录时间戳）作为时间参考点t0，设定公交路线的始发站坐标作为空间参考点x0,d式中，di是轨迹点与参考点之间的距离，θi是轨迹点距正北方向的旋转角度（按顺时针方向）,Trj基于移动轨迹的极坐标表示方式，可以探索用户和参考点之间的距离/时间关联性。提取轨迹序列中的距离和时间值并绘制散点图（图4.6），图中，静态点分布会呈现出与时间轴近似平行的趋势，表示用户长时间内位置未发生明显改变；动态点分布则呈现与距离轴近似平行的趋势，表示轨迹点携带有较大的速度矢量。单日内的轨迹点表现出重复出现的固定模式，体现了公交车辆沿固定线路运动的周期性。图中呈现出两处显著密集分布的静态轨迹点，对应着车辆在始发站和终点站位置发生的停留。因此，基于时间-里程变化信息，有助于更为清晰的提取公交车辆的不同的运动状态（静态模式、动态模式）、停留时长和状态变化时间点等时空运动特征。图4.6移动轨迹的时间-里程表达Figure4.6Individualtrajectoryrepresentedintime-distanceapproach核密度计算在空间分析中，核密度方法可以将样本点数据转换成连续平滑的面，已经被广泛地应用在交通研究和人类移动行为分析(Huetal.2018,Lietal.2020)中。传统核密度的计算公式为：f式中h为搜索带宽；n为与当前估算手机信令轨迹点的距离小于或等于带宽h的轨迹点数目；k·为采用的核函数；xi传统核密度方法侧重于描述要素或事件在空间上的分布，针对司乘人员轨迹的驻留点探测问题，应考虑手机信令与基站交互事件在时间维度上的异质性。因此，在空间核密度估计的基础上，考虑时空要素在时间维度上的集聚特性，衍生出时空核密度估计方法。借鉴空间核密度估计思想，将空间距离广义扩展成为“时空距离”，“时空距离”越近的事件对密度值的贡献越大，“时空距离”越远的事件对密度值的贡献越小。根据定义，累积出现概率表示为移动对象在某个位置上产生的所有轨迹点的停留时间的累积概率。参考(Qietal.2006)使用的核函数选择，加入时间变量，将每个时空单元中重点交通违法事件的密度估计值ff核函数定义为：KK其中，Ks·和Kt·分别是空间维和时间维的二维和一维高斯核核函数，n为手机信令轨迹中轨迹点数量，h1驻留点检测通过对轨迹点进行非参数核密度估计获取到的核密度曲线，反映了在路线的不同位置轨迹点的聚集程度。图4.7中展示了对公交路线307路的某条手机信令轨迹的核密度曲线，曲线中表现出两个主要的波峰和一些局部的变化。根据轨迹点的核密度定义，波峰位置对应着轨迹中发生停留的位置，需要给出定量化的标准对驻留点进行识别。图4.7公交司乘人员轨迹核密度曲线Figure4.7Trajectorykerneldensitycurveofbus-modestaff以往研究常采用固定的经验阈值来对轨迹的停留点进行判别，但由于公交路线往往跨越不同的城市区域，沿线的基站分布并不完全均匀的，单一的阈值无法准确地识别停留点。参考图4.8中的核密度曲线采用过大的阈值可能漏掉部分停留点，而过小的阈值会将轨迹中低速位置误识别为停留。因此，本文采用滑动窗口搜索范围内的局部极值点避免单一阈值对停留点的误分。给定窗口半径r，在[di图4.8核密度曲线窗口极值点查找Figure4.8Searchingforextremuminkerneldensitycurvewindow轨迹段语义化通过查找核密度曲线的极值点检测轨迹的停留点，这些停留点将整条手机信令轨迹分割多个行程段和停留段。此处行程段指的是公交车辆从始发站出发沿路线行，依次途径各公交站点，直至驶至终点站完成一次单程班次的过程；而停留段则是包括首班未发车、末班已结束、行驶过程中的临时停车和班次之间轮换休息等各类停留，表4.2给出了轨迹段的不同语义类型及其判别条件。表4.2轨迹段语义类型及判别条件Thesemantictypesoftrajectorysegmentsanddistinguishingrules运动状态语义类别判别条件行程段正常行驶在LCSS的首末匹配之间，且未中途发生停留停留段首班未发车在LCSS的首次匹配之前的时间段末班已结束在LCSS的末次匹配之后的时间段班次间短暂休息在LCSS的首末匹配之间，位置在始发站或终点站附近，且时间小于等于30min班次间长时休息在LCSS的首末匹配之间，位置在始发站或终点站附近，且时间大于30min途径站点停车在LCSS的首末匹配之间，位置在途径站点附近途中临时停车在LCSS的首末匹配之间，位于路线上其它位置如图4.9所示的司乘人员手机信令轨迹表现出典型的行程段-停留段分布模式。核密度函数存在两个波峰Peak1图4.9典型司乘人员行程段划分Figure4.9Tripsegmentdivisionoftypicalbus-modestaff而图4.10则展示了情况更加复杂的行程段-停留段分布模式。通过滑动窗口的极大值检测到核密度曲线的4个波峰，对应个体手机信令轨迹的4处主要停留位置，共划分出17条自轨迹段，其中包括9条停留段。结合LCSS匹配结果和停留点的空间位置，根据表4.2的规则确定，停留段①属于首班未发车，停留段⑨属于末班车已结束，停留段③⑤属于途径站点停车，而停留段②④⑥⑦⑧均属于短时间的班次间小憩。图4.10出现多个核密度峰时司乘人员行程段划分Figure4.10TripsegmentdivisionwithmultipleKDEpeak轨迹重建启发式优化问题启发式算法是指在可接受的计算时间、占用空间等开销的前提下给出待解决的组合优化问题的一个可行解。由于解决复杂的非线性问题的能力以及其在解的质量和计算效率之间取得了较好的平衡，启发式算法自提出以来就成为解决各类组合优化问题的有效方法之一。启发式算法的基本思想是：给定一个或多个目标函数，从初始解出发，通过某种“搜索策略”在搜索空间中寻找一组满足约束的解使得目标函数取得最值。这里的“搜索策略”包括局部搜索过程和学习过程，以及引入避免搜索陷入局部搜索区域的机制等。在以往研究中，启发式算法在交通领域内的路径选取、资源配置以及轨迹匹配聚类等优化问题都有着广泛的应用(Levinetal.2017,Oztopetal.2017,Perez-Rodriguezetal.2019)，这些带有约束的优化问题可表示如下：minimize

f(x)subjectg

式中fx:Rn→R是目标函数，gix为不等式约束，hix为等式约束，优化的目标是寻找使得fx最小的搜索策略选择面向不同类型的优化问题，启发式算法有着不同的求解思路以及最优解搜索策略。不同的决策变量、约束条件和目标函数，将优化问题分为不同类别，各类具体算法只能适应于对应类别的优化问题。根据决策变量来划分，可分为连续、整数或混合整数类型的优化问题；根据约束条件，可分为带约束的优化问题和无约束优化问题；而根据目标函数可分为单目标优化和多目标优化。本研究中对轨迹点位置的优化应属于带约束的连续型单目标优化问题，因此，在实验中选取四类满足对本优化问题适用性的启发式搜索算法策略（在表4.3中列出）对轨迹点位置进行优化重建，并在4.3.5中的重建结果分析中对比了这几类优化策略的效果。表4.3适用于轨迹点位置优化的启发式搜索策略启发式搜索策略实现模块适用问题类型指南针搜索(CS)PyGMO.algorithm.cs连续-带约束-单目标粒子群算法(PSO)PyGMO.algorithm.pso_gen连续-带约束-单目标模拟蜂群算法(ABC)\o"PyGMO.algorithm.bee_colony"PyGMO.algorithm.bee_colony连续-带约束-单目标增广拉格朗日算法(AL)PyGMO.algorithm.nlopt_auglag连续-带约束-单目标轨迹点位置优化模型在本研究中对于不同时刻公交-地铁模式轨迹点位置的估算问题，本身是一类高维非线性的问题，考虑采用启发式优化来进行求解。如图4.11中所示，经过行程划分的某Cell-ID子轨迹段包含多个与路线匹配上的“锚点”基站，可以知道手机在与基站发生交互产生记录的时刻（即数据中时间戳记录的时刻），车辆位于对应的基站扇区内，扇区和公交路线的交集为公交车辆可能出现的位置，确定了优化模型的搜索空间。图4.11 路径沿线基站覆盖范围与优化模型调整Figure4.11DiagramofBTScoverageandLCSSoffset对优化模型目标函数的确定，需要对公交车辆本身的运动特性展开分析。考虑到在没有遇到路口、车站等无阻碍通行的路段时，公交车辆出于满足固定车辆排班时刻表的需求，在路线上是以接近匀速的状态行驶的，换言之车辆在公交路线各路段上的平均速度波动很小；而在遭遇路口和需要停靠的公交站点时，则会需要减速或者停留，其在路段上的平均速度也会相应降低。此外，公交车辆在沿路线行驶时，有着固定的前进方向，其累计里程值应为单调递增。因此，我们以车辆行驶速度的方差作为目标函数，基站覆盖范围作为搜索空间，并考虑累计里程的递增性作为决策变量的不等式约束，建立优化模型：minimize

subjectm

如图4.12中所示，为了简化模型的求解，将空间二维的位置转换为车辆从始发站为参考点的一维累计里程，mi为轨迹中第i个点的累积里程，ti为轨迹中第i个点的时间戳，图4.12 启发式优化算法示意图Figure4.12Heuristicoptimizationofthelocalizationofanchorpoints数据模拟与模型精度评定在原始手机信令数据集中，个体真实途径的时空轨迹是难以从其他数据源中获取的，无法直接验证重建轨迹是否更加接近真实的个体时空轨迹。本节提出一种基于模拟仿真的验证框架，通过对高频手机APP采集数据进行子采样，能够构建模拟Cell-ID手机信令轨迹，通过对模拟数据处理效果验证轨迹重建方法的有效性。图4.13 基站扫频安卓应用界面Figure4.13ApplicationInterfaceofAndroidApplication我们采用一套安卓端的手机应用程序Geopaparazzi（图4.13为软件界面），该款应用能够以1Hz的频次检测手机天线所连接到的附近基站，同时通过内嵌GPS模块记录设备持有者的准确位置。我们对研究区域内的公交线上采集了多组数据，每一组数据包含了同一公交车辆的多次行程记录。表4.4中给出了APP记录的数据样例。表4.4 安卓应用记录的基站扫频数据示例Table4.4DataRecordedbytheAndroidApplicationNo.TimestampCidLacNetTypeLatLon120171204092707180165174566439.9730116.2900220171204092709181578274566439.9730116.2900320171204092712180165144566439.9732116.2917420171204092714180165144566439.9731116.2917520171204092716180165144566439.9731116.2917620171204092718180165144566439.9731116.2918720171204092720181578274566439.9730116.2918820171204092722181578274566439.9730116.2918920171204092724181578274566439.9730116.29181020171204092726181578274566439.9730116.2919在同样位置和外界环境下，Geopaparazzi所采集到的基站与手机在同一时刻发生交互的基站相同，换言之Geopaparazzi记录数据与Cell-ID手机信令数据在空间分布上一致。为模拟Cell-ID手机信令的时间分布特征，我们对APP采集的轨迹数据进行同样间隔时间的子采样。图4.14给出了子采样之后轨迹相邻点的间隔时间分布与原始数据集对比，模拟数据与真实数据的分布比较一致。图4.14 相邻轨迹点时间差概率分布曲线Figure4.14Distributionofconsecutivetrackingpoint轨迹重建结果分析精度评价指标我们采用平均绝对误差(MAE)来评估重建模型的效果，使用误差标准差(StDev)度量来评估重建模型的稳定性。给定一条手机信令轨迹Trj=pt1,…,ptnErrorMAE=其中，pti−pti'是手机信令轨迹点ptiStDev=重建结果首先对模拟手机信令轨迹和对应公交路线进行LCSS匹配，获取作为启发式算法初始输入的匹配锚点位置。对公交路线307路上采集的轨迹数据匹配中，沿线共有136个手机信令基站，其中有81个基站属于锚点基站。图4.15匹配锚点及对应的基站扇区Figure4.15Anchorpoint’ssearchspaceinamatchedBTSsectorLCSS匹配算法得到的锚点位置作为决策变量mi表4.5 迭代优化得到重建位置Table4.5Estimatedlocationofanchorpoints.PIDTimestampMileageCoordinatexCoordinatey010:02:2636118.53129509044864737110:03:2336407.21129511924864749210:07:2737221.02129520054864780310:10:3037779.06129525634864799410:12:1338164.97129529494864815510:17:0038918.11129529974865498……………表4.5中给出了迭代优化得到的重建位置的示例，包含了每个手机与基站发生交互时刻（即信令数据记录时刻）的坐标位置xi,图4.16 轨迹重建前后累计里程与GPS真实值比较Figure4.16Accumulateddistanceofreconstructedtrackingpoint利用Geopaparazzi应用采集到包含4次往返行程的验证数据，包含每次往返由GPS模块记录的个体真实轨迹以及由移动通讯模块记录的4组手机信令轨迹，对重建效果进行检验。图4.17中以“时间-里程”形式展示了行程划分与轨迹重建的结果，可以看出轨迹被正确地划分成4段，对于每一段行程调整后的锚点位置比调整前锚点更接近真实位置。图4.17 不同往返行程中累计里程与GPS真实值比较Figure4.17Accumulateddistanceofreconstructedtrackingpoint不同启发式算法比较我们选取了符合模型属性（连续-约束-单目标）的各类启发式算法，并对不同算法的轨迹重建效果进行了比较。优化模型采用python智能算法模块Pygmo进行求解，求解的详细步骤表示如下：Step1：确定迭代终止条件，设置最大迭代次数为200k次Step2：将匹配锚点作为初始输入，并通过基站扇区范围确定搜素空间Step3：在搜索空间内调整决策向量，并计算目标函数，如函数值小于当前取得的最小目标函数值，则更新最佳决策向量Step4：若满足终止条件，终止算法并输出最优值及最优解；否则返回step3图4.18中分别给出了采用粒子群算法（PSO）、增广拉格朗日算法（AL）、指南针搜索算法（CS）和人工蜂群算法（ABC）4种启发式算法来对优化模型进行求解的MAE和STDEV结果，并采用未经过优化的原始位置作为对照。结果表明，每一类算法在优化后都在MAE和STDEV两项指标上有所提升；与其它算法相比，指南针搜索算法（CS）对轨迹的重建效果最好，估计位置与实际位置的误差最小。图4.18 各类启发式算法误差比较Figure4.18Comparisonofdifferentheuristicoptimizations与已有方法的比较我们选取了在以往的轨迹重建研究中最常使用到的插值方法来和本文提出的启发式算法模型进行对比，对照的插值方法包括最近邻采样点插值、线性插值以及Hermit插值方法(Hoteitetal.2014)，线性插值以及Hermit插值方法分有无公交路线数据作为辅助约束条件分别进行插值，有公交路线