物流系统的节点选址PPT课件

1、1第一节第一节 物流节点的类型和功物流节点的类型和功能能物流节点（广义）：所有进行物资中转、集散和储运的节点，包括港口、空港、火车货运站、公路枢纽、大型公共仓库及现代物流中心、配送中心、物流园区等。物流节点（狭义）：现代物流中心、配送中心、物流园区和配送网点等。包装、卸载、储存、配货、流通加工等活动都是在节点上完成的。管理工作包括：订单接收和验证、货物库存安排、送货任务分配、物流任务形成、数量和质量的跟踪。第1页/共93页2第一节第一节 物流节点的类型和功物流节点的类型和功能能二、物流节点的类型二、物流节点的类型1、按功能功能分类：转运型节点：以接连不同线路和不同运输方式为主要职能的节点。铁路

2、运输线上的货站、车站；水运线路上的港口、码头；空运线路上的空港等。以转运货物为主，货物在节点上停滞时间较短。储存型节点：以保管存放货物为主要职能的节点。储备仓库、营业仓库、中转仓库、货栈等。货物需要较长时间储存，储存量大、周转较慢，对仓库的货物保管、养护要求较高。第2页/共93页3第一节第一节 物流节点的类型和功物流节点的类型和功能能流通型节点：连接干线物流与末端物流，以货物配备和组织送货为主要功能的节点。流通仓库、流通中心、配送中心等。配送中心具集货、分货、分拣、倒装、加工、配送、为客户调节库存、送货服务以及收集和传递信息的功能。综合型节点：集中于一个节点中全面实现两种以上主要功能按照功能复

3、杂功能复杂性：单一功能点、复合功能点、枢纽点第3页/共93页4第一节第一节 物流节点的类型和功物流节点的类型和功能能2、按规模规模分类：物流园区、物流中心、配送中心物流园区：在几种运输方式衔接地形成的物流节点活动的空间集散体，是在政府规划指导下多种现代物流设施和多家物流组织机构在空间上集中布局的大型场所，是具有一定规模和多种服务的新型物流业务载体。物流中心：综合性、地域性、大批量的货物物理位移转换集散的新型设施设备的集合，它把物流、信息流融为一体成为产销企业之间的中介组织和现代物流活动的主要载体。第4页/共93页5第一节第一节 物流节点的类型和功物流节点的类型和功能能从规模来看：物流园区是巨型

4、物流设施，其规模最大，物流中心次之，配送中心最小；从流通货物来看：物流园区的综合性较强，专业性较弱。物流中心在某个领域综合性、专业性较强，具有这个领域的专业性。配送中心则主要面向城市生活或某一类型生产企业，其专业性很强；从结点功能来看：物流园区的功能十分全面，存储能力大，调节功能强。物流中心的功能健全，具有一定的存储能力和调节功能。而配送中心的功能较为单一，以配送功能为主。第5页/共93页6物流园区物流中心功能具有多式联运、综合运输、干线终端运输等大规模处理货物和提供服务的功能主要是分销功能，并且具有货物运输中转功能，且以配送业务为主用地要求要求物流企业及相关的一些辅助企业在园区内聚集，且基础

5、设施相对齐全，要处理的物流量大，必须 在其周围留有适当空间为以后发展之用，所以物流园要求用地充裕且有扩展性物流中心在这方面要求较低改善城市交通环境程度一般建在远离市中心的地区，布设在城市外围或郊区，同时注重园区与城市对外交通枢纽的联动规划建设，所以对改善城市交通环境的影响较大主要以配送业务为主，要求快速准时提供服务，故在空间距离上应尽量靠近需求点，并要有连接市中心的快速干道，所以对改善城市交通环境的作用不是很大市场要求所服务的市场是多样化的服务的市场一般是专业化的服务对象有综合性的基础服务设施，且面向全社会提供服务只在局部领域进行经营服务经营管理方式物流园不一定是经营管理的实体，物流经营企业之

6、间的关系可以是资产入股、租赁、合作经营或联合开发物流中心是物流经营和管理的实体政策环境不同政府为了吸引各种企业在物流园区内聚集，使其获得规模效益、范围效益，进而降低物流成本，政府通常为入住的物流企业提供各种优惠政策对物流中心这样的优惠政策较少第6页/共93页7物流中心配送中心定义是从事物流活动的场所或组织是从事配送业务的物流场所或组织基本符合的条件1、主要面向社会服务；2、物流功能健全；3、完善的信息网络；4、辐射范围大；5、少品种、大批量；6、存储、吞吐能力强；7、物流业务统一经营、管理1、主要为特定用户服务；2、配送功能健全；3、完善的信息网络；4、辐射范围小；5、多品种、小批量；6、以配

