Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles     Next Articles

Shortest Time Path Algorithm Based on Shared Location Data

ZHU Han1, LI Huaiyu1, XIAO Han1, CHEN Xiuwan1, WANG Tingting2   

  1. 1. Institute of Remote Sensing and Geographical Information Systems, Peking University, Beijing 100871; 2. Unicore Communications Inc., Beijing 100094;
  • Received:2013-10-22 Online:2015-01-20 Published:2015-01-20



  1. 1. 北京大学遥感与地理信息系统研究所, 北京 100871; 2. 和芯星通科技北京有限公司, 北京 100094;

Abstract: In order to meet the need of reaching destination through a shortest time, while distributing flow reasonably, using public resources plenty, easing urban traffic jam during work peak period, the authors propose a shortest time target optimal path algorithm based on LBPSS (location based participatory sensing service) data. The algorithm is supposed to solve the lack of traffic information, road network coverage shortage, hysteresis traffic data update and data inconformity with reality. Then the goal of route navigation combining real-time traffic information can be achieved. Finally combining the ArcGIS and Android platform, using great methods of database as quick query, indexes and collections, the authors bring about an application example of shortest time path algorithm based on LBPSS data. Compared with recently popular algorithms, the feasibility and effectiveness of proposed algorithm are verified. The result shows that the algorithm proposed has more practical value in distributing traffic flow reasonably, in easing urban traffic jam during work peak period effectively and saving travel time wisely.

Key words: LBPSS, shortest time, optimal path

摘要: 为了满足人们以最短时间到达目的地的出行需求, 同时合理化地分配人流, 更加充分地利用公共资源, 缓解城市高峰期的道路拥堵问题, 提出一种基于共享位置数据(LBPSS)并以最短时间为目标的最优路径算法, 解决路况信息路网覆盖率不足、更新缓慢及其与现实路况不符等问题, 实现结合实时路况信息的路径导航。结合ArcGIS平台和Android平台, 利用数据库的快速查询、索引支持和集合运用方面的优秀性能, 实现基于共享位置数据的最短时间路径算法的应用实例, 并与目前的常用算法进行试验比较, 验证该算法的可行性和有效性。结果表明, 该方法更具实用价值, 在节省出行时间的同时, 更加合理地对高峰期拥堵道路的车辆进行分流。

关键词: LBPSS, 最短时间, 最优路径

CLC Number: