配送方法与配送路线的优化课件.ppt

1、第六章 配送与配送中心第一节 配送概述一、配送的特点配送：将货物从物流节点送交收货人1.配送是从物流据点至用户的一种特殊送货形式。2.配送不是单纯的运输或输送，而是运输与其他活动共同构成的组合体。3.配送不是广义概念的组织物资订货、签约、进货及对物资处理分配的供应，而是以供给者送货到户式的服务性供应，是门到门服务。4.配送是在全面配货基础上，完全按照用户要求所进行的运送，是配和送的有 机结合。二、配送的意义和作用1.完善了输送及整个物流系统。2.提高了末端物流的经济效益。3.通过集中库存，可使企业实现低库存或零库存。4.简化手续、方便用户。5.提高了供应保证程度。三、配送种类1.按配送组织分类

2、：商店配送；配送中心配送。2.按配送商品种类及数量分类：单品种，大批量；多品种，少批量配送。3.按配送时间及数量分类：定时配送；定量配送；定时定 量配送；定时、定路线配送；即时配送。第二节 配送方法一、配货作业方法1.分货方式：将需配送的同一种货物，从配送中心集中搬运到发 货场地，然后再根据各用户对该种货物的需求量进 行二次分配。2.拣选方式：用分拣车在配送中心分别为每个用户拣选其所需货物。二、配送路线的确定原则1.确定目标 （1）以效益最高为目标的选择 （2）以成本最低为目标的选择 （3）以路程最短为目标的选择 （4）以t.km最小为目标的选择 （5）以准确性最高为目标的选择2.确定配送路线

3、的约束条件 （1）满足所有收货人对货物品种、规格、数量的要求 （2）满足收货人对货物发到时间范围的要求 （3）在允许通行的时间内进行配送 （4）各配送路线的货物量不得超过车辆容积和载重量的限制 （5）在配送中心现有运力允许的范围内第三节 配送路线的优化一、节约法的基本规定节约法确定配送路线的主要出发点是根据配送中心的运输能力（包括车辆的多少和载重量）和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的t.kmt.km数最小的配送方案。基本假设：1.配送的是同一种货物2.各用户的坐标（x,y）及需求量均为已知3.配送中心有足够的运输能力满足条件：1.使配送总t.km最小2.方案能满足

4、所有用户的要求3.不使任何一辆车超载4.每辆车每天的总运行时间或行使里程不超过规定的上限5.能满足用户到货时间要求二、节约法的基本思想和求解步骤A方案配送路线：p0pip0pjp0总的配送距离为：d0id0jP0PiPj（A）P0PiPjdij（B）B方案配送路线：p0pipjp0总的配送距离为：00biijjDddd0022aijDdd000abijijDDddd00ijabijijSDDddd令：如果有一个配送中心P0分别向N个用户Pj(j=1,2,3N)配送货物，在汽车载重能力允许的前提下，每辆汽车的配送线路上经过的用户个数越多，则配送线路越合理，总配送距离越小。节约法的解题步骤：例 设

5、某配送中心P0P0向12个用户Pj(j=1,2,312)Pj(j=1,2,312)配送货物。各用户的需求量用qjqj表示，从配送中心到各用户的距离为d0j(j=1,2,12)d0j(j=1,2,12)，各用户之间的距离为dij(I=1,2,12,j=1,2,12)dij(I=1,2,12,j=1,2,12)；各参数的数值分别见表6-16-1，6-26-2，配送中心有三种型号的车辆，每种车辆的有效载重量为Wi(I=1,2,3)Wi(I=1,2,3)，各车辆的载重量的数值以及每种车辆的数量见表6-36-3。问如何制定最优的配送方案。Pi123456789101112qj12001700150014

6、0017001400120019001800160017001100d0j91421232225323638425052表表6-1 配送距离相关参数配送距离相关参数WiWiW1W1W2W2W3W3载重量400040005000500060006000车辆数不限不限3 34 4P1P2P3P4P5P6P7P8P9P10P11P1251222212431353741495171716232630363644461021302737433137391928253341293129910162220283071113172527101610182066141612122081010表表6-2 各用户之

7、间的距离各用户之间的距离表6-3 车辆数量及载重量解：（1）选择初始方案1P2P3P.jP12P初始方案是分别向每个用户单独送货，且分派12辆载重量为4000的汽车分别完成任务。（2）利用节约量的求解公式和表6-1、6-2中的d0j、dij求出初始方案的 所有节约量Sij，计算结果见表6-4中每个数字格中坐上角的数字。例如：13010313Sddd为分析方便，设置一个状态参数t tijij，其定义为：（1）当单独用一辆汽车从配送中心P P0 0，向某个用户P Pj j送货时，状态参数 t t0j0j=2=2，见表6-4带括号数字。（2）如果某个车辆的送货路线经过了某两个用户P Pi i和P P

