物流系统规划与设计3-选址模型PPT格式课件下载.ppt

1、在这些问题中，直线距离是可以接受的近似值。城市间配送问题的实际路线距离可以通过将欧几里得距离乘以一个适当的系数（如在美国大陆是1.2，在东南美州是1.26）来更好地近似。,9,2023年4月28日星期五,（2）折线距离折线距离采用如下的公式计算：折线距离一般用在道路较规则的城市内的配送问题及具有直线通道的工厂及仓库内的布置、物料搬运设备的顺序移动等问题中。,10,2023年4月28日星期五,二、连续点选址模型,一个简单的选择问题上式中，wi大街上第i个位置出现顾客的概率；xi大街上第i个位置到所选地址的距离；s选择投资的位置。计算结果表明：所开设的新店面需要设置在权重的中点，即两边的权重相等。

2、,11,2023年4月28日星期五,连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的一个选择。1、交叉中值模型（Cross Median）交叉中值模型是用来解决连续点选址问题的一种十分有效的模型，它是利用城市距离进行计算，通过交叉中值的方法可以对单一的选址问题在一个平面上的加权的城市距离进行最小化。,12,2023年4月28日星期五,其相应的目标函数为：在这个问题里面，最优位置也就是由如下坐标组成的点：是在x方向的对所有的权重的中值点；是在y方向的对所有的权重的中值点。考虑到 两者可能同时是惟一值或某一范围，最优的位置也相应的可能是一个点，或者是线，或者是一个区域。,式

3、中：,与第i个点对应的权重（例如需求）；,第i个需求点的坐标；,服务设施点的坐标；,需求点的总数目。,13,2023年4月28日星期五,例子：报刊亭选址一个报刊连锁公司想在一个地区开设一个新的报刊零售点，主要的服务对象是附近的5个住宿小区的居民，他们是新开设报刊零售点的主要顾客源。下图笛卡儿坐标系中确切地表达了这些需求点的位置，下表是各个需求点对应的权重。这里，权重代表每个月潜在的顾客需求总量，基本可以用每个小区中的总的居民数量来近似。经理希望通过这些信息来确定一个合适的报刊零售点的位置，要求每个月顾客到报刊零售点所行走的距离总和为最小。解：由于考虑的问题是在一个城市中的选址问题，评价是，使用

4、城市距离是合适的，交叉中值选址方法将会用来解决这个问题。,14,2023年4月28日星期五,15,2023年4月28日星期五,首先，需要确定中值：从上表中得到中值：为了找到x方向上的中值点xs，发现在需求点1、3之间1000m的范围内对于轴方向都是一样的：接着寻找在y方向上的中值点，在y方向只能选择一个有效的中值点：,16,2023年4月28日星期五,17,2023年4月28日星期五,18,2023年4月28日星期五,综合考虑x、y方向的影响，于是最后可能的地址为A、B之间的一条线段，见下图。,19,2023年4月28日星期五,然后对A、B两个位置的加权距离进行了比较。,20,2023年4月2

5、8日星期五,2、精确重心法（Exact Gravity）前面介绍的交叉中值模型由于其本身的局限性，例如使用的是城市距离，只适合于解决一些小范围的城市内的选址问题。精确重心法在评价的过程中使用的是欧几米德距离，即直线距离，它使选址问题变得复杂，但是有着更为广阔的应用范围。在使用了欧几米德距离之后，目标函数变成了：这是一个双变量系统，分别对xs和ys进行求偏微分，并且令其为零，这样就可以得到两个微分等式。应用这两个等式分别对xs和ys进行求解，即可以求出下面的一对隐含有最优解的等式：,21,2023年4月28日星期五,该微分议程组不能直接求解，可以通过迭代的方法进行求解，这需要提供一组初始值xs0

6、和ys0。然后利用xs（i-1）和ys（i-1）求出dis（i-1），再用它去求出xsi和ysi，迭代公式如下：,22,2023年4月28日星期五,如果该迭代过程具有收敛性，那么经过无限次的迭代之后，可以得到一个最优解xs*和ys*。但是在实际中，可以迭代的次数是有限的，所以在迭代过程中需要确定一个中止准则。设置中止准则有两个方法：（1）根据经验和以前的试验结果，直接设置一个确定的迭代次数N；（2）将每一次得到的迭代结果xsi和ysi 跟前面一次的迭代结果xs（i-1）和ys（i-1）比较，当两次的迭代结果变化小于某一个阈值、时，迭代过程结束。,23,2023年4月28日星期五,例子：运用精确

