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

《送货路线-数学建模-一等奖》由会员分享，可在线阅读，更多相关《送货路线-数学建模-一等奖（26页珍藏版）》请在装配图网上搜索。

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

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

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

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

5、线总路程；：送货员送货次数；：送货所用总时间；：赋权连通图；：的第个子图；：子图中的最佳回路；：边的边权；：点的点权；：的各边权之和；：的各点权之和； ：送货中的停留时间；：送货员的行驶速度；点权.为叙述方便起见，我们在文中不加说明地使用上述变量和符号的变形形式，它们的含义可以通过上下文确定.3 模型的分析与建立3.1 模型的建立把快递公司送货地点示意图抽象为一赋权连通图，在权图中，对应示意图中的快递公司地点及货物送达点，表示快递公司所在地，对应示意图中路径.边权对应示意图中的路径长度.建立的数学模型如下：求中回路使得满足：（1）（2）（3） 或）为了讨论方便，先给出图论中相关的一些定义. 定

6、义1 经过图G的每个顶点正好一次的圈，称为G的哈密顿环路，也称Hamilton圈. 定义2 在加权图中 (1)权最小的哈米顿圈称为最佳Hamilton圈； (2)经过每个顶点至少一次且权最小的闭通路称为TSP回路问题.由定义2可知，本问题是一个寻找TSP回路的问题.TSP回路的问题可转化为最佳Hamilton圈的问题.方法是由给定的图构造一个以V为顶点集的完备图，中每条边的权等于顶点x与y在图中最短路径的权，即在图论中有以下定理：定理1 加权图的送货员回来的权和的最佳Hamilton圈的权相同；定理2 在加权完备图中求最佳Hamilton圈的问题是NPC问题.在解决问题的过程中，我们用到以下算

7、法：算法一（Floyd算法）：令表示一个矩阵，它的元素是1将图中各顶点编为确定矩阵，其中元素等于从顶点到顶点最短弧的长度(如果有最短弧的话)如果没有这样的弧，则令对于，令2对，依次由的元素确定的元素，应用递归公式每当确定一个元素时，就记下它所表示的路在算法终止时，矩阵的元素就表示从顶点到顶点最短路的长度算法二：求加权图的TSP问题回路的近似算法：1用算法一（Floyd算法）求出中任意两个顶点间的最短路，构造出完备图，2输入图的一个初始Hamilton圈；3用对角线完全算法产生一个初始Hamilton圈；4随机搜索出中若干个Hamilton圈，例如2000个；5对2、3、4步所得的每个Hamil

8、ton圈，用二边逐次修正法进行优化，得到近似最佳Hamilton圈；6在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳Hamilton圈的近似解.算法三：蚁群算法蚁群算法是一种新型的模拟进化算法.该算法由意大利学者M. Dorigo V. Maniezzo和A. Colorini 等人在90年代首先提出，称之为蚁群系统(ant colony system )，应用该算法求解TSP 问题、分配问题，取得了较好的结果.算法受到真实蚁群觅食行为的启发，科学家发现虽然单个蚂蚁没有太多的智力，也无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线.经过大量细致观察研究发

9、现： 蚂蚁个体之间通过一种称之为外激素(pheromone) 的物质进行信息传递.蚂蚁在运动过程中, 能够在它所经过的路径上留下该种物质， 而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流寻找最优的到达食物源的线路.蚁群算法具有实现简单、正反馈、分布式的优点.图1 蚁群算法说明在图1中， 从A到E（或者从E 到A）有两条路径（ABCDE 和ABHDE），其中B到H、D到H的距离为1，B到C和D

10、到C的距离为0.5.下面分别考虑在时刻t = 0 , 1 ,2 . .时蚁群的运动情况.如图2b，在时刻t = 0 ,设有30只蚂蚁从A运动到B.此时路径BH、BC上没有外激素(蚂蚁留下的信息量)，故蚂蚁将以相同的概率向BC、BH 运动，于是各有15只蚂蚁分别选择路径BH和BC.在真实蚁群中，外激素的数量会随时间的流逝而蒸发掉一部分，为说明方便，此处假设： 所有蚂蚁运动的速度相等； 外激素蒸发量与时间成正比例，即路径上外激素的剩余量与路径的长度成反比； 蚂蚁选路的概率与所选路上外激素的浓度成正比.因为路径BHD 的长度是路径BCD的2倍，当B点的蚂蚁到达D点后，路径BCD上的外激素是BHD上的