7、送为主，储存为辅功能可单可全较为全面规模一般较大可大可小在供应链中的位置在配送中心的上游在物流中心的下游物流特点少品种、大批量、少供应商多品种、小批量、多供应商服务对象通常提供第三方物流服务一般为公司内部服务第7页/共93页8第一节第一节 物流节点的类型和功物流节点的类型和功能能三、物流节点的功能三、物流节点的功能储运衔接管理信息配套延伸第8页/共93页9第一节第一节 物流节点的类型和功物流节点的类型和功能能三、物流节点的功能三、物流节点的功能1、储运储运功能功能最基本功能，货物保管、安全库存、整合、分发、发运2、衔接衔接功能功能物流活动需要若干环节，在不同线路间进行转换，不同线路之间的输送形

8、态、输送装备、输送数量不同。节点将各个物流线路连接成一个系统，使各线路通过节点变得更为贯通1）通过转换运输方式衔接不同运输手段；2）通过加工、分拣、配货，衔接干线物流及配送物流；3）通过储存、保管衔接不同时间的供应和需求物流；4）通过集装箱、托盘等集装处理衔接整个“门到门”运输第9页/共93页10第一节第一节 物流节点的类型和功物流节点的类型和功能能3、信息信息功能功能物流系统的软件物流系统的软件物流节点是信息收集、处理、传递的集中地4、管理管理功能功能物流系统的神经物流系统的神经物流系统的管理设施和指挥机构往往集中设置于物流节点中，各物流节点大多是集管理、指挥、调度、信息、衔接及货物处理为一

9、体的物流综合设施5、配套配套功能功能1）车辆停靠及检修、加油、配件供应等辅助服务；2）金融生活配套服务，如餐饮、住宿、购物、提款、保险等服务；3）工商、税务、海关的服务6、延伸延伸功能功能货物调剂中心、系统技术设计、咨询培训服务等第10页/共93页第二节第二节 物流节点选址概述物流节点选址概述I.选址决策内容设施数量、规模和位置供货点、存储点指派仓储设施自营还是外租 设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。方法第11页/共93页II.II.选址决策的影响因素选址决策的影响因素外部影响因素外部影响因素 宏观政治、经济因素 基础设施及环境 竞争对手内部影响因素内

10、部影响因素 企业发展战略、服务水平、商品特性等方法第二节 物流节点选址概述第12页/共93页13III.III. 选址模型的分类选址模型的分类选址的对象选址的区域选址的目标约束条件选址考虑的问题第二节 物流节点选址概述第13页/共93页14III.III. 选址模型的分类选址模型的分类1 根据被定位设施的维度及数量l根据设施的维数l根据设施选址的数量体选址：定位三维物体面选址：定位二维物体线选址：定位一维物体点选址：定位零维物体单一设施选址：主要考虑运输成本多设施选址：需要考虑设施间需求分配、设施成本与数量间的关系第二节 物流节点选址概述第14页/共93页152 根据选址问题目标区域的特征连续

11、选址：待选区域是一个平面，不考虑其他结构，可能的选址位置数量无限。如企业配送中心的初步选址网格选址：待选区域是一个平面，被细分成许多相等面积的区域，候选地址的数量是有限的，但数量也很大。如：仓库中不同存储位置的分配离散选址：目标选址区域是一个离散的候选位置的集合。候选位置数量有限且较少。如：企业配送中心的详细选址设计第二节 物流节点选址概述第15页/共93页163 根据选址成本4 选址约束可行成本方案/最优成本方案Minisum / Minimax目标函数：Minisum是寻求设施选址总成本最小（中值问题）；Minimax是优化已存在设施的单个最大成本组分（中心问题）Maxmin目标函数是最优

