搜索
智能交通推荐系统综述刘景明摘要：信息超载是目前网络用户面临的一个严重问题，个性化推荐系统是解决该问题的一个有力工具。同样的，在智能交通研究领域中，根据各类交通及出行相关信息的智能推荐系统可以为司机或出行者提供相关的推荐服务，使得用户能够最大化地使用有限的城市交通资源，这在某种程度上也可以缓解城市交通压力和日益增长的出行时间。本文综合分析了智能交通推荐相关的研究热点，为未来的在智能交通推荐领域提供研究方向。关键字：智能交通推荐系统算法1.前言近年来，交通拥堵问题越来越成为制约城市发展的瓶颈问题。然而，由于资金、用地等客观条件的制约，以道路面积追车辆数量的方法并不现实。信息技术的快速发展为交通问题的解决带来了新的方向。借助于监测、通信和控制等新一代的信息技术应用的智能交通系统（IntelligentTransportationSystem，ITS）应运而生[1]。在智能交通研究领域中，出行规划推荐、行车路线推荐和用户个性化推荐等是比较热门的方向。已有众多的学者对智能交通的推荐问题进行了研究。2.智能交通系统简介智能交通系统作为一个信息化的系统，它的各个组成部分和各种功能都是以交通信息应用为中心展开的，因此，实时、全面、准确的交通信息是实现城市交通智能化的关键。从系统功能上讲，这个系统必须将汽车、驾驶者、道路以及相关的服务部门相互连接起来，并使道路与汽车的运行功能智能化，从而使公众能够高效地使用公路交通设施和能源。2.1智能交通系统主要子系统交通管理系统(TrafficManagementSystem，TMS）是智能交通系统的最重要组成部分，也是城市智能交通系统的重要基础部分。交通管理系统的主要体现在集成性、预测性、主动性、实时性等方面，即集成了众多交通管理功能，并基于全面的检测信息及预测分析进行主动性交通管理，摆脱被动适应性管理的滞后性。交通信息服务系统（TrafficInformationServiceSystem，TISS）主要面向公众出行者，利用无线与有线通信手段，以文字、语音、图形、视频等形式实时动态地提供与出行相关的各类交通信息，使出行者在整个出行过程中能够随时获得有关道路交通情况、所需时间、最佳换乘方式、所需费用以及目的地等各种相关信息，从而引导出行者选择合适的交通方式、出行路线和出发时间，以最高的效率和便捷的方式完成出行过程。智能公交系统（PublicTransportSystem，APTS)，是在公交网络分配、公交调度等关键理论研究的前提下，利用系统工程的理论和方法，将现代通信、控制、网络、GPS、GIS等新技术集成应用于公共交通系统，通过构建现代化的信息管理系统和控制调度模式，实现公共交通调度、运营、管理的信息化、现代化和智能化，为出行者提供更加安全、舒适、便捷的公共交通服务。2.2智能交通新技术的应用探索随着现代交通技术与电子、通信、计算机等技术的发展，如RFID和智能手机的广泛应用、大数据分析与云计算技术的出现等，为智能交通系统的快速发展提供了强有力的支撑。3.国内外相关研究现状由于智能交通系统是一个庞大复杂的系统，研究者们一般会选取某一个子系统的某一个方向去研究，目前比较的热门的研究是路径规划，出行推荐，个性化推荐等方向。3.1出租车出行推荐的研究孔蕙心[2]研究一种基于实时客流分布的路线推荐算法，为空载出租车司机推荐空载穿行时间短且载客概率高的出行路线。提出对推荐路线的衡量标准PVC（PotentialVacationCost）方程，用来计算每条路线的潜在空载开销，并设计出出租车出行路线的最小开销推荐算法。宋庆怡[3]已海量出租车轨迹数据为研究对象，以智能打车推荐为应用目标，建立对轨迹数据的分布式处理框架和挖掘分析系统，并实现在线的查询与推荐服务。解决的问题包括：轨迹预处理、轨迹数据聚类、轨迹数据査询、预测和推荐模型建立等多个方面。SantoshThakkar,SupriyaBhosale等[4]提出了一种基于时空分析的在线出租车推荐系统，分析了高利润的出租车司机的接送行为和大量的载客出租车的行车轨迹，使用网格聚类算法结合时空分布分析，帮助出租车司机决定最佳载客地点，减少等待时间，获得更多利润。3.2公交车出行推荐的研究陈丽佳,邹峥嵘等[5]提出基于Dijkstra的智能选择换乘线路的实现算法,根据公交换乘的特殊性，采用一种新式堆结构——“配对堆(pairingheap)”来实现优先队列，新的算法在原始Dijkstra算法的基础上,为每个网络节点增加了一个指向堆节点指针,在算法遍历到新节点时,需要构造配对堆节点,并动态更新配对堆。改进了传统Dijkstra算法在公交换乘方面的时间和空间复杂度。WonJooLee,JaegeolYim等[6]设计并实现一个寻找出发点到目的点之间的最短路径的推荐系统。分析了现有公交换乘算法不能实现跨站换乘，即使这两个公车站相距很近。提出一种结合步行的新的公交换乘算法，将两个可以步行来往的（小于100米）公车站看作一个站，使用Dijkstra算法找出最短的乘车路径。3.3其他方面推荐的研究邵阔义，班晓娟[7]提出了一种基于交通网络数据优化的地理信息推荐系统。该系统在协同过滤推荐模型基础上结合交通网络数据的地理信息对推荐算法进行改进，首先利用传统的协同过滤算法对数据集进行预处理，而后将地点上下文加入进来，生成包含基于交通网络数据地点上下文的新的数据集，再结合地理信息推荐算法进行实验，获得了更优的推荐结果。刘龙[8]提出了一个能实现个性化实时路径推荐服务的推荐系统框架，该系统能够为驾车旅行者提供基于车与车通信的实时个性化的路径推荐服务。该推荐服务主要利用车与车通信收集路径信息、个性化需求信息以及实时交通信息，根据路径信息和个性化路径偏好，利用模糊逻辑和多目标决策的方法对所有候选路径进行打分，根据驾车旅行者的个性化需求和实时的环境信息，利用遗传算法来搜索并生成最优路径推荐给驾车旅行者。潘义勇，马健霄等[9]提出一种基于可靠性理论建立了动态随机网络环境下自适应最可靠路径的算法，反映交通网络中考虑可靠性的路径选择行为，定义行程时间可靠度为路径的目标函数，建立动态随机网络自适应最可靠路径模型反映交通网络的耗时随机特性、时变特性和风险性；通过最优化理论把该问题转化为动态规划问题构造动态规划算法求解该问题，并针对实际交通网络展开数值试验。研究结果可为智能交通系统路径诱导子系统提供理论支撑和核心技术。XijunZhang,ZhantingYuan[10]研究了基于位置大数据的交通流的预测，给出基于位置大数据的智能交通过程的总体设计。通过数学模型深度挖掘和分析了兰州市的GPS大数据，从而得到了清楚的城市交通分析图表来预测交通流量。4.智能交通推荐相关的算法4.1Dijkstra算法Dijkstra算法[11]是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法步骤：a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则u,v正常有权值，若u不是v的出边邻接点，则u,v权值为∞。b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d.重复步骤b和c直到所有顶点都包含在S中。4.2K-Means算法K-means[12]是一种基于距离的迭代式算法。它将n个观察实例分类到k个聚类中，以使得每个观察实例距离它所在的聚类的中心点比其他的聚类中心点的距离更小。算法步骤：a.所有的观测实例中随机抽取出k个观测点，作为聚类中心点，然后遍历其余的观测点找到距离各自最近的聚类中心点，将其加入到该聚类中。这样，就有了一个初始的聚类结果，这是一次迭代的过程。b.每个聚类中心都至少有一个观测实例，这样，可以求出每个聚类的中心点（means），作为新的聚类中心，然后再遍历所有的观测点，找到距离其最近的中心点，加入到该聚类中。c.重复步骤b，直到前后两次迭代得到的聚类中心点一模一样。计算聚类的中心点的公式1所以：𝑑𝑖𝑗=√∑|𝑥𝑖𝑘−𝑥𝑗𝑘|𝜆𝑛𝑘=1𝜆公式(1)其中λ可以随意取值，可以是负数，也可以是正数，或是无穷大。4.3遗传算法遗传算法(GeneticAlgorithm)[13]是一种随机搜索启发式算法，特点是直接对结构对象进行操作，没有函数求导的限制，采用概率化寻优的方式并行搜索。遗传算法推荐路径的原理是，结构化编码路径中的染色体，根据适应度函数F(x)计算适应度值，应用“自然选择”的思想从种群中依据概率随机选取，选择概率P=F(x)/ΣF(x)，对优秀个体进行选择、交叉和变异操作，产生新一代的候选解群，从中挑选优秀个体重复遗传操作，直到满足某种收敛指标为止。4.4蚁群算法蚁群算法(AntColonyOptimization)[14]是一种基于种群寻找最短路径的启发式搜索算法，算法通用性强，利用正反馈原理自适应的解决问题。个体运动过程中会在路径上留下信息素，其他个体会根据信息素浓度选择前进的路线。蚁群算法中路径转移概率公式和信息素的更新公式如公式(c))所示：P(i,j)=[𝜏(𝑖,𝑗)]𝛼∙[𝜂(𝑖,𝑗)]𝛽∑[𝜏(𝑖,𝑗)]𝛼∙[𝜂(𝑖,𝑗)]𝛽公式(2)信息素更新公式如公式(3)所示：τ(j)=(1-ρ)∙τ(j)+ρ∙τ0公式(3)信息素τ表示某时刻节点i与节点间的信息量启发信息，η表示节点转移的期望程度，α、β是常数。ρ(0ρ1)表示信息素挥发因子，τ0表示局部更新的常数，是信息素的初始值。4.5粒子群算法粒子群算法PSO(ParticleSwarmOptimization)[15]是模拟鸟群觅食的一种基于迭代的优化算法，在解决复杂的组合优化类问题方面具有优越性。算法基本思想是粒子通过与群体的信息交换，比较个体信息pb和全局极值gb，随时调整飞行方向和速度，相互引导使整体聚集高质量解的区域。速度更新公式如公式(4)所示，w0是惯性权重，c1、c2是加速常数，取值范围是(0,2)，r1和r2是随机数，控制粒子的运动方向。v'=w0∙vi+c1∙r1(pbi-xi)+c2∙r2(gbi-xi)公式(4)5.智能交通推荐的研究重点、难点及发展方向大数据、云计算等技术为智能交通发展提供了强大的工具。在智能交通规划设计中利用大数据分析、云计算的概念与理念。但同时大数据分析和云计算技术在智能交通应用领域同样面临着巨大挑战[16]，在智能交通推荐系统中存在的问题主要包括数据安全问题、评分问题和非实时问题。5.1数据安全问题进行协同推荐时需要掌握用户的兴趣偏好等用户信息，但用户担心个人数据得不到有效保护而不愿暴露个人信息，如出行时间、目的地、偏好地等，因此，现有的推荐系统很难被一些关注隐私的用户接受或者很难应用在一些隐私要求较高的领域。这是协同推荐长期存在的一个问题。既能得到用户信息而提高性能，又能有效保护用户信息的推荐系统将是未来的一个研究方向。5.2评分问题大部分现有的推荐系统只是基于单个属性来对物品进行评分。比如根据用户对书或者电影打分来进行评价。然而，在智能交通应用中，最终用户往往根据多个属性来选择物品。例如，位置、距离、价格、天气和景点类型都是用户选择的重要属性。未来的推荐系统需要引入更精确适用的用户和对象属性。5.3非实时问题大多数现有的推荐系统都没有考虑推荐系统的及时性。然而，在智能交通应用中，越来越多的用户想要得到基于实时环境信息和个性化需求的服务。例如，路径指引系统可以结合实时交通信息帮助用户找到更好的路径，并且实时交通信息已经被应用在车辆路径服务领域来提供更好的路径支持。参考文献：[1].陆化普，李瑞敏.城市智能交通系统的发展现状与趋势[J].工程研究-跨