6章_配送路线选择与车辆调度方案.pptVIP

第六章 配送路线选择与车辆调度 学习要点： 单中心配送路线选择与车辆调度； 多中心配送路线选择与车辆调度。 第一节 单中心配送路线选择与车辆调度 一、单中心配送的节约法原理 单中心配送，是指一个配送中心向所属n个用户送货，各用户的需求量为bj(j=1,2,…,n)。假定以汽车作为配送车辆，配送车按其载重量的大小不同有p种，载重量为QK(K=1,2…p)的发送车有xK台,QK-1QK,且 （6－1） 解决这类配送问题的一种有效方法——节约法。节约法是由克拉克（Clarke）和怀特（Wright）提出来的，是一种启发式方法。 节约法的基本原理 如图6－2，由物流网点B0向两个用户B1、B2送货，B0至各用户的最短运输距离分别为d0,1和d0,2；用户需求量各为b1，b2；两用户之间的最短运输距离为d1,2。当用两台车分别对两个用户各自往返送货时，运输总距离为： 如果改用一台车巡回送货（假定汽车能够负荷b1、b2时），如图6－3，则总运输距离为 后一种方案比前一种方案可节约运输里程 式6—5称为节约量公式， 为B1和B2之间的节约量。 显然，将节约量大的两个用户 连接起来采用巡回方式送货， 则可获得较大的节约。 二、节约法的计算过程 设由配送中心B0向用户Bj (j=1, 2, …, n)送货，各用户需求量为bj；配送中心与用户间的最短距离为d0,j，用户之间的距离为di,j (i=1, 2, …, n; j=1, 2, …, n)；配送车按其载重量的大小不同有p种，载重量为QK(K=1,2…p)的发送车有xK台，QK-1QK。 假定： 计算过程如下： 先求初始解。 假定载重量最小的汽车台数是无限多的，即x1=∞。对每一用户各派一台最小的车往返送货，得一初始可行方案。显然这一方案的运输效率是很低的，而且x1=∞的假设实际也不存在。 然后迭代求满意解。 计算每两个用户之间的节约量，按节约法原理对方案进行修正。修正时，以节约量的大小为顺序，从大到小依次将节约量大的用户连接到巡回路线中，并考虑汽车载重量和各种车辆台数的约束。反复进行这样的修正，直至再没有可连接的用户时为止。 整个计算过程可在节约量表上进行。 下面用例子说明计算过程。 例：由配送中心B0向12个用户Bj (j=1,2,…12)送货，各点之间的运输里程和各用户的需求量见表6-1。表6-2为可供调度的车辆数目及其载重量。 表6-1 各点之间里程表（单位：公里） 表6-2 可供调度的汽车 解：由表6-1中的数据，按节约量公式（6-5）计算每两用户之间的节约量Si,j 列于表6-3，称节约量表。 表6-3 节约量表（单位：公里） 设ti,j(i=0,1,…,12; j=1,2,…,12；i≠j )表示i、j两点是否连接在一起的决策变量，并对其取值作如下定义： ti,j=1 表示i、j用户连接，即在同一巡回路线中； ti,j=0 表示i、j用户不连接，即不在同一巡回路线中； t0,j=2 表示j用户只与配送中心B。连接，由一台车单独送货。 根据以上定义，对任一用户j,有以下等式成立： 迭代求解： 第一步，求初始解 每用户各派一台车单独送货，得初始方案如表6—4。表中B0列中的数字为ti,j的取值。此方案的总行程为728公里。 按表6—4的初始方案，所用汽车台数如表6—5所列。 表6-4 初始方案 表6—5 初始方案所用汽车台数 第二步，按下述条件在初始方案表中寻找具有最大节约量的用户i、j （1）t0,i、t0,j＞0 i≠j； （2）Bi、Bj尚未连接在一条巡回路线中； （3）考虑车辆台数和载重量的约束。 如果最大节约量有两个或两个以上相同时，可随机取一个。 按此条件，在初始方案表6—4中寻到具有最大节约量的一对用户为：i=11,j=12，其节约量为92公里。将11和12两用户