11、2倍.如图2c，在时刻t =1有30只蚂蚁从E到达D.因为路径DC上的外激素量是DH上的2倍，根据蚂蚁选路特点，将会有20只蚂蚁选择DC，而只有10只蚂蚁选择DH.以此类推，当t = 2 ,3 ,4. . . 时，将会有更多的蚂蚁选择路径BCD.经过较长时间运动后，蚁群最终会沿着最优路径ABCDE运动.网络的路由问题与蚁群寻路的问题有很大的可比性，都是寻找可以到达目的地的最优路线.目前已经证明蚁群算法在解决路由问题上具有分布式、正反馈、全局收敛等优点.3.2 求解准备1）根据已知位置点的坐标和连接情况，使用Matlab做出各点位置图如下：图2 各点位置与连通情况图2）根据已知各点坐标，由两点间

12、距离公式求得图中相邻连通点间的距离如下表：表1 相邻连通点距离表序号点1点2距离（m）序号点1点2距离（m）序号点1点2距离（m）1131916 3116232098 6138361537 2182864 3217231775 6239271780 32207823 3318312104 6340341631 4242293 3419242259 6440453217 5381958 3520221499 6541442366 6343536 3621262192 6641372602 7422293 3721362880 6741462735 85155005 3821171824 6842

13、43918 9521253 3922301287 6942491971 10611294 4023171775 7043382618 117185918 4124311780 7144482153 12711968 4225414155 7244504987 138121757 4325191966 7345503103 149142681 4425291886 7445422352 159101946 4527311068 7546481494 1610185910 4628331326 7647402331 171072059 4729221098 7748442153 181112141

14、8 4830281018 7849503569 1912131457 4930414998 7949421971 2012255757 5031261537 8050403043 2112154806 5131342325 81O182182 2213183113 5232351114 82O211797 2313193456 5332231312 83O261392 2413111670 5433463759 2514185342 5533281326 2614162608 5634401631 2714172196 5735381410 2814213297 5836453182 2915

15、222861 5936272204 3015254235 6037402090 3.3 模型的求解3.3.1 问题1问题1要求将130号货物送到指定地点并返回，不考虑各货物的送达时间，考虑到，且，故不用考虑重量、体积对送货次数的影响，即只需一次送货，无需中途返回取货.方法一：Floyd算法 + 二次逐项修边法1由表1中的数据，做出图的邻接矩阵，根据Floyd算法，求得任意两点间的最短距离；2经过分析，发现运送130号货物只涉及22个点（含），由于其中21个送货点中有5个含2货物，2个含3货物；3、将这22个顶点令为点集=，令矩阵为仅含有点的最短距离方阵，构成加权图完备图；图3 加权完备图G的邻

16、接矩阵4、将的邻接矩阵通过经典货郎担问题的解法，即二次逐项修边法，求得最优的Hamilton圈.图4 方法一运行结果截图表2 程序中点的数字与图1中的对应转换程序0 1 2 3 4 5 6 7 8 9 10 图013141617182123242627程序11 12 13 14 15 16 17 18 19 20 21 图3132343638394042434549图5 路线示意图路线：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路程：= 54708 （m）方法二：蚁群算法蚁群

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

18、设置为5；随着的取值在031逐渐增大，所得的解越来越好，但应该小于1；而模型中，值在03 09之间变化，解变化不大，当其取值为05时，解的质量最优，建议取05。蚁群从同一地点或不同地点同时出发，按照按照下面的概率公式逐次访问各个城市节点：其中禁忌列表是保存了每只蚂蚁k已经访问过的城市的集合,是系统参数，分别表示信息素、距离对蚂蚁选择路径的影响程度； 表示由城市i到城市j的期望程度，可根据某种启发算法具体确定，一般为; 为边上的信息素强度。当蚁群完成了所有的节点的访问后，在原路返回的过程中，根据所得的解的好坏去修改路径上的信息素强度， 以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最

19、后判断系统是否满足停止的条件(停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等)，如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行，将所得的结果输出。从上面可以看出，蚁群优化算法的基本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习的过程，得到了最短路径，即全局最优解。通过MATLAB7.0运行程序得到如下输出结果：在下面同时附上运算过程中，蚁群算法中得到的近似最优解集（从中我们得出最优解）：R-Best(每代的最优路径)19-20-22-21-18-14-12-11-17-6-2-9-10-1-

20、7-5-3-4-8-13-16-1512-11-17-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-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-3

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

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

