物流系统的节点选址课件.pptx

1、1第一节第一节 物流节点概述物流节点概述一、物流节点的含义一、物流节点的含义物流过程：运动停顿运动停顿 运动线；停顿点。物流节点：物流网络中连接物流线路的结节处。节点和线路结合在一起，构成了物流网络结构，节点和线路的相互关系和配置形成物流系统的比例关系，即物流系统的结构。2第一节第一节 物流节点的类型和功能物流节点的类型和功能物流节点（广义）：所有进行物资中转、集散和储运的节点，包括港口、空港、火车货运站、公路枢纽、大型公共仓库及现代物流中心、配送中心、物流园区等。物流节点（狭义）：现代物流中心、配送中心、物流园区和配送网点等。包装、卸载、储存、配货、流通加工等活动都是在节点上完成的。管理工作

2、包括：订单接收和验证、货物库存安排、送货任务分配、物流任务形成、数量和质量的跟踪。3第一节第一节 物流节点的类型和功能物流节点的类型和功能二、物流节点的类型二、物流节点的类型1、按功能功能分类：转运型节点：以接连不同线路和不同运输方式为主要职能的节点。铁路运输线上的货站、车站；水运线路上的港口、码头；空运线路上的空港等。以转运货物为主，货物在节点上停滞时间较短。储存型节点：以保管存放货物为主要职能的节点。储备仓库、营业仓库、中转仓库、货栈等。货物需要较长时间储存，储存量大、周转较慢，对仓库的货物保管、养护要求较高。4第一节第一节 物流节点的类型和功能物流节点的类型和功能流通型节点：连接干线物流

3、与末端物流，以货物配备和组织送货为主要功能的节点。流通仓库、流通中心、配送中心等。配送中心具集货、分货、分拣、倒装、加工、配送、为客户调节库存、送货服务以及收集和传递信息的功能。综合型节点：集中于一个节点中全面实现两种以上主要功能按照功能复杂功能复杂性：单一功能点、复合功能点、枢纽点5第一节第一节 物流节点的类型和功能物流节点的类型和功能2、按规模规模分类：物流园区、物流中心、配送中心物流园区：在几种运输方式衔接地形成的物流节点活动的空间集散体，是在政府规划指导下多种现代物流设施和多家物流组织机构在空间上集中布局的大型场所，是具有一定规模和多种服务的新型物流业务载体。物流中心：综合性、地域性、

4、大批量的货物物理位移转换集散的新型设施设备的集合，它把物流、信息流融为一体成为产销企业之间的中介组织和现代物流活动的主要载体。6第一节第一节 物流节点的类型和功能物流节点的类型和功能从规模来看：物流园区是巨型物流设施，其规模最大，物流中心次之，配送中心最小；从流通货物来看：物流园区的综合性较强，专业性较弱。物流中心在某个领域综合性、专业性较强，具有这个领域的专业性。配送中心则主要面向城市生活或某一类型生产企业，其专业性很强；从结点功能来看：物流园区的功能十分全面，存储能力大，调节功能强。物流中心的功能健全，具有一定的存储能力和调节功能。而配送中心的功能较为单一，以配送功能为主。7物流园区物流中

5、心功能具有多式联运、综合运输、干线终端运输等大规模处理货物和提供服务的功能主要是分销功能，并且具有货物运输中转功能，且以配送业务为主用地要求要求物流企业及相关的一些辅助企业在园区内聚集，且基础设施相对齐全，要处理的物流量大，必须 在其周围留有适当空间为以后发展之用，所以物流园要求用地充裕且有扩展性物流中心在这方面要求较低改善城市交通环境程度一般建在远离市中心的地区，布设在城市外围或郊区，同时注重园区与城市对外交通枢纽的联动规划建设，所以对改善城市交通环境的影响较大主要以配送业务为主，要求快速准时提供服务，故在空间距离上应尽量靠近需求点，并要有连接市中心的快速干道，所以对改善城市交通环境的作用不

