(7.2.1)--6.1.1配送车辆调度与线路优化.pdf

配送车辆调度与线路优化任务引入任务引入腾飞配送中心的烦恼位于西安市长安区的腾飞配送中心主要为市内位于西安市长安区的腾飞配送中心主要为市内5 5家连锁便利家连锁便利店提供商品配送服务，其有店提供商品配送服务，其有3 3台台2t2t车和车和2 2台台4t4t车可满足日常业务车可满足日常业务需要。腾飞配送中心需要。腾飞配送中心P P0 0与客户以及客户间的距离、客户货物需与客户以及客户间的距离、客户货物需求量如下图所示：求量如下图所示：任务引入任务引入腾飞配送中心现行配送方案为从腾飞配送中心现行配送方案为从P P0 0分别向分别向5 5个客户派车送个客户派车送货。目前面临的问题是虽然能够基本满足客户的配送需求，但货。目前面临的问题是虽然能够基本满足客户的配送需求，但是配送中心的车辆资源调配紧张，配送成本过高，利润下降过是配送中心的车辆资源调配紧张，配送成本过高，利润下降过快，有时甚至出现亏本。快，有时甚至出现亏本。请为腾飞配送中心优请为腾飞配送中心优化设计新的配送线路，解化设计新的配送线路，解决目前在业务发展中所遇决目前在业务发展中所遇到配送烦恼到配送烦恼6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化一、节约里程法概述一、节约里程法概述节约里程法（节约里程法（VSP）也称为车辆调度程序法，是用）也称为车辆调度程序法，是用来解决运输车辆数目不确定问题的最有名启发式算法。来解决运输车辆数目不确定问题的最有名启发式算法。它最大的好处在于通过拼装运输提高配送车辆满积满它最大的好处在于通过拼装运输提高配送车辆满积满载率，减少车辆数的投入，同时使得配送线路节约的载率，减少车辆数的投入，同时使得配送线路节约的里程数最大。里程数最大。1.概念概念6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化一、节约里程法概述一、节约里程法概述节约里程法核心思想是依次将运输问题中的两个回路合并节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。到达到一辆车的装载限制时，再进行下一辆车的优化。几何学中的三角形一几何学中的三角形一边之长必定小于另外边之长必定小于另外两边之和两边之和2.核心思想核心思想3.基本原理基本原理二、节约里程法的基本思路二、节约里程法的基本思路配送中心配送中心P P配送中心配送中心P P客户客户A A客户客户A A客户客户B B客户客户B B方案一方案一方案二方案二方案方案配送路线配送路线配送距离配送距离方案一方案一P P-A A-P P-B B-P P2PA+2PB2PA+2PB方案二方案二P P-A A-B B-P PPA+PB+ABPA+PB+AB里程节约数为：里程节约数为：PA+PBPA+PB-ABAB6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化1.要求要求三、节约里程法应用要求三、节约里程法应用要求满足所有用户的需求满足所有用户的需求不使任何一辆车超载不使任何一辆车超载每辆车每天总运行时间或每辆车每天总运行时间或行驶里程不超过规定上限行驶里程不超过规定上限到货时间不得超过用户规定时间到货时间不得超过用户规定时间6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化基本假定配送的是同一种货物已知各用户的坐标（x，y）及需求量配送中心有足够配送能力2.基本假定基本假定6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化四、节约里程法计算步骤四、节约里程法计算步骤6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化第一步：计算配送中心到各配送点及配送点间的最短距离第一步：计算配送中心到各配送点及配送点间的最短距离第二步：根据节约里程公式计算出各用户间的节约里程数第二步：根据节约里程公式计算出各用户间的节约里程数并由大到小排序，编制节约里程顺序表并由大到小排序，编制节约里程顺序表第三步：第三步：根据节约里程顺序表、各配送点货物需求量及配根据节约里程顺序表、各配送点货物需求量及配送中心运力送中心运力 约束，完成配送车辆调度与线路优化，并绘约束，完成配送车辆调度与线路优化，并绘制出车辆配送路线制出车辆配送路线位于西安市长安区的腾飞配送中心主要为市内5家连锁便利店提供商品配送服务，其有3台2t车和2台4t车可满足日常业务需要。腾飞配送中心P0与客户以及客户间的距离、客户货物需求量如下图所示：五、节约里程法的应用五、节约里程法的应用试用节约里程试用节约里程法制订最优的法制订最优的配送方案配送方案6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化1.1.配送中心到各配送点及配送点间的最短距离配送中心到各配送点及配送点间的最短距离P1P2P3P4P5P0886710P112136P2413P39P4141518166.6.1 配送车辆调度与线路优化配送车辆调度与线路优化五、节约里程法的应用五、节约里程法的应用2.2.各用户间的节约里程数各用户间的节约里程数P2P3P4P5P1P2P3P40410120342106.6.1 配送车辆调度与线路优化配送车辆调度与线路优化五、节约里程法的应用五、节约里程法的应用3.3.节约里程顺序表节约里程顺序表序号序号路线路线节约里程节约里程1P1P5122P2P3103P3P444P1P245P4P536P2P427P1P316.6.1 配送车辆调度与线路优化配送车辆调度与线路优化4.4.根据节约里程顺序表及配送中心载重量约束，绘制配送路线根据节约里程顺序表及配送中心载重量约束，绘制配送路线6.6.1 配送车辆调度与线路优化配送车辆调度与线路优化课后练习某配送中心A要向所在城市B,C,D,E,F,G共6个客户点配送货物，如图所示，它们之间的距离（km）和每一处的配送货物量（t）见下图，运输车辆有2.5t和4t两种货车，试确定配送路线。