^`
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，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
TSP旅行商问题常见算法：枚举法，蚁群算法，模拟退火柴法。
4、模型的建立与求解
由2.1所给的条件与假设可以建立一个模型：
最小费用=
它是一个指派问题的整数规划模型。
为了证明该约束条件有预期的效果，必须证明：
（1）任何含子巡回的路线都不满足该约束条件；
（2）全部巡回都满足该约束条件。
首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为，则必有
把这k个式子相加，有
，矛盾！
故假设不正确，结论（1）得证。
下面证明（2），采用构造法。对于任意的总巡回，
可取访问城市i的顺序数，取值范围为。
因此，。下面来证明总巡回满足该约束条件。
(ⅰ)总巡回上的边
（ⅱ）非总巡回上的边
从而结论（2）得证。
这样我们把此问题转化成了一个混合整数线性规划问题。
我们通过用C语言编程得到编译结果的截屏图像
结论：最佳路线A->G->E->F->C->B->H->D->A。
5、模型的评价与改进
5.1、模型的优点：
该模型构造简洁，易于理解，思路清楚。通过列举法与C语言的结合使解决该问题更为快速。考虑到了各种情况。为消费者提供了一个好方法。
5.2、模型的推广：
该模型适合在旅行城市个数较少的时候推广。当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对于小规模问题，我们求解这个混合整数线性规划问题的方式还是有效的。
附录：
程序中的变量所带表的含义
money[8][8]
二维数组（用来存放城市之间旅行的路费）
all[10000]
一维数组（用来存放每一条旅行线路的费用）
sta2
B城市
sta3
C城市
sta4
D城市
sta5
E城市
sta6
F城市
sta7
G城市
sta8
H城市
L2
最佳线路的第2个城市
L3
最佳线路的第3个城市
L4
最佳线路的第4个城市
L5
最佳线路的第5个城市
L6
最佳线路的第6个城市
L7
最佳线路的第7个城市
L8
最佳线路的第8个城市
min
最佳线路所需费用
xuhao
all数组中最佳线路所需费用的序号
解决该模型的C语言程序：
#include "stdio.h"
void main ()
{
Long int money[8][8]=
{{0,56,35,21,51,60,43,39},
{56,0,21,57,78,70,64,49},
{35,21,0,36,68,0,70,60},
{21,57,36,0,51,61,65,26},
{51,78,68,51,0,13,45,62},
{60,70,0,61,13,0,53,26},
{43,64,70,65,45,53,0,50},
{39,49,60,26,62,26,50,0}};
Long int sta2,sta3,sta4,sta5,sta6,sta7,sta8,i=0,x=0,y=0,min=0,xuhao=0;
long int all[10000],l2,l3,l4,l5,l6,l7,l8;
printf("all case:\n");
for(sta2=1;sta2<=7;sta2++)
for(sta3=1;sta3<=7;sta3++)
for(sta4=1;sta4<=7;sta4++)
for(sta5=1;sta5<=7;sta5++)
for(sta6=1;sta6<=7;sta6++)
for(sta7=1;sta7<=7;sta7++)
for(sta8=1;sta8<=7;sta8++)
{
if(sta3!=sta2&&
sta4!=sta3&&sta4!=sta2&&
sta5!=sta4&&sta5!=sta3&&sta5!=sta2&&
sta6!=sta5&&sta6!=sta4&&sta6!=sta3&&sta6!=sta2&&
sta7!=sta6&&sta7!=sta5&&sta7!=sta4&&sta7!=sta3&&sta7!=sta2&&
sta8!=sta7&&sta8!=sta6&&sta8!=sta5&&sta8!=sta4&&sta8!=sta3&&sta8!=sta2)
{
all[i]=s[0][sta2]+s[sta2][sta3]+s[sta3][sta4]+
s[sta4][sta5]+s[sta5][sta6]+s[sta6][sta7]+
s[sta7][sta8]+s[sta8][0];
i++;
}
if(i==4039)
/此处的i是通过首先运行程序得到xuhao值后确定的/
{
l2=sta2;
l3=sta3;
l4=sta4;
l5=sta5;
l6=sta6;
l7=sta7;
l8=sta8;
}
}
for(x=0;x
展开阅读全文
相关搜索