EN中文

地球信息科学学报 >

2014 , Vol. 16 >Issue 6: 867 - 873

DOI: https://doi.org/10.3724/SP.J.1047.2014.00867

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

  • 史永 , 1, 2 ,
  • 龙毅 , 1, * ,
  • 陈林 1 ,
  • 吴小玲 1
展开
  • 1. 南京师范大学地理科学学院,虚拟地理环境教育部重点实验室,南京 210023
  • 2. 南京师范大学泰州学院信息工程学院,泰州 225300
*通讯作者：龙毅(1968-),男,博士,教授,博导,主要从事制图综合理论与方法,智慧旅游等研究。E-mail:

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

收稿日期: 2014-03-24

  要求修回日期: 2014-06-03

  网络出版日期: 2014-11-01

基金资助

国家自然科学基金项目“基于多时空粒度的旅游行程链模型与游客行为模式研究”(41301144)

常熟市海内外领军型创业创新人才项目“新一代智能行人导航技术及其产业化应用”(CSRC1130)

江苏省“青蓝工程”(2010)项目

南京市发改委项目“城市休闲智慧信息服务系统”

收起

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

  • SHI Yong , 1, 2 ,
  • LONG Yi , 1, * ,
  • CHEN Lin 1 ,
  • WU XiaoLing 1
Expand
  • 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
*Corresponding author: LONG Yi, E-mail:

Received date: 2014-03-24

  Request revised date: 2014-06-03

  Online published: 2014-11-01

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

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

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

本文引用格式

史永 , 龙毅 , 陈林 , 吴小玲 . 面向智能导游的双加权图模型及其路径规划[J]. 地球信息科学学报, 2014 , 16(6) : 867 -873 . DOI: 10.3724/SP.J.1047.2014.00867

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

1 引言

传统景区路径规划方法通常结合各景点POI(Point of Interest)和景区路网的路径规划生成[1-2],即通过把景区内的各景点简单抽象为顶点集合V,顶点之间的路网抽象为边集合E,从而构造图 G = V , E ， 运用图论及运筹学算法求解[3-5]。然而,实际中景区路径规划往往结合移动导游应用[6-7],即在步行游览过程中,导游路径规划以游客当前位置为起点,在仅考虑景点POI及其间路网时,所得到的最优路径规划往往与实际最优的游览路径存在明显差异。
图1(a)中景点A、B具有3个出入口,景点C具有2个出入口。在传统路径规划过程中,景点A、B、C作为POI映射到景区路网上分别为点Pa、点Pb和点Pc,进而得到传统规划路径L1,如图1(b)所示。但是考虑到景点A、B中景点自身出入口的连通性,得到实际可行的较优游览路径L2,如图1(c)所示。路径L1和L2中存在显著差异,其主要原因是景点出入口的内部连通性改变了原有路网的拓扑连接关系,进而改变了路径规划结果。
Fig. 1 Sketch maps of planned routes for touring scenic spot A, B and C

图1 游览景点A,B,C最优路径规划示意图

本文针对景点自身结构特征对于景区路径规划的影响展开分析,探讨了顾及多出入口情况下的景区路径规划模型与算法,并进行实验对比分析。

2 景点结构特征分析

景区路径规划把景点抽象为POI,利于基于图论及多智能体遗传算法、蚁群算法等人工智能算法开展最优规划求解[8-10],其规划结果一般表达为景点游览次序、线路距离和总游时等多个推荐部分。长期以来,人们对景点在路径规划中的影响研究,多从旅游个性化的角度,以推荐游览时间的方式开展[11],顾及了景点知名度[5]以及距离[21]等多个要素,但忽视了景点自身大小、形状等在实际游览中的影响。这是因为景点的大小、形状等范围结构特征和景点内部路网紧密相关,而内部路网把景观串联在一起,甚至本身也是景观的一部分。考虑到游客的旅游偏好、出行自主性及需求个性化等客观因素存在[12-13],把景点的范围结构特征对路径规划的影响归纳为推荐游时并加以研究[14]是比较合理的。
然而,面向散客自由行特别是步行条件下的旅游方式,景点的多出入口结构特征使得游客在实际游览中具有多种可选的离开景点方式,从而导致面对的下一个景点有所不同。并且随着景点的出入口的越多,游客进、出景点的实际选择就越多,导致实际的游览线路和推荐规划线路存在偏差的概率增大。表1详细总结了景点多出入口特征对路径规划产生的影响,并依据景点多出入口特征把景点分为了点状景点、线状景点、面状景点3类。其中,点状结构景点是指景点无内部路网或者景点与路网有一个出入口联通的景点。
Tab. 1 Influence on path planning from scenic spots’entrances or exits