8、j j，那么状态参数 t tijij的值变为1，说明用户P Pi i与用户P Pj j之间有共同的送货线路。如果 P Pi i，P Pj j不在同一送货线路上，则状态参数t tijij为零。（3）在表6-4中，所有的状态参数均应满足下式：1012(1,2,3,.,)jNijijiijttjN 对初始方案，由于是向各用户单独送货，因此有：02(1,2,.,12)0(1,2,.,12;)jijtjtiij利用表6-1及总配送距离公式求得初始配送方案的总的配送距离S0。0012728NjjSdWiWiW1W1W2W2W3W3可用车辆数不限不限3 34 4实用车辆数12120 00 0表6-5 初始方

9、案的车辆分配（3）修正初始方案从表6-4中选出满足下列条件的节约量S Sijij的最大值S Smaxijmaxij。1.该最大节约量S Smaxijmaxij对应的两个用户P Pi i、P Pj j的状态参数t toioi、t tojoj均大于零2.状态参数t tijij必须等于零，即P Pi i与P Pj j不在同一配送路线上3.用户P Pi i、P Pj j的需求量q qi i、q qj j之和应小于现有车辆中某种型号的车辆的载重量从表6-4中找到的满足上述条件的最大节约量S Smaxijmaxij为S S11,1211,12=92=92。说明向P P1111、P P1212两用户单独送货

10、改为用同一辆车向它们同时送货所取得的送货距离的节约量最大，节约值为9292。找到S Smaxijmaxij后，将原初始方案修正为将原方案中用两辆汽车（型号W W1 1）向P P1111、P P1212分别单独送货改为仅用一辆W1汽车向P11P11、P12P12同时送货。修改后送货线路变为11条，汽车数量变为11辆，总配送距离为原方案的配送距离S S0 0减去最大节约量，即：10max72892636ijSSS参数变化：1.由于修改后的方案P P1111、P P1212在同一线路上，由状态参数定义应该为：t t1111,1212=1=1 2.由于t t1111,1212的值发生了变化，与其相关的

11、t t0 0,1111、t t0 0,1212的值也发生变 化，t t0 0,1111=1=1、t t0 0,1212=1=13.如果方案修改后，某个t t0j0j(j=1,2,12)(j=1,2,12)的值变为1，则把同一配 送路线上所有的q qj j相加作为新的q qj j值。WiWiW1W1W2W2W3W3可用车辆数不限不限3 34 4实用车辆数11110 00 0表6-7 修正方案的车辆分配（4）方案的进一步修正。以表6-6为基础对方案进一步修正。先找出满足规定的最大节约量Smaxij=S11,12=84，然后对 状态参数tij进行修改，t10,12=1。修改后，t0,12=0t0,1

12、0=1q10=q11=2800+1600=4400修正后的方案总的配送距离为S221max63684552ijSSSWiWiW1W1W2W2W3W3可用车辆数不限不限3 34 4实用车辆数9 91 10 0表6-8 再次修正方案的车辆分配依次类推，对方案进行一次次修正，直到按规定方法找不到满足要求的S Smaxijmaxij为止。该例题最终的最优配送方案为：1.配送线路为4条第一条：P0 P1 P2 P3 P4 P0,送货量为5800，选用汽车的载重量为6000。第二条：P0 P5 P0，送货量为1700，选用汽车的载重量为 4000。第三条：P0 P6 P8 P9 P0，送货量5100，选用

13、汽车的载 重量为6000。第四条：P0 P10 P11 P12 P7 P0，送货量为5600，选用 汽车的载重量为6000。2.配送总距离S=290。3.实用车辆数见表6-9。WiWiW1W1W2W2W3W3可用车辆数不限不限3 34 4实用车辆数1 11 13 3表6-9 实用车辆数2.某企业计划进行一项投资，经过研究，提出A、B两个方案，有关数 据如下表所示：项目A方案B方案投资额（元）年净收益（元）寿命（年）残值（元）300000610005300006000022000102000假设基准收益率为10%，请运用净现值法对A、B两个方案进行比较分析选择。（附有关资料）1年年2年年3年年4

14、年年5年年6年年7年年8年年9年年10年年10%复利终值复利终值1.10001.21001.33101.46411.61051.77161.94872.14362.35792.593710%复利现值复利现值0.90900.82640.75130.68300.62090.56450.51320.46650.42410.385510%年金终值年金终值1.00002.10003.31004.64106.10517.71569.487211.43613.57915.93710%年金现值年金现值0.90911.73552.48693.16993.79084.35534.86845.33495.75906

