配送运输管理最短路径算法课件

第三节配送线路的优化

一、配送线路的优化方法㈠两点间直送式配送运输规划

——一对一配送的最短路线问题供应商客户3/23/20231设某物流公司要把一批货物从下图的公路网络中的V1城运送到V6城。网络中各边旁的数字表示相应两城之间的公路里程（公里）。试问:汽车应走从V1到V6的什么路线才能使所行驶的里程最少？3/23/20232算法1：指定两点间最短路的Dijkstra标号算法Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。3/23/20233算法的每一步都把某一点或几个点的T标号改为P标号;当指定点Vt得到P标号时全部计算结束。对于有N个顶点的网络，最多经过N-1步运算就可得到从指定点Vs到指定点Vt的最短路的长度。3/23/20235算法步骤Step1:给Vs以标号P标号0，即P(Vs)=0,其他各顶点Vi均给T标号，即T(Vi)=∞。Step2:若Vi是刚得到P标号的顶点，则考虑与Vi相邻的有T标号的所有顶点Vj,把这些顶点Vj的T标号修改为：T(Vj)=min{T(Vj),P(Vi)+Wij}3/23/20236Step3:比较所有具有T标号的顶点的标号，把最小者改为P标号，即当存在两个或两个以上最小T标号时，可以同时把它们都改为P标号。当全部顶点均为P标号时，或当Vt得到P标号时，停止运算；否则用代替转回步骤2。3/23/20237练习求V1到V6的最短距离。3/23/20239Dijkstra标号算法还可应用于有向网络。例2设有一个原油输送系统，油库为，码头为是三个中间阀门点。管道长度已知。原油由Vs经过中间阀门点流向码头。为了使原油尽快输送到码头，应该沿哪一条线路输送。3/23/202310㈡一对多配送的最短路线问题——分送式配送运输第三节配送线路的优化

一、配送线路的优化方法3/23/202311节约里程法Clarke和Wright于1964年提出该算法。节省里程法（SavingsAlgorithm）VSP网络法（VehicleSchedulingProgram）节约里程法的目标：根据配送中心的运输能力及其到客户之间的距离和各客户之间的相对距离来制订使总的配送车辆吨千米数达到或接近最小的配送方案。3/23/202313节约里程法的基本思想PABbaPABba㈠㈡D1=2(a+b)D2=a+b+cD1-D2=2(a+b)-(a+b+c)=a+b-c＞0第二种方案比第一种方案要节约a+b-c的里程数c3/23/202314节约里程法基本思想：如果一个配送中心分别向N个客户配送货物，在汽车载重能力允许的前提下，每辆汽车在配送路线上经过的客户个数越多，里程节约量越大，配送线路越合理。3/23/202315步骤1：计算网络结点之间的最短距离。步骤2：计算各客户之间的可节约的运行距离：

a+b-c,其中a为P点至各点距离；b为P点至各点距离；c为两点间最小距离。步骤3：对节约里程数按大小顺序进行排列。步骤4：组成配送路线图3/23/202317节约里程法算例配送中心P0向P1,P2,P3,P4,P5共5个客户配送货物，该配送中心和5家客户之间的运输距离以及5家客户需要送货的数量已知（单位：运输距离：km；送货数量：吨）。已知该配送中心备有额定载重量为2吨的卡车3辆，额定载重量4吨的卡车2辆。1.试利用节约里程法制定最优配送方案。2.设卡车行驶速度平均为40km/小时,试比较优化后的方案比单独向各用户分送可节约多少时间？3/23/202318该算例配送路线网络图10 P1

P0

P2

P4

（1.4） P3

P5

（2.4） （0.9） （1.7） （1.5） 12 7

5

12

4

13 6

8

12 16 8 3/23/202319配送中心与用户及用户间最短距离3/23/202321节约里程数3/23/202322节约里程数排序3/23/202323二次解8

（1.4） P0

P2

P3

P4

P5

P1

（2.4） （0.9） （1.7） （1.5） 10 7 5 4 8 Ⅰ16Ⅱ3/23/202325节约里程数为20km,故节约时间为20km/40km/小时=0.5小时3/23/2023263/23/202329cab3/23/202330(a+b-c=5+8-4=9)(5+7-7=5)(8+7-3=1