基于景点距离动态模型的大景区行程规划研究

李红梅

(河南检察职业学院 ， 河南 郑州 451191)

基于景点距离动态模型的大景区行程规划研究

李红梅

(河南检察职业学院 ， 河南 郑州 451191)

针对大景区旅游行程规划问题， 将其规约为非对称TSP问题， 并根据景点游客数量动态变化这一特点， 提出一种景点距离动态模型， 然后通过单个体交叉遗传算法对该模型进行求解和实验验证。 研究结果显示景点距离动态模型能较好地解决大景区的行程规划问题和景点游客负载均衡问题。 关键词: 旅游大景区； 非对称TSP问题； 遗传算法

随着社会的发展， 人们对旅游的内在需求不断提升， 旅游已进入“大景区时代”， 各地也纷纷采取措施适应这一变化， 譬如甘肃省计划建设“丝绸之路经济带”甘肃段大景区， 陕西省韩城市计划投资60亿元打造司马迁文化大景区等。 针对大景区时代的到来， 游客合理规划游览行程就显得尤为重要。 景区行程规划问题可以规约为一个非对称TSP(行程动态规划)问题， 非对称TSP问题已经被证明是一个计算复杂性很高的问题。 因此， 研究旅游景区不规则行程规划问题具有重要的现实意义和理论意义。

大景区通常由多个分布在广大区域的景点构成， 其行程规划与传统的TSP问题有较大的差异。 主要体现在：景点的分布是三维的， 从而造成行程不对称； 游客不一定遍历全部景点， 有可能仅仅遍历部分景点； 起点和终点有可能不同。 本文依据景区行程规划的基本要素， 通过分析传统TSP模型， 构建基于景点人数的距离模型， 依据该模型可动态获取游客游览各景点的行程， 提高游客旅游体验。

一、 大景区行程规划模型

(一)问题描述

游客从大景区中某景点出发， 行程涵盖全部感兴趣的景点， 要求行进距离和耗时最少， 并且游览的景点和行走行程不重复。 行程存在下列4种可能。

(1) 对景区部分景点感兴趣， 行程仅包括部分景点， 起点与终点不同。

(2) 对景区部分景点感兴趣， 行程仅包括部分景点， 起点与终点相同。

(3) 对景区全部景点感兴趣， 行程包括全部景点， 起点与终点不同。

(4) 对景区全部景点感兴趣， 行程包括全部景点， 起点与终点相同。

(二)景点距离动态模型

景区中各景点间距离并非直线距离， 无法用欧式距离描述景区间距离。 另外各景点在景区中呈三维分布， 导致景点i到景点j之间的距离dij不等于景点j到景点i之间的距离dji。 景点i到景点j之间的耗时不仅仅与距离dij相关， 还与景点i与景点j的游客数量相关， 因此， 本文描述的距离是以物理距离为基础的动态距离， 景点i到景点j之间的距离用dij(t)表示

dij(t)=Nj(t)×dij

(1)

其中

(2)

其中αj(t)为t时刻景点j内的游客数量；δj为景点j游客的最佳承载数量， 一般为常数。

从公式可以看出：景点i到景点j间的距离是一个动态变化的数值， 当景点j在t时刻游客在景点j的数量αj(t)大于其最佳承载量的系数比时， 从景点i至景点j的距离增大， 反之则距离减小。

二、 算法设计

(一)基本遗传算法流程

标准的遗传算法包括群体的初始化、 染色体选择、 染色体交叉、 染色体变异等操作。 其算法步骤可描述如下。

(1)随机产生一组染色体构成的初始种群， 根据适应度函数评价每个染色体的适应度。

(2)判断算法的收敛准则是否满足。 若满足输出搜索结果， 否则执行以下步骤。

(3)根据适应值以一定方式执行选择操作。

(4)按交叉概率Pc执行交叉操作。

(5)按变异概率Pm执行变异操作。

(6)返回步骤(2)。

基本遗传算法优化流程图见图1。

图1 基本遗传算法优化流程

(二)单个体交叉遗传算法设计

单个体遗传算法的基本思想是改变传统交叉算子使用双染色体进行交叉的方法， 交叉操作和变异操作均在单个染色体上进行。 这种算法简化了遗传操作， 计算效率有较大提高， 且对初始种群多样性的依赖性降低。

1.编码

遗传算法的编码方式有二进制编码、 格雷码编码、 浮点数编码和序号编码(自然数编码)等多种编码形式。 二进制编码等遗传算法的研究理论较为成熟， 实际应用也相当广泛。 在用遗传算法求解组合优化问题时， 使用序号编码比非序号编码更容易描述解空间和编码空间的一一映射关系。 但传统序号编码遗传算法是模仿非序号编码遗传算法的， 主要遗传算子仍为交叉算子， 而序号编码遗传算法的染色体不能在任意位置进行交叉， 随意交叉后的染色体很可能发生序号的缺失或重负， 这样的染色体无法映射至解空间， 需要对这些染色体进行伪解校正， 从而增加了计算复杂性。

