地球信息科学学报

地球信息科学学报 ›› 2014, Vol. 16 ›› Issue (6): 867-873.doi: 10.3724/SP.J.1047.2014.00867

• • 上一篇    下一篇

面向智能导游的双加权图模型及其路径规划

史永1,2(), 龙毅1,*(), 陈林1, 吴小玲1   

  1. 1. 南京师范大学地理科学学院,虚拟地理环境教育部重点实验室,南京 210023
    2. 南京师范大学泰州学院信息工程学院,泰州 225300
  • 收稿日期:2014-03-24 修回日期:2014-06-03 出版日期:2014-11-10 发布日期:2014-11-01
  • 通讯作者: 龙毅 E-mail:shiy_tz@163.com;longyi@njnu.edu.cn
  • 作者简介:

    作者简介：史永(1977-),男,博士生,副教授,山东滕州人,主要从事智能计算与内容服务,位置服务技术研究。E-mail:shiy_tz@163.com

  • 基金资助:
    国家自然科学基金项目“基于多时空粒度的旅游行程链模型与游客行为模式研究”(41301144);常熟市海内外领军型创业创新人才项目“新一代智能行人导航技术及其产业化应用”(CSRC1130);江苏省“青蓝工程”(2010)项目;南京市发改委项目“城市休闲智慧信息服务系统”

Research on Double-Weighted Graph Model and Optimal Path Planning for Intelligent Tourism Navigation Considering Entrances and Exits

SHI Yong1,2(), LONG Yi1,*(), CHEN Lin1, WU XiaoLing1   

  1. 1. School of Geographic Science, Nanjing Normal University,.MOE Key Laboratory of Virtual Geographical Environment, Nanjing 210023, China
    2. School of Information Engineering, Nanjing Normal University Taizhou College, Taizhou 225300, China
  • Received:2014-03-24 Revised:2014-06-03 Online:2014-11-10 Published:2014-11-01
  • Contact: LONG Yi E-mail:shiy_tz@163.com;longyi@njnu.edu.cn
  • About author:

    *The author: CHEN Nan, E-mail:fjcn99@163.com

RichHTML

PDF (PC)

赞

被引次数

3

摘要：

景区游览线路是游客游览不同景点的有效选择路径。在导航系统中通常结合各景点POI(Point of Interest)和景区路网的路径规划而生成,但是,针对具有一定范围与多出入口的景点(如建筑物类景点),单一的POI坐标描述机制规划产生的游览路径,往往与智能导游应用中实际可行的最优游览路径存在明显差异。本文分析了景点大小、多出入口等特征对景区游览路径规划的影响,提出了顶点和边的权重均可动态选择的景区双加权图模型,突破了单一POI描述机制的限制。同时,讨论了景区双加权图模型的化简、构建方法,并以Dijkstra算法和Prim算法为基础,给出了其最优路径规划求解算法。实验表明,本文模型及其最优路径规划算法所得结果更为优化与合理,具有较少的游览规划距离和更为紧凑的游览过程安排。

关键词: 最优路径规划, 双加权图模型, 多出入口, 智能导游, 图模型

Abstract:

When visiting multiple tourist scenic spots, a recommended travel line is usually the most effective route designed for tourists according to the actual road situations. In the field of intelligent tourism navigation, a traditional recommended travel line is mainly generated by path planning algorithm automatically, considering thescenic spots’ positions and road networks based on graph model. Normally, the traditional algorithms firstly map scenic spots (which belong to certain scenic area) into points of interests (POIs),and map the road network that links these POIs into a line collection, then build the corresponding graph model. But when a scenic spot has a limited area and involves multiple entrances or exits(for example buildings with multiple indoor space), the traditional described mechanism for single point coordinates is difficult to reflect these structural features. In reality, scenic area path planning is widely applied in the field of mobile tourism guide recently, especially for pedestrians. There exist significant differences between theoretical optimal paths and actual optimal paths, sincetouristsare inclined to have more choices. In order to solve this problem, this paper analyzed various influences on the process of path planning, caused by scenic spots’ own structural features (such as the size, shape and entrance), and focused on the influences of multiple entrances or exits located within the scenic area. Then,we proposed a Double-Weighted Graph Model considering multiple entrances and exits for tourist scenic area, and the weights of both vertexes and edges of the proposed model can be selected and weighted dynamically. Next, we discussed the building method for the model, and proposed an optimal path planning algorithm based on Dijkstra algorithm and Prim algorithm. Experimental results show that the optimal planned travel line derived from this proposed model and algorithms is considerably reasonable, and the travelling order and travelling distance can be further optimized.

Key words: optimal path planning, Double-Weighted Graph Model, multiple entrances or exits, tour guide, tourist routes