c最佳旅游路线设计 孟建龙 29页

安徽工程大学数学建模课程设计论文题目：最佳旅游路线设计指导老师：周金明成绩：完成日期：2013年7月3日 摘要：旅游的最佳线路的选择会直接决定旅行者的旅行时间和金钱的花费，设计合理可行的旅游线路则使这一费用的唯一标准，由于实际纷繁复杂的景点，交通，时间等对方面因素的综合影响和相互作用下，通过“点线图”将复杂的现实景点和路线表示在便于处理的简单的只有点和线组成的图中，便于我们运用一定的数学工具进行最优化处理。通过综合各方面的信息、资源，并对其进行相应的处理整合如“点线图”，在保证合理，准确，有效，详实的同时，将抽象的，复杂的实际概念和数据量，转化为有价值的，精确的时间和费用值。这样“点线图”中每一个点就对应地包含其最佳停留时间和花费情况，其中为了合理的表示花费，构造“城市分”的概念来表示。而每一条线也都对应地包含所花费的时间和费用，这些数量通过表格给出，在求取最优解时视为相应点或线的特性。为了难保证这种转化的实际意义和有效性，准确性，通过多方数据的综合分析、平均，共同得到的综合得到。在“点线图”的基础上，做出必要假设和的基础上，将图形做进一步的简化分区，将一个图形分成若干个子图，对图进行处理，把问题拆减。利用已经比较成熟的Dijstra算法，找到其它城市距离中心城市（这里使乌鲁木齐）的最小距离，然后利用避图法找到最小树，这样在路线周围，结合图形特点，围绕近似路线周围作局部搜索，在大大减少数据运算的情况下，得到相对最优解。对得到的最优解进行检验，验证其确实是比较优的线路。即基本处理过程为：抽象图形分解图找到近似算法子图中在近似算法得到路径周围搜索调整边界检验路线分析建模、解模的整个过程，合理地分析可以得到，方法可以被推广到其它更加复杂的环境。【关键词】：点线图城市分旅行推销员问题哈密顿Dijkstra算法，避图法0 301001一、问题重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。1.请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。2.如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。3.如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。4.新疆自治区旅游部门为迎接“五一旅游黄金周”（考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。二、问题的假设1、为了尽量节约费用，由于飞机的价格要远高于铁路和公路，而后两者基本相同。所以在新疆境内的交通费用，以铁路票价为主，没有开通铁路的线路，则以公路票价为主；2、对于公路的收费没有明确标价的路段，以两个旅游点之间的公路里程（km）除以平均时速（60km/h）进行估算。对于少数公路也欠发达的地区，则以速度折半为30km/h估算；3、假设在新疆的所有景点中，对任何的A、B两个景点，从A到B所需花在路上的时间与从B到A的相同，即忽略例如由于列车停靠站不同所造成的运行时间上的一些差异；4、暑假的一个月为31天，考虑到往返新疆的时间，故花费在新疆境内的旅游时间以30天计；5、在新疆境内各旅游景区的住宿费用均为一个定值：RMB150/标准间（两人）/天；6、设旅游途中的休息调整时间合并在每个景点的观光逗留时间之内，不再予以单独的计算；7、不考虑交通费用在白天和夜晚的区别，（如火车硬座与卧铺价格上的差异等）均以最低价格即硬座票价计算。8、对于旅行社推出的旅游线路的设计，与自助游不同，我们认为其主要目标不在于节省费用而在于多游览美景和旅途的舒适，因此假设在新疆省内白天的时间都用来游玩，景区间的行程则采用飞机（时间短故可忽略）连接或在晚间乘车抵达。9、假设铁路和公路交通费用的票价，与行驶的里程近似成线性关系，而又因为列车或汽车时速也是一定的，这样，某一段路程需要的交通费用也与其时间呈近似的线性关系，这样，求最小费用，也即求最短路线。注：假设9的依据：我们对部分景点间往返的时间和费用进行采样，并作回归分析如下页图所示：（R平方为0.9819，F值为595.6604，说明两者呈很强的线性关系。几乎可以认为交通费用与路程成正比。）27 301001（图1：价格—距离采样关系图）一、符号的约定编号景区（景点）名称编号景区（景点）名称1乌市11天鹅湖2石河子12喀什、香妃墓3伊犁13和田4天池14民丰5吐鲁番15博乐6火焰山16楼兰、罗布泊7哈密17阿勒泰8库尔勒18克拉玛依9库车19奎屯市10阿克苏20天鹅湖1.在所规划的旅游行程中,可能重复经过某些景点,对于经过而不停留的景点,采用[景点]表示;2.总路程S3.不均衡度27 3010013.旅游推荐总天数4.考察总天数一、模型建立与求解4.1模型一1.问题一一、问题分解：1.以旅游景点逗留的天数作为自变量，以单位天数所用的钱为目标函数，取最小值。2.选择最优巡回路，我们参考了如下两个定义：巡回路：过各个节点，每个节点至少经过一次的回路。哈密尔顿回路：每个节点只经过一次的回路。总长度最小的巡回就是最优巡回路。最优巡回赂和最优哈密尔顿回路在如下条件下是等价的；定理：回路中，任2个节点，若能满足下列三角不等式：则最优巡回路与哈密尔顿回路相同。理论模型建立的基本思想是：首先，对于任意一个无向网络，利用任意节点之间的最短路算法构建一个等价网络，在网络中个节点之间的距离用最短路代替。据此，解得的最优哈密尔顿回路就可以很方便的还原为最优巡回路，实质是TSP问题。而解最优哈密尔顿回路的方法可以才用最优二叉树法（参考书[1]64页）、DijKstra（见参考书[2]336页）法等。解TSP问题也有相应的软件求解，更为方便。基于以上对问题1的分析，要解决问题1的关键在于每种旅行路线方案的最优解的获得，而获得最优解的关键则在于确定网络的最优巡回路。第1步将图变换为。第2步为方便表示，将图中各节点进行编号如表1-1编号景区（景点）名称编号景区（景点）名称1乌市11天鹅湖2石河子12喀什、香妃墓3伊犁13和田4天池14民丰5吐鲁番15博乐27 3010016火焰山16楼兰、罗布泊7哈密17阿勒泰8库尔勒18克拉玛依9库车19奎屯市10阿克苏20天鹅湖表1-1第3步根据达坂城（位于乌鲁木齐）、天池、、吐鲁番、楼兰古城、伊宁五个点组成的网络求其完备图，其中任意两点间的最短距离可表示如表1-2：ACDEPA058018375542C5800763889622D1837630590225E7558895900797P426222257970表1-2第4步求解最优哈密顿回路，此处应用WINQSB软件中的Networkingmodel模块求解得27301001Solutionfor5place:Minimization(TravelingSalesmanProblem)FromNodeConnectToDistance/CostFromNodeConnectToDistance/Cost1AC5804DP2252CE8895PA423ED590TotalMinimalTravelingDistanceorCost=2326(ResultfromBranchandBoundMethod)即最优哈密尔顿回路为：A——C——E——D——P——A即：乌鲁木齐——伊宁——楼兰古城——吐鲁番——天池——乌鲁木齐其最短距离为2326KM。仅对此五个地点进行游览，则有：，27 301001至此完成了对第一组路线的建模，接下来可用LINGO解此非线性规划（原程序及详细结果见附录2），求得目标函数的最优解。解得：Objectivevalue=117.42由此可见，上述非线性规划建模的结果实质是证明了，目标函数在以下条件下成取得最优解：（1）各个景点所用的时间总和正好等于30天。（2）在各景点间满足交通距离最短的前提下，应该在单位时间花费最小的景点逗留时间长，而其余单位时间花费较大的景点只要满足推荐逗留时间即可。根据上述结论队之前的问题1模型的假设进行修正与简化。经简化与修正后，模型可陈述如下：在一个月的时间里，至少保证分配给以上五个地点推荐逗留时间，在剩余的时间里优先考虑离上述各景点距离最近、单位时间消费较少的景点。同时保证各景点推荐天数少于30天。这样就不必如之前的假设一样，每加一个景点计算一次最优解。而只需选出具备上述条件的景点，与前五个景点构成新图，求新图的完备图的，继而求其最优哈密尔顿回路，最后将所求结果回带到相应的目标函数中。按照上述方法求解，则：第1步按要求选出其余合适的点。图1-2优先考虑达坂城（位于乌鲁木齐）、天池、、吐鲁番、楼兰古城、伊宁这五个点连通后沿途的点。将选出的点与此五点组成新图，如图1-2。第2步求图1-2的完备图，其中任意两点间的最短距离可表示为：ABCDEFHKOPSA016058042183221555392488755286B1600420202343381562232328915126C5804200622736616518188247710294D422026220225263592722908797328E183343736225038390720671590469F22138161626338042875870962850727 301001H5555625185923904280330638200436K3922321887227207583300308530106O4883282479086717096383080838202P7559157107975906282005308380636S2861262943284695074361062026360第3步求解最优哈密顿回路，将矩阵表示的距离关系输入到WINQSB软件中的Networkingmodel模块，并建立TravelingSalesmanProblem（TSP）。得到如下结果：SolutionforThebestway:Minimization(TravelingSalesmanProblem)FromNodeConnectToDistance/CostFromNodeConnectToDistance/Cost1AF2217OS2022FE388SK1063EH3909KB2324HP20010BD2025PC71011DA426CO247TotalMinimalTravelingDistanceorCost=2590(ResultfromBranchandBoundMethod)由此得出最优路线为：A——F——E——H——P——C——O——S——K——B——D——A即：乌鲁木齐——火焰山——吐鲁番——库尔勒——楼兰——伊宁——博乐——奎屯市——天鹅湖——石河子——天池——乌鲁木齐汽车沿两点间的最短距离行驶，所行驶的距离为2590KM。又由于各地天鹅湖消费最小，因此在计算总费用时，其余各地只考虑最佳逗留时间即可（见附录），剩余的时间全部留给天鹅湖。因此的出一个人沿上述规定路线旅游所用的总费用为：由于是两个人一同旅游，因此二人所用的总费用为至此问题1基本解决。2.问题二、三以下两问共同规定符号：1.在所规划的旅游行程中,可能重复经过某些景点,对于经过而不停留的景点,采用[景点]表示;2.总路程S3.不均衡度3.旅游推荐总天数4.考察总天数27 301001一．问题二：分两次游玩,交通费用尽量节省.1．要求分解：分两次游玩设计总路程最短两组旅游天数尽可能均衡2．问题分析：在旅游地图中,每个景点或者景区抽象为图中的一个节点,各景点之间的通路看作图中对应节点之间的边,各路线的长度(一一对应交通费用)看作对应边上的权,所给的旅游图就转化成图论中的带权网络图G(V,E,W),交通费用最少问题就转化为一个图论问题.即在已知的带权网络图中,从一给定点(乌鲁木齐)出发,行遍所有景点再回到出发点,使得交通费用尽量地节省即总路程最短且两组旅游天数尽可能均衡.3．模型阐释：在加权图G=(V,E,W)中,构造一个以V为顶点集的图G’=(V,E’),E’的每条边(x,y)的权等于顶点x与y在图中最短路的权,则该图称为加权图G的完备图G’经过G的顶点正好一次,且权最小的圈称为最佳H圈;经过每个顶点至少一次且权最小的闭合通路称为最佳推销员回路总路程交通费用的不均衡度加权图G的最佳推销员回路的权与其完备图G’的最佳H圈的权相同，在加权图中寻求最佳推销员回路的问题可转化为在其完备加权图中寻求最佳哈密顿圈(1)分析方法一:将此问题模拟为多个推销员的最佳推销员回路问题,即在加权图G(V,E,W)中根据每个景点的最佳旅游天数将顶点集V划为天数大致相等的几个部分,…,,将G分成n个生成子图,,…,然后在子图中采用最佳推销员回路算法[3].由于单个推销员的最佳回路问题并不存在精确解,所以多个推销员的问题也不存在精确解,在该图中有19个节点,我们尽量寻求一种较为合理地划分准则27 301001在分组时采用准则如下准则一:尽量使同一干枝上及其分枝上的点分在同一组;准则二:如某景点交通实在太远,则可作为不可行点剔除准则三:尽量使用于交通的时间,以及用于旅游的时间在两组均衡显然在首要考虑交通费用的时候,离出发点乌鲁木齐太远[距离最近景点超过500公里]的景点(喀什,和田,民丰)可以不考虑.由上述分组准则,我们可以大致找到两组分组形式如下:分组一:其中0.6mm粗线线条所经过的景点为一组包括:阿克苏,库车,天鹅湖,库尔勒,楼兰罗布泊,吐鲁番,火焰山和哈密;0.3mm细线线条所经过的景点为第二组包括:伊犁,博乐,奎屯市,石河子,克拉玛依,阿勒泰,天山天池,乌鲁木齐;喀什,和田,民丰太偏僻,景点分散,路途遥远可以暂不考虑.27 301001分组二:其中0.3mm细线线条所经过的景点为一组包括:阿克苏,库车,天鹅湖,库尔勒,楼兰罗布泊,伊犁博乐,奎屯市,石河子;0.6mm粗线线条所经过的景点为第二组包括:克拉玛依,阿勒泰,天山天池,乌鲁木齐,吐鲁番,火焰山,哈密,石河子.根据定理1我们可以将最佳推销员回路问题转化为在完备加权图中寻找最佳H圈,即TSP问题分组一的近似解见表1旅游时间分组路线路线长度(公里)景点游玩时间(天数)路线总长度(公里)第一组乌鲁木齐—天山—阿勒泰—克拉玛依—奎屯市—博乐—伊犁-天鹅湖—[奎屯市]—[乌鲁木齐]2038225032第二组[乌鲁木齐]—吐鲁番—哈密—[吐鲁番]—火焰山-[吐鲁番]—库尔勒—楼兰罗布泊—[库尔勒]—库车—阿克苏—[库车]—[天鹅湖]—[奎屯市]—石河子—[乌鲁木齐]299422分组二的近似解见表2旅游时间分组路线路线长度(公里)景点游玩时间(天数)路线总长度(公里)第一组[乌鲁木齐]—天山—阿勒泰—克拉玛依—[奎屯市]—[天鹅湖]—[库尔勒]—楼兰罗布泊—[库尔勒]—吐鲁番—哈密—[吐鲁番]—火焰山—[吐鲁番]—[乌鲁木齐]3059205530第二组乌鲁木齐—奎屯市—石河子—博乐—伊犁-天鹅湖—库车—阿克苏—[库车]--库尔勒-[乌鲁木齐]247124分析以上分组所得路线可知:对于分组一:路线总长度27 301001不均衡度对于分组二:路线总长度不均衡度虽然按照分组一的行程分布不均衡度较大,但考虑到主要因素路线总长度按分组一较短,故可认为按照分组一的行程安排相对较优(1)分析方法二:方法一是将此问题模拟为多个推销员的最佳推销员回路问题,先分组然后再在每组内采用TSP方法,在此我们也可以采用先整体找出最佳推销员回路,然后再在恰当的地方将路径分段,从而得到较优的行程安排对整体采用TSP分析法,找出最佳推销员回路如下:乌鲁木齐—吐鲁番—哈密—[吐鲁番]—火焰山—[吐鲁番]—库尔勒—楼兰罗布泊—[库尔勒]—库车—阿克苏—[库车]—天鹅湖—伊犁---博乐--奎屯市--克拉玛依—阿勒泰—天山--[乌鲁木齐]于是我们在整条路径距离出发点最近的点(奎屯市)将它分开,分成如下两条:乌鲁木齐—吐鲁番—哈密—[吐鲁番]—火焰山—[吐鲁番]—库尔勒—楼兰罗布泊—[库尔勒]—库车—阿克苏—[库车]—天鹅湖—伊犁---博乐--奎屯市--[乌鲁木齐][乌鲁木齐]—奎屯市--克拉玛依—阿勒泰—天山--[乌鲁木齐]其中0.6mm粗线线表示整体最佳推销员回路,0.3mm细线线表示路径分割点分组三:旅游时间分组路线路线长度(公里)景点游玩时间(天数)路线总长度(公里)第一组[乌鲁木齐]—吐鲁番—哈密—[吐鲁番]—火焰山—[吐鲁番]—库尔勒—楼兰罗布泊—[库尔勒]—库车—阿克苏—[库车]—天鹅湖—伊犁---博乐—[奎屯市]--[乌鲁木齐]3525284820第二组乌鲁木齐—石河子—奎屯市--克拉玛依—阿勒泰—天山--[乌鲁木齐]12951627 301001在分组三情况下,各评价参数如下:路线总长度不均衡度显然综合上述三类分析,第三种旅游路线安排下,总的路线长度会最小,但同时造成了两次游玩时间和旅途不均衡,由于问题二仅出于对交通费用(即总的行程)的考虑,要求总的交通费用最少,所以分组三所安排的旅游线路更能满足题目所给要求二．问题三专家分三组考察尽早完成任务分析可知,该考察团将全面考察新疆境内,因此对于第二问忽略的偏远地带也将纳入行程范围,由于所有考察地所花费总时间一定,所以解决该问题的首要任务是,如何尽量均衡的将考察时间划分为三组所有旅游景点推荐总天数所有考察总天数分成三个考察小组,每个小组的大致考察天数约为现在尝试着将所有景点分为三组,分组原则除了遵守准则一之外,还应遵守一下准则:准则四:尽量使每组考察天数相等分组完成后,仍可按照问题二中的近似最佳推销员回路来确定考察每组行程,说明:图中不同线粗表示不同分组的路线及所考察的景点,中央细线表示至少两组之间的公用线路,其中的景点按需分配三组考察分配方案如下:旅游时间分组路线路线长度(公里)景点考察时间(天数)27 301001第一组乌鲁木齐—吐鲁番--哈密—[吐鲁番]—火焰山—[吐鲁番]—库尔勒--楼兰罗布泊—[库尔勒]--[乌鲁木齐]2164第二组[乌鲁木齐]—天山--阿勒泰—克拉玛依—奎屯市—博乐—伊犁—天鹅湖—[奎屯市]--[乌鲁木齐]2038第三组[乌鲁木齐]—[库尔勒]—民丰—和田—喀什—阿克—库车—[天鹅湖]—[奎屯市]—石河子—[乌鲁木齐]3783路线总长度考察时间不均衡度考察路程不均衡度由于该问题侧重于时间上的均衡要求,故对于路程上的差异较大,可以不予考虑,可能的原因是,南疆地区地处偏远,无法在路程上予以调和,此外三组考察团各自所用时间均接近于理论平均时间,所以该考察路线的安排能较好的满足题目所给要求3.问题四一、问题分解1．满足游客需求2．自治区接待能力3．路径合理二、满足游客需求[8][9][10][16]1.问题分析作为自治区吸引游客，满足其需求的首要条件是使其满意，但是满意度的衡量是一个复杂的问题，不同的消费者会有不同的消费倾向，而且为其带来最大化的满意度的产品组合也是不同的。在这里我们引入对游客进行分类，并且引入效用的概念。效用是经济学中衡量消费者满意程度的概念，不同的游客作为品位不同的消费者会有其自身的效用函数，而不同的旅游地点也会有不同的效用提供曲线。在这里我们对新疆旅游进行汇总，把游客选择去新疆旅行的影响因素统计分类为五个因子(Factor)：（统计过程略）ü历史、文化影响(History)—如题目中王先生夫妇受历史、人文等因素影响ü物质美感追求(Scenery)—是多数中产层选择去新疆的主要原因，当地的安全和民族冲突等因素作为该乡的负项因子ü刺激(Innovation)--新疆特有的地理地貌，罗布泊、楼兰等地的探险性质的动因ü放松休闲(Relaxation)—以景观、美食为正因数，安全、长途交通等与支负相关ü简约时尚(Expense)—主要以支出为负相关因子与五种因子相关，假设自治区推出了五种路线：掩卷访古，皇室特尊，心跳达人，休闲一派，简约时尚2.解决问题1)方法阐释：正如前所述，不同的又可有不同的取向和效用函数，不可以一概而论，而且作为一个主观度的描述我们需要建立定量的逻辑分析，在这里应用模糊数学中层次分析AnalyticalHierarchyProcess27 301001（AHP）的方法建模，将一种定性与定量分析相结合的多目标决策分析方法结合。吸收利用行为科学的特点，是将决策者的经验判断通过统计给予量化，可以克服本问题对目标（因素）结构复杂而且缺乏的困难。1)层次划分：游客效用历史美感刺激放松节约P1P2P3目标层准则层方案层2)构造判断矩阵（以下建模以“心跳达人”为例）：通过权重比较，建立矩阵，其中表示第i项因素相对于第j项因素的重要性，以1为界限，大于1表示i比j重要，小于1反之，采用1-9的数值标度，建立判断矩阵如下：判断矩阵是通过旅游者的主观评价给出的标度，可能有些时候并不一致，比如该局正应当满足：，且，可是事实上旅行者却有可能给出不一致的数值，因此需要将其一致化。3)判断矩阵一致化定义：设有正互反成对比较矩阵：除满足：（i）正互反性：即27 301001而且还满足：（ii）一致性：即则称满足上述条件的正互反对称矩阵A为一致性矩阵，简称一致阵。我们考察一致性矩阵（一致阵）性质：性质1：的秩　Rank(A)=1的唯一非0的特征根为n性质2：的任一列（行）向量都是对应特征根的特征向量：即有(特征向量、特征值)：，则向量满足：即：　　可知一致矩阵的含义：件物体，它们重量分别为，将他们两两比较重量，其比值构成一致矩阵，若用重量向量右乘，则A的特征值为n，以n为特征根的特征向量经归一化后就表示诸因素对上层因素的权重。心跳达人的正互反对称矩阵：，特征向量：27 3010011)一致性检验，，当CR<0.1时成为该矩阵满足一致性。在这里，我们计算的，通过检验。2)准则层正互反成对比较矩阵建立（仅以费用因素为例）。求解各景点在同一因子之下相比较的权重判断矩阵一致性比例：0.0455;对总目标的权重：0.1772费用因子克拉玛依哈密石河子乌鲁木齐伊犁罗布泊吐鲁番喀什民丰火焰山Wi克1.00005.00002.00002.00002.00000.25003.00003.00001.00000.25000.1130哈0.20001.00000.33330.33330.25000.20000.25000.25000.12500.11110.0207石0.50003.00001.00001.00001.00000.33330.50000.50000.33330.25000.0524乌0.50003.00001.00001.00001.00000.33330.50000.50000.33330.25000.0524伊0.50004.00001.00001.00001.00000.33330.50000.50000.33330.25000.0540罗4.00005.00003.00003.00003.00001.00000.50002.00001.00001.00000.1553吐0.33334.00002.00002.00002.00002.00001.00001.00000.50000.50000.0979喀0.33334.00002.00002.00002.00000.50001.00001.00000.50000.50000.0852民1.00008.00003.00003.00003.00001.00002.00002.00001.00001.00000.1628火4.00009.00004.00004.00004.00001.00002.00002.00001.00001.00000.2062同理，可以得到其它几种准则因子在“心跳达人”的效用取向之下各景点的权重3)计算组合权并排序由公式计算“心跳达人”的决策结果4)同理，计算所有线路的组合权并列表如下各线路景点组合结果备选方案（天数）掩卷访古皇室特尊心跳达人休闲一派简约时尚火焰山（1天）0.11690.10490.11220.10140.1050罗布泊（4天）0.03330.05210.05500.03770.0300石河子20.07730.11670.13740.09770.0773民丰20.05710.09740.09660.06830.0613伊犁30.05230.09610.09880.05170.0514哈密30.15100.09020.07750.14490.1513克拉玛依30.06840.05060.05470.04730.0678喀什20.08270.11140.11260.08450.0842乌鲁木齐30.16120.16610.16250.17450.1706吐鲁番30.19980.11450.09270.19210.201227 3010011)遴选出各路线符合条件的景点游客根据自己的消费倾向，按照权重配比由高到低的顺序，按照建议天数，决策出最佳方案。一、满足自治区接待能力[11][13]1.问题分析上表中黑体字表示为仅仅由游客进行自行选择而得到的方案，我们可以看出：1)景点选择比较分散，基本不会造成特别大的旅游压力。2)由于旅行者的权重配比真实度较高，乌鲁木齐作为交通要塞被所有旅行者选中，也验证了我们在前几问对所有游客做过的强约束的有效性。3)但是仅仅由游客进行自我选择也呈现出了一定的不均衡性，使得克拉玛依无人光顾，也使火焰山旅游环境压力过大，因此作为宏观规划者，旅游当局必须在尽量满足游客效用和意愿的情况下进行一定量的分散补偿。2.解决问题1)方法阐述：完全有游客决策的线路是完全的自组织过程[12]，理论上，游客与游客之间在动态博弈中可能达到长期均衡。但是往往由于信息的不充分还会造成某些拥塞，正如表格所示，在很多人选择出游的情况下，线路承载量因素不是一个可以提前预计并设置合理权重的变量，需要由合理的宏观规划来快速有效地解决。考虑不在经典线路之内的大量零散游客仍存在自组织行为，也就是存在着弱的反馈机制，只有少数几个连接全影响网络的输出，因而建立以某个局部区域为输入空间的径向基函数神经网络模型。RBF网络(RadialBasisFunction)具有从局部逼近网络，学习速度快的优点。2)符号及假设约定旅游路线方案集，对应前述五种旅游路线，实现了游客满意度达标的目的，以组合权衡量其优劣。旅游目的地集J={1,2,3,…,9,10}，对应十个景点，要求利用度不超标。根据题目总人数与线路数量正相关的条件以I集合中队起访问总量来度量。同时还可以建立访问矩阵，表示方案集I中元素对目的地集J中元素的访问。为取值为0，1的布尔值，0表示I方案中不包含j地点，1表示I方案中包含j地点。以旅游景点的资源耗用量为目标函数，考虑到实际旅行情况，仍规定乌鲁木齐为必经景点，且所有景点时间均为两天，即所有线路均为乌鲁木齐和其余五个景点的组合，目标函数简化为。3)模型框图27 301001nnn输入层隐含层输出层和常规的线性加和的多目标规划函数不同，这个模型之下考虑了散客或是推荐路线中很多游客的混沌行为对交通和景点资源带来的压力，因此添加了作为RBF网络中隐含层节点的输出，作为无量纲系数，对总体规划方案起到了修正和进一步仿真作用。的计算式为式中，称为第j个高斯基函数的尺度因子，（j=1,2,3,…,9）称为第j个高斯基函数的中心值，即某地在五种不同人群中的平均评价权重，是第j个隐含层节点的输出，建立最终目标函数，其实际意义是某地资源的利用度，求最小值即可。建立约束条件：，实际意义是旅行者的效用要达到完美尺度的一半以上。考察目标函数和约束条件，改变参数，使用递归算法进行局部调整后得到如下线路：各线路景点组合结果备选方案掩卷访古皇室特尊心跳达人休闲一派简约时尚火焰山0.11690.10490.11220.10140.1050罗布泊0.03330.05210.05500.03770.0300石河子0.07730.11670.13740.09770.0773民丰0.05710.09740.09660.06830.061327 301001伊犁0.05230.09610.09880.05170.0514哈密0.15100.09020.07750.14490.1513克拉玛依0.06840.05060.05470.04730.0678喀什0.08270.11140.11260.08450.0842乌鲁木齐0.16120.16610.16250.17450.1706吐鲁番0.19980.11450.09270.19210.2012一、最佳路径规划[14]1.问题分析[15]：最终遴选出来的景点数目不多，是小规模的路径规划问题，因此不适合使用网络算法或是模拟退火等复杂的算法，也不需要大规模编程计算。因此我们通过二叉树丛局部到整体的自下而上的局域迭代优化的方法来进行求解。2.解决问题1)二叉树建模分析：游客旅游时为达到尽量缩短路程的目的，凭经验一般会这样确定旅游路线：一旦决定去一个地方，譬如乌市，那么乌鲁木齐及其周围的各个旅游景点就是一个Package，从旅游者的角度来说，为到达乌鲁木齐而花去的大量费用作为机会成本或影子价格就会作为大量的沉淀成本，是它在旅游区内行为带有很多非理性色彩。因而考虑到实际情况，旅行者在同一旅游区内各项费用就没有单独计算的意义，所以我们将距离较近的旅游点分为旅游区，把这一区间内的费用，包括住宿，餐饮，门票，市内交通，旅行纪念品，甚至保险统一打成一个黑箱的包裹，具体的旅行行程中，可能会由单项费用的增减，但是这一个黑箱模型之内，由于各项费用相互制约和均衡及旅行者自我的调整，对于长途行者来说，是不大具有可变动的余地的。在各景点分成最基本的景区之后，应用同样的思想，我们可以把变量再次确定化，用可以继续扩大，从而形成由底向上的递归方法。当然这种递归不可能是一圈圈毫无差异的扩大，否则这种递归也将失去它的科学价值，再加上边界条件和约束条件的限制，这种递归不会成为宇宙大爆炸式盲目的“圈地运动”。然而，旅行者的分析过程明显可以归结为二叉树的层次关系，因此在下面我们也暂不进行严格的数学论证，只给出二叉树建模的过程。2)模型阐述：用表示景点i到景点j的距离，n个地点之间存在着距离矩阵（邻接矩阵），为结点的权。点之间存在双行路线，即，距离矩阵为对称阵同之前三问一样，问题又抽象为从乌鲁木齐出发，对各景点遍历且使闭合路径最短。于是这个旅游路线问题的有效解为这个元素的一个循环排列：。即树的带权路径长度(WeightedPathLengthofTree)，WPL=最短。定义为树中所有叶结点的带权路径长度之和建立最优解的目标函数，就是寻找一个C，使得f(C)最小。求解过程也就是Huffman二叉树的构造过程。27 301001选取邻接矩阵中最小的项，将a，b景点合并，记做结点，根据距离公式，重新计算，，并改写矩阵，依此类推，直至矩阵变为一个数字，其下标的编码便是最佳顺序。，，将2，6和并为结点，并产生新的距离矩阵，再逐次生成结点，，，，考虑到矩阵是以无向图为基础得到的双向循环序列，并结合实际情况，以乌鲁木齐为出发点，重组顺序为，即乌鲁木齐石河子民丰喀什伊犁火焰山乌鲁木齐同样得到其他几条线路的推荐游程，利用MicrosoftVB.Net编程并计算得到结果，列表如下：备选方案推荐线路掩卷访古乌鲁木齐克拉玛依喀什火焰山哈密吐鲁番乌鲁木齐皇室特尊乌鲁木齐吐鲁番民丰伊犁喀什石河子乌鲁木齐心跳达人乌鲁木齐石河子民丰喀什伊犁火焰山乌鲁木齐休闲一派乌鲁木齐吐鲁番哈密火焰山伊犁石河子乌鲁木齐简约时尚乌鲁木齐哈密火焰山喀什民丰克拉玛依乌鲁木齐4.2模型二遗传算法的求解27 301001根据第一小题的结果，我们发现，如果以与之前相同的出行方式显然不能在一个月之内遍历所有的20个景区，但是，在引言部分，我们也计算出，遍历所有景区与往返景区路途中的总时间是45.18天，这说明分两个月完成游览是完全可以的。由于两个月之内，我们会遍历所有的景区，所以在景区上的开支是恒定的，所以，如何安排两个月所分别游览的景区，使交通费用最省也即是使总费用最省。受第一小题的启发，我们依然想到运用遗传算法进行求解。选择、交叉、变异函数不变，适应度函数定义为两次游览的总交通费用的倒数，这样，用于交通的费用越少，适应度就越高，个体就越能遗传到下一代。由于景区总数只有20个，所以，我们下面采用一种分类遗传的方法，这样可以使结果更精确也可以使计算效率提高。做法是：将20个城市分为两部分，第一个暑假考察N个景区，第二个暑假考察20-N个景区，N从3开始到17（如果N小于3的话会导致不满足约束条件，即出现一个暑假游览所花费的时间大于30天），同时考虑到乌鲁木齐是省会，很多游览天山、昌吉等景区的旅行线路都是以乌鲁木齐为出发点的，所以为更切合实际，在这里我们也要求第一个暑假从乌鲁木齐出发（当然，这不是必要条件，我们后面采用的方法即不需要满足此条件）。对每一个给定的N用一次遗传算法。最后将每个N对应的交通上花费的时间作比较，我们发现，N从7到13所花费的时间较其他更少一些，故，作的柱状图如下：（图5：景区数量安排与耗时关系图）模型的结果与分析：从上图的结果，我们可以看到：当两个月各访问10个景点，并且按照我们列出的顺序访问，路上时间最少，而路途耗时与交通费几乎成正比，从而交通费也最省。我们给出一组最优线路：第一个暑假78654910132第二个暑假1211141315171820191627 301001遗传算法的效果和求解能力都能达到我们所期望的，但是对于这一问题固有的特性，我们也可以直接从图的角度来建立模型：2.2从图的角度直观求解两次暑假遍历所有的景区，也即是将原来20个景区的连通图分割成两个子图，并找出两条互不重叠的旅游路线。针对问题的特殊性，我们分如下几步来处理问题：第一步，不断地剪去图中所有度为1的顶点，即编号为：2、8、9、11、12、16、19的点（11是因为剪去12后它成为了度为1的顶点）。因为我们参观这类景区的时候，进出必然沿同一条线路，花费在这些路上的时间是不可缩减的。所以，在我们的最节约时间方案中一定会包含这些路径，故寻找最短路径的时候可以暂时将其从图上去除。第二步，我们将度为2的顶点去除，但保留原来的路，即编号为：1、4、6、15、17、18、20的点。原因与第一步类似，因为对于这类顶点，一般来说，游览它们的时候，是从顶点的一条边进入而从另一条边离开，所以，通过这类顶点的路径也是确定的，对我们所需要寻找的最短路径不会产生影响，可以暂时将其从图上去除。执行这两步之后，得到如下结果：（图6：简化后的景点图）我们发现，余下的顶点的度数都大于等于3。我们把被去除的顶点“附属于”某一个度数大于等于3的顶点，即如果我们到达某个顶点x，我们就要遍历它的“附属”点。要分割原先的图，并找出不重叠的两条路线就要选择如何分割这些度数大于等于327 301001的顶点。模型的结果与分析：由于数据量较少，我们用枚举的方式得出了五种较为合理的分组方式。分组情况一情况二情况三情况四情况五Group11—101—12、141—81—8、11、12、141—6、9、10Group211—2013、15—209—209101315—207,8,11—20情况一：Group123178654109Group212111413151718201916情况二：Group121391045678141112Group213151718201916情况三：Group123187654Group212111413109151718201916情况四：Group121345678141112Group291013151718201916情况五：Group1213564109Group21211147813151718201916由上面五组游览方案，我们分别计算它们的游览时间以及所需的路费，可以得到如下表的结果：单位（小时）情况一情况二情况三情况四情况五Group157.37107.0345.1791.8953.41Group2103.364.15126.5176.95130.75总时间160.7171.18171.68168.84184.16价格（元）一二三四五Group1292.3573.4220.1511.8270Group2694.3465.9845.7541.6841.3Sum986.61039.31065.81053.41111.3由上表，我们发现，情况一中所消耗的时间最短，所需的费用相应也最少。因此，我们认为，安排两个月的旅游线路最佳的分配方式由情况一的分组给出，具体的线路图可以表示如下：27 301001（图7：最佳线路安排图）五、模型评价与改进5.1模型的优点1、本文以规划模型为基础，以遗传算法作为求解工具，既取了规划模型的优点，即目标函数与约束条件的意义都十分清晰，而辅之的遗传算法又克服了线性规划由于变量过多而导致的计算效率下降等问题，从而使每一个模型基本上都能得到最优解。2、本文使用的模型和方法较为广泛，前三个问题都建立了两个模型或使用了两种方法，这样既丰富了文章的内容，也通过模型之间的相互比较和互相结合更好地完成了要求的任务。3、对于第四问，我们提出的算法思路不仅求得了多条黄金周旅游线路，同时还给出了一些有价值的短程游路线。加入这一完善结果，可以更充分地利用各景区的旅游资源，而且也同时满足了更多游客，让具有不同旅游需求的游客都可以领略新疆绚丽的风采，可以说取得了一种锦上添花的效果。4、本文综合运用了MATLAB、马克威分析系统、LINGO、EXCEL等多种软件，发挥其各自的特长，在提高编译和求解效率的同时，也使文章图文并茂，更直观更具有可读性。5.2模型的缺点27 3010011、本文的模型均建立在速度、单位行程的费用等都为恒定的基础假设之上，而实际上，对于不同的道路，时速以及费用都会略有波动，如果在模型中能加入一些随机因素，应该可以更接近现实生活。2、模型处理复杂问题的求解上，基本都采用了遗传算法。但是，由于遗传算法的进化是基于一定的概率，所以单纯的遗传算法有时并不能保证求得最优解，或者虽然能求得最优解却要耗费相当多的时间，而这与我们的初衷是相违背的。如果能将遗传算法与模拟退火算法、局部搜索等相结合，将会取得更好的效果。3、在第四问中我们仅考虑了错开景点旅游高峰，即仅从理性的角度分析策划了旅游线路，但没有考虑游客对各景点的偏好程度，即未加入感性的一些元素，而这些对于现实问题还是很有影响的，因此，如果将游客的一些特定需要添加到模型的约束中，将会更符合实际。4、本模型第一步对景点进行了聚类，这样在为后面的分析带来了许多方便的同时，也造成了一旦选择游览某个景区也即游览了此景区的所有景点的约束。而事实上，尤其是在一条线路旅游的最后阶段，有可能出现时间上不允许游览某个景区，但却足够游览一两个景点的情况。而我们的模型会直接将整个景区排除，这是我们线路设计模型的一个略有不足之处。5.3模型的改进与推广模型的建立还可以进一步考虑诸如：旅游景点的旅游时间不固定，两景点间可以选择多种交通方式（如坐汽车或坐飞机）等情形；此时将需要考虑一个权值不断变动的“变权图”，本小组曾经试图通过动态规划（DP）方法求解“变权图”中的最优解，但得到的DP算法复杂度极高，也曾考虑将DP方法简化为网络流（可变流）模型，但由于我们的时间有限，简化算法尚不成熟。模型中的算法也还有改进空间。我们使用的近似算法虽然已经得出非常好的结果，但仍可进一步考虑与其精确解的结合，如将近似最优解作为分枝定界法中的上界，使分枝定界法大为化简后求解，从而得到精确解。进一步的，如能给出灵敏度分析和误差分析，就将更为完善。对模型进行一些适当改动，便可推广到诸如清洁车的街道清扫、公安执勤人员的最优巡视路线、教师任课班级负荷分配、流水作业生产线的顺序安排等实际问题。参考文献：[1]张超，杨奕，李嵩，关于灾情巡视路线的模型：1～3页，1998。[2]耿素云，集合论与图论，北京：北京大学出版社，1998。[3]边馥萍，侯文化，梁冯珍，北京：高等教育出版社，2005。[4]赵静但琦,数学建模与数学实验,高等教育出版社,2001;[5]熊伟,运筹学,机械工业出版社,2004;[6]杨庭栋,李哓涛,郑长江,最佳灾情巡视路线的数学模型[7]搜狐旅游频道http://diy.travel.sohu.com/provinces[8]彭小云，宫治国，折学森，姜盈霓，地基处理方案优选的可拓层次分析法，长安大学学报（自然科学版）2006年11月第26卷第6期[9]蒋欣，钱瑜，张玉超，陆根法，层次分析法在规划环评中的应用[10]黄智星,夏富春，模糊层次分析法在区带勘探，内蒙古科技与经济，2004[11]成金华，肖荔瑾，诸克军，生物基因最短路径模型分析，大庆石油地质与开发，第17卷第1期，1998年2月[12]王安麟，复杂系统地分析与建模：上海，上海交通大学出版社，2004年，158页[13]栗雪娟，崔尚森，张柯，最佳旅游路线选择的神经网络方法，交通与计算机2006年第5期第24卷27 301001总132期[14]任刚，王炜，交通网络最短路权矩阵的迭代算法交通与计算机2005年第5期，第23卷(总第126期)[15]陆锋，最短路径算法：分类体系与研究进展，测绘学报第30卷第3期，2001年8月[16][日]田村坦之，系统工程，北京：科学出版社，2001附录：1、新疆境内的33个旅游景点名称及其相应的观光逗留时间，经、纬度如下表所示：序号景点名称景点观光时间经度纬度1哈纳斯湖187.248.22额尔齐斯河0.586.947.83阿勒泰188.1547.866674塔城182.9666746.755克拉玛依0.584.7666745.66怪石沟18345.27博尔塔拉281458博乐182.144.933339石河子185.9544.2666710昌吉187.244.211乌鲁木齐1.587.6833343.7666712天山188.443.713伊犁181.843.914昭苏边境的乾隆格登碑0.58143.215吐鲁番189.242.916哈密193.442.817巴音布鲁克天鹅湖0.584.143.118火焰山0.590.243.619回王陵192.743.820克孜尔千佛洞0.582.741.821库尔勒0.586.0666741.6833322博斯腾湖0.586.5333341.9523阿克苏180.241.124库车大寺0.582.941.625罗布泊490.441.626楼兰688.841.627苏丹·沙图克麻扎0.2575.939.628阿图什0.7576.1166739.7333329喀什175.939.430香妃墓0.576.239.527 30100131艾提尕清真寺0.575.939.232尼雅遗址682.63833和田179.937.12、景点间最短路矩阵：T=[0.0021.006.7315.979.9012.0211.0312.9718.9113.7121.000.0014.2723.5117.4419.5620.6322.5726.4521.256.7314.270.009.243.175.296.368.3012.186.9815.9723.519.240.006.078.199.2611.2012.207.009.9017.443.176.070.002.123.195.1315.3510.1512.0219.565.298.192.120.001.073.0117.4712.2711.0320.636.369.263.191.070.001.9418.5413.3412.9722.578.3011.205.133.011.940.0020.4815.2818.9126.4512.1812.2015.3517.4718.5420.480.005.2013.7121.256.987.0010.1512.2713.3415.285.200.0047.2656.8642.5945.4939.4237.3036.2338.1744.0141.2352.8162.4148.1451.0444.9742.8541.7843.7249.5646.7821.3128.8514.5814.6017.7519.8720.9422.8810.387.6026.0635.6621.3924.2918.2216.1015.0316.9722.8120.0328.9636.5022.2322.2525.4027.5228.5930.5318.0315.2551.3460.9446.6749.5743.5041.3840.3142.2548.0945.3135.9843.5229.2529.2732.4234.5435.6137.5525.0522.2736.5844.1229.8529.8733.0235.1436.2138.1525.6522.8737.4947.0932.8235.7229.6527.5326.4628.4034.2431.4639.1448.7434.4737.3731.3029.1828.1130.0534.3231.5447.2652.8121.3126.0628.9651.3435.9836.5837.4939.1456.8662.4128.8535.6636.5060.9443.5244.1247.0948.7442.5948.1414.5821.3922.2346.6729.2529.8532.8234.4745.4951.0414.6024.2922.2549.5729.2729.8735.7237.3739.4244.9717.7518.2225.4043.5032.4233.0229.6531.3037.3042.8519.8716.1027.5241.3834.5435.1427.5329.1836.2341.7820.9415.0328.5940.3135.6136.2126.4628.1138.1743.7222.8816.9730.5342.2537.5538.1528.4030.0544.0149.5610.3822.8118.0348.0925.0525.6534.2434.3241.2346.787.6020.0315.2545.3122.2722.8731.4631.540.005.5533.6321.2041.2846.4843.5542.9532.6334.285.550.0039.1821.2046.8352.0349.1048.5038.1839.8333.6339.180.0012.437.6537.7114.6715.2723.8623.9421.2026.7512.430.0020.0825.2822.3521.7511.4313.0841.2846.837.6520.080.0045.367.027.6221.0716.2946.4852.0337.7125.2845.360.0045.4944.8935.4336.2243.5549.1014.6722.357.0245.490.000.6014.059.2727 30100142.9548.5015.2721.757.6244.890.600.0013.458.6732.6338.1823.8611.4321.0735.4314.0513.450.004.7834.2839.8323.9413.0816.2936.229.278.674.780.00]。27