直送式配送运输的方法

1、直送式配送运输的方法2目前求解最短线路问题的方法很多，如位势法、“帚”形法、动态法等。现以位势法为例，介绍如何解决物流网络中的最短线路问题。已知物流网络如图所示，各结点分别表示为A、B、C、D、E、F、I、J、K，各结点间的距离如图所示，试确定各结点间的最短线路。寻找最短线路的方法步骤如下：第一步：选择货物供应点为初始结点，并取其位势值为“零”即VI = 0；第二步：考虑与I点直接相连的所有线路结点。设其初始结点的位势值为VI，则其终止结点J的位势值可按下式确定：VJ = VI + LIJ式中，LIJ为I点与J点之间的距离。第三步：从所得到的所有位势值中选出最小值，此值即为从初始结点到该点的最

2、短距离，将其标在该结点旁的方框内，并用箭头标出该连线IJ，以此表示从I点到J点的最短线路走法。如图所示。第四步：重复以上步骤，直到物流网络中所有结点的位势值均达到最小为止。最终，各结点的位势表示从初始结点到该点的最短距离。带箭头的各条连线则组成了从初始点到其余结点的最短线路。分别以各点为初始结点，重复上述步骤，即可得各结点之间的最短距离。例在物流网络图中，试寻找从供应点A到客户K的最短线路。解：根据以上步骤，计算如下：(1)取VA = 0；(2)确定与A点直接相连的所有结点的位势值：VB = VA + LAB = 0 + 6 = 6VE = VA + LAE = 0 + 5 = 5VF = V

3、A + LAF = 0 + 11 = 11VH = VA + LAH = 0 + 8 = 8(3)从所得的所有位势值中选择最小值V_E=5，标注在对应结点E旁的方框内，同时用箭头标出连线AE。即minVB,VE,VF,VH = min6,5,11,8 = VE = 5(4)以E点为初始结点，计算与之直接相连的D，G，F点的位势值。VD = VE + LED = 5 + 2 = 7VG = VE + LEG = 5 + 14 = 19VF = VE + LEF = 5 + 4 = 9(5)从所得的所有剩余位势值中选出最小值6，标注在对应的结点B旁，同时用箭头标出连线AB。即minVB,VH,VD

4、,VG,VF = min6,8,7,19,9 = VB = 6(6)以B点为初始结点，计算与之直接相连的D，C点的位势值。VD = VB + LBD = 6 + 10 = 16VC = VB + LBC = 6 + 11 = 17同一节点有多个位势值，则只保留最小值，即取VD=7。(7)从所得的所有剩余位势值中取最小值VD=7，标注在与之相应的D旁的方框内并用箭头标出其连线ED。即min8,7,19,9,17 = VD = 7如此继续计算，可得最优路线如图所示，由供应点A到客户K的最短距离为24。依照上述方法，将物流网络中的每一个结点当做初始结点，并使其位势值等于“零”，然后进行计算，可得所有

5、结点之间的最短距离。如表所示。结点之间的最短距离物流网结点ABCDEFGHIJKA0613759178152024B60111011152314212630C1311068121921283337D71060261315222731E51182041213202529F91512640810172226G17231913128015222731H8142115131015071216I1521282220172270109J20263327252227121008K2430373129263116980节约里程法节约里程法又称节约算法或节约法，是指用来解决运输车辆数目不确定的问题的最有名的启发

6、式算法。节约里程法核心思想节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种. 节约里程法基本规定利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件；（1）所有用户的要求；（2）不使任何一辆车超载；（3）每辆车每天的总运行时间或行驶里程不超过规定的上限；（4）用户到货时间要求。2 节约里程法基本思想为达到高效率的配送，使配送的时间最小距离最短成本

7、最低，而寻找的最佳配送路线。例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有3台2t卡车和2台4t两种车辆可供使用。利用节约里程法制定最优的配送方案。1 第一步，作运输里程表，列出配送中心到用户及用户间的最短距离。1 第二步，按节约里程公式求得相应的节约里程数。1 第三步，将节约里程按从大到小顺序排列。1 第四步，根据载重量约束与节约里程大小，顺序连接各客户结点，形成两个配送线。1 P2P3P3P4P2P4P4P5P1P2P1P5P1P3P2P5P3P5P1P4得出结果：配送线路一：运量=1.7+0.9+1.4=4t运行距离=8+4+5+7=24km用一辆4t车运送，节约距离为18km配送线路二：运量=2.4+1