1、多设施选址模型P-中值模型p问题描述n 在一个给定数量和位置的需求集合和一个候选设施位置的集合下，确定p个设施的位置，并指派每个需求点到一个特定的设施，使之达到设施和需求点之间的运输费用最低。多设施选址模型n模型建立P-中值模型。，否则。提供服务由设施，客户，否则。点建立设施，在目允许建设物流节点的数点的单位运输费用点到从个需求点的需求量第设施候选点集合，需求点集合，MjNijiyyMjjxxmppjicidmMMnNNijijjjiji,0;1;0;1);(;,.,2 , 1;,.,2 , 1MjNiyMjxpxMjNixyNiytsycdijjMjjjijMjijNiMjijiji，1 ,
2、 01 , 0,1. .min3-23公式多设施选址模型P-中值模型p模型求解n 求解一个P-中值模型需要解决两方面问题：选择合适的设施位置（x变量）指派需求点到相应的设施中去（y变量）n 与覆盖模型相似，求解P-中值模型主要有两大类方法，即精确计算法和启发式算法。常用的求解P-中值模型的启发式算法被称为：贪婪取走启发式算法。多设施选址模型p贪婪取走算法第二步第三步 将每个需求点指派给k个设施点中离其距离最近的一个设施点。 求出总运输费用Z 若k=p，得到k个设施点及各需求点的指派结果，停止 否则，转第四步第四步 从k个候选点中确定一个取走点，满足：若将它取走并将它的需求点指派给其它最近设施后
3、，总费用增加量最小 从候选集合中删去取走点，令k=k-1，转第二步第一步 令当前选中设施点数k=m，即所有m个候选位置都选中P-中值模型多设施选址模型n 某公司在一新地区经过一段时间的宣传广告后，得到了8个超市的订单，由于该地区离总部较远，公司拟在该地区新建2个仓库，用最低的配送成本来满足该地区的需求。经过一段时间的实地考察之后，已有4个候选地址，如下图所示。从候选地址到各个超市运输成本cij、各超市的需求量di都已经确定，如下表所示。试选择其中的两个候选点作为仓库地址，使总运输成本最小。P-中值模型3-6例n第一步初始化，令k=m=4；将每个客户指派给运输成本最低的一个候选位置，指派结果为：
4、 A=(a1, a2, a8)=(1,1,1,4,4,2,3,3)；总费用248081iiiadcZi多设施选址模型3-6例多设施选址模型n第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：3-6例取走候选点1，结果(4,2,2,4,4,2,3,3)，Z=3200，费用增量Z=720多设施选址模型n第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：3-6例取走候选点2，结果(1,1,1,4,4,3,3,3)，Z=2620，费用增量Z=140多设施选址模型n第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：3-6例取走候选点3，结果(1,1,
5、1,4,4,2,4,2)，Z=3620，费用增量Z=1140多设施选址模型n第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：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=26203-6例多设施选址模型n第三步分别对取走候选点1,3,4进行分析，并计算各自的费用增量：3-6例取走候选点1，结果(4,4,4,4,4,3,3,3)，Z=4540，费用增量Z=1920多
6、设施选址模型n第三步分别对取走候选点1,3,4进行分析，并计算各自的费用增量：3-6例取走候选点3，结果(1,1,1,4,4,4,4,4)，Z=5110，费用增量Z=2490多设施选址模型n第三步分别对取走候选点1,3,4进行分析，并计算各自的费用增量：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=37403-6例多设施选址模型n第四步k=2=p计算结束，得到2个设施点及各客户的指
7、派结果： 在候选位置1,3建设新仓库 指派结果：(1,1,1,1,3,3,3,3) 总运输费用：Z=37403-6例多设施选址模型n 某公司在某地区有6个主要客户A1,A2,A3,A4,A5和A6，该公司拟在该地区新建两个仓库，用最低的运输成本来满足该地区主要客户需求。经过一段时间的实地考察之后，公司确定三个候选地址D1、D2和D3，如下图所示。从候选地址到各客户运输成本、各客户的需求量都已经确定，如下表所示。试确定仓库位置。P-中值模型3-3练习多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（1）n 鲍摩-瓦尔夫(Baumol-Wolfe)模型，又称为单品种选址模型。模型从一组候
8、选地点中选择若干个位置作为物流设施节点，使得从已知若干个资源点(工厂)，经过某几个设施节点，向若干个需求点(客户)运送同一产品时，总的物流布局成本为最小。多设施选址模型. 0,;01; 0;. .)(min111111111111111ikjkijjjmiijnkjkmiijkmiiksjjkinkiksjijsjmiijjjjminkikiksjnkjkjkmisjijijZYXjjUMUXYXDZYSZXtsXWUVZeYdXcF点被淘汰点被选中;);10(;的固定费用候选节点动费用每单位货物通过量的变候选节点率直接进货的单位进货费从资源点需求点供货的单位发货费率向需求点候选节点进货的单位
9、进货费率从资源点候选节点变量是否选中的决策变量候选节点直接进货的数量从资源点需求点的货运量到需求点从候选节点的货运量到候选节点从资源点的产品需求量需求点的产品供应量资源点jVjWikekjdijcjUikZkjYjiXkDiSjjikjkijjikjkijki3-24公式多设施选址模型奎汉-哈姆勃兹(Kuehn-Hamburger)模型n 奎汉-哈姆勃兹(Kuehn-Hamburger)模型，又称为多品种选址模型。模型从一组候选地点中选择若干个位置作为物流设施节点，使得从已知若干个资源点(工厂)，经过某几个设施节点，向若干个需求点(客户)运送多种产品时，总的物流布局成本为最小。多设施选址模型.
10、 0; 1;. .)()()(minhijkjhjkjhikhijkhijkhijkjhjkhkijhijkhkhkhkjhjikhijkhjjjhijkhijkhjkhijXVWXYXVQXtsTDXSZFXdcF的能力。生产产品资源点需求不可分割某个候选节点服务，其产品只能由的点整型变量，则说明需求、为其中若配百分比；产品在各候选节点的分的需求点的吞吐能力候选节点数量需要的产品需求点损失费而支付的时，因延误时间配送产品向需求点费用而产生的部分可变中为保管产品在候选节点库存定额的最大向所有需求点配送产品各资源点由候选节点；否则取时，取当期间的平均固定管理费在候选节点的数量运送产品向需求点经过
11、候选节点从资源点的单位运输费率运送产品向需求点从候选节点的单位运输费率运送产品到候选节点从资源点hiYhkVhkVjWhkQThkTDhjXSjXXZjFhkjiXhkjdhjichihjkhjkjhkhkhkikhijkhjhikhijkhikhijkjjhijkhjkhij; 10 0;)()(;)(; 010;3-25公式多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）属于非线性规划，是以逐次求解运输问题为思路的启发式算法。其只考虑租用的仓库或配送中心，所以模型中不包含仓库或配送中心的固定投资成本。多设施选址模型鲍摩-瓦
12、尔夫(Baumol-Wolfe)模型（2） 鲍摩-沃尔夫法（2）问题抽象定义为： 运输成本与运输量呈简单的线性关系。 用户的位置及需求量为已知。 配送中心的容量无限制。 配送中心的候选位置及其变动成本已知。 在上述四项假设条件下，求解配送中心的个数及位置，以使运输成本及存储成本之和最小。 多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 与其他选址问题不同，鲍摩沃尔夫（2）不再假设配送中心存储成本随流通量呈线性变化，因为实际中更常见的情况是存储成本随流通量的增大而变得平坦，即表现出一定的规模经济性。因此鲍摩沃尔夫假设存储成本与配送中心流通量之间的函数关系为：kkkSd3-26公
13、式多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 存储成本； 配送中心单位流通量的可变 费用； 配送中心的流通量。 则边际存储成本（存储费率） kSkkd/ 2kkkkCdd3-27公式多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（2） 1111111min . ,0qmmikikkjkjkkkiiqikikqkjjkmnikkjkijikkjC XC XdstXaiYbjXYdkXY 3-28公式多设施选址模型p迭代算法 第二步 第三步 求解工厂i 和需求点 j 间的最优运输问题, 得到 , 并记录每个备选配送中心的流通量 ,进而根据式(3-27)计算各备选配
14、送中心的边际成本。 令L=L+1，求改进方案。用 代替 ，求解运输问题模型求解一组新的 。 第四步 新旧方案比较，如果两个方案完全相同，迭代结束，获得最优解。否则返回第二步，继续迭代，直到 与 完全相同。第一步 初始迭代数L=0 令所有q个备选配送中心上的流通量 ，则 对所有工厂i 和需求点 j ,求各工厂和各需求点之间的最低费率鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）0,1,2,LkCkqLijCmin()LLLLijikkjkCCCCLijX1/2LLLkkkkCddLkC1LkCLkd0LkdLkd1LkdLkd多设施选址模型 某区域（企业）的配送中心在选址规划时, 经调查大致
15、有3个进货渠道, 分8个客户方向, 现有5个配送中心的候选地址, 具体数据见如下2表, 求总费用最小时的配送中心选址和配送方案。鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）3-7例工厂到备选配送中心的单位运费及其生产能力备选配送中心到需求点的单位运费及客户需求量各配送中心的单位可变费用n第一步令 ，根据原始数据由公式 求出从各生产地 i 经备选配送中心 k 到需求点 j 的最小运费，进而通过运输问题的最小元素法知经过各配送中心的通过量 。多设施选址模型3-7例00,1,2,kCkq鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）0000min()ijikkjkCCCC0kd最小运输成本
16、及所经过的配送中心n第二步求解该运输问题，得到初始的运输方案、各配送中心的流通量和单位可变费用。注：因为备选配送中心D1的可变费用低于D2，所以A2-B3选择经过D1。计算总费用Z0=1250+1620+930+1730+840+1260+1130+1520 +1520 +300(800.5)+600(500.5)+500(1000.5)+200(700.5)=17269.2多设施选址模型3-7例1kC鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）初始运输方案各配送中心的流通量 及边际可变费用0kdn第三步令L=L+1，由公式 ，求出从各生产地 i 经备选配送中心 k 到需求点 j 的最小
17、运输成本，进而通过运输问题的最小元素法知经过各配送中心的通过量 。多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）1001min()ijikkjkCCCC1kd最小运输成本及所经过的配送中心求解该运输问题，得到改进的运输方案、各配送中心的流通量和边际可变费用。为计算方便，按以上最小运输成本表格计算总费用。 Z1=34.850+32.820+25.830+33.830+3340+3760+2330+272 +2720=9494注意：尽管在上面的最小运输成本表格中隐含了可变费用，但其是按边际可变费用计算的，即最后一个单位产品的存储成本。根据边际效用递减理论，其余产品的单位存
18、储成本应大于该边际费用，因而以上方法计算的总费用小于真实值。若要计算真实值，应代入公式(3-28)目标函数计算。多设施选址模型3-7例2kC鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）改进运输方案更新配送中心的流通量 及边际可变费用1kdn第四步新旧方案进行比较， 分配方案发生变化。目前的解有继续改进的可能，返回第一步继续迭代。n第一步（2）由公式 重新计算从各生产地 i 经备选配送中心 k 到需求点 j 的最小运费，进而可通过求解运输问题知经过各配送中心的通过量 。多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）2002min()ijikkjkCCCC2kd最小运输成本及所经过的配送中心n第二步（2）求解该运输问题，得到新运输方案。按以上最小运输成本表格计算总费用Z2=9260 新旧方案进行比较， 分配方案不发生变化，选用配送中心备选地1、3、4，放弃2、5，迭代结束。但并不能保证目前的解为最优解，只能保证其是可行解或近优解。 按式（3-28）目标函数重新计算真实总费用, Z*=14063.8。多设施选址模型3-7例鲍摩-瓦尔夫(Baumol-Wolfe)模型（2）改进运输方案
