张 霞, 赵玮丹, 江文萍, 唐炉亮
(1. 武汉大学 城市设计学院,湖北 武汉 430072; 2.武汉大学 资源与环境科学学院,湖北 武汉 430079;
3. 武汉大学 测绘遥感信息工程国家重点实验室,湖北 武汉 430079)
基于网络热度的道路景观评价与最美路径推荐
张霞1, 赵玮丹2, 江文萍2, 唐炉亮3
(1. 武汉大学 城市设计学院,湖北 武汉 430072; 2.武汉大学 资源与环境科学学院,湖北 武汉 430079;
3. 武汉大学 测绘遥感信息工程国家重点实验室,湖北 武汉 430079)
摘要:基于道路景观搜索量、签到和点赞等网络热度大数据建立道路景观热度综合评估模型,结合景观视域得到道路美丽度,并以距离、时间等为约束条件,设计和实现了最美路径优化算法.最后以武汉市28处道路景观进行实验,并将最美路径算法与传统最短路径算法进行比较,结果表明,在起止点相同情况下,最美路径算法可以在距离(时间)阈值约束范围内找到更美路径,提高出行过程中的愉悦感.
关键词:网络热度; 道路美丽度; 最美路径; 路径优化; 大数据
随着人民生活质量的不断提高,公众对出行有了更高的期望,不管是私家车休闲兜风还是公务上下班,在满足一定时间或距离约束下,都会尽可能追求一条舒适性高、自然风光美、人文历史厚的最美路径,而不再满足于简单可达路径,但是现有研究大都是追求效率高、路径短的最快路径或最短路径,忽略了出行公众的心理需求.完善的街景数据库和网络上高度共享的地理信息为这一需求提供了可能,如何从网络大数据中挖掘出道路景观信息,并将其应用在路径规划中,为公众提供更加舒适的可选路径,成为国内外学者研究的热点.
传统路径规划一般都是追求距离最短、出行时间最短、费用最小,有一些学者提出前K条最短路径算法[1-2],用于最短路径不符合条件时,次短或第k短路径的推荐.近年来,研究者更加关注公众出行的物质和心理等个性化偏好与需求[3-5],如于海璁等[3]提出了一种适宜多模式交通网络环境下的多标准路径搜索方法;Meng等[4]在路径规划时考虑了用户购物、就餐、看风景等一系列出行目的,利用蚁群算法为出行者推荐经过更多目标点的路线;Quercia等[5]研究了散步者的心理特征,将数据库图片众包到评价网站中进行投票,以美丽、安静和高兴三方面的得分生成网络图,推荐最美丽、最安静或最高兴路径.
大数据时代的到来为个性出行需求的路径规划带来了新机遇,社交网络共享图片与轨迹大数据成为个性化出行需求的数据源,一类是基于社交网络共享图片大数据[6-8],如Choudhury等[8]基于Flickr用户上传的带有位置和时间信息的照片构建POI(point of interest)图,在路径规划时链接该数据为出行者推荐最适合该用户的路径;另一类则是手机等移动设备全球定位系统(global positioning system, GPS)轨迹和车载GPS轨迹数据的众包轨迹数据[9-10],如唐炉亮等[9]基于浮动车数据(floating car data)研究了出租车司机路径选择规律,建立经验知识模型,设计基于经验知识的路径优化算法.此外,随着基于位置的服务(location based service,LBS)兴起产生的网络搜索与签到数据因信息量丰富、方便获得、成本低等优点,也逐渐被应用到旅游路径规划[11].
本文通过景观的网络搜索、签到和点赞等网络热度信息综合评价景观的热度和品质,从街景数据库中获取道路前进方向的景观视域范围,评估道路美丽度,并设计和实现了最美路径规划算法,提高出行的愉悦感和舒适性.
1基于网络热度的道路景观评价
1.1景观网络热度数据采集与预处理
现有景观评估主要针对城市、大型景区等旅游目的地或专门旅游道,通过组织调查获得景观公众评价,进行统计分析得到定量值[12].互联网的普及和大数据时代的到来为景观评估提供了丰富且低廉的数据源,公众评价可以通过网络调查或现有网络数据获得[5,13].本文中道路景观热度评估以网络大数据为基础,首先挖掘城市景观中具有历史意义、文化价值或令人赏心悦目的道路景观,以与景观热度密切相关的文字和照片网络搜索量(T)、网络签到人数(N)、网络点赞数(S)和景观等级(L)为评判标准,对道路景观热度进行定量评估.
本文以谷歌搜索为引擎,采集道路景观文字和照片搜索量,然后抓取微博签到数和点赞数,景观等级划分参考国家景区等级划分标准,3A、4A、5A级景观分别得3、4、5分,其余景观得分2.采用对数法对T、N和S做量纲一化处理,其中x表示量纲一化后的数据,x*为原始数据,如式(1)所示.
(1)
1.2景观热度评估
景观热度评估分为三个环节,依次是景观模糊关系计算、景观模糊聚类分析、景观热度评估.模糊聚类分析是用数学方法定量确定样本之间的亲疏关系,本文用景观属性聚类得到的景观亲疏关系指导并修正景观热度评估模型,具体建模过程如图1所示.
(1)建立景观模糊关系矩阵
研究了T, N, S和L四个属性,采用最大最小法建立Fuzzy关系矩阵R=(rij),rij表示第i个景观和第j个景观的相似度(亲密程度),计算方法如下:
(2)
式中:xik表示第i个景观的第k个属性,m为景观属性个数,本文中m=4.
图1 景观热度评估建模流程
(2)景观模糊聚类分析
在此基础上,根据隶属度α将景观分为n类,依据同一类景观相似度高,不同类之间差异度大的特征,并结合人的认知,按照以下规则指导和调整景观热度定量评估模型:
① 景观热度定量评估结果的相对大小应该符合大多数人的认知,即景观热度值的相对大小不能与人们的习惯认识相差太远;
② 将景观按热度升(降)序排列的结果称为景观序列h,同一类景观在h中的映射是连续的.划分在同一类的景观的4个属性之间较为亲密,因此其景观热度值也应具有较高相似度;
③ 不同类景观在序列h中的映射不能有交叉,类内部可以交叉.如图2所示,Ai表示景观i的热度,景观2和景观3属于不同类,则热度值也应属于不同类,对应的景观热度A2和A3不能交叉,而景观3和景观4属于同一个类别,它们所对应的景观热度A3和A4可以交叉.
图2 模型调整规则
(3) 景观热度评估
依据以上规则,对模型进行修正,直到景观热度评估结果符合该规则,最终得到景观热度表达式如下:
(3)
式中:Ai表示第i个景观的热度;Li表示等级;Si表示点赞数;Ti为网络搜索量;Ni为签到人数;w1和w2分别为Ti和Ni对应的权重,w1=w2=0.5.
1.3顾及拓扑方向的道路美丽度评估
1.3.1道路景观视域分析
道路美丽度是出行者对出行环境的心理感知,其中景观视域是不可忽略的因素,道路的网络拓扑关系决定了视域的有向性,本文的视域搜索建立在道路前进方向上.顾及拓扑方向的道路景观视域受景观高度、地势、周围建筑物以及景观与道路的位置关系等多种因素影响,街景地图是沿着车辆前进方向拍摄的实景地图,完整地保持了视域的方向性,因此通过在街景数据库中跟踪搜索得到景观视域范围l.
1.3.2道路美丽度
道路美丽度是指道路前进方向上道路景观热度与景观视域对出行者吸引力的总和.本文对道路美丽度的评估建立在道路景观热度的基础上,热度值高但在视野中出现时间短的景观对道路美丽度的贡献同样较小,另外,道路景观数量越多,对道路美丽度的影响越大.综上所述,道路景观热度、景观视域和道路景观数量是道路美丽度的三个评判标准.道路的美丽度的数学模型表达如下:
(4)
式中:Bi为第i条道路的美丽度;q表示视域投影在道路i上的景观总数;lj表示道路i上第j个景观的道路景观视域;Aj为道路i上的第j个景观的热度.
如在图3中,道路a的美丽度为景观P1、P2和P3各自的热度A1、A2、A3与相应景观视域l1、l2、l3a的乘积之和,即Ba=A1l1+A2l2+A3l3a,而道路b的美丽度Bb=A3l3b+A4l4.
图3 道路美丽度评估模型
2基于道路景观的最美路径规划
2.1公众对路径美丽度的认知
以道路景观为导向寻找最美路径往往需要考虑以下两方面因素的影响:
(1)道路美丽度:道路美丽度对出行安全和出行者的舒适度影响很大,在时间充裕的情况下,人们往往会选择有更高品质景观的道路.
(2)路径长度:具有目的地的出行一般都需要在预期时间内到达,出行者不会纯粹为了追求美丽而完全忽略距离(时间),因此将路径距离(时间)作为约束条件.
在路径规划时同时考虑道路美丽度和距离(时间)约束,建立最美路径规划模型,如式(5)所示,其中,Route(s,t)表示起点s到终点t的最美路径,F表示距离(时间)约束下的最美路径优化算法,Br表示路径美丽度,Lr表示路径距离(时间).
(5)
2.2最美路径规划思路
路径美丽度Br是起点与终点之间可达路径经过的所有道路的美丽度之和,如式(6)所示,其中n表示路径所经过的道路数,Bi为道路i的美丽度.
(6)
基于道路景观的最美路径规划要求在约束范围内寻找美丽度最大的路径,出行者可以根据自己的时间控制路径美丽度和路径消耗(时间或距离)之间的平衡点,一般情况下,路径美丽度越大,消耗越大.这种路径规划思想给公众提供了自主安排的空间,体现了人性化思想,增强了路径的体验性.
2.3距离(时间)约束下的最美路径规划算法
在单标准路径规划中,通常采用Dijkstra或Frod算法得到单标准最短路径,而本文的路径规划结果需要满足两个条件:①路径美丽度最大;②路径消耗不超过阈值,其本质是距离(时间)约束下的最长路径,最长路径规划的非确定多项式(non-deterministic polynomial, NP)性导致问题难以在多项式内求得最优解.若忽略算法运行的时间成本,一种简单的方法是通过暴力搜索找出起止点之间所有可行路径,然后在其中找出美丽度最大且符合消耗或约束限制的,随着道路节点的增多,算法复杂度呈指数形式增长.
本文将问题分解为两步求解:①运行Martins的前k条最短路径算法[2],得到起始点s和终止点t之间的前k条最短路径集合p,k的取值由距离(时间)阈值而定;②在集合p内找到美丽度最大的路径,即为距离(时间)约束下的最美路径,算法与流程图如图4所示.
图4 最美路径算法
输入:路网G=(V,E),起止点s,t,距离(时间)约束d
输出:最美路径BestRoute,路径长度Length和美丽度Beauty
初始化KRoute和BestRoute;
ShortestRoute=Dijkstra(s,t,G);//求最短路径
If ShortestRoute.Length KRoute= ShortestRoute; For KRoute.Length G=ReNewRoadNode(V,E,s,t);//更新路网图G KRoute= Dijkstra(s,t,G); //求第k条最短路径 If KRoute.Beauty> BestRoute.Beauty;//更新最美路径 BestRoute=KRoute; Else Break; 3实验分析与比较 本实验以武汉市为实验区域,采集了以2014年12月31日为截止时间,以二环线以内为主的28个道路景观的数据.通过式(1)对景观网络搜索量、签到数和点赞数这三组数据做量纲一化处理;用式(2)计算任意两个景观之间的模糊关系,建立模糊矩阵;通过模糊聚类分析,得当隶属度α=0.93时,道路景观被分为5类,在表1中,1为第一类,2~8为第二类,9~12为第三类,13~14为第四类,15~28为第五类;在此基础上,根据模型调整规则修正景观热度评估模型,得到式(3)并计算道路景观热度,结果按降序排列于表1中. 以28个景观为中心,在一定大小的缓冲区周围跟踪搜索SOSO街景地图,采集景观视域,根据式(4)计算道路美丽度,武汉市景观评估结果与道路美丽度如图5所示. 本文以C#为开发工具,以ArcGIS10.1为地理信息系统(GIS)平台进行路径规划实验,实现了距离约束下最美路径规划算法.还选取9个离散点构成一个环形线路,分别用传统最短路径算法和本文算法作路径规划,距离阈值分别设为1.5倍和2倍最短距离,共得到18条路径,选取路径长度、路径美丽度和每米平均美丽度3个指标进行比较,结果列于表2中,其中l表示最短路径长度. 表1 道路景观评估 图6中五角星表示起止点,虚线为最短路径规划结果,实线表示1.5倍阈值约束下的最美路径.可以看出,当不追求距离最短时,出行者可以通过绕行沿着美丽度更高的道路前进. 表2 两种算法实验结果对比 图5 评估结果可视化图 图6 两种方法规划路径对比图 Fig.6Routes contrast planned by the proposed model and shortest route model 4结论与展望 本文基于道路景观搜索量、签到和点赞等网络热度大数据建立道路景观热度综合评估模型,结合景观视域得到道路美丽度,并以距离(时间)作为约束条件,设计和实现了最美路径优化算法.最后以武汉市为例,选取28处道路景观进行实验,并将本文算法与传统的最短路径算法进行比较.结果表明,在起止点相同情况下,本文提出的模型方法可以在距离(时间)阈值约束内找到更美路径,提高出行过程中的愉悦感.本文后续在费用、道路拥挤等因素对出行的影响进行进一步研究. 参考文献: [1]Eppstein D. Finding the k shortest paths [J]. Siam Journal on Computing, 1999, 28(2):652. [2]Martins E Q, Santos J L. A new shortest paths ranking algorithm [J]. Investigacao Operacional, 2000, 20(1): 47. [3]于海璁, 陆锋. 一种基于遗传算法的多模式多标准路径规划方法[J]. 测绘学报, 2014(1): 89. YU Haicong, LU Feng. A Multi-modal multi-criteria route planning method based on genetic algorithm [J].ActaGeodaeticaetCartographicaSinica, 2014(1): 89. [4]MENG Xiangxu, LIN Xinye, WANG Xiaodong. Intention oriented itinerary recommendation by bridging physical trajectories and online social networks[C]// Proceedings of the ACM SIGKDD International Workshop on Urban Computing. Beijing: ACM, 2012: 71-78. [5]Quercia D, Schifanella R, Aiello L M. The shortest path to happiness: recommending beautiful, quiet, and happy routes in the city [C]// Proceedings of the 25th ACM conference on Hypertext and social media. New York: ACM, 2014:116-125. [6]Lucchese C, Perego R, Silvestri F,etal. How random walks can help tourism[C]// Advances in Information Retrieval. Barcelona: ECIR, 2012:195-206. [7]Orsi F, Geneletti D. Using geotagged photographs and GIS analysis to estimate visitor flows in natural areas [J]. Journal for Nature Conservation, 2013, 21(5): 359. [8]Choudhury M D, Feldman M, Sehim A Y,etal. Automatic construction of travel itineraries using social breadcrumbs[C]// Proceedings of the 21st ACM Conference on Hyper Text. Toronto: ACM, 2010:35-44. [9]唐炉亮, 常晓猛, 李清泉. 出租车经验知识建模与路径规划算法[J]. 测绘学报, 2010(4): 404. TANG Luliang, CHANG Xiaomeng, LI Qingquan. The knowledge modeling and route planning based on taxi' experience [J].ActaGeodaeticaetCartographicaSinica, 2010(4): 404. [10]Broach J, Dill J, Gliebe J. Where do cyclists ride? A route choice model developed with revealed preference GPS data [J]. Transportation Research Part A: Policy and Practice, 2012, 46(10):1730. [11]宋晓宇, 许鸿斐, 孙焕良,等. 基于签到数据的短时间体验式路径搜索[J]. 计算机学报, 2013,36(8): 1693. SONG Xiaoyu, XU Hongpei, SUN Huanliang,etal. Short-term experience route search based on check-in data [J]. Chinese Journal of Computers, 2013, 36(8): 1693. [12]Akbar K F, Hale W H G, Headley A D. Assessment of scenic beauty of the roadside vegetation in northern England [J]. Landscape and Urban Planning, 2003, 63(3): 139. [13]Song Lili, Qi Lina, Qi Ji,etal. Evaluation of the Attractiveness of Tourism Destinations Based on Link Analysis[C]// 18th International Conference on Geoinformatics. Beijing: International Conference on Geoinformatics, 2010:18-20. Landscape Evaluation and Most Beautiful Route Planning from Big Website Date ZHANG Xia1, ZHAO Weidan2, JIANG Wenping2, TANG Luliang3 (1. School of Urban Design, Wuhan University, Wuhan 430072, China; 2. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China;3. State Key Laboratory for Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China) Abstract:This paper presents a roadside landscapes evaluation model (RLEM) based on big website data about web hotspots, such as web searching data, web check-in data and web voting data. Then, Road beauty degree(RBD) is calculated by the proposed RLEM and the roadside landscapes’ visual ranges along road. Finally, the most beautiful route planning algorithm is designed and realized based on road networks RBD. An experiment was applied in Wuhan (China), where twenty-eight landscapes were measured by RLEM, and the road networks RBD were calculated. Comparing between the proposed model and the traditional shortest path model, the results show us that routes planned by the proposed method have higher RBD than the routes planned by the traditional shortest method. Key words:web hotspots; road beauty degree; most beautiful route; route planning; big data 文献标志码:A 中图分类号:P208 通讯作者:赵玮丹(1992—),女,硕士生,主要研究方向为三维地理信息,地理信息可视化.E-mail: zhaoweidan @whu.edu.cn 基金项目:国家自然科学基金资助项目(41571430;41371428;41271442) 收稿日期:2015-05-05 第一作者: 张霞(1975—),女,工学博士,副教授,主要研究方向为三维地理信息与城市空间动态性分析、建筑空间生态优化. E-mail: Xiazh75@126.com