《运输组织与管理》项目十-物流运输线路优化技术与方法

项目十物流运输线路优化技术与方法项目十物流运输线路优化技术与方法知识目标了解运输优化的方式与方法，了解图上作业法及表上作业法的基本原理。技能目标能够通过图上作业法及表上作业法对运输系统进行优化分析，并通过简单的计算完成对企业运输方案的选择。素质目标能坐得住，静下心，不怕难，敢于挑战，培养分析问题与解决问题的能力。引入案例广西康鑫全药业集团公司的配送择优思考题：应该如何安排，才能达到路程最近和时间及费用最省？任务一物流运输线路的选择优化一、单一装货地和单一卸货地的物流运输线路的选择优化——最短路径法路路通运输公司要把A点的一批化肥运送到J点，它根据这两个城市之间可选择的行车线路绘制的公路网络如图10-2所示。其中A点表示装货地，J点表示卸货地。此类运输线路的特点是A点和J点是两个点，不重合。这是运输活动中的一种情况。图10-2公路网络示意图最短路径法可以利用计算机进行求解。把运输网络中的线路（有的称为链）和节点的资料都存入数据库中，选好起点和终点后，计算机很快就可以算出最短路径。此计算的结果，称为单纯的最短距离路径，并未考虑各条线路的运行质量，不能说明穿越网络的最短时间。二、起点与终点为同一地点的物流运输线路的选择优化如图10-3所示，从V1经过V2、V3、V4、V5和V6回到V1，V1既是起点，也是终点。始发点和终点相重合的线路选择问题通常被称为“旅行推销员”问题、“货郎担”问题或者“中国邮递员邮路”问题。图10-3运输线路示意图起点与终点为同一地点（起讫点重合）的物流运输线路的选择优化，目标是找到一个可以走遍所有地点的最佳顺序，使运输车辆经过所有站点并且总距离或运输时间最短。这一类问题没有固定的解题思路，在实践中通常是根据实际情况的不同，结合经验寻找适用的方法。可以分为两种情况：1.规模很大规模很大，即包含的站点很多。某次运输在很多个站点的规模中找到最优路径，是不切合实际的。此情况不在我们讨论的范围内。2.规模比较小对于规模相对比较小的情况，可以应用经验试探法加以解决。三、多起点、多终点的物流运输线路的选择优化多起点、多终点问题的物流运输线路在物流运输实践中经常存在。如多个供应商供应给多个工厂，或者把不同工厂生产的同一产品分配到不同用户。在这些问题中，起点和终点都不是单一的。在这类问题中，各供应点的供应量往往也有限制。有多个货源地服务于多个目的地时，物流运输线路选择优化的任务是，要指定为各目的地服务的供货地，同时要找到供货地、目的地之间的最佳路径。解决这类问题常常可以运用一类特殊的线性规划方法，即物质调运问题图上作业法进行求解。任务二图上作业法的运算一、图上作业法的基本概念这是一种借助于流向流量图而进行货流合理规划的简便线性规划方法，它能消除环状交通网上物资调运中的相向运输（包括隐蔽相向运输）和迂回运输，得出总吨·千米最小的方案。这种方法对环状交通网上的货流规划行之有效，又被称为圆周关系法。它虽在20世纪30年代初已被人提出，但在我国得到广泛应用，却是新中国成立以后的事情。我国学者研究线性规划在管理中的应用，是从交通运输问题开始的。二、图上作业法的基本步骤（1）绘制交通图。根据客户所需货物汇总情况、交通线路、配送点与客户点的布局，绘制出交通示意图。（2）将初始调运方案反映在交通示意图上。任何一张交通示意图上的线路分布形态无非可分为成圈与不成圈两类。对于不成圈的运输，可按“就近调运”的原则制定调运方案。对于成圈的运输，可采用破圈法处理，即可得出初始调运方案。在绘制初始方案交通图时，凡是按逆时针方向调运的货物调运线路，其调运箭头线都画在圈外，称为外圈；否则，其调运箭头线都画在圈内，称为内圈。两种箭头以相反方向标注也可。（3）检查与调整。面对交通图上的初始调运方案，首先分别计算线路的全圈长、内圈长和外圈长（圈长指里程数），如果内圈长和外圈长都分别小于全圈长的一半，则该方案为最优方案；否则，为非最优方案，需要对其进行调整。三、图上作业法的具体方法1.运输线路不成圈的图上作业法线路不成圈的货物运输，即不构成回路的运输线路，包括直线、丁字线、交叉线和分支线等。只要不出现对流和迂回现象，就是最优调运方案。图10-6所示是某地区的物资供应网络，有①、③、⑥、⑧4个起运站，供应量分别为+7、+8、+6、+4单位（为了便于识别，供应量记“+”，需求量记“-”）；另有②、④、⑤、⑦4个目的地，需求量分别为-2、-8、-7、-8单位。为了便于检查对流现象，把流向箭头统一画在右侧。箭头旁边标注的数字表示调运量。具体调运方案是：从站点①开始，把7个单位的物资供应给②，②剩余5个单位，供应给③；站点④的8个单位由③供应；③剩余5个单位供应给⑤，⑤尚缺少2个单位，由⑥提供。⑧的4个单位经过⑥，连同⑥原有的4个单位合计8单位供给⑦。这样就得出一个最优调运方案。图10-6运输线路不成圈的调运方案2.运输线路成圈的图上作业法运输线路成圈，就是形成闭合回路的环形线路，可以是一个圈或者多个圈。图10-7包含两个圈：一是由①、②、③、⑤、⑥、⑦组成的圈；另一是由③、④、⑧、⑥、⑤组成的圈。圈可以是三角形、四边形和多边形。图10-7中的两个圈都是多边形。起运站（目的地）之间线路旁括号内标注的数字表示两点之间的距离。对于成圈运输线路的图上作业法，可以按照如下三个步骤求解，直到寻求到最优方案。成圈的线路流向图要同时达到既无对流现象，又无迂回现象的要求才是最优流向图，所对应的方案为最优运输方案。图10-7运输线路成圈的调运方案第一步：去段破圈，确定初始运输方案。第二步：检查有无迂回现象。第三步：重新去段破圈，调整流向。任务三表上作业法的运算一、表上作业法的基本概念表上作业法就是用列表的方法求解线性规划问题中运输模型的计算方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭回路法、位势法或矩形法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。运输问题是一类常见而且极其典型的线性规划（LinearProgramming，简称LP）问题。从理论上讲，运输问题可以用单纯型来求解。但由于运输问题数学模型具有特殊的结构，存在一种比单纯型法更简便的计算方法——表上作业法。与单纯型法相比，用表上作业法来求解运输问题可节约计算时间与计算费用，但表上作业法在实质上仍是单纯型法。利用表上作业法寻求运费最少的调运方案要经过这样三个基本步骤：首先依据问题列出调运物资的供需平衡表以及运价表；其次确定一个初始的调运方案；然后依据一个判定法则，判定初始方案是否为最优方案。当判定初始方案不是最优方案时，再对这个方案进行调整。一般来说，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案要少些，如此经过几次调整，就会得到最优方案。最小元素法是找出运价表中最小的元素，在运量表内对应的格填入允许取得的最大数，若某行(列)的产量(销量)已满足，则把运价表中该运价所在行(列)划去；找出未划去的运价中的最小数值，按此办法进行下去，直至得到一个基本可行解的方法。注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元素例外（同时划去一行和一列）。当填上一个数后行、列同时被满足（也就是出现退化现象）时，也只任意划去一行（列）。需要填入“0”的位置不能任意确定，而要根据规则来确定。