6、是很大市场要求所服务的市场是多样化的服务的市场一般是专业化的服务对象有综合性的基础服务设施，且面向全社会提供服务只在局部领域进行经营服务经营管理方式物流园不一定是经营管理的实体，物流经营企业之间的关系可以是资产入股、租赁、合作经营或联合开发物流中心是物流经营和管理的实体政策环境不同政府为了吸引各种企业在物流园区内聚集，使其获得规模效益、范围效益，进而降低物流成本，政府通常为入住的物流企业提供各种优惠政策对物流中心这样的优惠政策较少8物流中心配送中心定义是从事物流活动的场所或组织是从事配送业务的物流场所或组织基本符合的条件1、主要面向社会服务；2、物流功能健全；3、完善的信息网络；4、辐射范围大

7、；5、少品种、大批量；6、存储、吞吐能力强；7、物流业务统一经营、管理1、主要为特定用户服务；2、配送功能健全；3、完善的信息网络；4、辐射范围小；5、多品种、小批量；6、以配送为主，储存为辅功能可单可全较为全面规模一般较大可大可小在供应链中的位置在配送中心的上游在物流中心的下游物流特点少品种、大批量、少供应商多品种、小批量、多供应商服务对象通常提供第三方物流服务一般为公司内部服务9第一节第一节 物流节点的类型和功能物流节点的类型和功能三、物流节点的功能三、物流节点的功能储运储运衔接衔接管理信息管理信息配套延伸配套延伸10第一节第一节 物流节点的类型和功能物流节点的类型和功能三、物流节点的功能

8、三、物流节点的功能1、储运储运功能功能最基本功能，货物保管、安全库存、整合、分发、发运2、衔接衔接功能功能物流活动需要若干环节，在不同线路间进行转换，不同线路之间的输送形态、输送装备、输送数量不同。节点将各个物流线路连接成一个系统，使各线路通过节点变得更为贯通1）通过转换运输方式衔接不同运输手段；2）通过加工、分拣、配货，衔接干线物流及配送物流；3）通过储存、保管衔接不同时间的供应和需求物流；4）通过集装箱、托盘等集装处理衔接整个“门到门”运输11第一节第一节 物流节点的类型和功能物流节点的类型和功能3、信息信息功能功能物流系统的软件物流系统的软件物流节点是信息收集、处理、传递的集中地4、管理

9、管理功能功能物流系统的神经物流系统的神经物流系统的管理设施和指挥机构往往集中设置于物流节点中，各物流节点大多是集管理、指挥、调度、信息、衔接及货物处理为一体的物流综合设施5、配套配套功能功能1）车辆停靠及检修、加油、配件供应等辅助服务；2）金融生活配套服务，如餐饮、住宿、购物、提款、保险等服务；3）工商、税务、海关的服务6、延伸延伸功能功能货物调剂中心、系统技术设计、咨询培训服务等第二节第二节 物流节点选址概述物流节点选址概述I.选址决策内容l设施数量、规模和位置l供货点、存储点指派l仓储设施自营还是外租 设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。方法方法II

10、.II.选址决策的影响因素选址决策的影响因素外部影响因素外部影响因素l宏观政治、经济因素l基础设施及环境l竞争对手内部影响因素内部影响因素 企业发展战略、服务水平、商品特性等方法方法第二节第二节 物流节点选址概述物流节点选址概述14III.III.选址模型的分类选址模型的分类选址的对象选址的区域选址的目标约束条件选址考虑的问题第二节第二节 物流节点选址概述物流节点选址概述15III.III.选址模型的分类选址模型的分类1 根据被定位设施的维度及数量l根据设施的维数l根据设施选址的数量体选址：定位三维物体面选址：定位二维物体线选址：定位一维物体点选址：定位零维物体单一设施选址：主要考虑运输成本多

11、设施选址：需要考虑设施间需求分配、设施成本与数量间的关系第二节第二节 物流节点选址概述物流节点选址概述162 根据选址问题目标区域的特征连续选址：连续选址：待选区域是一个平面，不考虑其他结构，可能的选址位置数量无限。如企业配送中心的初步选址网格选址：网格选址：待选区域是一个平面，被细分成许多相等面积的区域，候选地址的数量是有限的，但数量也很大。如：仓库中不同存储位置的分配离散选址：离散选址：目标选址区域是一个离散的候选位置的集合。候选位置数量有限且较少。如：企业配送中心的详细选址设计第二节第二节 物流节点选址概述物流节点选址概述173 根据选址成本4 选址约束可行成本方案/最优成本方案Mini

