TSP问题及LINGO求解技巧.docx
《TSP问题及LINGO求解技巧.docx》由会员分享，可在线阅读，更多相关《TSP问题及LINGO求解技巧.docx（35页珍藏版）》请在冰点文库上搜索。
TSP问题及LINGO求解技巧
TSP问题及LINGO求解技巧
巡回旅行商问题（TravelingSalesmanProblem，TSP），也称为货郎担问题。
最早可以追溯到1759年Euler提出的骑士旅行问题。
1948年，由美国兰德公司推动，TSP成为近代组合优
化领域的一个典型难题。
它已经被证明属于NP难题。
用图论描述TSP，给出一个图G
（V,E），每边e
E上有非负权值
w（e）,寻找G的
Hamilton圈C，使得C的总权W（C）
w（e）最小.
e
E（C）
几十年来，出现了很多近似优化算法。
如近邻法、贪心算法、最近插入法、最远插入法、
模拟退火算法以及遗传算法。
这里我们介绍利用
LINGO软件进行求解的方法。
问题1
设有一个售货员从
10个城市中的某一个城市出发，去其它
9个城市推销产品。
10个
城市相互距离如下表。
要求每个城市到达一次仅一次后，
回到原出发城市。
问他应如何选择
旅行路线，使总路程最短。
表1
10个城市距离表
城市
1
2
3
4
5
6
7
8
9
10
1
0
7
4
5
8
6
12
13
11
18
2
7
0
3
10
9
14
5
14
17
17
3
4
3
0
5
9
10
21
8
27
12
4
5
10
5
0
14
9
10
9
23
16
5
8
9
9
14
0
7
8
7
20
19
6
6
14
10
9
7
0
13
5
25
13
7
12
5
21
10
8
13
0
23
21
18
8
13
14
8
9
7
5
23
0
18
12
9
11
17
27
23
20
25
21
18
0
16
10
18
17
12
16
19
13
18
12
16
0
我们采用线性规划的方法求解
设城市之间距离用矩阵d来表示，dij表示城市i与城市j之间的距离。
设0--1矩阵X用
来表示经过的各城市之间的路线。
设
xij
0
若城市i不到城市j
1
若城市i到城市j,且i在j前
考虑每个城市后只有一个城市，则：
n
xij1,i1,,n
j1ji
考虑每个城市前只有一个城市，则：
n
xij
1,
j1,,n
；
i1
ij
但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。
为此我们引入额外变量ui（i1,,n，附加以下充分约束条件：
uiujnxijn1,1ijn；
该约束的解释：
如i与j不会构成回路，若构成回路，有：
xij1，xji1，则：
u
u
j
1，u
j
u1，从而有：
i
i
12，导致矛盾。
如i，j与k不会构成回路，若构成回路，有：
xij1，xjk1，xki1则：
u
u
j
1，u
j
u
1，u
u1从而有：
i
k
k
i
13，导致矛盾。
其它情况以此类推。
于是我们可以得到如下的模型：
n
min
z
dijxij
i,j
1
n
L
xij1,
j1,,n
i1
ij
n
xij1,
L
s..t
j
1
j
i
uiujnxij
xij0或1,
ui为实数,
n
1,
1ijn
L
n
i,j1,
i
L
n
1,
前面问题的Lingo程序
!
TSPquesion;
MODEL:
SETS:
city/1..10/:
u;
link（city,city）:
d,x;
ENDSETS
DATA:
d=07
4
5
8
6
12
13
11
18
7
0
3
10
9
14
5
14
17
17
4
30
5
9
10
21
8
27
12
5
1050
14
9
10
9
23
16
8
9
9
14
0
7
8
7
20
19
6
1410
9
7
0
13
5
25
13
12
521
10
8
13
0
23
21
18
13148
9
7
5
23
0
18
12
111727
23
20
25
21
18
0
16
18
1712
16
19
13
18
12
16
0;
ENDDATA
MIN=@SUM（link:
d*x）;
@for（city（j）:
@sum（city（i）|j#ne#i:
x（i,j））=1）;!
城市j前有一个城市相连;
@for（city（i）:
@sum（city（j）|j#ne#i:
x（i,j））=1）;!
城市i后前有一个城市相连;
@for（link（i,j）|i#NE#j#and#i#gt#1:
u（i）-u（j）+10*x（i,j）<=9）;
@FOR（link:
@BIN（x））;
End
得到的结果如下：
X（3,2）=1,X（4,1）=1,X（4,3）=1,X（6,5）=1,X（7,2）=1,X（7,5）=1,X（8,6）=1,X（9,1）=1,X（10,8）=1,X（10,9）
=1。
其它全为0。
其最短路线为1—4—3—2—7—5—6—8—10—9—1，最短距离为77公里。
问题2．2005年电工杯B题比赛项目排序问题
全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标
相配套的社会系统工程和跨世纪的发展战略规划。
现在，以全民健身为主要内容的群众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩大了竞技体育的社会影响，提高了竞技体育水平。
现在各级、各类、各种运动比赛比比皆是，这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了荣誉。
在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：
在比赛项
目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常
水平。
1．表2是某个小型运动会的比赛报名表。
有14个比赛项目，40名运动员参加比赛。
表中第1行表示14个比赛项目，第1列表示40名运动员，表中“＃”号位置表示运动员参
加此项比赛。
建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的
运动员人次尽可能的少；
2．文件“运动员报名表”中给出了某个运动比赛的报名情况。
共有61个比赛项目，1050
人参加比赛。
请给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛
的运动员人次尽可能的少；
3．说明上述算法的合理性；
4．对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方
案。
表2某小型运动会的比赛报名表
项目
2
3
4
5
6
7
8
9
10
11
12
13
14
1
运动员
1
#
#
#
#
2
#
#
#
3
#
#
#
4
#
#
#
5
#
#
#
6
#
#
7
#
#
8
#
#
9
#
#
#
#
10
#
#
#
#
11
#
#
#
#
12
#
#
13
#
#
#
14
#
#
#
15
#
#
#
16
#
#
#
17
#
#
18
#
#
19
#
#
20
#
#
21
#
#
22
#
#
23
#
#
24
#
#
#
#
25
#
#
#
26
#
#
27
#
#
28
#
#
29
#
#
#
30
#
#
31
#
#
#
32
#
#
33
#
#
34
#
#
#
#
35
#
#
#
36
#
#
37
#
#
#
38
#
#
#
#
39
#
#
#
#
40
#
#
#
#
问题一解答：
若项目i和项目j相邻，可以计算出同时参加这两个项目的人数，作为i和j的
距离dij。
则问题转化为求项目1到项目14的一个排列，使相邻距离和最小。
我
们采用TSP问题求解。
但由于开始项目和结束项目没有连接，可考虑引入虚拟项目15，该虚拟项目与各个项目的距离都为0。
距离矩阵D的求法：
该报名表用矩阵A4014表示。
1第i个人参加项目j
aij
第i个人不参加项目j
0
40
则dij
aki.akj
i
j,i,j,
1,2,L
14
k
1
dii0
i
1,2,L
14
另外di,150,d15,i
0
i1,2,L
15
由于问题1中40个运动员参加14个项目的比赛是word表，可将其拷贝到
Excel表中，然后将#替换为1，将空格替换为
0，形成0-1表，并拷贝到数据文
件table1.txt中。
问题2中1050个运动员参加的61个项目比赛的Access数据
库中的表保存为Excel表，然后在表中将#替换为1，将空格替换为0，形成0-1表，并拷贝到数据文件table2.txt中。
在Matlab中编制如下程序形成距离矩阵。
loadtable1.txt;
a=table1;
[m,n]=size（a）;
d=zeros（n+1,n+1）;%定义距离矩阵;
fori=1:
n
forj=1:
n
fork=1:
m
d（i,j）=d（i,j）+a（k,i）*a（k,j）;%计算不同项目之间距离end
end
end
fori=1:
n+1
d（i,i）=0;
end
%输出文件fid=fopen（'dis1.txt','w'）;
fori=1:
n+1
forj=1:
n+1
fprintf（fid,'%1d',d（i,j））;
end
fprintf（fid,'\n'）;
end
fclose（fid）;
输出的距离矩阵
D为：
0
2
1
2
0
0
1
0
1
2
1
1
1
1
0
2
0
1
4
1
0
1
1
1
3
1
0
2
1
0
1
1
0
1
0
0
0
3
1
1
0
2
2
1
0
2
4
1
0
1
1
2
1
0
2
1
0
1
1
0
0
1
0
1
0
2
0
1
1
1
0
1
1
2
0
0
0
0
1
2
0
1
2
1
1
1
2
1
2
0
1
1
0
2
0
1
0
1
1
1
0
2
2
1
0
0
1
3
1
1
2
1
0
1
2
1
4
2
2
0
1
1
1
0
1
1
1
1
0
1
1
1
3
1
0
2
3
1
2
1
1
1
2
1
0
1
0
0
3
0
1
1
0
1
0
1
0
1
1
1
0
3
1
1
0
1
0
2
0
1
2
2
4
1
0
3
0
1
0
0
1
2
2
1
1
1
2
2
3
0
1
1
0
4
0
1
1
1
1
2
2
1
2
1
3
1
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
然后按照前面介绍的
方法2程序：
!
第一个问题的求解的程序：
!
比赛项目排序问题;
model:
sets:
item/1..15/:
u;
link（item,item）:
dist,x;
endsets
n=@size（item）;
data:
!
距离矩阵;
dist=@file（'c:
\lingo12\prg\dis1.txt'）;
!
文件路径
;
!
输出为1的变量;
@text（）=@writefor（link（i,j）|x（i,j）#GT#0:
'x（',i,',',j,'）=',x（i,j））;
enddata
MIN=@SUM（link:
dist*x）;
@for（item（j）:
@sum（item（i）|j#ne#i:
x（i,j））=1）;
!
点j前有一个点相连
;
@for（item（i）:
@sum（item（j）|j#ne#i:
x（i,j））=1）;
!
点i
后前有一个点
;
!
保证不出现子圈;
@for（link（i,j）|i#NE#j#and#i#gt#1:
u（i）-u（j）+
@FOR（link:
@BIN（x））;!
定义X为0-1变量;
n*x（i,j）<=
n-1）;
end
其中数据文件dis1.txt为：
0
2
1
2
0
0
1
0
1
2
1
1
1
1
0
2
0
1
4
1
0
1
1
1
3
1
0
2
1
0
1
1
0
1
0
0
0
3
1
1
0
2
2
1
0
2
4
1
0
1
1
2
1
0
2
1
0
1
1
0
0
1
0
1
0
2
0
1
1
1
0
1
1
2
0
0
0
0
1
2
0
1
2
1
1
1
2
1
2
0
1
1
0
2
0
1
0
1
1
1
0
2
2
1
0
0
1
3
1
1
2
1
0
1
2
1
4
2
2
0
1
1
1
0
1
1
1
1
0
1
1
1
3
1
0
2
3
1
2
1
1
1
2
1
0
1
0
0
3
0
1
1
0
1
0
1
0
1
1
1
0
3
1
1
0
1
0
2
0
1
2
2
4
1
0
3
0
1
0
0
1
2
2
1
1
1
2
2
3
0
1
1
0
4
0
1
1
1
1
2
2
1
2
1
3
1
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Lingo12求解结果为：
目标值z=2
x（1,8）=1x（2,6）=1x（3,11）=1x（4,13）=1x（5,1）=1
x（6,3）=1
x（7,5）=1x（8,15）=1x（9,4）=1x（10,12）=1x（11,7）=1
x（12,14）=1
x（13,10）=1x（14,2）=1x（15,9）=1
由于15是虚拟项，去掉后对应序列为
9-4-13-10-12-14-2-6-3-11-7-5-1-8-9
则项目排序如下，其中箭头上所示数字为连续参加相邻两项目的运动员数。
即有两名运动员连续参加比赛。
问题2解答与问题1相同，只是项目变成61个，引入虚拟项目后变为62个，运动员为1050名。
模型建立同问题1。
在问题一中的Matlab程序中只需要将表table1.txt改为table2.txt，输出数据文件将dis1.txt改为dis2.txt就可以了。
在Lingo程序中将项目数由15修改为62，使用的数据文件由15改为62，同样
可以运行，只是运行时间较长，本程序在Lingo12中大约运行6分钟左右。
原始数据文件table2.txt和Matlab输出的距离矩阵dis2.txt，由于数据较大这里不列出，可参见附录。
Lingo程序
!
第二个问题的求解的程序：
!
比赛项目排序问题;
model:
sets:
item/1..62/:
u;
link（item,item）:
dist,x;
endsets
n=@size（item）;
data:
!
距离矩阵;
dist=@file（'c:
\lingo12\prg\dis2.txt'）;
!
文件路径
;
!
输出为1的变量;
@text（）=@writefor（link（i,j）|x（i,j）#GT#0:
'x（',i,',',j,'）=',x（i,j））;
enddata
MIN=@SUM（link:
dist*x）;
@for（item（j）:
@sum（item（i）|j#ne#i:
x（i,j））=1）;
!
点j前有一个点相连
;
@for（item（i）:
@sum（item（j）|j#ne#i:
x（i,j））=1）;
!
点i
后前有一个点
;
!
保证不出现子圈;
@for（link（i,j）|i#NE#j#and#i#gt#1:
u（i）-u（j）+
@FOR（link:
@BIN（x））;!
定义X为0-1变量;
n*x（i,j）<=
n-1）;
end
Lingo12求解结果：
Lingo12求解结果为：
目标值z=5
x（1,19）=1x（2,44）=1x（3,50）=1x（4,25）=1x（5,20）=1
x（6,15）=1x（7,42）=1x（8,59）=1x（9,35）=1x（10,3）=1
x（11,54）=1x（12,21）=1x（13,32）=1x（14,41）=1x（15,40）=1
x（16,57）=1x（17,22）=1x（18,9）=1x（19,60）=1x（20,6）=1
x（21,10）=1x（22,37）=1x（23,14）=1x（24,51）=1x（25,13）=1
x（26,27）=1x（27,29）=1x（28,17）=1x（29,24）=1x（30,58）=1
x（31,12）=1x（32,56）=1x（33,47）=1x（34,23）=1x（35,46）=1
x（36,45
升级会员 