一种单向动机迭代改进旅游路线规划算法*

周 啸，袁云飞，杨 佳，杨明雷，崔财财

(1. 信息工程大学 指挥军官基础教育学院，河南 郑州 450001； 2. 陆军边海防学院，陕西 西安 710100)

旅游者到一个陌生城市旅游前往往需要以城市景点数量、属性、布局及其周边服务等信息为基础规划最佳旅游路线以尽可能获得最大动机利益满足. 目前旅游路线规划方法主要有两类，一是基于旅游者主观意识和对旅游城市的初步认知，以海量数据为依托抽取离散兴趣信息，对兴趣信息自我加工后决定最适合自身风格爱好的旅游路线； 二是市场上大批量旅行社设计规划多种既定旅游路线供旅游者选择[1-3]. 以旅游者主观意识与认知为背景规划旅游路线时，旅游者往往对陌生城市海量地理信息和旅游服务信息的认知不足，具有随主流、教科书式的行程规划趋向，表浅的规划策略和较强主观性对客观条件不充分等缺陷导致最终规划的旅游路线难以达到最大动机利益； 旅行社提供既定路线以盈利为目的，考虑旅游者个体兴趣爱好较少，旅游者跟随旅行社出游后真正充分获得动机利益满足的不多[4-6]. 目前，自驾游、自助游等个性化旅游出行方式占据旅游市场很大份额，是未来旅游市场的热点和发展趋势. 个性化出游要求旅游路线以追求旅游者动机利益为目的，使旅游者获得最佳旅行体验，特别是城市旅游中，不同景点对旅游者的吸引力不同，最大限度地遵循个性需求，规划适合单一个体或群体的兴趣旅游路线是智慧旅游中智能规划旅游路线的重要研究内容. 从路线规划算法上看，Dijkstra算法、Floyd算法、人工蚁群算法和A*算法等以距离最短为目标，采用不同模式规划最佳路线，并未融入旅游者对旅游路线的个性需求和对旅游路线动机利益的最大化追求，仅从算法本身研究路径规划不能充分考虑旅游者主观意志. 因此，将旅游者出行规划和旅游过程中关心的因素量化为路径规划算法参数指标，构建符合旅游者主观个性需求的路径规划算法，是实现旅游动机利益最大化的有效方法[7-9]. 本文在景点路径规划算法的基础上构建了一种单向动机迭代的改进算法，以输出动机迭代作用值为规划最佳旅游路线的重要依据，通过仿真算例分析给出可行旅游路线规划方案.

1 景点特征编码集建模

旅游城市的市内典型景点数量和分类一定，首先构建景点特征编码集模型，在此基础上构建子集. 景点特征编码集是旅游者智能随机选取个性化需求景点的数据集，通过调用随机函数选取景点特征编码子集和景点特征编码元素对应兴趣景点，可实现智能选取或人工选取以充分满足旅游者动机[10-12].

Def.1 景点特征编码集. 由旅游城市包含的全部典型景点及其特征编码构成的父集为景点特征编码集. 存储不同种类特征景点，其子集为景点特征编码子集.

Def.2 景点特征编码子集. 由旅游城市包含的一类典型景点及其特征编码构成的子集为景点特征编码子集. 存储同类特征景点，其包含的元素为景点特征编码元素.

Def.3 景点特征编码元素. 景点特征子集包含的一个特征景点对应的编码为景点特征编码元素.

令旅游城市景点为u类，景点特征编码集为U，则U={Ut|t∈(0,u)⊂Z+}，Ut为景点特征编码子集. 景点特征编码子集包含et个景点特征编码元素，则t∈(0,u]⊂Z+. 令∀Ut元素为UtVr且r∈(0,et]⊂Z+. 取1维景点特征编码基向量a=(UtV1,UtV2,…,UtVet)，由u维景点特征编码基向量构成景点特征编码矩阵A=[UtVr]，包含u行maxet列u×maxet个特征景点编码，第t行由景点特征基向量和maxet-et个0元素构成，如式(1)所示. 景点特征编码矩阵是提取特征景点元素对应景点的源矩阵.

(1)

设连续型随机变量X的分布函数为

(2)