12、sum/Minimax目标函数：Minisum是寻求设施选址总成本最小（中中值值问题）；Minimax是优化已存在设施的单个最大成本组分（中心中心问题）Maxmin目标函数是最优化已存在设施的最小成本组分（反中心反中心问题）固定权重/可变权重（单纯选址问题/选址 分配问题）：新设施与已存在设施的关系（权重）与新设施的位置无关/有关。有能力约束/无能力约束不可行区域约束067反中心点=2.5中心点=3.5中值=5.55第二节第二节 物流节点选址概述物流节点选址概述18一般采用两种方法计算节点之间的距离：直线距离（欧几里得距离）；折线距离（城市距离）IV.IV.选址问题中的距离计算选址问题中的距离

13、计算第二节第二节 物流节点选址概述物流节点选址概述19Rijijijdxxyy22()()Rijijijdxxyy1 直线距离直线距离常用于城市间配送问题和通信问题城市间配送问题的实际路线距离受到城市道路的约束，可以将两点间的直线距离乘以一个适当的系数来近似。美国大陆是1.2，东南美洲是1.26，刘飞（2009）使用1.41。2 折线距离折线距离一般用于道路较规则的城市内的配送问题、直线通道的工厂及仓库内的布置、物料搬运设备的顺序移动第二节第二节 物流节点选址概述物流节点选址概述u 连续选址模型 待选区域是一个平面，不考虑其他结构 可能的选址位置的数量是无限的一、交叉中值模型一、交叉中值模型交

14、叉中值模型（Cross Median）用来解决连续点选址问题，利用城市距离进行计算。通过交叉中值方法对单一选址问题在一个平面上的加权城市距离进行最小化。第三节第三节 选址模型选址模型2023年1月9日星期一全国网点布局全国网点布局石家庄网点布局石家庄网点布局槐安路中华大街新华路西二环21申通快递服务网点选址申通快递服务网点选址城市内、单一设施点、连续选址问题城市内、单一设施点、连续选址问题交叉中值模型交叉中值模型A(3,1);1B(5,2);7C(4,3);3D(2,4);3E(1,5);612345622 一维简单选址：在一街道上，选择一个快递网点，使得服务街道上所有顾客的总距离最短。01x

15、s一一 交叉中值模型交叉中值模型不考虑其他因素（住宅区的位置、权重）时选址位置：路线的中点选址位置：路线的中点假定住宅小区的居民需求在这条街道上均匀分布1.基本原理基本原理233504()()isiiisiiw xxw xx51miniisiZw xx考虑权重因素x1w1x2w2x3w3x4w4x5w501xs选址位置：路线的权重中心选址位置：路线的权重中心中值中值3504=iiiiww最优解：最优解：一一交叉中值模型交叉中值模型245151miniiiiisisZw xw yyx (x1y1)w1(x3y3)w3(x2y2)w2(x4y4)w4(xsys)(x5y5)w5X X轴中值轴中值Y

16、 Y轴中值轴中值 二维（面）选址：在一定区域内设置一个快递网点，使服务所有顾客的总距离最短。一一交叉中值模型交叉中值模型252023年1月9日星期一11371 36/2102niiWw kmxs43kmys31、计算权重中值：2、寻找X轴的中值：（见图）3、寻找Y轴的中值：（见图）4、确定交叉中值，获得可能方案：（见图）一一交叉中值模型交叉中值模型2.模型应用模型应用申通快递网点的选址演示表261234560A(3,1);1B(5,2);7C(4,3);3D(2,4);3E(1,5);6123456XY3 4sxkm3 4sxkm3 4sxkm6iw 9iw 10iw 10iw X X轴中值轴

