当前旅游业正朝着定制化、个性化方向发展, 对旅游路径的规划也逐渐成为研究热点。多数学者针对单一景区内的游人行走线路或针对长距离、大跨度的跨省、出境游路径规划展开研究, 而忽略了受众更广, 更贴近日常出行真实状况的中远途 (不跨省) 、短时间内 (不超过1周) 的自驾出行情况, 本文正是针对该范围内的中小型区域旅游展开研究, 将上海及周边多个景区构成的旅游目的地网络作为研究对象, 将路线规划问题抽象成TSP问题并建立哈密顿回路的数学模型, 通过传统遗传算法实现对该区域旅游路径的规划, 帮助游客提升出行体验。
一、提出问题
假设一游客计划从上海出发, 自驾游览上海市及周边共30个景区并最终回到出发地, 根据出行需求, 游客要遍历每个景区且各个景区只能到访一次, 如何规划路线可以使游客在最短时间内完成游览目标。
根据问题, 提出以下假设:
(1) 每两个景区之间都有直接接通的公路, 不存在两个景点间必须通过其他景点才能到达的情况, 且连接各景区的公路均为直线。
(2) 游客在景区间的移动过程全程自驾, 且平均车速为40km/h。
(3) 不考虑游客中途停车、用餐、夜间休息或其他突发因素造成的时间增加, 且游客到达景区马上开始游览, 没有时间间隔。
(4) 游客在各个景区内的游览时间是固定的, 不因到达的时刻不同而变化。
二、建立模型
TSP问题即旅行商问题, 可描述为:已知n各城市坐标, 一个商人从起点城市出发, 经过且只经过每个城市一次, 最后回到起点城市的最短路程。TSP问题属于NP完全问题的一种, 目前没有精确算法可以找到最优解, 只能找到有效地近似解。
TSP问题的数学描述为:在正权图G (V, E) 中, 顶点集合V={1, 2, …, n}, 边集合为E, d为城市i到城市j的距离矩阵, 要找到最短路径的回路, 成为最佳哈密顿回路或最佳哈密顿圈。
三、算法实现
遗传算法是模拟生物界“物竞天择, 适者生存”的自然演化规律的一种随机搜索方法, 它将自然界繁殖、杂交、变异、竞争等概念引入算法当中, 通过一组可行解进行交叉、变异、逆转化等操作得到最优解, 是一种全局最优算法。其基本思路为, 首先对问题参数进行编码, 形成一定数量的染色体, 即初始种群, 然后计算种群的适应度, 再利用迭代对初始种群进行交叉、变异等操作得到更加优秀 (适应度更高) 的种群, 最终保留符合目标的最优群体。
在本例中, 利用遗传算法求解上述模型的主要步骤及部分代码如下:
(1) 编码
在遗传算法中, 大部分时候采用二进制编码方式, 但在求解旅行商问题时最简单最直接的编码方式是基于结点顺序进行编码, 如针对一个9个景点的旅游路径3-2-6-4-8-9-5-1-7可直接用 (3 2 6 4 8 9 5 1 7) 进行编码, 直观明了的情况下还可以满足模型中的约束条件。
(2) 初始化种群
随机生成一个初始解, 初始解的个数决定了初始化种群的数量, 本文中设定初始解中个体的数量为NIND=30, 同时设定最大迭代次数为GENMAX=500次。
(3) 适应度函数
适应度函数是用来评判个体优劣性的唯一标准, 是遗传算法进行个体选择的依据, 通常适应度函数由目标函数转化而来, 当求解目标函数最小值时, 一般使适应度值最大, 因此采用目标函数的倒数值作为适应度值, 本文模型中目标函数为总距离最短, 因此适应度函数设置如下
(4) 选择操作
选择操作是使用轮盘赌的方式, 从上一代种群中选择较优秀的个体作为父代繁衍子代, 父代个体被选择的概率与其适应度值相关, 适应度值越高, 被选择的概率越大, 个体i被选择的概率pi为
其中Fi为个体i的适应度值, NIND为初始种群数量。
(5) 交叉操作
将上一步选择的两个个体作为父代进行交叉操作以产生新的子代, 其方法是在[1, 9] (以9个城市为例) 之间随机取两个整数r1和r2, 将r1和r2之间的部分交换, 本文中设置交叉概率pc=0.8。
(6) 变异操作
变异操作是指在新产生的子代个体上进行的变异操作, 主要为了维持子代个体的多样性, 其方法是在[1, 9]之间随机取两个整数r1和r2, 将个体这两个位置上的编码数字互换。
(7) 终止条件判定
本文的终止条件为迭代次数=GENMAX (最大迭代次数) , 否则返回步骤3进行循环。
四、结果分析
根据以上遗传算法模型, 利用MATLAB编程进行模拟求解, 得到结果在第462代的到最优结果, 最优路径为1-2-19-20-10-21-18-3-9-11-7-8-14-15-24-25-26-29-28-27-23-22-16-17-30-12-13-4-5-6-1, 总距离为459.86km, 计算后可得游客在旅途路上 (不包括游览时间) 所用的最短时间为11.5h。对结果分析可知, 该模型和算法大大缩短了总路程, 根据问题描述和假设, 得到了最短距离、最短时间游览全部景点的路径, 该问题得到解决, 可见遗传算法对于解决TSP旅游路径规划问题效果显著。
总结与展望
本文首先将旅游规划问题转换成TSP问题, 然后建立混合整数规划模型, 最后利用遗传算法设计程序并求解该问题, 高效便捷的解决了旅游线路规划问题。但本研究结果仍存在不足, 如当景点数量n过大时, 遗传算法求解效率会大幅降低, 此时可以考虑将其他近似算法与遗传算法相结合提高求解效率, 这些内容有待进一步研究。
摘要：本文针对当前重点关注的旅游路径规划问题, 综合利用图论和智能算法的相关理论, 通过建立TSP数学模型和使用遗传算法对问题进行求解, 得到了遍历30个景点的时间最短、总距离最短的旅游路径。结果表明该方法具有较好的有效性和实用性。
关键词：旅游路径规划,TSP,遗传算法
参考文献
[1] 徐婷婷, 王柱, 徐海洋.旅游路线规划数学模型的建立与应用探讨[J].廊坊师范学院学报 (自然科学版) , 2016, 16 (1) :23-26.
[2] 喻菡.遗传算法求解TSP的研究[D].西南交通大学, 2006.
[3] 郑天翔.基于动态实时调度的主题公园游客时空分流导航管理研究[J].旅游科学, 2012, 26 (4) :8-16.
[4] 郑天翔, 吴蓉, 罗海媛.国内景区旅游流调控研究综述[J].地理与地理信息科学, 2015, 31 (5) :90-96.