多物流节点选址方法与模型课件.pptx

1、 多物流节点选址方法与模型u多重心法u覆盖模型uP-中值模型uCFLP模型u鲍摩-瓦尔夫（Baumol-Wolfe）模型u奎汉-哈姆勃兹（Kuehn-Hamburge）模型1、多重心法 分组如何分？ 选址计算 调整分组为什么要调整？如何调整？ 分组结果变化？有，回到第二步；无，结束。例 某公司计划建立2个药品配送点向10个药品连锁店送货，各药品连锁店的地址和坐标和药品每日需求如下图，运价均为1，试确定这两个药品配送点的地址，使送货运输费用最低。连锁连锁店店 j12345678910Xj70958020401040751090Yj7050206010506090304需求量81065781251

2、19药品连锁店地址坐标与需求量药品连锁店地址坐标与需求量1.分组连锁连锁店店 j12345678910Xj70958020401040751090Yj7050206010506090304需求量81065781251192.选址计算利用精确重心法，求出2个配送点的地址坐标为（P1,Q1）=(74.342,46.147),（P2,Q2）=（40,60）3.计算各药品连锁店到两个配送点的送货运输费用连锁店号jXjYj需求量需求量到（到（P1,Q1）运输费用运输费用到（到（P2,Q2）运输费用运输费用170708193.9598252.98222955010210.1425559.017380206

3、160.513339.4113420605280.3997100540107349.0171350610508515.6581252.98227406012444.36930875905219.2897230.48869103011729.7087466.69051090409151.3924484.6648调整分组为调整分组为1,2,3,5,8,10和和4,6,7,94.将新的分组进行重新选址，运用精确重心法计算出新的配送点的地点坐标，再次算出各个药品连锁店到两个配送点的运输费用，继续进行重新分组，分组迭代，直至迭代后分组不变，不变的分组就是最佳的分配方案。2、覆盖模型 1)集合覆盖模型，用

4、最小数量的设施去覆盖所有的需求点。2)最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求点。yj xjNminij 1,jMiNdiyij C jx j,iA( j)jB(i)iN, jMjMyij 0,x j 0,1, 1)集合覆盖模型N ：需求点集合；M：候选点集合；dj：第j个节点的需求量；Cj：设施节点j的容量；yij：节点j需求中被分配给节点的部分；xj：节点j是否被选中。12 例 在某区域需规划建设若干个农贸市场为将来该区9个主要居民点提供服务。除第6居民点外，其他各点均有建设市场的条件，如图所示。已知市场的最大服务半径为3km，为保护该区域的环境，希望尽可少地建造农贸市场。问应

5、如何规划？9786543222233333444111居民点A(j)B(i)11，2，3，41，2，3，421，2，3l，2，33l，2，3，4，5，61，2，3，4，541，3，4，5，6，71，3，4，5，753，4，5，63，4，563，4，5，7，874，6，7，84，7，886，7，8，97，8，998，98，9127865432292333334244111A（j）：节点j所覆盖的需求节点的集合B（i）：可以覆盖需求节点i的节点j的集合最少点覆盖启发式算法选择指派候选点的集合1,3,4,7,8考虑建一个农贸市场，不满足覆盖全部需求 点的要求考虑建两个农贸市场，运用穷举法，农贸市场可

6、取(1,3),(1,4),(1,7),.,(7,8) ，发现取（3,8）作为农贸市场选址时，能满足所有需求点的配送需求因此，最少建两个农贸市场，能使全部居民点覆盖，建设农贸市场的居民点是3和8(2)最大覆盖模型max d i y ijj N i A ( j ) y ij 1, i Nj B ( i ) d i y ij C j x j , j Mi A ( j )j Mjx p , j Mxj 0,1, j My ij 0, i N , j M12 例 在某区域需规划建设若干个农贸市场为将来该区9个主要居民点提供服务。除第6居民点外，其他各点均有建设市场的条件，如图所示。已知市场的最大服务半径

7、为3km，为保护该区域的环境，最多只能建2个农贸市场。问应如何规划？978654322223333344411111，2，3，4231，2，3l，2，3，4，5，64567891，3，4，5，6，73，4，5，64，6，7，86，7，8，98，9129786543222233333444111A（j）：节点j所覆盖的需求节点的集合居民点 A ( j)贪婪算法选择具有最大满足能力的候选点居民点123456789A ( j)22288，98，9居民点123456789A ( j)1，2，3，41，2，3l，2，3，4，5，61，3，4，5，6，73，4，5，64，6，7，86，7，8，98，9解为

8、（4,8）最优解？居民点123456789A ( j)77,87，8，98，9居民点123456789A ( j)1，2，3，41，2，3l，2，3，4，5，61，3，4，5，6，73，4，5，64，6，7，86，7，8，98，9（3,8）满足全部需求，为最优解 现有一个企业有18个分销公司，该企业需要建立3个配送仓库，经该企业的考核，有6个候选地，现在身为企业决策者的你，要从6个候选地选出3个配送仓库你应该如何选？或者说你要考虑的因素有哪一些？总运输费用从分销公司到配送中心的单位运输费用分销公司运输的需求量我们要如何选择仓库？3.P中值模型指在一个给定数量和位置的需求集合和一个候选设施位置的

9、集合下，分别为p个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在工厂和需求点之间的运输费用和最低。需求点设施候选点P=3 d icij yijiN jMminij yjM1,i Nj pxjMyij=xj，i N，jMP中值模型1、精确法2、启发式算法-贪婪取走启发式算法贪婪取走总费用增加量最小P中值模型贪婪取走算法：第一步：令当前选中设施点数k m，即将所有m个候选位置都选中。第二步：将每个客户指派给k个设施点中距离最近的一个设施点。求出总运输费用Z。第三步：若k p，输出设施点及各客户的指派结果，停止；否则，转第四步。第四步：从k个设施候选点中确定一个取走点，满足：假如将它