23、0283212:0093212:00192712:00292312:00103810:1520249:00301612:0022点之间的距离矩阵即如图2；则问题是求一个从点0出发，在满足时间约束条件下，走遍所有中间点，到达点2l的一个最短路径.求解的遗传算法描述如下： (1)解空间记为的所有固定起点和终点的循环排列集合，即：=为的循环排列，其中以表示在第次侦察第点.解空间是满足时间约束的的子集.(2)编码策略采用十进制编码，用随机序列作为染色体，其中，；每个随机序列都和种群中的一个体对应，例如一个9目标问题染色体为：其中编码位置代表目标，位置的随机数表示目标在路径中的顺序，我们将这些随机数按升

24、序排列得到如下路线：(3)适应度函数适应度函数定义如下即合法染色体的适应度定义为运行时间的倒数，不满足时间约束的非法染色体的适应度定义为0.(4)交叉操作我们的交叉操作采用单点交叉.设计如下，对于选定的两个父代个体我们随机地选取第个基因处为交叉点，经过交叉运算后得到的子代编码记为和，的基因由的前个基因和的后个基因构成，的基因由的前个基因和的后个基因构成，例如：设交叉点为第四个基因处，则交叉操作的方式有很多种选择，我们应该尽可能选取好的交叉方式，保证子代能继承父代的优良特性.(5)变异操作变异也是实现群体多样性的一种手段，同时也是全局寻优的保证.我们的变异采用两种方式.1)对选定变异的个体，随机

25、地取三个整数，满足，把，之间的基因段插到后面.2)调整有时间限制的对应基因位置，使染色体对应的路线序列满足时间约束，得合法染色体.为了加快算法的速度，我们对所有的染色体都进行变异，其中一半染色体进行方式1)的变异，一半染色体进行方式2)的变异.(6)选择采用确定性的选择策略，也就是说选择适应度最大的个体进化到下一代，这样可以保证父代的优良特性被保存下来.在每一代个体的选择中，如果种群的数量不够的话，我们再生成一些染色体，适当调整有时间要求的送货位置对应基因的位置，使之成为合法的染色体.计算结果及结论使用上述算法，计算时的参数如下设置：种群大小，最大代数，交叉概率，变异概率.我们的计算结果为总用

26、时为t = 38.67 hour.相对于现代优化算法中的其它算法，我们的上述算法可以实时地求得一个较满意的解.路线结果如图所示：图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）到达时间离开时间时间要求0-182182588:058:089:0018-1331148118:168:199:0013-193456998:288:2812:0019-242259698:348:3

27、79: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:0010:1538-3615374710:0410:0712:0036-27220461210:1310:1912:0027-3917804710:2310:2612:003

28、9-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:0016-14260871011:2011:2312:0014-1721965811:2811:3112:0017-2118245811:3611:3912:0021-26219251111:4411:5012:0026-013923311

29、:53-总计56980142232-3.3.3 问题3由于第三个问题中，加入了体积和重量限定的因素，因此就势必要求送货员需要返回O点取货，这样就要需要几次往返才能完成任务。根据计算，本问题中货物的总质量是148千克，总体积是2.8立方米。因此直觉上估计需要三四个来回才能将所有的货物送完。为了减少送货员行进路程中重复的量，我们采用分块的原则将图形分开，分区域进行送货。然后对每块区域进行最短距离解的计算，由此得出全局的最优解。基于这样的想法，我们采用分割求解法和蚁群算法结合的方式求解第三个问题。分割求解法的基本思想：分割求解的关键在于正确分割。正确分割的判定标准是子问题的最优解是否能通过连接分割前

30、设定的固定连接点，形成原问题的最优解。图6是一个简单的旅行商问题的分割求解示意图。图6将顶点集l，2，3，10，ll，12分成子问题一，其余顶点分成子问题二。其次，在子问题中分别选择固定连接点3，10)和4，9。然后对子问题分别求最优解如图所示，在最后合成时，可以连接分割前设定的固定连接点，分别连接3，4)和9，10，打破相应的边，将子问题的解合成为原问题的解。容易看到，这个解是原问题的最优解。图7的例子与图6的相同，将点11错误的划分，造成分割错误。如图所示，尽管各子问题的解仍然是相应子问题的最优解，但最后合成的解已不是原问题的最优解。图6 正确的分割求解图7 错误的分割求解图6是一个简单的

31、例子，很容易人工分割，但现实的例子往往很复杂。显然，想人工分割是不大可能的。为了解决这样的问题，我们用如下方法:首先引入共同边：如果边i，j在所有的近似解中都出现，则将此边称为共同边。共同边属于最优解的比率普遍大于90，有的甚至为100。共同链：假设最优近似解中有一条链a，b，c，d，e，r，g，h，i，j，k)，其中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称为共同链。显然，可以把首尾相连的共同链合成为更大的共同链。本算法中，把