12、化已存在设施的最小成本组分（反中心问题）固定权重/可变权重（单纯选址问题/选址 分配问题）：新设施与已存在设施的关系（权重）与新设施的位置无关/有关。有能力约束/无能力约束不可行区域约束067反中心点=2.5中心点=3.5中值=5.55第二节 物流节点选址概述第16页/共93页17一般采用两种方法计算节点之间的距离：直线距离（欧几里得距离）；折线距离（城市距离）IV.选址问题中的距离计算第二节 物流节点选址概述第17页/共93页18Rijijijdxxyy22()()Rijijijdxxyy1 直线距离常用于城市间配送问题和通信问题城市间配送问题的实际路线距离受到城市道路的约束，可以将两点间的

13、直线距离乘以一个适当的系数来近似。美国大陆是1.2，东南美洲是1.26，刘飞（2009）使用1.41。2 折线距离一般用于道路较规则的城市内的配送问题、直线通道的工厂及仓库内的布置、物料搬运设备的顺序移动第二节 物流节点选址概述第18页/共93页u连续选址模型 待选区域是一个平面，不考虑其他结构 可能的选址位置的数量是无限的一、交叉中值模型交叉中值模型（Cross Median）用来解决连续点选址问题，利用城市距离进行计算。通过交叉中值方法对单一选址问题在一个平面上的加权城市距离进行最小化。第三节 选址模型2021年11月15日星期一全国网点布局石家庄网点布局槐安路中华大街新华路西二环第19页

14、/共93页20申通快递服务网点选址城市内、单一设施点、连续选址问题交叉中值模型A(3,1);1B(5,2);7C(4,3);3D(2,4);3E(1,5);6123456第20页/共93页21 一维简单选址：在一街道上，选择一个快递网点，使得服务街道上所有顾客的总距离最短。01xs一交叉中值模型不考虑其他因素（住宅区的位置、权重）时选址位置：路线的中点假定住宅小区的居民需求在这条街道上均匀分布1.基本原理第21页/共93页223504()()isiiisiiw xxw xx51miniisiZw xx考虑权重因素x1w1x2w2x3w3x4w4x5w501xs选址位置：路线的权重中心中值350

15、4=iiiiww最优解：一一交叉中值模型交叉中值模型第22页/共93页235151miniiiiisisZw xw yyx (x1y1)w1(x3y3)w3(x2y2)w2(x4y4)w4(xsys)(x5y5)w5X轴中值Y轴中值 二维（面）选址：在一定区域内设置一个快递网点，使服务所有顾客的总距离最短。一交叉中值模型第23页/共93页242021年11月15日星期一11371 36 / 2102niiWw kmxs43kmys31、计算权重中值：2、寻找X轴的中值：（见图）3、寻找Y轴的中值：（见图）4、确定交叉中值，获得可能方案：（见图）一交叉中值模型2.模型应用申通快递网点的选址演示表

16、第24页/共93页251234560A(3,1);1B(5,2);7C(4,3);3D(2,4);3E(1,5);6123456XY3 4sxkm3 4sxkm3 4sxkm6iw 9iw 10iw 10iw X轴中值从左到右从右到左257iw 10iw 返回第25页/共93页261234560A(3,1);1B(5,2);7C(4,3);3D(2,4);3E(1,5);6123456XY11iw3 4sykm3sykm2 3sykm8iw Y轴中值从上到下从下到上12iw9iw 返回第26页/共93页27kmxs43kmys3kmxs432 3sykm3sxkmkmys3A(3,1);1B(

17、5,2);7C(4,3);3D(2,4);3E(1,5);6123456123456MS可能方案可行方案线段 MC区域 S点 M交叉中值第27页/共93页282021年11月15日星期一需求点沿X轴的位置从左到右E166D239A3110C4313B57从右到左B577C4310A3111D23E16iwiw表1：X轴方向中值计算ix3 4sxkm3 4sxkm第28页/共93页292021年11月15日星期一需求点沿Y轴的位置从上到下E566D439C3312B27A11从下到上A111B278C3311D43E56iwiw表2：Y轴方向中值计算iy回3 4sykm2 3sykm第29页/共

18、93页30l交叉中值模型（实例）M（3,3）C（4,3）需求点权重距离总和需求点权重距离总和112211332732127214331333004326433956424565305656一一交叉中值模型交叉中值模型第30页/共93页31 前面介绍的交叉中值模型由于其本身的局限性，只适合于解决一些小范围的城市内选址问题。精确重心法在评价的过程中使用的是直线距离，使得选址问题变得复杂，但是有着更为广阔的应用范围。 选址实例：TCL公司希望筹建一个北方地区配送中心，为所有北方地区顾客提供服务。二、精确重心法二、精确重心法城市间、单一设施、连续选址问题精确重心法第31页/共93页32 在使用了直线距

