物流节点选址模型与方法北京交通大学经济管理学院何为物流节点选址?•物流节点选址通常也称为物流设施选址,是指在一个具有若干供应点及若干需求点的经济区域内,选一个地址设置物流设施的规划过程。•较佳的物流节点选址方案是使商品通过物流节点的汇集、中转、分发,直至输送到需求点的全过程的效益最好。物流节点选址方法•物流节点选址涉及的问题比较多,其中定量化分析是其中的重要内容,本章在分析物流节点选址的程序和步骤的基础上,重点对几种定量化方法进行探讨。•这些方法包括:整数规划方法、重心法、鲍摩-瓦尔夫模型方法、物流节点选址方法的改进模型、基于遗传算法的物流节点选址规划方法等。第一节物流设施选址问题•物流设施选址问题的类型•设施选址问题的特点•物流设施选址问题示例物流设施选址问题的类型•目前己形成了多种选址方法,按选择的离散程度大致可分为连续选址模型(ContinuousLocationModels)与离散选址模型(DiscreteLocationModels)两类。•连续选址模型认为可以考察一个连续空间内所有可能的点,并选择其中最优的一个或多个,其代表性的方法是重心法(CentroidMethod)。•离散选址模型则是指在一系列可能方案中做出选择,这些方案事先已经过了合理性分析,代表性模型有鲍摩-瓦尔夫(Baumo1-wolfe)模型、B1son模型和奎汉·哈姆勃兹提出的KuehnHamhurger模型等。物流设施选址问题的类型•从选址目标来看,物流设施选址有三种基本类型和综合型。三种基本类型分别是:成本最小化类型、服务最优化类型和物流量最大化类型。•除了这三种基本类型外,对于有些物流项目,单独考虑成本、服务和物流量尚不能满足投资决策者的需要,这时可能要综合考虑多方面的目标来进行物流设施选址,这时较多采用多目标决策的方法。设施选址问题的特点(1)•选址决策是研究不同层次的人类组织的选址问题,从个人、家庭到公司、政府机构甚至是国际机构。•选址决策是一个战略决策,需要考虑长期的资金利用和经济效益。对于私营设施,选址决策直接影响到公司在市场上的竞争实力;对于公用设施,选址决策会影响到提供公用服务的效率和公众享受公用服务的公平性。设施选址问题的特点(2)•选址决策还涵盖了经济的外延含义。包括污染、交通拥挤和经济发展潜力等。•由于大多数选址问题是NP-hard问题,很难求得选址模型的最优解,特别是大型问题。•选址问题都有相应的应用背景,模型的结构(目标函数、变量和约束)由相应的应用背景决定。没有一个通用的模型可以解决所有的选址问题。物流设施选址问题示例(1)•已知A村每年产粮食50吨,B村40吨,C村60吨,D村20吨,E村70吨,F村90吨。问该粮库应建在哪一个村子,使各村送粮食最方便?AFEDCB2781361364物流设施选址问题示例(2)•显然,这个问题寻求最优化的原则是保持所有各村运输总量(吨公里)最小,在此基础上尽可能使得各村运输量比较均衡。•最直观的求解方法就是分别计算出在6个备选地点建粮库所对应的总运量,然后选择总运量最小的备选地点建粮库。•可先采用Floyd算法计算图中任意两点间的最短路,然后再计算对应的总运输量,如表4-1和表4-2。通过计算(计算过程略,读者可以自己练习),在D村建设粮库是最佳选择。如需知道其它各村将粮食运往粮库(D村)的运输路径,只需记录Floyd算法计算过程中最短路的路径即可。各产地到粮库的运量产地粮库位置ABCDEF总运量A0803601405609902130B10002401004208101670C3001600201404501070D350200600703601040E4002401202002701050F5503603008021001500产量504060207090选址问题小结•通过这一例子可以看出,选址问题就是根据一定的给定条件,在满足要求的前提下选择最优方案。•小规模、复杂性较低的选址问题一般比较好解决,大规模、复杂性较高、约束条件较多的选址问题,采用枚举法是行不通的。•对于连续型选址问题,更是无法采用枚举法来求得最优解。•当然,还有很多选址问题尚没有找到很好的求解方法,也就是说,求解精确最优解可能只是一种奢望,对于这类问题,采用启发式算法寻求满意解是较好的选择。第二节物流设施选址的程序和步骤•选址约束条件分析•搜集整理资料•地址筛选•定量分析•结果评价•复查和确定选址结果复查图4-2物流设施选址的程序地址筛选定量分析确定选址结果选址约束条件分析物流系统的现状分析地图、地价、业务量、费用分析、配送路线、设施现状的分析及需求预测。单一配送中心选址方法(如重心法等)多个配送中心选址方法(如鲍摩、瓦尔夫模型;CELP法等)选址的制约条件地理、地形、地价、环境、交通条件、劳动条件及有关法律的研究。结果评价市场的适应性;购置土地条件;服务质量;总费用;商流、物流的职能及其他。收集整理资料选址约束条件分析•需求条件•运输条件•配送服务的条件•用地条件•法规制度•流通职能条件•其他搜集整理资料•对业务量和生产成本进行正确的分析和判断•掌握业务量•掌握费用•其它地址筛选•在对所取得的上述资料进行充分的整理和分析,考虑各种因素的影响并对需求进行预测后,就可以初步确定选址范围,即确定初始候选地点。定量分析•针对不同情况选用不同的模型进行计算,得出结果。如对多个物流设施进行选址时,可采用奎汉·哈姆勃兹模型、鲍摩-瓦尔夫模型、CELP法等;如果是对单一物流设施进行选址,可采用重心法等。结果评价•结合市场适应性、土地购置、服务质量等条件对计算所得结果进行评价,看其是否具有现实意义及可行性。复查•分析其它影响因素对计算结果的相对影响程度,分别赋予它们一定的权重,采用加权法对计算结果进行复查。如果复查通过,则原计算结果即为最终结果;如果复查发现原计算结果不适用,则返回第三步继续计算,直至得到最终结果为止。确定选址结果•在用加权法复查通过后,则计算所得的结果即可作为最终的计算结果。但是所得解不一定为最优解,可能只是符合条件的满意解。选址的注意事项•选址固然重要,但选址又十分困难,其原因有三方面。–选址因素相互矛盾。–不同因素的相对重要性很难确定和度量。–判断的标准会随时间变化而变化,现在认为是好的选址,过几年就不一定是好的了。•因此,可以说选址问题包含的环节多、难度大。大中城市的物流设施应采用集中与分散相结合的方式选址;在中小城镇中,因物流设施的数目有限且不宜过于分散,故宜选择独立地段;在河道(江)较多的城镇,商品集散大多利用水运,物流设施可选择沿河(江)地段。应当引起注意的是,城镇要防止将那些占地面积较大的综合性物流设施放在城镇中心地带,以防止给城市带来交通不便和环境污染。不同类型物流设施选址注意事项•转运型物流设施大多经营倒装、转载或短期储存的周转类商品,大都使用多式联运方式,因此一般应设置在城市边缘地区的交通便利的地段,以方便转运和减少短途运输。•储备型物流设施主要经营国家或所在地区的中、长期储备物品,一般应设置在城镇边缘或城市郊区的独立地段,且具备直接而方便的水陆运输条件。•综合型物流设施经营的商品种类繁多,根据商品类别和物流量选择在不同的地段。例如与居民生活关系密切的生活型物流设施,若物流量不大又没有环境污染问题,可选择接近服务对象的地段,但应具备方便的交通运输条件。第三节整数规划选址方法•0-1整数规划方法选址问题的提出•引入0-1变量的实际问题•用0-1变量建立规划模型的思路与技巧•隐枚举法•混合整数规划选址示例0-1整数规划方法选址问题的提出•所谓选址问题,就是从s个候选库址中选取一个最佳地址建库,使物流费用达到最低。0-1整数规划方法选址问题的提出•设Cij表示从Ai到Dj的每单位运输量的运输成本;djk表示从Dj到Bk的每单位运输量的运输成本。引进变量:X=(Xl,X2,…,Xs)。其中•那么选址问题表述为:建库在建库不在jjjDDx10sjjjsjminkkjkiijxtosubjectxQdpcxf11111min引入0-1变量的实际问题•相互排斥的选址项目•某公司拟在地区的东、西、南三区建立存储点,拟议中有7个位置Ai(i=1,2,…,7)可供选择。规定:•在东区,由A1,A2,A3三个点中至多选两个;•在西区,由A4,A5两个点中至少选一个;•在南区,由A6,A7两个点中至少选一个。•如选用Ai点,设备投资估计为bi元,每年可获利润估计为ci元,但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?引入0-1变量的实际问题•解题时先引入0-1变量xi(i=1,2,…,7),令•于是问题可列成:点被选用当点没被选用当iiiAAx1010112*76543217171或jiiiiiixxxxxxxxBxbxcMaxZ用0-1变量建模的思路与技巧•在一组(J个)相互排斥的事件中,至多只能选择一个事件•如果只是在选择事件l的情况下,才考虑是否选择事件k•问题只要满足两个约束之一即可•在p个约束条件中至少要满足k个约束条件•有界变量的整数规划与0-1规划的等价性问题隐枚举法•方法之一是设置目标函数的过滤值•其基本原理是:对于当前欲检验的点,如果其目标函数值比已知的某个可行点的目标值差,那么这个当前点就没有必要去检验是否是可行点。也就是说,事先找到一个可行点,以其目标函数值作为过滤值,对其它未检验的点,首先计算其目标函数值,若比过滤值差,则不再检验其可行性;若目标函数值优于过滤值,则进一步检验其可行性,若不是可行点,则放弃该点,若是可行点则记下该点为当前最优点,并以其目标函数值作为新的过滤值,再对其他未检验点进行检验。这样,就可减少大量的计算量。隐枚举法•方法之二是对原问题的目标函数(尤其是当目标函数是线性时,效果更好)及约束条件进行适当的调整处理,找出目标函数值增大(或减少)的规律,以减少大量工作量。混合整数规划选址示例•某集团公司考虑生产一种童衣系列。童衣产品将由工厂运至配送中心,再由配送中心将产品运至分销店。该集团有5家工厂(备选工厂)可生产这类童衣,有3家配送中心(备选配送中心)可以配送童衣产品,有4家分销店经营童衣产品。这些工厂和配送中心的年度固定成本如表4-3。工厂的年生产能力和工厂到各备选配送中心的单位运价如表4-4所示。配送中心运至各分销店的运输成本和各分销店的需求量如表4-5所示。表4-3工厂与配送中心的固定成本单位工厂1工厂2工厂3工厂4工厂5配送中心1配送中心2配送中心3年固定成本(元)3500045000400004200040000400002000060000表4-4工厂的年生产能力和工厂到各备选配送中心的单位运价终点起点运输成本(元/箱)生产能力(箱)配送中心1配送中心2配送中心3工厂1工厂2工厂3工厂4工厂580070080050070010005006006006001200700500700500300200300200400表4-5配送中心运至各分销店的运输成本和各分销店的需求量终点起点运输成本(元/箱)分销店1分销店2分销店3分销店4配送中心1配送中心2配送中心3407080804030906050508060需求量(箱)200300150250Zmin=T1*(800*X11*S1+1000*X12*S2+1200*X13*S3)+T2*(700*X21*S1+500*X22*S2+700*X23*S3)+T3*(800*X31*S1+600*X32*S2+500*X33*S3)+T4*(500*X41*S1+600*X42*S2+700*X43*S3)+T5*(700*X51*S1+600*X52*S2+500*X53*S3)+S1*(40*Y11+80*Y12+90*Y13+50*Y14)+S2*(70*Y21+40*Y22+60*Y23+80*Y24)+S3*(80*Y31+30*Y32+50*Y33+60*Y34)