15、.1446车辆路线的优化1.出发地和目的地是同一地点2.单一出发地和单一目的地，且出发地和目的地不同3.多出发地和多目的地单一出发地和单一目的地，且出发地和目的地不同出发地和目的地都单一的车辆路线计划问题可以看作一类网络规划问题，此类问题可用运筹学的求最短路径解决。其中，最常用的方法是E.W.Dijkstra算法。该方法的基本思路基于以下原理：若序列Vs,V1,V2,V3,Vn-1,Vn是从Vs到Vn的最短路径，则序列Vs,V1,V2,V3,Vn-1必为从Vs到Vn-1的最短路径。Dijkstra算法基本步骤Dijkstra算法采用标号法，可用两种标号：采用T标号和P标号，T标号为临时性标号，

16、P为永久性标号，给 点一个P标号时，表示从 到点的最短路权，点的标号不再改变。给 点一个T标号时，表示从到 点估计最短路权的上界，是一种临时标号，凡是没有得到P标号的点都有T标号。基本步骤：1）给 以P标号，其余各点都给T标号，2）若 点为刚得到P标号的点，考虑这样的点 ，且 为T标号。对 的T标号进行如下的更改：3）比较所有具有T标号的点，把最小者改为P标号，即：若全部点均为P标号则停止，否则重复23步骤。ivivsvivivivsvsv0)(svP)(ivTivjvjvjv)(),(min)(ijijilvPvTvT)(min)(TivivTvPi标号点为V1V2V4V6V3V5V7V84

17、594676144755例：某公司要在V1和V8 之间寻找一条距离最短的路线，见下图。试用DijkstraDijkstra方法解出。（1）首先给 以P标号，其余所有点都给T标号，（2）考虑 点：（3）比较所有T标号，最小，所以令 （4）为刚得到P标号的点，考察端点：（5）比较所有T标号，最小，所以令：1v0)(1vP)(ivT32,vv660,min)(),(min)(440,min)(),(min)(1313312122lvPvTvTlvPvTvT)(2vT4)(2vP2v54,vv)(3vT6)(3vP844,min)(),(min)(954,min)(),(min)(2525524244

18、lvPvTvTlvPvTvT（6）考虑点（7）比较所有T标号，最小，令（8）考察（9）所有全部T标号中，最小，令（10）考察（11）所有T标号中，最小，令3v876,8min)(),(min)(946,9min)(),(min)(3535534344lvPvTvTlvPvTvT)(5vT8)(5vP5v1468,min)(),(min)(1358,min)(),(min)(5757756566lvPvTvTlvPvTvT)(4vT9)(4vP4v1499,14min)(),(min)(1399,13min)(),(min)(4747746466lvPvTvTlvPvTvT)(6vT13)(6v

19、P（12）考察（13）所有T标号中，最小，令（14）考察(15)只有一个T标号 ，令 ，停止。纵上，最短路径为：6v17413,min)(),(min)(14513,14min)(),(min)(6868867677lvPvTvTlvPvTvT)(7vT14)(7vP7v15 114,17min)(),(min)(78788lvPvTvT)(8vT15)(8vP87521vvvvv习题：教材P133ABCDEFGIHJ90138348661564813212084846048150132126126多起点、多终点问题已知三个工厂1、2、3的需求量分别为600、500、300，而三家供应商的最大

20、供应量分别为400、700、500。每个供应商到每个工厂单位重量的运输成本见上图。求最优供应计划。A BC123476555958解：设供应商A到三个工厂的供应量分别为XA1、XA2、XA3；供应商B到三个工厂的供应量分别为XB1、XB2、XB3；供应商C到三个工厂的供应量分别为Xc1、Xc2、Xc3.则：1231312312313123111222333476555958400700500600500300AAABB2BCCCAAABB2BCCCABCABCABCMinZXXXXXXXXXXXXXXXXXXXXXXXXXXX习题：1.假设有两个制造企业A1、A2，其产品产量分别为35万单位和

21、43万单位。它们生产的产品供应B1、B2、B3三个销售点，其需要量分别为28万单位、31万单位和19万单位。而各自产地到各销售地的运输价格表如下：A1A2B1B2B3制造厂制造厂运价运价销售点销售点50606011070160运价单位运价单位：元元/单位单位决策问题：如何调运才能使总运费最省？请根据题目给出的条件和数据建立线性规划模型。（说明建模过程，不必求解。）起点与终点为同一地点仓仓库库300030002000300020001000400020002000200020001000步骤：1.把所有销售点及仓库位置在坐标图上标示出来2.从仓库处沿某一方向划一条直线，转动这条直线，当到 它穿过一个销售点时，这条直线划过的区域的供应量总 合小于卡车的载重量时，停止转动。3.在每一个区域，再进行最短路线计划来选择运输的顺序。