配送运输管理最短路径算法.ppt

第三节 配送线路的优化一、配送线路的优化方法㈠两点间直送式配送运输规划 —— 一对一配送的最短路线问题供应商客户7/30/20241 设某物流公司要把一批货物从下图的公路网络中的V1城运送到V6城网络中各边旁的数字表示相应两城之间的公路里程（公里）试问:汽车应走从V1到V6的什么路线才能使所行驶的里程最少？7/30/20242算法1：指定两点间最短路的Dijkstra标号算法•Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低•Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等7/30/20243•Dijkstra算法的基本过程是采用标号法在操作过程中有两种标号：暂时性标号T（Temporary Label) 和永久性标号P(Permanent Label)•给顶点Vi一个P标号P(Vi)时表示从指定点Vs到Vi的最短路的长度为P(Vi)，且Vi的标号不再改变。

•给顶点Vi一个T标号T(Vi)时表示从指定点Vs到Vi的估计最短路长的上界为T(Vi)，是一个临时标号7/30/20244•算法的每一步都把某一点或几个点的T标号改为P标号;当指定点Vt得到P标号时全部计算结束•对于有N个顶点的网络，最多经过N-1步运算就可得到从指定点Vs到指定点Vt的最短路的长度7/30/20245算法步骤•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}7/30/20246•Step3:比较所有具有T标号的顶点的标号，把最小者 改为P标号，即•当存在两个或两个以上最小T标号时，可以同时把它们都改为P标号当全部顶点均为P标号时，或当Vt得到P标号时，停止运算；否则用代替转回步骤27/30/20247首先求出从1出发的一条最短路径（1-2：4），求次短路径（2-5：2），依次类推： （5-6：8）， （5-4-6：7）， （5-4-3-6：6），最短距离求得的最短路径是：1-2-5-4-3-6距离是：4+2+6=12 7/30/20248•练习•求V1到V6的最短距离。

7/30/20249•Dijkstra标号算法还可应用于有向网络•例2 设有一个原油输送系统，油库为，码头为是三个中间阀门点管道长度已知原油由Vs经过中间阀门点流向码头为了使原油尽快输送到码头，应该沿哪一条线路输送7/30/202410㈡一对多配送的最短路线问题——分送式配送运输第三节 配送线路的优化一、配送线路的优化方法7/30/202411分送式配送运输•分送式配送是指由一个供应点对多个客户的共同送货•基本条件：同一条线路上所有客户的需求量总和不大于一辆车的额定载重量，送货时，由这一辆车装着所有客户的货物，沿着一条精心挑选的最佳路线依次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染7/30/202412节约里程法•Clarke 和Wright 于1964年提出该算法•节省里程法（Savings Algorithm） •VSP网络法（Vehicle Scheduling Program）•节约里程法的目标：根据配送中心的运输能力及其到客户之间的距离和各客户之间的相对距离来制订使总的配送车辆吨千米数达到或接近最小的配送方案。

7/30/202413节约里程法的基本思想PABbaPABba㈠㈡D1=2(a+b) D2=a+b+cD1-D2=2(a+b)-(a+b+c)=a+b-c＞0第二种方案比第一种方案要节约a+b-c的里程数c7/30/202414•节约里程法基本思想：节约里程法基本思想：•如果一个配送中心分别向N个客户配送货物，在汽车载重能力允许的前提下，每辆汽车在配送路线上经过的客户个数越多，里程节约量越大，配送线路越合理7/30/202415•节约法节约法的基本规定的基本规定：1.配送的是同种或相似的货物；2.各客户的位置及需求量已知；3.配送中心有足够的运输能力且满足：1.满足所有用户的要货需求；2.每辆车不能超载；3.每车每天总运行时间或行驶里程不能超出规定上限；4.方案能满足所有用户的到货时间要求7/30/202416步骤1：计算网络结点之间的最短距离步骤2：计算各客户之间的可节约的运行距离： a+b-c ,其中a 为P点至各点距离；b为P点至各点距离；c为两点间最小距离步骤3：对节约里程数按大小顺序进行排列步骤4：组成配送路线图7/30/202417节约里程法算例•配送中心P0向P1,P2,P3,P4,P5共 5个客户配送货物，该配送中心和5家客户之间的运输距离以及5家客户需要送货的数量已知（单位：运输距离：km；送货数量：吨）。

已知该配送中心备有额定载重量为2吨的卡车3辆，额定载重量4吨的卡车2辆•1.试利用节约里程法制定最优配送方案•2.设卡车行驶速度平均为40km/小时,试比较优化后的方案比单独向各用户分送可节约多少时间？7/30/202418该算例配送路线网络图10P1P0P2P4（1.4）P3P5（2.4）（0.9）（1.7）（1.5）12751241368121687/30/202419节约里程法基本步骤•Step1:作运输里程表，列出配送中心到用户及用户间的最短距离；•Step2:由运输里程表、按节约里程公式，求得相应的节约里程数，如上表（）内 ；•Step3:将节约里程进行分类，按从大到小顺序排列；•Step4:按“节约里程”的大小和客户的收货数量或重量，在车辆载重允许的情况下组成配送巡回路线图7/30/202420配送中心与用户及用户间最短距离7/30/202421节约里程数7/30/202422节约里程数排序7/30/202423初始方案P3P47（1.4）P0P2P5P1（2.4）（0.9）（1.7）（1.5）106887/30/202424二次解8 （（1.4））P0P2P3P4P5P1（（2.4））（（0.9））（（1.7））（（1.5））107548ⅠⅠ16ⅡⅡ7/30/202425•节约里程数为20km,故节约时间为20km/40km/小时=0.5小时7/30/202426练习：练习： 求求节节约约里里程程的的线线路路设设计计，，假假定定该该公公司司有有2T和和4T车车，，每每次次运运行距离不超过行距离不超过60KM。

147/30/2024277/30/2024287/30/202429cab7/30/202430(a+b-c=5+8-4=9)(5+7-7=5)(8+7-3=12)7/30/2024317/30/202432(5+8+7+5+4+12+9+12+6)*2=1367/30/2024337/30/2024347/30/2024357/30/2024367/30/202437。