版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第15章选址问题第15章选址问题115.1概述选址理论:是关于选址问题模型和算法的理论。选址在整个物流系统中占有非常重要的地位,主要属于物流管理战略层的研究问题。选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点,如制造商、供应商、仓库、配送中心、零售网点等。15.1概述选址理论:是关于选址问题模型21、选址问题设计算法和模型时要考虑:(1)被定位的对象具有什么特性(2)目标选址地区的结构特点是什么(3)目标和成本参数是什么(4)其他限制条件是什么1、选址问题设计算法和模型时要考虑:32、选址问题的分类(1)按被定位的对象的空间维数分为:立体选址、平面选址、线选址、点选址。
立体选址:集装箱装箱问题平面选址:工厂或货运站的设施布局线选址:巷道内划出拣选带点选址:制造或配送系统的选址2、选址问题的分类4(2)按照目标区域的结构来划分:连续选址、网格选址、网络选址和离散点选址。连续选址:候选区域是一个平面或球面,任意点都可作为选址点。网格选址:目标区域被划分成多个单元,要求为对象分配其中若干单元。网络选址:目标选址区是一个网络,即节点和边的集合。离散点选址:候选点数量有限且较少。(2)按照目标区域的结构来划分:连续选址、网格选址、网络选址5(3)从目标函数来分类:中位问题、中心问题,反中心问题中位问题:总成本最小为目标。中心问题:服务于每个客户的最大成本最小化为目标。反中心问题:服务于每个客户的最小成本最大化为目标。(3)从目标函数来分类:中位问题、中心问题,反中心问题60567中位点中心点3.5反中心点2.50567中位点中心点3.5反中心点2.57(4)根据问题中的参数是否与解存在关联:纯选址问题和选址分配问题。纯选址问题:其中的参数或结构不依赖新建设施而改变,是事先确定的。选址分配问题:其中的参数或结构依赖新建设施而改变。(5)根据问题中的参数是否随时间而改变,分为静态选址和动态选址。(6)根据参数是确定性的还是随机性的,分为确定性选址问题和随机选址问题。(7)根据候选点是否存在服务能力约束,可以分为无限能力选址和有限能力选址。(4)根据问题中的参数是否与解存在关联:纯选址问题和选址分配815.2连续点选址问题连续点选址问题中,点到点的距离计算标准有两种。设平面上的点坐标分别为(xi,yi),(xj,yj)直线距离dijE:折线距离dijR:yxij15.2连续点选址问题连续点选址问题中,点91、直线距离准则下的选址用直线距离准则进行选址,则目标函数为:1、直线距离准则下的选址用直线距离准则进行选102、折线距离准则下的选址重心法,用于以总和最小为目标函数的单一设施选址问题。此时目标函数为:2、折线距离准则下的选址重心法,用于以总和最11可见,原问题可以被拆成两个独立的问题,即:可见,原问题可以被拆成两个独立的问题,即:12例1:报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报刊零售点,主要的服务对象为附近的五个居民小区。表中数字分别为各个小区的x坐标和y坐标,以及需求量。小区x坐标y坐标需求量wiA311B527C433D243E156例1:报刊亭选址。有一个报刊连锁公司想在一个地区设一个新的报13用坐标图来表示五个小区的位置小区x坐标y坐标需求量wiA311B527C433D243E156xy0123455432112345用坐标图来表示五个小区的位置小区x坐标y坐标需求量wiA3114解:先求x坐标的解(1)按坐标从小到大的顺序排列需求点(2)计算总权重(需求量)W,计算累积权重(需求量)(3)找满足累积需求量
计算编号小区名称x坐标累积需求量1E12D23A34C45B569101320由计算结果可知计算编号s=3解:先求x坐标的解计算编号小区名称x坐标累积需求量1E12D15若,则选址的x坐标即为对应的需求点s的x坐标。若,则选址的x坐标即为对应原需求点s和需求点s+1的x坐标范围内任一点。所以,本题选址点的x坐标是编号为3和编号为4的需求点的x坐标之间的任意值,即为[3,4]之间的任意值。再求解y坐标的解。若,则选址的16(1)按坐标从小到大的顺序排列需求点(2)计算总权重(需求量)W,计算累积权重(需求量)计算编号小区名称y坐标累积需求量1A12B23C34D45E518111420(3)y坐标为编号为3的需求点对应的y坐标,即y坐标为3。(1)按坐标从小到大的顺序排列需求点计算编号小区名称y坐标累17x坐标为[3,4]之间的任意值,y坐标为3,说明新的报刊零售点的位置可以是PQ线段上的任意一点。xy0123455432112345PQx坐标为[3,4]之间的任意值,y坐标为3,说明新的报刊零售1815.3离散点选址问题离散点选址指的是在有限的候选位置里,选取最为合适的一个或者一组位置为最优方案,相应的模型称为离散点选址模型。离散点选址问题,目前主要有两种模型可供选择,分别是覆盖模型和k中位模型。其中覆盖模型常用的是集合覆盖模型和最大覆盖模型。覆盖模型,是对于需求已知的一些需求点,如何确定一组服务设施来满足这些需求点的需求。在这个模型中,需要确定服务设施的最小数量和合适位置。15.3离散点选址问题离散点选址指的是在有19覆盖模型适用于商业物流系统,如零售点的选址,加油站的选址、配送中心的选址等,公用事业系统,如急救中心、消防中心等,以及计算机与通信系统。集合覆盖模型:用最小数量的设施去覆盖所有的需求点。覆盖模型适用于商业物流系统,如零售点的选址,20最大覆盖模型:在给定数量的设施下,覆盖尽可能多的需求点。最大覆盖模型:在给定数量的设施下,覆盖尽可能21集合覆盖模型:定义:xi——需求点cj——覆盖成本sj——覆盖集合子集,取1时表示该子集启用,取0时表示该子集未启用。A——覆盖关系矩阵aij——覆盖关系矩阵中的元素,取1时表示集合sj可以把需求点xi覆盖进去,取0时表示集合sj不可以把需求点xi覆盖进去。数学模型:目标函数:约束条件:aij和sj为0,1变量。集合覆盖模型:数学模型:约束条件:aij和sj为0,1变量。22矩阵简化法求解第一步:若A中行i只有一个非0元素,例如aij,则记J={j},即sj在最优解中。对A删除列j以及该列中aij=1的行。第二步:若A中存在行i和i’,若对所有列有aij≥ai’j,则删除行i。第三步:若A中存在列j和j’,若对所有行有aij≤aij’,则删除列j。第四步:反复进行前三步,直至矩阵A中不再包含任何元素,或不存在行或列可以删除。矩阵简化法求解23例2:有7个航线需要安排乘务员,有五组乘务组可选,请尽量安排最小的乘务组,且保证每条航线都至少有一个乘务组服务。乘务组航线s1s2s3s4s5x110110x210010x311010x401110x510001x600100x701010例2:有7个航线需要安排乘务员,有五组乘务组可选,请尽量安排24解:(1)在矩阵A中找出行中只有一个非0元素的行。x1x2x3x4x5x6x7s1s2s3s4s5记J={s3}(2)删除行x3,因为x3包含x2。(3)删除列s5,因为s1包含s5。删除列s2,因为s4包含s2。x2x3x5x7s1s2s4s5x2x5x7s1s4
(4)记J={s3,s1}(5)记J={s3,s1,s4}解:(1)在矩阵A中找出行中只有一个非0元素的行。x1s125例3:某物流企业要建设一些配送中心,为九个城市的客户服务,配送中心最远的服务距离为300km,即任何一个城市的周边300km处至少有一个配送中心。不考虑配送中心的服务能力,物流企业要确定需要多少个配送中心以及这些配送中心的位置。其中第6个城市由于缺乏建立配送中心的必要条件,不可以建立配送中心。图表示各个城市的相对位置和距离。240013456789200300200100350300250150150300400300200300例3:某物流企业要建设一些配送中心,为九个城市的客户服务,配26解:第一步是要建立覆盖矩阵。240013456789200300200100350300250150150300400300200300s1s2s3s4s5s7s8s9c11c21c31c41c51c6c71c81c911110100001000000111100001011110000111000000101100000011100000001解:第一步是要建立覆盖矩阵。240013456789200327第二步进行计算。(1)找出行中只有一个非0元素的行。(2)简化矩阵第二步进行计算。28简化矩阵后得记J={s3}记J={s3,s8}简化矩阵后得记J={s3}记J={s3,s8}29k中位模型:设在某一地区要建立若干的配送中心,给其客户配送商品,配送中心有N个候选地址。现要求设立的配送中心到所有客户的总运输成本最小。k中位模型:30例4:某公司准备在8个客户的附近建立2个仓库,用最低的运输成本来满足客户的需求。现计划从4个候选地址选择2个地方建立仓库。从候选地址到不同的仓库的运输成本、各个超市的需求量都已确定,如表所示:p1p2p3p4需求量x1412206100x2210251050x3341614120x4659280x5181273200x61424970x7203021160x82412622100例4:某公司准备在8个客户的附近建立2个仓库,用最低的运输成31用贪婪取走启发式算法:第一步:初始化,令循环参数k=m,将所有的m个候选位置全选中,然后将每个客户指派给离其距离最近的一个候选位置。123456781423400100360160600140120600总成本费用为:2480用贪婪取走启发式算法:123456781423400100332第二步:选择并取走一个位置点,满足以下条件:取走它并将客户重新指派后,总费用增加量最小,然后令k=k-1。第三步:重复第二步,直到k=2。123600500480456781423160600140120600取走1后,总费用为3200,增加720。第二步:选择并取走一个位置点,满足以下条件:取走它并将客户重33取走2后,总费用为2620,增加140。628012345781423400100360160600120600取走2后,总费用为2620,增加140。628012345734取走3后,总费用为3620,增加1140。1234561423400100360160600140786601200取走3后,总费用为3620,增加1140。12345614235取走4后,总费用为3520,增加1040。4540014007812361423400100360140120
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 销售业务员个人年终工作总结
- 晚会年会闭幕词模板(3篇)
- 规章制度学习心得范文
- 数学评课稿范文(34篇)
- 幼儿园卫生保健工作总结14篇
- 解除安装合同协议书(3篇)
- 新教材高考地理二轮复习三10个长效热点综合专项训练热点6“一带一路”建设含答案
- 湖北省荆州市石首市2024-2025学年五年级上学期11月期中道德与法治试题
- 广东省云浮市第一中学2024-2025学年七年级上学期11月期中生物学试题(含答案)
- 北京市2024-2025学年高三上学期期中物理试题(含答案)
- 第5课《食物中的营养》教学设计(教科版小学四年级上册科学第一单元)
- 抗炎免疫药物的研究进展课件
- 辩论赛教案(Word)
- 金属材料试样制作规范
- 统编语文一上《江南》课例点评
- 《一元二次方程》(复习课)说课稿
- 律师事务所金融业务部法律服务方案
- 施工人员计划配置表(共1页)
- 装修工程施工进度计划表excel模板
- 宿舍管理流程图
- 骨科复试问答题
评论
0/150
提交评论