李建伏, 王思博, 宋国平
(中国民航大学 计算机科学与技术学院, 天津 300300)
路径规划是指从道路网络中寻找从起始节点到目的节点的最优路径. 传统路径规划算法通常利用经典的图搜索算法(如Dijkstra, Floyd和A*算法)在道路网络中寻找最短路径. 但在实际应用中, 路径长度不是人们选择出行路径的唯一标准. 为使规划的路径能满足用户的实际需求, 路径规划被进一步形式化为多目标最短路径问题[1]或多约束最短路径问题[2-3], 即将用户的出行偏好建模为多个目标或约束. 但用户的出行偏好受多种因素影响, 而这些因素如何影响用户偏好未知, 甚至用户自己也无法准确地表达其出行偏好. 因此, 不能准确地描述用户出行偏好已成为限制多目标路径规划或多约束路径规划发展的瓶颈.
近年来, 随着全球定位系统(global positioning system, GPS)技术的发展及移动设备的普及, 已产生并收集了大量用户出行的轨迹数据. 轨迹数据中蕴含用户的出行偏好, 从而为获得用户的出行偏好并进一步制定最优路径规划提供了可行性. 基于轨迹的路径规划目前已成为该领域广泛关注的问题. 理想情况下, 连接任意两点的每条路径均被足够多的历史轨迹覆盖, 此时, 基于轨迹的路径规划算法只需计算每条路径的出现频次并返回频次最多的路径即可. 实际上, 大量轨迹都集中在某些局部区域, 在很多节点对之间未被历史轨迹覆盖. 因此, 现有基于轨迹的路径规划算法的基……