C_数学建模旅游问题上交 2.docVIP

安徽工程大学 数学建模课程论文C 最佳旅游路线设计 指导老师： 成 绩： 完成日期：2013年7月3日 q 摘 要 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 一.问题的重述 王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。 Q1．请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。 Q2．如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。 Q3．如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。 Q4．新疆自治区旅游部门为迎接“五一旅游黄金周”（考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。 二.问题的假设 模型假设及分析 所有景区、景点均为节点。 假设个旅游景点之间用同样的汽车作为交通工具，并且单位路程的交通费相同（均为0.10元）。 只考虑不同景点间公路的连接，将公路作为节点之间的通路。在简化过程中，优先考虑主要公路。 汽车发车时间连续，行驶时间不单独计算，不考虑交通中的意外。 考虑仅乌鲁木齐有全国班机通航，规定游客的旅行起止都是从乌鲁木齐 问题初步分析 根据图中给出的各景点的分布情况，结合所搜集的信息，将位于主要交通线路上的、知名度高的景点作为重要景点，并简化为算法中的节点。结合实际情况，从上海出发到新疆，则旅游起点只能为乌鲁木齐，因此将乌鲁木齐设为中心节点。在根据所查得的景点和景区间的距离，对题目所给交通图简化如图1-1。图中连线表示各地之间的公路，数字代表路程（单位为KM）。 图1-1 三．问题一 问题分解： 以旅游景点逗留的天数作为自变量，以单位天数所用的钱为目标函数，取最小值。 选择最优巡回路，我们参考了如下两个定义： 巡回路：过各个节点，每个节点至少经过一次的回路。 哈密尔顿回路：每个节点只经过一次的回路。 总长度最小的巡回就是最优巡回路。 最优巡回路和最优哈密尔顿回路在如下条件下是等价的； 定理：回路中，任2个节点，若能满足下列三角不等式： 则最优巡回路与哈密尔顿回路相同。 理论模型建立的基本思想是： 首先，对于任意一个无向网络，利用任意节点之间的最短路算法构建一个等价网络，在网络中个节点之间的距离用最短路代替。据此，解得的最优哈密尔顿回路就可以很方便的还原为最优巡回路，实质是TSP问题。而解最优哈密尔顿回路的方法可以才用最优二叉树法（参考书[1]64页）、DijKstra（见参考书[2]336页）法等。解TSP问题也有相应的软件求解，更为方便。 基于以上对问题1的分析，要解决问题1的关键在于每种旅行路线方案的最优解的获得，而获得最优解的关键则在于确定网络的最优巡回路。 第1步 将图变换为。 第2步 为方便表示，将图中各节点进行编号如表1-1 编号 景区（景点）名称 编号 景区（景点）名称 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 C D E P A 0 580 183 755 42 C 580 0 763 889 622 D 183 763 0 590 225 E 755 889 590 0 797 P 42 622 225 797 0 表1-2 第4步 求解最优哈密顿回路，此处应用WINQSB软件中的Networking model模块求解得 Solutio