TSP问题及LINGO求解技巧.

Presentation on theme: "TSP问题及LINGO求解技巧."— Presentation transcript:

1 TSP问题及LINGO求解技巧

2 TSP问题介绍 巡回旅行商问题(Traveling Salesman Problem, TSP)，也称为货郎担问题。最早可以追溯到1759年Euler提出的骑士旅行问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的一个典型难题。它已经被证明属于NP难题。 用图论描述TSP，给出一个图 ，每边 上有非负权值 ，寻找G的Hamilton圈C，使得C的总权 最小。

3 TSP问题算法 几十年来，出现了很多近似优化算法： 近邻法 贪心算法 最近插入法 最远插入法 模拟退火算法 遗传算法
LINGO软件进行求解方法

4 TSP例题 问题1：设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。10个城市相互距离如下表。要求每个城市到达一次仅一次后，回到原出发城市。问他应如何选择旅行路线，使总路程最短。

5 问题1 表 个城市距离表 城市 1 2 3 4 5 6 7 8 9 10 12 13 11 18 14 17 21 27 23 16 20 19 25

6 问题1解答 我们采用线性规划的方法求解： 设城市之间距离用矩阵d来表示， 表示城市i与城市j之间的距离。设0--1矩阵X用来表示经过的各城市之间的路线。设 考虑每个城市后只有一个城市，则：

7 问题1解答 该约束的解释： 考虑每个城市前只有一个城市，则：
但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。为此我们引入额外变量 ，附加以下充分约束条件： 该约束的解释： 如i与j不会构成回路，若构成回路，有： ， ，则：

8 问题1 问题1解答 ， ，从而有： ，导致矛盾。 如i，j与k不会构成回路，若构成回路，有： ， ， 则： ， ， 从而有： ，导致矛盾。
， ，从而有： ，导致矛盾。 如i，j与k不会构成回路，若构成回路，有： ， ， 则： ， ， 从而有： ，导致矛盾。 其它情况以此类推。

9 问题1 问题1解答 于是我们可以得到如下的模型：

10 问题1解答 问题1 Lingo程序如下： !TSP quesion; MODEL: SETS: city/1..10/:u; ENDDATA
link(city,city):d,x; ENDSETS DATA: d= ; end ENDDATA !城市j前有一个城市相连; !城市i后前有一个城市相连; @for(link(i,j)|i#NE#j#and#i#gt#1:u(i)-u(j)+10*x(i,j)<=9); end

11 TSP例题 问题2： 2005年电工杯B题比赛项目排序问题。
全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。现在，以全民健身为主要内容的群众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩大了竞技体育的社会影响，提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是，这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了荣誉。

12 TSP例题 问题2： 2005年电工杯B题比赛项目排序问题。
在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。 1．表2是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中“＃”号位置表示运动员参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少；

13 TSP例题 问题2： 2005年电工杯B题比赛项目排序问题。
2．文件“运动员报名表”中给出了某个运动比赛的报名情况。共有61个比赛项目，1050人参加比赛。请给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛的运动员人次尽可能的少； 3．说明上述算法的合理性； 4．对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。

14 问题2 表2 某小型运动会的比赛报名表

15 问题2 表2 某小型运动会的比赛报名表

16 问题2 表2 某小型运动会的比赛报名表

17 问题2 问题一解答 若项目i和项目j相邻，可以计算出同时参加这两个项目的人数，作为i和j的距离 。则问题转化为求项目1到项目14的一个排列，使相邻距离和最小。我们采用TSP问题求解。但由于开始项目和结束项目没有连接，可考虑引入虚拟项目15，该虚拟项目与各个项目的距离都为0。 距离矩阵D的求法： 该报名表用矩阵 表示。

18 问题2 问题一解答 则 另外 由于问题1中40个运动员参加14个项目的比赛是 word 表，可将其拷贝到 Excel 表中，然后将 # 替换为 1，将空格替换为0，形成0-1表，并拷贝到数据文件table1.txt 中。问题2中1050个运动员参加的61个项目比赛的 Access 数据库中的表保存为Excel 表，然后在表中将 # 替换为1，将空格替换为0，形成0-1表，并拷贝到数据文件table2.txt中。

19 问题2 问题一解答 在Matlab中编制如下程序形成距离矩阵。 for i=1:n+1 load table1.txt; d(i,i)=0;
end %输出文件 fid=fopen('dis1.txt','w'); for j=1:n+1 fprintf(fid,'%1d ',d(i,j)); fprintf(fid,'\n'); fclose(fid); load table1.txt; a=table1; [m,n]=size(a); d=zeros(n+1,n+1); %定义距离矩阵; for i=1:n for j=1:n for k=1:m d(i,j)=d(i,j)+a(k,i)*a(k,j); %计算不同项目之间距离 end

20 问题2 问题一解答 在Matlab中编制如下程序形成距离矩阵。 输出的距离矩阵D为：

21 问题2 问题一解答 Lingo程序：

22 问题2 问题一解答 Lingo程序： 其中数据文件dis1.txt为： 0 2 1 2 0 0 1 0 1 2 1 1 1 1 0

23 问题2 问题一解答 Lingo12求解结果为： 目标值z=2
x(1,8)=1 x(2,6)= x(3,11)=1 x(4,13)=1 x(5,1)=1 x(6,3)=1 x(7,5)= x(8,15)=1 x(9,4)=1 x(10,12)=1 x(11,7)=1 x(12,14)=1 x(13,10)=1 x(14,2)=1 x(15,9)=1 由于15是虚拟项，去掉后对应序列为 则项目排序如下，其中箭头上所示数字为连续参加相邻两项目的运动员数。 即有两名运动员连续参加比赛。

24 问题2 问题二解答 问题2解答与问题1相同，只是项目变成61个，引入虚拟项目后变为62个，运动员为1050名。模型建立同问题1。

25 谢谢！！