基于遗传算法的旅游线路优化*

潘玉侠， 梁勤欧

(浙江师范大学地理与环境科学学院，浙江金华 321004)

0 引言

一个旅游区域内各景点分布在不同的位置，对某些景点进行游览的先后顺序有多种不同的串联方式，组合成不同的旅游线路．为了使旅游者能花费较少的时间而尽可能多地游览风景名胜，设计出最优的旅游线路成为必要．但是，旅游业发展到今天，无论在国内还是国外，旅游线路设计的成果都不是很多，高水平的研究成果更为稀少［1］．规划出的旅游线路多是依据各景点的历史文化背景和景区特色进行的分类规划，综合考虑到使旅行时间和距离最优化的研究很少．目前国内外有关这方面的文献主要有:文献［2］建立了最优旅游线路的模型;文献［3］研究了从中心城市出发的最优旅游线路;文献［4-5］选择不同的角度，构造了5种旅行线路模式．本文拟引进遗传算法，对旅游线路进行优化，实验对象为浙江省内20个旅游景点的旅游线路优化，目的是研究遗传算法进行旅游线路优化的可行性和高效性．

1 旅游线路优化问题描述

旅行线路设计的好坏直接影响到开发的功效，因此，旅游线路设计在区域旅游的开发中是一个非常重要的内容．一般的旅游设计着重于旅行景点的多样化，使游客在旅行过程中对每个景点都能产生截然不同的感觉;也有的旅游线路将同类的旅游景点串联起来，给游客展现出一类景点的完整画面，如历史古迹游、风景名胜游等．但这些线路的设计往往只考虑到某些景点的串联可以带给游客怎样的感官享受．这种设计方法很少注重效益方面的问题，即旅游者在出游时希望通过最小的旅游时间和成本获取最大的旅游经历．时间上，一般一个景点的游览时间大约都是一致的，予以重点考虑的是旅途时间，在空间上尽可能使整条线路有最便捷的走向来提高旅游效益．本文以景点之间的距离这个约束因素，对选定的20个旅游景点的旅行线路进行距离上的优化．

2 遗传算法对旅行线路优化求解设计

遗传算法最早由美国密执安大学的Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究，是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法［6］．遗传算法对旅行线路优化求解设计的具体运算过程如图1所示．

2．1 染色体编码

遗传算法中有多种不同的编码方法，主要有二进制编码方法、符号编码方法、浮点数编码方法等．在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码施加选择、交叉、变异等操作，不断搜索出适应度较高的个体，并在群体中逐渐增加其数量，最终寻出问题的最优解或近似最优解．

为了本文的研究简便起见，笔者采用符号编码方法．符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集．这个符号集可以是1个字母表，如{A，B，C，D，…};也可以是 1 个数字序号表，如{1，2，3，4，5，…}等;本文需要研究包含20个旅游景点的旅行路线优化问题;用符号编码的方法，每个数字代表1个景点，随机生成区间为［1，20］的20个整数的随机排列，如下所示，这个排列就可以作为一个染色体．

图1 遗传算法对旅行线路优化求解设计的主要运算过程

?

从以上可以看出，符号编码具有以下优点:1)符合有意义积木块编码原则;2)便于在遗传算法中利用所求解问题的专门知识;3)便于遗传算法与相关近似算法之间的混合使用．

2．2 适应度函数设计

本文所要研究的是在给定特定景点的情况下，选择怎样的编排方式，使旅途所花费的时间和成本最少，取得最优效益．因此，构造适应度函数时，为了简单起见，本文只考虑各景点之间的实际距离．适应度函数构造如下:

式(1)中，Sij代表第i个景点和第j个景点之间的欧氏距离．

2．3 控制参数设计

遗传算法进行旅游线路优化控制参数设计如表1所示．

表1 遗传算法主要控制参数

2．4 存活选择策略

采用轮盘赌的方式，选取适应值大的个体作为父体．

选择过程是以旋转赌轮100次为基础，每次旋转都为新的种群选择一个个体．赌轮是按个体的适应度进行选择的，适应值大的个体则选取，适应值小的个体则去除．具体算法设计是:先计算出每个个体累计概率值，然后从区间［0，1］中产生出一个随机数r，若某个个体的累计概率值大于这个随机数r，则选取这个个体．