19、离后，目标函数变成了：221min()()niisisiZxxyy二二精确重心法精确重心法 分别对xs和ys进行求偏微分，并且令其为零，这样就可以得到两个微分等式。应用这两个等式分别对xs和ys进行求解，即可以求出下面的一对隐含有最优解的等式：(x1y1)w1(x3y3)w3(x2y2)w2(x4y4)w4(xsys)1. 基本原理第32页/共93页332021年11月15日星期一 该微分方程组不能直接求解，使用迭代方法求解。niisiniisiisdwdxwx11niisiniisiisdwdywy1122isisisdxxyy其中，迭代法步骤：1）初始值设定2）迭代3）中止准则第33页/共

20、93页342021年11月15日星期一101101niiisniiniiisniiw xxww yyw1）初始值xs0和ys0 的确定：a. 任意选择一个点作为初始值；b. 按照下面的简化公式选址初始值。二精确重心法第34页/共93页352021年11月15日星期一1(1)( )1(1)1(1)( )1(1)niiiis is iniiis iniiiis is iniiis iw xdxwdw ydywd2）迭代迭代公式二精确重心法22(1)(1)(1)is iis iis idxxyy其中，第35页/共93页362021年11月15日星期一如果该迭代过程具有收敛性，那么经过无限次的迭代之后

21、，可以得到一个最优解xs*和ys*。但是在实际中，可以迭代的次数是有限的，所以在迭代过程中需要确定一个中止准则。中止准则的设置：a.根据经验，直接设置一个确定的迭代次数N；二精确重心法3）中止准则第36页/共93页372021年11月15日星期一b.判断两次迭代结果的差值是否小于设定的阈值； 1( )()limss is isitxxxx 1( )()limss is isityyyy 二精确重心法3）中止准则c. 判断总距离是否减少或者两次迭代差值小于设定值。1222( )( )1( )niis iis iiZ iwxxyylim( )(1)( )( )(1)itZ iZ iZ iZ iZ

22、iZ 或者 第37页/共93页382021年11月15日星期一选址实例：选址实例：假设这个住宅聚集区街道建设尚未完成，住宅聚集区内大多是空地和纵横交错的小街道，可以使用直线距离对距离加以计算。使用精确重心法选择一个最优的位置作为快递收发网点。 从M点（3，3）（即：xsi0=3和ysi0 =3）开始进行直线最优的搜索，下表进行了一些必要的计算。2. 模型应用二精确重心法第38页/共93页精确重心法第一次迭代初始位置(xs0,ys0)33需求点ABCDE(xi,yi)3152432415权重wi17336距离dis(0)22.23611.4142.828wixi/dis(0)；wiyi/dis(

23、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第39页/共93页第二次迭代(xs1,ys1)3.26613.205需求点12345(xi,yi)3152432415权重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

24、(1)0.4503.3153.9382.0072.075迭代位置(x2,y2)3.3743.165中止判断（Z2）41.118第40页/共93页精确重心法第三次迭代(xs2,ys2)3.3743.165需求点12345(xi,yi)3152432415权重wi17336距离dis(2)2.19720.6471.6083.001wixi/dis(2)；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中止判断

25、（Z3）40.9672021年11月15日星期一第41页/共93页中止准则的使用。若（1）N=2；（2）坐标值阈值为0.2；坐标值变化幅度小于4%；（3）总费用阈值为0.2；总费用相对变化幅度小于1%。迭代次数坐标点坐标点迭代差值总距离总距离迭代差值xy绝对差值相对差值41.866绝对值相对值13.2663.2050.266， 0.2058.88%，6.85%41.1180.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%第

26、42页/共93页补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用重心法为配送中心选址。零售点物资需求量qi运输费用ri坐标xiyi1252223511332.5510841549第一步，按照简化公式确定初始值9 .415 .2329185 .23322)0(8 .715 .23241105 .211322)0(11111111niiiniiiiniiniiisniiiniiiiniiniiisrqyrqwywyrqxrqwxwx第43页/共93页精确重心法第二步，以点（7.8，4.9）作为配送中心，计算距离与总费用，迭代确定配送中心1 . 56 . 5/18 . 3/5 .

27、 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()108 . 7()0(7 . 3)39 . 4()118 . 7()0(5 . 6)29 . 4()28 . 7()0(2/12242/12232

28、/12222/1221ssssdddd1965)6 . 518 . 35 . 27 . 335 . 62()0(Z第44页/共93页精确重心法第三步，以点（8.6，5.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/22) 1 () 1 ()2(41414141iisiiisiisiisiii

29、siisdwdywydwdxwx6)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第45页/共93页第四步，以点（9.0，5.2）作为配送中心，计算距离与总费用此时，Z(2)=Z(1)=191，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（9.0，5.2）或（8.6，5.1）。3 . 6)92

