基于格网模型的维特比旅游路径规划算法

殷浤益 何贞铭 张 颖 赵 暖

(长江大学 地球科学学院, 湖北 武汉 430100)

0 引言

随着网络技术的发展,当下人们出行旅游前多在各大旅游网站上搜集信息[1],但仅能获得景点、酒店的静态位置及属性信息,依此信息设计满足自身旅游需求的路径规划将耗费大量时间与精力。虽然少量旅游网站也提供类似路径规划功能,但选取该功能后多数出现旅行社旅游线路产品推荐而非区域内旅游路径规划。因此大众迫切需要一种考虑景点、酒店等多方面因素的旅游路径规划方法,以满足游客的个性化及实用需求。

近年来,许多学者对旅游路径规划算法进行了大量深入的研究[2-6]。樊守伟等[2]采用改进的Dijkstra算法实现了旅游路线规划。牛悦诚将旅游路径规划问题转化为旅行商问题,并使用改进的蚁群算法进行求解[3];卢昕[4]、徐峰等[5]对蚁群算法进行了改进;李孟则采用改进的A*算法求解旅行商问题[6]。

现有旅游路径规划研究成果相对较多,但仍存在不足之处:(1)限制因素比较固定,并未考虑多种实际因素的影响,如大多算法仅依据景区进行旅游线路规划,而实际旅游过程中并未考虑重要因素“酒店”的影响,致使路径规划结果适用性下降;(2)大多算法中的数据基源于历史数据,这些数据并未充分顾及游客的个性需求,并未根据游客喜好、消费水平的不同而生成个性化的旅游路线规划方案。

维特比算法是一种在数字通信中经常使用的译码算法,于1976年由维特比(Viterbi)提出,是最优的动态规划算法之一[7],本文将旅游路径规划问题抽象成多阶段决策最优化问题,即将旅游路径分解成若干个由景点和酒店交错组成的链状序列,其每个节点与前后都具有相关联系,用维特比算法求解每个阶段的最优解,最后得到整个最优路径,同时引入了格网模型与景点、酒店的属性信息来实现路径规划的个性化需求。

1 顾及多因素的旅游路径规划算法实现

1.1 相关概念介绍

为了方便介绍本文的研究内容,对本文算法中所涉及概念进行解释。

1.1.1景点、酒店

本文中进行旅游线路规划的两个重要因素:景点是游客能够游玩的一系列地点,酒店是能为游客提供住宿条件的地点,它们的属性包括:坐标,名称,用户评价等级,消费等级。

1.1.2经济型旅游

这是针对消费水平较低的游客选取的旅游方式,例如学生游客,此类群体在旅游时往往选择性价比高的景点和酒店,性价比高代表用户评价等级高且消费等级低。

1.1.3舒适型旅游

相对于经济型旅游的概念,当游客为拥有较高稳定收入的人群时,其需求为最佳的旅游体验,这就要求用户评价等级与消费等级均高的景点和酒店。

1.1.4观测状态概率

维特比算法进行动态规划的重要基础之一,代表景点和酒店对游客的吸引程度。若无任何其他因素的影响,每个景点和酒店的观测概率都是相同的,但是当用户选择舒适型旅游或者经济型旅游时就会发生变化,由景点、酒店的用户评价等级和消费等级决定。

1.1.5三类空间位置关系

在GIS中描述两点之间的空间位置关系仅用重叠和不重叠表达,不能较好地表达景点与景点或者景点与酒店之间空间位置关系,因此定义如下三类点与点之间的空间位置关系,用h表达两点间的距离,α,β为常量,单位均为km。①距离相近:当0≤h<α时,两点之间是距离相近关系;②距离适中:当α≤h<β时,两点距离适中;③远离:当h≥β时,两点距离较远。α,β的数值需要根据不同城市的具体情况进行确定。

1.1.6状态转移概率

维特比算法进行动态规划的另外一个重要基础,在本文中表示游客从一个景点到下一个景点或者酒店的概率,基于1.1.5节的空间位置关系定义,本文用距离作为自变量的高斯函数计算状态转移概率。

1.1.7旅游时间

为了让游客有充足的时间来旅游,本文中旅游时间计算以天为单位,且为游客提供个性化的旅游时间选择方式。在总结国内旅游网站的旅游线路推荐和实际调研基础上,认为单日旅游两个景点相对适中,因此单日旅游时间代表两个景点和一个酒店,两日及以上的旅游时间依此类推。

1.2 用格网模型表达点之间的空间位置关系

在旅游路径规划中,可以近似将景点和酒店作为点来处理,在九交模型中,重叠与不重叠2种点/点关系[7]不足以充分描述旅游景点或酒店间的位置关系,于是本文提出了1.1.5节中的三种空间关系,其实质是以距离为梯度对点进行聚类处理,而格网模型是实现聚类的一种基础且重要的方法。本文用起点与下一点之间的曼哈顿距离代替两点之间的实际距离,依据1.1.5节的定义对格网距离进行梯度划分,得到三类空间位置关系,此方法不仅能简化坐标计算,并且划分的结果充分契合高斯函数的特性。