17、中值从左到右从左到右从右到左从右到左267iw 10iw 返返回回271234560A(3,1);1B(5,2);7C(4,3);3D(2,4);3E(1,5);6123456XY11iw3 4sykm3sykm2 3sykm8iw Y Y轴中值轴中值从上到下从上到下从下到上从下到上12iw9iw 返返回回28kmxs43kmys3kmxs432 3sykm3sxkmkmys3A(3,1);1B(5,2);7C(4,3);3D(2,4);3E(1,5);6123456123456MS可可能能方方案案可可行行方方案案线段线段 MCMC区域区域 S S点点 M M交叉中值交叉中值292023年1月

18、9日星期一需求点沿X轴的位置从左到右E166D239A3110C4313B57从右到左B577C4310A3111D23E16iwiw表1：X轴方向中值计算ix3 4sxkm3 4sxkm302023年1月9日星期一需求点沿Y轴的位置从上到下E566D439C3312B27A11从下到上A111B278C3311D43E56iwiw表2：Y轴方向中值计算iy回3 4sykm2 3sykm31l交叉中值模型（实例）M（3,3）C（4,3）需求点权重距离总和需求点权重距离总和112211332732127214331333004326433956424565305656一一交叉中值模型交叉中值模型

19、32 前面介绍的交叉中值模型由于其本身的局限性，只适合于解决一些小范围的城市内选址问题。精确重心法在评价的过程中使用的是直线距离，使得选址问题变得复杂，但是有着更为广阔的应用范围。选址实例：TCL公司希望筹建一个北方地区配送中心，为所有北方地区顾客提供服务。二、精确重心法二、精确重心法城市间、单一设施、连续选址问题精确重心法精确重心法33 在使用了直线距离后，目标函数变成了：221min()()niisisiZxxyy二二精确重心法精确重心法 分别对xs和ys进行求偏微分，并且令其为零，这样就可以得到两个微分等式。应用这两个等式分别对xs和ys进行求解，即可以求出下面的一对隐含有最优解的等式：

20、(x1y1)w1(x3y3)w3(x2y2)w2(x4y4)w4(xsys)1.基本原理基本原理342023年1月9日星期一 该微分方程组不能直接求解，使用迭代方法求解。niisiniisiisdwdxwx11niisiniisiisdwdywy1122isisisdxxyy其中，迭代法步骤：1）初始值设定2）迭代3）中止准则352023年1月9日星期一101101niiisniiniiisniiw xxww yyw1）初始值xs0和ys0 的确定：a.任意选择一个点作为初始值；b.按照下面的简化公式简化公式选址初始值。二二精确重心法精确重心法362023年1月9日星期一1(1)()1(1)1

21、(1)()1(1)niiiis is iniiis iniiiis is iniiis iw xdxwdw ydywd2）迭代迭代公式迭代公式二二精确重心法精确重心法22(1)(1)(1)is iis iis idxxyy其中，372023年1月9日星期一l如果该迭代过程具有收敛性，那么经过无限次的迭代之后，可以得到一个最优解xs*和ys*。但是在实际中，可以迭代的次数是有限的，所以在迭代过程中需要确定一个中止准则。l中止准则的设置：a.根据经验，直接设置一个确定的迭代次数N；二二精确重心法精确重心法3）中止准则382023年1月9日星期一b.判断两次迭代结果的差值是否小于设定的阈值；1()(

22、)limss is isitxxxx 1()()limss is isityyyy 二二精确重心法精确重心法3）中止准则c.判断总距离是否减少或者两次迭代差值小于设定值。1222()()1()niis iis iiZ iwxxyylim()(1)()()(1)itZ iZ iZ iZ iZ iZ 或者 392023年1月9日星期一选址实例：选址实例：假设这个住宅聚集区街道建设尚未完成，住宅聚集区内大多是空地和纵横交错的小街道，可以使用直线距离对距离加以计算。使用精确重心法选择一个最优的位置作为快递收发网点。从M点（3，3）（即：xsi0=3和ysi0=3）开始进行直线最优的搜索，下表进行了一些

