基于遗传算法的环中国旅行路线优化策略

魏书禾

东北财经大学国际商学院，辽宁大连 116000

引言

当今世界，经济和社会的高速发展，给人们的休闲娱乐生活带来了更大的选择性和多样性。近年来国家统计局出示的报告显示国家的旅游业正在逐年高速发展，其中，自助游正在越来越受到人们的追捧[1]。在实际旅游的过程中，自助游所最需要考虑的就是关于路线的规划，即路径寻优加上有关费用的问题。那么，在路径寻优的问题中，如何进行更有效的规划？如何在城市或者景点之间实现路线的动态规划和均衡？在实现路线规划后如何找到用户满意度最高的一条路线？通过阅读大量的参考文献我们可以发现，大多旅游路线的规划文献运用的方法是启发式的蚁群算法[2-8]；部分文献则注重于某个省份或地区旅游线路的优化[9-12]

由于蚁群算法具有种群的限制性和约束优化型，针对环中国的旅游线路优化问题，本文拟采用GA遗传算法，随机产生种群，用轮盘策略确定个体的适应度，用判断是否确定个体的舒适度来判断是否符合优化准则，不断循环输出最佳个体和最优解，并且按照一定的交叉概率和交叉方法生成个体和种群并不断地优化求解。

利用R软件，我们画出了中国地理位置的经纬度画出中国地图标注省会城市（见图1）。

一 基本理论支撑

（一）遗传算法（GA）的基本原理

遗传算法模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量—染色体，向量的每个元素称为基因. 通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。

（二）遗传算法（GA）的思想

遗传算法借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

（三）遗传算法（GA）在文中的应用

遗传算法是一种无约束优化的遗传算法。在运用时候，可通过数学的方式，利用计算机仿真技术，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法，通常能够较快地获得较好的优化结果。常用来解决路径寻优问题，以及一系列的优劣决策问题。在本文中，我们的遗传操作包括以下三个基本遗传算子：选择、交叉、变异。

本文选了全国43个主要城市为旅游地，是一个典型的旅行线路的线性规划模型和图论模型。通过GA算法的重复循环和多次决策，我们寻找到的最优路径达到全程最短为38286公里。接着，我们将分为动车和自驾两种出行方式，分别算出所需花费的费用，并进行比较。

（四）遗传算法（GA）的流程图

在文中，我们的目的是根据旅游路线设计的特点与游客信息完成对旅游线路的优化工作。遗传算法用于解决NP难题，与旅游路线的规划相契合，因此把遗传算法应用到旅游路线的规划中。本次拟合全国43个主要的城市，设定流程控制设计（见图2）。

图2 遗传算法流程图

二 模型运行与操作

（一）遗传算法的基本操作

遗传算法有3个最关键步骤：选择运算，染色体交叉，染色体变异。选择运算是从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体做准备。

首先设计染色体编码，把解空间的表示方法转化成适用于遗传算法搜索空间中的可行解，即转化成可用遗传算法进行处理的基因编码。本文中43个主要城市的路线优化难题，可用符号编码的方式，使用数字1—43生成一个随机排列，作为一个染色体，假定初始的种群中含有10个染色体。

在GA算法进化过程中，依据适者生存的原则，适应度比例法为了划分种群中个体的优劣的标准。本文研究环中国主要城市的旅游路线规划，选择一条路线使得路程最短，从而降低旅途的时间成本和金钱成本，提高旅行的价值最大化。

本文使用R统计软件实现编程，由城市之间的距离矩阵，每条染色体（即43个主要城市的一个随机排列）中每个基因的距离的和，作为适应度的运算结果。距离的和越小，路线越短，实现旅游路线的优化。

（二）选择方法

本文采用常见的轮盘赌的方式，选取适应值大的作为个体作为父体，赌轮是按个体的适应度进行选择的，适应值大的个体则选取，适应值小的个体剔除。

交叉操作：随机选择2个个体，在对应位置交换若干个基因片段，提示保证每个个体依然是1—43的随机排列，本文采用的交叉率为0.8。

变异操作：随机选取个体的2个基因进行交换以实现变异操作，本文采用的变异概率为0.2。

（三）全国43个城市旅游路线GA算法优化

本文对收敛速度机进行控制，种群规模提取500，总共进行1000次迭代，交叉概率0.8，变异概率取0.2，利用R软件进行计算，结果如图3环中国旅行路线图所示。

图3 环中国旅行路线图

通过R软件对坐标进行标准化后拟合得到的单向闭合的旅行线路图形，可见遗传算法对旅游线路的选择有明显的优化作用，达到全程最短里程数。并在经过844次的迭代后趋于平稳，得出全局最短距离为38286公里。利用GA算法得到最优的路线为：

大连—丹东—吉林—齐齐哈尔—沈阳—哈尔滨—牡丹江—长春—二连浩特—北京—济南—杭州—福州—南昌—深圳—广州—桂林—株洲—徐州—合肥—南京—上海—青岛—石家庄—太原—锦州—武汉—郑州—成都—贵阳—柳州—南宁—长沙—重庆—昆明—拉萨—西宁—乌鲁木齐—兰州—西安—呼和浩特—银川—天津—大连。优化后的旅游线路，不但路程最短，用时最短，从而实现旅游价值的最大化。

GA进化迭代过程如图4，横坐标表示迭代的次数，纵坐标表示适应度即距离的倒数。从图中可以清晰地看出，当迭代到850次左右，适应度函数趋于平稳，平稳值为2.6119*10-5。起倒数为38286公里。

图4 GA进化迭代过程图

（四）按照两种不同交通工具计算费用

采用自驾游方式出行：假设在旅行中自驾游每天行驶500公里、每三天中有一天行驶1000公里，每公里费用1元，每人每天食宿为230元；那么38286公里共花去大约58天时间，得到四个人的总费用为：

230×58×4＋ 38286=91646（元），完成 43个中国主要城市的旅行共计花去91646元。

采用动车出行方式：

动车基价是由线路和车辆等级（运行速度）共同决定的，一般情况下：

在200km/h的速度下，一等座基价大约是0.37元/公里，二等座基价大约是0.30元/公里。

在300km/h的速度下，一等座基价大约是0.74元/公里，二等座基价大约是0.46元/公里。

按照动车二等座200km/h计算，每公里0.30元票价标准，在城市停留天数与自驾游一致58天；进行得到4个人环游43座城市的费用为：

230×58×4+38286×0.3×4=99303.2元，完 成43个中国主要城市的旅行共计花去99303.2元。

对比两种出行方式，4个伙伴自驾游的费用较节省。

三 结语

本文针对从大连出发，每人费用1万元的条件下，4个人环游中国43个主要的城市之旅。首先采用遗传算法（GA）对中国主要43个城市进行环中国旅行路线进行优化，利用种群是10个，交叉率0.8,变异率0.2 ，进行1000次的GA算法迭代，得到最短路径。共计38286公里。分别采用自驾游和动车出行的方式计算费用，得出结论：自驾游出行方式能够更加节省。

未来可以对本课题进行更加细致的研究，精确计算景区的游玩时间以及在城市的停留时间；把GA算法优化旅游线路中做得更加精确。比如适应度函数可以添加不同的权重等。