物流设施选址方法综述.doc

《物流设施选址方法综述.doc》由会员分享，可在线阅读，更多相关《物流设施选址方法综述.doc（13页珍藏版）》请在三一文库上搜索。

1、2.3配送中心选址方法综述本文在建立配送中心选址模型、设计模型求解方法时，需要借鉴大量前人 的研究成果。为了更直观地了解这些理论，本节对配送中心选址的方法进行了 归纳，并对几种常用选址模型进行介绍。从配送中心各备选点属性的可量化的程度分析，这些方法可分为定性方法 和定量方法两种，每种方法中又包含了复杂程度以及所用数学算法不同的多种 方法，现归纳如图2-3所示。物範施选址g图2-3物流设施选址方法归纳定性方法定性分析法是指凭借集体或个人的经验做出决策的过程。其一般执行步骤 包括：1) 根据以往经验结果进行确定备选点；2) 利用指标对各备选点进行优劣性检验；3) 根据检验结果做出决策。较常用的定性

2、方法有头脑风暴法、专家选择法、 PERT 法等，这类方法的 中心思想是将专家凭借经验做出的判断以量化的数值形式表示，对各个数值进 行综合分析后作出决策。由于基于定量分析的选址方法很难将影响决策的所有 因素考虑周全，如环境、地理、交通、城市用地、城市发展、劳动力等，并且 即便想周全考虑这些因素，也很难量化所建模型中的各约束条件。因此，根据 实际情况建立一套完整的选址评价指标体系，采用模糊评价(Fuzzy Judge)层次分析(Analytic Hierarchy Process简称AHP)等数学方法进行综合评价，进而 确定配送中心的最优选址区位就显得十分有效。在这类方法中，专家的主观判 断占主导

3、地位，决策结果往往受到专家的知识结构、经验以及他们所处的时代、 社会地位和社会环境等诸多因素的制约和影响。对于有限的备选地点，该类方 法较为有效，但是如果以整个城市大系统甚至更大规模的选址问题为研究对象 来研究配送中心的选址问题，则必须具备足够的基础资料，辅助以定量分析方 法，否则决策结果缺乏足够的说服力。 29定量方法定量分析法应用非常普遍，从建模方法的角度分类，可归纳为三大类：解 析法、模拟法和启发式方法。1) 解析法 解析法主要是通过建立并求解数学模型，以求得最优选址方案。一般来说 可分为基于成本的模型和基于效益的模型。基于成本的模型主要考虑成本的最 小化，而基于效益的模型考虑的则是总收

4、益的最大化。虽然这两类模型所考虑 的因素不同，但其数学处理方法在本质上是一致的。现实中，多数情况以研究 成本为主。采用解析法时，首先应根据问题的特征、外部条件以及内在的联系 建立适当的数学模型，然后对模型进行求解，获得最优选址方案。这种方法的 优点是能获得精确的最优解。但是，在解决某些复杂问题是，用该方法难以建 立起恰当的模型，或者由于模型太复杂，使得求解过程困难或付出相当高的代 价。因此，解析法在实际运用中受到一定的限制。 30采用解析法建立的模型包括微积分模型、数学规划模型、重心法模型等。 数学规划模型又包括线性规划模型、非线性规划模型、整数规划模型、混合规划模型等。在模型的选择上，应根据

5、问题的具体属性而定。2）模拟法选址规划方法中的模拟法是将实际问题用数学方程和逻辑关系模型表示出 来，通过模拟计算和逻辑推理后得到最佳选址方案。这种方法较之解析法建立 并求解数学模型较为简单。采用模拟法进行选址规划时，分析者必须提供预先 设定的各种网点组合方案，以供分析和评价，从中选出最优组合。因此，决策 结果主要依赖于分析者预先设定的组合方案，判断其是否接近最优方案，这也 是该方法的一个缺点。3）启发式方法启发式方法是针对模型的求解方法而言的，它是一种逐次逼近最优解的方 法。有些启发式方法中会设有一定的过滤条件，将劣解过滤掉，以减少寻找最 优解的复杂度。这种方法对求得的解进行反复判断和修正，直

