配送中心设施平面布局模型.ppt

配送中心 设施平面布局模型,参考文献：孙焰，现代物流管理技术建模理论及算法设计，同济大学出版社,内容,前言 系统布局设计基本概念与流程 关系表布局法 CORELAP布局法 ALDEP布局算法 CRAFT布局算法 MultiPLE布局算法,前言,设施的平面布局模型也称为二维选址模型，主要研究在一个给定区域内确定具有一定面积要求的各个设施的最佳位置问题。一个配送中心一般由若干个设施组成，如停车场、验货场、仓库等，当不同类别的货物运到配送中心后，根据作业流程的要求，需要在其中不同的设施进行处理，所需要的时间、数量和次序是不相同的，因此，各种设施在配送中心内的相对位置是否合理，将直接影响配送中心的工作效率，进而影响物流成本。 基本问题：已知各个设施的作业面积、作业量以及作业流程，试在一个给定的区域内合理布置这些设施的位置和形状，使配送中心内的作业流程最为顺畅。,系统布局设计（Systematic Layout Planning）基本概念与流程,相互关系图,相互关系图是用于描述各个设施之间关系的密切程度的图，通常，所谓的关系密切程度指的是货品流量。,通常，用A-F等6个等级来描述设施间的关系，A最重要、B其次，一直到E。而F表示两设施间不能有联系。,关系等级的标定,通常，等级关系可以利用设施间的货品流量、信息流量来确定。,流量大的给予高的关系等级，反之给予低的等级； 从管理的信息流量角度对关系等级进行补充； 等级标定的规则要保障A、B级占15以内，以方便后期的布局设计。,空间关系图,空间关系图指的是考虑了面积需求后的各个设施的位置关系的图。例如某配送中心的5个主要设施，其空间关系图：,基本流程,（1）对各设施之间的相互关系作出分析，包括物流和非物流的相互关系，建立关系图 （2）根据相互关系图中各设施的关系的密切程度，决定各设施之间距离的远近，安排各设施的位置，绘制设施位置相关图，将各设施实际占地面积与设施位置相关图结合起来，形成设施空间关系图； （3）通过设施空间关系图的修正与调整，得到若干可行的布局方案； （4）量化各因素，建立方案质量评估的数量指标，对各个方案进行评估，以得到最佳布局方案。,关系表布局法,主要步骤,（1）将设施相互关系图转化为关系表； （2）选择A级关系最多的设施作为第1设施优先进入布置； （3）选择与第1设施具有A级关系的设施作为第2设施进入布置； （4）按照与第1设施、第2设施为AA、AB、AC、AD的排列顺序选择第3设施； （5）依次选择直至全部设施选择完毕； （6）按照设施排序，根据面积进行实际布置的操作过程，形成空间关系图。,例子,设某配送中心由5个主要设施D1、D2、D3、D4、D5组成，各个面积需求如表1所示。该配送中心的主要业务流程有3个，记为P1、P2和P3 ，各业务流程及流量如表2所示。,解第1步：计算流量矩阵,设Qij为由Di到Dj的流量，可以求出各设施间的流量矩阵Q（也可称为O-D矩阵）。,解第2步：绘制相互关系图,解第3步：生成关系表,解第4步：确定设施排序,设施2具有1个A关系，2个C关系，所以选择设施2作为首选设施进行安排； 其次，选择与设施2具有A关系的设施，即设施1； 接下来，分析其它设施与设施2、设施1的关系组合，设施4、设施5均为C，任选设施4； 分析其它设施与设施2、设施1、设施4的关系，选中设施5； 最后是设施3； 所确定的布置顺序为2-1-4-5-3。,解第5步：形成空间关系图,根据已经确定的顺序，考虑具体的面积，将关系密切的设施相邻放置，关系较不密切的设施，位置可较灵活放置。,D2,D2,D5,D4,D1,D2,D1,D4,D2,D1,D5,D4,D2,D1,D3,CORELAP布局算法,简介,CORELAP(Computerized Relationship Layout Planning)是Lee R.C.和Moore J.M.于1967年提出的一种布局优化算法。 提出一个衡量设施布局方案的评价方法（布局质量指标），以及最优布局方案的选取步骤。 基本思路： 按一定规则生成一个设施顺序矢量，依照这个矢量的顺序逐个将设施加入到区域中去，并尽量使新加入的设施与已有的设施在相对位置上保证关系最密切。布置方案完毕后，对其质量指标进行评估。 该算法无论是设施顺序矢量的确定、相对位置的选择以及质量指标的计算，都依赖于设施间的关系程度的衡量，即CORELAP算法的出发点是设施之间的相互关系图（Relation-Chart）。,布局质量指标,要计算布局质量指标，首先需要对关系等级标定转换成数值。 优化的目标函数值可通过计算任意两设施间的关系值乘以该两设施间的最短距离的总和来求得，即：,最小化,布置设施顺序的确定,CORELAP的选择方法，即布置顺序矢量的产生方法，是根据各设施所有关系的综合TCR（Total Closeness Rating）的值来确定的。令 称TCR(i)为设施i的关系总和，选择TCP最大的设施作为最先进入布置的设施。若最大的TCR值有多个设施，即出现“结”（相持），则选择面积最大的设施解“结”（相持的突破）；若依然解不开，则随机选取。 第2个设施选择与第1个设施具有最高级别关系（A级）的设施，依次选择B级、C级、，如果同一关系级别出现多个设施（“结”），选择这些设施中TCR最大的设施先布置（解“结”）。 在布置中，设施的形状尽可能设计成若干个正方形组成。,相对位置的确定,生成了布置矢量后，依照这个矢量的顺序逐个将设施向布置图中放置。放置原则是在所有可布置的位置中选择使进入布置图的设施与前面进入的相邻设施的关系值的和NCR（Neighbour Closeness Rating）最大的那个位置。,3,3,4,1a,1b,1c,案例：,已知配送中心的5个设施场所作业面积和相互关系如图，试用CORELAP法求该配送中心的设施布局方案。,求各个设施的TCR值,顺序： 2 1 4 5 3,根据各设施面积确定布置,评估布置方案,对多个方案进行比较，可获得最佳方案（或较佳方案）。,ALDEP布局算法,简介,ALDEP（Automated Layout Design Procedure）法与CORELAP法类似，其布置基础也是关系图，算法思路也是每次选择一个设施加入布置图，按一定规则寻找其适当的位置，并对方案进行评估。 三个方面与CORELAP不同： 方案评估的指标（目标） 设施的选择次序 位置的确定方法,布局质量指标,优化目标函数是求所有两两相邻设施间的关系值的总和达到最大，即 在做关系等级转换（映射）时，特地拉大了不同等级之间的数值差距。,设施的顺序,第1个布置设施的选择方法是随机选取的； 随后，给定一个最低关系门槛值TCR（Threshold Closeness Rating），对其它设施，根据与第1个设施的关系进行降序排队，直到排到设定的最低关系门槛值TCR； 选择大于TCR的所有设施，如果数量大于1，顺序为随机。 例如：设TCR=B，则只选择与先布置设施具有A、B关系的设施进入排列，对于与先布置设施均为A或B的布置设施，则随机选择进入布置。,设施位置的确定,ALDEP的设施位置放置方法是将选定布置顺序的各设施，按照其单位面积数，以设定的宽度，从布置图的左上角向下，蛇形蜿蜒，直至布置完所有的设施，如图，其中设定的宽度（称为扫描宽度，Sweep Width）为2。,案例：,已知配送中心的5个设施场所作业面积和相互关系如图，试用ALDEP法求该配送中心的设施布局方案，其中TCR=C，扫描宽度为1。,设施顺序,随机选择第1个设施，如D3； 与D3不存在有A/B/C关系的设施，因此进一步随机选择第2个设施，如D4； 与D4不存在有A/B关系的设施，但存在有C关系（是设定的TCR的最小值）的设施，分别是D2和D5，随机确定，如D2； 与D2存在有A关系的设施，即D1，因此第4个设施是D1； 最后一个是D5。 即进入顺序为34215。,依照顺序布置设施,计算质量指标,可进行多次布局，生成多个方案 选择Z值最大的作为最终方案。,CRAFT布局算法,简介,CRAFT（Computerized Relative Allocation of Facilities Technique）是Buffa等人于1964年提出的。 其优化目标是使物流节点内的总搬运费最少。 CRAFT是一种改进型的算法，对一个初始可行布置方案，它给出了一种使总搬运费用减少的调整方法，并保证调整后的方案仍是可行布置方案。,目标函数,关于设施交换,设施交换是CRAFT一个重要操作，通过两个设施的位置的交换，企图降低总体的搬运成本。设施交换操作需要注意：相互交换的设施必须满足具有公共边或者面积相等，以便使得位置交换后不引起其它设施位置的变化。,CRAFT算法,输入：设施数n，流量矩阵Q=(qij)，单位距离成本矩阵C=(cij)，初始布局方案P0。 输出：布局方案P，总搬运成本Z。 步骤： 第1步：将规划区按要求划分成若干面积相等的方形小单元（方便交换），满足每个设施至少包含1个单元，且每个单元只在1个设施中。 第2步：计算P0中各个设施的折线距离dij和目标函数Z0。 第3步：列出所有满足交换条件的设施交换方案，进行逐个交换，选择目标函数最小的布局作为交换结果，记为P，所对应的目标函数值为Z。 第4步：若Z Z0 ，则令Z0 = Z ， P0 =P，重复第2、3步；否则令Z = Z0 ， P = P0 ，计算停止。,案例,某配送中心5个设施之间的货物流量矩阵Q和一个初始布局方案P0如图，试用CRAFT算法对该方案进行调整。,第1步：,区域划分,计算距离矩阵,其中，单位距离成本cij设为1,第2步,列出P0所有的满足交换条件的设施交换方案，分别是1-2，1-3，1-5，2-3，2-4，2-5，3-5，4-5（1-4不能交换是因为两者面积不等，也没有公共边）。 先交换1-2，并计算距离矩阵与Z。 继续对1-3、1-5、2-3、2-4、2-5、3-5、4-5等交换，分别计算出Z，直到找到搬运费下降最大的一种交换，结束本轮交换。,P0,P,ZZ0,第3步,第1轮交换结束后，绘制出首轮布置图。针对这一布置图，再次进行具有公共边（或面积相等）的设施的新一轮交换。 直到搬运费用不再降低为止。,CRAFT算法的注意事项,计算结果与所划分的单元大小有关 当单元划分太大，则可行的交换方案少，很难优化目标函数。 当单元面积太小，则计算结果可能使得各设施的形状很不规则，在实际布局中无法接受，同时也增加计算次数。,MultiPLE布局算法,简介,MultiPLE（Multi-floor Plant Layout Evaluation）时类似于CRAFT的一种改进的算