周洪涛-物流系统规划-第6章-配送规划优秀PPT.ppt

《周洪涛-物流系统规划-第6章-配送规划优秀PPT.ppt》由会员分享，可在线阅读，更多相关《周洪涛-物流系统规划-第6章-配送规划优秀PPT.ppt（118页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 配送规划配送规划周洪涛周洪涛华中科技高校系统工程探讨所华中科技高校系统工程探讨所zht730yahoo p 61 配送规划概述p 62 配送网络设计p 6.3 配送成本限制p 6.4 配送绩效评估指标主要内容主要内容61 配送规划概述配送规划概述6 61 11 1 配送的概念配送的概念 配送包括“配”和“送”两个方面的活动，“配”包括了货物的集中、分拣和组配活动，“送”包括了各种不同的送货方式和送货行为。配送在经济合理区域范围，依据用户的要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。61 配送规划概述配送规划概述6 61 11 1 配送的概念配送

2、的概念 配送是在整个物流过程中的一种物流活动和商业活动，是商流和物流紧密结合的一种综合的、特殊的物流活动，也是物流网络中的关键环节。物流活动包括集货、存储、拣货、配货和装货等；商业活动输送、送达、验货等以送货上门为目的的商业活动。61 配送规划概述配送规划概述6.1.2 6.1.2 配送的功能与作用配送的功能与作用r完善运输系统（支线小批量运输）r消退交叉输送（干脆配送，设置配送中心）r有利于实现低库存或零库存（生产企业）r简化程序，便利用户（配送作业打包一次性托付）r提高供应链的牢靠性（更强的物流处理实力）61 配送规划概述配送规划概述配送业务的基本流程配送业务的基本流程r基本流程基本流程6