23、必要的计算。2.模型应用模型应用二二精确重心法精确重心法精确重心法精确重心法第一次迭代初始位置(xs0,ys0)33需求点ABCDE(xi,yi)3152432415权重wi17336距离dis(0)22.23611.4142.828wixi/dis(0)；wiyi/dis(0)1.50.515.6536.2611294.2426 8.485 2.121 10.606wi/dis(0)0.53.13032.1212.121迭代位置(x1,y1)3.2663.205中止判断（Z1）41.866第二次迭代(xs1,ys1)3.26613.205需求点12345(xi,yi)3152432415权重

24、wi17336距离dis(1)2.2212.1110.7621.4952.891wixi/dis(1)；wiyi/dis(1)1.350 0.450 16.576 6.630 15.752 11.814 4.0138.0262.075 10.37wi/dis(1)0.4503.3153.9382.0072.075迭代位置(x2,y2)3.3743.165中止判断（Z2）41.118精确重心法精确重心法第三次迭代(xs2,ys2)3.3743.165需求点12345(xi,yi)3152432415权重wi17336距离dis(2)2.19720.6471.6083.001wixi/dis(2)

25、；wiyi/dis(2)1.366 0.455 17.500718.54513.9093.731 7.462 1.999 9.997wi/dis(2)0.4553.5004.6361.8651.999迭代位置(x3,y3)3.4633.117中止判断（Z3）40.9672023年1月9日星期一中止准则的使用。若（1）N=2；（2）坐标值阈值为0.2；坐标值变化幅度小于4%；（3）总费用阈值为0.2；总费用相对变化幅度小于1%。迭代次数坐标点坐标点迭代差值总距离总距离迭代差值xy绝对差值相对差值41.866绝对值相对值13.2663.2050.266，0.2058.88%，6.85%41.118

