第二章物流选址规划.ppt

最大覆盖模型 最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务。 最大覆盖模型 N——研究对象中的n个需求点； di——第i个节点的需求量； Cj——设施位于节点j时的相应的容量； A(j)——可以被节点j的设施所覆盖的所有节点的集合；； B(i)——可以覆盖节点i的设施节点j的集合； p——允许投建的设施的数目； Xj——设施是否位于节点j； Yij——节点i需求中被分配给节点j的部分。 （1）式满足最大可能的对需求提供服务； （2）对需求的限制，服务不能大于当前需求的总和； （3）式为设施能力的限制； （4）式限制最多可投建的设施的数目。 最大覆盖模型 下面介绍由Richard Church Charles Re Velle 设计的贪婪算法进行求解。 [例题]如前例医疗站问题，如果仍不考虑其服务能力的限制，最多的诊所数目为2，请用最大覆盖法进行求解。 [解析]第一步到第三步如前述。 第四步：初步确定解的集合为 ，然后比较A(3)、A(4)、A(8)的数目。由于4村可以提供服务的对象最多，因此，将4村加入到解集合S中，S＝{4}； 第五步：比较3村和8村，除去4村提供服务的1、3、4、5、6、7外，剩下的只有{2,8,9}。3村可以对2村提供服务，而8村可以对8、9两个村提供服务，因此，8村作为第二个投建点加入到集合中，S＝{4,8}； 最大覆盖模型 第六步：若满足条件（本例中仅建两个诊所）则停止，否则，转第五步。 显然，启发式方法不是最优解。 P－中值模型 P－中值模型是指在一个给定数量和位置的需求集合和一个候选设施位置的集合下，分别为p个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在需求点和设施位置之间的运输费用最低。 求解一个P-中值模型需要解决两个问题： （1）选择合适的设施位置（表达式中的x变量）； （2）指派客户到相应的设施中去（表达式中的y变量）。 P－中值模型 N-系统中的n个客户（需求点）； di-第i个客户的需求； M-m个投建设施的候选地点； cij-从地点i到地点j的单位运输费用； p-可以建立的设施的总数（pm）； yij-客户i由设施j来提供服务； xj-在地点j建立设施的情况。 第（4）式为保证没有设施的地点不会有客户。 P－中值模型 下面介绍贪婪取走启发式算法。 [例题]某饮料公司在某新地区经过一段时间的宣传之后，得到了8个超市的订单，由于该新地区离总部较远，该公司拟在该地区新建两个仓库，经过一段时间的实地考查之后，已有四个候选地址。从候选地址到不同的仓库的运输成本、各个超市的需求量都已经确定，如表所示。如何用最低的运输成本来满足该地区的要求？ cij j di 1 2 3 4 1 4 12 20 6 100 2 2 10 25 10 50 3 3 4 16 14 120 4 6 5 9 2 80 5 18 12 7 3 200 6 14 2 4 9 70 7 20 30 2 11 60 8 24 12 6 22 100 P－中值模型 [题解] 第一步：初始化，令循环参数k=m，将所有的m个候选位置都选中，然后将每个客户指派给费用最省（距离与费用的乘积）的一个候选位置，如图1所示，总成本＝2480。 2 3 1 7 6 5 4 8 1 4 3 2 100 140 400 360 160 600 120 600 P－中值模型 第二步：选择总取走一个位置点，以满足下列条件：假如将它取走并将它的客户重新指派后，总费用增加量最小。然后令k＝k-1。 （2.1）移走位置1： 2 3 1 7 6 5 4 8 1 4 3 2 500 140 600 480 160 600 120 600 （a）移走候选位置1后的变化 总费用＝3200，增量＝3200-2480=720 P－中值模型 （2.2）移走位置2： 2 3 1 7 6 5 4 8 1 4 3 2 100 280 400 360 160 600 120 600 （b）移走候选位置2后的变化 总费用＝2620，增量＝2620-2480=140 P－中值模型 （2.3）移走位置3： 2 3 1 7 6 5 4 8 1 4 3 2 100 140 400 360 160 600 660 1200 （c）移走候选位置3后的变化 总费用＝3620，增量＝3620-2480=1140 P－中值模型 （2.4）移走位置4： 由上面（a）-（d）四图知，移走第2个点产生的增量（140）是最小的，所以，第1个被移走的候选点就是候选位置2。这样，就得到了k=3时的临时解。 2 3 1 7 6