物流多设施选址模型概述ppt34页课件.ppt

集合覆盖模型集合覆盖模型多设施选址模型P-中值模型p问题描述n 在一个给定数量和位置的需求集合和一个候选设施位置的集合下，确定p个设施的位置，并指派每个需求点到一个特定的设施，使之达到设施和需求点之间的运输费用最低最大覆盖模型最大覆盖模型P-P-中值模型中值模型多设施选址模型n模型建立集合覆盖模型集合覆盖模型P-中值模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-23公式集合覆盖模型集合覆盖模型多设施选址模型P-中值模型p模型求解n 求解一个P-中值模型需要解决两方面问题：ü选择合适的设施位置（x变量）ü指派需求点到相应的设施中去（y变量）n 与覆盖模型相似，求解P-中值模型主要有两大类方法，即精确计算法和启发式算法常用的求解P-中值模型的启发式算法被称为：贪婪取走启发式算法最大覆盖模型最大覆盖模型P-P-中值模型中值模型多设施选址模型p贪婪取走算法第二步第三步•将每个需求点指派给k个设施点中离其距离最近的一个设施点•求出总运输费用Z•若k=p，得到k个设施点及各需求点的指派结果，停止•否则，转第四步第四步•从k个候选点中确定一个取走点，满足：若将它取走并将它的需求点指派给其它最近设施后，总费用增加量最小•从候选集合中删去取走点，令k=k-1，转第二步第一步•令当前选中设施点数k=m，即所有m个候选位置都选中集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型P-中值模型多设施选址模型n 某公司在一新地区经过一段时间的宣传广告后，得到了8个超市的订单，由于该地区离总部较远，公司拟在该地区新建2个仓库，用最低的配送成本来满足该地区的需求。

经过一段时间的实地考察之后，已有4个候选地址，如下图所示从候选地址到各个超市运输成本cij、各超市的需求量di都已经确定，如下表所示试选择其中的两个候选点作为仓库地址，使总运输成本最小集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型P-中值模型3-6例n第一步Ø初始化，令k=m=4；Ø将每个客户指派给运输成本最低的一个候选位置，指派结果为： A=(a1, a2, … a8)=(1,1,1,4,4,2,3,3)；Ø总费用多设施选址模型集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例多设施选址模型n第二步Ø分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例ü取走候选点1，结果(4,2,2,4,4,2,3,3)，Z=3200，费用增量ΔZ=720多设施选址模型n第二步Ø分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例ü取走候选点2，结果(1,1,1,4,4,3,3,3)，Z=2620，费用增量ΔZ=140多设施选址模型n第二步Ø分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例ü取走候选点3，结果(1,1,1,4,4,2,4,2)，Z=3620，费用增量ΔZ=1140多设施选址模型n第二步Ø分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例ü取走候选点4，结果(1,1,1,2,3,2,3,3)，Z=3520，费用增量ΔZ=1040多设施选址模型n第二步Ø取走候选点2，使得ΔZ=140为最小Ø所以，第一个被取走的是候选点2Ø候选位置：k=4-1=3Ø指派结果：(1,1,1,4,4,3,3,3)Ø总费用：Z=2620集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例多设施选址模型n第三步Ø分别对取走候选点1,3,4进行分析，并计算各自的费用增量：集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例ü取走候选点1，结果(4,4,4,4,4,3,3,3)，Z=4540，费用增量ΔZ=1920多设施选址模型n第三步Ø分别对取走候选点1,3,4进行分析，并计算各自的费用增量：集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例ü取走候选点3，结果(1,1,1,4,4,4,4,4)，Z=5110，费用增量ΔZ=2490多设施选址模型n第三步Ø分别对取走候选点1,3,4进行分析，并计算各自的费用增量：集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例ü取走候选点4，结果(1,1,1,1,3,3,3,3)，Z=3740，费用增量ΔZ=1120多设施选址模型n第三步Ø取走候选点4，使ΔZ=1120为最小Ø所以，第二个被取走的是候选点4Ø候选位置：k=3-1=2Ø指派结果：(1,1,1,1,3,3,3,3)Ø总费用：Z=3740集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例多设施选址模型n第四步Ø∵k=2=pØ∴计算结束，得到2个设施点及各客户的指派结果：ü 在候选位置1,3建设新仓库ü 指派结果：(1,1,1,1,3,3,3,3)ü 总运输费用：Z=3740集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型3-6例多设施选址模型n 某公司在某地区有6个主要客户A1,A2,A3,A4,A5和A6，该公司拟在该地区新建两个仓库，用最低的运输成本来满足该地区主要客户需求。

经过一段时间的实地考察之后，公司确定三个候选地址D1、D2和D3，如下图所示从候选地址到各客户运输成本、各客户的需求量都已经确定，如下表所示试确定仓库位置集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型P-P-中值模型中值模型P-中值模型3-3练习多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（1）n 鲍摩-瓦尔夫(Baumol-Wolfe)模型，又称为单品种选址模型模型从一组候选地点中选择若干个位置作为物流设施节点，使得从已知若干个资源点(工厂)，经过某几个设施节点，向若干个需求点(客户)运送同一产品时，总的物流布局成本为最小奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型多设施选址模型3-24公式奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型多设施选址模型奎汉-哈姆勃兹(Kuehn-Hamburger)模型n 奎汉-哈姆勃兹(Kuehn-Hamburger)模型，又称为多品种选址模型模型从一组候选地点中选择若干个位置作为物流设施节点，使得从已知若干个资源点(工厂)，经过某几个设施节点，向若干个需求点(客户)运送多种产品时，总的物流布局成本为最小。

鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型多设施选址模型3-25公式鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）属于非线性规划，是以逐次求解运输问题为思路的启发式算法其只考虑租用的仓库或配送中心，所以模型中不包含仓库或配送中心的固定投资成本奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 鲍摩-沃尔夫法（2）问题抽象定义为： ① 运输成本与运输量呈简单的线性关系 ② 用户的位置及需求量为已知 ③ 配送中心的容量无限制 ④ 配送中心的候选位置及其变动成本已知 在上述四项假设条件下，求解配送中心的个数及位置，以使运输成本及存储成本之和最小 奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 与其他选址问题不同，鲍摩—沃尔夫（2）不再假设配送中心存储成本随流通量呈线性变化，因为实际中更常见的情况是存储成本随流通量的增大而变得平坦，即表现出一定的规模经济性。

因此鲍摩—沃尔夫假设存储成本与配送中心流通量之间的函数关系为：奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型3-26公式多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） —— 存储成本； —— 配送中心单位流通量的可变 费用； —— 配送中心的流通量 则边际存储成本（存储费率） 奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型3-27公式多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 奎汉奎汉- -哈姆勃兹模哈姆勃兹模型型鲍摩鲍摩- -瓦尔夫模型瓦尔夫模型3-28公式多设施选址模型p迭代算法 第二步 第三步•求解工厂i 和需求点 j 间的最优运输问题, 得到 , 并记录每个备选配送中心的流通量 ,进而根据式(3-27)计算各备选配送中心的边际成本。

•令L=L+1，求改进方案用 代替 ，求解运输问题模型求解一组新的 第四步•新旧方案比较，如果两个方案完全相同，迭代结束，获得最优解否则返回第二步，继续迭代，直到 与 完全相同第一步•初始迭代数L=0•令所有q个备选配送中心上的流通量 ，则•对所有工厂i 和需求点 j ,求各工厂和各需求点之间的最低费率鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）多设施选址模型 某区域（企业）的配送中心在选址规划时, 经调查大致有3个进货渠道, 分8个客户方向, 现有5个配送中心的候选地址, 具体数据见如下2表, 求总费用最小时的配送中心选址和配送方案鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）3-7例工厂到备选配送中心的单位运费及其生产能力备选配送中心到需求点的单位运费及客户需求量各配送中心的单位可变费用n第一步Ø令 ，根据原始数据由公式 求出从各生产地 i 经备选配送中心 k 到需求点 j 的最小运费，进而通过运输问题的最小元素法知经过各配送中心的通过量 。

多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）最小运输成本及所经过的配送中心n第二步Ø求解该运输问题，得到初始的运输方案、各配送中心的流通量和单位可变费用Ø注：因为备选配送中心D1的可变费用低于D2，所以A2-B3选择经过D1Ø计算总费用Z0=12×50+16×20+9×30+17×30+8×40+12×60+11×30+15×20 +15×20 +300×(80^0.5)+600×(50^0.5)+500×(100^0.5)+200×(70^0.5)=17269.2多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）初始运输方案各配送中心的流通量 及边际可变费用n第三步Ø令L=L+1，由公式 ，求出从各生产地 i 经备选配送中心 k 到需求点 j 的最小运输成本，进而通过运输问题的最小元素法知经过各配送中心的通过量 多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）最小运输成本及所经过的配送中心Ø求解该运输问题，得到改进的运输方案、各配送中心的流通量和边际可变费用。

Ø为计算方便，按以上最小运输成本表格计算总费用 Z1=34.8×50+32.8×20+25.8×30+33.8×30+33×40+37×60+23×30+27×2 +27×20=9494Ø注意：尽管在上面的最小运输成本表格中隐含了可变费用，但其是按边际可变费用计算的，即最后一个单位产品的存储成本根据边际效用递减理论，其余产品的单位存储成本应大于该边际费用，因而以上方法计算的总费用小于真实值若要计算真实值，应代入公式(3-28)目标函数计算多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）改进运输方案更新配送中心的流通量 及边际可变费用n第四步Ø新旧方案进行比较， 分配方案发生变化目前的解有继续改进的可能，返回第一步继续迭代n第一步（2）由公式 重新计算从各生产地 i 经备选配送中心 k 到需求点 j 的最小运费，进而可通过求解运输问题知经过各配送中心的通过量 多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）最小运输成本及所经过的配送中心n第二步（2）Ø求解该运输问题，得到新运输方案。

Ø按以上最小运输成本表格计算总费用Z2=9260 新旧方案进行比较， 分配方案不发生变化，选用配送中心备选地1、3、4，放弃2、5，迭代结束但并不能保证目前的解为最优解，只能保证其是可行解或近优解 按式（3-28）目标函数重新计算真实总费用, Z*=14063.8多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）改进运输方案。