7、重心法，对前面的报刊零售点选址问题作一个假设，假设这个报刊亭附近都是空地，使用欧几米德距离进行计算是合适的，然后我们就用精确重心法选择一个最优的位置。从A点（3，3）（即：xsi0=3和ysi0=3）开始进行欧几米德距离最优的搜索，下表进行了一些必要的计算。,24,2023年4月28日星期五,然后根据前面的公式，即可得到迭代结果：然后进行中止准则的判断，确定是否继续进行迭代。注意：用精确重心法得到的最优解只有一个点，而不会是一条线段或者一个区域。而且只有在十分偶然的情况下，才会出现用交叉中值法和精确重心法得到的最优优地址一致的情况。,25,2023年4月28日星期五,三、离散点选址模型,离散点

8、选址指的是在有限的候选位置里面，选取最为合适的一个或者一组位置为最优方案，相应的模型就叫做离散点选址模型。它与连续点选址模型的区别在于：它所拥有的候选方案只有有限个元素，我们考虑问题的时候，只需要在这几个有限的位置进行分析。对于离散点选址问题。目前主要有两种模型可供选择，分别是覆盖模型（Covering）和P中值模型。其中覆盖模型常用的有集合覆盖模型（Set Covering Location Problem）和最大覆盖模型（Maximum Covering Location）。,26,2023年4月28日星期五,1、覆盖模型 所谓覆盖模型，就是对于需求已知的一些需求点，如何确定一组服务设施来

9、满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适的位置。该模型适用于商业物流系统，如零售点的选址问题、加油站的选址、配送中心的选址等，公用事业系统，如急救中心、消防中心等，以及计算机与通信系统，如有线电视网的基站、无线通信网络基站、计算机网络中的集线器设置等。根据解决问题的方法的不同，可以分为两种不同的主要模型：（1）集合覆盖模型，用最小数量的设施去覆盖所有的需求点。（2）最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求点。两类模型的区别：集合覆盖模型要满足所有的需求点，而最大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取决于服务设施的资源充足与否。,27,2023

10、年4月28日星期五,（1）集合覆盖模型 集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点，相应的目标函数可以表达为：约束条件为：,最小化设施的数目,保证每个需求点的需求得到完全的满足,是对每个提供服务的服务网点的服务能力的限制,保证一个地方最多只能投建一个设施,允许一个设施只提供部分的需求,28,2023年4月28日星期五,对于此类带有约束条件的极值问题，有两大类方法可以进行分解：一是精确的算法，应用分枝定界求解的方法，能够找到小规模问题的最优解，由于运算量方面的限制，一般也只适用于小规模问题的求解；二是启发式方法，所得到的结果不能保证是最优解，但是可以保证是可行解，可以对大型问题进行有

11、效的分析、求解。,29,2023年4月28日星期五,例子：乡村医疗诊所选址问题 卫生部门考虑到农村地区的医疗条件的落后和匮乏，计划在某一地区的9个村增加一系列诊所，以改善该地区的医疗卫生水平。它希望在每一个村周边30km的范围之内至少有一个诊所，不考虑诊所服务能力的限制。卫生部门需要确定至少需要多少个诊所和它们相应的位置。除了第6个村之外，其他任何一个村都可以作为诊所的候选地点，原因是在第6村缺乏建立诊所的必要条件。下图是各个村之间的相对位置和距离的地图。,30,2023年4月28日星期五,第一步，找到每一个村可以提供服务的所有村的集合，即它们距该村距离小于或等于30km的所有村的集合。第二步

12、，找到可以给每一个村提供服务的所有村的集合。一般说来，这两个集合是一致，但是考虑到其他的一些限制条件，就可能出现差异。第三步，找到其他村服务范围的子集，将其省去，可以简化问题。,31,2023年4月28日星期五,32,2023年4月28日星期五,第四步，确定合适的组合解。很显然，问题得到简化之后，在有限的候选点上选择一个组合解是可行的。（3，4，8）本身就是一个组合解，但是为了满足经济性要求，尽可能少地建立诊所，还需要从中剔除可以被合并的候选点。（3，8）则是可以覆盖所有村的一个数量最少的组合解：3村的诊所可以覆盖村1村到5村，而8村的诊所覆盖6村到9村。如果放宽一些问题的限制条件，例如一个诊