则称随机变量X服从[a,b]区间上的均匀分布，记为X～F(a,b). 一次调用闭合区间上均匀分布函数可生成不超过区间内单调最大值的指定有限元素个数，且元素具有较强随机性[13-15]. 根据模型，旅游者获取路线的方式有三种，一是在提供兴趣需求和景点数量后智能输出路线，二是定向选取若干景点特征编码子集对应的景点种类，根据所需子类景点数量随机选取景点后输出路线，三是定向选取所需个数景点特征编码元素对应景点后输出路线. 前两种方法适用于对陌生旅游城市认知不足的旅游者[16-18].

(3)

2 单向动机迭代改进规划算法

Def.4 景点动机区间H. 1号景点与Pk号景点间的摆渡总行程为景点动机区间H. 景点动机区间是输出动机迭代值的介质.

Def.5 景点动机子区间ΔH. ∀Pi号景点与相邻Pi-1号或Pi+1景点间的摆渡行程为景点动机子区间ΔHi，i∈(0,k)⊂Z+.

Def.6 景点动机区间迭代值W. 游览所有选取景点后由1号景点至Pk号景点迭代输出的动机值.

Def.7 景点动机子区间迭代值ΔW(Pi,Pi+1). ∀Pi号景点摆渡至下一景点Pi+1迭代输出的动机值，是构成景点动机区间迭代值的子单元. 景点动机子区间是输出局部最优动机迭代值的介质，景点动机作用值一定时，摆渡区间产生的动机迭代是景点动机区间输出动机迭代值的数据源. 依据贪心算法思想，景点动机子区间迭代值各自独立，区间迭代值即是各子区间迭代值的叠加，满足式(4).

(4)

城市景点间摆渡产生的动机迭代值受区间距离z1(km)、公交地跌线路数z2、出租车费用z3、道路节点(红绿灯)z4、拥堵指数z5等因子影响. 表 1 定义各因子对旅游者动机利益的影响指标，其中λ1为区间距离，λ2为公交地铁线路数，λ3为出租车费用，λ4为道路节点(红绿灯)数，λ5为拥堵指数，参数g(j)为算法输出的不同路径编码.

表 1 各因子对旅游者动机利益的影响指标Tab.1 The influence indexes of various factors on tourists’ motive benefits

考虑旅游者心理要求，摆渡区间耗时越少、周折越少、摆渡越便捷，越能促使旅游者产生较大动机利益满足和对旅游城市好感. 不同路线下不同景点间的动机子区间迭代值ΔW(Pi,Pi+1)不同. 根据旅游城市地理信息基础数据构建改进景点子区间算法，如图 1 所示.

图 1 景点子区间改进算法Fig.1 Improved algorithm for sub-interval of scenic spots

改进算法如下：

Step 1：确定相邻两景点间通路包含的关键道路节点Qj，j∈(0,maxj]⊂Z+；

Step 2：令同一地点之间的距离为0，不可直接到达的两点之间距离为∞. 以景点Pi为顶点，初始化路径集合S0=Dist{Pi,Pi}=0； 待选节点路径集合为:S1=Dist{Pi,Q1}=d1，S2=Dist{Pi,Q2}=d2，S3=Dist{Pi,Q3}=Dist{Pi,Q4}=Dist{Pi,Pi+1}=∞. 比较S1和S2并冒泡输出最小值S1*=min(S1,S2)，清空S1,S2,…存储值；

Step 3：同Step 2，以该段S1*所在边末端节点为起点继续搜索，输出待选节点路径集合S1,S2,S3,…. 比较S1*,S1,S2,S3,…，并替换原始S1*输出最小值S1*=S1*+min(S1,S2,S3,…)；

Step 4：同Step 3，冒泡输出从景点Pi到景点Pi+1最短路径g(j)对应的Sg(j)*，同时记录其他δ-1条次优路径g(1),g(2),…,g(j-1),g(j+1),…,g(δ)对应的S*；

Step 5：给定初始值，对每条路径迭代影响指标因子，输出景点动机子区间迭代值ΔWij(Pi,Pi+1)，表示为

(5)

冒泡输出迭代值最高的路径为最优路径，每个景点动机子区间ΔHi均包含唯一对应编号j的最优路径，定义为ΔWij′opt(Pi,Pi+1)；

(6)

传统算法仅考虑路径最短，而最短路径的景点动机区间迭代值W可能并非最优. 改进算法在考虑路径最短基础上融合迭代影响旅游者动机利益产生的各类影响因子，综合输出最优路径.

3 仿真算例

