1、管理运筹学专题3管理运筹学专题三多回路运输问题求解2011/6/9小组成员：目录一、引言 3二、具体案例分析 3三、案例求解 43.1、LINGO软件求解 43.2、枚举法求解 63.3、指派问题解法（匈牙利算法）： 73.4、EXCEL求解 83.5、图论方法求解： 9四、约束条件下的配送方案 124.1、车辆载重5t 124.1.1需求变化后的情况 154.2、费用限制下的配送方案 154.2.1车载无限制下的配送 17五、参考文献： 18六、附录 18管理运筹学专题三案例一、引言运筹学中，对旅行商问题的研究一直很深入，并通过各类方法探求出合理的解决途径。旅行商问题（Traveling S
2、alesman Problem, TSP）字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 旅行商问题经过演变发展，与实际情况结合，演变出很多分支。例如中国邮递员问题（Chinese Postman Problem CPP），“一笔画”问题（Drawing by one line），配送路线问题（Route of Distribution），多个旅行商问题（Multiple TSP），多回路运
3、输问题（Vehicle Routing Problem, VRP）。多回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。 VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。二、具体案例分析某配送中心从A地出发（货源充
4、足），将货物配送至B、C、D、E各地用户，再返回A地，各地之间的距离（公里）见下表。试确定最短配送路线。自 至ABCDEA10753B11468C7478D4573E5883方法提示（以下方法供参考，但不限于这些方法，问题6至问题9必须完成）：1枚举法：可产生最优解，但如果配送点很多时（如10个点），此方法不行。2动态规划：假设无后效性，可得到一个满意解。由于问题本身实际有后效性，所以不一定能产生最优解。3指派问题解法（匈牙利算法）：当出现小范围回路时需对上述路线表做一定的调整，而且调整的方式很多，需讨论。4用图论的方法来求解此问题。5节约法（一种启发式算法）：可得到满意解，不一定是最优解。6
5、当B、C、D、E各处货物需求量分别为6.1吨、13.8吨、6.8吨、12.7吨时，配送车辆最大载货量为5吨，试用不同方法探求配送方案，并进行对比分析。7由于客户需求的变化，B、C、D、E各处货物需求量分别为6.8吨、13.8吨、6.1吨、12.7吨时，配送车辆最大载货量为5吨，试用不同方法探求配送方案，并进行对比分析。8对问题6，运输费用为1.6元/吨公里，每次装车、卸车费用各30元，空车（载货量少于0.5吨时按空车计收运费）返程费按0.8元/公里计算，试论证采用多大载货量（载货量有5吨、8吨、10吨、12吨、20吨几种规格）的车辆效果最好？9对问题6，运输费用为1.6元/吨公里，每次装车、卸
6、车费用各30元，空车（载货量少于0.5吨时按空车计收运费）返程费按0.8元/公里计算，试论证采用多大载货量（载货量允许为任意值）的车辆效果最好？三、案例求解3.1、LINGO软件求解MODEL: SETS:!初始设置; CITY / 1. 5/: U;!U(i)为地点编号; LINK( CITY, CITY):DIST, X;!DIST为两地间距离; ENDSETS!数据区; DATA: DIST =999 11 7 4 5 10 999 4 5 8 7 4 999 7 8 5 6 7 999 3 3 8 8 3 999; ENDDATA N = SIZE( CITY);!模型的大小; MIN
7、 = SUM( LINK: DIST * X);!目标函数为点距之和最小的路径; FOR( CITY( K): SUM( CITY( I)| I #NE# K: X( I, K) = 1;!对于线路中每一个地点只有一条路指向这个地点; SUM( CITY( J)| J #NE# K: X( K, J) = 1;!从这个城市出发只有一条路可以离开; FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:!如果连接cityk和cityj,则cityj = cityk+1; U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K,
8、J) + ( N - 3) * X( J, K); ); FOR( LINK: BIN( X); FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1);END最短路：U( 1) 0.000000 0.000000U( 2) 2.000000 0.000000U( 3) 1.000000 0.000000U( 4) 3.000000 0.000000U( 5) 4.000000 0.000000ACBDEA路长：7+4+5+3+3=223.2、枚举法求解建立所有路线表：路线路程总路程路线路程总路程ABCDEA11+4+7+3+328AC
9、BDEA7+4+5+3+322ABCEDA11+4+8+3+531ACBEDA7+4+8+3+527ABDCEA11+5+7+8+334ACDBEA7+7+6+8+331ABDECA11+5+3+8+734ACDEBA7+7+3+8+1035ABECDA11+8+8+7+539ACEBDA7+8+8+5+533ABEDCA11+8+3+7+736ACEDBA7+8+3+6+1034ADBCEA4+6+4+8+325AEBCDA5+8+4+7+529ADBECA4+6+8+8+733AEBDCA5+8+5+7+732ADCEBA4+7+8+8+1037AECDBA5+8+7+6+1036ADCB
10、EA4+7+4+8+326AECBDA5+8+4+5+527ADECBA4+3+8+4+1029AEDBCA5+3+6+4+725ADEBCA4+3+8+4+726AEDCBA5+3+7+4+1029由上表可以得出最短路线为：ACBDEA，此时的总路程为7+4+5+3+3=22（公里），所以我们通过枚举法得出最短配送路线为：ACBDEA，其最短总路程为22公里。3.3、指派问题解法（匈牙利算法）：根据计算结果可知，出现了两条回路：ADEA，BCB，最短路程为3+4+4+3+3+1=18公里。当前所求得的最佳路线方案并非是一个完整的封闭回路，而是分成了两条封闭的支路，不满足我们所要求的最佳完整封
11、闭回路。接下来，我们要拆分其中一条回路，需找新的更合理的最优路线。通常选择较短路线入手，即第条线路，可以设置人为障碍，使得从B到C的路线不可以被选择（或者从C到B的路线不可以被选择），相当于人为宣布了此路不通，寻找新的路线方案替代原有回路。同时，可以确定，无论找到什么样的路线方案，得到的新的总路程不会小于目前的总路程结果（18公里）。设置一：B到C的距离为M最佳路线：ACBDEA，最短路程为3+4+7+3+3+2=22公里。设置二：C到B的距离为M最佳路线之一：AEDBCA，最短路程为3+6+4+3+3+1+4+1+1-1=25公里，大于设置一的22公里。因此，最短配送路线为ACBDEA，总路
12、程为22公里。3.4、EXCEL求解出发地抵达地路程图ABCDEA99910753B11999468C7499978D4579993E5883999初始数据设置出现了两条回路：ADEA，BCB加入限制条件BC不通22ACBDEACB不通25ADBCEA因此，最短配送路线为ACBDEA，总路程为22公里。3.5、图论方法求解：图形可描述现实世界中许多状态变化，图形表达事物是现代科学技术中的一种重要手段。图形不仅形象直观，而且可以结合数据，可以数形结合便于汁算，因此图论内容是相当现实和必需的。旅行售货员问题是一个经典的组合优化问题，其实质是在一个带权的完全无向图中，找一个权值最小的回路。解法步骤1
13、在完全图中任选一点作为起始点，找出一个与始点最近的点，形成一条边的初始路，然后逐点的扩充这条路。步骤2设X表示最新加入到这条路上的顶点，从不在路上的所有顶点中，选一个与X最临近的点，把连接于点X的边加到这条路上，重复这一步，直到图中所有的顶点都完全包含在路中。步骤3把起始点和最后加入的顶点之间的边放入，得到回路。步骤如图：最邻近算法例图改进算法：但在实际中随着问题规模的增大用如上的近似算法解决问题是相当困难的，因为随着问题规模的增大，近似的程度也会增大，问题规模越大和精确解的相差就越大。因为这是一个离散的问题，对上述的算法进行改进，运用类似三角剖分的方法对于该问题做如下的近似算法。步骤1首先找
14、到所有边中权最小的一条边，然后以这条边为起始边用类似三角剖分的办法找到权和最小的三角形，删除最大的边。步骤2从下一个点出发继续按照步骤1的方法往下做，在这个过程中如果遇到不符合的情况则要按照邻近算法选择权最小的一条路径，然后以这条路的下一个顶点按照步骤1继续做。在最后的几个顶点中，如果按照上面步骤回到源点那么操作完成。但是如果没有形成回路，那么对最后2到3个顶点用近似邻近算法找到回路。步骤3对已经找到的边的权相加得到的就是旅行售货员问题的一个解。 图1在图1中，选点a作为源点，找到以此点为出发点的最小权边ae，并以此为三角形一边找到权和最小的三角形aed并删除最大权边ad（如图2），则以顶点a
15、和e为出发点分别找到最小权边以及最小权和三角形abc和bcd，接着分别比较这两个三角形的两条权较小的边权之和有bc+acCBA; ADEAS5=21+10=31S总=21+28+9+16+31=105公里BEA; ADCAS5=22+18=40公里S总=21+28+9+16+40=114公里4.2、费用限制下的配送方案当载货量为5吨时，参见问题6可知，最优路线为A与B之间往返一次；A与C之间往返两次；A与D之间往返一次；A与E之间往返两次；ACBA，ADEA。AB 30*2+5*10*1.6+0.8*10=148AC (30*2+7*5*1.6+0.8*7)*2=243.2AD 30*2+5*
16、5*1.6+0.8*5=104AE （30*2+3*5*1.6+0.8*3）*2=172.8ACBA此时车载4.9吨 30*2+7*4.9*1.6+4*1.6*1.1+30+0.8*11=160.72ADEA 此时车载4.5吨 30*2+4.5*5*1.6+3*1.6*1.8+30+0.8*5=138.64共计费用967.36元当车载量为10吨时：A与C之间需要往返一次 30*2+1.6*10*7+0.8*7=177.6A与E之间需要往返一次 30*2+1.6*10*3+0.8*5=112BCDE之间的需求剩余量为：BCDE6.13.86.82.7B地与C地需求量之和为：9.9吨； D地与E地
17、需求量之和为9.5吨；故路线为：最优路径为ACBA; ADEAACBA此时车载量为9.9吨 30*2+9.9*7*1.6+4*6.1*1.6+30+0.8*11=248.72ADEA此时车载量为9.5吨 30*2+9.5*4*1.6+3*2.7*1.6+30+0.8*3=166.16共计费用为：704.48元当载货量为20吨时，则BCDE6.113.86.812.7B地与C地需求量之和为：19.9吨； D地与E地需求量之和为19.5吨；故路线为：最优路径为ACBA; ADEAACBA 此时车载19.9吨 30*2+19.9*7*1.6+6.1*4*1.6+30+0.8*11=360.72ADE
18、A 此时车载19.5吨 30*2+19.5*5*1.6+6.8*3*1.6+30+0.8*5=282.64共计费用为：643.36元综上，采用20吨的载货量的车辆效果最好。4.2.1车载无限制下的配送根据4.2的分析ACBA 此时车载19.9吨 30*2+19.9*7*1.6+6.1*4*1.6+30+0.8*11=360.72ADEA 此时车载19.5吨 30*2+19.5*5*1.6+6.8*3*1.6+30+0.8*5=282.64共计费用为：643.36元故实际车载为19.9t时，车辆利用率最高，效果最好。五、参考文献：1李军. 非对称距离的旅行商问题的构造算法J.运筹与管理，2000
19、,9.2 许金星,吴素萍.旅行售货员问题的图论近似算法J. 计算机工程与应用,2009,45.3徐国松.Lingo软件在运输问题中的应用J.管理科学.4 霍佳震,张磊. 求解配送收集旅行商问题的启发式算法J.同济大学学报,2006.5邱家学. 中国邮递员问题的EXCEL求解J.科学实践.六、附录会议纪要：第一次会议：时 间：2010年6月4日晚21点地 点：思东八层参加人员：刘景华 周界村 夏蕾 罗炜罡 邓文涛 关明亮 刘庚记 录 人：刘景华会议的主题及内容：本次案例相比于前2次的案例有了很大的提高,案例本身具有灵活性,可以用多种方法进行求解,本次案例没有固定的要求,对于案例的丰富性与准确性有
20、了更深层次的要求.这次是我们小组第一次会议,主要完成的是明确本次案例的问题和初步的分工.具体分工如下，关明亮邓文涛负责枚举法相关问题的解答，夏蕾，罗炜罡负责匈牙利法的相关讨论，周界村选择动态规划法及节约法进行处理，刘庚负责图论解答方法。本人将解题资料发至组员邮箱，作为参考，方便解题。并尝试用数学软件解题，初步计划使用LINGO和EXCEL进行求解。并由我及时将大家的方案进行汇总，帮助大家解题。第二次会议：时 间：2010年6月6日下午16：00地 点：思东大厅参加人员：刘景华 周界村 夏蕾 罗炜罡 邓文涛 关明亮 刘庚记 录 人：刘景华会议的主题及内容：本次会议的内容是核对大家的最短路解题结果
21、。由于枚举法是最不易出错的，所以以枚举法的结果作为参照。夏蕾组负责的匈牙利法解题正确，同时和我所负责的EXCEL解题结果一样，出现两条回路，经过人工调整得到最优解。LINGO的解法正确。大家针对6,7,8,9题提出自己思路答案，对于无法提出思路的问题再进行讨论，由于第七题和第六题想类似，所以我们将讨论的重点放在第八题和第九题上。会议进行中，周界村和夏蕾同学针对邓文涛和关明亮枚举法发车的方式有不同见解，并提出散车运输成本会更低，运输过程和方式也更灵活化。同时鼓励周界村对动态规划和节约法进行尝试建立模型。第三次会议：时 间：2010年6月8日晚22点地 点：思东八层参加人员：刘景华 周界村 夏蕾 罗炜罡 邓文涛 关明亮 刘庚记 录 人：刘庚会议的主题及内容：在本次会议的最后组员对各题目都有了完整的思路并基本写出了题目的简要步骤，大家进行了核查修正了有遗漏的问