13、所的服务半径增加到40km，也可能会出现多解的情况。（3，8），（3，9），（4，7），（4，8）和（4，9）都是可以覆盖所有的村而且数量最少的组合解。,33,2023年4月28日星期五,（2）最大覆盖模型 最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务。它的相应目标函数是：,是满足最大可能的对需求提供服务,是需求的限制，服务不可能大于当前需求的总和,是设施的服务能力的限制,是问题本身的限制，也就是说最多可能投建设设施的数目,保证一个地方最多只能投建一个设施,允许一个设施只提供部分的需求,34,2023年4月28日星期五,35,2023年4月28日星期五,前面提到的医疗

14、站问题，如果仍旧不考虑其服务能力的限制，最多的诊所数目为2，用最大覆盖模型对其进行分析，贪婪算法可以进行求解。该算法是一个空集合作为原始的解集合，然后在剩下的所有的其他候选点中，选择一个具有最大满足能力的候选点加入到原来的候选集合中，如此往复，直到到了设施数目的限制或者全部的需求都得到满足为止。在医疗站的问题中，我们已经分析得到候选集合为（3，4，8）。初步确定解的集合。然后比较A（3）、A（4）和A（8）的数目，4村可以提供服务的对象最多，将4村加入到解集合S中，。接着比较3、8两个村，除去4提供服务的村1、3、4、5、6、7外，剩下只有，3村对2村提供服务。8村将作为第二个投建点加入到解集

15、合中去，。这就是我们通过最大覆盖法得到的解集合，显然是最优解，这也是启发式算法的特点。,36,2023年4月28日星期五,2、P中值模型P中值模型是指在一个给定数量和位置的需求集合和一个候选设施位置的集合下，分别为p个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在工厂和需求点之间的运输费用最低。,37,2023年4月28日星期五,P中值模型也可以通过精确的数学语言进行描述。在用数学语言进行描述时，需要准确地表达问题的约束条件、目标、还有合理的变量定义。一般P中值问题的目标函数是：,是P中值模型的目标函数,保证每个客户（需求点）只有一个设施来提供相应的服务,限制了总的设施数目为p

16、个,有效地保证没有设施的地点不会有客户对应,38,2023年4月28日星期五,39,2023年4月28日星期五,可以看出，求解一个P中值模型需要解决两方面问题：（1）选择合适设施位置（数学表达的变量）；（2）指派客户到相应的设施中去（表达式中的变量）。例子：某饮料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地考查之后，已有4个候选地址。从候选地址到不同的仓库运输成本、各个超市的需求量都已经确定，如图所示。,40,2023年4月28日星期五,41,2023年4月28日星期五

17、,用启发式求解P中值模型的算法贪婪取走启发式算法（Greedy Dropping Heuristic Algorithm）。这种算法的基本步骤如下：（1）第一步，初始化，令循环参数k=m，将所有的m个候选位置都选中，然后将每个客户指派给离其距离最近的一个候选位置；（2）第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令 k=k-1；（3）第三步，重复第二步，直到 k=p；,42,2023年4月28日星期五,43,2023年4月28日星期五,44,2023年4月28日星期五,45,2023年4月28日星期五,46,2023年4月28日星期五,

18、47,2023年4月28日星期五,这样就得到了k=3时的临时解。重复上面步骤，对图2-15分别移走候选位置1、3、4进行计算，可以发现移走候选位置4的增量最小，所以第二次移走走第4个候选位置。最后的结果就是在候选位置1、3投建新的仓库，总的运输成本为：3740。值得注意的是，不是只有贪婪取走算法一种启发式算法，相应的还有贪婪加入算法（Greedy Adding Heuristic）、模拟退火算法（Simulated Annealing）、Tabu搜索（TS）等。,实例分析：TransAlta Utilities的服务网络重构规划,1、服务网络的现状与问题2、服务网络的分析与重构（1）服务网点的数量（2）服务网点分布（3）专用交通工具选址问题：案例中的选址属于哪种选址类型？连续选址、网格选址、离散选址服务网点采用的是哪种选址模型？服务网点选址采用的是哪种距离？专用交通工具采用的哪种选址模型？,48,2023年4月28日星期五,49,2023年4月28日星期五,习题,50,2023年4月28日星期五,