（系统工程专业论文）物流配送选址优化模型的研究.pdf

摘要 物流系统平台中的选址问题可以抽象为以下四类：配送中心选址、仓 库选址、订单出库选址和货物配送路径选址，这四种选址问题在交通、运 输、仓储和工业探测等行业得到了广泛的应用。近年来物流选址问题是国 内外研究的一个热点，本文在将四大选址问题分类的基础上，主要研究配 送中心的选址模型并对其优化算法进行求解分析与实现。因为配送中心选 址在物流选址问题中占有重要的地位。配送中心选址的合理化可以大大降 低企业的运营总成本，其中包括运输费、建设费和可变费用等，其研究意 义重大。本文的具体研究内容如下： 首先，提出选址问题，所谓的选址问题就是关于为需要设置的“设施” 选择最优位置的问题。并把物流系统中的问题抽象为选址问题进行分析研 究，主要包括对配送中心选址的影响因素分析以及常用的选址方法研究。 其次，针对这种抽象提出了一种全面通用的目标函数模型，在众多的 建模方法中，由于层次分析法( a h p ) 建模方法是一种利用专家经验将定 性的综合判断转化为具体的定量判定的方法，同时具有定性分析和定量分 析的能力，所以考虑到物流系统的复杂性以及配送中心选址影响因素的多 样性，本文选用a h p 建模方法进行物流选址问题的假设、建模和检验。 同时详细介绍了a h p 建模方法的实现思想。 最后，结合物流系统的特点和所建模型的特性，选择了两种有效的优 化算法，即模拟退火算法和遗传算法，并对它们的实现思想分别进行了介 绍。同时根据每种优化算法的实现思想不同，对它们进行分析比较，给出 了它们在解的特性、初始解、约束条件、收敛速度等因素下的比较表。考 虑到遗传算法在解决问题中的某些不足，提出了它与模拟退火相结合的算 法，并对选址模型分别用遗传算法和模拟退火遗传混合算法实现，且给出 了相应的实验数据和算法思想以作比较。 通过一定的研究，结合理论分析得出结论，结果表明运用a h p 建模 方法大大简化了物流系统的选址问题，具有很大的适用性。同时模拟退火 遗传混合优化算法也得到了较好的应用，取得了应有的效果。 关键字：配送中心，选址问题，层次分析法，模拟退火算法，遗传算法 a b s t r a c t t h i sp a p e rr e g a r d st h ef o u rl o c a t i o np r o b l e m s ，s u c ha sd i s t r i b u t i n gc e n t e r w a r e h o u s e ，f e t c h i n gc a r g o e sa n dc a r g o e sd i s t r i b u t i n gr o u t i n g ，a sa na b s t r a c t p r o b l e m t h i s f o u rl o c a t i o n p r o b l e m s a r e w i d e l ya p p l i e d i n t r a f f i c ， t r a n s p o r t a t i o n ，s t o r a g e ，i n d u s t r ye x p l o r ea n de t c i nr e c e n ty e a r s ，l o c a t i o n p r o b l e m si nl o g i s t i c sa r eah o tt o p i ci nt h ew o r l d b a s e do nt h ec l a s s i f i c a t i o n o ff o u rl o c a t i o np r o b l e m s ，t h i sp a p e rm a i n l yd r a w so u td i s t r i b u t i n gc e n t e r m o d e l so fl o c a t i o np r o b l e m sf r o mt h et h e o r y a n a l y s e sa n di m p l e m e n t si t s p r o p e ro p t i m a la l g o r i t h m b e c a u s ed i s t r i b u t i n g c e n t e rl o c a t i o n p l a c e s a n i m p o r t a n tp a r ta m o n gt h el o g i s t i cl o c a t i o np r o b l e m i t sr e a s o n a b i l i t yw i l l g r e a t l yr e d u c ee n t e r p r i s e sc o s t s ，i n c l u d i n gt r a n s p o r tc o s t 、b u i l d i n gc o s ta n d s o m ev a r i a t i o nc o s t o b v i o u s l yt h er e s e a r c hi s s i g n i f i c a n t t h es p e c i f i c c o n t e n t sa sf o l l o w i n g s ： f i r s t l y , t h i sp a p e rg i v e so u tl o c a t i o np r o b l e m t h el o c a t i o np r o b l e mi s a b o u ts e l e c t i n gt h eo p t i m a ll o c a t i o n sf o rt h eb u i l d i n gf a c i l i t i e s a n dd r a w i n g t h e mo u tl o c a t i o np r o b l e m sw i l ls o l v et h ep r o b l e m si nl o g i s t i cs y s t e m m a i n l y s o m ei n f l u e n c ef a c t o r st od i s t r i b u t i n gc e n t e rl o c a t i o na r ea n a l y z e da n ds o m e u s u a ll o c a t i o nm e t h o d sa r er e s e a r c h e d s e c o n d l y ，ac o m p r e h e n s i v ea n du n i v e r s a lf u n c t i o nm o d e li sp r o v i d e d b a s e do i la b o v ea b s t r a c t i nm a n ym o d e l i n gm e t h o d s ，o n l ya h ph a sb o t h q u a n t i t ya n a l y s i s a n dq u a l i t a t i v ea n a l y s i s c o n s i d e r i n gt h ec o m p l e x e so f l o g i s t i cs y s t e ma n dt h ed i v e r s eo fi n f l u e n c ef a c t o r s ，t h i sp a p e rc h o o s e sa h p t o h y p o t h e s i s ，m o d e la n dc h e c ki nl o g i s t i cl o c a t i o np r o b l e m m e a n w h i l ei t a l s o i n t r o d u c e sa h p si d e ai nd e t a i l f i n a l l y ，r e s u l t i n gi nt h ec h a r a c t e r so ft h el o g i s t i cs y s t e ma n dt h em o d e l ， t w ov a l i do p t i m a la l g o r i t h m sa r es e l e c t e d t h e ya r es t i m u l a t i n ga n n e a l i n g a l g o r i t h ma n dg e n e t i ca l g o r i t h m b ya n a l y z i n ga n dc o m p a r i n g t h e i ri d e a s ，o n e t a b l ei sl i s t e dw i t ht h ef a c t o r s ，s u c ha st h ep r o p e r t yo fr e s u l t s ，i n i t i a lv a l u e s ， r e s t r i c tc o n d i t i o n sa n dt h es p e e do fc o n v e r g e n c e 。c o n s i d e r i n gs o m ed e f i c i e n c y j i o fg aw h e ns o l v i n gs u c hp r o b l e m s ，an e wa l g o r i t h m s t i m u l a t i n g a n n e a l i n g m e r g e dw i t hg ai sp u tf o r w a r d a n dii m p l e m e n tt h el o c a t i o nm o d e lw i t h g e n e t i ca l g o r i t h ma n ds t i m u l a t i o na n n e a l i n gm e r g e dw i t hg a t h e nlg i v eo u t s o m ee x p e r i m e n td a t aa n dt h ei d e a so ft h ea l g o r i t h m s a f t e rs o m es t u d ya n dw i t ht h ef o r m e rt h e o r ya n a l y s i s ，t h ee x p e c t e dr e s u l t i sa c q u i r e d i tg r e a t l ys i m p l i f i e st h el o c a t i o np r o b l e mo fl o g i s t i cs y s t e m t h i s v e r i f i e di t sa p p l i c a b i l i t yi nt h i sf i e l d a tt h es a m et i m et h es t i m u l a t i n g a n n e a l i n gm e r g e dw i t hg ao p t i m a la l g o r i t h m si su s e db e t t e r k e yw o r d s ：d i s t r i b u t i o nc e n t e r , l o c a t i o np r o b l e m s ，a n a l y t i ch i e r a r c h y p r o c e s s ( a h p ) ，s t i m u l a t i n g a n n e a l i n ga l g o r i t h m ( s a ) ，g e n e t i ca l g o r i t h m ( g a ) 1 1 1 武汉理工大学硕士学位论文 第一章绪论 1 1 选题的目的、意义及国内外研究现状 1 1 1 选题的目的、意义 物流是指为满足顾客服务水平需要，为追求整体系统的有效性和总体 成本最小化，由供应商、制造商、配送中心、零售商等利用由各种现代化 技术协调控制下的原材料，在制品和成品、起始点和消费点之间，有计划 的流动和存储及其相关的经济和信息活动。一个完整的物流系统是物资由 生产者到消费者的全过程，包括市场需求预测、合理产品组合、合理运输 方案、合理仓库布局以及库容最优确定等，这些环节相互有机配合、协调 致形成一个统一体。 特别是在日益全球化的今天，现代物流作为“第三个利润源泉”正受 到日益广泛的重视，并面临着前所未有的发展机遇。入世五年来，在中国 经济持续较快增长、对外开放更加扩大的背景下，中国物流进入加速发展 期，多种所有制、多种运作模式和多种服务方式的专业物流在中国快速成 长，从中央到地方政府都十分重视物流发展，都在极力营造有利于物流发 展的体制政策环境。而对于一个企业来说，物流是其生产的前提保证，所 以要使一个企业能够得到快速运转。必须拥有一个良好的物流系统，通过 合理配置，使企业最终以最少的生产投入获得利润最大化。物流系统是一 个庞大复杂的网络工程，是个多目标、多约束综合优化问题，要想对其实 现多目标优化关键在于各种f o - i 题的建模方法和实现优化的算法研究1 1 1 。 物流配送是物流活动中一个重要环节，也可以看作是物流过程的中转 型送货。在产品用户集中的区域，供应基地按照用户的订货要求和时间计 划，在物流中心配货，并将配好的货物采用汽车巡回运送方式送交收货人。 配送不是单纯的运输或送货，而是运输与其它活动的组合，即除了各种 “运”、“送”活动外，还要从事大量的集货、分货、配货、送货等工作， 是“配”与“送”的结合。物流配送中心在整个物流系统中起着承上启下 的作用，其目标是促进货物运输向组织化、综合化、现代化方向发展。物 武汉理工大学硕士学位论文 流配送中心的布局对其中心功能的发挥影响极大。 通过研究，如果能够解决物流系统中的选址问题，那么整个物流系统 将得到快速运转，相应的企业发展速度将得到提高，同时也促使了我国的 国民经济的运行方式和结构的优化。因此，寻找较好的建模方法，确定一 个实际有效的系统模型和相应的优化算法极其重要。在这方面虽然有许多 学者做了研究，但仍有些不足，还有待于继续研究。 本课题的研究对企业的更快发展起着举足重轻的作用，致力于使企业 以最小的投入获得最大的收入。 1 1 2 国内外的研究现状： 物流配送中心规划问题包括物流配送中心数量殴置决策与物流配送 中心选址规划。物流配送中心数量设置决策主要研究在给定的位置设置策 略与一定的物资运输量条件下，按照利润最大化、运营成本最低或者其他 条件，确定物流配送中心的设置数量。物流配送中心选址规划通常是在给 定物流配送中心数量的前提下，综合考虑各地运输物资数量、频度、交通 状况、运输成本等各种因素，决定在何地设置物流配送中心。按照系统中 物流配送中心设置的数量，可以将物流配送中心选址规划分为单物流配送 中心选址规划与多物流配送中心选址规划问题。物流配送中心数量设置决 策与物流配送中心选址规划是密切相关的，但是为了研究方便，目前的研 究往往假设给定物流配送中心选址规划计算物流配送中心数量，或者给定 数量，选择合理的配送位置。 在物流选址策略研究时，往往假定按照某种规则确定物流配送中心到 目的地物资运送路线，物流配送中心到目的地的路由是确定的，即不考虑 物理路线状态或者突发事件。在现实生活中，由于自然环境、人为因素等， 例如山体滑坡造成道路或桥梁的破坏，按照计划中的路由，无法以最低成 本或者最佳服务质量将物资运送到目的地，必须重新选择一条路径运送货 物。这就要求在建设配送中心时一定要考虑合适地点的选择，即物流配送 选址问题，物流配送选址优化问题是物流配送业务中优化决策问题之一。 合理选择配送中心对加快配送速度、提高服务质量以及降低成本均具有较 大作用。 由于物流配送中心选址问题是一项复杂的系统工程，考虑的因素众 2 武汉理t 大学硕士学位论文 多，在实际研究或应用中，考虑的侧重点不同，因而各种研究成果的条件 和方法都有较大差别，但是对于科学合理地规划我国各种类型的物流配送 中心而言，都有许多值得借鉴之处。在物流配送中心选址问题研究中，人 们往往将建设配送中心的费用、运输费用或者运输距离等作为目标函数， 忽略了运送服务质量与物流配送数量( 配送收入) 的关系。如何分析各个 指标的关系，建立合理的目标函数，对于物流配送中心选址是非常重要的。 国外对物流配送选址问题的研究已有6 0 余年的历史，对各种类型物 流配送中心的选址问题在理论和实践方面都取得了令人注目的成就，形成 了许多可行的模型和方法。归纳起来，这些配送中心选址方法可分为三类： ( 1 ) 应用连续型模型选择地点； ( 2 ) 应用离散型模型选择地点1 2 】； ( 3 ) 应用德尔菲( d e l p h i ) 专家咨询法选择地点。 第一类方法是以重心法为代表，认为物流中心的地点可以在平面上取 任意点，物流配送中心设置在重心点时，货物运送到各需求点的距离将最 短。该方法不限于对特定的备选点的选择，灵活性较大，特别是在单个物 流中心选址的应用中，已得到多数人的接受和认可。但是，由于这个地址 可能位于河流、建筑物或其他无法实现的地点，实际上找到的最优地址往 往难以实际实施。 第二类方法认为物流中心的各选地点是有限的几个场所，最合适的地 址只能按照预定的目标从有限个可行点中选取。代表性的方法有：整数或 混合整数规划法【3 1 、鲍姆尔一沃尔夫( b a u m o l w o i f e ) 法i “、库恩一汉姆布利 尔( h u e h n h a m b u r e e r ) 法、反町氏法、逐次逼近模型法1 5 等。a i k e n s 给出 了线性规划、0 1 整数规划、动态规划等九种基本形式的选址模型，目标 函数段是使总的选址费用最小，不同的规划形式主要取决于费用函数的形 式。t a n i g u c h i 采用双层规划求解了高速公路交叉口附近运输网络中公共物 流转运站点的选址，上层规划目标是运输车辆数量、选址费用最小，下层 规划考虑路网状况，遵循用户平衡条件对车辆进行平衡配送l ”。h o l m b e r g k 考虑了非线性运输费用的选址问题，并用分枝定界法进行了求解i ”。 f r a n c i s c ob 等用混合整数规划法建立了仓库选址模型，除考虑选址的固定 费用、运输费用外，还考虑了库存费用 s l 。各模型的共同点是以各费用之 和为目标函数，求使费用达到最小的解。如果基础数据完备，该类方法得 武汉理工大学硕士学位论文 出的解是较符合实际情况的。但由于这类方法所建立的模型多数己被证明 为n p l 9 j ( n o n d e t e r m i n i s t i cp o l y n o m i a l ，即非确定型多项式算法) 难题，不宜 用线性模型来处理，因此计算工作量很大，而且需要的基础资料也很多。 第三类方法的中心思路则是将专家凭经验、专业知识做出的判断用数 值形式表示，从而经过综合分析后对选址进行决策。由于前两类方法的选 址研究很难将选址中的所有影响因素考虑周全，如：地理、地形、地物、 地基、环境、交通、劳动力、城市用地、城市发展等等，并且即便想把这 些因素考虑全面，也很难量化形成模型中的约束条件。因此，建立一种物 流中心的选址评价指标体系，应用模糊评价( f u z z yj u d g e ) 1 1 0 i 、层次分析法 f a h p ) 等数学方法进行综合评价，进而确定物流中心的最优位置就显得十 分重要。由美国运筹学教授t l s a t t y 提出的层次分析法是一种简便、灵活 而又实用的多准则决策方法，它根据问题的性质和要达到的目标分解出问 题的组成因素并按因素间的相互关系将因素层次化，组成一个层次结构模 型，然后按层次分析，最终获得最低层因素对于最高层因素( 总目标) 的重 要性权值。但是，这类方法专家的主观判断占主导地位，决策结果常常受 到专家知识结构、经验以及他们所处地位、时代和社会环境等诸多因素的 限制和影响。所以，对于有限的备选地点，该类方法尽管常常有效，但是 若以整个城市大系统为研究对象来研究物流中心的布局选址，则必须具备 足够的基础资料，辅助以定量分析，否则将缺乏足够的说服力。 国内在物流中心选址方面的研究起步较晚1 1 ，只有1 0 余年历史，但 也有许多学者对其进行了较深入的研究，在理论和实践上都取得了较大的 成果。 北方交通大学鲁晓春等对配送中心的重心法【1 2 l 选址作了深入的研究， 认为原有的重心法存在着问题，并把原有的计算公式用流通费用偏微分方 程来取代。中国矿业大学周梅华也用重心法和微分法相结合的方法在徐州 矿业集团自用型配送中心的选址中进行应用，取得了很好的效果。 同济大学王战权，西南交通大学姜大立、杜文等都对物流中心的选址 问题作了研究，分别提出了各种混合整数规划模型，并采用遗传算法对模 型进行分析求解。 北京科技大学高学东等对鲍姆尔一沃尔夫( b a u m o l w o l f e ) 模型进行了 分析改进，提出了一种混合o - 1 规划模型，并通过分析其特殊结构，建立 4 武汉理工大学硕十学位论文 了一个分解一过滤模式，进而对导出的可行子问题给出了一种启发式算法 ”。西南交通大学刘海燕【”】等在分析物流系统中库存管理、运输、配送 中心之间的联系的基础上，应用最优化方法建立了一种物流中心选址的数 学模型，并给出了按b e n g e r s 方法设计的求解算法。胡刚f 1 6 1 等考虑物流 配送中心固定运营成本和可变运营成本等成本因素，以物流配送中心自身 能取得的利益最大为目标，提出了启发式算法，并认为第三方物流企业一 次在多个地点同时兴建规模很小但数目很多的物流配送中心是不经济和 不科学的，在一次物流预测的基础上通过模型求得多个合理兴建地点而分 阶段进行建设也是不合理的，因为区域物流情况发生变化时，按照原有的 预测建设不可行，而重新预溯显然浪费。因此中心备选点在设置时就应该 科学合理规划1 17 1 。孙会君等对己有多个配送中心存在的前提下，新增配送 决策模型把求解问题归结为无约束的非线性规划问题，并给出了迭代算 法，讨论了多种选址影响因素( 主要考虑利润因素) 及多个新增配送中心 的复杂情况。 黎青松等通过对最优库存策略的研究，提出最优库存费用与其承担的 需求量之间具有非线性关系，在总需求一定的情况下，得出总库存费用与 配送中心数目的平方根模拟表达式，提出考虑库存成本的选址模型。 西南交通大学袁庆达等对基于“服务型”物流战略的多中心( p c e n t e r ) 选址问题作了研究，将大规模配送网络的多配送中心选址问题抽象为求解 图的多中心问题，并给出了选址问题的一个多项式近似算法。另外，北京 市工程咨询公司张广军等也以北京市蔬菜流系统化研究为基础，运用g i s 软件提供的设施定位模型对蔬菜集散中心的选址问题进行了分析，为决策 者提供了定量分析依据。 对于第三类物流中心选址方法，国内进行的研究相对较少，主要在物 流园区的布局规划中有所应用。深圳市规划国土局、深圳市规划设计研究 院在研究深圳物流园区的规划布局时，对物流园区选址的影响因素作了深 入分析，并据此提出了深圳市两大类型【1s j ( 货运枢纽型和配送中心型) 、五 种类别( 综合、港口、陆路口岸、航空、配送) 、八大物流园区的总体规划 布局方案。但此方法只是根据定性分析，尊重“自然”，缺乏有力的定量 分析。同济大学王战权、戴禾等也对物流园区的选址问题进行了探索研究， 提出了物流园区选址的原则，建立了物流园区布局规划的评价指标体系， 5 武汉理工大学硕士学位论文 并以深圳物流园区规划为例进行说明。 综观以上研究成果，由于物流中心选址问题是一项复杂的系统工程， 考虑的因素众多，在实际研究或应用中，考虑的侧重点不同，因而各种研 究成果的条件和方法都有较大差别，但是对于科学合理地规划我国各种类 型的物流中心而言，都有许多值得借鉴之处。 1 2 本课题的研究方法与技术路线 1 2 1 主要研究方法 在物流系统中，物流中心是货物从制造商至零售商之间的中间储存据 点，是集中和分散物资、促进货物迅速流转的枢纽。为了降低物流成本、 提高物流效率，科学合理地选择物流中心的具体地址就具有十分重要的意 义，也是市场竞争的必然结果。物流中心的合理选址能够有效节省物流费 用，促进生产和消费两种物流的协调与配合，保证物流系统的平衡发展。 因此，本文在对物流中心进行科学分类的基础上，探索建立配送型物流中 心的选址模型与方法，针对物流系统的复杂性特点，采用a h p 方法建立 相应的数学模型，然后考虑到模型的特殊性，选择启发式优化算法对所建 立的模型进行求解。经过比较检验证明：该优化算法在解决物流配送中心 选址问题方面起到很好的效果。具体采用的研究方法如下： ( 1 ) 通过i n t e r n e t 和实地调查收集企业的原料场和各原料的物滚 现状、物流管理方式，以及物流技术应用情况，分析影响物流配送选址的 因素，观测、调查收集企业的物流作业流程、信息流程和组织方式等数据 信息，整理并进行归纳分析； ( 2 ) 理论分析研究、建立优化模型； ( 3 ) 寻求解决模型的合理方法； ( 4 ) 模型的求解与方案的比较； ( 5 ) 优化方案的选择与确定。 武汉理工大学硕士学位论文 1 2 2 技术关键路线 ( 1 ) 用a h p 建模方法对要研究的问题进行分析，建立相应的数学模 型； ( 2 ) 启发式算法的实现，本文主要是运用遗传算法、模拟退火遗传 混合优化算法对建立的选址模型进行求解。 1 3 本文主要工作概述 通过对国内外相关的研究，可以看出，在物流配送中心选址规划研究 中，人们往往假设在系统中有给定数量的物流配送中心，将建设物流配送 中心的费用、运输费用或者运输距离等作为目标函数，而忽略了运送服务 质量与物流配送数量( 配送收入) 的关系。所以如何分析各个指标的关系， 建立合理的目标函数，确定物流配送中心的数目与选择合理地址都是至关 重要的。 本文主要是对物流配送中心选址进行研究，建立物流配送中心数量确 定函数。在确定了一个城市或区域物流配送中心数量规模后，从配送中心 选址决策出发建立物流配送中心配送选址模型，主要的研究内容总结如 下： ( 1 ) 在分析有关选址问题相关术语的基础上，侧重讨论研究空间意义上 的物流配送中心选址的概念，即此处所讨论的物流配送中心统指具有一定 规模并从事综合物流服务功能的现代物流基础设施，其选址的优劣直接反 映了整个物流系统运转的好坏。并进一步分析了物流配送中心规划国内外 研究现状，对比各种算法的优缺点； f 2 、综合分析物流系统建设成本、运营成本、货物运输成本、物流服务 质量、货物数量等联系，基于物流收入、物流配送中心固定成本、货物运 输成本中心损耗等建立物流费用最小模型。以该模型为目标函数，计算规 划物流配送中心的数量，并进一步讨论物流配送中心数量和各因素的定量 关系。 ( 3 ) 在确定物流配送中心数量的基础上，设计配送中心选址算法。基于 重心法忽略的实际的地理环境、道理交通状况等主要缺点，根据道路覆盖 武汉理p t 大学硕士学位论文 网络的实际情况，设计一个易于用计算机迭代实现的物流中心选址算法。 该算法考虑当地交通状况的现实影响因素再结合数学模型，采用模拟退火 遗传算法分析物流配送系统，通过应用，以选出最优方案。本文主要是解 决多配送中心选址问题，提出了一种基于区域分割的多配送中心选址方 法。 ( 4 ) 通过具体的实例验证算法在物流选址问题中的有效性。最后进行总 结本文的工作。 1 4 论文整体结构与章节安排 论文具体章节安排如下：第一章绪论，主要阐述本课题的研究目的、 意义以及国内外对物流中心选址研究现状，并对课题中采用的研究方法和 技术关键路线进行了简要说明，然后简要概述了本文的主要工作： 第二章主要是对选址问题进行综述，进而引出物流配送中心选址问 题，并详细综述了与其相关的知识点，包括配送中心选址问题的分类和解 决此类问题的常用方法。 第三章综合分析物流配送中心选址问题，针对问题的特殊性，选择用 层次分析法( a h p ) 进行分析研究，该方法将定性定量相结合，被广泛应 用于诸多领域。本章首先详细介绍了a h p 法的实现步骤，然后通过分析 建立了选址优化模型； 第四章介绍配送中心选址模型的算法设计，本文中选用的是启发式算 法，对遗传算法和模拟退火算法进行了详细介绍，然后将二者有机结合得 到模拟退火遗传混合算法，并分别把遗传算法和混合算法运用到物流配送 选址模型中去，还给出了实际算例，通过求解，结果表明了模拟退火遗传 混合算法的优越性； 第五章总结本文所做工作，并提出有待进一步研究的问题。 8 武汉理工大学硕士学位论文 2 1 选址问题 第二章选址问题的提出 选址问题，就是关于为需要设置的“设施”选择最优位置的问题，是 一个有广泛现实意义的最优化问题，从2 0 世纪6 0 年代以来，受到运筹学 专家、管理专家、经济专家、军事专家、城市规划师、工程师等各方面人 士的关注，得到了迅猛的发展。人们经常在某种系统中设置一个( 或多个) 集散物资、传输信息或执行某种服务的“中心”，例如物流管理中的配送 中心、通讯系统中的交换台站以及自来水厂、医院、核电站等，自然应考 虑选在什么位置才能使得系统的运行效能最佳。选址问题是一个特殊类型 的最优化问题，属于非线性规划和组合最优化的研究范围。但是，基于它 本身的特点，存在单独研究的必要。 选址问题可分为两种基本类型：连续型( 中心及连线都可以在平面上 连续变动) 和离散型( 中心及连线只在网络的有限个点和边中选择) 。前者 也称为平面上的选址问题，其研究方法多属微积分及数学规划方面；后者 也称为网络上的选址问题，其研究方法多与组合分析密切相关。 尽管选址问题主要是一个宏观战略问题，但它的现实意义体现在很多 方面。例如在许多工程设计管理中，或者某一系统的设计本身就是一个典 型的选址问题，或者以选址问题作为一个子问题。一般意义下的选址问题 可能是非常复杂的，常常涉及到自然的、社会的、时间的、空间的各种复 杂条件，所以对此还有许多未解决的问题。 2 2 物流配送中心选址问题 配送中心作为供应链的关键组成部分，一直受到企业界和学术界的重 视。配送中心对供应链的影响主要来自于两个方面：一是配送中心本身的 操作效率，通过加强管理、提高操作的信息化和自动化等手段即可解决， 如沃尔玛的自动化分拣中心；另一个是配送中心地址的选择和规划布局。 本文将重点讨论配送中心的选址问题。 9 武汉理上人学硕士学位论文 选址在整个物流系统中占有非常重要的地位，属于管理战略层的研究 问题。选址决策就是确定所要分配的设施的数量、位置以及分配方案。这 些设旌主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、 零售商网点等。就单个企业而言，设施的选址决定了整个物流系统及其他 层次的结构；反过来，物流系统的其他层次( 库存、运输等) 的规划又会影 响选址决策。配送中心对整个供应链及物流系统效率和效益的提高具有重 大意义，因此，其选址问题是值得深入探讨和研究的。 2 2 1 配送中心选址问题的分类 根据问题的不同，选址问题可以被归为不同的类型，根据不同的类型 可以建立相应的选址模型，进而选择有效的优化算法进行求解，这样就可 以得到该选址问题的最优方案。 目前，我们可将选址问题分为下面几类： 1 根据设施的维数分： 点选址，是用来定位零维物体的， 线选址，是用来定位一维物体的， 选所需要的货物； 例如定位一个新的配送中心。 例如分拣工人向传送带按照订单拣 面选址，是用来定位二维物体的，例如一个制造企业的部门布置； 体选址，是用来定位三维物体的，例如卡车的装卸； 更高维数的选址问题也是存在的，但是比较少。例如，如果问题的约 束条件或者参数随着时间改变，那么这个选址问题就成为带有“时间维” 的四维选址问题，这种问题也称为“动态选址问题”。 2 根据设施选址的数量分： 单一设施选址问题； 多设施选址问题。 其中单一设施选址无需考虑竞争力、设施之间需求的分配、设施成本 与数量之间的关系，主要考虑运输成本，因此，相对于多设旌选址问题丽 言，它是比较简单的一类问题。 3 根据选址问题目标区域的特征分： 1 0 武汉理 大学硕士学位论文 连续选址：待选区域是个平面，不考虑其他结构，可能的选址位置 的数量是无限的。典型的应用是一个企业的配送中心初步选址。 网格选址；待选区域是一个平面，被细分为许多相等面积( 通常是正 方形) 的区域，候选地址的数量是有限的，但是也相当大。典型的应用是 仓库中不同货物的存储位置的分配。 离散选址：待选区域是个离散的候选位置的集合，数量通常是有限 的且甚少的。这种模型是最切合实际的。典型的应用是一个企业的配送中 心的详细选址设计。 4 根据选址成本分： 根据选址成本可以将选址问题分为这样几类问题：是寻求可行成本方 案还是寻求最优成本方案；是寻求总成本的最小化还是成本最大值的最小 化；是固定权重还是可变权重；是确定性的还是随机性的；被定位设施间 有无相互联系：是静态的还是动态的选址闯题。 5 根据选址约束分： 有能力约束与无能力约束：如果新设施的能力没有限制，那么选址问 题就是无能力约束的选址问题：反之，就是有能力约束的选址问题。 不可行区域约束：如果在目标区域内有些区域不合适作为选址地点， 那么这个选址问题就包含了不可行区域的约束。例如，在美国大陆进行配 送中心的选址，五大湖区和墨西哥湾就是不可行区域。 2 2 2 配送中心选址问题的解决方法 为 配送中心选址问题的常用解决方法主要有以下几种： 1 定性方法 定性方法是指凭借个人或集体的经验做出决策。它的执行步骤一般 ( 1 ) 根据经验确定评价指标； ( 2 ) 对各待选地点，利用评价指标进行优劣性检验； ( 3 ) 根据检验结果进行决策。 定性选址常用的方法有头脑风暴法、专家调查法、p e r t 法等。 武汉理1 ：大学硕士学位论文 定性方法的优点是：注重历史经验，简单易行。其缺点是：容易犯经 验主义和主观主义的错误，并且当可选地点较多时，不易做出理想的决策， 导致决策的可靠性不高。 2 定量方法 根据选址设施的数量，将选址方法分为以下两大类： ( 1 ) 单一设施选址 a 重心法i ”1 ：是单个设施选址摄常用的方法。重心法是一种静态的方 法，将运输成本作为唯一的选址决策因素。给定供给点与需求点的坐标以 及节点之间的运输量，则单设施选址的目标是使运输总成本最小。在选址 计算肘，作如下假设： 1 1 运输费用只与配送中心和配送点的直线距离有关，不考虑城市交通 状况； 2 1 不考虑配送中心所处地理位鹭的地产价格。 运输费用的计算方法简述如下： 设有n 个配送点，分布在不同的坐标点( 蕾，y i ) 上，现假设配送中心设 置在，) 处，则总运输费用h 可表示为： h - 罗q w i d i ( 2 - 1 ) 其中：a i 一一配送中心到配送点f 每单位重量、单位距离所需的费用； 砒一一配送中心到配送点i 的运输量； d ；一一配送中心到配送点f 的欧几里德距离， 即d i ；一) 2 + ( y o - y f ) 2 ( 2 - 2 ) 在对配送中心进行选址时，要使总运输费用h 最小，则须分别对、y 。进 行求偏微分，且令其为零，然后应用得到的两个微分等式分别对x o 、y 。求 解，既可以求出隐含最优解的一对等式： 武汉理工大学硕士学位论文 或：善 ) ，：善 ( 2 3 ) 从式( 2 - 3 ) 可以看出，式子的右边含有两个未知数鼍，m 和隐变量以，所 以一次不能求出最优解，对此，可以采取迭代的方法进行求解，首先提供 一组初始解，然后利用薯。，咒。求出d 。，再用它求出蕾和咒。这样经过无限 次的迭代之后就可以求出最优解式和y ：。 b 交叉中值模型：是用来解决连续点选址问题的一种十分有效的模 型，它利用加权的城市距离进行最小化计算。其目标函数为： s = 砉q ”置卜l y o - y i | 式中：峨一一与第1 个需求点对应的权重 t ，y i 一一第i 个需求点的坐标； ( 2 4 ) x o ，y o 一一配送中心的坐标： n 一一需求点的总数目。 求解过程中，综合考虑x 、y 方向上的影响，最后得到的结果可麓为 一条直线。 ( 2 ) 多个设旌选址 a k u e h n h a m b u r g e r ( 奎汉- 哈姆勃兹) 模型： 是对多个设施进行选址的典型方法。它是一种启发式的方法，采用的 是“逐次逼近求近似解的方法”1 2 0 1 ，即先简单地求出初次解，然后经过反 复计算修改这个解，使之逐步达到近似最优解的方法。此方法的模型考虑 了扩建、新建配送中心以及取消不合理的旧的配送中心的因素。 b 模拟模型： 是在求解的精度性上要低于数学优化模型，但能在全面反映实际问题 1 3 武汉理工人学硕士学位论文 的基础上求得满意解的一种模型。如l v a n d e nb r u g g e n ，r g r u s o n ， m s a l o m o n 在1 9 9 5 年为一家大型石油公司处理石油加油站的选址和分配 到每个站点的顾客量的问题时写了一篇文章，发表在欧洲运作研究上， 通过仿真表示优化后的结构每年能节省费用5 6 【2 1 1 。 c 加权评分法： 选址时的许多重要因素难以精确的量化，面对这些因素与指标缺乏 定程度的量化就难以对各种选址方案作对比分析。常用的处理方法就是加 权评分法。加权平分法就是选定几个因素，并给出权重，对欲确定的地址 求加总分得出该选址方案的最后评分，以此得出最优的选址方案。 d 空间一引力模型： 其基本思想如下： 散布在城市中各个区域的顾客与各个销售点有一定的空间距离，假设 各零售店的商品种类大致相同，则顾客购物是因为这家零售店对他的吸引 力较大。 e c f l p ( c a p a c i t a t e df a c i l i t i e sl o c a t i o np r o b l e m ) 模型： 这是反町洋一创造并发表的方法，即反町氏法，用线性规划( l p ) 运输 法，确定各配送中心的市场占有率，求出它们的重心，然后再用混合整数 规划法的“筹划型”确定配送中心的位置。其目标函数与约束条件为： 叫n z 。荟善勺嘞+ 荟只) ，一 5 约束条件： s a n x i ( i - l 2 ，卅) ( 2 - 6 ) 酗“ 善。d ，( ，= 1 ，2 ，刀) 工“0 ，i l 2 ，+ ，m , y 1 ，2 ，。，l 式中：m 一一配送中心建设候补地数目； ( 2 7 ) ( 2 8 ) ( 2 9 ) 武汉理工大学硕士学位论文 k 一一候补配送中心的最大个数 t 一一需求地数目； z 一总费用； c i 一从候补地i 到需求地j 的运输单位费用； 一从配送中心i 到需求地j 的运输量 f 一建设候补配送中心i 的固定费用 儿一一在候补地i 设为配送中心时取值为1 ，否则为0 4 一一配送中心建设候补地i 的建设容量； d i 一一需求地，的需求量。 式( 2 - 6 ) 表示候补配送中心i 的总输出量应不大于其最大供应量；式 ( 2 - 7 ) 表示表示被选中的配送中心个数不超过原定的最大限额；式( 2 - 8 ) 表示配送中心i 的输出量应满足需求地的需求。 此外，还有一些新型的优化算法也被运用到物流配送中心的选址问题 中f 2 到，例如有遗传算法、模拟退火算法、人工神经网络阻及模糊控制方法 等【2 3 1 。本文将尝试其中的新型优化算法。 与定性方法相比较，用定量方法进行选址的优点是能求出比较准确、 可信的解；缺点是常常为了量化，使本来比较复杂的事物简单化、模糊化 了，而有的意见被量化以后可能被误解和曲解。 3 定性与定量方法相结合 定性与定量方法相结合的模型1 2 4 】是现有文献中最常见的一种方法。这 种方法适用于在大范围内进行选址的行为，并且都是先对候选地点进行评 价，筛选掉与目标相差甚远的地点，然后利用数学模型进行再挑选。此方 法的优点是综合了定性和定量两方面，能够做出比较理想的决策，所以被 广泛运用于多个领域。 一 亟坚堡王奎兰堡主堂垡堡塞 第三章物流配送中心选址优化模型的建立 3 1 物流系统中的选址问题分析 3 1 1 配送中心选址的影响因素分析 就单个企业而言，配送中心的选址问题属于企业长远的、战略性的决 策问题，配送中心地址选择的好坏直接影响到企业物流系统环节效率的优 劣。站在整个供应链的角度，配送中心是整个供应链的连接点，影响产品 在供应链中流动的方向和流动速度，对供应链的效率和服务水平起着关键 性作用。 配送中心的地址选择是一个复杂的过程，需要经过多次的反复挑选， 才能选出满意的地点。同时一个配送中心的建立，不仅会对当地的经济产 生直接影响，还会对当地的交通环境和生态环境产生影响，所以建立时应 考虑诸方面的因素1 2 “。尽管影响配送中心选址的因素很多，但是总的来说 可分为两类：成本因素和非成本因素。成本因素是指与直接成本有关的、 可用货币单位衡量的因素。非成本因素是指与成本无直接关系，但能够影 响成本和企业未来发展的因素。具体说明如下： 1 成本因素 ( 1 ) 运输成本：对配送中心的上下游企业来讲，配送中心离他们的远 近对配送中心与他们之间的运输手段( 公路运输还是铁路运输) 、运输方 式( 整车运输还是零担运输) 等有直接的影响。通过合理选择地址，使运输 距离最短，一般在靠近码头、铁路等交通网络比较发达的地方选址，这样 可以使运输成本尽量降低，服务尽量达到最好； ( 2 ) 营运成本：是指配送中心建成后所需花费的各种可变费用。主 要包括所选地区的动力和能源成本、劳动力成本、利率、税率和保险、管 理费用和设备维修保养费等； ( 3 ) 建筑成本和土地成本：配送中心厂房的建设费用，由于不同的 选址方案，对土地的征用、建筑要求等方面有不同的要求，所以可能导致 不同的成本开支，而且各个国家和地区对配送中心征用土地有不同的规 武汉理工大学硕士学位论文 定。一般来说，在仓库的选址过程