表1 景点多出入口特征对路径规划的影响

景点分类 特征描述 路径规划影响
点状景点(POI) 景点无内部路网或有1个出入口 一种离开方式,对下一个景点选择及线路规划距离均无影响
线状景点(LOI) 景点有2个出入口 2种离开方式,景点内路网为景区唯一路网时,对下一个景点选择不产生影响;由于游览过程即是行程过程,会对规划距离产生影响
面状景点(AOI) 景点多于2出入口 多种离开方式,对下一个景点选择会产生影响,同时会对规划距离产生影响
显而易见,相比于传统的景区路径规划方法,顾及景点多出入口条件下的路径规划分析是贴近游览实际和更加精细化的规划方法。因此,本文从景点的多出入口结构特征入手,提出了顶点和边的权重均可动态选择的景区双加权图模型,并讨论其最优规划路径算法。

3 景区双加权图模型

在传统景区图模型基础上,双加权图通过增加顶点出入口位置的动态选择,从而体现景区自身的结构特征对景区路线规划的影响,改进了传统景区图模型顶点不变,而顶点与边的权值可变的最优路径求解模式[15]。本文给出景点、景区图模型的定义,并以距离权值为例,给出其顶点、边的权重函数和最优路径定义。
(1)景点模型
S = S ' , T S S ' = s i i = 1,2 , … , n (1)
式(1)中,S代表景点; S ' 表示景点S的出入口位置集合,si表示景点S的出入口;n表示景点S的出入口个数;TS表示景点S的推荐游时(游览时间)。
(2)景区图模型G
G = V , E V = S i ' | i = 1,2 , … , m E = S kx , S jy | s kx ∈ S k ' , s jy ∈ S j ' (2)
式(2)中, S i ' 表示景区第i个景点的出入口集合;m表示景区包含景点的数量;Skx(Sjy)表示第k(j)景点的第x(y)个出入口。
从式(1)、(2)可看出,景区双加权模型由于其顶点是相应景点的出入口集合,导致该模型是具有多重边的复杂图。
(3)边的权重函数 f ( S k , S j )
f S k , S j = T k k = j , S k ∉ V , S k ∈ N min dis S kx , S jy | x , y = 1,2 , … , cou ( S k ' ) k = j , S k ∈ M min dis S kx , S jy x = 1,2 , … , cou S k ' , y = 1,2 , … , cou ( S j ' ) k ≠ j , S kx ∉ V ' , S k ∈ N min dis S kx , S jy | x = 1,2 , … , cou S k ' , y = 1,2 , … , cou ( S j ' ) k ≠ j , V kx ∈ V ' , S k ∈ M ∞ ∃ spz ∈ S p ' , and f S kx , S jy = f S k , S p + f S p , S j (3)
式(3)中, d is S kx , S jy 为基于Dijkstra算法求解顶点Skx,Sjy最短路径距离函数;min({})为求集合中最小元素函数;cou({})为求集合元素个数函数; V ' 为已遍历出入口集合;N为必游景点集合;M为路过景点或不玩景点集合。
(4)进入景点(图顶点)的权重函数 f ' ( s , S i ' ) )
f ' s , S i ' = min dis s , S ix | x = 1,2 , … , cou ( S i ' ) (4)
式(4)中,s表示当前起始点或者确定的景点的出入口;Six表示景点Si第x个出入口的位置。
(5)离开景点(图顶点)的权重函数 f ' ( S i ' , S j ' ) )
f ' ( S i ' , S j ' ) ) = min dis S ix , S jy (5)
式(5)中 x = 1,2 , … , cou S i ' y = 1,2 , … , cou ( S j ' ) y ≠ f ' ( s , S i ' )
s表示当前起始点或者确定的景点的出入口; S i ' , S j ' 表 示景点Si,Sj的出入口位置集合; S jy 表示景点 S j 第y个出入口的位置。
依据式(3)、(4)、(5),可从定义(2)的多重边复杂图中,化简得到直接关联的顶点和边。
(6)景区路径 R = ( V ' , P , C ) ,其中V ′、P、C分别为：
R = V ' , P , C V ' = S kx | k = 1,2 , … , m , x = 1,2 , … , n P = s , S kx , T k , S ky , … , S jo , S jp , t C = ∑ k = 1 n T k + ∑ k , j = 1 n f S k , S j (6)
式(6)中,P表示游览过程经过的顶点及游时;s,t分别表示游览的起止点;Skx,Tk,Sky表示从Sk景点的x入口进入游览,从第y个出口离开景点;Sjo,Sjp表示从Sj景点的x、p入口经过而没有游览;C为路径的总消费(游时+路径距离)。

4 最优路径规划算法

在景区双加权图模型基础上,设计了景区图化简,以及路径规划求解算法。约定景点的多出入口编号按北半球指北方向,从第一象限开始以顺时针为序编号。

4.1 景区图构建算法

由于景区的复杂性,实际的景区图往往并不是完全图。因此,本文最优路径求解过程先需对式(2)的景区双加权图进行化简,结合不同的游览出入口选择,构造景区求解图(图2)。具体构建过程如下：
Fig. 2 Building procedure of scenic graph

图2 景区图G构建过程

(1)确定景区的景点及其出入口位置,依据式(1)、(2)构造顶点集合V。
(2)依据V及式(3)构造边集合E。
(3)依据式(1),删除不直接关联的边(边权值为 ∞ );构造景区图模型G。
(4)添加游览的起、止位置s,t。
(5)依据式(3),求解s,t最近的景点出入口,添加边(s,Si),(t,Sj)。

4.2 最优路径规划算法

在构造景区求解图的基础上,依据Dijkstra最短路径算法[16]和Prim最小生成树算法[17],设计景区双加权图模型的最优路径求解算法,其步骤如下：
(1)初始化,依据式(2)、(6),设 V ' ={}, P = { s } 为路径, V 为景点集合,Sy为当前游玩景点。
(2)求s关联的景点集合为Vt,遍历取景点 S i ∈ V t , 且 S i ∉ V ' ， 依据式(4),求解 f ' s , S i ' 得到到达景点Si的入口Sij;添加Si到 V ' ,添加Sij到P;若Ti不属于P,则添加到P,执行步骤(3);否则s=Sij,执行步骤(2)。
(3)遍历取景点Sm ∈ V 且 S m ∉ V ' ， 依据式(5),求解Sm的离开出口 f ' S i ' , S m ' , 得到离开景点Si的出口Sik,令s=Sik;添加Sik到 V ' 。
(4)重复执行步骤(2)、(3),直到P包含所有景点。
(5)求当前s到t的最短路径,将经过的景点出入口位置加入到P。

5 模型的路径规划实验与分析

5.1 实验区地理背景

实验区域选择常熟市尚湖公园内湖部分,其影像图如图3所示,共包含7个景点(图3中圈示)。景点基本情况与出入口的编号如图3及表2所示,共包括3处AOI景点,1处LOI景点,3处POI景点。
Fig. 3 Remote sensing image of experiment area

图3 实验区影像图

Tab. 2 Information of experiment area structure

表2 实验区地理背景

景点名称 景点编号 出入口编号 景点类型
牡丹园 A A1,A2,A3 AOI
留香馆 B B1,B2,B3 AOI
水上森林 C C1 POI
博雅堂 D D1,D2 LOI
串月桥 E E1,E2,E3 AOI
四景园 F F1(=E1) POI
唐寅系舟处 G G1(=A1) POI

5.2 实验区路径规划

5.2.1 传统景区图模型与双加权图模型比较
依据式(1)、(2)及景区图构建算法,建立景区双加权图(图4(a))。为了方便比较,选择A3,B1,C1,D2,E3,F1,G1点作为传统景区模型的映射顶点,直接关联的2个顶点连线作为边,采用本文提出的景区图构建算法(传统景区图模型只考虑一个出入口情况,可视为本文模型的特例),建立传统景区图模型(图4(b))。
Fig. 4 Graph model of experiment area

图4 景区图模型

图4建立的传统景区图模型和双加权图模型都是简单图,表达景点间实际的关联关系。传统景区图模型顶点是固定的,景点间路网距离(m)作为边的权重。双加权图模型随着进入和离开的出入口不同,顶点及顶点间距离是动态可变的。在图4(a)中,F1作为悬挂点表示在景区双加权图模型中,景点F处在景区E的多出入口作为顶点构成的路径上。
5.2.2 最优路径规划比较
为了突出双加权图模型在路径规划方面的优越性,将最优路径分为游览路径和返回路径2部分。其中,游览路径是游客在景点间的串行路径,返回路径则是在游览路径已串联游览了所有的景点后,需引导游客到达景区出入口的最优路径,并进而从路径规划的游览次序、规划距离等角度进行综合比较。
基于图4(a)、4(b)的景区图模型,分别采用本文设计的最优路径规划求解算法：(1)比较从景区入口s到景区出口t的最优规划路径结果,如图5所示;(2)比较从景区出口t到景区入口s的最优路径规划结果,如图6所示。
Fig. 5 Comparative analysis of optimal path from s to t

图5 从s到t最优路径比较

Fig. 6 Comparative analysis of optimal path from t to s

图6 从t到s最优路径比较

在图5、6中,符号“A3>A1,A3,A2”表示：(1)最优规划路径推荐从A3出入口进入景点A并游览,并推荐从A1出入口离开景点A;(2)后续游览过程中,经过了A3和A2出入口,但没有游览景点A。依据式(6),将传统景区图模型和本文模型得到最优路径规划结果综合比较,如表3所示。
Tab. 3 Results of path planning of experiment area

表3 最优游览路径规划结果

线路方向 使用模型 路径安排 规划距离 结果分析
入口到出口 传统模型 s,A3,TA,B1,TB,C1,TC,D2,TD,E3,TE,F1,
TF,G1,TG,t		 总长1918 m,其中,游览路径1492 m,返回路径426 m 景点游览次序发生变化,且本文模型使得规划距离缩短406 m
本文模型 s,A3,TA,A1,G1,TG,E2,TE,E1,TF,E2,D2,
TD,D1,B3,TB,B2,C1,TC,A3,G1,t		 总长1512 m,其中,游览路径586 m,返回路径926 m
出口到入口 传统模型 t,G1,TG,F1,TF,E3,TE,D2,TD,C1,TC,B1,
TB,A3,TA,A3,s		 总长1918 m,其中,游览路径1767 m,返回路径151 m 景点游览次序发生变化,且本文模型规划使得距离缩短858 m
本文模型 t,A2,TA,A1,G1,TG,E2,TE,F1,TF,E3,
D2,TD,D1,B3,TB,B2,C1,TC,A3,s		 总长1060 m,其中,游览路径659 m,返回路径401 m

5.3 实验结果分析

(1)从图5、6可看出,景区双加权图模型相比传统景区图模型,最优游览路径规划的景点次序有了较明显的改变。
(2)如表3所示,景区双加权图模型在路径规划过程中有效地减少了规划距离及游览距离,这进一步表明了本文模型在游览路径规划过程中实现了紧凑的安排,使得游览过程更加有效率。同时,这也使得本模型可用于景区游客的集散规划,即通过分析游览路径和规划路径的结合点,来合理安排景区内部的游客集散点,更好地服务游客行程。
(3)传统景区图模型可认为是本文景区双加权图模型景点只有一个出入口情况的特例。由于景点的出入口个数有限,最优路径的求解算法实际时间复杂度保持在O(n3)。因此,本文成果可有效应用于旅游线路的调整、游览引导等工作。

6 结语

本文针对景区游览线路规划在智能导游应用中的具体问题,分析了景点本身结构特征对其规划路径的影响;提出了顶点和边的权重均可动态选择的景区双加权图模型,并给出了景区图构建,以及景区最优游览路径的求解算法。通过实验分析表明,景区双加权图模型的求解最优规划路径可有效地降低行程规划的线路距离,更加贴近旅游过程实际,具有较好的个性化线路规划服务能力。
在双加权图模型中,本文仅是把顶点间的路网距离作为权值加以应用。在下一步研究中可结合游客对景点的个性化偏好及景点的自身特色(如景点的分类、知名度、吸引力等),并考虑景点的实时客流、动态交通状况等动态信息,融合社交网络、社会计算模式[18-19]等多源数据建立综合权重计算模型。本文成果作为动态旅游行程规划服务的重要支撑[20],将更好地应用于景区的精细化服务建设。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Hu J G, Dong F, Qi H N.Study on the path planning of tourist scenic area based on BVC Ant Colony Algorithm[C]. International Symposium on Computational Intelligence and Design, 2010:18-22.

[2]
Xu F,Du J P.Main algorithms study and implementation of tourist spot navigation system[C]. Computational Intelligence and Software Engineering, 2009:1-5.

[3]
方冬云. 图论在旅游线路选择中的应用[J].长春工业大学学报(自然科学版),2009,30(5):582-596.

[4]
史小艺. 旅游线路的优化设计[J].重庆文理学院学报(自然科学版),2012,31(1):9-14.

[5]
邹时林,阮见,刘波,等.最短路径算法在旅游线路规划中的应用——以庐山为例[J].测绘科学,2008,33(5):190-192.

[6]
王肃,杜军平,高田.多媒体旅游智能导航系统的研究与实现[J].中南大学学报(自然科学版),2009,40(增刊):335-340.

[7]
Gavalas D,Kenteris M, Konstantopoulos C, et al. Personalized routes for mobile tourism[C].Wireless and Mobile Computing, Networking and Communications(WiMob) IEEE 7th International Conference, 2011:295-300.

[8]
陆青,梁昌勇,黄永青,等.面向旅游行程规划的交互式多智能体遗传算法[J].计算机应用研究,2008,25(11):3311-3313.

[9]
钟伟才,薛明志,刘静,等.基于AER模型的multi-agent遗传算法[J].模式识别与人工智能,2003,16(4):390-396.

[10]
RoyS B, Das G, Amer-Yahia S, et al. Interactive itinerary planning[C]. Data Engineering (ICDE), 2011,4:15-26.

[11]
李山,王慧,王铮. 中国国内观光旅游线路设计中的游时研究[J]. 人文地理,2005(2):51-56.

[12]
张燕君,徐克林.基于模糊APACA的多目标团队个性旅游线路设计[J].计算机工程与应用,2012,48(35):207-212.

[13]
Rodríguez B, Molina J, Pérez F, et al.Interactive design of personalized tourism routes[J].Tourism Management,2011,33(4):926-940.

[14]
Antoine Z, 苗学玲. 妻子参与旅游决策的研究[J]. 人文地理,2003(2):98-101.

[15]
孙平安,谭秋月,郭进辉.基于顶点加权有向图与边加权图的景区动态客流统计与预测[J].苏州科技学院学报(自然科学版),2012,29(3):61-66.

[16]
王玉琨,吴锋.嵌入式GIS 最短路径分析中Dijkstra算法的改进[J].计算机工程与应用,2008,44(28):128-129.

[17]
杜文霞. 基于Prim 算法构建商丘市旅游景区最短游线[J].三门峡职业技术学院学报,2008,7(4):41-44.

[18]
Ahmedi L, Rrmoku K, Sylejmani K.Tourist tour planning supported by social network analysis[C]. 2012 International conference on social informatics, 2012:295-303.

[19]
Tran V X, Tsuji H.Using semantic technologies for dynamic and flexible trip planning[C]. 3rd IEEE International Conference on Digital Ecosystems and Technologies,2009:481-486.

[20]
Angskun T, Angskun J.A travel planning optimization under energy and time constraints[C]. International Conference on Information and Multimedia Technology, 2009:131-134.

[21]
滕聪,曹文.旅游景点筛选组合及旅游线路的优化算法与应用[J].地球信息科学学报,2010,12(5):668-673.

Options
文章导航

/

〈 〉