针对本文的大景区行程规划问题， 采用序号编码方式， 即染色体(1， 2， …,n)代表行程为1->2->…->n。 用单个染色体实现交叉和变异操作， 避免了校正伪解的过程， 从而降低了算法计算复杂性。

2.目标函数和适应度函数

遗传算法的一个特点是它仅根据问题的目标函数值就可以得到下一步的有关搜索信息， 而对目标函数值的使用是通过评价个体适应值来实现的。

最优化问题主要分为两大类： 一类求解目标函数的全局最大值， 另一类求解目标函数的全局最小值。 本文涉及的计划优化是一个将保障时间最小化为目标的目标函数全局最小化的最优化问题。 对于目标函数全局最小化问题由解空间中某一点的目标函数值f(x)到搜索空间中对应的个体适应函数值F(x)的转换可用下面的方法：

(3)

式(3)中Cmax为一个相对较大的数。

3.交叉算子

交叉算子是遗传算法中关键的遗传操作， 它是模拟自然界有性繁殖、 基因重组过程， 对父代两个个体进行基因操作， 把原有个体优良基因遗传到下一代种群中， 并生成包含崭新基因结构的新个体。 交叉算子可看作为父代空间到子代空间的随机映射。

部分影射杂交(PMX)方法可以看作两点杂交的变形， 它通过一种特殊的修补过程来处理可能的非法现象。PMX的主要步骤如下。

第1步：在染色体上任意选择两个分割点。 由两个分割点定义的字串称作影射片断。

第2步：在两个父代间交换字串从而产生原型后代。

第3步：确定两个影射片断间的影射关系。

第4步：采用影射关系使后代合法化。

部分映射交叉由于存在对新个体的修正来保证新个体合法化的步骤而增大了遗传算法的复杂程度， 本文采用单个体交叉方法， 具体实现步骤如下：

第1步：按照交叉概率确定一个待进行交叉操作的个体。

第2步：选择两个不相同位置。

第3步：将两个位置之间的基因反转， 实现新个体的诞生。

图2

图2-1为两个被选中进行部分映射交叉的个体。 图2-2为根据交叉的部位两个个体交叉后产生的新个体。 第一个个体表述的是景点3和景点5在同一行程上遍历了两次， 第二个个体表述的是景点11和景点8在同一行程上遍历了两次， 显然， 这两个个体对应的解都是“伪解”。 因此， 需要对这两个伪解进行合法化， 图2-3表述的是合法化后的两个新个体。 图2-4中上面的个体为旧个体， 下面的个体为经过单个体交叉操作后产生的新个体， 这种交叉算子不存在对不合法解进行合法化的处理， 因此大大降低了计算的复杂性。

4.变异算子

变异操作通过随机改变种群中个别个体的某些基因而产生新个体， 变异操作增加种群中的个体多样性， 在一定程度上避免早熟收敛(非全局最优)。

本文中变异操作采用互换操作算子(swap)， 即按照变异概率随机选择染色体中两个不同基因编码的位置并进行基因交换，swap相对于INV(逆序操作)和INS(插入操作)更有助于算法的大范围搜索， 增强算法的广度搜索能力。

对于一个行程的染色体的变异操作， 根据变异概率确定是否进行变异操作， 随机选择行程上的两个景点进行交换。 例如：变异交换位置为2和8， 变异算子见图3。

图3 变异算子

5.精英保留策略

当前种群中适应度最高的个体不参与交叉运算和变异运算， 用它来替换掉本代群体中经过交叉、 变异等遗传操作后所产生的适应度最低的个体。 采用精英保留策略可在概率上保证遗传算法能够在解空间得到最优解。

6.选择算子

遗传算法最基本的选择方式是根据个体适应值的比例进行选择， 即轮盘赌选择。 这种选择方式严格按照群体中个体适应值的比例进行选择， 适应值高的个体被选择来繁殖后代的机会大， 适应值低的个体被选择来繁殖后代的机会小。 选择操作按照以下步骤进行。

(1)计算种群中全部个体适应值之和。

(4)

式中f(xi)是个体xi的适应度，i=1， 2， …，N。

(2)计算种群中每个个体的选择概率。

(5)

(3)计算群体中全部个体选择概率的累积和。

(6)

(4)产生一个随机数r∈[0,1]， 若r∈[q(xi-1),q(xi)]， 则选择个体xi，i∈{1,2,…N}，q0=0。

