旅游线路优化设计探讨.docx

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