1、旅游线路优化设计探讨 摘 要 本文主要探讨最佳旅游线路的设计问题，在满足相关约束条件的情况下，用最少的天数游览尽可能多的景点是我们追求的目标。本文以运筹学中最优化理论和图论的相关知识为基础，对河南省旅游线路设计的问题加以分析。 下载 关键词 最优旅游路线 排列组合原理 最邻近插入法 分枝定界法 中图分类号： F590.1 文献标识码： A 一、问题的提出 随着生活水平的不断提高和精神压力的不断增加，旅游已成为人们调节心情、释放压力、提高生活质量的重要活动。旅游本身应该是一个让人身心愉悦的过程。但是实际上，经常会听到旅途中的游客抱怨 “ 累死了 ” 、“ 我还没来得及拍照呢 ” 。可见，选择合理
2、的旅游线路是很有必要的。 一个旅游区域内的若干景点各在不同的空间位置，对这些景点游览或活动参与的先后顺序与连接方式，可有多种不同的串连方式，由此产生组合成不同的旅游线路。旅游线路设计可以分为四类：第一类指区域旅游规划中的线路设计；第二类指景区 内部的游道设计；第三类指旅行社线路设计；第四类指旅游者自主旅游所设计的旅游线路。本文探讨的旅游线路设计是第四种，即游客根据自己的喜好所设计的旅游线路。 在编制线路时应充分考虑到节省游客的每一分花费，使游客每一个景点都要游览，并且不走回头路，同时不同的旅游类型的线路设计应有差别。下面用最优化的知识探讨一下性价比最高的休闲度假游的河南自驾游方案。 二、景点选
3、取 旅游界流传着这样的说法：我国旅游看 “ 三南 ” ，一个是海南，一个是云南，再一个就是河南。河南省旅游资源得天独厚，高品位的人文胜 迹与诸多的自然景点交相辉映。按照中国旅游资源普查规定，将旅游资源分为 6类 74 种基本类型，河南的旅游资源几乎全部覆盖，现已形成以郑州、洛阳、开封三大旅游城市为中心，辐射全省的旅游发展格局。其中拥有世界文化遗产 3个，分别是龙门石窟、安阳殷墟、登封 “ 天地之中 ” 历史建筑群；世界地质公园 4个，分别是云台山、嵩山、王屋山 黛眉山、伏牛山；全国5A 级旅游景区 9 家：登封嵩山少林景区、洛阳龙门石窟景区、焦作云台山、开封清明上河园、安阳殷墟、洛阳嵩县白云山
4、风景区、焦作云台山 ?神农山景区、焦作青天河景区、尧山 中原大佛景区； AAAA级景区 72 个，分别是白马寺、鸡公山、南湾湖、关林，相国寺等。 根据河南省旅游景区概况，下面以景区级别、交通通达度、景区集群状况、游客个人喜好、旅游纪念品五大因素作为景点旅游价值指标体系，给各个景点进行赋值，利用 Excel进行排名，进而选出在这些条件下能代表河南的 6大旅游景点。旅游行政部门与游客可根据不同需要进行调整、建立相应的旅游价值指标体系。 设定： 1、景区级别：世界文化遗产或世界地质公园 =10分； AAAAA级 =8分；AAAA 级 =6 分（ AAAA 以下不考虑）； 2、交通通达度：高速沿线 =
5、10 分，国道沿线 =6 分，省道沿线 =3分； 3、集群状况： 50km内有其他景点加 3分； 4、游客个人喜好：自然景观 =10分；人文景观 =6分； 5、旅游纪念品：有 =5 分。据调查，景区中 50 元以下的中低价位旅游纪念品销路最好，纪念品花费一般占旅游者景点总花费的 10%15% 。 根据河南省导游图和上面设定的旅游价值指标体系，选出的景点如表 1： 表 1 所选取的最优景点 三、模型假设与符号说明 1、旅行者前往下一个目的地 时，不会出现被滞留等意外情况； 2、仅考虑路费与门票费，其它费用不计； 3、将城市看作点（旅行路线的总路程不包括在某一城市中观光旅游的路程）； 4、两城市之
6、间的距离可以近似看作直线距离； 5、通过查找资料所获取的城市信息是真实可靠的，具有使用价值； 6、没有超出景区承载力； 7、假设公路没有等级差别，即可将所有路面的状况视为等同且汽车恒速。 四、具体解法 随着生活节奏的不断加快，在旅游舒适度不受影响及体力许可的情况下，用最少的钱 与天数游览尽可能多的景点是游客追求的目标，由于门票价格固定，旅游所用的时间与旅游路程成正比关系，从而把问题转化为制定一个合理的路线，尽量缩短旅游的路程，使总路程最短，即求最短的旅游线路问题。由于各景点距离依托城市（郑州）的距离较远，加上游客不走 “ 回头路 ” 与 “ 冤枉路 ” 的原则，要走的是环形回路，放射形回路显然
7、是不可取的。这个问题可以用求加权无向图总权数最小的哈密顿圈来寻找近似的最短旅游线路。 下面运用图论中的 “ 最邻近插入法 ” 来寻找近似最佳旅游线路，其算法与具体求解过程如下：把每个旅游景点看作加权无向图 中的各个顶点，各景点之间的直达公路看作加权无向图中对应顶点间的边，各条公路的长度看作对应边上的权。若景点之间没有直达的公路则加权无向图中对应顶点之间用 “ 边 ” 相连，而这条 “ 边 ” 的含义是：由其中一个景点出发，通过中转站到达另一景点所需的最短距离，这样所旅游的各个景点间的公路网就转化为加权无向图 (各边的权数是对各景点间距离取整而得 )，所旅游各个景点的近似最佳旅行线路问题，就转化
8、为在给定的加权无向图中，寻找从给定的顶点出发，行遍所有顶点只有一次再回到该指定的顶点，使得总权数 (总路程 )最小。寻找近似最佳旅游线路的算 法如下： 步骤 1：用 Floyd 算法求出加权无向图中任意两点之间的最短路程，形成一条边的初始路，其权限 w(i， j)。 步骤 2：设 z 表示最新加到这条路上的景点，从而不在这条路上的所有景点中选一个与 z景点最靠近的景点 y，把连接 z景点与 y景点的边加到这条路上。重复这一步，直到加权无向图中所有景点都包含此路上。 步骤 3：将连接起点与最后加入景点之间的边加到这条路上，就得到一个总权数最小的哈密顿回路。 对三中所选 6 个景点旅游线路的优化问
9、题可以描述为：从河南省会郑州市出发，遍访各个 景点一次且仅有一次后，再返回郑州，求总路程最短的闭合路径，那么这 6个景点之间的距离关系可用一个加权无向图 G来表示，如下图 1 所示： 图 1 景点距离关系无向图 G 由河南省典型景点的加权无向图 G寻找这 6个景点的近似最佳旅游线路的具体过程如下： 开始于顶点 1，组成闭旅程 11，在下一阶段最邻近 1的顶点为顶点 2，建立闭旅程 121，顶点 3最邻近顶点 2，建立闭旅程 1231。 接下来，由于顶点 5最邻近顶点 3，将顶点 5插入上面闭旅程，根据排列组合原理计算，得到 6个闭旅程，它们的长度分别如 下： 12351： 60+75+140+
10、143=418， 12531： 60+116+140+124=440， 13251： 124+75+116+143=458， 13521： 124+140+116+60=440， 15231： 143+116+75+124=458， 15321： 143+140+75+60=418。 在这些闭旅程中选取长度最短的旅程为 12351 或 15321。 距离顶点 5最邻近的为顶点 6，将顶点 6插入上面最短闭旅程，根 据排列组合原理计算，得到 24 个闭旅程，它们的长度分别如下： 123561： 60+75+140+170+187=632， 123651： 60+75+311+170+143=75
11、9， 125361： 60+116+140+311+187=814， 125631： 60+116+170+311+124=781， 126351： 60+266+311+140+143=920， 126531： 60+266+170+140+124=630； 132561： 124+75+116+170+187=672， 132651： 124+75+266+170+143=778， 135261： 124+140+116+266+187=833， 135621： 124+140+170+266+60=760， 136251： 124+311+266+116+143=960， 136521：
12、 124+311+170+116+60=781； 153261： 143+140+75+266+187=811， 153621： 143+140+311+266+60=920， 152361： 143+116+75+311+187=832， 153261： 143+116+266+311+124=960， 156231： 143+170+266+75+124=778， 156321： 143+170+311+75+60=759； 163251： 187+311+75+116+143=832， 163521： 187+311+140+116+60=814， 162351： 187+266+75+
13、140+143=811， 162531： 187+266+116+140+124=833， 165321： 187+170+140+75+60=632， 165231： 187+170+116+75+124=672。 在这些闭旅程中选取长度最短 (632)的旅程为 123561 或 165321。 最后，将顶点 4插入上面最短闭旅程，根据排列组合原理计算，得到闭旅程 120个及其长度，要从中选择最短旅程，计算过程就比较复杂。下面用“ 分枝定界法 ” 寻找近似的 最佳旅游线路。 “ 分枝定界法 ” 的图论模型如下：用阶矩阵 D 中的各个元素来表示各个景点之间的距离，且各个景点之间的距离是没有方向
14、的，那么 n阶矩阵 D是对称型矩阵。首先，在这个矩阵 D中，抽取每行的最小元素，并令矩阵 D每行中的所有元素减去该行的最小元素，得到新的矩阵 D1。再抽取矩阵 D2 每列的最小元素，并令矩阵各列的所有元素减去该列的最小元素，得到新的矩阵，这样得到的矩阵每行每列都至少有一个零元素存在。然后，选择起点与某景点之间距离为零的元素，把这个元素所在的行和列从矩阵 D2中划去，得到新的矩阵 D3。同时，把 起点与某景点组成一条路。对矩阵 D3重复矩阵 D变化到矩阵 D2的步骤操作，得到新的景点加入到最近路的末顶点的后面，使其成为一条新路。直到得到的最后矩阵是，且这条路包含所有的景点，所有的景点在这条路上只
15、能出现一次，这样操作才算停止，否则重复上面的步骤。 寻找这 7个景点的近似最佳旅游线路的具体过程如下： 选顶点 2，线路 12 ，把 D1 中的第 1 行第 2 列划掉，令 d21= 得 选顶点 3，线路 123 ，把 D5中的第 1行第 2列划掉，令 d31= ，得 选顶点 4，线路 1234 ，把中的 第 1行第 2列划掉，令 d41= ，得 选顶点 6，线路 12346 ，把 D9中的第 1行第 3列划掉，令 d61= ，得 从而得线路 1234651 ，长度为 60+75+196+259+170+143=903，在这些闭旅程中，选取长度最短 (903)的旅程为 1234651。显然，长
16、度最短的闭旅程就是所要寻找的近似最佳旅游线路。 （作者：王美香，郑州旅游职业学院教师，郑州大学数学系在职硕士研究生，研究方向：线性规划与最优设计；杨继奎，郑州大学数学系硕士研究生，研究方向：图论与组 合最优化） 参考文献： 汤庆园、夏安桃等 . 发展特色河南旅游业的优势、问题及路径 J.湖南城市学院学报， 2010(9) 赵西萍 .旅游市场营销学 .高等教育出版社， 2002 徐凤生 .最短路径的求解算法 .计算机应用， 2004(5) 蔡文芳 .运筹学在旅游线路规划中的作用 .经营管理， 2009(9) 殷剑宏、吴开亚 .图论及其算法 .中国科学技术出版社， 2003 方冬云 .图论在旅游线路选择中的应用 .长春工业大学学报， 2009
