集合覆盖模型集合覆盖模型
多设施选址模型
P-中值模型
问题描述
在一个给定数量和位置的需求集合和一个候选
设施位置的集合下,确定p个设施的位置,并指派
每个需求点到一个特定的设施,使之达到设施和
需求点之间的运输费用最低。
最大覆盖模型最大覆盖模型
P-P-中值模型中值模型
多设施选址模型
模型建立
集合覆盖模型集合覆盖模型
P-中值模型
最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-23公式
集合覆盖模型集合覆盖模型
多设施选址模型
P-中值模型
模型求解
求解一个P-中值模型需要解决两方面问题:
选择合适的设施位置(x变量)
指派需求点到相应的设施中去(y变量)
与覆盖模型相似,求解P-中值模型主要有两大
类方法,即精确计算法和启发式算法。常用的求解
P-中值模型的启发式算法被称为:贪婪取走启发式
算法。
最大覆盖模型最大覆盖模型
P-P-中值模型中值模型
多设施选址模型
贪婪取走算法
第二步 第三步
• 将每个需求点
指派给k个设施
点中离其距离
最近的一个设
施点。
• 求出总运输费
用Z
• 若k=p,得到k
个设施点及各
需求点的指派
结果,停止
• 否则,转第四
步
第四步
• 从k个候选点中
确定一个取走点,
满足:若将它取
走并将它的需求
点指派给其它最
近设施后,总费
用增加量最小
• 从候选集合中删
去取走点,令
k=k-1,转第二步
第一步
• 令当前选中设
施点数k=m,
即所有m个候
选位置都选中
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
P-中值模型
多设施选址模型
某公司在一新地区经过一段时间的宣传广告后,得到了8个超市的订
单,由于该地区离总部较远,公司拟在该地区新建2个仓库,用最低的配
送成本来满足该地区的需求。经过一段时间的实地考察之后,已有4个候
选地址,如下图所示。从候选地址到各个超市运输成本cij、各超市的需求
量di都已经确定,如下表所示。试选择其中的两个候选点作为仓库地址,
使总运输成本最小。
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
P-中值模型3-6例
第一步
初始化,令k=m=4;
将每个客户指派给运输成本最低
的一个候选位置,指派结果为:
A=(a1, a2, … a8)=(1,1,1,4,4,2,3,3);
总费用
多设施选址模型
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
多设施选址模型
第二步
分别对取走候选点1,2,3,4进行分析,
并计算各自的费用增量:
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
取走候选点1,结果(4,2,2,4,4,2,3,3),
Z=3200,费用增量ΔZ=720
多设施选址模型
第二步
分别对取走候选点1,2,3,4进行分析,
并计算各自的费用增量:
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
取走候选点2,结果(1,1,1,4,4,3,3,3),
Z=2620,费用增量ΔZ=140
多设施选址模型
第二步
分别对取走候选点1,2,3,4进行分析,
并计算各自的费用增量:
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
取走候选点3,结果(1,1,1,4,4,2,4,2),
Z=3620,费用增量ΔZ=1140
多设施选址模型
第二步
分别对取走候选点1,2,3,4进行分析,
并计算各自的费用增量:
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
取走候选点4,结果(1,1,1,2,3,2,3,3),
Z=3520,费用增量ΔZ=1040
多设施选址模型
第二步
取走候选点2,使得ΔZ=140为最小
所以,第一个被取走的是候选点2
候选位置:k=4-1=3
指派结果:(1,1,1,4,4,3,3,3)
总费用:Z=2620
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
多设施选址模型
第三步
分别对取走候选点1,3,4进行分析,
并计算各自的费用增量:
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
取走候选点1,结果(4,4,4,4,4,3,3,3),
Z=4540,费用增量ΔZ=1920
多设施选址模型
第三步
分别对取走候选点1,3,4进行分析,
并计算各自的费用增量:
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
取走候选点3,结果(1,1,1,4,4,4,4,4),
Z=5110,费用增量ΔZ=2490
多设施选址模型
第三步
分别对取走候选点1,3,4进行分析,
并计算各自的费用增量:
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
取走候选点4,结果(1,1,1,1,3,3,3,3),
Z=3740,费用增量ΔZ=1120
多设施选址模型
第三步
取走候选点4,使ΔZ=1120为最小
所以,第二个被取走的是候选点4
候选位置:k=3-1=2
指派结果:(1,1,1,1,3,3,3,3)
总费用:Z=3740
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
多设施选址模型
第四步
∵k=2=p
∴计算结束,得到2个设施点及各
客户的指派结果:
在候选位置1,3建设新仓库
指派结果:(1,1,1,1,3,3,3,3)
总运输费用:Z=3740
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
3-6例
多设施选址模型
某公司在某地区有6个主要客户A1,A2,A3,A4,A5和A6,该公司拟在该
地区新建两个仓库,用最低的运输成本来满足该地区主要客户需求。经过
一段时间的实地考察之后,公司确定三个候选地址D1、D2和D3,如下图
所示。从候选地址到各客户运输成本、各客户的需求量都已经确定,如下
表所示。试确定仓库位置。
集合覆盖模型集合覆盖模型 最大覆盖模型最大覆盖模型 P-P-中值模型中值模型
P-中值模型3-3练习
多设施选址模型
鲍摩-瓦尔夫(Baumol-Wolfe)模型(1)
鲍摩-瓦尔夫(Baumol-Wolfe)模型,又称为单
品种选址模型。模型从一组候选地点中选择若干
个位置作为物流设施节点,使得从已知若干个资
源点(工厂),经过某几个设施节点,向若干个需求
点(客户)运送同一产品时,总的物流布局成本为最
小。
奎汉奎汉--哈姆勃兹哈姆勃兹
模型模型
鲍摩鲍摩--瓦尔夫模瓦尔夫模
型型
多设施选址模型
3-24公式
奎汉奎汉--哈姆勃兹哈姆勃兹
模型模型
鲍摩鲍摩--瓦尔夫模瓦尔夫模
型型
多设施选址模型
奎汉-哈姆勃兹(Kuehn-Hamburger)模型
奎汉-哈姆勃兹(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公式
多设施选址模型
迭代算法
第二步 第三步
• 求解工厂i 和需求
点 j 间的最优运输
问题, 得到 , 并
记录每个备选配送
中心的流通量 ,
进而根据式(3-27)
计算各备选配送中
心的边际成本。
• 令L=L+1,求
改进方案。用
代替 ,
求解运输问题
模型求解一组
新的 。
第四步
• 新旧方案比较,
如果两个方案完
全相同,迭代结
束,获得最优解。
否则返回第二步,
继续迭代,直到
与
完全相同。
第一步
• 初始迭代数L=0
• 令所有q个备选
配送中心上的流
通量 ,则
• 对所有工厂i 和
需求点 j ,求各工
厂和各需求点之
间的最低费率
鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)
多设施选址模型
某区域(企业)的配送中心在选址规划时, 经调查大致有3个进货渠道,
分8个客户方向, 现有5个配送中心的候选地址, 具体数据见如下2表, 求总
费用最小时的配送中心选址和配送方案。
鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)3-7例
工厂到备选配送中心的单位运费及其生产能力 备选配送中心到需求点的单位运费及客户需求量
各配送中心的单位可变费用
第一步
令 ,根据原始数据由公式 求
出从各生产地 i 经备选配送中心 k 到需求点 j 的最小运费,进
而通过运输问题的最小元素法知经过各配送中心的通过量 。
多设施选址模型
3-7例 鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)
最小运输成本及所经过的配送中心
第二步
求解该运输问题,得到初始的运输方案、各配送中心的流通
量和单位可变费用。
注:因为备选配送中心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^)+600×(50^)+500×(100^)+200×(70^)=
多设施选址模型
3-7例 鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)
初始运输方案
各配送中心的流通量 及边际可变费用
第三步
令L=L+1,由公式 ,求出从各生产地 i 经备
选配送中心 k 到需求点 j 的最小运输成本,进而通过运输问题
的最小元素法知经过各配送中心的通过量 。
多设施选址模型
3-7例 鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)
最小运输成本及所经过的配送中心
求解该运输问题,得到改进的运输方案、各配送中心的流通量和边
际可变费用。
为计算方便,按以上最小运输成本表格计算总费用。
Z1=×50+×20+×30+×30+33×40+37×60+23×30+27×2 +27×20=9494
注意:尽管在上面的最小运输成本表格中隐含了可变费用,但其是按边际可变费用计算
的,即最后一个单位产品的存储成本。根据边际效用递减理论,其余产品的单位存储成
本应大于该边际费用,因而以上方法计算的总费用小于真实值。若要计算真实值,应代
入公式(3-28)目标函数计算。
多设施选址模型
3-7例 鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)
改进运输方案
更新配送中心的流通量 及边际可变费用
第四步
新旧方案进行比较, 分配方案发生变化。目前的解有继续改
进的可能,返回第一步继续迭代。
第一步(2)
由公式 重新计算从各生产地 i 经备选配送中
心 k 到需求点 j 的最小运费,进而可通过求解运输问题知经过
各配送中心的通过量 。
多设施选址模型
3-7例 鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)
最小运输成本及所经过的配送中心
第二步(2)
求解该运输问题,得到新运输方案。
按以上最小运输成本表格计算总费用Z2=9260
新旧方案进行比较, 分配方案不发生变化,选用配送中心
备选地1、3、4,放弃2、5,迭代结束。但并不能保证目前的
解为最优解,只能保证其是可行解或近优解。
按式(3-28)目标函数重新计算真实总费用, Z*=。
多设施选址模型
3-7例 鲍摩-瓦尔夫(Baumol-Wolfe)模型(2)
改进运输方案