30、 . 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 用精确重心法得到的最优解只有一个点，而不会是一条线段或者一个区域。而且只有在十分偶然的情况下，才会出现用交叉中值法和精确重心法得到的最优优地址一致的情况。第46页/共93页连续选址模型连续选址模型交叉中值模型与精确重心法 城市距离（折线距离）； 适合于小范围的城

31、市内选址问题； 目标使对加权的城市距离最小化； 属于单一设施连续点选址问题。 欧几米德距离（直线距离）； 适合于大范围城市间选址问题； 目标是使加权的直线距离最小化； 属于单一设施的连续点选址问题。2021年11月15日星期一第47页/共93页48u离散选址模型 在有限的候选位置里面，选取最合适的一个或者一组位置为最优方案 候选方案只有有限个元素，只需要分析这几个有限的位置V.V.选址模型选址模型 例：北国超市计划在裕华区选址设置超级市场，通过初选，满足超市选址要求的备选点共计10处，裕华区的各住宅小区位置及权重已知。 请问：北国超市如何决策最终的选址方案？第48页/共93页49V.V.选址模

32、型选址模型ABCDEFGHIJ目前主要有两种模型：覆盖模型、P中值模型。第49页/共93页50三覆盖模型对于需求已知的一些需求点，如何确定一组服务设施来满足它们的需求。在模型中，需要确定服务设施的最小数量和合适位置。n适用范围：商业物流系统，如零售点的选址问题、加油站的选址、配送中心的选址等；公用事业系统，如急救中心、消防中心等。计算机与通信系统，有线电视网的基站、无线通信网络基站等。 V.V.选址模型选址模型第50页/共93页51根据解决问题的方法不同，分为两种不同的主要模型：1、集合覆盖模型：用最小数量的设施去覆盖所有的需求点2、最大覆盖模型：在给定数量的设施下，覆盖尽可能多的需求点。 两

