TSP问题及LINGO求解技巧.docx

资源描述

TSP问题及LINGO求解技巧.docx

《TSP问题及LINGO求解技巧.docx》由会员分享，可在线阅读，更多相关《TSP问题及LINGO求解技巧.docx（16页珍藏版）》请在冰点文库上搜索。

TSP问题及LINGO求解技巧.docx

TSP问题及LINGO求解技巧

巡回旅行商问题（TravelingSalesmanProblem，TSP），也称为货郎担问题。

最早可以追溯到1759年Euler提出的骑士旅行问题。

1948年，由美国兰德公司推动，TSP成为近代组合优化领域的一个典型难题。

它已经被证明属于NP难题。

用图论描述TSP，给出一个图

，每边

上有非负权值

寻找G的Hamilton圈C，使得C的总权

最小.

几十年来，出现了很多近似优化算法。

如近邻法、贪心算法、最近插入法、最远插入法、模拟退火算法以及遗传算法。

这里我们介绍利用LINGO软件进行求解的方法。

问题1设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。

10个城市相互距离如下表。

要求每个城市到达一次仅一次后，回到原出发城市。

问他应如何选择旅行路线，使总路程最短。

表110个城市距离表

城市

我们采用线性规划的方法求解

设城市之间距离用矩阵

来表示，

表示城市

与城市

之间的距离。

设0--1矩阵

用来表示经过的各城市之间的路线。

设

考虑每个城市后只有一个城市，则：

考虑每个城市前只有一个城市，则：

；

但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。

为此我们引入额外变量

，附加以下充分约束条件：

；

该约束的解释：

如

与

不会构成回路，若构成回路，有：

，

，则：

，

，从而有：

，导致矛盾。

如

，

与

不会构成回路，若构成回路，有：

，

则：

，

从而有：

，导致矛盾。

其它情况以此类推。

于是我们可以得到如下的模型：

前面问题的Lingo程序

TSPquesion;

MODEL:

SETS:

city/1..10/:

link（city,city）:

d,x;

ENDSETS

DATA:

d=07458612131118

703109145141717

43059102182712

510501491092316

8991407872019

614109701352513

12521108130232118

131489752301812

1117272320252118016

1817121619131812160;

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某小型运动会的比赛报名表

项目

运动员

问题一解答：

若项目

和项目

相邻，可以计算出同时参加这两个项目的人数，作为

和

的距离

。

则问题转化为求项目1到项目14的一个排列，使相邻距离和最小。

我们采用TSP问题求解。

但由于开始项目和结束项目没有连接，可考虑引入虚拟项目15，该虚拟项目与各个项目的距离都为0。

距离矩阵

的求法：

该报名表用矩阵

表示。

则

另外

由于问题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:

forj=1:

fork=1:

d（i,j）=d（i,j）+a（k,i）*a（k,j）;%计算不同项目之间距离

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）;

输出的距离矩阵

为：

021200101211110

201410111310210

110100031102210

241011210210110

010102011101120

000120121112120

110201011102210

013112101214220

111011110111310

231211121010030

110101011103110

102012241030100

122111223011040

111122121310400

000000000000000

然后按照前面介绍的

方法2程序：

第一个问题的求解的程序：

比赛项目排序问题;

model:

sets:

item/1..15/:

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）+n*x（i,j）<=n-1）;

@FOR（link:

@BIN（x））;!

定义X为0-1变量;

end

其中数据文件dis1.txt为：

021200101211110

201410111310210

110100031102210

241011210210110

010102011101120

000120121112120

110201011102210

013112101214220

111011110111310

231211121010030

110101011103110

102012241030100

122111223011040

111122121310400

000000000000000

Lingo12求解结果为：

目标值z=2

x（1,8）=1x（2,6）=1x（3,11）=1x（4,13）=1x（5,1）=1x（6,3）=1

x（7,5）=1x（8,15）=1x（9,4）=1x（10,12）=1x（11,7）=1x（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/:

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）+n*x（i,j）<=n-1）;

@FOR（link:

@BIN（x））;!

定义X为0-1变量;

end

Lingo12求解结果：

Lingo12求解结果为：

目标值z=5

x（1,19）=1x（2,44）=1x（3,50）=1x（4,25）=1x（5,20）=1x（6,15）=1x（7,42）=1x（8,59）=1x（9,35）=1x（10,3）=1x（11,54）=1x（12,21）=1x（13,32）=1x（14,41）=1x（15,40）=1x（16,57）=1x（17,22）=1x（18,9）=1x（19,60）=1x（20,6）=1x（21,10）=1x（22,37）=1x（23,14）=1x（24,51）=1x（25,13）=1x（26,27）=1x（27,29）=1x（28,17）=1x（29,24）=1x（30,58）=1x（31,12）=1x（32,56）=1x（33,47）=1x（34,23）=1x（35,46）=1x（36,45）=1x（37,30）=1x（38,49）=1x（39,31）=1x（40,48）=1x（41,1）=1x（42,52）=1x（43,38）=1x（44,4）=1x（45,7）=1x（46,62）=1x（47,55）=1x（48,34）=1x（49,26）=1x（50,36）=1x（51,16）=1x（52,18）=1x（53,39）=1x（54,43）=1x（55,5）=1x（56,11）=1x（57,53）=1x（58,61）=1x（59,28）=1x（60,8）=1x（61,2）=1x（62,33）=1

由于62是虚拟项，去掉后对应序列为

33—47—55—5—20—6—15—40—48—34—23—14-41—1—19—60—8—59—28—

17—22—37—30—58—61—2—44—4—25—13—32—56—11—54—43—38—49—

26—27—29—24—51—16—57—53—39—31—12—21—10—3—50—36—45—7—

42—52—18—9—35—46

可以验证，其中d（14,41）=1,d（51,16）=1,d（31,12）=1,d（10,3）=1,d（45,7）=1。

其余相邻两个项目比赛没有两名运动连续参加比赛。

即有5名运动员连续参加比赛。

展开阅读全文