32、共同链作为分割旅行商问题的依据，这种算法可以成功分割一些有规律的旅行商问题。在最优近似解中，共同链的分布不是唯一的，但是有这的原则，分割线经过共同链的成分越多，其部分解覆盖全局最优解的概率越大。基本步骤1)独立运行蚁群算法，保留k个最优近似解组成近似解集合。如果一个近似解实际上是最优解，则不保留，否则近似解集合中包含了最优解，分割实验就没了意义。2)在近似解集合中，寻找共同边。3)在最优近似解中寻找共同链分布。共同链分布不是唯一的，依据前述的原则寻找最好的分布。4)合并较小的共同链，使得最终只有2-3个大的共同链，再以此来进行分割。关于蚁群算法基本思想由于在第一问中已经有所介绍这里不再赘述。根

33、据这样的思想，我们首先利用蚁群算法，寻找若个个近似最优近似解组成的近似解集合。利用MATLAB，我们得到这样的近似解集。R-Best=9-12-13-14-19-32-28-40-46-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-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-4

34、2-45-49-47-34-29-31-23-30-26-20-25-19-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-43-50-51-46-41-35-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-38-42-45-49-47

35、-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-6-3-5，6-3-5-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-38-42-45-49-47-34-29-31-21-2

36、3-30-26-20-25-19-14-13-12-9-16L-Best1.2782 e+0051.2881e+0051.2661e+0051.271e+0051.2583e+0051.2292e+005根据以上的结果，我们在图像上绘出共同链得到如图 图8 近似解共同链连接图由此根据此图得到分割的图形：图9 分区图如上图所示用棕色线条表示一号区域，用蓝色线条表示二号区域，用黄色线条表示三号区域。接下来我们将运用蚁群算法对每个区域进行最优求解求解一号区域图10 区域一利用MATLAB计算，得到输出结果如下：进过电脑数据和题目数据的变幻后得：路线：O-21-17-23-16-14-9-10-7-1

37、-6-1-8-3-4-2-5-15-12-11-13-18-O路程：=51440（m）求解二号区域图11 区域二利用MATLAB计算，得到输出结果如下：进过电脑数据和题目数据的变幻后得：路线： O-26-31-34-40-37-41-44-48-46-33-28-30-22-20-22-29-25-19-24-31-26-O路程：=39894（m）求解三号区域图12 区域三利用MATLAB计算，得到输出结果如下：进过电脑数据和题目数据的变幻后得：路线： O-21-17-23-32-35-38-43-42-49-50-40-47-40-45-36-27-39-27-31-26-O路程： = 42

38、173（m）最短总路程：（m）下面用表格说明每个区域的质量分配问题：区域的货物和体积分配表区域一区域二区域三地点编号质量/千克体积/立方米地点编号质量/千克体积/立方米地点编号质量/千克体积/立方米182.620.0908264.390.0619275.120.0687133.490.0364312.580.0622393.630.1035111.670.0682344.610.0428364.20.0381122.630.0484401.630.0484455.040.1383154.880.0745373.930.0381472.120.02351.410.0387411.410.0132

39、501.120.028421.150.0501441.260.0005492.360.07141.230.0006480.540.0542424.230.064531.630.0483465.850.1167433.960.113180.760.0346334.40.0627385.190.063711.260.025281.720.0583510.005560.540.0067300.060.0402327.440.17572.680.0622220.390.0001234.130.07345102.450.0299202.220.0814173.660.0778291.340.037292

40、.140.0087254.490.0111163.240.0527194.990.0511143.380.0591244.170.0954234.130.07345213.530.0724合计48.480.95855合计49.980.8752合计49.540.96625（注：23号点的货物等分后，分两次送出）4 模型优缺点分析优点l 对典型的TSP问题提供了一种实际简单的寻找最优解的方法，经过程序的验证，确实可行。l 在第三个问题，根据现有的TSP问题求解做出一定的改进，实现分割求解法和蚁群算法合成算法求解方法，通过局部求得全局优解。缺点l 对于典型TSP问题虽然我们用计算机模拟技术，得到了近似优解，但跟实际存在的最优解直接仍然有一定差距。l 对于求解问题中，对于一些问题我们基于一些假设，但是还是缺少证明，同时还应该加入一些数据修整的优化方法。参考文献：【1】 Richard Johnsonbaugh，Marcus Schaefer著，大学算法教程M，清华大学出版社【2】 燕忠， 袁春伟，用蚁群优化算法求解中国旅行商问题J,电路与系统学报【3】 黄厚生，求解TSP问题的新方法J，天津大学硕士学位论文专心-专注-专业