三、 景区行程规划与算法应用

(一)景区行程规划

某景区中的10个景点分布抽象为图4的二维分布， 各景点最佳游客数量均为500人。 在景区各个景点出入口处分别设置游客计数器， 实时统计景点游客数量， 每小时向景区数据中心发送该时段的游客数量， 数据中心根据本文提出的景点距离动态模型计算各景点间的距离， 并通过本文提出的单个体交叉算子遗传算法对路径进行优化， 每小时通过景区公共信息网络对游客发布一次最佳路径， 技术原理如图5。

(二)算法应用

在初始状态下， 各景点的游客数量均为0， 此时景点i与景点j之间的距离dij(0)=dij。 遗传算法的控制参数为：种群规模(PopSize)100， 交叉概率Pc=0.6， 变异概率Pm=0.1， 迭代次数(Generation)50。VS2010环境下用C#进行编程， 得到的最佳行程见图6。t=0时刻， 最佳行程为1->10->9->8->7->2->6->5->4->3。

图4 景点分布

为方便计算， 假定各景点的最佳游客数量均为500。t=T时刻αj(t)为200—800内的随机数， 该时刻各个景点的人数分布见表1。

图5 技术原理图

图6t=0时刻最佳行程

表1 t=T时刻各景区游客数量(人)

从表1可以看出在t=T时刻， 景点2、 景点3、 景点4和景点6的游客数量均小于最佳游客承载数量， 因此， 根据公式可以得到其他景点到这些景点的距离均小于物理距离， 而到其他景点的距离由于超出了经典最佳游客承载数量而大于其物理距离。 根据公式重新计算得到景点之间距离， 得到的最佳行程见图7。

从图7可以看出，t=T时刻， 最佳行程为1->3->4->2->5->6->7->8->9->10。t=T时刻由于景点3的游客数量小于最佳游客承载数量， 导致景点1至景点3的距离等于物理距离， 而景点1至景点10的距离由于景点10超出了最佳承载数量而大于其物理距离， 因此， 尽管景点1至景点10的物理距离小于景点1至景点3的物理距离， 寻优行程还是选择了景点3作为景点1的后续景点。 由以上分析可知， 本文提出的基于游客数量景点间距离模型具有动态的旅游路线规划的能力， 在路线规划中避开了人数较多的景点， 可实现旅游景区的游客数量的负载均衡。

图7t=T时刻最佳行程

针对大景区内景点行程规划问题， 本文提出一种景点距离动态模型， 该模型将景点游客数量和景点间物理距离进行关联， 根据景点游客最佳承载数量与实际游客的数量对物理距离进行动态变化， 根据不同时刻景区内游客分布， 利用遗传算法与TSP问题的有机结合求出不同时刻的景区行程规划。 实验证明， 该模型可根据景点游客数量合理规划景区行程， 可为游客和景区提供较为合理的旅游方案。

[1] 胡军国，祁享年，董峰，等.一种改进蚁群算法研究和旅游景区路径规划问题求解[J].计算机应用研究，2011(5):1647-1650.

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

[3] 徐锋，杜军平.改进蚁群算法在旅游线路中的应用研究[J].计算机工程与应用，2009,45(23):193-195,226.

[4] 潘玉侠，梁勤欧.基于遗传算法的旅游线路优化[J].浙江师范大学学报，2011(8)：350-354．

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

[6] 王兆峰．基于遗传算法的理想区间法在旅游环境质量评价中的应用[J]．系统工程，2013(2)：106-114.

[7] 宋国峰，梁昌勇，梁焱，等．改进遗传算法优化BP神经网络的旅游景区日客流量预测[J]．小型微型计算机系统，2014(9)：2136-2141.

[8] 周辰红，李中．基于多目标进化算法和遗传算法的最佳旅游套餐设计：以上海市为例[J]．信息科技，2014(10)：245-248.

[责任编辑 李继峰]

A Study of Large Tourist Attraction Path Planning Based on Scenic Spot Dynamic Distance Model

LI Hong-mei
(HenanProcuratorialVocationalCollege,Zhengzhou451191,China)

This paper discusses the problem of large tourist attraction path planning, which is re-defined with asymmetric TSP. A scenic spot dynamic distance model is proposed to approach the topic problem, which is solved and demonstrated with individual crossover genetic algorithm. As the results indicate, the problem of large tourist attraction and scenic spot tourist load coordination can be effectively solved with scenic spot dynamic distance model.

large tourism attraction; asymmetric TSP; genetic algorithm

2016-12-02

李红梅(1983—)， 女， 河南偃师人， 助教。

F590

A

1009-4970(2017)04-0023-04