物流设施选址

集合覆盖模型多设施选址模型P-中值模型问题描述在一个给定数量和位置的需求集合和一个候选设施位置的集合下，确定p个设施的位置，并指派每个需求点到一个特定的设施，使之达到设施和需求点之间的运输费用最低。最大覆盖模型P-中值模型多设施选址模型模型建立集合覆盖模型P-中值模型。，否则。提供服务由设施，客户—，否则。点建立设施，在—目允许建设物流节点的数—点的单位运输费用点到从—个需求点的需求量第—设施候选点集合，—需求点集合，—MjNijiyyMjjxxmppjicidmMMnNNijijjjiji,0;1;0;1);(;;};,...,2,1{};,...,2,1{最大覆盖模型P-中值模型MjNiyMjxpxMjNixyNiytsycdijjMjjjijMjijNiMjijiji，，　，　　　，　，　　}1,0{}1,0{,1..min3-23公式集合覆盖模型多设施选址模型P-中值模型模型求解求解一个P-中值模型需要解决两方面问题：选择合适的设施位置（x变量）指派需求点到相应的设施中去（y变量）与覆盖模型相似，求解P-中值模型主要有两大类方法，即精确计算法和启发式算法。常用的求解P-中值模型的启发式算法被称为：贪婪取走启发式算法。最大覆盖模型P-中值模型多设施选址模型贪婪取走算法第二步第三步•将每个需求点指派给k个设施点中离其距离最近的一个设施点。•求出总运输费用Z•若k=p，得到k个设施点及各需求点的指派结果，停止•否则，转第四步第四步•从k个候选点中确定一个取走点，满足：若将它取走并将它的需求点指派给其它最近设施后，总费用增加量最小•从候选集合中删去取走点，令k=k-1，转第二步第一步•令当前选中设施点数k=m，即所有m个候选位置都选中集合覆盖模型最大覆盖模型P-中值模型P-中值模型多设施选址模型某公司在一新地区经过一段时间的宣传广告后，得到了8个超市的订单，由于该地区离总部较远，公司拟在该地区新建2个仓库，用最低的配送成本来满足该地区的需求。经过一段时间的实地考察之后，已有4个候选地址，如下图所示。从候选地址到各个超市运输成本cij、各超市的需求量di都已经确定，如下表所示。试选择其中的两个候选点作为仓库地址，使总运输成本最小。集合覆盖模型最大覆盖模型P-中值模型P-中值模型3-6例42131457863212341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi第一步初始化，令k=m=4；将每个客户指派给运输成本最低的一个候选位置，指派结果为：A=(a1,a2,…a8)=(1,1,1,4,4,2,3,3)；总费用248081iiiadcZi多设施选址模型集合覆盖模型最大覆盖模型P-中值模型3-6例42131457863212341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi100400360140160600120600421314578632多设施选址模型第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi取走候选点1，结果(4,2,2,4,4,2,3,3)，Z=3200，费用增量ΔZ=720100400360140160600120600421314578632150060048014016060012060042314578632多设施选址模型第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi取走候选点2，结果(1,1,1,4,4,3,3,3)，Z=2620，费用增量ΔZ=140100400360140160600120600421314578632100400360280160600120600421314578632多设施选址模型第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi取走候选点3，结果(1,1,1,4,4,2,4,2)，Z=3620，费用增量ΔZ=11401004003601401606001206004213145786321004003601401606001314563212006604728多设施选址模型第二步分别对取走候选点1,2,3,4进行分析，并计算各自的费用增量：集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi取走候选点4，结果(1,1,1,2,3,2,3,3)，Z=3520，费用增量ΔZ=10401004003601401606001206004213145786321004003601404001400120600421314578632多设施选址模型第二步取走候选点2，使得ΔZ=140为最小所以，第一个被取走的是候选点2候选位置：k=4-1=3指派结果：(1,1,1,4,4,3,3,3)总费用：Z=2620集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi100400360280160600120600421314578632100400360140160600120600421314578632多设施选址模型第三步分别对取走候选点1,3,4进行分析，并计算各自的费用增量：集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi100400360280160600120600421314578632取走候选点1，结果(4,4,4,4,4,3,3,3)，Z=4540，费用增量ΔZ=19205006001680280160600120600421314578632多设施选址模型第三步分别对取走候选点1,3,4进行分析，并计算各自的费用增量：集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi100400360280160600120600421314578632取走候选点3，结果(1,1,1,4,4,4,4,4)，Z=5110，费用增量ΔZ=24901004003606301606002200213145863266074多设施选址模型第三步分别对取走候选点1,3,4进行分析，并计算各自的费用增量：集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi100400360280160600120600421314578632取走候选点4，结果(1,1,1,1,3,3,3,3)，Z=3740，费用增量ΔZ=11201004003602804801400120600421314578632多设施选址模型第三步取走候选点4，使ΔZ=1120为最小所以，第二个被取走的是候选点4候选位置：k=3-1=2指派结果：(1,1,1,1,3,3,3,3)总费用：Z=3740集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi1004003602801606001206004213145786321004003602804801400120600421314578632多设施选址模型第四步∵k=2=p∴计算结束，得到2个设施点及各客户的指派结果：在候选位置1,3建设新仓库指派结果：(1,1,1,1,3,3,3,3)总运输费用：Z=3740集合覆盖模型最大覆盖模型P-中值模型3-6例12341412206100221025105033416141204659280518127320061424970720302116082412622100jicijdi1004003602801606001206004213145786321004003602804801400120600421314578632多设施选址模型某公司在某地区有6个主要客户A1,A2,A3,A4,A5和A6，该公司拟在该地区新建两个仓库，用最低的运输成本来满足该地区主要客户需求。经过一段时间的实地考察之后，公司确定三个候选地址D1、D2和D3，如下图所示。从候选地址到各客户运输成本、各客户的需求量都已经确定，如下表所示。试确定仓库位置。集合覆盖模型最大覆盖模型P-中值模型P-中值模型A1A5A6A2A3A4D1D3D2D1D2D3A151020100A22102550A34415110A465950A516127150A61454100cijjdii3-3练习500100440300150400A1A5A6A2A3A4D1D3D2总费用:Z=2790多设施选址模型鲍摩-瓦尔夫(Baumol-Wolfe)模型（1）鲍摩-瓦尔夫(Baumol-Wolfe)模型，又称为单品种选址模型。模型从一组候选地点中选择若干个位置作为物流设施节点，使得从已知若干个资源点(工厂)，经过某几个设施节点，向若干个需求点(客户)运送同一产品时，总的物流布局成本为最小。奎汉-哈姆勃兹模型鲍摩-瓦尔夫模型s2131n32...需求点k物流节点j...资源点i1m32...多设施选址模型.0,,;01;0;;;..)(min111111111111111ikjkijjjmiijnkjkmiijkmiiksjjkinkiksjijsjmiijjjjminkikiksjnkjkjkmisjijijZYXjjUMUXYXDZYSZXtsXWUVZeYdXcF　　　　点被淘汰　　点被选中　　　　　　　　　　　　　　　　　　　　;;;;;);10(;;;;;的固定费用候选节点—动费用每单位货物通过量的变候选节点—率直接进货的单位进货费从资源点需求点—供货的单位发货费率向需求点候选节点—进货的单位进货费率从资源点候选节点—变量是否选中的决策变量候选节点—直接进货的数量从资源点需求点—的货运量到需求点从候选节点—的货运量到候选节点从资源点—的产品需求量需求点—的产品供应量资源点—jVjWikekjd