经济旅游线路优化设计-数学建模

《经济旅游线路优化设计-数学建模》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2009-2010学年第一学期《数学建模》论文论文题目经济旅游线路优化设计姓名学号班级论文分数（教师填写）徐州X程學ft1、论文的创新点综合运用了列举法结合C语言解决TSP简单问题:程序运行环境visualC++6.0;2、各成员的分工丰田搜索材料和编程陈曦撰写一部分论文徐俊撰写一部分论文3、各成员的贡献丰田35%；陈曦35%；徐俊30%;4、论文的原创性声明本人郑重声明：所呈交的论文，是在论文小组成员讨论下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成

2、果。论文如有抄袭嫌疑，后果由木人承担。各成员签字：曰期：2010年1月8日经济旅游线路优化设计摘要：对给定的数据进行旅游线路优化，设计出更经济的旅游线路。针对问题：如何用简洁的方法解决TSP商旅问题；运用列举法通过C语言编程将所有可能的路线所需费用计算出来，通过比较求出最经济的旅行路线。关键词：经济，列举法，C语言。1、问题的提出现在有8个城市，己知两个城市之间的路费如下表，现在冇一个人从A城市出发旅行，应该选择怎样的路线才能刚好每个城市都到达一次又回到A城市，其总路费最少？ABCDEFGHA05635215160433

3、9B215778706449C3668---7060D51616526E134562F5326G502、条件的假设与符号的约定2.1条件的假设：把该问题的每个解看作是一次“巡冋”。在下述意义下，引入一些o-i整数变量：=p,巡冋路线是从/到y，j,,[0,其它惜况其目标只是使心=1为最小。这里有两个明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。n7=1n2.2符号约定:Xij循环路线(i=l，2•••，nj=l,2,

4、3•••,n)Cij从一_个城市到另一_个城市所需的费用。（i=l：2，•••，nj=l：2，3,…，n）W/(7=2,3,…，n)•參额外变量ni，j='旅行完8个城市所需总路费3、问题分析从A市出发选择合适的路线旅游每一个城市一次，使路费最少，其本质是一个TSP商旅问题。我们可以对己有的TSP商旅模型进行修改，通过编程将所有路线所需费用列举出来，找出最经济的路线。关于TSP旅行商问题:旅行商问题（TravelingSalemanProblem，TSP）是VRP的特例，由于Gaery[l]已证明TSP问题是NP难题，因

5、此，VRP也属于NP难题。旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成木。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。TSP问题在物流屮的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可

6、以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或III谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。TSP旅f亍商问题常见算法：枚举法，蚁群算法，模拟退火柴法。4、模型的建立与求解由2.1所给的条件与假设可以建立一个模型:最小费用='■，片它是一个指派问题的整数规划模型。为了证明该约朿条件有预期的效果，必须证明：(1)任何含子巡回的路线都不满足该约朿条件；(2)全部巡冋都满足该约束条件。首先证明(1),用反证法。假设还存在子巡［Hb也就是说至少有两个子巡回。那么至少存在一

7、个子巡回中不含城市1。把该子巡回记为^2"乂<则必有W…卜1ui2{-u^n

8、e{2,3,zr+1}In0,Z=2,3,…，n我们通过用c语言编程得到