3、1 配送规划概述配送规划概述配送业务的基本流程配送业务的基本流程r食品配送流程食品配送流程n第类商品由于保质期短，保鲜要求高如海鲜产品、鱼、肉类制品等，集货后不经过储存马上分拣配货、配装后送达客户；n第类商品保质期较长，比如矿泉水、便利食品等，可以在集货后经过存储保管后，再按客户订单要求组织配送。n第类商品在集货后，需按客户的要求按商品特性经过配送加工后再组织配送，如速冻食品、大包装进货食品。61 配送规划概述配送规划概述6.1.4 6.1.4 配送规划设计的内容配送规划设计的内容 r配送中心的布置与规划配送中心的布置与规划(3,4(3,4章章)r配送中心的作业规划配送中心的作业规划r配载规划

4、的优化配载规划的优化r配送路途的规划和优化配送路途的规划和优化r区域配送网络结构的规划区域配送网络结构的规划r配送车辆的调度配送车辆的调度r配送信息系统的规划配送信息系统的规划r配送成本限制和绩效评估等内容配送成本限制和绩效评估等内容6.2 配送网络设计配送网络设计 配送网络是一个涉及多方面、多层次、多子系统的困难系统。配送网络设计包括1）众多物流配送中心之间和其通道组成的配送网络结构体系设计和配送路途设计，也包括2）配送中心内部区域布置、3）作业设计等内容。配送网络结构体系配送中心订单品项与数量分析（EIQ）分拣方式确定、配送中心内部区域布置确定配送中心作业系统设计分拣作业规划设计、配货与配

5、载规划6.2 配送网络设计配送网络设计6.2.1 6.2.1 配送网络结构体系配送网络结构体系一、多级、多层次的配送网络体系一、多级、多层次的配送网络体系6.2 配送网络设计配送网络设计6.2.1 6.2.1 配送网络结构体系配送网络结构体系二、两级、双层次的配送网络体系二、两级、双层次的配送网络体系6.2 配送网络设计配送网络设计6.2.1 6.2.1 配送网络结构体系配送网络结构体系三、单层次的配送网络体系三、单层次的配送网络体系6.2 配送网络设计配送网络设计6.2.2 EIQ6.2.2 EIQ分析分析一、订单出货资料的分解（一天为单位）一、订单出货资料的分解（一天为单位）（1 1）订单

6、量）订单量(EQ)(EQ)分析：单张订单出货数量的分析。分析：单张订单出货数量的分析。（2 2）订单品项数）订单品项数(EN)(EN)分析：单张订单出货品项数的分析。分析：单张订单出货品项数的分析。（3 3）品项订货数量）品项订货数量(IQ)(IQ)分析：单一品项出货总数量的分析。分析：单一品项出货总数量的分析。（4 4）品项订货次数）品项订货次数(IK)(IK)分析：单一品项出货次数的分析。分析：单一品项出货次数的分析。留意运用统一的数量单位，质量体积单位与物流作业有关，留意运用统一的数量单位，质量体积单位与物流作业有关，金额单位与商品价值有关，常用于商品分类和存储区管理。金额单位与商品价值

7、有关，常用于商品分类和存储区管理。6.2 配送网络设计配送网络设计6.2.2 EIQ6.2.2 EIQ分析分析二、订单出货资料的取样二、订单出货资料的取样 要了解物流配送中心实际运作的物流特性，可就单日的出货量进行初步分析，找出可能的作业周期及其波动幅度，若各周期内出货量基本相像，则可缩小处理资料的范围，以一较小周期内的资料进行分析，若各周期内趋势相近，但是作业量仍有很大的差异，则应对资料作适当分组，再于各群组中找出代表性的资料进行分析。6.2 配送网络设计配送网络设计6.2.2 EIQ6.2.2 EIQ分析分析三、资料统计分析三、资料统计分析（1 1）柏拉图分析（出货品项数）柏拉图分析（出货

8、品项数累计出货数，累计出货数，EQ,IQEQ,IQ）（2 2）次数分布（分组计数）次数分布（分组计数）（3 3）ABCABC分析分析（4 4）交叉分析）交叉分析6.2 配送网络设计配送网络设计6.2.2 EIQ6.2.2 EIQ分析分析四、图表数据的分析四、图表数据的分析 订单量（订单量（EQEQ）分析）分析 订单品项数（订单品项数（ENEN）分析）分析 品项订货数量（品项订货数量（IQIQ）分析）分析 品项订货次数（品项订货次数（IKIK）分析）分析 IQ IQ及及IKIK交叉分析交叉分析6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计一、分拣作业的类

9、型一、分拣作业的类型1 1按订单分拣批量分类按订单分拣批量分类（1 1）按单分拣（先拣后汇总）按单分拣（先拣后汇总）（2 2）批量分拣（先汇总拣后分类）批量分拣（先汇总拣后分类）（3 3）按单分拣与批量分拣的组合）按单分拣与批量分拣的组合2 2按作业程序分类按作业程序分类（1 1）单一分拣法（一个人分拣）单一分拣法（一个人分拣）（2 2）分程传递法（数人分拣，每人拣一部分传递下去）分程传递法（数人分拣，每人拣一部分传递下去）（3 3）分区并行分拣法（数人分拣，每人拣一部分然后汇）分区并行分拣法（数人分拣，每人拣一部分然后汇总）总）3.3.按作业方法分类按作业方法分类（1 1）拣选式分拣法（摘果

10、子时分拣配货法）拣选式分拣法（摘果子时分拣配货法）（2 2）分货式分拣法）分货式分拣法 （播种式分拣配货法，先取共同须（播种式分拣配货法，先取共同须要的货物，然后分放）要的货物，然后分放）6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计二、拣选策略二、拣选策略分区策略分区策略订单分割策略订单分割策略订单分批处理策略订单分批处理策略分类策略分类策略6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计二、拣选策略二、拣选策略-分区策略分区策略商品特性分区商品特性分区特殊存储搬运或分别存储商品进行区特殊存储搬运或分别存储商品

11、进行区域分割。域分割。拣选单位分区拣选单位分区存储单位与拣选单位分类统一，分拣存储单位与拣选单位分类统一，分拣搬运商品单元化，分拣作业单纯化，自动化和标准化。搬运商品单元化，分拣作业单纯化，自动化和标准化。拣选方式分区拣选方式分区拣选方法和设备差异，分若干分拣区拣选方法和设备差异，分若干分拣区域，域，ABCABC分类，选合适的拣选设备和分拣方式。目的是拣分类，选合适的拣选设备和分拣方式。目的是拣选作业单纯一样，削减不必要的重复行走时间。选作业单纯一样，削减不必要的重复行走时间。工作分区工作分区相同拣选方式，拣选场地再划分相同拣选方式，拣选场地再划分6.2 配送网络设计配送网络设计6.2.3 6

12、.2.3 拣货作业规划设计拣货作业规划设计二、拣选策略二、拣选策略-订单分割策略订单分割策略将订单按拣选区域进行分解的过程叫订单分割。订单分割策略一般是与拣选分区策略同时运用，对于接受拣选分区的配送中心，其订单处理过程的第一步就是要按区域进行订单的分割，各个拣选区依据分割后的子订单进行分拣作业，各拣选区子订单拣选完成后，再进行订单的汇总。6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计二、拣选策略二、拣选策略-订单分批处理策略订单分批处理策略总合计量分批分拣路径减至最短，需强大的分类系统，适合固定点间的周期性配送。时窗分批适合达到时间短而平均的订单形态，

13、但订购量和品项数不宜太大。固定订单量分批订单分批先到先处理原则，累计订单达到固定量时起先拣选作业，目标留意维持较稳定的作业效率，处理的速度较前者慢。智能型分批订单汇总后计算机处理，将分拣路径相近的订单分成一批同时处理，缩短拣选行走和搬运距离。对紧急插单作业处理较困难。6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计二、拣选策略二、拣选策略-分类策略分类策略拣货时分类拣货同时将货品依据各订单分类（固定量分批，智能型分批联合运用）拣货后集中分类人工，或分类运输机系统6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计三、分

14、拣作业系统规划三、分拣作业系统规划分拣系统规划程序（分拣系统规划程序（P=托盘、托盘、C=箱子、箱子、B=单品）单品）6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计三、分拣作业系统规划三、分拣作业系统规划-订单资料的订单资料的EIQ分析分析 IKIK值值ENEN值值货品重复订购货品重复订购频率频率IKIK值值高高中中低低出货品出货品项数项数ENEN值值多多 S SP PS SS S中中P PP PS S少少P PP PS SP PEN值越大表示一张订单所订购的货品品项数越多，货品的种类越多越困难时，批量分拣时分类作业越困难，实行按单拣选较好。IK值越大

15、，表示某品项的重复订购频率越高，货品的周转率越高，此时，接受批量分拣可以大幅度提高拣选效率。S按单拣选；P批量分拣6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计三、分拣作业系统规划三、分拣作业系统规划-拣货单元拣货单元PCB分析分析拣选单位基本上可分为托盘、箱、单品三种。订单确定拣选单位；拣选单位和商品拣选频率及数量确定存储单位；存储单位要求供应商入库单位。拣选模式编号拣选模式编号存储单位存储单位拣选单位拣选单位记号记号1 1托盘托盘托盘托盘P PP P2 2托盘托盘托盘箱托盘箱 P PP PC C3 3托盘托盘箱箱P PC C4 4箱箱箱箱C CC

16、C5 5箱箱单品单品C CB B6 6箱箱箱单品箱单品 C CC CB B7 7单品单品单品单品B BB B6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计三、分拣作业系统规划三、分拣作业系统规划-拣选策略的运用拣选策略的运用 6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计三、分拣作业系统规划三、分拣作业系统规划-拣选信息的处理拣选信息的处理（1 1）传票）传票复印订单制成拣选传票；干脆从多联式复印订单制成拣选传票；干脆从多联式订单撕下拣选专用的一联。适合货品品项数不多，按单订单撕下拣选专用的一联。适合货品品项数

17、不多，按单拣选。拣选。（2 2）拣选单）拣选单订单输入订单输入+商品存量，存储位置商品存量，存储位置按订单时间打印出拣选单，产生补货和出货指示。批量按订单时间打印出拣选单，产生补货和出货指示。批量拣选，按单拣选。拣选，按单拣选。（3 3）拣选标签）拣选标签分拣贴标签代替了清点货品数量的分拣贴标签代替了清点货品数量的过程；附有流通条码的标签供应自动分类系统识别信息。过程；附有流通条码的标签供应自动分类系统识别信息。（4 4）电子信息）电子信息仓储仓储MISMIS处理拣选信息后将指令传处理拣选信息后将指令传给限制器，传出限制信号操纵设备。电子标签协助分拣给限制器，传出限制信号操纵设备。电子标签协助

18、分拣系统和系统和RFRF拣选系统。拣选系统。6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计三、分拣作业系统规划三、分拣作业系统规划-拣选系统设备配置拣选系统设备配置 序号序号 分拣单元模式分拣单元模式设备配置模式设备配置模式1 1P PP P就地托盘堆垛叉车就地托盘堆垛叉车2 2P PP P托盘类货架叉车托盘类货架叉车3 3P PP P自动仓储系统输送机（穿梭车）自动仓储系统输送机（穿梭车）4 4P PC C自动仓储系统输送机（穿梭车）自动仓储系统输送机（穿梭车）5 5P PC C自动仓储系统拆盘机输送机（穿梭车）自动仓储系统拆盘机输送机（穿梭车）6

19、6P PC C自动仓储系统侧面底层人工拣选自动仓储系统侧面底层人工拣选7 7P PC C托盘类货架拣选叉车托盘类货架拣选叉车8 8P PC C横梁式托盘类货架底层人工拣选手推车横梁式托盘类货架底层人工拣选手推车6.2 配送网络设计配送网络设计6.2.3 6.2.3 拣货作业规划设计拣货作业规划设计三、分拣作业系统规划三、分拣作业系统规划-拣选系统设备配置拣选系统设备配置 序号序号 分拣单元模式分拣单元模式设备配置模式设备配置模式9 9P PC C重力式托盘货架底层人工拣选输送机重力式托盘货架底层人工拣选输送机1010P PC C就地托盘堆垛底层人工拣选输送机就地托盘堆垛底层人工拣选输送机111

20、1C CC C箱式自动仓储系统输送机箱式自动仓储系统输送机1212C CC C流利式货架或其他箱装货物货架输送机（手推车）流利式货架或其他箱装货物货架输送机（手推车）1313C CB B非流利式箱装货物货架手推车非流利式箱装货物货架手推车1414C CB B流利式货架输送机流利式货架输送机1515C CB B箱式旋转货架输送机（手推车）箱式旋转货架输送机（手推车）1616B BB BA A型分拣机输送机型分拣机输送机1717B BB B轻型箱式货架手推车轻型箱式货架手推车6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、货架仓库拣货路径优化一、货架仓库拣货路径

21、优化例例6-1 6-1 货架仓库拣货的路径问题。对于规整的托盘单元式货架仓库货架仓库拣货的路径问题。对于规整的托盘单元式货架仓库（下图），每条通道两边均分布货架，通道之间的货架背靠背摆放。（下图），每条通道两边均分布货架，通道之间的货架背靠背摆放。假设拣货员从起先位要拣取全部图中阴影货位（设货位尺寸均为一单假设拣货员从起先位要拣取全部图中阴影货位（设货位尺寸均为一单位宽深）中的货物，然后回到结束位。位宽深）中的货物，然后回到结束位。6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、货架仓库拣货路径优化一、货架仓库拣货路径优化 将这一拣货路径问题转化为最短路问题

22、。先按上图右边将四条通道予以划分，并在每通道两端1R、1L等点。我们的始点即1R。通道宽为两单位，这些端点离货架顶端一单位距离远。拣货中通常要求拣货员拣完一条通道内的货物后，才能进入另一条通道，为提高拣货效率不允许回退。6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、货架仓库拣货路径优化一、货架仓库拣货路径优化 因为货物在通道内分布深度不一，拣货员就可能有两种方法，一是从通道R端始终走到L端，一种是从一端走到拣货位，拣取货物后，再原路退出。应用这两种方法对第一条通道内货物拣货时所得距离如下图所示。6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路

23、径优化拣货路径优化一、货架仓库拣货路径优化一、货架仓库拣货路径优化以此类推，可得到最终的网络图表示，如下图所示 6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、货架仓库拣货路径优化一、货架仓库拣货路径优化 对于上图右边的网络图，很简洁求出它的最短路，还可以形象地画出此问题总的最短拣货路径，如下图所示 6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、最短路问题的延长一、最短路问题的延长TSP问题问题 1.S1.S形算法（形算法（S-shape heuristicS-shape heuristic）假如仓库里每一个通道内至少有

24、一种货品要拣取，就可实行S形算法.当然，S形可以改进，对没有货品要拣取的通道可忽视不走，但考虑回路问题，奇数条无拣通道多走一点。像右图中的偶数条不走刚好可以从原定位置走出。因为S 形走法在同一通道内可往两边拣货，因此通道可以在其他条件允许下窄一些。但一个拣货员同时行走这么多通道可能效率不高，仓库里常会接受分区拣选，此时通道可能须要多人通过，不能太窄。6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、最短路问题的延长一、最短路问题的延长TSP问题问题 2.2.最大径距法（最大径距法（Largest gap heuristicLargest gap heurist

25、ic）对于拣选路径的具体TSP问题，用径距（gap）代表上下两个要拣取货品的距离，明显这是直角距离，这一距离可能是在同一通道内，也可能以两个相近通道直角距离计算。拣货员先到离I/O口最近的边通道，拣取所需的货物，然后退出该通道再按通道的最大径距确定下一个要进入的通道。6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、最短路问题的延长一、最短路问题的延长TSP问题问题 例例6-2 6-2 某果汁公司的仓库如下图所示，假设行走时间与距离成正比某果汁公司的仓库如下图所示，假设行走时间与距离成正比6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货

26、路径优化一、最短路问题的延长一、最短路问题的延长TSP问题问题 解：按解：按S S形算法和最大径距法的图形分别如上图左右所示，而最优的路径形算法和最大径距法的图形分别如上图左右所示，而最优的路径是行走距离最短的路径，接受是行走距离最短的路径，接受RatliffRatliff和和RosenthalRosenthal的动态规划解法给出的的动态规划解法给出的结果如下图所示。结果如下图所示。6.2 配送网络设计配送网络设计6.2.4 6.2.4 拣货路径优化拣货路径优化一、最短路问题的延长一、最短路问题的延长TSP问题问题 Ratliff和Rosenthal的动态规划解法给了拣选路径最优化的算法，只要

27、给定仓库的全部货位就可以快速找到最短的路径。这适用大规模的仓库，这里对该算法作点简化，即加上限制：已拣过的通道不再回退，这样虽然得到的是近优解，但易于编程和说明。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划一、配送配载概述一、配送配载概述-配送配载的概念配送配载的概念 所谓配载就是为了提高车辆在容积和载货两方面的装载效率，进而提高车辆运载运力的利用率，降低配送运输成本，配送中心充分利用运输配送的货物资源，对货物进行装车调配、优化处理。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划一、配送配载概述一、配送配载概述-配送

28、配载的配送配载的原则原则 轻重搭配原则（重下轻上）货物性质搭配原则（化学性质物理属性不相抵触）大小搭配原则（削减厢内空隙）一次配载原则（同一地点适合配装货物尽可能一次配载）最大限载原则（不超过车辆额定负荷）后送先装原则（便于卸货）6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题问题描述载重和体积受限配装问题问题描述 该问题一般描述为：物流中心配送车辆最大载重为该问题一般描述为：物流中心配送车辆最大载重为W W，最，最大装载体积为大装载体积为V V。现有。现有N N种货物

29、须要运输，已知第种货物须要运输，已知第i i种货物的种货物的单位重量为单位重量为wiwi，体积为，体积为vi vi，价值为，价值为cici（实际中，可依据订（实际中，可依据订单的重要性，设置每件货物的配送价值）。要求确定每种单的重要性，设置每件货物的配送价值）。要求确定每种货物的装载件数，在不超过最大载重和最大体积状况下，货物的装载件数，在不超过最大载重和最大体积状况下，使货车装运货物的总价值为最大。使货车装运货物的总价值为最大。满载问题的优化，满载问题的优化，即运筹学中的背包问题即运筹学中的背包问题6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车

30、辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题数学模型数学模型 若用xi 表示i种货物的装载件数，则问题归结为整数线性规划问题。前提：忽视了各尺寸包前提：忽视了各尺寸包装箱组合后可能留下的不装箱组合后可能留下的不可填充的缝隙等剩余空间可填充的缝隙等剩余空间6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题数学模型数学模型 现将此问题转化为动态规划模型。把装载N种货物看作依次分N个阶段完成，用k（

31、k=1,2,N）来表示阶段；（w，v）为二维状态变量，w表示货车中装入货物第1种到第k种的总重量，v表示货车中装入货物第1种到第k种的总体积。决策变量xk表示装入第k种物品的件数。则状态转移方程为：则允许决策集合为：6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题数学模型载重和体积受限配装问题数学模型 设设fkfk（w w，v v）表示当总重量不超过）表示当总重量不超过w w，总体积不超过，总体积不超过v v，货车中只装前货车中只装前k k种货物的最大价值。明显有：种货

32、物的最大价值。明显有：因而可写出动态规划的依次递推关系为：6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题数学模型数学模型然后，逐步计算出然后，逐步计算出f1(wf1(w，v)v)，f2(w f2(w，v)v)，fk(w fk(w，v)v)，以及相应，以及相应的决策函数的决策函数x1(wx1(w，v)v)，x2(w x2(w，v)v)，xk(w xk(w，v)v)，最终得出所求的，最终得出所求的最大价值，相应的最优策略可由反推运算得出。最大价值，相

33、应的最优策略可由反推运算得出。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题应用案例应用案例例例6-3 6-3 某电器配送中心一辆配送货车，该货车的额定载重为某电器配送中心一辆配送货车，该货车的额定载重为1010吨，最大吨，最大允许装载体积为允许装载体积为1616立方米，现有三种货物须要运输。已知这立方米，现有三种货物须要运输。已知这3 3种货物的单种货物的单位重量、体积及价值关系如表位重量、体积及价值关系如表6.96.9，问如何配装这三种货物，

34、才能使货车，问如何配装这三种货物，才能使货车装载货物的价值最大。装载货物的价值最大。配送信息表配送信息表货货物代号物代号 重量（吨）重量（吨）体体积积（立方米）（立方米）价价值值（千元）（千元）1 11 11 14 42 24 46 65 53 32 27 76 66.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题应用案例应用案例解：（1）设xi表示第i（i=1，2，3）种货物装载件数，则问题规划模型为：6.2 配送网络设计配送网络设计6.2.5 6

35、.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题应用案例应用案例（2）用动态规划法，只要求出f3（10，16）即可。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题应用案例应用案例（3）由上可以看出，要计算f3（10，16）必需先计算出 f2（10，16），f2（7，7），f2（6，0）。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货

36、与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题应用案例应用案例同理可求得：f2(7，7)maxf1(7，7)，5+f1(0，2)f2(6，0)f1(6，0)这里x2取0，1时，分别对应f1(7，7)，5+f1(0，2)。f2(6，0)f1(6，0)（这里x20时，对应f1(7，1)）。所以，为了计算f2(10，16)，f2(7，7)和f2(6，0)，还须要计算f1(10，16)，f1(6，10)，f1(2，4)，f1(7，7)，f1(0，2)和f1(6，0)。6.2 配送网络设计配送网络设计6.2.5 6

37、.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题应用案例应用案例（4）同理可求得：f1(6，10)24 （x1=6）f1(2，4)7 （x1=2）f1(7，7)32 （x1=7）f1(0，2)0 （x1=0）f1(6，0)0 （x1=0）6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划二、提高车辆装载效率的数学方法二、提高车辆装载效率的数学方法1.1.载重和体积受限配装问题载重和体积受限配装问题应用案例应用案例（5）从而 f2(10，16)max f1(10

38、，16)，5+f1(6，10)，10f1(2，4)max40，524，10740 （x1=10，x2=0）f2(7，7)max f1(7，7)，5+f1(0，2)max32，532（x1=7，x2=0）f2(6，0)f1(6，0)0 （x1=0，x2=0）（6）最终得到f3（10，16）max f2(10，16)，7+f2(7，7)，16f2(6，0)max 40，7+32，16040 （x1=10，x2=0，x3=0或者x1=7，x2=0，x3=1）最大装载价值为40。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化 接受网

39、络图等运筹学方法利用计算机来协助确定车辆最终的行驶线路，以保证车辆高效运行。这些方法就是车辆路径问题VRP（Vehicle Routing Problem）。路径问题也称为线路优化问题，它主要解决运输工具与运输目的地之间路途、载运量、到达时间与依次等支配，以达到某种“最佳”的效益。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化 VRP问题可以正式定义如下：设图G=(V,A)，其中点集V=v0,v1,vn，弧集A=(vi,vj):vi,vjV,ij。点v0代表仓库（起始点），其他各点代表顾客。弧集有对应的成本矩阵(cij)和行

40、驶时间矩阵(tij)。假如这两个矩阵是对称的，就得到基于无向图的VRP问题，G=(V,E)，其中E=vi,vj :vi,vjV,i j 为边集。每一个顾客都有一个非负的需求量qi和服务时间ti。仓库有由m辆容量均为Q的一样的卡车组成的车队，卡车数量要么提前已知要么作为决策变量。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划 VRP问题就是要确定最多m条配送路径或收货路径，以满足下列条件：（1）每条路径都是从仓库动身，回到仓库；（2）每个顾客只能探望一次，且只能由一辆车探望；（3）每条路径的总需求量不超过Q；（4）每条路径的总持续时间（行驶时间+服务时间）不

41、超过预设的时限D；（5）总成本最低。三、配送路径优化三、配送路径优化6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化扩展扩展VRPVRP问题：问题：容量限制的容量限制的VRPVRP问题问题CVRPCVRP（Capacitated VRPCapacitated VRP）带时间窗口（带时间窗口（time windowtime window）的）的VRPTWVRPTW问题问题车辆可以是不同的（车辆可以是不同的（heterogeneous vehicle fleetheterogeneous vehicle fleet）车辆同时进行配

42、送和收货的作业（车辆同时进行配送和收货的作业（VRPPDVRPPD）去程送货（去程送货（linehaul deliverieslinehaul deliveries）回程收货（回程收货（backhaul pick-upsbackhaul pick-ups）多仓库（多仓库（multi-depotmulti-depot）VRPVRP问题问题将车辆路径与调度安排相结合的将车辆路径与调度安排相结合的Vehicle Routing and Vehicle Routing and SchedulingScheduling问题问题6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配

43、载规划三、配送路径优化三、配送路径优化节约法(the Savings Algorithm)假设起始状态为两个网点 i、j，各单独由一辆车服务，现在改为下图所示的送货方式，两网点由一辆车服务，就可以得到距离的节约值 S(i，j)，节约值计算公式为：S(i，j)=2d(0，i)+2d(0，j)d(0，i)d(i，j)d(j，0)d(0，i)+d(0，j)d(i，j)其中d(i，j)表示网点 i 至网点 j 的距离，网点0表示配送中心。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化例例6-5 6-5 现有一配送网络，如下图所示，图

44、中P为配送中心，其余A,I为各客户的接货点，各边上的数字为公里数，括弧里的数字为需输送到各接货点的货物数量，单位为吨。假设该配送中心有最大装载重量为2吨和5吨的两种货车，并限制车辆一次运行线路距离不超过35公里。求合理配送路径。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化解：解：利用前面所述的最短路径法，求出网络各节点的最短距离，计算结果用右表表示。PABCDEFGHA5B84C773D51074E491073F121720171310G914171614134H12121619171675I63710111016149网

45、络节点的最短路径表网络节点的最短路径表 6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化解：解：依据上表，依据上表，计算各用户之间计算各用户之间的节约里程，如的节约里程，如右表所示右表所示 ABCDEFGHB9C512D067E0246F00246G0000017H540001716I77300219用户之间的节约里程表用户之间的节约里程表 6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化解：解：对节约里程按大小依次进行排列，结果如下表所示对节约里程按大小依次

46、进行排列，结果如下表所示 节约行程排序结果表节约行程排序结果表 序 号1234567891011连 接 点F-GF-HG-HB-CA-BH-IA-IC-DB-IB-D D-E节约里程171716129988766序 号1213141516171819202122连 接 点E-FA-CA-HB-HC-ED-FC-IB-EC-FF-IG-I节约里程655444322216.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化初始解：从初始解：从P P向各个接货点配送，共有向各个接货点配送，共有9 9条，总的运行距离为条，总的运行距离为13

47、6136公里，公里，须要须要2 2吨汽车吨汽车7 7辆，辆，5 5吨汽车吨汽车2 2辆，如下图所示。辆，如下图所示。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化二次解：依据节约里程的大小依次连接二次解：依据节约里程的大小依次连接F-G,F-HF-G,F-H，如下图所示。总，如下图所示。总运行距离为：运行距离为：2(6+5+8+7+5+4)+(9+4+7+12)=1022(6+5+8+7+5+4)+(9+4+7+12)=102公里，配送路途公里，配送路途7 7条，条，须要须要2 2吨车吨车5 5辆，辆，5 5吨车吨车2 2辆

48、。配送路途辆。配送路途I I的运行距离为的运行距离为3232，装载量为，装载量为4.74.7吨。吨。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化三次解：连接三次解：连接B-C,A-B,H-IB-C,A-B,H-I，但因，但因H-IH-I加入配送路途加入配送路途I I后，超过车辆后，超过车辆最大载重量最大载重量5 5吨，所以不予连接，如下图所示。此时，总的配送路途吨，所以不予连接，如下图所示。此时，总的配送路途为为5 5条，须要条，须要2 2吨配送车辆吨配送车辆2 2辆，辆，5 5吨配送车辆吨配送车辆3 3辆。配送路途辆。配

49、送路途IIII的运行的运行距离为距离为1919公里，装载量为公里，装载量为3.83.8吨。吨。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化四次解：连接四次解：连接A-IA-I到配送路途到配送路途IIII，如图，如图6.276.27所示。总的配送路途为所示。总的配送路途为4 4条，需条，需5 5吨车辆吨车辆3 3辆，辆，2 2吨车辆吨车辆1 1辆。辆。6.2 配送网络设计配送网络设计6.2.5 6.2.5 配货与配载规划配货与配载规划三、配送路径优化三、配送路径优化最终解：由于受配载的限制，配送路途不再添加新的结点，连接最终

50、解：由于受配载的限制，配送路途不再添加新的结点，连接D-ED-E。这样就完成了全部的配送路途设计，总共有。这样就完成了全部的配送路途设计，总共有3 3条配送路途，运行距离条配送路途，运行距离为为6767公里，须要公里，须要2 2吨车吨车0 0辆，辆，5 5吨车吨车3 3辆。辆。其中配送路途其中配送路途I I：运行距离：运行距离3232公里，装载量公里，装载量4.74.7吨；配送路途吨；配送路途IIII：运：运行距离行距离2323公里，装载量公里，装载量5 5吨；配送路途吨；配送路途IIIIII：运行距离为：运行距离为1212公里，装载量公里，装载量为为4.74.7吨，如下图所示。吨，如下图所示