2011年第八届苏北数学建模联赛 承诺书 我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。 我们的参赛报名号为： 参赛组别（研究生或本科或专科）：本科 参赛队员(签名) ： 队员1： 队员2： 队员3： 获奖证书邮寄地址：
编号专用页 参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）： 竞赛评阅编号（由竞赛评委团评阅前进行编号）：
题目旅游线路的优化设计 摘要 本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。 第一问放松时间约束，要求游客游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。使用lingo编程得到最佳旅游路线为：徐州—常州—舟山—黄山—庐山—武汉黄鹤楼—龙门石窟—秦兵马俑—祁县乔家大院—八达岭长城—青岛崂山—徐州。 第二问给定时间约束，要求设计合适的旅游路线。我们建立了一个最优规划模型，在给定游览景点个数的情况下以总费用不限，时间最少为目标。再引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：徐州—恐龙园—舟山—黄山—庐山—黄鹤楼—秦兵马俑—龙门石窟—乔家大院—八达岭长城—青岛崂山—徐州。 第三问放松时间约束，要求游客在总费用低于2000元的约束下游览最多的景点。在第一问的基础上建立模型，并增加总费用低于2000元的约束。使用lingo编程得到最佳旅行路线为：徐州—常州—武汉—洛阳—西安—祁县—北京—青岛—徐州。 第四问给定时间约束，放松对总费用的约束。我们在第二问的基础上建立一个最优化模型，以时间最少为目标。再引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：徐州-常州-九江-武汉-洛阳-西安-祁县-北京-徐州。 第五问给定时间、总费用小于2000的双重约束。我们在第三问、第四问的基础上建立模型，以在规定时间内，规定总费用内，以游览最多景点为目标。使用lingo编程对模型求解。推荐方案：徐州-常州-舟山-黄山-九江-武汉-洛阳-西安-徐州 关键词：最佳路线TCP问题景点个数最小费用
最短路算法及其应用 广东北江中学余远铭【摘要】 最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围，并对其应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。 【关键字】 最短路 【目录】 一、基本概念 (2) 1．1 定义 (2) 1．2简单变体 (2) 1．3负权边 (3) 1．4重要性质及松弛技术 (4) 二、常用算法 (5) 2．1 Dijkstra算法 (5) 2．2 Bellman-Ford算法 (7) 2．3 SPFA算法 (8) 三、应用举例 (10) 3．1 例题1——货币兑换 (10) 3．2 例题2——双调路径 (11) 3．3 例题3——Layout (13) 3．4 例题4——网络提速 (15) 四、总结 (18)
【正文】 一、基本概念 1．1 定义 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并 在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？ 一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是没必要考虑的。 下面我们将阐明如何有效地解决这类问题。在最短路问题中，给出的是一 有向加权图G=(V ,E)，在其上定义的加权函数W:E →R 为从边到实型权值的映射。路径P=(v 0, v 1,……, v k )的权是指其组成边的所有权值之和： 11()(,)k i i i w p w v v -==∑ 定义u 到v 间最短路径的权为 {}{}min ():)w p u v u v v δυ→(,=∞ 如果存在由到的通路 如果不存在 从结点u 到结点v 的最短路径定义为权())w p v δυ=(,的任何路径。 在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。 边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示 时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。 1．2简单变体 单目标最短路径问题： 找出从每一结点v 到某指定结点u 的一条最短路 径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题：对于某给定结点u 和v ，找出从u 到v 的一 条最短路径。如果我们解决了源结点为u 的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。 每对结点间的最短路径问题：对于每对结点u 和v ，找出从u 到v 的最短 路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。
金华双龙洞旅游路线中最短路问题 摘要： 金华双龙洞景点分布较多，通过对其旅游路线的设置，转化为图论内容中的最短路情景进行讨论，建立模型，并通过搜索资料，利用几种方法解决路线最小的问题。 关键字： 数学建模最短路问题 lingo Dijkstra法 flod算法 一、研究背景： 在旅游过程中，我们常常感觉到自己一天下来走了很多路，回到宾 馆脚痛的不行。但其实我们可以利用运筹学的知识，通过建立数学 模型，转化为图论的内容。从而较为合理的制定出选择的路线（即 最短路问题）。 因而这次的小论文，我主要探究一下几个问题： 1.从景点进口到出口的最短路程。（最短路问题） 2.从景点到出口的最长路线。 3.建立的模型是否满足能回到起点（古典图论问题） 二、研究内容： 根据从互联网中搜索的资料，金华双龙洞的主要景点：景区进口双 龙洞，冰壶洞，朝真洞，桃源洞，黄大仙祖宫五个，其余为小景点 （若要加入，同样可以按照以下问题的研究方法进行讨论）现在忽 略。 问题总假设：分别设置双龙洞，冰壶洞，朝真洞，桃源洞，黄大仙 祖宫五个景点为A,B,C,D,E五点，根据现实及假设，可以得到如图 所示的路线图：
再利用用Dijkstra算法求解无负权网络的最短路。同时也可以利用此法算出最长路程。 问题一的解决：以A为景点出口，E为出口。 故A点标号为P（a）=0 给其余所有的T标号T（i）=+∞ 考虑与A相邻的两个顶点BC，两个顶点为T标号，故修改这两个点的标号为：T(b)=min[T(b),P(a)+l12]=min[+∞,0+3]=3 T(c)=min[T(c),P(a)+l13]=min[+∞,0+2]=2 比较所有T标号，T(c)最小，所以令P(c)=2 再考察（C,B）(C,D)(C,E)的端点：同理可得 T(b)=6 T(d)=6.8 T(e)=10.2(显然已经到终点但还需要看看其余路线长短) 故又令P（b）=6.综合分析只有一条线路即A→C→B→D→E 此时总路程为2+4+3+8.4=16.4>10.2 所以，最短路程为A→C→E。即当游客不想再看双龙洞时或者因为脚伤等因素需以最小路程离开时，可以路线A→C→E离开景区。 特殊情况的处理：游客一定要去B景点则在一开始就应该先选择 B，而非C。才能使路线最短。因此，对于特殊问题，我们应当具体 问题，具体分析。
图论及其应用 学时：40 学分：2 课程属性：专业选修课开课单位：理学院 先修课程：高等代数后续课程：无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教学目的 通过教学，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。 三、教学内容 1.图的基本概念 2.图的连通性 3.树的基本性质及其应用 4.Euler Graphs and Hamilton Graphs with Applications 5.平面图性质 6.匹配，求最大匹配算法及应用 7.图的染色及应用 8.极图理论 四、学时分配 章课程内容学时 1 图的基本概念 4 2 图的连通性 6 3 树的基本性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 匹配，求最大匹配算法及应用 6
7 图的染色及应用 4 8 极图理论 4 合计40 五、教学方式 本课程采用多媒体课堂讲授，结合实际范例深入浅出讲解讨论。 六、考核方式 本课程考核采用平时与期末考核相结合的办法，特别注重平时的考核，作业采用简单练习、论文等形式，期末考试采用简单考题或论文形式。 七、教材及教学参考书 参考教材： [1] J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. [2] 蒋长浩．图论与网络流．北京：中国林业出版社，2000． 参考书目： [1] Bela Bollobas．Modern Graph Theory（现代图论，影印版）．北京：科学出版社，2001． [2] 殷剑宏、吴开亚．图论及其算法．合肥：中国科学技术大学出版社，2003． [3] 谢金星、邢文训．网络优化．北京：清华大学出版社．2000． [4] 程理民、吴江、张玉林．运筹学模型与方法教程．北京：清华大学出版社，2000． [5] 三味工作室．SPSS V10.0 for Windows 实用基础教程．北京：北京希望电子出版社2001． [６] 孙魁明、张海彤．Mathematica工具软件大全．北京：中国铁道出版社，1994． [７] 楼顺天、于卫、闫华梁．MATLAB程序设计语言．西安：西安电子科技大学出版社，1997．八、教学基本内容及要求 第一章图的基本概念 1．教学基本要求 掌握的图的基本概念、特殊图概念，了解最短路问题。 2．教学具体内容 图的基本概念，路和圈，最短路问题。
龙源期刊网 https://www.doczj.com/doc/264949958.html, 旅游线路的优化设计 作者：陈鑫刘汗青徐常恒 来源：《科教导刊》2011年第28期 摘要本文主要研究最佳旅游路线的设计问题，在满足相关约束条件的情况下，在规定的 时间内花最少的钱游览尽可能多的景点是本设计的理想目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。 关键词最佳线路 TSP Hamilton圈综合评判 0-1变量 中图分类号：F592文献标识码：A Optimization of Tourism Route CHEN Xin, LIU Hanqing, XU Changheng (College of Mechanical Engineering, Southwest Jiaotong University, Chengdu, Sichuan 611756) AbstractThis paper studies the problem of optimal design of tourist routes, to meet the constraints related to the case, within the prescribed time to spend the least money to visit as many attractions is the ideal goal of this design. Based on this study, a mathematical model, to design the best tourist routes. Key wordsbest route; TSP Hamilton;comprehensive evaluation; 0-1 variable 随着经济的发展，人们的生活水平不断提高，旅游已成为日常生活中一项重要活动。江苏徐州的一位旅游爱好者打算今年的五月一日早上8点之后出发，到全国十个著名景点旅游，最后再回到徐州。他考虑到跟团旅游受限太大，打算自己作为背包客出游。为了让他能有一个快乐顺利的旅程，我们针对如下的几种情况，为他设计出详细的行程表，该行程表包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。 针对选取在规定时间内花最少钱游览尽可能多的景点，我们分成五个步骤来研究，先研究在时间不限的情况下或者旅游费用不限的情况下，游客将十个景点全游览完，分别至少需要多少旅游费用；再研究游客准备2000元旅游费用或者旅客只有5天的时间，想尽可能多游览景点，分别设计旅游行程表；最后综合以上的研究结果，游客在只有5天的时间和2000元的旅游费用下，想尽可能多游览景点，建立数学模型并设计旅游行程表。
一、旅游业由直接提供旅游产品和服务的主体部门、间接提供的相关部门、管理部门构成 二、旅游业的三大支柱：旅行社住宿业交通运输业 三、旅游业赖以生存和发展的三大要素：旅游资源（自然风光、历史古迹、民族习俗是经营旅游业的吸引能力）旅游设施（旅游交通、旅游住宿、旅游餐饮、旅游游乐设施）旅游服务（是各种劳务和管理行为的结合是经营旅游业的接待能力）四、旅游业的种类：旅游产业不是一个单一产业而是一个产业群由多种产业组成具有多样性和分散性包括景点经营、旅行社、餐饮服务业、交通业、娱乐业等五、旅游的形式：跟团游、自助游、半自助游、自驾游、驴友等所谓无景点旅游就是不再跟随旅行团走马观花到知名景点一游了之而是驻扎到某地随意安排行程或者在城市大街小巷闲逛，或者到乡郊野外体验民风民俗 六、旅行社赚钱方式:（1）先是低买高卖，也就是旅行社去和酒店、景区、餐厅等签下协议价然后以稍低于门前价的价格卖出去赚差价 （2）大卖场模式：旅行社通过完整的网络布点、强大的宣传攻势来达到巨大的收客量，再用这种收客量去要求酒店、航空公司、景区给予比平均协议价低的合作价格 七、旅游产品：是指旅游者以货币形式向旅游经营者购买的一次旅游活动所消费的全部产品和服务的总和 八、旅游产品的形态（1）观光旅游产品（2）文化~（3）商务~（4）度假~（5）康体~（6）业务~ （7）享受~ （8）探险~ 九、旅游产品构成分析（1）按市场营销划分：旅游产品由核心部分、外形部分和延伸部分组成(2）按劳动形式划分：旅游产品可分为以物化劳动表现的旅游产品部分、以活劳动表现的旅游产品部分和完全不包含劳动消耗的旅游产品部分（3）按消费形式划分：由吃、住、行、游、娱、购六部分组成（4）按旅游需求程度划分：分为基本旅游产品和非基本旅游产品 十、旅游产品的构成要素（1)旅游吸引物（自然和人文）(2)旅游设施（基础设施和旅游服务设施）(3)旅游服务(4)可进入性 十一、产品生命周期：是指一个产品从它进入市场开始到最后撤出市场的全部过程，分为推出期、成长期、成熟期、衰退期 （1）旅游产品的推出期：旅游新产品正式推向旅游市场，具体表现为旅游景点、饭店、娱乐设施建成，新的旅游路线开通，新的旅游项目、旅游服务推出（2）成长期：这一阶段，旅游景点、旅游地开发初具规模，旅游设施、旅游服务逐步配套，旅游产品基本定型并形成一定的特色（3）成熟期：在这一阶段潜在顾客逐步减少，大多属于重复购买的市场（4）衰退期：指产品的更新换代阶段，这一阶段新的旅游产品已进入市场，正在逐渐代替老产品 结论：（1）任何旅游产品都有一个有限的生命大部分旅游产品都经过一个类似S 形的生命周期（2）每个旅游产品生命周期阶段的时间长短不同（3）旅游产品在不同生命周期阶段中，利润高低不同 十二、旅游线路设计内容⑴确定线路主题，评估目的地（主题是旅游产品的灵魂）⑵策划旅游线路，计划活动日程⑶选择交通工具，安排住宿餐饮。⑷筹划娱乐购物活动，满足自由活动需求(5)核算产品成本，制定产品价格（自由发挥） 十三、单项旅游产品设计（点、线、面、体结合）（1）餐饮产品设计（2）住宿~ <功能化、个性化、绿色化>（3）游览~（4）购物~（5）娱乐~
最短路问题及应用 摘要:主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法以及这两种算法在实际问题中的应用和比较。 关键词：最短路获克斯特拉(Dijkstra)，弗罗伊德(Floyd)算法 1.引言 图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数 学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等。这些古老的难题，当时吸引了很多学者的注意。在这些问题研究的基础上又继续提出了著名的四色猜想 和汉米尔顿（环游世界）数学难题。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学 等各个领域的问题时，发挥出越来越大的作用在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点 间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学 与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2.最短路算法 2.1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0 w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的，该ij 算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短
旅游景点线路设计和优化中的问题及发展新特点 选择适合的旅游点、设施和服务提供商是整合优化的核心是线路优化的重要环节，以下是小编搜集整理的一篇探究旅游景点线路设计优化的论文范文，欢迎阅读查看。 一、城郊分布旅游景点线路优化的概念 城郊分布旅游景点旅游线路作为旅游产品的一部分，它主要是由城郊各县和乡镇间的交通线路连接而成，其旅游资源可能分布在某个城郊区域的若干个区县和乡镇，城郊旅游线路的设计和优化对城郊区域经济的发展是至关重要的。 (一)城郊旅游线路优化的核心 城郊旅游的核心在于为旅游者提供丰富多彩的城郊生态景观和民俗文化，为游客在短途旅行当中带来精神满足。 城郊旅游区别于其他旅游形式的不同在于，城郊旅游参与者更多是希望通过短途旅游获取原生态的美、自然的田园风光、古朴的旧式建筑和城郊特有的民俗风情。 城郊旅游节点的资源挖掘是线路设计过程当中非常关键也是困难的一环。 城郊旅游节点资源与大型旅游区节点资源相比，其资源优势的呈专一性和独特性。正是因为充分发挥其独特资源效益，推动该节点辐射区域经济的发展，提高该旅游节点的核心竞争力。 (二)城郊旅游线路优化提升城郊区域经济发展水平 城郊经济的发展是城市化进程的必经之路，是城市经济向农村延
伸的过渡地带。城郊经济的整体发展是城市发展的重要推动力之一。 因此，城郊旅游线路的优化应充分调动区域资源，不能局限于点，应该从面上进行资源整合，打破行政区域的限制，从资源根本特性出发进行考虑，这样才能为整个城郊旅游经济的发展起到推动作用，进而提升城郊区域的综合竞争力。 二、城郊分布旅游景点线路优化的方法和步骤 城郊旅游节点的特点是拥有优美的自然环境，能够提供一定的公共活动需求，但是水平都还相对较低，满足不了游客长时间的旅游生活需要。随着私家车的迅猛发展，城郊旅游已经逐渐成为了城市居民重要的休闲旅游方式之一。 (一)城郊旅游线路优化的原则 以自助短途旅游为主。城郊旅游线路产品的目标市场主要是来自于城市的散客旅游者，以自驾车游客居多，在线路优化时，应当注重研究游客的需求。如游客当中多数以家庭或者朋友为单位，通过短途城郊旅游欢聚闲暇时光，希望拥有相对私密的空间。当然很大一部分游客是为了远离城市，接近大自然，舒缓心情，减缓工作压力，希望拥有较舒适的休闲区域。 因此线路设计过程中应充分考虑城郊旅游人群的旅游目的和特点，才能更好结合城郊旅游节点资源进行整合、优化和宣传。不同类型的游客通过合理的线路获得满意的旅游产品可以有效的提升线路的知名度。 (二)突出线路的主题
最短路问题(short-path problem) 若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径） 1、Dijkstra算法： 用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度 代码： procedure dijkstra（v0：longint）；//v0为起点做一次dijkstra begin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongint for i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里 visit[v0]:=true;//已经连接v0结点 for i:=1 to n-1 do//剩下n-1个节点未加入路径里； begin min:=maxlongint;//初始化min for j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小 begin min:=d[j];k:=j;end; visit[k]:=true;//连接进去 for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值， if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k]; end; writeln(d[n]);//结点v0到结点n的最短路。 思考：在实现步骤时，效率较低需要O(n)，使总复杂度达到O(n^2)。对此可以考虑用堆这种数据结构进行优化，使此步骤复杂度降为O(log(n))(总复杂度降为O(n log(n))。 实现：1. 将与源点相连的点加入堆（小根堆），并调整堆。 2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。 3. 处理与u相邻（即下一个）未被访问过的，满足三角不等式的顶点 1):若该点在堆里，更新距离，并调整该元素在堆中的位置。 2):若该点不在堆里，加入堆，更新堆。 4. 若取到的u为终点，结束算法；否则重复步骤2、3。 **优化代码：(DIJKSTRA+HEAP) program SSSP;{single source shortest path} {假设一个图的最大节点数为1000，所有运算在integer范围内} {程序目标：给定有向图的邻接表，求出节点1到节点n的最短路径长度} const maxn=1000;{最大节点数} var n:integer;{节点个数} list:array[1..maxn,1..maxn] of integer;{邻接矩阵，表示边的长度}
旅游线路的优化设计 作者:
--------------- 日期：
承诺书 我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。 我们的参赛报名号为： 参赛组别（研究生或本科或专科）：本科 参赛队员（签名）： 队员1 ： 队员2 ： 队员3： 获奖证书邮寄地址：
编号专用页 参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）： 竞赛评阅编号（由竞赛评委团评阅前进行编号）：
题目旅游线路的优化设计 摘要 本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。 第一问放松时间约束，要求游客游遍所有的景点，该问题也就成了典型的货郎担 （TSP）问题。使用lingo编程得到最佳旅游路线为：徐州一常州一舟山一黄山一庐山 —武汉黄鹤楼一龙门石窟一秦兵马俑一祁县乔家大院一八达岭长城一青岛崂山一徐州。 第二问给定时间约束，要求设计合适的旅游路线。我们建立了一个最优规划模 型，在给定游览景点个数的情况下以总费用不限，时间最少为目标。再引入0 —1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：徐州一恐龙园一舟山一黄山一庐山—黄鹤楼一秦兵马俑一龙门石窟一乔家大院一八达岭长城一青岛崂山一徐州。 第三问放松时间约束，要求游客在总费用低于2000元的约束下游览最多的景 点。在第一问的基础上建立模型，并增加总费用低于2000元的约束。使用lingo编 程得到最佳旅行路线为：徐州一常州一武汉一洛阳一西安一祁县一北京一青岛一徐州。 第四问给定时间约束，放松对总费用的约束。我们在第二问的基础上建立一个最 优化模型，以时间最少为目标。再引入0 —1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求 解。推荐方案：徐州-常州-九江-武汉-洛阳-西安-祁县-北京-徐州。 第五问给定时间、总费用小于2000的双重约束。我们在第三问、第四问的基础上建立模型，以在规定时间内，规定总费用内，以游览最多景点为目标。使用lin go 编程对模型求解。推荐方案：徐州-常州-舟山-黄山-九江-武汉-洛阳-西安-徐州 关键词：最佳路线TCP 问题景点个数最小费用
毕业设计文献综述 计算机科学与技术 旅游线路优化设计 一、前言部分： 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）[1-3]。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。 二、主题部分 旅游线路优化设计是一个旅行商问题，通过c++,matlab等多种软件对于初始数据进行分析运算，并将其合理运用以建立模型，最后采用遗传算法对数据进行运算。 旅游线路优化也叫巡回旅行商问题（Traveling Salesman Proble- m,TSP），也称为货郎担问题[4]。它是一个较古老的问题，最早可以追溯到1759年Euler提出的骑士旅行问题。货郎担问题可以解释为，一位推销员从自己所在城市出发，必须遍访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（或旅行距离最短）的路径。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的一个典型难题。它是一个具有广泛
一、问题重述 随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算在今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如附表1（见附录I）所示。 假设 (A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车 票或机票可预订到。 (B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。 (C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20： 00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。 (D)假设景点的开放时间为8:00至18:00。 问题： 根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数 学模型并设计旅游行程表。 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数 学模型并设计旅游行程表。 (3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并 设计旅游行程表。 (4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计 旅游行程表。 (5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立 相关数学模型并设计旅游行程表。 二、问题假设 1、忽略乘坐出租车时经过收费路段所交的费用； 2、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考 虑； 3、所有旅馆都未客满，并且忽略从旅馆到火车站或景点的时间； 4、列车车次和飞机航班没有晚点等情况发生； 5、列车和飞机的票足够，没有买不到票的情况发生； 6、景点的开放，列车和航班的运营不受天气的影响； 7、绘图时，经线和纬线近似平行分布； 8、将城市和路径的关系转化为图论问题； 9、在时间的认识上，我们把当天的8点至次日的8点作为一天。
旅游线路设计期末考试 要点 Company number【1089WT-1898YT-1W8CB-9UUT-92108】
一、旅游业由直接提供旅游产品和服务的主体部门、间接提供的相关部门、管理部门构成 二、旅游业的三大支柱：旅行社住宿业交通运输业 三、旅游业赖以生存和发展的三大要素：旅游资源（自然风光、历史古迹、民族习俗是经营旅游业的吸引能力）旅游设施（旅游交通、旅游住宿、旅游餐饮、旅游游乐设施）旅游服务（是各种劳务和管理行为的结合是经营旅游业的接待能力） 四、旅游业的种类：旅游产业不是一个单一产业而是一个产业群由多种产业组成具有多样性和分散性包括景点经营、旅行社、餐饮服务业、交通业、娱乐业等 五、旅游的形式：跟团游、自助游、半自助游、自驾游、驴友等所谓无景点旅游就是不再跟随旅行团走马观花到知名景点一游了之而是驻扎到某地随意安排行程或者在城市大街小巷闲逛，或者到乡郊野外体验民风民俗 六、旅行社赚钱方式:（1）先是低买高卖，也就是旅行社去和酒店、景区、餐厅等签下协议价然后以稍低于门前价的价格卖出去赚差价 （2）大卖场模式：旅行社通过完整的网络布点、强大的宣传攻势来达到巨大的收客量，再用这种收客量去要求酒店、航空公司、景区给予比平均协议价低的合作价格 七、旅游产品：是指旅游者以货币形式向旅游经营者购买的一次旅游活动所消费的全部产品和服务的总和
八、旅游产品的形态（1）观光旅游产品（2）文化~（3）商务~（4）度假~（5）康体~（6）业务~ （7）享受~ （8）探险~ 九、旅游产品构成分析（1）按市场营销划分：旅游产品由核心部分、外形部分和延伸部分组成(2）按劳动形式划分：旅游产品可分为以物化劳动表现的旅游产品部分、以活劳动表现的旅游产品部分和完全不包含劳动消耗的旅游产品部分（3）按消费形式划分：由吃、住、行、游、娱、购六部分组成（4）按旅游需求程度划分：分为基本旅游产品和非基本旅游产品 十、旅游产品的构成要素（1)旅游吸引物（自然和人文）(2)旅游设施（基础设施和旅游服务设施）(3)旅游服务(4)可进入性 十一、产品生命周期：是指一个产品从它进入市场开始到最后撤出市场的全部过程，分为推出期、成长期、成熟期、衰退期 （1）旅游产品的推出期：旅游新产品正式推向旅游市场，具体表现为旅游景点、饭店、娱乐设施建成，新的旅游路线开通，新的旅游项目、旅游服务推出（2）成长期：这一阶段，旅游景点、旅游地开发初具规模，旅游设施、旅游服务逐步配套，旅游产品基本定型并形成一定的特色（3）成熟期：在这一阶段潜在顾客逐步减少，大多属于重复购买的市场（4）衰退期：指产品的更新换代阶段，这一阶段新的旅游产品已进入市场，正在逐渐代替老产品 结论：（1）任何旅游产品都有一个有限的生命大部分旅游产品都经过一个类似S形的生命周期（2）每个旅游产品生命周期阶段的时间长短不同（3）旅游产品在不同生命周期阶段中，利润高低不同 十二、旅游线路设计内容⑴确定线路主题，评估目的地（主题是旅游产品的灵魂）⑵策划旅游线路，计划活动日程⑶选择交通工具，安排住宿餐饮。⑷筹划
《最短路径问题》的反思及应用 我们知道，有效地开发和利用课本，对于学生的学习具有重要的意义。学生对于课本上例题或习题能否吃透，直接影响着学生的学习效果。因此教师要引导学生挖掘教材，引导学生进行反思，从中领悟问题解决过程的数学内涵。 有这样一个问题： 如图1所示，牧马人从A 地出发，到一条笔直的河边l 饮马，然后到B 地。牧马人到河边的什么地方饮马，可使所走的路径最短? 分析 我们把河边近似看做一条直线l (如图2)，P 为直线l 上的一个动点，那么，上面的问题可以转化为：当点P 在直线l 的什么位置时，AP 与PB 的和最小。 如图3所示，作点B 关于直线l 的对称点'B ，连接'AB ，交直线l 于点P ，则点P 就是牧马人到河边饮马的位置。事实上，点'B 与点A 的线段'AB 最短，由对称性质知，'PB PB =，因为''PA PB PA PB AB +=+=，即点P 到点A 、B 的距离之和最小。 上述路径问题，是利用轴对称的性质，通过等线段代换，将所求路线长转化为两定点之间的距离，基本思路是运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长。从解题过程不难看出，本题蕴含着三个数学思想方法:数学模型思想，转化思想，对称思想。如果学生一旦认识或明白这些思想方法，就能举一反三，再复杂的问题也会迎刃而解。 一、基本应用 如图4，点O 是矩形ABCD 的中心，E 是AB 上的点，沿CE 折叠后，点B 恰好与点O 重合，若3BC =，则折痕CE 的长为多少? 分析 沿CE 折叠后，点B 恰好与点O 重合，则点B 、点O 关于直线CE 对称， 3CO CB ==，1122 ACB ∠=∠=∠，点O 是矩形ABCD 的中心，知26AC CO ==。所以12302 ACB ∠=∠=?，又在Rt CBE ∠中，30BCE ∠=?，3BC =，若设BE x =，则 2CE x =，得222(2)3x x -=，13x =23x -（舍去），所以223CE x == 二、拓展应用 如图5两条公路BA 、BC 相交于点B ，在两条公路之间的P 点有一个油库，若要在公
毕业设计开题报告 计算机科学与技术 旅游线路优化设计 一、选题的背景、意义 随着科技的不断发展和进步，现在的计算机越来越趋向于智能化发展，未来将会出现许多智能的计算机，这些智能机器功能各异，能够满足人们对生活和应用的需求，一些现实问题可以在电脑上解决。旅游线路优化也叫巡回旅行商问题（Traveling Salesman Proble- m,TSP），也称为货郎担问题[1-3]。它是一个较古老的问题，最早可以追溯到1759年Euler 提出的骑士旅行问题。货郎担问题可以解释为，一位推销员从自己所在城市出发，必须遍访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（或旅行距离最短）的路径。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的一个典型难题。它是一个具有广泛应用背景和重要理论价值的组合优化问题。TSP的搜索空间随着城市规模数n的增加而增大，这类组合优化问题称之为NP完全问题。在如此庞大的搜索空间中寻求近似最优解，对于常规方法和现有的计算工具而言，存在着诸多的计算困难。因此，借助遗传演化算法，模仿大自然界生物的繁殖、杂交及其变异的演化过程来解决TSP问题，显得非常必要。基于以上原因，本人采用经典遗传算法理论及个体实数编码方法设计了此算法，试图进一步探索TSP组合优化问题的有效解决方案。 与其他的算法相比，遗传算法与之在本质上有着不同之处：遗传算是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 旅游线路优化设计，能让旅客在遍历所有景点的情况下，让旅行的开销实现最小化。 二、研究的基本内容与拟解决的主要问题 本课题是设计现实旅游线路优化。根据一个区域内全部景点的地理分布，以及各个景点之间的旅行开销，在实现所有景点遍历的前提下，达到旅行开销最小化。鉴于传统搜索方法难以解决复杂和非线性问题的原因，要求在设计中运用遗传算法（GA）这一借鉴生物界自然选择和自然遗传机制的随机化搜索算法。 具体来说，本课题要研究的是如何运用遗传算法的相关知识来对一个区域的所有景点
第25卷第3期 Vol .25 No .3长春师范学院学报(自然科学版)Journal of Changchun Normal University (Natural Science )2006年6月Jun .2006 最短路问题在运输网络中的应用 李 玲 (陕西工业职业技术学院,陕西咸阳 712000) [摘 要]最短路问题是在图的基础上衍生出来的,也是网络优化中的一个基本问题,许多选择优化 问题都可以转化为最短路问题来求解。本文重在研究公路网络运输中的最短路问题。 [关键词]最短路;网络运输;网络优化;动态规划 [中图分类号]O221 [文献标识码]A [文章编号]1008-178X (2006)03-0058-04 [收稿日期]2006-02-01 [作者简介]李 玲(1977-),女,陕西商洛人,陕西工业职业技术学院教师,从事计算机专业基础课教学研究。 1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图(w ij ≥0)的有效算法是由荷兰著名计算机专家E .W .Dijkstra [1]在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解 图G 中一特定点到其它各顶点的最短路。后来海斯[2]在Dijkstra 算法的基础之上提出了海斯算法。但这两种 算法都不能解决含有负权的图的最短路问题。因此由Ford [3]提出了Ford 算法,它能有效地解决含有负权的最 短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在(w ij ≥0)的情况下选择Dijkstra 算法。 定义1[4]若图G =G (V ,E )中各边e 都赋有一个实数W (e ),称为边e 的权,则称这种图为赋权图,记为G =G (V ,E ,W )。 定义2[5] 若图G =G (V ,E )是赋权图且W (e )≥0,e ∈E (G ),若u 是v i 到v j 的路W (u )的权,则称W (u )为u 的长,长最小的v i 到v j 的路W (u )称为最短路。 若要找出从v 1到v n 的通路u ,使全长最短,即min W (u )=∑e ij ∈u W (e )。2 最短路问题算法的基本思想及基本步骤 在诸多算法中(w ij ≥0)最经典的算法当属Dijkstra 算法,该算法的基本思想是动态规划[6]最优原理,即最短路线上任意两点间的路线也是最短。因此,若v i 到v j 的最短路线经过v k ,则v i 到v k 以及v k 到v j 的部分都是相应的最短路线。 基本步骤: 令 s ={v 1},i =1, s ={v 2,v 3,…,v n } 并令 W (v 1)=0 T (v j )=∞,v j ∈ s ①对v j ∈ s ,求min {T (v j ),W (v i )+w ij }=T (v j )。 ②求min v j ∈ s {T (v j )}得T (v k ),使T (v k )=min v j ∈ s {T (v j )}