33、类模型的区别：集合覆盖模型要满足所有的需求点，而最大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取决于服务设施的资源充足与否。三三覆盖模型覆盖模型第51页/共93页第52页/共93页1、集合覆盖模型 目标：用尽可能少的设施去覆盖所有的需求点。数学模型为：( )( )min1,. .0,1,0, ,jj Nijj B iiijjji A jjijxyiNd yC xjNstxiNyi jN第53页/共93页542021年11月15日星期一1、集合覆盖模型 Njjxmin)(1iBjijN，iy)(,jAijjijiNjxCydNixj,1 , 0Njiyij, 0最小化设施的数目保证每个需求

34、点的需求得到完全的满足是对每个提供服务的服务网点的服务能力的限制保证一个地方最多只能投建一个设施允许一个设施只提供部分的需求第54页/共93页552021年11月15日星期一 对于此类带有约束条件的极值问题，有两大类方法：一是应用分枝定界的方法，由于运算量方面的限制，一般也只适用于小规模问题的求解；二是启发式方法，所得到的结果不能保证是最优解，但是可以保证是可行解，可以对大型问题进行有效的分析、求解。 第55页/共93页562021年11月15日星期一 例子：例子：乡村医疗诊所选址问题 卫生部门考虑到农村地区的医疗条件的落后和匮乏，计划在某一地区的9个村增加一系列诊所，以改善该地区的医疗卫生水

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

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

37、, 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1,1 , 01111111110. .min9998898887787774686765646355545347454443413534333231232221141312116987654321jiyjxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyxtsxxxxxxxxxzijj9998989888786878777674768676564636565554535474645444341436353433323132322212141312111999999999. .xyyxyyyyxyyyyxyyyyyx

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

39、选址，为尽可能多的对象提供服务。目标函数是： 约束条件为： )(maxjAiijiNjyd)(1iBjijN，iy)( jAijjijiN，jxCydNjjpxN，j，xj10Njiyij, 0最大可能地对需求提供服务需求的限制，服务不可能大于当前需求的总和设施的服务能力的限制问题本身的限制，也就是说最多可能投建设设施的数目保证一个地方最多只能投建一个设施允许一个设施只提供部分的需求第62页/共93页2021年11月15日星期一 医疗站问题，如果仍旧不考虑其服务能力的限制，最多诊所数目为2，用最大覆盖模型进行分析，用贪婪算法进行求解。该算法是以空集合作为原始解集合，然后在剩下的所有候选点中，选

40、择一个具有最大满足能力的候选点加入到现在的解集合中，如此往复，直到达到设施数量限制或全部需求都得以满足。632、最大覆盖模型第63页/共93页集合覆盖模型与最大覆盖模型数学模型比较 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集合覆盖模型最大覆盖模型第64页/共93页整数规划模型最大覆盖模型整数规划1111111110. .min999889888778777468676

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

42、, 1,1 , 0999999999. .9998989888786878777674768676564636565554535474645444341436353433323132322212141312111jiyjxxyyxyyyyxyyyyxyyyyyxyyyyxyyyyyyxyyyyyyxyyyxyyyytsijj第65页/共93页2021年11月15日星期一 思考题：一个快递企业准备在某县的农村地区建设一批快递收发网点。该地区的村落坐落情况和相对距离如图所示。快递企业需要为任意一村服务的距离在20min以内，需要设置几个服务网点，它们的位置又在哪里？66三、覆盖模型12347562

43、5152035152020201520第66页/共93页672021年11月15日星期一 P-中值模型是指在一个给定数量和位置的需求集合和一个候选设施位置的集合下，分别为p个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在工厂和需求点之间的运输费用最低。四、P-中值模型需求点（N）设施点（M）p=3一般适用于工厂或仓库的选址问题第67页/共93页682021年11月15日星期一 实例：实例：某饮料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地考查之后，确定了

44、4个候选地址。从候选地址到不同超市的单位产品运输成本、各个超市的需求量都已经确定，如图和表所示。四、P-中值模型第68页/共93页69候选地点 j需求di12341412206100221025105033416141204649280518127320061424970720302116082412622100123456781234运费cijP-中值模型需要解决的问题：超市i（1）选择合适设施位置（ ）（2）指派客户到相应的设施中去（ ）ijyjx第69页/共93页702021年11月15日星期一 P-P-中值模型的数学表达式中值模型的数学表达式ijc10jx10ijyN第i个需求点的需求

45、量建设设施id不建设设施从需求点i到设施点j的单位运输费用需求点i不由设施点j提供服务需求点i由设施点j提供服务需求点数量M备选设施点数量未知变量第70页/共93页712021年11月15日星期一 P-P-中值模型的数学表达式中值模型的数学表达式MjijijiNiycdminMjijN，iy1Mjjpx,ijjyx iN jMM，j，xj10MjNiyij,1 , 0目标函数每个客户（需求点）只有一个设施来提供服务限制总设施数为p保证没有设施的地点不会有客户对应目标函数：约束条件：第71页/共93页72lP-中值模型（实例）贪婪取走启发算法贪婪加入启发算法基本步骤： （1）第一步，初始化，令循

46、环参数k=M，将所有的M个候选位置都选中，然后将每个客户指派给离其距离最近的一个候选位置 ；超市候选地点需求12341412206100221025105033416141204649280518127320061424970720302116082412622100四、P-中值模型123456781234400100360600160140120600设施点费用1860214037204760总费用2480第72页/共93页73（2）第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令 k=k-1；四、P-中值模型P中值模型贪婪取走启发式算

47、法需求点移走位置1后费用增加量1+2002+4003+120总费用增加量+720移走位置1：超市候选地点需求1234141220610022102510503341614120464928051812732006142497072030211608241262210012345678234600160140120600600500480第73页/共93页P中值模型贪婪取走启发式算法需求点移走位置2后费用增加量6+140总费用增加量+140移走位置2：超市候选地点需求12341412206100221025105033416141204649280518127320061424970720302

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

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

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