送货路线-数学建模-一等奖

1、摘要本文讨论了送货员送货路线的优化设计问题，即在给定送货地点和给定 设计规范的条件下，综合考虑最大载重范围、最大带货体积以及各货物送货时限， 确定业务员的最佳运行路线策略.并总结出一些在这类图中求解近似最优回路的 有效法则对于问题1，采用了两种方法进行了计算，第一种是通过 Floyd算法做出各 顶点间的最短路径矩阵，然后选出130号货物所送达的顶点间的最短路径及距 离，用二边逐次修正法求解 Hamilton圈；第二种是通过蚁群算法获得多条近似 优解，选取最佳线路对于第二问，则采用改进的遗传算法，求解有时间约束条件的 TSP问题， 根据线路规划问题的特点，基于遗传算法（GA ）建立了一个适用于带

2、有时间约 束的送货路线规划模型实验证明了此算法的有效性和可行性对于第三问，利用分割求解法和蚁群算法的合成算法， 运用共同链分割全图， 对每一个分图进行最优求解，由此得到全图的最优解。关键词 送货问题；优化路线；TSP模型；蚁群算法1送货路线设计的数学模型1问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人 送多个地方，请设计方案使其耗时最少现有一快递公司，库房在图1中的0点，一送货员需将货物送至城市内多处， 请设计送货方案，使所用时间最少该地形图的示意图见图1,各点连通信息见表 3,假定送货员只能沿

3、这些连通线路行走，而不能走其它任何路线.各件货物的相关信息见表1，50个位置点的坐标见表2.假定送货员最大载重50公斤，所带货物最大体积1立方米.送货员的平均速 度为24公里/小时.假定每件货物交接花费3分钟，为简化起见，同一地点有多件 货物也简单按照每件3分钟交接计算.现在送货员要将100件货物送到50个地点.请完成以下问题1. 若将130号货物送到指定地点并返回设计最快完成路线与方式给出结果. 要求标出送货线路2假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不 能超过指定时间，请设计最快完成路线与方式要求标出送货线路3.若不需要考虑所有货物送达时间限制（包括前30件货物），

4、现在要将100件 货物全部送到指定地点并返回设计最快完成路线与方式要求标出送货线路，给 出送完所有快件的时间由于受重量和体积限制，送货员可中途返回取货 可不考 虑中午休息时间.2模型的假设与符号说明2.1模型假设1 假设送货员只能沿如图所示连通线路行走，而不能走其它任何路线；2在连通线路中业务员可以任意选择路线；3假设送货员每到达一个地点，交接一件货物花费都为3分钟，交接完毕马上前往下一个地点，期间不花费时间；4假设送货员的速度保持匀速，即保持24公里/小时，不考虑堵车，发生意外等现象；2.2符号说明Wi :第i个货物的重量；(x, y)j :序号为i的送货点的坐标；V :第i个货物的体积；C

