《C 数学建模旅游问题上交》由会员分享，可在线阅读，更多相关《C 数学建模旅游问题上交（22页珍藏版）》请在金锄头文库上搜索。
1、安徽工程大学安徽工程大学 数学建模数学建模 课程设计论文课程设计论文C 最佳旅游路线设计最佳旅游路线设计姓名： 李 阳班级：数学 112学号：3110801221指导老师：指导老师： 周金明周金明 成成 绩：绩： 完成日期：完成日期： 2013 年年 7 月月 3 日日摘 要旅旅行行商商问问题题，即即 TSP 问问题题（Traveling Salesman Problem）是是数数学学领领域域中中著著名名问问题题之之一一。假假设设有有 一一个个旅旅行行商商人人要要拜拜访访 N 个个城城市市，他他必必须须选选择择所所要要走走的的路路径径，路路径径的的限限制制是是每每个个城城市市只只能能拜拜访访一
2、一次次， 而而且且最最后后要要回回到到原原来来出出发发的的城城市市。路路径径的的选选择择目目标标是是要要求求得得的的路路径径路路程程为为所所有有路路径径之之中中的的最最小小值值。 其实际问题的约束条件复杂，目标函数多样，问题的特殊性使其甚至不具有最优算法。本文其实际问题的约束条件复杂，目标函数多样，问题的特殊性使其甚至不具有最优算法。本文 则运用多种方法多角度对这一问题进行了建模及求解。第一问从传统的图论解法开始，通过则运用多种方法多角度对这一问题进行了建模及求解。第一问从传统的图论解法开始，通过 无向图的无向图的 HamiltonHamilton 回路建模，使用回路建模，使用 Dijkstr
3、aDijkstra 的改进算法将问题转化为单目标的非线性规划的改进算法将问题转化为单目标的非线性规划 函数并得出了单一旅行商的问题。第二、三问仍从图论入手，基于最小生成树用两种方法共函数并得出了单一旅行商的问题。第二、三问仍从图论入手，基于最小生成树用两种方法共 同建立出模型。第四问的求解跳出传统的算法框架，借用经济学中消费者效用的概念从旅行同建立出模型。第四问的求解跳出传统的算法框架，借用经济学中消费者效用的概念从旅行 者的角度出发，先运用模糊数学的层次分析法（者的角度出发，先运用模糊数学的层次分析法（AHPAHP）将复杂的满意度的主观评价问题定量）将复杂的满意度的主观评价问题定量 分析，得
4、出比较分散的景点选择域。考虑到游客在消费博弈中的自组织行为和政府规划的管分析，得出比较分散的景点选择域。考虑到游客在消费博弈中的自组织行为和政府规划的管 制效应，建立局部反馈的制效应，建立局部反馈的 RBFRBF 神经网络模型通过迭代对景点选区进行优化。最后运用神经网络模型通过迭代对景点选区进行优化。最后运用 HuffmanHuffman 二叉树对景点进行路性组织，得到适合于不同品味人群的五条路线，同时还分散了二叉树对景点进行路性组织，得到适合于不同品味人群的五条路线，同时还分散了 游客对环境和资源的压力。模型的建立过程中从浅入深，虽然还存在很大改进余度，但已逐游客对环境和资源的压力。模型的建
5、立过程中从浅入深，虽然还存在很大改进余度，但已逐 步摒弃了传统步摒弃了传统 TSPTSP 问题中对游客刚性的、理性的、线性的行为假设，还原了社会生活中柔性问题中对游客刚性的、理性的、线性的行为假设，还原了社会生活中柔性 的、非线性，非理想的行为人模式，具有很强的现实价值和拓展前景。的、非线性，非理想的行为人模式，具有很强的现实价值和拓展前景。关键词：关键词：TSPTSP 问题问题 多目标动态优化多目标动态优化 最短路径最短路径 HamiltonHamilton 回路回路 最小生成树最小生成树 主观评价主观评价 层次分层次分 析法析法 RBFRBF 神经网络神经网络 最优二叉树最优二叉树 非线性
6、非线性一一. .问题的重述问题的重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。受文学作品的影响，天池、达坂城、 吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。 Q1请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多 的地方，并估算除吃饭之外的费用。 Q2如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新 疆境内的交通费用尽量地节省。 Q3如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和 前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们
7、设计合适的考察路线，以便尽早完 成考察任务。 Q4新疆自治区旅游部门为迎接“五一旅游黄金周” （考虑到远途旅游，自治区内游程延长为十二天） 准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路 线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备 向游客推介的全部旅游路线。二二. .问题的假设问题的假设1 模型假设及分析 （1）所有景区、景点均为节点。 （2）假设个旅游景点之间用同样的汽车作为交通工具，并且单位路程的交通费相同（均为 0.10 元） 。 （3）只考虑不同景点间公路的连接，将公路作为节点之间的通路。在简化
8、过程中，优先考虑主要公路。（4）汽车发车时间连续，行驶时间不单独计算，不考虑交通中的意外。 （5）考虑仅乌鲁木齐有全国班机通航，规定游客的旅行起止都是从乌鲁木齐 2 问题初步分析 根据图中给出的各景点的分布情况，结合所搜集的信息，将位于主要交通线路上的、知名度高的景 点作为重要景点，并简化为算法中的节点。结合实际情况，从上海出发到新疆，则旅游起点只能为乌鲁 木齐，因此将乌鲁木齐设为中心节点。在根据所查得的景点和景区间的距离，对题目所给交通图简化如 图 1-1。图中连线表示各地之间的公路，数字代表路程（单位为 KM） 。图 1-1三问题一三问题一一、问题分解：1.以旅游景点逗留的天数作为自变量，
9、以单位天数所用的钱为目标函数，取最小值。ptPpM t2.选择最优巡回路，我们参考了如下两个定义： 巡回路：过各个节点，每个节点至少经过一次的回路。 哈密尔顿回路：每个节点只经过一次的回路。 总长度最小的巡回就是最优巡回路。 最优巡回路和最优哈密尔顿回路在如下条件下是等价的；定理：定理：回路中，任 2 个节点，若能满足下列三角不等式：,G V E W,ijV VijikjkWWW,;ijkkikjijV V VV VV VV VV则最优巡回路与哈密尔顿回路相同。 理论模型建立的基本思想是：首先，对于任意一个无向网络，利用任意节点之间的最短路算法构建一个等价网络,G V E W，在网络中个节点之
10、间的距离用最短路代替。据此，解得的最优哈密尔顿0000,G V E W0000,G V E W回路就可以很方便的还原为最优巡回路，实质是 TSP 问题。而解最优哈密尔顿回路的方法可以才用最优 二叉树法（参考书164 页） 、DijKstra（见参考书2336 页）法等。解 TSP 问题也有相应的软件求解，更 为方便。 基于以上对问题 1 的分析，要解决问题 1 的关键在于每种旅行路线方案的最优解的获得，而获得最 优解的关键则在于确定网络的最优巡回路。第 1 步 将图变换为。,G V E W0000,G V E W第 2 步 为方便表示，将图中各节点进行编号如表 1-1编号景区（景点） 名称编号
11、景区（景点） 名称A乌市K天鹅湖B石河子L喀什、香妃 墓C伊犁M和田D天池N民丰E吐鲁番O博乐F火焰山P楼兰、罗布 泊G哈密Q阿勒泰H库尔勒R克拉玛依I库车S奎屯市J阿克苏K天鹅湖表 1-1第 3 步 根据达坂城（位于乌鲁木齐） 、天池、 、吐鲁番、楼兰古城、伊宁五个点组成的网络求其完备图，其中任意两点间的最短距离可表示如表 1-2：A AC CD DE EP PA A0 05805801831837557554242C C5805800 0763763889889622622D D1831837637630 0590590225225E E7557558898895905900 079779
12、7P P42426226222252257977970 0表 1-2 第 4 步 求解最优哈密顿回路，此处应用 WINQSB 软件中的 Networking model 模块求解得Solution for 5 place: Minimization (Traveling Salesman Problem) From Node Connect ToDistance/CostFrom NodeConnect ToDistance/Cost 1 AC580 4DP225 2 CE889 5PA42 3 ED590 TotalMinimal TravelingDistance or Cost=2326
13、 (ResultfromBranchand BoundMethod) 即最优哈密尔顿回路为：ACEDPA 即：乌鲁木齐伊宁楼兰古城吐鲁番天池乌鲁木齐 其最短距离为 2326 KM。 仅对此五个地点进行游览，则有：，116345116345140120901201500.1 2326minttttt ttttt 116345116345 t1=4;t2=1;t3=4;t4=4;t5030. .030(P=1,16,3,4=,5,)4;ppttttttttttsttt 取整数至此完成了对第一组路线的建模，接下来可用 LINGO 解此非线性规划（原程序及详细结果见附录 2） ， 求得目标函数的最优解
14、。解得：Objective value=117.42 116345t =4 t =1 t =17 t =4 t =4由此可见，上述非线性规划建模的结果实质是证明了，目标函数在以下条件下成取得最优解： （1）各个景点所用的时间总和正好等于 30 天。 （2）在各景点间满足交通距离最短的前提下，应该在单位时间花费最小的景点逗留时间长，而其 余单位时间花费较大的景点只要满足推荐逗留时间即可。 根据上述结论队之前的问题1模型的假设进行修正与简化。经简化与修正后，模型可陈述如下：在一 个月的时间里，至少保证分配给以上五个地点推荐逗留时间，在剩余的时间里优先考虑离上述各景点距 离最近、单位时间消费较少的景
15、点。同时保证各景点推荐天数少于30天。 这样就不必如之前的假设一样，每加一个景点计算一次最优解。而只需选出具备上述条件的景点， 与前五个景点构成新图，求新图的完备图的，继而求其最优哈密尔顿回路，最后将所求结果回带到相应 的目标函数中。 按照上述方法求解，则： 第1步 按要求选出其余合适的点。图1-2 优先考虑达坂城（位于乌鲁木齐） 、天池、 、吐鲁番、楼兰古城、伊宁这五个点连通后沿途的点。将 选出的点与此五点组成新图，如图1-2。 第2步 求图1-2的完备图，其中任意两点间的最短距离可表示为：ABCDEFHKOPS A0160 580 42183 221 555 392 488 755 286
16、 B160 0420 202 343 381 562 232 328 915 126 C580 420 0622 736 616 518 188 247 710 294 D42202 622 0225 263 592 722 908 797 328 E183 343 736 225 038390 720 671 590 469 F221 381 616 263 380428 758 709 628 507 H555 562 518 592 390 428 0330 638 200 436 K392 232 188 722 720 758 330 0308 530 106O488 328 247 908 671 709 638 308 0838 202 P7