曼哈顿距离是两点在南北方向上的距离加上东西方向上的距离[9]。相比于欧氏距离,曼哈顿距离更适用于城市街道中的距离表达,也具有更高的计算效率;相比于实际距离,在城市中选择不同的交通工具,其实际距离往往具有很大的区别,很难进行统一的量化处理。综合考虑,本文采用了曼哈顿距离来近似表达两点间的距离。

为使格网模型能够恰当地表达点之间距离相近、适中、远离的空间位置关系,单位格网需为边长为α的正方形,那么根据景点、酒店最大范围的经纬度坐标,需要用如下公式计算格网的行数NR与列数NC:

(1)

式中,μ代表1纬度的实际距离;θ、φ分别代表经度和纬度。

建立上述格网,选择任意点为起点,与起点在同一格网内的其他点就与起点的关系是相近的,因为它们之间的距离小于α;以起点为中心,计算离起点的曼哈顿距离在β内的点,则这些点到起点的关系是适中的;与起点的曼哈顿距离大于β的点与起点的关系是远离的,如图1所示,图中取β=2,则横线格网内的点与起点的距离相近,阴影格网内的点与起点的距离适中,白色格网内的点与起点是远离关系。

图1 用曼哈顿距离表示空间位置关系示意图

1.3 状态转移概率与观测状态概率的计算

从日常人们的出行经验来看,若无其他因素影响,人们在旅游时前往下一个目标的概率与当前位置到下一目标的距离近似成高斯分布,即距离越远,游客愿意到达这个目标的概率越小,因此本文采用高斯函数来表达曼哈顿距离与状态转移概率之间的关系,其数学表达式如下:

(2)

式中,μ、σ分别代表期望和均方差;x代表曼哈顿距离;P(x)为起点到下一个点的状态转移概率。当两个点在同一格网里时有x=0,此时两点间的距离小于α,对应两点距离相近的空间位置关系,表示游客到达另一个点的可能性最大,因此P(x)在x=0时应取最大值,所以有μ=0;由高斯函数在x>μ上单调递减的性质可知,∃β>α,σ=f(β)使得P(β)≈10-8,那么当x>β时,可以认为游客到达该点的概率几乎为0。为提高算法效率,本文只计算距离起点β内的点的状态转移概率。使用高斯函数来表达距离与状态转移概率之间的关系,既充分考虑了高斯函数的特性也符合实际。

文中介绍了景点和酒店观测状态概率由景点和酒店的消费等级和用户评价等级确定,这里用Lc和Lq(Lc、Lq∈[1,2,3,4,5])来分别表示消费等级和用户评价等级,0与1分别代表经济型和舒适型,T代表旅游类型,λ为常数,xi表示起点附近的第i个点,最后景点、酒店的观测状态概率为E(xi),其计算公式为:

E(xi)=Ec(xi)×Eq(xi)

(3)

(4)

1.4 维特比算法实现旅游路径规划

在上文中已经通过游客选择旅游类型确定每个景点和酒店的观测状态概率,通过格网模型和高斯函数确定了两个点之间状态转移概率。基于维特比算法实现旅游路径规划的方法是,分步求解每一个状态到下一个状态的最优路径,从而得到整个最优路径,每个状态的最优路径通过寻找观测概率和转移概率乘积的最大值来确定[10],循环计算每个状态,直到达到用户设定的旅游时间,如图2所示。

图2 维特比算法示意图

每个状态的最优解可以用以下公式计算:

(5)

s≥1,0≤i≤n-1

其具体的流程如图 3所示。首先,游客需要确定旅游的起始点,预计旅游的时间以及旅游类型。接着,以游客确定的景点为起点,计算剩余每个景点到起点的曼哈顿距离,剔除远离起点的景点和酒店以减少计算量,将与起点距离相近或适中的点的距离代入(2)式得到状态转移概率,然后使用(3)、(4)式得到范围内景区、酒店的观测状态概率。用(5)式得到每个状态的最优解,即为当前状态中最有可能到达的点[11],将该点放入一个结果集合中,再以该点作为新的起点,在进行距离计算时剔除结果集合中的点,防止计算结果回溯,然后一直循环下去,直到满足用户需要的旅游时间。最后,算法结束,将结果集合中的点显示在主界面上。

图3 维特比旅游路径规划算法流程图

2 实验研究

为了展示研究成果,本文利用ArcGIS Engine平台与ArcGIS Engine开发了基于维特比算法的旅游路径规划系统的桌面应用程序,实现了让用户选择旅游起点、旅游天数、旅游类型后,自动计算出最符合要求的旅游路径。

2.1 实验数据准备

本文以武汉市为例,选取了武汉市具有代表性的15个景点,例如:黄鹤楼、户部巷、武汉欢乐谷等;32个酒店,包括一般连锁酒店与高档酒店。底图和坐标数据均来自湖北省天地图。为了能确定1.1.5中α,β的值,统计了常见各类出行方式的平均速度,以武汉市市区为例,如表1所示。

表1 常见各类出行方式平均速度