5、 :送货路线总路程；N :送货员送货次数；t:送货所用总时间；G(V,E):赋权连通图；Gi : G(V,E)的第i个子图；Li :子图Gi中的最佳回路；- (e):边e的边权；(v):点v的点权；li : Li的各边权之和；e : Li的各点权之和；T:送货中的停留时间；u :送货员的行驶速度；点权 (ViT V .为叙述方便起见，我们在文中不加说明地使用上述变量和符号的变形形式， 它们的含义可以通过上下文确定3模型的分析与建立3.1模型的建立把快递公司送货地点示意图抽象为一赋权连通图G(V,E)，在权图G中，v- V(G)对应示意图中的快递公司地点及货物送达点，V0表示快递公司所在地，eE

6、(G)对应示意图中路径.边权'(ejT对应示意图中的路径长度建立的数学模型如下：飞 E(G),，(e) N, v V(G),(v) V?,v0 V求G中回路L1,L2jH,Lk(k>1)，使得满足:k(1)V。V(Li),i "2|,k; (2)V(LJ=V(G);n(3)二二-：(e) = min(目标为总距离最短)i 二 e圧(LJjT%或 max 二 注(e) :二(v) = min(目标为时间最短 )1勺兰、e手(LJem(LJ为了讨论方便，先给出图论中相关的一些定义定义1经过图G的每个顶点正好一次的圈，称为G的哈密顿环路，也称Hamilton 圈.定义2在加权

7、图G =(V,E)中(1) 权最小的哈米顿圈称为最佳 Hamilton圈；(2) 经过每个顶点至少一次且权最小的闭通路称为TSP回路问题.由定义2可知，本问题是一个寻找 TSP回路的问题.TSP回路的问题可转化 为最佳Hamilton圈的问题.方法是由给定的图G=(V,E)构造一个以V为顶点集 的完备图G'(V,E)，E中每条边(x,y)的权等于顶点x与y在图中最短路径的 权，即卩mm -1m-1 m-1、djmin dimdmj © 在图论中有以下定理：定理1加权图G的送货员回来的权和G 的最佳Hamilton圈的权相同；定理2在加权完备图中求最佳 Hamilton圈的问题

8、是NPC问题.在解决问题的过程中，我们用到以下算法：算法一(Floyd算法)：令Dn表示一个N x N矩阵，它的(i, j)元素是dj.1. 将图中各顶点编为1,2,H|,N .确定矩阵Do，其中(i,j)元素等于从顶点i到 顶点j最短弧的长度(如果有最短弧的话).如果没有这样的弧，则令d/：.对 于 i，令 d/ =0 .2. 对m=1,2川|,N，依次由Dm-i的元素确定Dm的元素，应用递归公式mm JmJ m J.dij -mindmdmj ,dj .每当确定一个元素时，就记下它所表示的路.在算法终止时，矩阵Dn的元素(i,j)就表示从顶点I到顶点j最短路的长度.算法二：求加权图G =(

9、V,E)的TSP问题回路的近似算法：1用算法一(Floyd算法)求出G=(V,E)中任意两个顶点间的最短路，构造出完备图G =(V,E ),-(x,y) E； (x,y)=mi n dG(x,y).2. 输入图G 的一个初始Hamilton圈；3. 用对角线完全算法产生一个初始 Hamilton圈；4. 随机搜索出GJ(V,E)中若干个Hamilton圈，例如2000个；5. 对2、3、4步所得的每个Hamilton圈，用二边逐次修正法进行优化，得到近似最佳Hamilton圈；6. 在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳Hamilton圈的近似解.算法三：蚁群算法蚁群算法是

10、一种新型的模拟进化算法该算法由意大利学者 M. Dorigo V.Maniezzo和A. Colorini 等人在90年代首先提出，称之为蚁群系统(ant colony system )，应用该算法求解TSP问题、分配问题，取得了较好的结果.算法受到 真实蚁群觅食行为的启发，科学家发现虽然单个蚂蚁没有太多的智力，也无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线 经过大量细致观察研究发现：蚂蚁个体之间通过一种称之为外激素(pheromo ne) 的物质进行信息传递蚂蚁在运动过程中，能够在它所经过的路径上留下该种物 质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导

11、自己的运动方向， 因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径 的概率就越大.蚂蚁个体之间就是通过这种信息的交流寻找最优的到达食物源的线路.蚁群算法具有实现简单、正反馈、分布式的优点町b）c）图1蚁群算法说明在图1中， 从A到E （或者从E到A）有两条路径（ABCDE和ABHDE，其中B 到H D到卜的距离为1，B到C和D到C的距离为0.5.下面分别考虑在时刻t = 0 , 1 ,2 . 时蚁群的运动情况.如图2b,在时刻t = 0 ,设有30只蚂蚁从A运动到B. 此时路径BHBCh没有外激素（蚂蚁

12、留下的信息量），故蚂蚁将以相同的概率向BC BH运动，于是各有15只蚂蚁分别选择路径BH和BC.在真实蚁群中，外激素的数量会随时间的流逝而蒸发掉一部分， 为说明方便， 此处假设： 所有蚂蚁运动的速度相等； 外激素蒸发量与时间成正比例，即路径上外激素的剩余量与路径的长度成反比； 蚂蚁选路的概率与所选路上外激素的浓度成正比.因为路径BHD的长度是路径BCD勺2倍，当B点的蚂蚁到达D点后，路径BCDt的外激素是BHDt 的2倍.如图2c，在时刻t =1有30只蚂蚁从E到达D.因为路径DC上的外激素 量是DH1的2倍，根据蚂蚁选路特点，将会有20只蚂蚁选择DC而只有10 只蚂蚁选择DH.以此类推，当t

13、 = 2 ,3 ,4.时，将会有更多的蚂蚁选择路径BCD经过较长时间运动后，蚁群最终会沿着最优路径 ABCD运 动.网络的路由问题与蚁群寻路的问题有很大的可比性，都是寻找可以到达目的地的最优路线.目前已经证明蚁群算法在解决路由问题上具有分布式、正反馈、全局收敛等优点3.2求解准备1）根据已知位置点的坐标和连接情况，使用Matlab做出各点位置图如下:图2各点位置与连通情况图2）根据已知各点坐标，由两点间距离公式 d （咅_x2）2 （% y2）2求得图中相邻连通点间的距离如下表：表1相邻连通点距离表序号点1点2距离（m）序号点1点2距离（m）序号点1点2距离（m）113191631162320

14、986138361537218286432172317756239271780322078233318312104634034163142422933419242259644045321753819583520221499654144236663435363621262192664137260274222933721362880674146273585155005382117182468424391895212533922301287694249197110611294402317177570433826181171859184124311780714448215312711968422541

15、41557244504987138121757432519196673455031031491426814425291886744542235215910194645273110687546481494161018591046283313267647402331171072059472922109877484421531811121418483028101878495035691912131457493041499879494219712012255757503126153780504030432112154806513134232581O182182221318311352323511148

16、2O2117972313193456533223131283O261392241311167054334637592514185342553328132626141626085634401631271417219657353814102814213297583645318229152228615936272204301525423560374020903.3模型的求解331 问题1问题1要求将1 30号货物送到指定地点并返回，不考虑各货物的送达时间，3030考虑到W =48.5 ：50，且7 Vi =0.88 ： 1，故不用考虑重量、体积对送货次数i =0i =0的影响，即只需一次送货，无需中

17、途返回取货.方法一：Floyd算法+二次逐项修边法1 由表1中的数据，做出图G(V,E)的邻接矩阵A(0)，根据Floyd算法，求 得任意两点间的最短距离 A(51)；2 经过分析，发现运送130号货物只涉及22个点(含V。)，由于其中21 个送货点中有5个含2货物，2个含3货物；3、将这22个顶点令为点集Xi=(ai,bJ，0,1,2J|,21 ，令矩阵B为仅含有点Xi的最短距离方阵，构成加权图完备图 G-(V,E )；052965094749336212182179753954709139239972929670752544677621557776885975188337860117225

18、2960845611063 891631147092106915714668862855217120037542848910026 8065917313562 12645 11671155345094845602608219653423297397088065489809370265282935061777714987310981 11250 10333 935913222749311063 26080387279505696209811205 788896759425341011750 7471593311454 13380 946985521065311441362189162196387

19、2058031824177573334016662055533086787747045610840095089146822978871111821823114534279505803039797577388435743171210488894428537569134951605910449 95318558124201797709232975696182439790359855092192479737294910605428804418657676847954703660639925539510691 3970209817757577359809107579075777327131296525

20、3733836935711283 737264548556934347095714880611205 7333388455099107033172848178091134105505265894628573610125 9208823412097139266885489788840163574219257903317026051537710238624809634643855493988289657991118543997628580939675662031714797757728482605010686265339322043741178050237278636053869249292952

21、17702694255553210437297327178015371068073332325327248092848395683457428645410317670712003 52823410308688894910131291137102626573330965840612524804510461 606051427244803152547542935011750 78774428605496524105386233932325965805596713451721631720081174848824346778489617774714704537528805373505248092204

22、32724061559601537398464005074415631837045621510026 7714593356106913441838366589634637414809252471341537055217937353626184720550857778065987311454 8400495165769357462843851780284880455172398455210680390578140716611029688591731098113380 95086059768411283 57365493502339561046116316400793768030556964863

23、2176612975113562 11250 9469914610449 7954737210125 988272788345606072005074353690575569091823521971883312645 10333 855282299531703664549208896563607428514281174156261881406486918032692889786011671 935910653 78878558606385568234799153866454724448483183472071663217235232690432311722 15534 13222 11441

24、11118 12420 9925934312097 11854924910317 803182437045550811029 66121971288943230图3加权完备图G '勺邻接矩阵4、将P(V,E,w)的邻接矩阵B(i,j)通过经典货郎担问题的解法，即二次逐项10修边法，求得最优的Hamilton圈.Hmiton. cppint tradek/ int匚shnju_ txt -记事本文件® 編辑 格式 查看迪 帮肋（Wint if j ；coiif dpn-l k!=return dpn-：22e 5296 5094 7493 3621 2182 1797 5395

25、 M7095296 0 S456 11063 S916 3114 7092 10691 57C: Docuaent s and SettingsAd*inist rator桌面'数模'哈審軸-动态垛划Ea>Ishuju *txtU?0e0 5 1 S 11 IB 16 13 17 18 20 1? 21 15 14 12 7 3 2 4 & 9 0陰按任意犍继续-图4方法一运行结果截图程序012345678910图013141617182123242627程序1112131415 11617181920r 21图3132343638394042434549表2程序

26、中点的数字与图 1中的对应转换1600012C00图5路线示意图11路线:0->18->13->19->24->31->27->39->31->34->40->45->42->49->42->43->38->36->38->35->32->23->16->14-> 17->21->26->0路程：C = 54708 (m方法二：蚁群算法蚁群算法中、-等参数对算法性能有很大的影响。：值的大小表明留 在每个结点上的信息量受重视的程度，:值

27、越大，蚂蚁选择以前经过的路线的可 能性越大，但过大会使搜索过早陷于局部最小解； 1的大小表明启发式信息受 重视的程越大，蚂蚁选择离它近的城市的可能性也越大； t表示信息素的保留 率，如果它的值取得不恰当，得到的结果会很差。对比蚁群算法模型中，、的取值情况发现若 二取默认值 =1时 所得最优值和平均值比取其他值更好，此时它的最优值和最差值之差也最小。 这说明解的质量和稳定性都是最好的， 所以模型中的最佳设置应为1。对于一：， 其值在15之间逐渐增大，取、1默认值时，模型所得解的质量越来越高。当 的取值超过5时，所得解的质量开始下降，所以它们的1最佳设置为5;随着T的 取值在0. 31逐渐增大，所

28、得的解越来越好，但 亍应该小于1;而模型中，t值 在0. 30 . 9之间变化，解变化不大，当其取值为0. 5时，解的质量最优，建 议t取0. 5。蚁群从同一地点或不同地点同时出发，按照按照下面的概率公式逐次访问各个城市节点：'（厲和小如申Pk=”¥'如果rJkJ0,其他其中禁忌列表TabUk是保存了每只蚂蚁k已经访问过的城市的集合Jk =N Tabu、1是系统参数，分别表示信息素、距离对蚂蚁选择路径的影响程度；j表示由城市i到城市j的期望程度，可根据某种启发算法具体确定，一般为1/dj；.j为边L（i,j）上的信息素强度。当蚁群完成了所有的节点的访问后，在原路返回的

29、过程中，根据所得的解的 好坏去修改路径上的信息素强度，以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最后判断系统是否满足停止的条件（停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等），如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行， 将所得的结果输出。从上面可以看出，蚁群优化算法的基本思想就是质量越好的 解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习 的过程，得到了最短路径，即全局最优解。通过MATLAB7.0运行程序得到如下输出结果：Shortest .Route =Colurans 1 thro

30、ugh2019 2221 IS M !2 I 1792Columns 19 through 221ID?5Shgrt eErt_LBngh =54709在下面同时附上运算过程中，蚁群算法中得到的近似最优解集（从中我们得 出最优解）：R-Best（每代的最优路径）19->20->22->21->18->14->12->11->17->6->2->9->10->1->7->5->3->4->8->13->16->1512->11 ->1

31、7->15->16->20->19->22->21 ->18->14->10->1 ->7->5>8>13>4>3>6>2>915>16>20>19>22>21>18>14>12>11>17>9>6>2>1 ->10->7->5->3->4->8->133->4->8->13->15->16->20->19->

32、22->21 ->18->14->12->11 ->17->9->2->6->1 ->10->7->5L-Best (每代最优距离)57057569775599354709根据程序中数字和题目中数据的对换。得到如下解：路线:0->18->13->19->24->31->27->39->31->34->40->45->42->49->42->43->38->36->38->35->32->23-

33、>16->14->17->21->26->0路程：C = 54709 (m)3.3.2 问题2问题2是有时间约束的线路规划问题.遗传算法（genetic algorithm ，简称GA） 是一种解决复杂问题的有效方法，具有很强的通用性.本文根据线路规划问题的 特点，基于GAt立了一个适用于带有时间约束的送货路线规划模型.实验证明了 此算法的有效可行性.表3列出了各货物的时限信息，考虑到多货一点的情况，将货物所需送达地 点按1,2,，21顺序编号（实际节点为22个，含0点），由表可知货物1、2、 30需要在9:00前送到，货物3、21、24、25、26需要在9

34、:30前送到，其余在 12:00前送到.货员每到达一个地点，交接一件货物花费都为3分钟，交接完毕马上前往下一个地点，期间不花费时间；送货员的速度保持匀速，保持24公里/ 小时.表3各货物时限信息表货物号送达地点不超过时间货物号送达地点不超过时间货物号送达地点不超过时间1139:0011459:3021319:302189:00124310:15222712:003319:30133912:00232612:0042612:0014459:3024349:3052112:00154210:1525409:3061412:00164310:1526459:3071712:00173212:0027

35、4910:1582312:00183612:00283212:0093212:00192712:00292312:00103810:1520249:00301612:0022点之间的距离矩阵D=(dj )22 22即如图2;则问题是求一个从点0出发，在满足时间约束条件下，走遍所有中间点，至V达点21的一个最短路径.求解的遗传算法描述如下：(1) 解空间S记门为0,1,2, H |,21的所有固定起点和终点的循环排列集合，即：Q=(二 1,山,二 22)丨二1 ",(二2川I,二 21)为1,2,20的循环排列，二 22 =21其中以：二j表示在第i次侦察第j点.解空间S是满足时间约束

36、的门的子集(2) 编码策略采用十进制编码，用随机序列-'Q -2'21作为染色体，其中0<1 (i =1,2,川,20)尬O=o,co21=1.每个随机序列都和种群中的一个体对， ;应，例如一个9目标问题染色体为：0.23, 0.82, 0.45, 0.74, 0.87, 0.11, 0.56, 0.69, 0.781其中编码位置i代表目标i，位置i的随机数表示目标i在路径中的顺序，我们将这些随机数按升序排列得到如下路线：6- 1 -3-7-8-4-9-2-5(3) 适应度函数适应度函数f12?ll,22)定义如下（二 1,二2,川,(二1,川,匚22)S(二 1,川,.

37、二 22)一 S即合法染色体的适应度定义为运行时间的倒数，不满足时间约束的非法染色体的 适应度定义为0.(4) 交叉操作我们的交叉操作采用单点交叉.设计如下，对于选定的两个父代个体£ 们2川如21, f2 =®1叫11121我们随机地选取第t个基因处为交叉点，经过交叉运算后得到的子代编码记为&和S2,3的基因由h的前t个基因和f2的后22-t个 基因构成，S2的基因由f2的前t个基因和f的后22t个基因构成，例如：10,0.14,0.25,0.27,|0.29,0.54,|HQ19,11f 0,0.23,0.44,0.56,|0.74,0.21，川,0.24,1设交

38、叉点为第四个基因处，则- 10,0.14,0.25,0.27,|0.74,0.21,1,0.24,11s2 - O0.23,0.44,0.56,|0.29,0.54|,0.19,11交叉操作的方式有很多种选择，我们应该尽可能选取好的交叉方式，保证子代能继承父代的优良特性.（5 ）变异操作变异也是实现群体多样性的一种手段，同时也是全局寻优的保证.我们的变异 米用两种方式.1）对选定变异的个体，随机地取三个整数，满足1乞u ： v ： w乞21，把u，v之 间的基因段插到w后面.2）调整有时间限制的对应基因位置，使染色体对应的路线序列满足时间约束， 得合法染色体.为了加快算法的速度，我们对所有的染

39、色体都进行变异，其中一 半染色体进行方式1）的变异，一半染色体进行方式 2）的变异.选择采用确定性的选择策略，也就是说选择适应度最大的个体进化到下一代，这 样可以保证父代的优良特性被保存下来.在每一代个体的选择中，如果种群的数 量不够的话，我们再生成一些染色体，适当调整有时间要求的送货位置对应基因 的位置，使之成为合法的染色体.计算结果及结论使用上述算法，计算时的参数如下设置：种群大小M -50，最大代数G=1000，交叉概率巳=1，变异概率=1.我 们的计算结果为总用时为t = 38.67 hour相对于现代优化算法中的其它算法，我 们的上述算法可以实时地求得一个较满意的解.路线结果如图所示

40、：16000IM4(KOKOO60©10M01)00IO1£«图5问题2路线示意图线路：0->18->13->19->24->31->34->40->45->49->42->43->38->36->27->39->27->36->38->35->32->23->16->14->17->21->26->0表4问题二解法中各点运行情况表路径距离路程用时（min）路程加送货用时（min）到达时间离开时间时间要求

41、0-182182588:058:089:0018-1331148118:168:199:0013-193456998:288:2812:0019-242259698:348:379:0024-3117804108:418:479:3031-342325698:538:569:3034-401631479:009:039:3040-4532178179:119:209:3045-422352699:269:2912:0042-491971589:349:3710:1549-421971559:429:4210:1542-43918289:449:5010:1543-3826187109:5710

42、:0010:1538-3615374710:0410:0712:0036-27220461210:1310:1912:0027-3917804710:2310:2612:0039-2717804410:3010:3012:0027-3622046610:3610:3612:0036-3815374410:4010:4012:0038-3514104410:4410:4412:0035-32111431210:4710:5612:0032-2313123910:5911:0512:0023-1620985811:1011:1312:00162011:2312:0014-

43、1721965811:2811:3112:0017-2118245811:3611:3912:0021-26219251111:4411:5012:0026-013923311:53-总计56980142232-333 问题3由于第三个问题中，加入了体积和重量限定的因素，因此就势必要求送货员 需要返回0点取货，这样就要需要几次往返才能完成任务。根据计算，本问题中 货物的总质量是148千克，总体积是2.8立方米。因此直觉上估计需要三四个来回 才能将所有的货物送完。为了减少送货员行进路程中重复的量， 我们采用分块的 原则将图形分开，分区域进行送货。然后对每块区域进行最短距离解的计算，由此得出全局的

44、最优解。基于这样的想法，我们采用分割求解法和蚁群算法结合的 方式求解第三个问题。分割求解法的基本思想：分割求解的关键在于正确分割。正确分割的判定标准是子问题的最优解是否 能通过连接分割前设定的固定连接点，形成原问题的最优解。图6是一个简单的旅行商问题的分割求解示意图。图6将顶点集I，2, 3, 10，II , 12分成子问题一，其余顶点分成子问题二。其次，在子问题中分别选择固 定连接点3， 10）和4，9。然后对子问题分别求最优解如图所示，在最后合成 时，可以连接分割前设定的固定连接点，分别连接 3，4）和9，10，打破相应 的边，将子问题的解合成为原问题的解。容易看到，这个解是原问题的最优解

45、。图7的例子与图6的相同，将点11错误的划分，造成分割错误。如图所示，尽管各 子问题的解仍然是相应子问题的最优解，但最后合成的解已不是原问题的最优 解。| 4*+ n li7图7错误的分割求解t +5 3*9- 3二+他攔诩1子冃羅一子简試二合咸園韓舫图6是一个简单的例子，很容易人工分割，但现实的例子往往很复杂。显然， 想人工分割是不大可能的。为了解决这样的问题，我们用如下方法：首先引入共同边：如果边i，j在所有的近似解中都出现，则将此边称为共 同边。共同边属于最优解的比率普遍大于 90%，有的甚至为100%。共同链：假设最优近似解中有一条链a，b，c，d，e，r，g，h，i，j，k）， 其中

46、a，b和j，k是共同边，如在近似解集合中，共同边a，b）和j，k之间 的顶点集都是c , d, e, f, g, h, j,仅仅顶点排序有不同一一例如：d , f, g, e, c, i , h，那么就把链b , c, d, e, f, g, h, i , j称为共同链。显然， 可以把首尾相连的共同链合成为更大的共同链。本算法中，把共同链作为分割旅行商问题的依据，这种算法可以成功分割一些有规律的旅行商问题。在最优近似解中，共同链的分布不是唯一的，但是有这的原则，分割线经 过共同链的成分越多，其部分解覆盖全局最优解的概率越大。基本步骤1）独立运行蚁群算法，保留k个最优近似解组成近似解集合。如果一

47、个近似 解实际上是最优解，则不保留，否则近似解集合中包含了最优解，分割实验就没了意义。2）在近似解集合中，寻找共同边。3）在最优近似解中寻找共同链分布。共同链分布不是唯一的，依据前述的原 则寻找最好的分布。4）合并较小的共同链，使得最终只有2->3个大的共同链，再以此来进行分 割。关于蚁群算法基本思想由于在第一问中已经有所介绍这里不再赘述。根据这样的思想，我们首先利用蚁群算法，寻找若个个近似最优近似解组成 的近似解集合。利用MATLAB我们得到这样的近似解集。R-Best= 9->12->13->14->19->32->28->40->46

48、->37->39->36->33->24->18->22- ->1->27->25->20->26->30->23->31->29->34->47->49->45->42->38->41- ->35->48->51->50->43->44->17->15->10->11->8->2->7->4->5->3-> 6->16->21 ,6- ->

49、;3->5->4->2->7->8->11->10->15->18->22->1->27->32->28->40->37- ->39->36->33->24->17->44->43->50->51->46->41->35->48->38->42->45->49->47->34->29->31->23->30->26->20->25->19-

50、>14->12->13-> 9->21->16,21->23->30->26->20->25->32->28->40->37->39->36->33->24->18->22 _->1->27->19->14->12->13->9->4->2->7->8->11->10->15->17->44->4 3->50->51->46->41->35

51、->48->38->42->45->49->47->34->29->31->16->6->3->5 ,12->13->9->4->2->7->8->11->10->15->17->24->18->22->1->27->32- >28->40->37->39->36->33->44->43->50->51->46->41->35->48-&g

52、t;38->42- ->45->49->47->34->29->31->23->21->30->26->20->25->19->14->16->6->3->5 ,4->2->7->8->11->10->15->18->22->1->27->32->28->40->37->39->36- ->33->24->17->44->43->50->51->46->41->35->48->38->42->45->49->47->34->29->31->23->21->30->26->20->25->19->14->13->12->9->16-&g