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

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

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

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 tra-ditional described mechanism for single point coordinates is difficult to reflect these structural features. In reali-ty, scenic area path planning is widely applied in the field of mobile tourism guide recently, especially for pedes-trians. There exist significant differences between theoretical optimal paths and actual optimal paths, sincetourist-sare 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 o