物流系统选址规划设计.ppt

武汉工贸职业学院周丽娜,物流系统规划与设计,第4章物流系统选址规划设计,本章学习目标：物流系统选址规划的目标物流节点选址问题分类、方法选择决策的影响因素选址问题早期研究理论及选址技术方法,引言,Wal-Mart创始人山姆说“连锁超市成功的关键有3个条件，那就是选址、选址、还是选址”连锁店选址的5件事：1.对于人流量调查结果的分析有效客流量；2.对竞争对手的分析估计销售潜力、制定有效策；3.地理位置方便顾客；4.成本的核算考虑零售店之间、零售店与配送中心之间的距离，充分发挥规模经济效益5.交通状况在车站下方，避免在道路狭窄、停车场小、车流过大的地方等。,4.1物流系统选址规划概论,4.1.1物流节点选址的意义物流系统的选址决策就是确定整个物流系统中所需的节点数量，它们的地理位置，以及服务对象分配方案。设施选址问题是物流网络中一项十分重要的战略决策。决定了整个物流网络的模式、结构和性状。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。,宏观物流（社会物流系统）关注物流园区物流中心等节点的选址物流节点的选址决策就是确定整个社会物流系统中所需要的节点数量、位置、以及服务对象分配方案。,物流园区的选址日本在上世纪70年代就提出了物流园区的思想，他们在一些作为流通重点的城市周围建立了若干集约运输、仓储、市场、信息管理功能的物流园区，这些园区对于日本随后的经济崛起发挥了重要的作用促进了日本物流业的快速发展。物流园区的选址首先要考虑物流市场的需求，规划不合理，会导致园区之间竞争资源，或者因园区中物流企业数量不足而未能发挥有的效果，或者因物流场所和设备的多余闲置而造成物流资源的浪费。物流园区的布局还要考虑土地资源、交通设施、劳动力素质与成本、环境等多方面的因素。,微观物流（企业物流系统）关注配送中心、仓储设施、工厂的选址单个企业的物流网络系统，一方面，物流节点的选址决策影响整个企业物流系统的结构和系统中其它要素的决策，例如库存、运输等；另一方面，系统中其它要素的决策也会影响到物流节点的选址。因此，重点考虑选址与运输、库存成本之间的关系。供应链体系中，一个企业的物流系统选址决策往往要受到供应链中其它企业的影响，供应链系统中的核心企业的选址决策将影响到所有供应商的物流系统的选址。例如：Dell工厂的选址，将影响到供应商和物流服务商的节点选址。,物流中间节点的数量增加，可以提高服务及时率，减少缺货率，但也会增加库存量与库存成本。在规划设计中采取的重要措施是：尽量减少物流中间节点数量，扩大中间节点规模。在物流园区规划中采用集约化设计，实现大规模配送。同样，物流节点的数量增加，可以减少运输距离，降低运输成本，但如果增加到一定程度，由于订单的数量过少，增加了运输频率，并且达不到运输批量，从而造成运输成本的大幅上涨。因此，物流节点数量与运输成本之间也形成制约关系。,确定合适得到物流节点数量是选择规划的重要任务之一。,4.1.2物流节点选址规划的目标,物流节点选址的目标,1、成本最小化,2、物流量最大化,3、服务最优化,4、发展潜力最大化,5、综合评价目标,成本主要包括运输成本与设施成本,服务指标主要包括送货时间、距离、速度和准时率,物流量的主要指标是吞吐量和周转量,1、成本最小化最常用的目标，主要包括运输成本和设施成本。（1）运输成本取决于运输数量、运输距离与运输单价。（2）设施成本与设施相关的成本包括固定成本、存储成本和搬运成本。固定成本是指那些不随设施的经营活动水平而改变的成本。存储成本是指那些随设施内货物数量变化而改变的成本。搬运成本是指随着设施吞吐量变化的成本。,2、物流量最大化物流量是反映物流节点作业能力的指标，主要包括吞吐量和周转量。从投资物流节点来看，以上两个指标用来测量物流节点的利用率，物流量越大，效率越高。但从整个物流系统的发展来看，吞吐量和周转量无法适应多品种、小批量、高频度的趋势，如物流节点与客户距离越远，则周转量越大，费用也越高。如果以货物运输吨数和公里数的最大化为决策目标时，物流节点选址与客户的距离越远越好，这显然违背了设置物流节点的根本目的。因此要在成本最小化的前提下，考虑物流量最大化,3、服务最优化与选址决策直接相关的服务指标有：送货时间、距离、速度和准时率。物流节点与客户距离越近，送货速度越快，订货周期也越短，而订货周期越短，准时率也越高。4、发展潜力最大化既要考虑现状，也要考虑将来发展潜力，包括物流节点生产扩展的可能性及顾客需求增长的潜力。5、综合评价目标单一目标不能满足物流系统经营需要，需要采用多目标决策的方法来综合评价。,4.1.3物流节点选址问题的特点,在选址问题的研究中，Daskin总结了五个特点：（1）选址决策是研究不同层次的人类组织的选址问题，从个人、家庭到公司、政府机构甚至是国际机构。（2）选址决策是一个战略决策，需要考虑长期的资金利用和经济效益。（3）选址决策还涵盖了经济的外延含义，包括污染、交通拥挤和经济潜力等。（4）由于大多数选址问题是NP_HARD问题，很难求得选址模型的最优解，特别是大型问题。（5）选址问题都有相应的应用背景，模型的结构（目标函数、变量和约束）由相应的应用背景决定。,4.1.4物流结点选址问题的分类,物流结点选址问题是指用数学方法确定物流系统中网点的数量、位置和规模，其目标是通过合理规划物流网络的结构和布局，使物流成本达到最小。在建立一个选址模型之前，需首先确定以下几个问题：（）选址的对象是什么？（）选址的目标区是怎样的？（）选址目标和成本函数是什么？（）有什么样的一些约束？根据以上这些不同的问题，选址模型可以分为相应的类型，不同的类型将建立不同的数学模型，进而选择相应的算法进行求解。这样，就可以得到该选址问题的方案。,分类标准,一般，可将选址问题按下面几种方法分类：按设施对象划分按设施的维数划分按设施的数量划分按选址的离散程度划分按目标函数划分按能力约束划分,1、按设施对象划分,不同的物流设施其功能不同，选址时所考虑的因素也不相同；在决定设施定位的因素中，通常某一个因素会比其他因素更重要。在工厂和仓库选址中，最重要的因素通常是经济因素。零售网点选址时最重要的因素是零售服务顾客的消费偏爱。服务设施（如医院、银行）选址时，到达的容易程度则可能是首要的选址要素，在收入和成本难以确定时，尤其如此。在地点带来的收入起决定性作用的选址问题中，地点带来的收入减去场地成本就得到该地点的盈利能力。,、按设施的维数划分,根据被定位设施的维数，可以分为体选址、面选址、线选址和点选址四种类型：）体选址是用来定位三维物体的，例如卡车和飞机的装卸或箱子外货盘负载的堆垛；）面选址是用来定位二维物体的，例如一个制造企业的部门布置；）线选址是用来定位一维物体的，例如在配送中心分拣区域，分拣工人向传递带按照订单拣选所需要的货品；）点选址是用来定位零维设施的。相对于设施的目标位置区域而言，当设施的尺寸可以忽略不计时，可使用点选址模型。大多数选址问题和选址算法都是基于这种情况的。本章主要介绍的是点选址模型，如在工业企业的配送系统中定位一个新的配送中心。,、按设施的数量划分,根据选址设施的数量，可以将选址问题分为单一设施选址问题和多设施选址问题。单一设施的选址与同时对多个设施选址是截然不同的两个问题，单一设施选址无需考虑竞争力、设施之间需求的分配、集中库存的效果、设施成本与数量之间的关系等，而运输成本是要考虑的首要因素。单一设施选址是两类问题中较简单的一类。,、按选址的离散程度划分,按照选址目标区域的特征，选址问题分为连续选址和离散选址两类。连续选址问题是指在一个连续空间内所有点都是可选方案，需要从数量是无限的点中选择其中一个最优的点。称作连续选址法，这种方法常应用于设施的初步定位问题。离散选址问题是指目标选址区域是一个离散的候选位置的集合。候选位置的数量通常是有限的，可能事先已经过了合理分析和筛选。这种模型是较切合实际的，称为离散选址法,常应用于设施的详细选址设计问题。,、按目标函数划分,按照选址问题所追求的目标和要求不同，模型的目标函数可分以下几种：）可行点最优点:对于许多选址问题来说，首要的目标是得到一个可行的解决方案，即一个满足所有约束的解决方案。可行方案得到以后，第二步的目标是找到一个更好的解决方案。,）中值问题（minisum):在区域中选择（若干个）设施位置，使得该位置离客户到最近设施的距离（或成本）的“合计”最小。这种目标通常在企业问题中应用，所以也称为“经济效益性”。在中值问题中，被选择设施的数量往往预先确定，当选择设施数量为时，称为-中值问题。,X：新的待定设施的位置坐标j：已存在且位置固定的需求点编号：新设施在X位置时到需求点j的成本,）中心问题(min-max):根据使得被选择设施的位置离最远需求点的距离（或成本）集合中取最小的原则，在区域中选择设施的位置的方法称为中心问题。其目标是优化最坏的情况，由已存在设施的单个成本（或距离）最大的部分组成，其目标函数可以表示为：其中，为新的待定设施的位置，j为需求点编号，j()为新设施在位置时到需求点j的距离（或成本）。,4）反中心问题(max-min):根据使得被选择设施的位置离最近需求点的距离（或成本）集合中取最大的原则，在区域中选择设施的位置的方法称为反中心问题。其目标也是优化最坏的情况，由已存在设施的单个成本（或距离）最小的部分组成，其目标函数可以表示为：其中，为新的待定设施的位置，j为需求点编号，j()为新设施在位置时到需求点j的距离（或成本）。,5）单纯选址问题选址分配问题:如果新设施和已存在设施间的关系与新设施的位置无关，而是固定的，则选址问题称为单纯选址问题，也称为有固定权重的选址问题。如果这种权重或关系与新设施的位置相关，那么，这些权重本身就成为变量，这种问题被称作“选址分配问题”。例如，配送中心的客户分配问题，添加一个新的配送中心不仅改变了原配送中心的客户分配，同时也改变了配送中心到客户的距离。,、按能力约束划分,根据选址问题的约束种类，可以分为有能力约束的选址问题和无能力约束的选址问题两种，如果新设施的能力可充分满足客户的需求，那么，选址问题就是无能力约束的设施选址问题；反之，若各设施具有所能够满足需求的上限，就是有能力约束的选址问题。无能力约束设施选址问题往往被称为“单纯设施配置问题”,4.1.5物流结点选址的方法,近年来，选址理论迅速发展，特别是计算机的应用，促进了物流系统选址的理论发展，对不同方案的可行性分析提供了强有力的工具。物流结点选址的方法大体上有以下几类：、专家选择法、精确法、模拟计算法4、启发法,、专家选择法,专家选择法是以专家为索取信息的对象，运用专家的知识和经验，考虑选址对象的社会环境和客观背景，直观地对选址对象进行综合分析研究，寻求其特性和发展规律并进行选择的一类选址方法。专家选择法中最常用的有因素分析法、德尔菲法、模糊综合评价法与层次分析法。,、精确法,精确法是通过数学模型进行物流网点布局的方法。采用这种方法首先根据问题的特征、已知条件以及内在的联系建立数学模型或者是图论模型，然后对模型求解，获得最佳布局方案。采用这种方法的优点是能够得到较为精确的最优解，缺点是对一些复杂问题建立恰当的模型比较困难，因而在实际应用中受到很大的限制。解析法中最常用的有重心法和线性规划法两种。,、模拟计算法,模拟计算法是将实际问题用数学方法和逻辑关系表示出来，然后通过模拟计算及逻辑推理确定最佳布局方案。这种方法的优点是比较简单，缺点是选用这种方法进行选址，分析者必须提供预定的各种网点组合方案以供分析评价，从中找出最佳组合。因此，决策的效果依赖于分析者预定的组合方案是否接近最佳方案。该法是针对模型的求解而言的，是一种逐次逼近的方法。对这种方法进行反复判断，实践修正，直到满意为止。该方法的优点是模型简单，需要进行方案组合的个数少，因而，容易寻求最佳的答案。缺点是这种方法得出的答案很难保证是最优化的，一般情况下只能得到满意的近似解。,4、启发法,指可以有助于减少求解平均时间的任何原理或概念，也可以是用启发法表示为指导问题迅速解决的经验原则。当经验原则运用到选址问题时，有助于加快求解过程的经验可迅速从大量被选方案中找出好的解决方案。采用该方法可以带来合理的计算时间和内存空间要求，可以很好地表现实际情况，得到满意解。,1、选址决策的外部因素（1）宏观政治、经济因素宏观政治因素：国家的长远发展战略、政权稳定、法制健全；宏观经济因素：税收政策、关税、汇率；（2）基础设施及环境基础设施因素：物流基础设施、通信设施可利用性；交通运输状况、运输费率。环境因素：自然环境及社会环境，如总体规划情况，生产要素供应情况，劳动力成本、供应数量、素质等；（3）竞争对手要考虑竞争对手的布局情况,4.1.6选址决策的影响因素,2、选址决策的内部因素选址决策时要使选择的方案与企业发展战略相适应，与生产产品或提供服务的特征相匹配。例如：产品的类型：实用性产品（低成本物流）还是创新产品（快速反应物流）；商业物流体系：连锁便利店还是大型超市，设施的布局是不一样的。,4.1.7物流节点选址的一般原则,1、经济发展中心地区和城市2、各种交通方式重叠和交汇地区3、物流资源较优地区4、土地开发资源较好地区5、支持产业发展需要6、符合区域物流特点7、有利于整合物流网络的优化8、有利于各种节点的合理分工、协调配合9、地区管理和人才资源较好地区,4.1.8物流节点选址的步骤和程序,一、物流设施选址约束条件分析,（一）需求条件（二）运输条件（三）配送服务的条件（四）用地条件（五）法律法规（六）流通职能条件（七）其他,（一）掌握业务量（1）工厂到物流设施之间的运输量（2）向顾客配送的货物数量（3）物流设施保管的数量（4）配送路线上的其他业务量（二）掌握费用（1）工厂至物汉设施之间的运输费；（2）物流设施到顾客之音质配送费；（3）与设施、土地有关的费用及人工费、业务费等。,二、搜集整理资料,三、地址筛选四、定量分析五、结果评价六、复查七、确定选址结果八、选址的注意事项（1）选址因素相互矛盾（2）不同因素的相对重要性很难确定和度量（3）判断的标准会随时间变化而变化,目前物流选址的趋势,4.2选址问题的早期研究理论,4.2.1选址研究历程设施选址是一个十分古老而又经典的问题，古代的选址决策往往以经验、制度甚至迷信思想为依据，缺乏科学性。1909年德国学者韦伯第一篇选址论文的发表标志着设施选址问题进入到科学研究的时代。在其发展的百年历史中，各时期研究侧重点各有不同。按时间可分为三个阶段1.零散研究阶段（19091960s）。2.系统研究阶段（1960s1980s）3.不确定性问题研究阶段（1980s至今）,1、零散研究阶段（19091960s）。,该阶段研究侧重于解决生产、生活中的各种实际问题，内容零散，经济学者在此阶段早期有突出贡献。早在1909年德国经济学家韦伯（AlfredWeber）在其工业区位论文中研究如何使单个仓库到不同客户总距离最短，该文是最早的设施选址论文。另一位早期设施选址问题研究学者Hotelling在其1929年发表的论文中考虑两个竞争供应商在一直线的区位选择并构建选址模型。随后Smithies(1941)、Stevens(1961)对此问题进行了更深入的研究。区域经济学家Isard（1956）还从土地利用、投入产出等角度入手对工业区位的选择进行分析。上世纪50年代，越来越多的研究者偏重于设施选址的实际应用，包括产品销售网点的分布与设计（Losch1954与Moses1958）、消防设施选址（Valinsky1955）、垃圾处理厂选址（Wersanetal.1962）、电话网络程控交换设备选址（Rapp1962）、铁路货运编组站选址(MansfieldanWein1958)等。,2、系统研究阶段（1960s1980s）,1964年Hakimi关于网络多设施选址论文的发表标志着设施选址问题已成为一个系统、科学的理论。此后，选址问题被引入一个更宽广的领域，包括生产中心选址（Eilonetal.1971）、交通枢纽选址（WirasingheandWaters1984）、变电站选址（Hochbaum1982）等等。研究方法也更集中于运筹学、拓扑学，经济学方法的应用越来越少。,3、不确定性问题研究阶段（1980s至今）,进入上世纪80年代，随着市场变化加剧，实际生产、生活中运输时间、需求量、需求空间分布以及设施建造成本等输入变量都是不确定性因素，以往静态、确定性选址模型与方法已不能适应选址研究的发展。随机选址问题已成为众多学者关注的焦点。Louveaux(1986)、Mirchandanietal(1985)、WeaverandChurch(1983)等学者在对不确定中值问题研究时均将运输时间与需求设为随机变量。BermanandOdoni(1982)、BermanandLeblanc(1984)将运输时间或运输成本设为不确定决策变量研究随机网络的交通问题。,4.2.2杜能的地租出价曲线（Bid-RentCurves）,杜能认为，经济活动能支付的最高地租是产品的市场价格与运输成本之差，经济活动将根据其支付地租的能力分布在城市中心（或运输枢纽）周围。在农业经济中，各种农业生产活动可能按下图所示的方式从市场向外布局。,4.2.3韦伯AlfredWeber的工业分类,工业区位论的奠基人韦伯认识到原材料运输在生产过程中所起的作用及其对选址的影响。根据原材料与成品之间的重量不同，将生产过程分为：失重的，原材料重量之和大于成品重量。如炼钢（有无用的副产品），生产过程倾向于接近原材料产地增重的，普遍存在的要入进入生产过程，如空气和水，如罐装饮料行业；生产过程尽量靠近市场。等重的，如装配先生产，生产场地应相应地靠近零部件聚集产地或销售市场。,五种指向型的工业类型,4.2.4胡佛的递减运输费率,考虑到运输费率随距离的增加而增幅下降，如果运输成本是选址的主要因素则选址就在原料产地或市场。,靠近市场：外向运输成本(从仓库到顾客的运输成本)降低，内向运输成本(从供应商、制造商到仓库的运输成本)增加。,4.2.5区域经济学理论,研究一国或一个区域内经济运行的特定规律，生产力布局的特定要求或经济发展的特定模式；研究确立多层次的经济规划体系，实现地域分工；使各地人力、自然资源得到充分利用，人尽其才，地尽其利。城市功能分区政务区、商贸流通区、商务中心区、旅游区、居民居住小区的划分；,4.3选址的技术与方法,4.3.1选址问题中距离计算选址问题模型中，最基本的一个参数是各个节点之间的距离。一般采用三种方法来计算节点之间的距离，一种是直线距离，也叫欧几里德距离（EuclideanMectric）；另一种是折线距离（RectilinearMetric）,也叫城市距离（MetropolitanMetric）；第三种是大圆距离，利用球面三角学计算。,1、直线距离,区域内两点和间直线距离计算公式为:(4-1)其中，称为迂回系数，一般可取定一个常数，当取为1时，为平面上的几何直线距离,取值的大小要视区域内的交通情况，在交通发达地区，取的值较小；反之，取值较大。如在美国大陆，是1.2，而在南美州,是1.26。,、折线距离,折线距离也称为城市距离，当选址区域的范围较小而且区域内道路较规则时，可用折线距离代替两点间的距离。如城市区的配送问题、具有直线通道的配送中心、工厂及仓库内的布置、物料搬运设备的顺序移动等问题。折线距离的计算公式如下：（4.）,3、大圆距离,各种地图制图激素讲球体映射到平面上会引起变形。故用平面坐标来计算距离会产生误差，误差大小取决于地图映射方法以及在地图上的什么位置计算距离。采用经纬度坐标和大圆距离公式即可避免误差，而且还考虑到地球的弯曲程度。,4.3.2单一物流节点的选址模型,中值问题引入在一条直线上（街道）选择一个有效位置（商店）即一种设施选址，为了能让在这条街上的所有客户到达商店的平均距离最短。在不考虑其他因素的情况下，当然这条大街的中点是最为合理的位置。但实际上各位置上顾客的频率是不同的，所以还需要给不同位置赋予一个权重wi，于是该中值问题可以表示成如下的目标函数：(4-3)(4-4),对上述模型求解，首先对等式两边求微分，然后令微分值为零，结果如下：通过上述公式，得出如下结论：求上述中值问题时，所开设的新店面需要设置在权重的中心，即设置点的左右两边的权重和都占50。,例如，假设在一条线上，在位置0、6、8和10上分别有4个点，为每个点服务的成本与这些点到新设施之间的距离成正比，并且权重相同，求：新设施的最优位置？假如最左面的点在500，而不是0，新设施的最优位置？答：这些点的中值点，即点6到点8之间的一条线段。对于中值问题，固定位置的顺序比他们的实际位置更加重要。,对于中心问题，上述问题的最优位置是这些点的中心点，x*=5,新址位置到最左边点和到最右边点的距离是相等的，中心问题的选址是由那些极端位置决定的，而其它内部的位置对它不起作用。对于反中心问题,在一定区域内（0-10之内）的最优位置是这些店的反中心点，x*=3,新址位置是相邻点间距离最大的两点的中心，反中心问题的选址是由相邻点间距离最大的两点位置决定的，而其它内部的位置对它不起作用。,1、交叉中值模型,交叉中值模型是利用折线距离来进行距离计算，用来解决连续点选址（在一条路径内任何一个位置都可以作为选址问题的候选解）问题的一种有效的模型。通过交叉中值的方法可以对单一的选址问题在一个平面上的加权的城市距离进行最小化。,其相应的目标函数为：在这个问题里面，最优位置也就是由如下坐标组成的点：是在x方向的对所有的权重的中值点；是在y方向的对所有的权重的中值点。考虑到两者可能同时是惟一值或某一范围，最优的位置也相应的可能是一个点，或者是线，或者是一个区域。,式中：,与第i个点对应的权重（例如需求）；,第i个需求点的坐标；,服务设施点的坐标；,需求点的总数目。,例题4.1：一个冷冻食品公司想在一个地区开设一个新的冷食提货点，其主要的服务对象是附近5个住宅小区的居民。为了计算方便，把每个住宅小区的中心抽象成这个小区的需求点位置。权重表示每个月潜在的客户需求总量，可以用每个小区中的总居民数量来近似代表。已知五个小区点的坐标：A(3,2),B(4,3),C(5,1),D(1,4)和E(2,5),权重分别为：3，1，8，3，7。公司经理希望通过这些信息来确定一个合适的冷食提货点的位置，要求每个月顾客到这个冷食提货点所行走的距离总和最小。提示：先确定需求点的中值，再通过x轴与y轴分别进行计算讨论。,需求点对应的权重,首先，需要确定中值：从上表中得到中值：为了找到x方向上的中值点x0，在x方向只能选择一个有效的中值点：接着寻找在y方向上的中值点y0，发现在需求点A、B之间的范围内对于y轴方向都是一样的：,综合考虑x、y方向的影响，于是最后可能的地址为(3,2)、(3,3)之间的一条线段，见下图。,2、精确重心法前面介绍的交叉中值模型由于其本身的局限性，例如使用的是城市距离，只适合于解决一些小范围的城市内的选址问题。精确重心法在评价的过程中使用的是欧几米德距离，即直线距离，它使选址问题变得复杂，但是有着更为广阔的应用范围。重心模型是选址问题中最常用的一种模型，可以解决连续区域直线距离的单点选址问题。重心模型的基本假设：(1)需求量集中于某一个点上；(2)选址区域不同地点物流节点的建设费用和运营费用相同；(3)运输费用随运输距离成正比例增加，显线性关系。(4)运输路线为空间直线。,（1）问题描述设有n个客户（收货单位）分布在平面上，其坐标分别为()，客户的需求量为，费用函数为设施（配送中心）与客户之间的直线距离乘以需求量。确定设施的位置(),使总运输费用最小。这一类问题也称为Weber问题。,（2）建立模型配送中心到收货点每单位量、单位距离所需运费。的需货量。到的直线距离。则总运输费H为:(4-5),求H的极小值点（）。由于式（4-5）为凸函数，最优解的必要条件为满足：,(4-6)令,得,上式右端中仍含未知数故不能一次求得显解，但可以导出关于x和y的迭代公式：(4-7)(4-8)应用上述迭代公式，可采用逐步逼近算法求得最优解，该算法称为不动点算法,（3）算法（单一配送中心选址的不动点算法）输入：n客户数；()各客户点的坐标，；各客户点的单位运费和运量。输出：（）设施坐标;总运量,第一步：选取一个初始的迭代点,如：，然后计算出A到各客户点的直线距离和费用：,第二步，令，及，转第三步。第三步，若，运费已无法减小，输出最优解和，否则，转第四步。第四步：令，转第二步。,例4.2：运用精确重心法，对前面的冷冻公司提货点选址问题作一个假设，假设居民区以外的选址区域都是空地，使用欧几米德距离进行计算是合适的，然后我们就用精确重心法选择一个最优的位置。解：从点（3.5，2.5）开始进行欧几米德距离最优的搜索，可采用Excel软件进行计算，见教材65页。注意：用精确重心法得到的最优解只有一个点，而不会是一条线段或者一个区域。而且只有在十分偶然的情况下，才会出现用交叉中值法和精确重心法得到的最优优地址一致的情况。,4.3.3多物流节点选址模型,物流区域规划中，往往需要同时确定两个或者两个以上设施的位置，问题就变成更为复杂。由于不能将这些物流设施看成经济上相互独立的要素，而且可能存在向多的选址布局方式，寻求最优解很困难，因此问题自然十分复杂，但更接近实际情况，在实际工作中更普遍。多物流节点选址问题一般需要完成如下决策：如何组织货流？各个物流节点的关系如何？运输路线和各物流节点的关系怎样？网络中应该设几个物流节点？分别处于什么位置?物流节点服务于哪些顾客或者市场区域？规模多大？具有哪些功能？,重点介绍：多重心法、覆盖模型、P-中值模型、鲍摩瓦尔夫（Baumol-Wolfe)模型简要介绍：奎汉-哈姆勃兹（kuehn-Hamburge）模型、CFLP模型、多枢纽站单一分派轴辐式网络选址问题、多枢纽站多分派轴辐式网络选址问题,1、多重心法,多重心法的计算思路：第一步：初步分组。将需求点按照一定原则分成若干个群组，使分群组数等于物流节点的数量。第二步：选址计算。针对每一个群组的单一物流节点选址问题，运用精确重心法确定该群组新的物流节点的位置。第三步：调整分组。对每个需求点分别计算到多有物流节点的运输费用，并将每个需求点调整到运输费用最低的那个物流节点负责服务。第四步：重复第二步，直到族群成员无变化为止。此时的物流节点的分配方案为最优分配方案，物流节点的位置为最佳地址。手工计算起来非常麻烦，我们一般采用软件进行计算。如Logware软件的MULTICOG功能。,例4.3：某公司计划建立两个药品配送点向10个药品连锁店送货，各药品连锁店的地址坐标和药品每日需求量如表4-2所示，运价均为1，试确定这两个药品配送点的地址，是运输费用最低。计算过程见书本67页,2、覆盖模型,覆盖模型是一种离散点选址模型，即在有限的候选位置里，选择最合适的若干设施位置为最优方案。覆盖模型是指当设施服务半径一定时，对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。在这个模型中需要确定设施的最小数量和合适的位置。该模型适用于商业物流系统，如零售点的选址问题、加油站的选址、配送中心的选址等，公用事业系统，如急救中心、消防中心等，以及计算机与通信系统，如有线电视网的基站、无线通信网络基站、计算机网络中的集线器设置等。,根据解决问题的方法的不同，可以分为两种不同的主要模型：（1）集合覆盖模型，用最小数量的设施去覆盖所有的需求点。（2）最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求点。两类模型的区别：集合覆盖模型要满足所有的需求点，而最大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取决于服务设施的资源充足与否。,（1）集合覆盖模型集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点，相应的目标函数可以表达为：约束条件为：,最小化设施的数目,保证每个需求点的需求得到完全的满足,是对每个提供服务的服务网点的服务能力的限制,保证一个地方最多只能投建一个设施,允许一个设施只提供部分的需求,对于此类带有约束条件的极值问题，有两大类方法可以进行分解：一是精确的算法，应用分枝定界求解的方法，能够找到小规模问题的最优解，由于运算量方面的限制，一般也只适用于小规模问题的求解；二是启发式方法，所得到的结果不能保证是最优解，但是可以保证是可行解，可以对大型问题进行有效的分析、求解，可显著减少计算量。,例子：乡村医疗诊所选址问题卫生部门考虑到农村地区的医疗条件的落后和匮乏，计划在某一地区的9个村增加一系列诊所，以改善该地区的医疗卫生水平。它希望在每一个村周边30km的范围之内至少有一个诊所，不考虑诊所服务能力的限制。卫生部门需要确定至少需要多少个诊所和它们相应的位置。除了第6个村之外，其他任何一个村都可以作为诊所的候选地点，原因是在第6村缺乏建立诊所的必要条件。下图是各个村之间的相对位置和距离的地图。,第一步，找到每一个村可以提供服务的所有村的集合，即它们距该村距离小于或等于30km的所有村的集合。第二步，找到可以给每一个村提供服务的所有村的集合。一般说来，这两个集合是一致，但是考虑到其他的一些限制条件，就可能出现差异。第三步，找到其他村服务范围的子集，将其省去，可以简化问题。,第四步，确定合适的组合解。很显然，问题得到简化之后，在有限的候选点上选择一个组合解是可行的。候选点集合（3，4，7，8）本身就是一个组合解，但是为了满足经济性要求，尽可能少地建立诊所，还需要从中剔除可以被合并的候选点1、2、5、9。（3，8）则是可以覆盖所有村的一个数量最少的组合解：3村的诊所可以覆盖村1村到5村，而8村的诊所覆盖6村到9村。如果放宽一些问题的限制条件，例如一个诊所的服务半径增加到40km，也可能会出现多解的情况。（3，8），（3，9），（4，7），（4，8）和（4，9）都是可以覆盖所有的村而且数量最少的组合解。,（2）最大覆盖模型最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务。它的相应目标函数是：约束条件为：,是满足最大可能的对需求提供服务,是需求的限制，服务不可能大于当前需求的总和,是设施的服务能力的限制,是问题本身的限制，也就是说最多可能建设设施的数目,保证一个地方最多只能投建一个设施,允许一个设施只提供部分的需求,模型可采用精确求解法和启发式方法求解贪婪启发式算法：首先求出可以作为候选点的集合，并以一个空集作为原始解的集合；然后在候选点集合中选择一个具有最大满足能力的候选点进入原始解集合，作为二次解，以此重复，直到设施数目满足要求为止。,前面提到的医疗站问题，如果仍旧不考虑其服务能力的限制，最多的诊所数目为2，用最大覆盖模型对其进行分析，贪婪算法可以进行求解。在医疗站的问题中，我们已经分析得到候选集合为(3,4,7，8)。初步确定解的集合。然后比较A(3)、A(4)、A(7)和A(8)的数目，4村可以提供服务的对象最多，将4村加入到解集合S中，。接着比较3、7、8三个村，除去4提供服务的村1、3、4、5、6、7外，剩下只有，3村对2村提供服务。8村能服务8、9两个村，因此将8村作为第二个投建点加入到解集合中去，是我们通过最大覆盖法得到的解集合，显然不是最优解，这也是启发式算法的特点。,3、P中值模型P中值模型是指在一个给定数量和位置的需求集合和一个候选设施位置的集合下，分别为p个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在工厂和需求点之间的运输费用最低。,P中值模型也可以通过精确的数学语言进行描述。在用数学语言进行描述时，需要准确地表达问题的约束条件、目标、还有合理的变量定义。一般P中值问题的目标函数是：约束条件为：,是P中值模型的目标函数,保证每个客户（需求点）只有一个设施来提供相应的服务,限制了总的设施数目为p个,有效地保证没有设施的地点不会为客户服务,与覆盖模型一样，P中值模型主要有两大类算法：精确法和启发式算法。用启发式求解P中值模型的算法贪婪取走启发式算法（GreedyDroppingHeuristicAlgorithm）。这种算法的基本步骤如下：（1）第一步，初始化，令循环参数k=m，将所有的m个候选位置都选中，然后将每个客户指派给离其距离最近的一个候选位置；（2）第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令k=k-1；（3）第三步，重复第二步，直到k=p；,可以看出，求解一个P中值模型需要解决两方面问题：（1）选择合适设施位置（数学表达的变量X）；（2）指派客户到相应的设施中去（表达式中的变量Y）。例子：某饮料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地考查之后，已有4个候选地址。从候选地址到不同的仓库运输成本、各个超市的需求量都已经确定，如图所示。,这样就得到了k=3时的临时解（1,3,4）。重复上面步骤，对图2-15分别移走候选位置1、3、4进行计算，可以发现移走候选位置4的增量最小，所以第二次移走走第4个候选位置。最后的结果就是在候选位置1、3投建新的仓库，总的运输成本为：3740。值得注意的是，不是只有贪婪取走算法一种启发式算法，相应的还有贪婪加入算法（GreedyAddingHeuristic）、模拟退火算法（SimulatedAnnealing）、Tabu搜索（TS）等。,4、鲍摩瓦尔夫（Baumol-Wolfe)模型,（1）问题描述假设有m个资源点（工厂）的单一产品，从候选集合中选出若干个位置作为物流设施节点（如配送中心），使得从已知若干个资源点（如工厂），经过这几个设施网点（配送中心），向若干个客户运送同一种产品时总的物流布局成本（或运输成本）为最小，如图所示。也可能存在从某资源点直接将产品送往某个客户点。也称为多节点单品种选址模型,资源,配送网点,客户,1,2,3,m,1,2,3,n,1,2,3,q,i=,j=,k=,单品种多配送网点选址问题示意图,（2）建立模型记资源点i的产品供应量客户k的产品需求量；从资源点i到备选网点j的货物量；从备选网点j到客户k的货物量；客户k从资源点i直达进货物量；备选网点j是否选中的决策变量（0-1变量）；备选网点j从资源点i进货的单位物资进货费率；备选网点j向客户k供货的单位物资发送费率；客户k从资源点i直接进货的单位物资进货费率；备选网点j每单位货物通过量的变动费（如仓库管理或加工费等，与规模相关）；备选网点j选中后的基建设资费用（固定费，规模无关的费用）。,假设F为网点布局方案的总成本，根据网点布局的概念，应使总成本最低，于是有目标函数：在这个模型中，各个资源点调出的物资总量不大于该资源点的生产、供应能力，各个用户调运进来的物资总量不小于它的需求量，则有如下的约束条件存在：对于一个物流网点，由于它既不能生产物资，也不消耗物资，因此，每个物流网点调进的物资总量应等于调于物资的总量，即有如下的约束条件存在：,此外，网点布局经过优化求解后的结果，可能有的备选地址被选中，而另外的一些被淘汰。被淘汰的备选网点，经过它中转的物资数量为零。这一条件可由下面的约束条件满足；其中方程式中的M是一个相当大的正数。由于x是物资调运量，不可能小于零，故当U为零时,X=0成立；当U=1时，M是一个相当大的正数；MU足够大，X为一有限值，所以不等式成立。,综合所述，可以写出多点单品种物流网点布局的数学模型如下：,这是一个混合整数规划的数学模型，解这个模型，可以求得,的值。表示了网点j的进货来源,决定了该网点的规模;表示了网点j与用户k的供应关系与供货量，相应地也就知道了该网点的供货范围；而，表示直接供货部,为计划区域内应布局网点的数目。,（3）计算步骤第一步：求初始解。对产地到销地的所有组合，找出单位进货运输成本和配送运输成本之和最小的配送中心。根据初始解汇总各配送中心的吞吐量，进而求出配送中心的存储费率。第二步：求二次解。对产地到销地的所有组合，找出单位进货运输成本、配送运输成本和存储费率之和最小的配送中心，得到一组新的解。第三步：求最优解。重复上述步骤，直到各配送中心的吞吐量没有变化为止。,（4）鲍摩-瓦尔夫模型优缺点,模型的优点：计算比较简单能评价流通过程的总费用能求解配送中心的通过量不仅确定了哪些配送中心需要建设，而且确定了该配送中心服务的上游和下游对象，货物调运数量和调运方向都可同时确定。模型的缺点：由于采用的是逐次逼近法，所以，不能保证必然会得到最优解。此外，由于选择备选地点的方法不同，有时，求出的最优解中可能出现配送中心数目较多的情况。配送中心的固定费用没在所得的解中反映出来。,5、奎汉哈姆勃兹（kuehn-Hamburge）模型,这是一个多节点多品种选址模型，从表面上看，只需在单品种选址问题中增加多品种的因素就行了，即可分解成多个单品种选址子问题。但从实际情况看，由于各品种都要按照各自的优化方案选择物流节点中转，因此，同一客户可能会需要品种不同的货物，他们将从不同的物流节点进货，运输某些需求量不多的货物就会造成运输工具低效率而导致运输成本增大，这种情况的效果不是最经济的。为此，有必要将各客户所需的所有货物的供货点相对集中，最好由一个物流节点供货。,问题描述如下：有m家工厂生产多种产品，其中这些工厂各种产品的产能已知，而每个销售区对每种产品的需求也已知。产品经由物流节点运往销售区，每个销售区的所有产品都由某个指定的物流节点独家供货，并考虑缺货损失费，另外物流节点的候选地也是给定的，并且容量有限制，希望从这些候选地中选择若干个作为配送中心中转，以达到总运营成本最低的目标。物流节点成本包括固定成本+可变成本，整个系统网络没有考虑直送情况。,6、CFLP模型,前提：当配送中心的能力有限制，并且拟建配送中心的个数已确定没有考虑配送中心进货成本，供应地离规划区域足够远基本思想：首先假定物流节点的备选方案已定，根据初始方案，按照运输规划模型求出各节点的服务范围，然后在服务范围内分别移动物流节点到其他备选地址，以使各服务范围内总费用下降。当移动每个物流节点的位置都不能使本区域总费用下降，则计算结束。,基本步骤（1）选取初始方案通过定性分析，给出适当的物流节点数量和设置地点。（2）确定初始方案的服务范围：求解运输规划（3）在以上各配送范围内，移动配送中心到其他备选地点，寻找改进方案。（4）比较新、旧方案得到的总费用，如果费用没有下降表示已经得到最优解，如果下降表示还没有找到最优解，需要返回步骤（2）进行重复计算。,7、多枢纽站单一分派轴辐式网络选址问题,研究有双向物流的网络节点选址问题，按照多枢纽站单一分派轴辐式网络组织模式进行管理的。问题描述：在一个有n个节点的物流网络中，每个节点都可能是货物的起始点或终止点，货物从起始地到达目的地的流通量就是OD量，经过的节点链就是OD流,根据其组织模式要求每条OD流汇聚于一个或两个枢纽站后到达目的地，问题在于如何从n个节点中选择p个节点作为枢纽点，以使整个网络物流成本最小。即p-hub选址问题。由于枢纽站之间的干线运势具有规模效益，能够节约整个网络的物流成本。,对于小规模的此类问题的求解，可采用穷举法或分支定界法，可选用现成的优化软件，如LINGO软件。对于大规模的问题，求解非常困难，可用近年来的优化技术和一些针对特殊问题特征的启发式算法。,8、多枢纽站多分派轴辐式网络选址问题,也是研究有双向物流的网络节点选址问题，按照多枢纽站多分派轴辐式网络组织模式进行管理的。在多枢纽单