2．5 遗传算子设计

1)交叉算子设计:本文采用部分映射交叉(PMX)，确定交叉操作的父代，将100个样本两两组合分为50组．首先从闭区间［0，1］中产生2个随机数b1和b2，另r1等于b1×100和b2×100，确定2个位置，对2位置中间的数据进行交叉．交叉后，同一样本中会有重复的景点，不重复的数字保留，重复的数字采用部分映射交叉法消除重复．

2)变异算子设计:本文采用倒位变异法，和交叉算子的设计相似．即随机选择2个点c1和c2，交换位置，并将2点间的数字从c2开始倒序放置．

3 实验仿真

本文采用位于浙江省内的20个景点进行路线优化的试验，景点名称和景点序号代码及景点经纬度坐标如表2所示，所选取的景点排除了受季节性影响比较大的个体，如舟山桃花岛．因为景点级别相当，文中对景点权重值和游客在每个景点的逗留时间进行了简化处理，即假设各景点的权重值及游客在每个景点的逗留时间均为1，在进行旅游线路优化时，只考虑景点之间的欧氏距离，即给出各景点的相对坐标值，采用欧氏距离的计算方法:

式(2)中:Sij代表第i点到第j点之间的距离;(xi，yi)，(xj，yj)为i点和j点的相对经纬度坐标值．实验中忽略了地图投影引起的差异，在小范围内作实验研究，只是想说明遗传算法的效果，在以后进一步的研究中将以实验球面距离来计算．

表2 各景点的相对经纬坐标值

本文基于遗传算法理论建立的旅行线路优化算法运行结果如图2所示，其中的1～20数字是各城市的代号，具体所代表的城市和表2相对应．运行的最优结果为 10．409 3，平均值为12．475 4．图3 为搜索过程，验证了该算法具有较好的收敛性;图4为搜索路径的最终结果图，较好地展示了最优的行走路线．为了更好地将结果展示出来，本文采用ArcGIS软件将结果在地图上绘制出来，如图5所示，以使结果更明确，同时根据路线图也验证了实验所得的数据具有一定的真实性，最终验证了遗传算法理论运用于旅行线路优化设计中的可行性．

图2 旅游线路优化算法运行结果

图3 搜索最优旅游路线过程

图4 最优旅游路径运行结果

4 结论

随着旅游业的蓬勃发展，设计出完善可行的旅游线路，既有利于我国旅游业的发展，也有利于游客及旅行社在旅游过程中节约成本．而现阶段的旅游线路设计多是着重于旅游景点的搭配和特色旅游线路之上，很少有从优化旅行距离和时间入手的．鉴于此，本文首次提出了将遗传算法理论运用于旅游线路优化之中，并建立了基于遗传算法的旅行线路优化算法．经过实验仿真，证明了遗传算法理论运用于旅游线路优化之中的有效性．在采用遗传算法理论进行旅游线路优化的过程中，所选取的影响因子过于单一，本文变量因子只有距离因素，有可能会使实验结果与事实有一定程度的偏差，许多方面还有待完善．期望在以后的研究中能够有更完善的成果，使采用该方法规划的旅游线路能够具有一定的灵活性，并和事实能够紧密结合，让这一理论在旅游线路规划和设计方面的应用能够扩展开来，真正应用到实际中来．

图5 最优旅行路线图

［1］吕威，倪玉华．基于等距加密和案例推理的旅游线路聚类算法［J］．计算机工程和应用，2010，46(11):223-225．

［2］Campbell C K．An approach to research in recreational geography［M］．British Columbia:Department of Geography，University of British Columbia，1967:32-37．

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

［4］Stewart S I，Vogt C A．Multi-destination trip patterns［J］．Annals of Tourism Research，1997，24(2):458-461．

［5］Lundgren J O J．The development of tourist travel system:A metropolitan economic hegemony par excellence［M］．Jahrgang:Jahrbuch fur Fremdenverkegr，1972:62-65．

［6］周明，孙树栋．遗传算法原理及应用［M］．北京:国防工业出版社，1999:38-39．