26、0.7481.79%23.3743.1650.108，-0.0413.30%，-1.27%40.9670.1500.37%33.4633.1170.089，-0.0482.64%，-1.52%40.8440.1240.30%补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用重心法为配送中心选址。零售点物资需求量qi运输费用ri坐标xiyi1252223511332.5510841549第一步，按照简化公式确定初始值9.415.2329185.23322)0(8.715.23241105.211322)0(11111111niiiniiiiniiniiisniiiniiiini

27、iniiisrqyrqwywyrqxrqwxwx精确重心法精确重心法第二步，以点（第二步，以点（7.87.8，4.94.9）作为配送中心，计算距）作为配送中心，计算距离与总费用，迭代确定配送中心离与总费用，迭代确定配送中心1.56.5/18.3/5.27.3/35.6/26.5/918.3/85.27.3/335.6/22)0()0()1(6.86.5/18.3/5.27.3/35.6/26.5/418.3/105.27.3/1135.6/22)0()0()1(41414141iisiiisiisiisiiisiisdwdywydwdxwx6.5)99.4()48.7()0(8.3)89.4(

28、)108.7()0(7.3)39.4()118.7()0(5.6)29.4()28.7()0(2/12242/12232/12222/1221ssssdddd1965)6.518.35.27.335.62()0(Z精确重心法精确重心法第三步，以点（第三步，以点（8.68.6，5.15.1）作为配送中心，计）作为配送中心，计算距离与总费用，迭代确定配送中心算距离与总费用，迭代确定配送中心2.56.5/18.3/5.27.3/35.6/26/910.3/85.22.3/333.7/22)1()1()2(0.96.5/18.3/5.27.3/35.6/26/410.3/105.22.3/1133.7

29、/22)1()1()2(41414141iisiiisiisiisiiisiisdwdywydwdxwx6)91.5()46.8()1(0.3)81.5()106.8()1(2.3)31.5()116.8()1(3.7)21.5()26.8()1(2/12242/12232/12222/1221ssssdddd1915)610.35.22.333.72()1(Z第四步，以点（第四步，以点（9.0，5.2）作为配送中心，计算距离与总费用）作为配送中心，计算距离与总费用此时，Z(2)=Z(1)=191，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（9.0，5.2）或（8.6，5.1

30、）。3.6)92.5()40.9()1(0.3)82.5()100.9()1(0.3)32.5()110.9()1(7.7)22.5()20.9()1(2/12242/12232/12222/1221ssssdddd1915)3.610.35.20.330.72()2(Z 用精确重心法得到的最优解只有一个点，而不会是一条线段或者一个区域。而且只有在十分偶然的情况下，才会出现用交叉中值法和精确重心法得到的最优优地址一致的情况。连续选址模型连续选址模型交叉中值模型与精确重心法交叉中值模型与精确重心法 城市距离（折线距离）；城市距离（折线距离）；适合于小范围的城市内选址问题；适合于小范围的城市内选址

31、问题；目标使对加权的城市距离最小化；目标使对加权的城市距离最小化；属于单一设施连续点选址问题。属于单一设施连续点选址问题。欧几米德距离（直线距离）；欧几米德距离（直线距离）；适合于大范围城市间选址问题；适合于大范围城市间选址问题；目标是使加权的直线距离最小化；目标是使加权的直线距离最小化；属于单一设施的连续点选址问题。属于单一设施的连续点选址问题。2023年1月9日星期一49u 离散选址模型 在有限的候选位置里面，选取最合适的一个或者一组位置为最优方案 候选方案只有有限个元素，只需要分析这几个有限的位置V.V.选址模型选址模型 例：北国超市计划在裕华区选址设置超级市场，通过初选，满足超市选址要

32、求的备选点共计10处，裕华区的各住宅小区位置及权重已知。请问：北国超市如何决策最终的选址方案？50V.V.选址模型选址模型ABCDEFGHIJ目前主要有两种模型：覆盖模型、目前主要有两种模型：覆盖模型、PP中值模型。中值模型。51三三覆盖模型覆盖模型对于需求已知的一些需求点，如何确定一组服务设施来满足它们的需求。在模型中，需要确定服务设施的最小数量和合适位置。n适用范围：商业物流系统，如零售点的选址问题、加油站的选址、配送中心的选址等；公用事业系统，如急救中心、消防中心等。计算机与通信系统，有线电视网的基站、无线通信网络基站等。V.V.选址模型选址模型52根据解决问题的方法不同，分为两种不同的

33、主要模型：1、集合覆盖模型：集合覆盖模型：用最小数量的设施去覆盖所有的需求点2、最大覆盖模型：最大覆盖模型：在给定数量的设施下，覆盖尽可能多的需求点。两类模型的区别：区别：集合覆盖模型要满足所有的需求点，而最大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取决于服务设施的资源充足与否。三三覆盖模型覆盖模型1、集合覆盖模型、集合覆盖模型 目标：用尽可能少的设施去覆盖所有的需求点。数学模型为：()()min1,.0,1,0,jj Nijj B iiijjji A jjijxyiNd yC xjNstxiNyi jN552023年1月9日星期一1、集合覆盖模型、集合覆盖模型 Njjxmin)(1i

34、BjijN，iy)(,jAijjijiNjxCydNixj,1,0Njiyij,0最小化设施的数目保证每个需求点的需求得到完全的满足是对每个提供服务的服务网点的服务能力的限制保证一个地方最多只能投建一个设施允许一个设施只提供部分的需求562023年1月9日星期一l对于此类带有约束条件的极值问题，有两大类方法：一是应用分枝定界的方法，由于运算量方面的限制，一般也只适用于小规模问题的求解；二是启发式方法，所得到的结果不能保证是最优解，但是可以保证是可行解，可以对大型问题进行有效的分析、求解。572023年1月9日星期一l例子：例子：乡村医疗诊所选址问题 l卫生部门考虑到农村地区的医疗条件的落后和匮

35、乏，计划在某一地区的9个村增加一系列诊所，以改善该地区的医疗卫生水平。它希望在每一个村周边30km的范围之内至少有一个诊所，不考虑诊所服务能力的限制。卫生部门需要确定至少多少个诊所和它们相应的位置。除了第6个村之外，其他任何一个村都可以作为诊所的候选地点，原因是在第6村缺乏建立诊所的必要条件。下图是各个村之间的相对位置和距离的地图。582023年1月9日星期一l第一步，找到每一个村可以提供服务的所有村的集合 ，即它们距该村距离小于或等于30km的所有村的集合。l第二步，找到可以给每一个村提供服务的所有村的集合 。一般说来，这两个集合是一致，但是考虑到其他的一些限制条件，就可能出现差异。l第三步

36、，找到其他村服务范围的子集，将其省去，可以简化问题。)(jA)(iB1 1、集合覆盖模型、集合覆盖模型592023年1月9日星期一602023年1月9日星期一l第四步，确定合适的组合解。（3，8）是可以覆盖所有村的一个数量最少的组合解：3村的诊所可以覆盖村1村到5村，而8村的诊所覆盖6村到9村。n 思考题，如果放宽问题的限制条件，将一个诊所的服务半径增加到40km，最终选择什么样的组合村作为备选方案。1 1、集合覆盖模型、集合覆盖模型 集合覆盖模型整数规划集合覆盖模型整数规划整数规划模型：整数规划模型：9,8,7,6,5,4,3,2,1,9,8,7,6,5,4,3,2,1,09,8,7,6,5

37、,4,3,2,1,1,01111111110.min9998898887787774686765646355545347454443413534333231232221141312116987654321jiyjxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyxtsxxxxxxxxxzijj9998989888786878777674768676564636565554535474645444341436353433323132322212141312111999999999.xyyxyyyyxyyyyxyyyyyxyyyyxyyyyyyxyyyyyyxyyyxyyyyts

38、622023年1月9日星期一2、最大覆盖模型、最大覆盖模型 l已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择p个位置作为物流设施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。l目标：对有限的服务网点进行选址，为尽可能多的对象提供服务。目标函数是：()()()max1,0,1,0,iijj N i A jijj B iiijjji A jjj Njijd yyiNd yC xjNxpxjNyiN jN 632023年1月9日星期一2、最大覆盖模型、最大覆盖模型 l目标：对有限的服务网点进行选址，为尽可能多的对象提供服务。目标函数是：l约束条件为：)(maxjAii

39、jiNjyd)(1iBjijN，iy)(jAijjijiN，jxCydNjjpxN，j，xj10Njiyij,0最大可能地对需求提供服务需求的限制，服务不可能大于当前需求的总和设施的服务能力的限制问题本身的限制，也就是说最多可能投建设设施的数目保证一个地方最多只能投建一个设施允许一个设施只提供部分的需求2023年1月9日星期一l医疗站问题，如果仍旧不考虑其服务能力的限制，最多诊所数目为2，用最大覆盖模型进行分析，用贪婪算法进行求解。该算法是以空集合作为原始解集合，然后在剩下的所有候选点中，选择一个具有最大满足能力的候选点加入到现在的解集合中，如此往复，直到达到设施数量限制或全部需求都得以满足。

40、642 2、最大覆盖模型、最大覆盖模型集合覆盖模型与最大覆盖模型数学模型比较 MjjAiijiyd)(max()()1,0,1,0,ijj B iiijjjiA jjj MjijyiNd yC xjNxpxjNyiN jNMjjxmin()()1,0,1,0,ijj B iiijjji A jjijyiNd yC xjNxjNyiN jN集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型整数规划模型整数规划模型最大覆盖模型整数规划最大覆盖模型整数规划1111111110.min999889888778777468676564635554534745444341353433323123222114

41、1312116987654321998998887868877767476555453574645444341463534333231332221241312111yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyxpxxxxxxxxxtsyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyz9,8,7,6,5,4,3,2,19,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,1,0999999999.99989898887868787776747686765646365655545354746454443414363534333231323

42、22212141312111jiyjxxyyxyyyyxyyyyxyyyyyxyyyyxyyyyyyxyyyyyyxyyyxyyyytsijj2023年1月9日星期一l思考题：一个快递企业准备在某县的农村地区建设一批快递收发网点。该地区的村落坐落情况和相对距离如图所示。快递企业需要为任意一村服务的距离在20min以内，需要设置几个服务网点，它们的位置又在哪里？67三、覆盖模型三、覆盖模型123475625152035152020201520682023年1月9日星期一lP-中值模型是指在一个给定数量和位置的需求集合和一个候选设施位置的集合下，分别为p个设施找到合适的位置并指派每个需求点到一个特

43、定的设施，使之达到在工厂和需求点之间的运输费用最低。四、四、P-P-中值模型中值模型需求点（N）设施点（M）p=3一般适用于工厂或仓库的选址问题一般适用于工厂或仓库的选址问题692023年1月9日星期一l实例：实例：某饮料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地考查之后，确定了4个候选地址。从候选地址到不同超市的单位产品运输成本、各个超市的需求量都已经确定，如图和表所示。四、四、P-P-中值模型中值模型70候选地点 j需求di12341412206100221025

44、105033416141204649280518127320061424970720302116082412622100123456781234运费cijP-P-中值模型需要解决的问题：中值模型需要解决的问题：超市i（1 1）选择合适设施位置（）选择合适设施位置（）（2 2）指派客户到相应的设施中去（）指派客户到相应的设施中去（）ijyjx712023年1月9日星期一lP-P-中值模型的数学表达式中值模型的数学表达式ijc10jx10ijyN第i个需求点的需求量建设设施id不建设设施从需求点i到设施点j的单位运输费用需求点i不由设施点j提供服务需求点i由设施点j提供服务需求点数量M备选设施点数

45、量未知变量未知变量722023年1月9日星期一lP-P-中值模型的数学表达式中值模型的数学表达式MjijijiNiycdminMjijN，iy1Mjjpx,ijjyx iN jMM，j，xj10MjNiyij,1,0目标函数每个客户（需求点）只有一个设施来提供服务限制总设施数为p保证没有设施的地点不会有客户对应目标函数：约束条件：73lP-中值模型（实例）贪婪取走启发算法贪婪加入启发算法基本步骤：（1）第一步，初始化，令循环参数k=M，将所有的M个候选位置都选中，然后将每个客户指派给离其距离最近的一个候选位置；超市候选地点需求1234141220610022102510503341614120

46、4649280518127320061424970720302116082412622100四、四、P-P-中值模型中值模型123456781234400100360600160140120600设施点费用1860214037204760总费用248074（2）第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令 k=k-1；四、四、P-P-中值模型中值模型P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法需求点移走位置1后费用增加量1+2002+4003+120总费用增加量+720移走位置移走位置1 1：超市候选地点需求12341412

47、20610022102510503341614120464928051812732006142497072030211608241262210012345678234600160140120600600500480P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法需求点移走位置2后费用增加量6+140总费用增加量+140移走位置移走位置2 2：超市候选地点需求1234141220610022102510503341614120464928051812732006142497072030211608241262210021345678134400100360600160280120600P中

48、值模型贪婪取走启发式算法中值模型贪婪取走启发式算法需求点移走位置2后费用增加量7+5408+600总费用增加量+1140移走位置移走位置3 3：超市候选地点需求12341412206100221025105033416141204649280518127320061424970720302116082412622100123456781244001003606001601406601200需求点移走位置2后费用增加量4+2405+800总费用增加量+1040移走位置移走位置4 4：超市候选地点需求1234141220610022102510503341614120464928051812732

49、0061424970720302116082412622100123456781234001003601400400140120600因此，移走位置因此，移走位置2 2，总费用为，总费用为26202620，令，令k=k-1=3k=k-1=378（3）第三步，重复第二步，直到 k=p；四、四、P-P-中值模型中值模型移走位置移走位置1 1：P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法需求点移走位置1后费用增加量1+2002+4003+1320总费用增加量+1920超市候选地点需求123414122061002210251050334161412046492805181273200614

50、2497072030211608241262210012345678346005001680600160280120600P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法移走位置移走位置3 3：需求点移走位置1后费用增加量6+3507+5408+1600总费用增加量+2490超市候选地点需求1234141220610022102510503341614120464928051812732006142497072030211608241262210012345678144001003606001606302200660P中值模型贪婪取走启发式算法中值模型贪婪取走启发式算法移走位置移走位置4