TSP问题及LINGO求解技巧

TSP问题及LINGO求解技巧巡回旅行商问题(Traveling Salesman Problem, TSP)，也称为货郎担问题。最早可以追 溯到1759年Euler提出的骑士旅行问题。1948年，由美国兰德公司推动，TSP成为近代组合优 化领域的一个典型难题。它已经被证明属于NP难题。用图论描述TSP，给出一个图G = (V,E)，每边e e E上有非负权值w(e),寻找G的Hamilton圈C，使得C的总权W(C) =w(e)最小.e e E(C)几十年来，出现了很多近似优化算法。如近邻法、贪心算法、最近插入法、最远插入法、 模拟退火算法以及遗传算法。这里我们介绍利用LING O软件进行求解的方法。问题1 设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。10个 城市相互距离如下表。要求每个城市到达一次仅一次后，回到原出发城市。问他应如何选择 旅行路线，使总路程最短。表110个城市距离表城市1234567891010745861213111827031091451417173430591021827124510501491092316589914078720196614109701352513712521108130232118813148975230181291117272320252118016101817121619131812160我们采用线性规划的方法求解设城市之间距离用矩阵d来表示，d表示城市i与城市j之间的距离。设0-1矩阵X用来表示经过的各城市之间的路线。设0若城市i不到城市jXij = 1若城市倒城市j,且i在j前考虑每个城市后只有一个城市，则：n 4 Xj =1,j=1J节考虑每个城市前只有一个城市，则: xij T, J =1,n ； i=1 i尹j但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。为此我们引入额外变量七(i = 1,n)，附加以下充分约束条件：u. uj + nXj n -1,1 i 丰 j n ；该约束的解释：如i与j不会构成回路，若构成回路，有:u u . 1，u . u. 1，从而有:i j ， j i ，|闩：。 2，导致矛盾。如i，j与k不会构成回路，若构成回路，有:Xij T，、=1，xki =1 则：u u 1 u u 1 u u 1 u 布右i j ， j k ， k i从而有:03，导致矛盾。其它情况以此类推。于是我们可以得到如下的模型:min z IL d xi,j-1 J Jx 1,j 1,.,ni-1 j n-1,1 i 牛 j nLx. - 1, ij j1 j的iju - u. + nxx 0或1,iju.为实数，前面问题的Lingo程序!TSP quesion;MODEL:SETS:city/1.10/:u;link(city,city):d,x;ENDSETSDATA:d= 0774 59814651214131711171803 104305910218271251050 1491092316899 14078720196141097013525131252110813023211813148 975230181211172723 2025211801618171216 19131812160;ENDDATAMIN=SUM(link:d*x);for(city(j):sum(city(i)|j#ne#i:x(i,j)=1); 城市前有一个城市相连;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。其最短路线为143275681091,最短距离为77公里。问题2. 2005年电工杯B题比赛项目排序问题全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各群众组织和社 会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标 相配套的社会系统工程和跨世纪的发展战略规划。现在，以全民健身为主要内容的群众性体 育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩 大了竞技体育的社会影响，提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是， 这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了 荣誉。在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项 目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常 水平。1. 表2是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。 表中第1行表示14个比赛项目，第1列表示40名运动员，表中“#”号位置表示运动员参 加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的 运动员人次尽可能的少；2. 文件“运动员报名表”中给出了某个运动比赛的报名情况。共有61个比赛项目，1050 人参加比赛。请给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛 的运动员人次尽可能的少；3 .说明上述算法的合理性；4.对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方 案。表2某小型运动会的比赛报名表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的距离勺。则问题转化为求项目1到项目14的一个排列，使相邻距离和最小。我 们采用TSP问题求解。但由于开始项目和结束项目没有连接，可考虑引入虚拟项 目15,该虚拟项目与各个项目的距离都为0。距离矩阵D的求法：该报名表用矩阵A表示。40x141第，个人参加项目ja - _ j 0第个人不参加项目j贝g d =丈 a .ai 主 j,i, j,-1,2-,143k=1Jd = 0 i 1,2,.,14另外 d 0, d 0 i = 1,2,.,15i ,1515, i由于问题1中40个运动员参加14个项目的比赛是word表，可将其拷贝到 Excel表中，然后将#替换为1，将空格替换为0，形成0-1表，并拷贝到数据文 件table1.txt中。问题2中1050个运动员参加的61个项目比赛的Access数据 库中的表保存为Excel表，然后在表中将#替换为1，将空格替换为0，形成0-1 表，并拷贝到数据文件table2.txt中。在Matlab中编制如下程序形成距离矩阵。load table1.txt;a=table1;m,n=size(a);d=zeros(n+1,n+1); %定义距离矩阵；for i=1:nfor j=1:nfor k=1:md(i,j)=d(i,j)+a(k,i)*a(k,j); %计算不同项目之间距离endendendfor i=1:n+1d(i,i)=0;end%输出文件fid二fopen(dis1.txt,w);for i=1:n+1for j=1:n+1fprintf(fid,%1d ,d(i,j);endfprintf(fid,n);endfclose(fid);输出的距离矩阵D为:021200101211110201410111310210110100031102210241011210210110010102011101120000120121112120110201011102210013112101214220111011110111310231211121010030110101011103110102012241030100122111223011040111122121310400000000000000000然后按照前面介绍的方法2程序：!第一个问题的求解的程序：!比赛项目排序问题；model:sets :item / 1. 15/: u;link ( item, item) :dist,x;endsetsn = size( item);data:!距离矩阵；dist=file(c:lingo12prgdis1.txt); !文件路径;!输出为1的变量；text()=writefor(link(i,j)|x(i,j)#GT#0: x(,i,j,)=,x(i,j); enddataMIN=SUM(link:dist*x);for (item(j): sum(item(i)|j#ne#i:x(i,j)=1); !点前有一个点相连;for(item(i) :sum(item(j) |j#ne#i:x(i,j)=1); !点1后前有一个点;!保证不出现子圈；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为:021200101211110201410111310210110100031102210241011210210110010102011101120000120121112120110201011102210013112101214220111011110111310231211121010030110101011103110102012241030100122111223011040111122121310400000000000000000Lingo12求解结果为：目标值z=2x(1,8)=1x(2,6)=1x(3,11)=1 x(4,13)=1 x(5,1)=1x(6,3)=1x(7,5)=1x(8,15)=1 x(9,4)=1x(10,12)=1 x(11,7)=1x(12,14)=1x(13,10)=1 x(14,2)=1 x(15,9)=1由于15是虚拟项，去掉后对应序列为9-4-13-10-12-14-2-6-3-11-7-5-1-8-9则项目排序如下，其中箭头上所示数字为连续参加相邻两项目的运动员数。9 4131012142J 8 J 3 11 -J 5 1 8 即有两名运动员连续参加比赛。问题2解答与问题1相同，只是项目变成61个，引入虚拟项目后变为62个，运 动员为1050名。模型建立同问题1。在问题一中的Matlab程序中只需要将表 table1.txt改为table2.txt，输出数据文件将dis1.tx t改为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;endsetsn = size( item); data:!距离矩阵；dist=file(c: lingo12prgdis2.txt); !文件路径;!输出为1的变量；text()=writefor(link(i,j)|x(i,j)#GT#0: x(,i,j,)=,x(i,j); enddataMIN=SUM(link:dist*x);for (item(j): sum(item(i)|j#ne#i:x(i,j)=1); !点前有一个点相连;for(item(i) :sum(item(j) |j#ne#i:x(i,j)=1); !点1后前有一个点;!保证不出现子圈；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变量; endLingo12求解结果：Lingo12求解结果为：目标值z=5x(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)=1 x(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)=1 x(42,52)=1 x(43,38)=1 x(44,4)=1 x(45,7)=1 x(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)=1 x(62,33)=1由于62是虚拟项，去掉后对应序列为3347555206154048342314-4111960859281722373058612444251332561154433849 2627292451165753393112211035036457一 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名运动 员连续参加比赛。