仿真算例以郑州市内景点和基础地理信息数据为例. 根据属性特征将其分为u=4类.U1为公园(绿地)编码子集，U2为游(娱)乐场编码子集，U3为场馆编码子集，U4为购物消费编码子集. 选取市内最具代表性和热门的大众基础旅游服务景点，取t∈(0,4]⊂Z+且maxt=4. 根据选取景点，e1=8，e2=4，e1=7，e1=6. 表 2 给出景点特征编码子集元素景点编码.

表 2 景点特征编码子集元素景点编码Tab.2 Subset element scenic spots code of scenic spots feature code

构建1维景点特征编码基向量a1=(U1V1,U1V2,…,U1V8)，a2=(U1V1,U1V2,U1V3,U1V4)，a3=(U3V1,U3V2,…,U3V7)，a4=(U4V1,U4V2,…,U4V6)，则有景点特征编码矩阵A=[UtVr]

(7)

Ⅰ： ①P1→②P2→③P3；

Ⅱ： ①P1→③P2→②P3；

Ⅲ： ②P1→①P2→③P3；

Ⅳ： ②P1→③P2→①P3；

Ⅴ： ③P1→①P2→②P3；

Ⅵ： ③P1→②P2→①P3.

以第一条游览顺序①P1→②P2→③P3为例. 路线包含1个景点动机区间H： ①P1→②P2→③P3，2个景点动机子区间ΔH1： ①P1→②P2和ΔH2： ②P2→③P3以及对应的景点动机区间迭代值W和景点动机子区间迭代值ΔW(Pi,Pi+1). 确定景点P1和P2间关键道路节点数和可行摆渡通路，如图 2 所示.

根据本文改进算法确定前5条最优通路为：(1)P1Q1Q2Q3Q4P2； (2)P1Q1Q2Q3Q4Q5P2； (3)P1Q1Q6Q7P2； (4)P1Q1Q6Q7Q8P2； (5)P1Q1Q6Q7Q8Q9Q10P2及其各自对应区间的动机影响因子，如表 3 所示. 迭代结果为通路(3)是景点P1和P2间产生动机利益最大的路径，即ΔW13′opt(P1,P2)=0.316，且路径长短与动机迭代值不成正比. 改进算法后不仅考虑路径最短，同时考虑旅游者动机利益. 同理迭代输出景点P2和P3间最优路径，二者叠加为第一条游览顺序①P1→②P2→③P3的最佳动机迭代输出路径，获得景点动机区间H(P1,P3)景点动机区间迭代值W1. 同理输出其他5条游览顺序的景点动机区间迭代值Wμ并获得最大值maxWμ，表 4 为改进算法下各游览顺序输出的景点动机区间迭代值.

图 2 景点P1和P2间关键道路节点及通路Fig.2 Key road nodes and paths of sight spot P1 and P2

表 3 改进算法下景点P1,P2间不同通路动机影响因子Tab.3 Different path motive impact factors between P1 and P2 of improved algorithm

表 4 改进算法下各游览顺序景点动机区间迭代值Tab.4 Scenic spots’ motive interval iterative value of improved algorithm under each traveling sequence

分析仿真算例结果，改进算法下游览路线Ⅰ输出最大动机迭代值，其次是路线Ⅵ，即当前选中景点条件下旅游者首先游览郑州动物园，再游览二七纪念馆，最后游览西元广场，可以获得最大动机利益满足. 其次是按照先游览西元广场，再游览二七纪念馆，最后游览郑州动物园，也可获得次优动机利益满足. 从一天游览时间安排上看，该两种游览路线也较为合理，且为沿景点分布的顺路方向，方便旅游者行程. 当景点数量增多时，亦可获得相同结论. 仿真算例证明，本文构建算法充分考虑市内景点旅游动机影响因子，为旅游者选择景点及其游览路线提供了优化方案，促进旅游者获得最大动机利益满足，同时也在提高旅游者对旅游城市的主观印象、提升旅游城市形象、促进旅游经济发展等方面起到积极作用.

4 结束语

本文在目前旅游者游览城市景点存在问题的基础上，根据旅游者游览习惯和动机目的提出了一种单向动机迭代改进旅游路线规划算法. 对城市景点进行特征编码集建模，提出融合旅游动机影响因子算法的改进最优路线规划算法，单向输出动机利益迭代值最优的旅游路线. 算例证明，本文所提算法能够输出满足旅游者需求并产生最大动机利益满足的旅游路线，具有一定可行性和实践意义.