6、到满意为止。31启发式方法能够比较有效地处理 NP困难问题，因此，启发式算法常与其 它优化方法结合使用，使两者的优点得到进一步发挥。目前，比较常用的启发 式算法包括：遗传算法、模拟退火算法、神经网络算法、蚁群算法等。用启发式方法进行选址规划的过程一般应包括以下几个步骤：（1）定义一种计算总成本或总收益的方法；（2）拟定判别准则；（3）规定方案改进途径；（4）给出初始方案；（5）反复迭代求解。常用模型介绍1 ）连续型选址模型32该模型有两个基本属性，一是解的空间在规划区域内可以是任何点；二是 点之间距离由一合适的矩阵表示。连续型定位模型需求出p个设施点的坐标（x,y） Rp Rp。（1）单设施选

7、址问题（TheSubjectoftheWeberProblem，SWP）模型 v（SWP）二 Min Wkd（x,y）（2-1）kK目标函数：（2-1）式：设施节点至所有给定客户需求点之间距离之和最小。变量：（x, y）:设施节点坐标。参数：Wk :权系数;dk(x,y):给定客户需求点k的坐标，dk(x,y)- “(x ak)2 (y bk)2该模型中的设施节点坐标(x, y)可由迭代法有效求出。(2) 多设施选址问题(Multi-source of the WeberProblem, MWP)模型pv(MWP)=Min、 (Wkdk(x,y)Zj(2-2)k:=K js.t.pzkj =1

8、-k K(2j3)Zj lO,门 k K j =1,2,L ,p(24)x, y Rp( 25) 目标函数：(2-2)式：设施节点至所有给定客户点之间距离之和最小。变量：(x, y):设施节点坐标;Zkj : Zkj “表示设施j向客户k提供服务，否则不为其提供服务。参数：Wk :权系数；dk (x, y):给定客户需求点k的坐标，dk (x, y) = (x匚aj2(y匚bk )2一;p :设施节点个数。该模型是典型的NP困难问题，可用精确法中的重心法或启发式算法求解。2)离散型选址模型(1)P-中值问题(P-medianProblem，PMP)模型(2-6)v(PMP)二 Min 、 (W

9、kdij)ZjkK j JZkj=1j J_k K（2-7）Zj _yj _0-k K, -j J（2-8） % = pjWJ（2-9）Zj, y: 0,1;-k K,-j J（2-10）目标函数：(2-6)式：选中的设施节点到所服务的客户需求点之间距离之和最小变量：zkj : 0-1变量，zkj =1表示设施点j为客户需求点k服务，否则不为其服务;yj : 0-1变量，yj =1表示设施点j被选中，否则未被选中参数：p :设施节点个数约束条件：(2-7 )式：每个客户的需求被满足；(2-8)式：设施节点的选定与分派的任务具有一致性;(2-9)式：设立的设施节点数不超过规定值。（2）P-中心问

10、题（P-centerProblem，PCP）模型v（PCP）二Mi nr（ 2-11）s.t.r 八 WkdkjZkj 一0k K（2-12）j Jzkj =1-k K（2-13）jJZj - yj 一0-k K,一jJ（2-14）片二P（2-佝jJZkj, yj 0,1? k K,j J（2-16）目标函数：（2-11）式：设施节点的服务半径最小。变量：r :设施节点的服务半径；Zkj : 0-1变量，Zkj =1表示设施点j为客户需求点k服务，否则不为其服务； yj : 0-1变量，yj =1表示设施点j被选中，否则未被选中。参数：Wk :权系数；dk（x,y）:设施节点到客户节点的距离，

11、dk（x,y） =、.（x-ak）2 （y-bk）2 ；（ak,bk）:客户需求点k的坐标；p :设施节点个数。约束条件：（2-12 ）式：设施节点的服务半径不小于客户需求点到被选中设施节点的距离；（2-13 ）式：每个客户的需求被满足；（2-14）式：设施节点的选定与分派的任务具有一致性；（2-15）式：设立的设施节点数不超过规定值。（3）集合覆盖模型v = Min yj（2-17）j Js.t.7Zkj=1-kK（2-18）jB（k）7dkZkj_&yj-kK,j J（2-19）k A（ j）zkj, y 0,1：_kK,j J（2-20）目标函数：（2-17）式：用尽可能少的设施节点覆盖

12、所有的客户需求点。变量：Zq : 0-1变量，Zq =1表示设施点j为客户需求点k服务，否则不为其服务;yj : 0-1变量，yj =1表示设施点j被选中，否则未被选中参数：dk :客户需求点k的需求量；Cj ：设施节点j的容量;A（j）:可以被设施节点j所覆盖的客户需求点集合;B（k）:可以覆盖客户需求点k的设施节点集合。约束：（2-18 ）式：每个客户的需求被满足；（2-19）式：设施节点j所服务的客户需求点的总需求量不超过其容量。对此类带有约束条件的极值问题，有两类方法可以求解。一是分枝定界法, 能够找到小规模问题的最优解；二是启发式算法，所得到的结果不能保证是最 优解，但可以保证是可行

13、解，对大型问题的求解用启发式算法可以大大减少运S.t.(4) 最大覆盖模型Zkj1-k K（2-22）j B(k)7dkZj 空 5yjk K,-j J（2-23）k.A( j) yj 二 p j J（2-24）Zkj, yr 1 0,k K,j J（2-25）v = MaxdkZkj( 2-21)j 3 k A(j)目标函数：（2-21）式：在给定数量的设施节点前提下，覆盖尽可能多的客户需求点变量：Zkj : 0-1变量，Zq =1表示设施点j为客户需求点k服务，否则不为其服务;yj : 0-1变量，yj =1表示设施点j被选中，否则未被选中 参数：dk :客户需求点k的需求量；5 :设施节

14、点j的容量；A（j）:可以被设施节点j所覆盖的客户需求点集合;B（k）:可以覆盖客户需求点k的设施节点集合;p :设施节点个数。约束：（2-22）式：每个客户的需求被满足；（2-23）式：设施节点j所服务的客户需求点的总需求量不超过其容量；（2-24）式：设立的设施节点数不超过规定值。最大覆盖模型可用贪婪算法求解，首先求出可以作为候选点的集合，并以 一个空集作为一个原始解的集合，然后在候选点集合中选择一个具有最大满足 能力的候选点进入集合，作为二次解，如此反复，直到设施数目满足要求。3）混合整数规划模型只要给出一些潜在设施点，则设施规划问题就可归结为混合整数规划数学 模型给予以求解。（1）无容

15、量约束的设施选址问题（Un capacitated Facility LocationProblem, UFLP）的单阶段模型(2-26)v(UFLP)二 Min 、 Okj Zkj + 为 f j yjk zK j Jj Js.t. zkj =1_k Kj. j(2-27)Zkj-yj 0k K, j J(2-28)0 Zkj _1_k K, - j J(2-29)(2-30)% 10,1；目标函数：(2-26)式：使包括运输成本与固定成本在内的总成本最小化变量：Zkj :表示客户需求点k的需求中，由设施节点j为其服务的比率；yj: 0-1变量，yj =1表示设施点j被选中，否则未被选中。参

16、数：ckj :从设施点j到客户需求点k的单位运输费率；fj :设施节点j的固定费用；约束条件：(2-27)式：表示客户需求点k的需求被满足；(2-28)式：表示设施节点的选定与客户需求点的分配具有一致性。(2)有容量约束的单阶段设施选址模型(Single-stage Capacitated Facility Location Problem，SCFLP)v(CFLP)二 Min CkjZkj +，f j yj(2-31)kWK jj WJs.t.zkj=1j WJ-k K(2-32)dkZj - qyj _ 0-j J(2-33)kWKZkj_ yj _ 0-k K,-j J(2-34)、Sj

17、yj _d(K)j - J(2-35) Zkj汨k K,-q Q(2-36)j - Jq0 一 Zj 一 1,k K,-j J(2-37)yj g,(2-38)目标函数：(3-31)式：使包括运输成本与固定成本在内的总成本最小化 参数：5 :从设施点j到客户需求点k的单位运输费率;fj :设施节点j的固定费用；dk :客户需求点k的需求量；Sj :设施节点j的容量。变量：Zkj :表示客户需求点k的需求中，由设施节点j为其服务的比率；yj : 0-1变量，yj =1表示设施点j被选中，否则未被选中。约束条件：（2-32）式：表示客户需求点k的需求被满足；（2-33）式：表示设施节点j提供的服务量不超过其容量限制；（2-34）式：表示设施节点的选定与客户需求点的分配具有一致性；（2-35）式：表示客户需求点总需求量不超过所有被选中设施点的容量之 和；（2-36）式：表示某一客户需求点的需求量可由多个设施节点共同满足。 上述模型应用于实际问题中时，要解出一个精确解十分困难，可以用启发 式算法求出相对较优的满意解。基于上述模型的分类介绍，选择符合本文配送中心选址问题的模型类型。 由3.1问题描述可知，各潜在配送中心区位已给出，因此选择离散型选址模型 中的整数规划模型来构建本文数学模型，具体构建过程见 3.3。