2019, Vol. 44文章信息
- 宁津生, 吴学群, 刘子尧
- NING Jinsheng, WU Xuequn, LIU Ziyao
- 顾及道路通达性和时间成本的多用户位置推荐
- Multi-user Location Recommendation Considering Road Accessibility and Time-Cost
- 武汉大学学报·信息科学版, 2019, 44(5): 633-639
- Geomatics and Information Science of Wuhan University, 2019, 44(5): 633-639
- http://dx.doi.org/10.13203/j.whugis20190026
-
文章历史
收稿日期: 2019-01-17
2. 昆明理工大学国土资源工程学院, 云南 昆明, 650093
2. Engineering Institute of Land and Resources, Kunming University of Science and Technology, Kunming 650093, China
随着通信、室内外定位、互联网技术的快速发展，位置服务融入传统社交网络形成了地理社交网络（location-based social network，LBSN）[1]，将人们的虚拟网络行为与客观世界所处位置相联系，加强了人们之间的交流与沟通。国内外常用的LBSN有Foursquare、Gowalla、Whrrl、大众点评、美团、微信等。
地理社交网络的位置推荐功能可以从海量数据中向人们推荐其可能感兴趣的位置等信息[2-3]，因此成为地理社交网络领域研究和应用的热点。国内外学者围绕位置推荐开展了大量研究，现有的位置推荐算法主要是依据用户及好友使用LBSN服务时的签到、搜索历史、社会关系、社交活动、兴趣偏好等数据推荐兴趣点给用户，采用基于协同过滤、基于内容以及混合模型的位置推荐方法满足用户的位置需求[3-7]。影响位置推荐结果的因素主要侧重于地理位置、个人爱好、社会关系及时间周期等[1]。随着城市的不断扩张，人们工作生活节奏越来越快，人们在参加集体社交活动时开始更多地考虑用户当前位置到活动地点的距离、时间成本的问题。在大众点评、美团、饿了么等LBSN中，针对多个用户群体活动的位置推荐算法主要有：（1）按照商圈推荐位置；（2）全城范围内推荐位置；（3）多用户的地址坐标构成区域进行位置推荐；（4）根据多用户的地址坐标建立几何中心区域进行位置推荐；（5）周边算法(如附近5 km范围内)推荐位置。
现有的位置推荐算法主要是基于LBSN的上下文信息（包括兴趣、位置、时间、物理环境、搜索历史等[8-9]）感知，未考虑到城市实际的复杂路况（单行、绕行、施工限行、拥堵等）与用户所需付出的时间，可能出现推荐的活动地点可到达性差或耗费时间过多的问题。单个用户从现有LSBN获得推荐位置后，可以利用导航定位软件判断自己当前位置到活动地点的距离和时间成本，但针对城市范围内的多个用户，上述方法就难以满足多个用户对距离和时间成本的集体规划需求。本文主要是针对城市范围内集体社交活动（如聚会、沙龙、派对、健身、运动等）场地选择的需求，综合考虑参加活动的多个用户所在位置到活动地点的道路通达性和时间成本，利用现有在线地图资源进行多用户位置推荐方法的研究。
1 城市多用户位置推荐方法 1.1 多用户位置推荐现有的基于位置的社交网络主要是采用全城、某个街区(商业区)、附近多少千米范围内、多用户构成的区域等4种方式为用户进行商家位置的推荐。若是多个用户的群体活动，主要是由其中的组织者在上述区域的商家根据活动主题、环境、大家的喜好、禁忌等进行个性化选择，各用户再使用地图导航软件选择到达活动地点的行车路线。这种位置推荐方式简单，但容易出现某些用户能方便便捷地到达、某些用户到达时间过长的状况。各用户到达活动地点的道路是否通达、如何均衡大家到达活动地点的时耗，就成了组织者需要重点考虑的因素。
1.2 道路通达性和时间成本城市道路是社会经济活动的载体，它的规划与建设深刻影响着商业集聚分布[10-13]，而道路通达性通常是指某种特定交通系统到达某一地点或区域的便利程度[14-15]。目前，国内大城市布局大多是单中心圈层式结构，为缓解日益严重的交通拥堵，大城市规划建设的道路交通网络（含轨道交通）主要以“环线-放射线”为主，如图 1所示，环线在现阶段的城市快速交通网络中发挥着骨干作用[16-18]。对在线导航地图中的道路及日常导航路线规划结果进行分析，城市环线多是众多驾车用户及路线规划的优先选项。
|
| 图 1 环线-放射线道路网 Fig. 1 Annular-Radiant Road Network |
本文所涉及的时间成本主要是指人们为参加社交集体活动，采用某种交通工具从工作或生活位置到活动所在地所耗时间。城市发展规模不断扩大、交通拥堵常态化，一天当中，城市中的人们在路上耗费的时间占了较大的比重。当需要参加相关社交集体活动时，越来越多的人们开始考虑从当前位置到活动地点所耗费的时间是否在自身可忍受范围内。
1.3 顾及道路通达性和时间成本的多边形寻址为便于用户能够进一步根据活动主题、环境、特色等进行个性化的选择，通常是在某个区域内给出一系列的商家信息。
在城市复杂路网、路况情况下，人们参加社交集体活动时若需要考虑道路通达和路上时间成本问题，可以利用现有社交网络提供的商家（如饭馆）信息，分别计算各用户到商家的路上时间，根据时间长短进行排序供各用户进行位置选择。但是: (1)如果提供的是全城商家信息，各用户面对的信息量太大，既难以选择又不容易统一思想；(2)如果提供的是某个街区（或商圈）商家信息，用户进一步选择位置的余地受限；(3)若是按某个半径范围内的方式，如何确定合适的半径范围又是个进一步优化的问题。
上述寻址区域主要是由特征点构成。由于城市环线的特点，在两点间的路线导航时，现有导航软件通常优先选择环线再利用环线间的放射线到达目的地。本文通过多种方案对比，选择用户之间行车路线的中点来构成位置推荐的多边形区域。这种方式可以保证区域边界的可到达性，而区域内的道路网确保活动地点的可到达性；用户间的行车路线采用花费时间最少的路线，有利于平衡各用户到达推荐位置所需的时间成本。如图 2所示，A、B、C代表 3个用户，AB、BA分别代表A到B、B到A导航路线的中间点, 其他同理，虚线围成区域为位置推荐区域。对于用户A来说，进入位置推荐区域总有A-AB、A-AC两条路线；同理，对于主体B和C来说, 也各自有B-BA、B-BC和C-CA、C-CB两条路线。在实际的路网中，进入位置推荐区域的路径可能还会更多。
|
| 图 2 多边形区域示意图 Fig. 2 Polygonal Area Schematic |
本文算法利用各用户之间行车路径的中点构造多边形过程中, 需要解决自动识别多边形顶点顺序的问题。利用点集作为参数自动构造的多边形会发生顶点按非理想顺序连接，多边形区域内的位置推荐结果会大幅减少，难以满足用户需求，因此，本文算法采用离散点构建多边形的凸包计算[19-21]对导航路径中点构造的多边形区域进行修正，选取Jarvis步进法实现多边形顶点自动识别，生成多边形。
具体计算步骤如下：
1）将各用户间导航路线中点的经纬度分离为经度、纬度链表；
2）遍历纬度链表，选择纬度最小的点作为多边形的起点和极角起点；
3）从极角起点分别连接点集中其他各点，计算各连线极角；
4）遍历所有极角，将极角最小的点放入多边形顶点集中，并设为新的极角起点；
5）重复步骤3）、4），直至最终所求多边形顶点为最初的起点。
1.5 算法流程由于对道路通达性好和消耗较少的时间成本的预期，本文算法选择多用户间行车路线的中点构成多边形区域，在多边形区域内搜索商家信息进行位置推荐，以满足多用户的位置需求，主要算法流程如图 3所示。
|
| 图 3 算法流程图 Fig. 3 Flowchart of the Proposed Algorithm |
算法具体步骤如下：
1）获取n个用户A1、A2…An位置的经纬度坐标；
2）选取Ai（i=1…n）点作为起点，针对其他n-1个用户分别求取驾车导航路径Lj（j=1…i-1, i+1…n）；
3）从返回的每条导航路径点集Lj（j=1…i-1, i+1…n）中分别提取该路径中点，记为Bij；
4）分别选取A2…An点作为起点，重复步骤2）、3）；
5）利用上述获取的路径中点，自动识别生成位置推荐区域多边形；
6）以位置推荐区域多边形为参数，搜索多边形区域内的商家信息，给出推荐位置。
2 多用户位置推荐算法实验为了验证顾及道路通达性和时间成本的多用户位置推荐算法的可行性和效果，在高德地图应用程序接口的基础上，利用J2EE+SSM技术框架设计实现了一个多用户位置推荐实验系统。
2.1 实验系统设计实验系统利用高德地图API[22-25]提取驾车导航路线的经纬度坐标点信息，获取以用户位置为中心的数字地图为底图，通过地理编码（反地理编码）接口实现地名地址、地图点选两种用户地址输入方式。位置推荐结果链接阿里巴巴的商家信息页面，提供商家联系方式、团购、折扣等详细信息。
在Windows环境下，实验系统利用Java、JavaScript进行开发，采用B/S架构，包括数据层、应用层和表现层，整个系统的架构及主界面分别如图 4、图 5所示。
|
| 图 4 系统架构 Fig. 4 System Architecture |
|
| 图 5 系统主界面 Fig. 5 System Interface |
由于所在城市具备三重环线系统且正值多条地铁线路施工期间，城市路网存在单行线路、禁左（右）等道路类型，因此，选择所在城市作为实验区域。利用实验系统，在二环区域内选择道路复杂的地段，设计了两套实验方案，如表 1所示。实验选择驾车(AMap.Driving)的交通方式，采用默认的时间消耗最少的路线，搜索商户分类为“美食”。
| 方案 | 用户地址 | 备注 |
| 3用户 | A：黄土坡立交桥 B：昆明理工大学 C：环城南路地铁站 |
附近的学府路属于单向通行道路，绕行路线较多 |
| 6用户 | A：津桥学院 B：省水文水资源局 C：西山区政府 D：西华小区 E：福德立交桥 F：龙泉里小区 |
用户主要位于居民区密度较高的单位以及学校区域 |
两种实验方案中, 选择的各用户位置分布如图 6、图 7所示。
|
| 图 6 3用户位置 Fig. 6 Location of 3 Users |
|
| 图 7 6用户位置 Fig. 7 Location of 6 Users |
|
| 图 8 3用户的实验结构 Fig. 8 Experimental Results of 3 Users |
|
| 图 9 6用户的实验结构 Fig. 9 Experimental Results of 6 Users |
上述位置推荐结果在界面右侧分3页显示。为了分析各用户到位置推荐结果的道路通达性和时间成本，在两个实验方案的位置推荐结果中，每个分页选取5项，总共抽取15个位置，分别计算用户所在地到推荐位置的路程和所需时间，结果统计及分析见表 2。
| 方案 | 平均耗时/min | 路程 |
| 3用户 | 11~15.6 | 平均路程在3.9~5.4 km之间，无绕路情况 |
| 6用户 | 17~19.8 | 平均路程在5.5~6.5 km之间，绕路情况少，E点至“欢喜拾味云南菜馆”、F点至“一栋洋楼”、F点至“蔼若春”各躲避拥堵路段200、500、100 m |
两个实验结果中，推荐的位置更靠近区域内的路况复杂地块，各用户到达推荐位置的道路通行状况较好，路程与时间消耗相差不大，各用户到各个推荐位置的驾车路程有差异但相近。
3 结语现代城市生活工作节奏的加快，促使人们在参加集体社交活动时重点关注道路的通达性和往返的时间成本。针对多用户社交活动的位置选择需求，本文提出的方法利用用户间导航路线的中点构建了多边形位置推荐区域，能够较好地综合考虑多用户对道路通达性和时间成本的要求。在地图API基础上采用Web技术建立了一个实验系统，进行了算法的具体验证。通过真实数据的实验验证，结果表明本文的方法较好地平衡了各用户到推荐位置的道路可达性和所耗时间成本，能够满足多用户社交活动集体规划需求，同时也可以为商家选址、城市规划等提供参考。
实际应用中，由于选择活动位置的时间段（如上午）和参加活动的时间段（如晚间下班高峰）不同，因此本文后续研究将引入过往数据，模拟参加活动时间段的导航路线建立多边形推荐区域。同时，如果用户过于集中于一个地区，也可以通过增加个别的虚拟用户来扩大寻址区域范围。
| [1] |
Dai Shifang, Li Yan, Hai Lin. Personalized Location Recommendation Algorithm Mixing Multi-Factors[J]. Computer Engineering, 2018, 44(6): 300-304. (代仕芳, 李燕, 海凛. 多因素融合的个性化位置推荐算法[J]. 计算机工程, 2018, 44(6): 300-304. DOI:10.3969/j.issn.1000-3428.2018.06.051 ) |
| [2] |
Ju Ping. Research on Recommendation Algorithm in Location Based Social Network[D]. Changchun: Jilin University, 2016 (鞠萍.基于位置的社交网络推荐算法研究[D].长春: 吉林大学, 2016) http://cdmd.cnki.com.cn/Article/CDMD-10183-1016084565.htm
|
| [3] |
Jing Ning, Wang Yuehua, Zhong Zhinong, et al. Location Recommendation on Location-Based Social Networks[J]. Journal of National University of Defense Technology, 2015, 37(5): 1-8. (景宁, 王跃华, 钟志农, 等. 地理社交网络位置推荐[J]. 国防科技大学学报, 2015, 37(5): 1-8. ) |
| [4] |
Liu Shudong, Meng Xiangwu. Recommender Systems in Location-Based Social Networks[J]. Chinese Journal of Computers, 2015, 38(2): 322-336. (刘树栋, 孟祥武. 基于位置的社会化网络推荐系统研究[J]. 计算机学报, 2015, 38(2): 322-336. ) |
| [5] |
Wang Teng, Wang Yandong, Zhao Xiaoming, et al. Network-Constrained Spatial Point Pattern Analysis for Commercial Facilities[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1746-1752. (王腾, 王艳东, 赵晓明, 等. 顾及道路网约束的商业设施空间点模式分析[J]. 武汉大学学报·信息科学版, 2018, 43(11): 1746-1752. ) |
| [6] |
Yu Wenhao, Ai Tinghua, Yang Min, et al. Detecting "Hot Spots" of Facility POIs Based on Kernel Density Estimation and Spatial Autocorrelation Technique[J]. Geomatics and Information Science of Wuhan University, 2016, 41(2): 221-227. (禹文豪, 艾廷华, 杨敏, 等. 利用核密度与空间自相关进行城市设施兴趣点分布热点探测[J]. 武汉大学学报·信息科学版, 2016, 41(2): 221-227. ) |
| [7] |
Wang Yandong, Li Hao, Wang Teng, et al. The Mining and Analysis of Emergency Information in Sudden Events Based on Social Media[J]. Geomatics and Information Science of Wuhan University, 2016, 41(3): 290-297. (王艳东, 李昊, 王腾, 等. 基于社交媒体的突发事件应急信息挖掘与分析[J]. 武汉大学学报·信息科学版, 2016, 41(3): 290-297. ) |
| [8] |
D'Roza T, Bilchev G. An Overview of Location-Based Services[J]. BT Technology Journal, 2003, 21(1): 20-27. DOI:10.1023/A:1022491825047 |
| [9] |
Schiller J H, Voisard A. Location-Based Services[M]. San Francico: Morgan Kaufmann, 2004.
|
| [10] |
Tian Jing, Wu Dang, Zhan Yifei. Degree Correlation of Urban Street Networks[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3): 332-334. (田晶, 吴荡, 湛逸飞. 城市道路网的度相关性研究[J]. 武汉大学学报·信息科学版, 2014, 39(3): 332-334. ) |
| [11] |
She Bing, Zhu Xinyan, Su Kehua, et al. Test Methods for Space-Time Interaction of Events Under Road Network Constraints[J]. Geomatics and Information Science of Wuhan University, 2015, 40(3): 353-356. (佘冰, 朱欣焰, 苏科华, 等. 道路网约束下的事件时空交互检验方法研究[J]. 武汉大学学报·信息科学版, 2015, 40(3): 353-356. ) |
| [12] |
Tian Jing, Yu Mengting, Ren Chang, et al. Network-Scape Metric Analysis for Celluar Pattern Analysis in Urban Street Networks[J]. Geomatics and Information Science of Wuhan University, 2018, 43(10): 1588-1594. (田晶, 余梦婷, 任畅, 等. 城市道路网元胞模式分析的网络景观指数分析法[J]. 武汉大学学报·信息科学版, 2018, 43(10): 1588-1594. ) |
| [13] |
Han Yuyao, Jiao Limin, Xu Gang. Correlation Analysis of Road Structure and Commerical Agglomeration in Wuhan City[J]. Progress in Geography, 2017, 36(11): 1349-1358. (韩宇瑶, 焦利民, 许刚. 武汉市道路结构与商业集聚空间关联分析[J]. 地理科学进展, 2017, 36(11): 1349-1358. ) |
| [14] |
Hansen W G. How Accessibility Shapes Land-Use[J]. Journal of the American Institute of Planners, 1959, 25(2): 73-76. |
| [15] |
Li Pinghua, Lu Yuqi. Review and Prospectation of Accessibility Research[J]. Progress in Geography, 2005, 24(3): 69-78. (李平华, 陆玉麒. 可达性研究的回顾与展望[J]. 地理科学进展, 2005, 24(3): 69-78. DOI:10.3969/j.issn.1007-6301.2005.03.009 ) |
| [16] |
Xu Zhiwei. Analysis of Urban Loop Traffic Adaptability[D]. Chengdu: Southwest Jiaotong University, 2013 (徐志威.城市环线交通适应性分析[D].成都: 西南交通大学, 2013) http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y2577496
|
| [17] |
Wang Wanying. Research on the Relationship Between Urban Road Network and Rail Transit Line Network[J]. Journal of Railway Engineering Society, 2017(2): 81-86. (王婉莹. 城市道路网与轨道交通线网形态的关系研究[J]. 铁道工程学报, 2017(2): 81-86. DOI:10.3969/j.issn.1006-2106.2017.02.016 ) |
| [18] |
Feng Shumin, Gao He, Guo Caixiang. Evaluation of Urban Road Network Structure[J]. Journal of Harbin Institute of Technology, 2007, 39(10): 1610-1613. (冯树民, 高贺, 郭彩香. 城市道路网结构形式的评价[J]. 哈尔滨工业大学学报, 2007, 39(10): 1610-1613. DOI:10.3321/j.issn:0367-6234.2007.10.023 ) |
| [19] |
Mao Peng. Fast Convexhull Computation Implementation and Its Application[D]. Xi'an: Xidian University, 2013 (毛鹏.快速凸包计算实现及其应用[D].西安: 西安电子科技大学, 2013) http://cdmd.cnki.com.cn/Article/CDMD-10701-1013297618.htm
|
| [20] |
Huang Yi, Wang Yunjia, Hu Zhaoling, et al. Center's Service Area Considering Topology[J]. Geomatics and Information Science of Wuhan University, 2013, 38(1): 105-108. (黄翌, 汪云甲, 胡召玲, 等. 考虑图形关系的中心服务范围确定[J]. 武汉大学学报·信息科学版, 2013, 38(1): 105-108. ) |
| [21] |
Wang Jiechen, Chen Yanming. A Gird-Aided Algorithm for Determining the Minimum Convex Hull of Planar Points Set[J]. Geomatics and Information Science of Wuhan University, 2010, 35(4): 403-406. (王结臣, 陈焱明. 一种栅格辅助的平面点集最小凸包生成算法[J]. 武汉大学学报·信息科学版, 2010, 35(4): 403-406. ) |
| [22] |
Tian Qin, Gong Yue, Kang Mengjun, et al. A Comparative Evaluation of Online Geocoding Services in China[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1351-1358. (田沁, 巩玥, 亢孟军, 等. 国内主流在线地理编码服务质量评价[J]. 武汉大学学报·信息科学版, 2016, 41(10): 1351-1358. ) |
| [23] |
Liu Xiao. The Design and Implementation of Natural Language Interface for Highmoralmap via Semantic Parsing[D]. Nanjing: Nanjing Normal University, 2015 (刘晓.面向高德地图的自然语言接口语义解析系统设计与实现[D].南京: 南京师范大学, 2015) http://cdmd.cnki.com.cn/Article/CDMD-10319-1015430306.htm
|
| [24] |
Wang Zicong. The Intelligent Transport System and Positioning Algorithm Based on the Android Platform[D]. Changchun: Jilin University, 2016 (王子聪.基于Android平台的智能公交系统及定位算法研究[D].长春: 吉林大学, 2016) http://cdmd.cnki.com.cn/Article/CDMD-10183-1017009754.htm
|
| [25] |
Chen Mingdong. Research and Development on Transportation Information Interaction Platform Based on Floating Car[D]. Harbin: Harbin Institute of Technology, 2016 (陈明东.基于浮动车的交通信息交互平台研究与开发[D].哈尔滨: 哈尔滨工业大学, 2016) http://cdmd.cnki.com.cn/Article/CDMD-10213-1016915053.htm
|