10、取走并将它的客户指派给其他的最近设施点后，总费用增加量最小。第五步：从候选点集合中删去取走点，令k k 1，转第二步。Greedy Dropping Heuristic algorithm 某医药公司有8个分销公司(A1 A8)，公司拟新建2个配送仓库，用最低的运输成本来满足8个分销公司的需求。经过实地考察后，公司确定5个候选(D1D5),从候选地到各分销公司的单位运输成本、各分销公司的需求已确定，如表2-7所示，各分销公司分布及候选仓库位置如图2-12所示，试确定仓库的位置与分销公司分派情况，并计算出各仓库的运输成本。D1D2D3D4D5需求量需求量A1304548103510A225607

11、035506A3281525321011A4453020241225A5581225603015A6653015573313A7653516452820A822303520168各客户需求量与单位运输成本矩阵图第一步：贪婪总运输成本=10*10+25*6+10*11+.=1483 k=52 当移走D1之后，受到影响的是A2，A2指派给（除D1外，被移除之后）运输费用最低的D4，所产生的运费增加量为=210（35*6）-150（25*6）=60 移除D1后对整体运费的影响是增加了60 同理当移走D2之后，所产生的运费增加量为=195当移走D3之后，所产生的运费增加量为=435当移走D4之后，所产

12、生的运费增加量为=200当移走D5之后，所产生的运费增加量为=287 K=42 总运费增加量最小的60，也就是移除D1后对整体运费影响是最小的，故移除D1最为合理。同理移除的三个候选地分别是D1，D3，D4例 某公司在某新地区经过一段时间的宣传广告后，得到了 8 个超市的订单，由于该新地区离总部较远，该公司拟在该地区新建 2 个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地考查之后，已有 4 个候选地址。如图所示。从候选地址到各个超市运输成本Cij、各个超市的需求量di都已经确定，试选择其中的两个候选点作为仓库地址，使总运输成本最小。( p 2)。124567842133图 超市

13、及仓库候选点位置124567842133图 仓库选址及客户指派结果该模型是带容量限制的多设施选址问题s.t. Xij（运输量）=Dj(需求量) Xij=WiYi（配送中心容量） Yi=0CFLP模型求解方案一穷举法方案二分支定界法方案三 lingo软件求解lingo软件求解lingo模型基本用法（通常由以下三个部分组成）(1)目标函数:一 般表示成求某个数学表达式的最大值或最小值。(2)决策变量:目标函数值取决于哪些变(3)约束条件:对变量附加一些条件限制(通常用等式或不等式表示)注:LINGO默认所有决策变量都非负，因而变量非负条件可以不必输入。LINGO模型的基本组成:(1)集合定义部分:

14、集合的名称集合内的成员(组成集合的个体， 元素)，集合的属性(可以看成是与集合有关的变量或常量)(2)数据初始化(数据段)sets函数给定义的所有集合的已知属性赋初值“/”是指规定语法的规则(3)目标函数和约束条件for(s:e)该函数常用在约束条件中，表示对集合s中的每个成员都生成一个约束条件表达式，表达式的具体形式由参数e描述. sum(s:e)对集合s中的每个成员，分别得到表达式e的值然后返回所有这些值的和bin（x）限制x为0或1需求点B1B2B3B4B5B6B7B8需求量101010155151015例 有两个资源厂A 1、 A2可供资源量分别为a1 40单位，a2 50单位；有 8

15、 个需求点Bj(j 1,2.,8)，各点需求量如表 1 所示；已选定 5 个备选网点DK(K 1,2,.,5)网点，存储费用和网点规模的关系为一方根函数Hj j dK 。其中dK 为 1/2 吞吐量。表 1 各需求点需求量汇源B1B2B3B4B5B6B7B8资源量A112/D118/D110/D113/D510/D313/D311/D211/D240A217/D515/D511/D510/D511/D58/D416/D48/D450需求量101010155151015D1D2D3D4D5中转量201552525边际成本(四舍五入)8101787步骤一 求初始方案步骤二 求边际存储费用 总成本2

16、499D1D2D3D4D5B1B2B3B4B5B6B7B8A17781211A21412968D18511385101111D2101416894744D3171011352595D4815139672102D57973265128汇源B1B2 B3B4B5B6B7B8A120D125 18D5 D120D520D122D421D221D240A224D522 18D5 D517D521D416D424D416D4501010 10155151015步骤三新调运问题新费率表新运输规划模型汇源B1B2B3B4B5B6B7B8A120D125D51810D1205D5205D121D42410D2

17、21D240A224D522D518D517D520D415D4423D415D450101010155151015D1D2D3D4D5中转量251003025边际成本(四舍五入)81377步骤四 迭代新的费率表与前一次迭代相同，算法结束。hjikhkjhijkDhkThkFjZ j Shj(xhijk)dhjk)xhijk (chijminF 6、Kuehn-Hamburger模型1jkhijkjkhijkhijkjVjk 0,1xhijk 0hikVWjxQhkVjkYhixix内向与外向运输费用物流节点固定物流节点变动成本损失费小结 多物流节点选址方法与模型的优点与局限性优点：库存和运输同步决策的问题局限性：考虑的是成本，而未关注收入效应 其他的多物流节点选址的模型与方法？多级选址生产技术库存水平环保水平