1附件2:第八届全国大学生创新创业年会学术论文雾霾天气下新型城市交通系统的大数据研究----以京津冀地区为例河北金融学院闫晓圆李佳崔骁1.河北金融学院经济贸易系,河北省保定市,071051;2.河北金融学院信息管理与工程系,河北省保定市,071051;3.河北金融学院保险系,河北省保定市,071051。王立斌助教袁国强副教授肖倩讲师摘要:针对雾霾天气下现有城市交通系统存在的诸多问题,设计城市洒水车路线安排模型和城市交通系统实时优化策略,力求以最小成本最大程度发挥交通系统的潜力,并达到洒水除霾的环保需求。首先,对城市各个站点每天的具体位置信息进行统计,建立城市交通的网络分布图,应用几何中心算法与聚类方法,对城市交通数据进行分类整理,采用随机型邻域搜索算法(SNS)寻求最佳的洒水车路线安排;其次,采集城市交通数据,深入挖掘居民出行的规律性和随机性,通过城市交通系统的实时监测数据,应用弧路径规划模型,实时调整主要干线公交车的频率,最大限度地缓解交通压力。最后,应用标准数据集,实验验证模型的可行性和稳定性。Abstract:Formanyproblemsunderfogandhazeandurbantransportsystems,watering-cartsroutingmodelofurbanandoptimizationstrategiesofurbantransportsystemsinreal-timearedesigned.Itseektominimizecosts,butmaximizethepotentialofthetransportsystem,andachievetheenvironmentalneedsofthesprinklereliminatinghaze.First,specificlocationinformationofeachsiteforeachcityisaddup,networkingdistributionofurbantransportisconstructed,clusteringandgeometriccenteralgorithmsisappliedtosortthecitytrafficdata,stochasticneighborhoodsearchalgorithm(SNS)isdesignedtoexplorebestofwatering-cartsrouting;secondly,urbantransportdataiscollectedtodigresidentstravelregularityandrandomness.Throughreal-timemonitoringdataofurbantransportsystems,arcroutingmodelisusedtoimplementreal-timeadjustmentofthefrequencyofthemaintrunkbuses,maximizerelieftrafficpressure.Finally,Undertheapplicationofstandarddatasets,feasibilityandstabilityofthemodelisexperimentalvalid.关键词:雾霾天气;交通系统;启发式算法;局部搜索;自适应性一、引言近年来,雾霾天气频繁袭扰我国北方的诸多地区,京津冀地区雾霾现象尤为严重。随着改革开放的不断深入,工业化程度加重,空气质量开始恶化,雾霾天气现象出现增多,并且重霾频袭,危害逐渐加大,给城市建设、社会和谐带来很多困扰,尤其对城市交通系统的影响日益严重。因此,缓解雾霾天气,解决雾霾天气下交通拥挤问题便成为京津冀地区协同发展的核心内容。目前,许多专家学者对雾霾天气下的交通系统的建设进行了研究,突出以京津冀等区域为重点,力图作者简介:闫晓圆(1993-),女,中国,电子商务,三年级,智能城市交通及物流系统研究;李佳(1994-),男,中国,计算机科学与技术,二年级,大数据挖掘算法;崔骁(1992-),男,中国,保险学,三年级,交通意外车险、人险赔付结构研究。2实现环境效益、和谐交通环境双赢。从上世纪80年代左右,学者便开始从事对城市交通系统的量化研究[1],开展了一系列大规模的交通状况的统计调查[2],以数据为依据,探索城市交通的现实规律,依托于京津冀三地的地理特点和城市潜力,构建合理的交通模型,并逐渐形成了四阶段的城市交通系统的分析方法[3]。基本确立了京津冀城市的交通模型体系,为我国城市交通系统的优化和再建设提供了重要的理论支撑。由Golden和Wong等提出的容量约束弧路径问题(CapacitatedArcRoutingProblem,CARP)[4-5]作为物流配送系统的重要组成部分,一直是城市交通系统研究领域中最活跃的主题之一。城市中的公交车规划问题、雾霾天气下的洒水车路线设计、交通拥堵状态下交通岗红绿灯时间转换问题[6]等均可视为弧路径问题。这些问题直接关系到城市的未来发展,因此近年来,弧路径问题受到了越来越多研究者的关注,加之逐步普及的信息化监测,为我们构建和谐的人性化的新型的城市交通系统提供了可能。二、研究内容综合以上研究现状,并结合我国交通系统以及信息系统的发展现状,通过对雾霾天气下城市洒水车路线设计、实时优化城市交通系统与物流系统两方面的研究,为京津冀地区未来交通系统的完善提供了可靠的理论依据和解决方案。(一)城市洒水车路线设计该研究内容旨在设计出最优的街道洒水路线安排,确保城市大部分街道能够通过洒水实现除霾降尘的效果。具体如下:首先,应用Oracle数据库,对每个街道每天的平均客流量进行统计,得出城市街道交通的一般情况。其次,设计随机需求下的弧路径规划问题模型,应用几何中心算法与聚类方法,对城市街道交通数据进行分类整理,确保模型符合交通系统的一般特征。最后,应用随机型邻域搜索算法(SNS)对模型求解,得出最佳的街道洒水路线安排。1.模型建立洒水车路线设计问题描述如下大数据网络模型:给定一个无向图,GVE,其中01,,...,nVvvv代表顶点集,E代表顶点间的有向弧集,任一eE都有一个非负的费用或长度属性ec。假定同一条边上不同需求可以被不同的洒水车服务。因此,构建一条弧(,)pqevv,其中e的方向为pqvv,即()iphsv,()iqtsv。jR代表第j条路径,即第j辆车所走的路径。一条边可以被服务多次,也可以经过多次。令()ics为对应边(,)pqevv的长度,(,)ijdvv为顶点iv与jv之间的最短距离,则路径jR的长度为()1101()01()((),())(,())((),)njjiinjiDRhshsdvhshsv,(1)其中11((),())()((),())iiiiihshscsdtshs,()0()()0((),)()((),)njnjnjhsvcsdtsv。为了提高算法的效率,在提出的随机型邻域搜索算法中,允许非可行解的出现,如下定义解S的评价函数:111()()(())JJKjkjjjkZSDReR(2)其中为自适应参数,调节解的空间,保证最终解为可行解。2.模型求解---随机型邻域搜索算法概率型邻域搜索算法(SNS),该算法以邻域结构为基础,首先通过随机路径扫描产生初始解,构建最优解集,然后根据算法的概率机制,判断邻域搜索的强度,进行大小邻域结构的转化,指导邻域搜索,加快算法收敛速度,最后,通过Restart策略,扩大解空间的范围,避免局部过度搜索,提高算法效率。下面首先介绍SNS算法的几个主要元素。(1)解的相似度设A、B为问题的两个解,则A与B的距离为(,)DisABABAB,相似度为(,)ABSimABAB,其中A表示解A所包含边的数。(,)0DisAB,(,)0,1SimAB。若(,)0DisAB,(,)1SimAB,A与B完全相似;若(,)0DisAB,(,)0,1SimAB,A与B不完全相似,且(,)DisAB越大,(,)SimAB越小,A与B越不相似。(2)邻域搜索的强度设最优解训练集为,其容量为100m。令当前解为X,nberX为中与X最近的邻域解,AX为3以nberX为中心进行邻域搜索的最优解,BX为nberAXX过程中收敛于AX的解,即...nberBAXXX。定义BAXX的收敛概率为1(,)ABnberADisXXpXX,AXX的收敛概率为2(,)BnberADisXXpXX,则X进行邻域搜索的强度为expectnberAtXX,其上界为21upperptp。(3)解的初始化——合成扫描首先,对于每条需求弧(,)pqevv,构造初始路径00epqRvvvv。其次,将初始路径聚合成初始解。按照以下四种不同的规则,产生四个初始解。设两条需求边1(,)pqevv,2(,)rsevv,1eR与2eR聚合规则如下:S1:100pqrsRvvvvvv,11200(,)(,)(,)(,)qrqrsaveedvvdvvdvv;(3)S2:200qprsRvvvvvv,21200(,)(,)(,)(,)prprsaveedvvdvvdvv;(4)S3:300pqsrRvvvvvv,31200(,)(,)(,)(,)qsqssaveedvvdvvdvv;(5)S4:400qpsrRvvvvvv,41200(,)(,)(,)(,)pspssaveedvvdvvdvv。(6)(4)随机型邻域搜索算法随机型邻域搜索算法是基于洒水车路径规划问题非对称性而提出,首先,根据算法的进程,自适应调整解空间的大小,形成大小两种邻域结构算法。大邻域结构算法(NS1)侧重于对解的破坏,发现更深刻的解,而小邻域结构算法(NS2)主要强调对现有解的深度挖掘,发掘更细致的解。在整个算法中,依托现有搜索能力,通过概率的方式,进行结构切换。NS1(NS2)算法:I.随机产生一个正整数0.1,0.2qRR(0,0.1qR);II.按照S1S2S3S4依次改进当前解,一旦改进解new优于,令new,转入1;III.直至无改进解,记录最优解,更新。(二)雾霾天气下实时优化城市交通系统在公交站点确定的基础上,合理设计的公交车运行安排和频率是完善城市交通系统的关键内容。基于对城市居民出行规律充分认识的前提下,运用大数据技术,构建京津冀地区新型城市交通系统,应用启发式算法,寻求最优的公交车路线设计,促进城市交通系统的自我完善。1.城市居民的出行规律的统计分析首先,对城市居民出行的目的地进行调查,精确掌握各个站点的乘客流量;其次,统计正常情况下城市不同站点间的平均客流量,定量把握城市不同线路的繁忙度;最后,分析上下班、节假日等现象产生的出行规律的异常值。2.公交车路线模型设定城市的公交站点网络图:给定一个无向图,GVE,其中V代表顶点集,由两个集合1V、2V组成,1V代表公交车的起点和终点集合,2V代表普通站点集合,E代表顶点间的边弧集,代表相邻的两个站点,eE都有一个距离属性()de。统计任意两个节点iv至jv的正常时段平均客流量(,)Qij,定义流量矩阵为Q。jR代表第j条路径,即第j路公交车所走的路径,()qj表示第j辆公交车的容载量,()hj表示第j路公交车的数量。一条边可以被多辆公交车服务多次,也可以经过多次。目标函数:在保证所有的站点都被服务且满足公交车的容纳要求((())()QRjqj)的前提下,使得公交车行进总路程的最短。数学模型:Min()jhjDR(7)s.t.(())()QRjqj1(),()jjhRhRV()RjV4三、模型验证与推广(一)模型验证为验证上述模型在城市洒水车路线设计及交通系统规划过程中的可行