表1统计的平均速度包含红绿灯、武汉市的路况信息,公共交通的停站等待时间等,可以看出在武汉市市中心的出行速度较为缓慢,结合武汉市市区的实际出行情况,本文取α=1,β=15,此时根据计算取σ=β/2时,P(β)≈10-8。

计算得到参数后需要对数据进行处理。首先,将数据导入ArcMap中,给每个景点和酒店赋属性值,其中用户评价等级和消费等级的数据来源于网络。本文中所有景点和酒店范围的经度最大值为114.42°,最小值为114.21°,纬度最大值为30.68°,最小值为30.50°,将以上所有数据都代入式(1)得到NR≈20.006,NC≈19.998。然后,打开ArcMap中的Fishnet功能,输入上述数据生成20×20的格网。最后,再将生成的格网分别与景区和酒店做叠加分析生成Intersect_Fishnet_Sceinc和Intersect_Fishnet_Hotel图层,此时已经可以在新图层的属性表获取到景点、酒店的格网坐标、等级、名称、用户评价等级和消费等级等所有信息。

2.2 实验结果

本文假设了四种不同的情景,如表2所示,每个情景的条件都互不相同,对应了不同游客的需求,同时也可以对比不同条件下旅游路径规划结果,从整体来看,旅游路径规划结果满足不同游客对旅游类型和旅游时间的需求。

表2 实验详情

在实验1中,游客选择以“武汉大学”作为起点,规划的路线如表3实验结果所示,“武汉大学”的下一个景点是“湖北省博物馆”,该景点门票免费,且藏品丰富,参观价值极高,是武汉市性价比较高的景点之一,距离“武汉大学”约4 km,距离适中。搜索的酒店是“汉庭酒店(东湖店)”,该店在“携程”等旅游网站中评分较高,该酒店地理位置优越,近地铁四号线,价格亲民,距离“湖北省博物馆”约1 km,因此规划的路线整体符合用户要求。

表3 实验结果展示

实验2、3、4均是实验1的对比实验。在实验2中仅改变旅游类型,检索的下一个景点就变为“楚河汉街”,该景点属于购物娱乐类型,周围是3个大型商圈,因此人均消费较高,距离“武汉大学”约5 km,在距离适中的范围内,检索的酒店是武汉市的五星级酒店,距离“楚河汉街”约为0.2 km,规划结果十分符合舒适型旅游的要求。在实验3中改变了旅游时间,发现实验1与实验3第1日的旅游路径相同,可以看出维特比算法从局部最优到整体最优的特性;实验3第2日以“东湖海洋世界”作为起点开始检索,距离该景点15 km内的景点有多个,但距离相对较近的只有“楚河汉街”与“武汉欢乐谷”,这两个景点对规划结果的影响较大,“武汉欢乐谷”到起点的距离虽然更近,但是由于消费等级的存在,最后计算结果是“楚河汉街”优于“武汉欢乐谷”,为该状态下的最优解,说明了本文算法中观测状态概率与状态转移概率相互影响。最后实验4中只改变了起始点,但是从计算结果来看,与实验1并无本质区别。

从以上的实验中可以得出,基于维特比算法的旅游路径规划充分运用了维特比算法的动态规划方法,既考虑了游客与景点、酒店之间的距离因素,也结合了游客自身的旅游需求。引用的高斯函数能较好地表达距离与状态转移概率之间的关系;旅游类型的设定让游客的选择多样化。

2.3 实验结果与其他旅游路径规划结果对比

文献[2]中使用改进的Dijkstra算法也实现了旅游路径规划,本文将维特比算法与其进行比较(表4)。在时间复杂度上两个算法相差不大。实用性上维特比算法得出的旅游路径更符合游客的要求,实用性较高。但不能否认Dijkstra算法适应性强和实现简单的优点。

表4 维特比算法与文献[2]中算法对比

3 结束语

本文对维特比算法和格网模型在旅游路径规划问题上进行了探索,创新性地提出了将酒店加入旅游路径规划之中,增加了旅游路径规划的实用性;用格网表达景点、酒店的空间位置关系;运用高斯函数表达观测状态概率;利用景点和酒店的属性来表达状态转移概率;最后,成功把维特比算法与上述方法结合在一起,实现了维特比旅游路径规划算法,并用实验进行了验证,结果表明该算法是合理的,并且在一定程度上满足了用户多因素的路径规划需求。但是,该算法也存在不足之处,比如本文以格网模型下的曼哈顿距离代替实际距离会不可避免地产生误差,在未来的研究中可以探索其他的聚类方法,尽可能减小误差,使规划结果更准确。

当今我国信息化产业发展迅猛,旅游业与GIS相结合使其信息化水平逐步提高[12],但仍然还有很大的发展空间。未来应用中,可建立全国最优旅游路径网站或旅游线路查询决策系统,旅游路径规划可以扩展到具体的道路规划。旅游路径的开发水平、完善程度,起到把控旅游流量、流向的作用,同时可以缓解旅游高峰期的拥堵情况,可有效地提高游客整体的旅游质量,对我国旅游业的发展具有重要意义。