退化现象是指：当在平衡表中某一处填入一数字后，该数字所在的行和列同时被满足，即需方的需求得到满足，同时供方的供应数量也已经供完的现象。最小元素法的基本思想是：运价最小的优先调运，即从单位运价中最小的运价开始确定供销关系，然后次小，一直到给出初始基本可行解为止。位势法(potentialmethod)是在运输问题中，用来求非基变量的检验数和调整调运方案的方法。一般地，在调运方案中，凡有数字的格，都换上单位运价表中对应的运价，并在表的最右面和最下面增加一列和一行，通常用ui(i=1,2,...,m)和vj(j=1,2,...,n)表示，分别称为第i行和第j列的位势。若第i行第j列为数字格，则ui和vj之和等于表中基变量空格对应的运价数，即ui+vj=cij（cij为基变量空格中原运价数）。对已知的初始方案，只要先给出一个位势，则其他行、其他列的位势存在而且惟一由ui+vj=cij，即解方程可求出ui和vj。任一非基变量空格的检验数为Aij=Dij-Cij（Dij为非基变量空格中的原运价数；Cij=ui+vj为非基变量空格中的新生成运价数）。若所有的检验数Aij都非负，则该调运方案为最优方案，否则就需要调整，直至所有检验数均非负为止，调整的方法与闭回路法相同。二、表上作业法在运输问题中的应用【例】某公司下属4个储存某种物资的材料库，供应5个工地的需要。4个材料库的供应量和5个工