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

2009-2010学年第一学期 《数学建模》论文 论文题目 经济旅游线路优化设计 姓 名 学 号 班 级 论文分数 (教师填写) 1、论文的创新点 综合运用了列举法结合C语言解决TSP简单问题； 程序运行环境 visual C++6.0; 2、各成员的分工 丰田 有哪些信誉好的足球投注网站材料和编程 陈曦 撰写一部分论文 徐俊 撰写一部分论文 3、各成员的贡献 丰田 35%； 陈曦 35%； 徐俊 30%； 4、论文的原创性声明 　　本人郑重声明：所呈交的论文，是在论文小组成员讨论下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。论文如有抄袭嫌疑，后果由本人承担。 各成员签字： 日 期： 2010年1月8日 经济旅游线路优化设计 摘要：对给定的数据进行旅游线路优化，设计出更经济的旅游线路。 针对问题：如何用简洁的方法解决TSP商旅问题； 运用列举法通过C语言编程将所有可能的路线所需费用计算出来，通过比较求出最经济的旅行路线。 关键词：经济，列举法，C语言。 1、 问题的提出 现在有8个城市，已知两个城市之间的路费如下表，现在有一个人从A城市出发旅行，应该选择怎样的路线才能刚好每个城市都到达一次又回到A城市，其总路费最少？ A B C D E F G H A B C D E F G 0 56 35 21 51 60 43 39 21 57 78 70 64 49 36 68 --- 70 60 51 61 65 26 13 45 62 53 26 50 2、条件的假设与符号的约定 2.1条件的假设: 把该问题的每个解看作是一次“巡回”。 0-1整数变量： 为最小。 这里有两个明显的必须满足的条件： 访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。 。 2.2符号约定： 循环路线（i=1，2···，n j=1,2,3···，n） 从一个城市到另一个城市所需的费用。（i=1，2，···，n j=1，2，3，···，n） ： 额外变量 旅行完8个城市所需总路费 3、问题分析 从A市出发选择合适的路线旅游每一个城市一次，使路费最少，其本质是一个TSP商旅问题。我们可以对已有的TSP商旅模型进行修改，通过编程将所有路线所需费用列举出来，找出最经济的路线。 关于TSP旅行商问题：旅行商问题（Traveling Saleman Problem，TSP）是VRP的特例，由于Gaery[1]已证明TSP问题是NP难题，因此，VRP也属于NP难题。 　旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。 　　TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。 　　TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，有哪些信誉好的足球投注网站空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 它是一个指派问题的整数规划模型。 为了证明该约束条件有预期的效果，必须证明： （1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。 1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为，则必有 k个式子相加，有