留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

顾及道路通达性和时间成本的多用户位置推荐

宁津生 吴学群 刘子尧

宁津生, 吴学群, 刘子尧. 顾及道路通达性和时间成本的多用户位置推荐[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026
引用本文: 宁津生, 吴学群, 刘子尧. 顾及道路通达性和时间成本的多用户位置推荐[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026
NING Jinsheng, WU Xuequn, LIU Ziyao. Multi-user Location Recommendation Considering Road Accessibility and Time-Cost[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026
Citation: NING Jinsheng, WU Xuequn, LIU Ziyao. Multi-user Location Recommendation Considering Road Accessibility and Time-Cost[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026

顾及道路通达性和时间成本的多用户位置推荐

doi: 10.13203/j.whugis20190026
基金项目: 

国家自然科学基金 41561083

国家自然科学基金 41561082

详细信息
    作者简介:

    宁津生, 教授, 博士生导师, 中国工程院院士, 主要从事测绘地理领域的理论与方法研究。jsning@sgg.whu.edu.cn

    通讯作者: 吴学群, 博士生。wuxuequn520@163.com
  • 中图分类号: P208

Multi-user Location Recommendation Considering Road Accessibility and Time-Cost

Funds: 

The National Natural Science Foundation of China 41561083

The National Natural Science Foundation of China 41561082

More Information
    Author Bio:

    NING Jinsheng, professor, Academician of Chinese Academy of Engineering, specializes in the scientific research and teaching work of geomatics field. E-mail: jsning@sgg.whu.edu.cn

    Corresponding author: WU Xuequn, PhD candidate. E-mail: wuxuequn520@163.com
图(9) / 表(2)
计量
  • 文章访问数:  724
  • HTML全文浏览量:  109
  • PDF下载量:  182
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-01-17
  • 刊出日期:  2019-05-05

顾及道路通达性和时间成本的多用户位置推荐

doi: 10.13203/j.whugis20190026
    基金项目:

    国家自然科学基金 41561083

    国家自然科学基金 41561082

    作者简介:

    宁津生, 教授, 博士生导师, 中国工程院院士, 主要从事测绘地理领域的理论与方法研究。jsning@sgg.whu.edu.cn

    通讯作者: 吴学群, 博士生。wuxuequn520@163.com
  • 中图分类号: P208

摘要: 位置推荐是地理社交网络的重要应用,针对城市范围内多用户集体社交活动的规划需求,在顾及道路通达性和时间成本的情况下进行位置推荐算法的研究。针对城市路网结构特征和导航路线规划特点,在地图应用程序接口的支持下,利用各用户间导航路线上的特定点自动识别、构建区域实现位置推荐,平衡多个用户到推荐地点的可到达性和时间成本。实验结果验证了所提方法的有效性,在地理社交网络上可以为城市多用户的集体活动提供有效的位置推荐方案。

English Abstract

宁津生, 吴学群, 刘子尧. 顾及道路通达性和时间成本的多用户位置推荐[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026
引用本文: 宁津生, 吴学群, 刘子尧. 顾及道路通达性和时间成本的多用户位置推荐[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026
NING Jinsheng, WU Xuequn, LIU Ziyao. Multi-user Location Recommendation Considering Road Accessibility and Time-Cost[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026
Citation: NING Jinsheng, WU Xuequn, LIU Ziyao. Multi-user Location Recommendation Considering Road Accessibility and Time-Cost[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 633-639. doi: 10.13203/j.whugis20190026
  • 随着通信、室内外定位、互联网技术的快速发展,位置服务融入传统社交网络形成了地理社交网络(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获得推荐位置后,可以利用导航定位软件判断自己当前位置到活动地点的距离和时间成本,但针对城市范围内的多个用户,上述方法就难以满足多个用户对距离和时间成本的集体规划需求。本文主要是针对城市范围内集体社交活动(如聚会、沙龙、派对、健身、运动等)场地选择的需求,综合考虑参加活动的多个用户所在位置到活动地点的道路通达性和时间成本,利用现有在线地图资源进行多用户位置推荐方法的研究。

    • 现有的基于位置的社交网络主要是采用全城、某个街区(商业区)、附近多少千米范围内、多用户构成的区域等4种方式为用户进行商家位置的推荐。若是多个用户的群体活动,主要是由其中的组织者在上述区域的商家根据活动主题、环境、大家的喜好、禁忌等进行个性化选择,各用户再使用地图导航软件选择到达活动地点的行车路线。这种位置推荐方式简单,但容易出现某些用户能方便便捷地到达、某些用户到达时间过长的状况。各用户到达活动地点的道路是否通达、如何均衡大家到达活动地点的时耗,就成了组织者需要重点考虑的因素。

    • 城市道路是社会经济活动的载体,它的规划与建设深刻影响着商业集聚分布[10-13],而道路通达性通常是指某种特定交通系统到达某一地点或区域的便利程度[14-15]。目前,国内大城市布局大多是单中心圈层式结构,为缓解日益严重的交通拥堵,大城市规划建设的道路交通网络(含轨道交通)主要以“环线-放射线”为主,如图 1所示,环线在现阶段的城市快速交通网络中发挥着骨干作用[16-18]。对在线导航地图中的道路及日常导航路线规划结果进行分析,城市环线多是众多驾车用户及路线规划的优先选项。

      图  1  环线-放射线道路网

      Figure 1.  Annular-Radiant Road Network

      本文所涉及的时间成本主要是指人们为参加社交集体活动,采用某种交通工具从工作或生活位置到活动所在地所耗时间。城市发展规模不断扩大、交通拥堵常态化,一天当中,城市中的人们在路上耗费的时间占了较大的比重。当需要参加相关社交集体活动时,越来越多的人们开始考虑从当前位置到活动地点所耗费的时间是否在自身可忍受范围内。

    • 为便于用户能够进一步根据活动主题、环境、特色等进行个性化的选择,通常是在某个区域内给出一系列的商家信息。

      在城市复杂路网、路况情况下,人们参加社交集体活动时若需要考虑道路通达和路上时间成本问题,可以利用现有社交网络提供的商家(如饭馆)信息,分别计算各用户到商家的路上时间,根据时间长短进行排序供各用户进行位置选择。但是: (1)如果提供的是全城商家信息,各用户面对的信息量太大,既难以选择又不容易统一思想;(2)如果提供的是某个街区(或商圈)商家信息,用户进一步选择位置的余地受限;(3)若是按某个半径范围内的方式,如何确定合适的半径范围又是个进一步优化的问题。

      上述寻址区域主要是由特征点构成。由于城市环线的特点,在两点间的路线导航时,现有导航软件通常优先选择环线再利用环线间的放射线到达目的地。本文通过多种方案对比,选择用户之间行车路线的中点来构成位置推荐的多边形区域。这种方式可以保证区域边界的可到达性,而区域内的道路网确保活动地点的可到达性;用户间的行车路线采用花费时间最少的路线,有利于平衡各用户到达推荐位置所需的时间成本。如图 2所示,ABC代表 3个用户,ABBA分别代表ABBA导航路线的中间点, 其他同理,虚线围成区域为位置推荐区域。对于用户A来说,进入位置推荐区域总有A-ABA-AC两条路线;同理,对于主体BC来说, 也各自有B-BAB-BCC-CAC-CB两条路线。在实际的路网中,进入位置推荐区域的路径可能还会更多。

      图  2  多边形区域示意图

      Figure 2.  Polygonal Area Schematic

    • 本文算法利用各用户之间行车路径的中点构造多边形过程中, 需要解决自动识别多边形顶点顺序的问题。利用点集作为参数自动构造的多边形会发生顶点按非理想顺序连接,多边形区域内的位置推荐结果会大幅减少,难以满足用户需求,因此,本文算法采用离散点构建多边形的凸包计算[19-21]对导航路径中点构造的多边形区域进行修正,选取Jarvis步进法实现多边形顶点自动识别,生成多边形。

      具体计算步骤如下:

      1)将各用户间导航路线中点的经纬度分离为经度、纬度链表;

      2)遍历纬度链表,选择纬度最小的点作为多边形的起点和极角起点;

      3)从极角起点分别连接点集中其他各点,计算各连线极角;

      4)遍历所有极角,将极角最小的点放入多边形顶点集中,并设为新的极角起点;

      5)重复步骤3)、4),直至最终所求多边形顶点为最初的起点。

    • 由于对道路通达性好和消耗较少的时间成本的预期,本文算法选择多用户间行车路线的中点构成多边形区域,在多边形区域内搜索商家信息进行位置推荐,以满足多用户的位置需求,主要算法流程如图 3所示。

      图  3  算法流程图

      Figure 3.  Flowchart of the Proposed Algorithm

      算法具体步骤如下:

      1)获取n个用户A1A2An位置的经纬度坐标;

      2)选取Aii=1…n)点作为起点,针对其他n-1个用户分别求取驾车导航路径Ljj=1…i-1, i+1…n);

      3)从返回的每条导航路径点集Ljj=1…i-1, i+1…n)中分别提取该路径中点,记为Bij

      4)分别选取A2An点作为起点,重复步骤2)、3);

      5)利用上述获取的路径中点,自动识别生成位置推荐区域多边形;

      6)以位置推荐区域多边形为参数,搜索多边形区域内的商家信息,给出推荐位置。

    • 为了验证顾及道路通达性和时间成本的多用户位置推荐算法的可行性和效果,在高德地图应用程序接口的基础上,利用J2EE+SSM技术框架设计实现了一个多用户位置推荐实验系统。

    • 实验系统利用高德地图API[22-25]提取驾车导航路线的经纬度坐标点信息,获取以用户位置为中心的数字地图为底图,通过地理编码(反地理编码)接口实现地名地址、地图点选两种用户地址输入方式。位置推荐结果链接阿里巴巴的商家信息页面,提供商家联系方式、团购、折扣等详细信息。

      在Windows环境下,实验系统利用Java、JavaScript进行开发,采用B/S架构,包括数据层、应用层和表现层,整个系统的架构及主界面分别如图 4图 5所示。

      图  4  系统架构

      Figure 4.  System Architecture

      图  5  系统主界面

      Figure 5.  System Interface

    • 由于所在城市具备三重环线系统且正值多条地铁线路施工期间,城市路网存在单行线路、禁左(右)等道路类型,因此,选择所在城市作为实验区域。利用实验系统,在二环区域内选择道路复杂的地段,设计了两套实验方案,如表 1所示。实验选择驾车(AMap.Driving)的交通方式,采用默认的时间消耗最少的路线,搜索商户分类为“美食”。

      表 1  两种实验方案

      Table 1.  Two Experimental Operations

      方案 用户地址 备注
      3用户 A:黄土坡立交桥
      B:昆明理工大学
      C:环城南路地铁站
      附近的学府路属于单向通行道路,绕行路线较多
      6用户 A:津桥学院
      B:省水文水资源局
      C:西山区政府
      D:西华小区
      E:福德立交桥
      F:龙泉里小区
      用户主要位于居民区密度较高的单位以及学校区域

      两种实验方案中, 选择的各用户位置分布如图 6图 7所示。

      图  6  3用户位置

      Figure 6.  Location of 3 Users

      图  7  6用户位置

      Figure 7.  Location of 6 Users

    • 实验结果如图 8图 9所示。

      图  8  3用户的实验结构

      Figure 8.  Experimental Results of 3 Users

      图  9  6用户的实验结构

      Figure 9.  Experimental Results of 6 Users

      上述位置推荐结果在界面右侧分3页显示。为了分析各用户到位置推荐结果的道路通达性和时间成本,在两个实验方案的位置推荐结果中,每个分页选取5项,总共抽取15个位置,分别计算用户所在地到推荐位置的路程和所需时间,结果统计及分析见表 2

      表 2  实验结果分析

      Table 2.  Experimental Result Analysis

      方案 平均耗时/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

      两个实验结果中,推荐的位置更靠近区域内的路况复杂地块,各用户到达推荐位置的道路通行状况较好,路程与时间消耗相差不大,各用户到各个推荐位置的驾车路程有差异但相近。

    • 现代城市生活工作节奏的加快,促使人们在参加集体社交活动时重点关注道路的通达性和往返的时间成本。针对多用户社交活动的位置选择需求,本文提出的方法利用用户间导航路线的中点构建了多边形位置推荐区域,能够较好地综合考虑多用户对道路通达性和时间成本的要求。在地图API基础上采用Web技术建立了一个实验系统,进行了算法的具体验证。通过真实数据的实验验证,结果表明本文的方法较好地平衡了各用户到推荐位置的道路可达性和所耗时间成本,能够满足多用户社交活动集体规划需求,同时也可以为商家选址、城市规划等提供参考。

      实际应用中,由于选择活动位置的时间段(如上午)和参加活动的时间段(如晚间下班高峰)不同,因此本文后续研究将引入过往数据,模拟参加活动时间段的导航路线建立多边形推荐区域。同时,如果用户过于集中于一个地区,也可以通过增加个别的虚拟用户来扩大寻址区域范围。

参考文献 (25)

目录

    /

    返回文章
    返回