资源描述:
《[精选]物流多设施选址模型概述.pptx》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、集合覆盖模型多设施选址模型P-中值模型问题描述在一个给定数量和位置的需求集合和一个候选设施位置的集合下,确定p个设施的位置,并指派每个需求点到一个特定的设施,使之达到设施和需求点之间的运输费用最低。最大覆盖模型P-中值模型多设施选址模型模型建立集合覆盖模型P-中值模型最大覆盖模型P-中值模型3-23公式集合覆盖模型多设施选址模型P-中值模型模型求解求解一个P-中值模型需要解决两方面问题:选择合适的设施位置(x变量)指派需求点到相应的设施中去(y变量)与覆盖模型相似,求解P-中值模型主要有两大类方法,即精确计算法和启发式算法。常用的求解P-中值模型的启发式算法被称为:贪婪取走启发式算
2、法。最大覆盖模型P-中值模型多设施选址模型贪婪取走算法第二步第三步将每个需求点指派给k个设施点中离其距离最近的一个设施点。求出总运输费用Z若k=p,得到k个设施点及各需求点的指派结果,停止否则,转第四步第四步从k个候选点中确定一个取走点,满足:若将它取走并将它的需求点指派给其它最近设施后,总费用增加量最小从候选集合中删去取走点,令k=k-1,转第二步第一步令当前选中设施点数k=m,即所有m个候选位置都选中集合覆盖模型最大覆盖模型P-中值模型P-中值模型多设施选址模型某公司在一新地区经过一段时间的宣传广告后,得到了8个超市的订单,由于该地区离总部较远,公司拟在该地区新建2个仓库,用最
3、低的配送成本来满足该地区的需求。经过一段时间的实地考察之后,已有4个候选地址,如下图所示。从候选地址到各个超市运输成本cij、各超市的需求量di都已经确定,如下表所示。试选择其中的两个候选点作为仓库地址,使总运输成本最小。集合覆盖模型最大覆盖模型P-中值模型P-中值模型3-6例第一步初始化,令k=m=4;将每个客户指派给运输成本最低的一个候选位置,指派结果为:A=(a1,a2,…a8)=(1,1,1,4,4,2,3,3);总费用多设施选址模型集合覆盖模型最大覆盖模型P-中值模型3-6例多设施选址模型第二步分别对取走候选点1,2,3,4进行分析,并计算各自的费用增量:集合覆盖模型最大
4、覆盖模型P-中值模型3-6例取走候选点1,结果(4,2,2,4,4,2,3,3),Z=3200,费用增量ΔZ=720多设施选址模型第二步分别对取走候选点1,2,3,4进行分析,并计算各自的费用增量:集合覆盖模型最大覆盖模型P-中值模型3-6例取走候选点2,结果(1,1,1,4,4,3,3,3),Z=2620,费用增量ΔZ=140多设施选址模型第二步分别对取走候选点1,2,3,4进行分析,并计算各自的费用增量:集合覆盖模型最大覆盖模型P-中值模型3-6例取走候选点3,结果(1,1,1,4,4,2,4,2),Z=3620,费用增量ΔZ=1140多设施选址模型第二步分别对取走候选点1,2
5、,3,4进行分析,并计算各自的费用增量:集合覆盖模型最大覆盖模型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-中值模型3-6例多设施选址模型第三步分别对取走候选点1,3,4进行分析,并计算各自的费用增量:集合覆盖模型最大覆盖模型P-中值模型3-6例取走候选点1,结果(4,4,4,4,4,3,3,3),Z=4540,费用增
6、量ΔZ=1920多设施选址模型第三步分别对取走候选点1,3,4进行分析,并计算各自的费用增量:集合覆盖模型最大覆盖模型P-中值模型3-6例取走候选点3,结果(1,1,1,4,4,4,4,4),Z=5110,费用增量ΔZ=2490多设施选址模型第三步分别对取走候选点1,3,4进行分析,并计算各自的费用增量:集合覆盖模型最大覆盖模型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
7、,3)总费用:Z=3740集合覆盖模型最大覆盖模型P-中值模型3-6例多设施选址模型第四步∵k=2=p∴计算结束,得到2个设施点及各客户的指派结果:在候选位置1,3建设新仓库指派结果:(1,1,1,1,3,3,3,3)总运输费用:Z=3740集合覆盖模型最大覆盖模型P-中值模型3-6例多设施选址模型某公司在某地区有6个主要客户A1,A2,A3,A4,A5和A6,该公司拟在该地区新建两个仓库,用最低的运输成本来满足该地区主要客户需求。经过一段时间的实地考察之后,公司确定