（概率论与数理统计专业论文）基于k均值聚类遗传算法的联合选址库存模型研究.pdf

j o i n tl o c a t i o n 一i n v e n t o r ym o d e l b a s e do nk m e a n sc l u s t e r i n g g e n e t i ca l g o r i t h m at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em s d e g r e ei nn a t u r a ls c i e n c e b y l i u r o n g p o s t g r a d u a t ep r o g r a m s c h o o lo fm a t h e m a t i c sa n ds t a t i s t i c s c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l ib o a c a d e m i ct i t l e ：a s s o c i a t ep r o f e s s o rs i g n a t u r e l l | f l 删 2 0 ? 一y “x c 弋 a p p r o v e d a p r i l 2 0 1 1 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均己在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：引莱 1 日期：五叭1 年岁月l 日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：丧t i 棠 日期：p l 、年岁月i 日 导师签名： ) 和础 1 日期：二- f 年广月l ，日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回童诠塞握变压进蜃! 旦圭生；旦= 生；旦三生筮查! 作榔：丧怵 糊张3 争知& 日期：z 。年岁月l 、7 日 日期：工q 年广月f 5 日 1一 中文摘要 物流配送中心是物流系统中最主要的硬件设施之一，物流配送中心的选址在物 流系统规划中至关重要。配送中心的选址问题是物流理论研究中最活跃和最有价值 的问题之一。近年来，越来越多的学者在研究配送中心选址问题时将库存控制策略 考虑进来，建立了联合选址库存模型。联合选址库存模型统筹考虑了库存、运输、 选址和缺货等诸多成本，更加符合物流实际。对联合选址库存模型的深入研究具有 重要的理论意义和现实意义。 基于已有的研究成果，结合具体问题的实际，本文逐步建立和完善了三个模型： ( 1 ) 对单一产品、需求时变且库存影响销售情形，建立了以周期运营成本最小为目标 的联合选址库存模型；( 2 ) 对两类产品、不同需求特性即时变需求和随机需求同时存 在情形，建立了以运营成本最小为单一目标的联合选址库存模型：( 3 ) 在第二个模型 基础上，建立了以运营成本最小、时间满意度最大为双目标的联合选址库存模型。 其中第三个模型最符合实际。 针对所建立的模型，设计了基于k 均值聚类算法与遗传算法的混合算法，称之 为k 均值聚类遗传算法，算法可分为四步：( 1 ) 用k - 均值聚类算法将零售商聚类；( 2 ) 用评价函数评价配送中心对零售商类的优劣，得到备选选址方案；( 3 ) 用改进遗传算法 确定备选选址方案下的最优指派方案；( 4 ) 比较目标函数值找到最优解。 针对实际问题，按照本文提出的k 均值聚类遗传算法原理和步骤使用m a t l a b 软件编写了算法的具体程序，通过对结果的计算与分析，验证了本文建立的模型是 符合实际的、有意义的，本文算法对离散选址问题是有效性的。特别地，本文提出 的k - 均值聚类遗传算法，思路清晰，操作性强。针对本文实际问题，本文算法得到 的最优解，与枚举法( 采用最近指派) 、贪婪取走算法得到的解相比较均有明显提高， 大大的节省了运营成本。 法 关键词：配送中心；联合选址库存模型；k - 均值聚类算法；遗传算法；贪婪取走算 硕士学位论文 m a s t e r st h e s i s a b s t r a c t l o g i s t i c sd i s t r i b u t i o nc e n t e ri so n eo ft h em a j o rf a c i l i t i e si nl o g i s t i c ss y s t e m t h e l o c a t i o no fd i s t r i b u t i o nc e n t e ri so fv i t a li m p o r t a n c e l o c a t i o np r o b l e mo fd i s t r i b u t i o n c e n t e ri st h em o s ta c t i v ea n dv a l u a b l ep r o b l e mi nl o g i s t i c st h e o r yr e s e a r c h i nr e c e n t y e a r s ，m o r ea n dm o r es c h o l a r st a k ei n v e n t o r yp o l i c yi n t oa c c o u n tw h e nr e s e a r c h i n go n l o c a t i o np r o b l e m as e r i e so fj o i n tl o c a t i o n - i n v e n t o r ym o d e l sh a v eb e e nb u i l t d e e p r e s e a r c ho nj o i n tl o c a t i o n i n v e n t o r ym o d e lh a si m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c ea n d p r a c t i c a ls i g n i f i c a n c e b a s e do np r e v i o u sr e s e a r c ha n das p e c i f i cp r o b l e m ，t h i sp a p e rb u i l d saj o i n t l o c a t i o n - i n v e n t o r ym o d e lf o rat y p eo fp r o d u c tw h o s ed e m a n dr a t ei st i m e v a r y i n ga n d i n f l u e n c e db yi n v e n t o r yl e v e l a n dt h e na u t h o re x t e n d st h em o d e lt oa n o t h e rt w om o d e l s w h i c hc o n s i d e r s t h ec a s et h a tt i m e v a r y i n g - d e m a n dp r o d u c ta n ds t o c h a s t i c d e m a n d p r o d u c te x i s t sm e a n t i m e t h ef i r s tm o d e lo ft h et w oh a sa no b j e c t i v eo fm i n i m i z i n gt h e c y c l ec o s t s o b j e c t i v eo ft h es e c o n di sm i n i m i z i n gt h ec y c l ec o s t sa n dm a x i m i z i n gt h e t i m es a t i s f a c t i o na tt h es a m et i m e t ot h em o d e l se s t a b l i s h e d ，t h i sp a p e rg i v e sah y b r i da l g o r i t h mn a m e dk - m e a n s c l u s t e r i n gg e n e t i ca l g o r i t h mw h i c hi sb a s e do nk m e a n sc l u s t e r i n ga l g o r i t h ma n dg e n e t i c a l g o r i t h m i tt a k e sf o u rs t e p s ：( i ) c l u s t e rr e t a i l e r sb yu s i n gk - m e a n sc l u s t e r i n ga l g o r i t h m ；( 2 ) j u d g ec a n d i d a t el o c a t i o np o i n tb ye v a l u a t i o nf u n c t i o nv a l u ea n do b t a i nc a n d i d a t el o c a t i o n d e c i s i o n s ；( 3 ) f i n dt h eb e s ta l l o c a t i o nd e c i s i o nu n d e rac e r t a i nc a n d i d a t e1 0 c a t i o nd e c i s i o n b yu s i n gg e n e t i ca l g o r i t h m ；( 4 ) c o m p a r et h ev a l u eo fo b j e c t i v ef u n c t i o na n df m dt h e o p t i m a ls o l u t i o n w i t hm a t l a b ，a u t h o rw r i t e st h ep r o g r a mo fk - m e a n sc l u s t e r i n gg e n e t i ca l g o r i t h m b ys o l v i n gas p e c i f i cp r o b l e m ，a u t h o rp r o v e st h a tt h em o d e l se s t a b l i s h e da r ep r a c t i c a la n d m e a n i n g f u la n dt h ea l g o r i t h md e v e l o p e di su s e f u lf o rs o l v i n gd i s c r e t el o c a t i o np r o b l e m c o m p a r e dw i t he n u m e r a t i o nm e t h o da n dg r e e d y d r o p p i n gh e u r i s t i ca l g o r i t h m ， s o l u t i o no b t a i n e db yt h ea l g o r i t h mi nt h i sp a p e rs a v e sm o n e yi na l a r g ep e r c e n t a g e k e yw o r d s ：d i s t r i b u t i o nc e n t e r ；j o i n tl o c a t i o n - i n v e n t o r ym o d e l ；k m e a n sc l u s t e r i n g a l g o r i t h m ；g e n e t i ca l g o r i t h m ；g r e e d yd r o p p i n gh e u r i s t i ca l g o r i t h m 硕士学位论文 m a s t e r st h e s i s 目录 中文摘要 a b s t r a c t 第一章绪论 1 1 论文研究的目的 1 2 国内外研究现状。 1 3 本文研究的主要内容 第二章库存影响销售环境下联合选址库存模型。5 2 1 传统p 中值模型5 2 2 单产品单目标模型l 7 2 3 双产品单目标模型2 1 3 2 4 双产品双目标模型3 1 6 第三章k - 均值聚类遗传算法1 8 3 1 遗传算法、k 均值聚类算法简介。1 8 3 2k 均值聚类遗传算法设计2 l 3 2 1k 均值聚类遗传算法步骤、主要思想2 2 3 2 2 算法中其它相关参数、相关量2 3 3 3 本章小结。2 7 第四章实例验证2 8 4 1 实例及计算结果2 8 4 2 相关量、相关结果的分析3 2 4 2 1 时变需求及库存影响销售率系数对成本的影响3 2 4 2 2 单位产品单位距离运输成本对解的影响3 4 4 2 3 本文算法与枚举法、贪婪取走算法的比较3 7 4 3 本文模型与算法的优点3 8 第五章总结与展望：3 9 参考文献4 0 致谢。4 2 硕士学位论文 m a s t e r st h e s i s 1 1 论文研究的目的 第一章绪论 在经济日益全球化的今天，企业与企业之间的竞争空前激烈。现代物流作为“第 三利润源泉”，受到越来越多企业的重视。我国的物流业正处在一个快速发展的阶 段，不管是政府还是企业，都已经认识到物流业在经济发展过程中所起的重要作用。 但我国物流理论的研究仍处于起步阶段，相对滞后的物流理论不能够满足快速发展 的物流业的需要。因此，物流理论的研究很有必要也很有意义。 物流配送中心的选址问题是物流理论研究中最活跃和最有价值的问题之一。配 送中心是物流系统中最主要的硬件设施，货物的装卸、加工、仓储、包装等几乎所 有的物流活动都基于配送中心来进行。科学合理的配送中心选址能有效节省运营成 本，提高资源和设备的利用率，促进生产和消费的协调与配合，蕴含着巨大的经济 效益和社会效益。因此，配送中心选址决策在物流系统规划中至关重要。 在选址决策中常常要全面考虑众多影响因素，往往使得配送中心选址问题一般 都非常复杂，建立符合实际的模型并寻找合适的解决方案就显得尤为重要。本论文 研究的主要目的是针对实际生活中存在的两类不同需求特性的产品，建立一个更加 准确详实地描述这两类产品共存的情形下物流配送中心选址问题的数学模型，并为 建立的模型设计实用的算法，编写相应的算法程序，使建立的模型和设计的算法具 有实际可操作性。 1 2 国内外研究现状 国外物流配送中心选址问题的研究已有数十年的历史，对各种类型的物流配送 中心选址问题在理论和实践方面都取得了丰硕的成果。配送中心选址问题按照不同 的划分标准，有许多不同的分类方法。按照选址目标区域的特征划分是一种常用的 划分方式。按照该方式配送中心选址问题可分为连续型选址问题和离散型选址问题 两类。 连续型选址是指在一个连续空间内所有点都是配送中心的备选地点，需从数量 是无限的点中选择最优的点。该类问题备选地点选择空间很大，常应用于物流设施 的初步定位。代表性的连续选址方法是重心法，这种方法考虑的影响因素较少，模 型简单，主要应用在单个物流中心选址问题上。实际应用中该方法受限制很大，用 硕士学位论文 m a s t e r st h e s l s 该方法求的最终的选址地点可能位于建筑物、河流或者其他无法实现的地点，往往 很难实施。 离散型选址是指目标选址区域是一个离散的候选位置的集合，候选位置的数量 的是有限个，最优的选址点从这有限个可行点中选取。这种选址问题较切合实际， 常应用于设施的详细选址问题。代表性的模型有：运输规划模型、混合整数规划模 型、p 中值模型、集合覆盖模型，代表性的方法有：鲍姆尔法、线性规划法、整数 或混合整数规划法、逐次逼近法、启发式算法。该类方法得出的解比较符合实际情 况，但由于需要的基础资料、基础数据很多，计算工作量很大。 早期传统的物流配送选址模型和方法如重心法、混合整数规划法、鲍姆尔法等 往往是以运输成本和选址成本之和最小化作为目标函数，来进行选址决策。在确定 了配送中心的最优数量和位置后，再制定各级设施的库存控制策略。但是随着理论 研究的不断深入，研究者发现战略层面的设旌选址决策与战术层面的库存管理决策 之间有着深入的联系。传统选址库存方法依次独立解决这两个问题，人为割断了二 者之间的内在联系。当客户处需求波动明显或者库存成本较高时，实践表明这些传 统选址决策往往只能达到局部最优，没有达到整体运营的最优化。因此，在配送中 心选址模型中将库存控制策略统筹考虑进来很有必要。 e p p e n 1 早在1 9 7 9 年就研究发现将零售商处库存集中起来在配送中心处统一 管理可以实现显著的库存成本减少，这种现象被称为“r i s kp o o l i n ge f f e c t ”。随着 研究的深入，越来越多的研究者将选址与库存成本集中考虑。n o z i e k 2 研究了二级 库存系统与选址模型的集成问题，考虑了库存成本和服务水平的均衡，提出各级库 存分配的方法并将库存成本考虑到选址模型中。t e o 等【3 】研究了配送中心集中管理 库存对选址问题的影响，将选址成本与库存成本同时考虑进目标函数中，并设计了 相应的算法，但没有考虑网络设计对运输成本的影响。d a s k i n 等【4 】将安全库存和运 作库存引入到无能力约束选址问题中，建立了一个混合整数规划模型，并采用拉格 朗日松弛算法求解。s h e n 5 研究了单供应商和多零售商的联合选址库存模型，将模 型转化为集合覆盖模型，并提出了相应的解决算法。c h e n 等【6 】使用依概率分布的 情景来描述未来事件的不确定性，研究了该类不确定性下的设施选址问题。s n y d e r 等 7 】利用情景规划来描述不确定性，建立了基于情景规划的随机联合选址库存模 型。v i d y a r t h i 等【8 】将配送中心选址、运输量、安全库存水平以及将零售商分配给那 些配送中心提供服务作为决策变量，进一步研究了一类多产品的生产库存配送系 统设计问题，以运营成本最小化为目标建立了一个混合整数规划模型。 国内在物流中心选址方面的研究起步较晚，只有十余年的历史，但随着研究的 2 硕士学位论文 m a s t e r st h e s i s 深入也取得了一定的成果。黎青松等【9 】提出最优库存费用与需求量之间具有非线性 关系。姜大立等【1 0 】针对易腐物品建立了一种求解配送中心连续选址问题的c a g a 算法，并用实验证明该方法有较好的搜索特性。孙会军等【1 1 1 对已有多个配送中心 存在的情形下，新增配送中心以最大市场占有量为目标，如何选址的问题进行了研 究，建立了选址决策模型并给出了迭代算法。谭凌等 1 2 】研究了由2 个配送中心和 多个门店构成的连锁零售企业配送系统，考虑了各级库存服务水平约束，采用了枚 举法完成系统优化。唐凯等 1 3 1 建立了基于情景规划的随机联合库存选址模型，并 给出了相应的拉格朗日算法。秦绪伟等【1 4 】研究了随机条件下单供应商库存选址问 题，建立了二级库存与无能力约束的集成规划模型，给出了拉格朗日松弛算法并用 仿真实验验证了算法的有效性。戴更新等【1 5 】针对区域多配送中心选址问题构建了 确定性规划模型，并提出了求解该模型的混合遗传算法。黄松等【1 6 】针对一类具有 季节性需求特性的商品，建立了一类随机需求下以期望收益最大化为目标的联合选 址库存模型，并给出求解该问题的基于拉格朗日松弛算法的两阶段算法。 在联合库存选址问题中学者们常常对库存做简化处理，已有的联合选址库存模 型一般只考虑客户处需求量确定或需求量为简单随机变量情形下的库存。事实上， 现实生活中，很多类型产品的需求率在库存周期并不是恒定的。有些产品的需求率 随着时间的增加而增加，另一些产品则正好相反，还有一些产品的需求率呈上下波 动的趋势，产品的需求率表现为时间的函数。同时产品的需求率与库存水平有密切 的联系。产品库存展示的越多，越能吸引顾客购买，这种现象被称为库存影响销售 率( i n v e n t o r y 1 e v e ld e p e n d e n td e m a n dr a t e s ) 。s i l v e r 和p e t e r s o n 1 7 】发现产品的销售量 趋于和展示的库存成比例。随后，基于时变需求且存货影响销售率的情形，一些学 者研究了许多库存控制模型，比较有代表性的研究有【1 8 】- 【2 2 】。时变需求且库存影 响销售率的情形下的库存控制相对于需求量确定或需求量为简单随机变量情形下 的库存控制复杂很多，但在现实中配送中心处该类产品的库存占了很大比例。因此 有必要采取一定的简化策略将时变需求且库存影响销售率的情形下的库存控制引 入到联合选址库存问题中来。 1 3 本文研究的主要内容 本文章节安排： 第一章，介绍了本文研究的目的和意义，国内外研究现状，及本文的主要内容。 第二章，针对一个实际问题，建立了时变需求且库存影响销售率环境下的联合 选址库存模型。首先介绍了解决这类问题的常规p 中值模型和算法，然后建立了更 加符合物流实际的时变需求且库存影响销售率环境下的联合选址库存模型，并将模 型推广到时变需求产品与随机需求产品共存时的双产品单目标模型和双产品双目 标模型。 第三章，针对所建模型，设计了基于k 均值聚类算法与遗传算法的混合算法。 首先对k - 均值聚类算法与遗传算法做了简要介绍，然后详细叙述了本文所设计算法 的步骤、主要思想、改进以及在实际问题中相关参数的设置。 第四章，对一个从实际中简化而来的算例进行了计算，验证了本文模型是符合 实际的合理的、本文算法是有效的。通过对影响运营成本的因素的分析，指出本文 模型中考虑时变需求和库存影响销售率是符合实际且很有必要的，通过与枚举法、 贪婪取走算法的比较，验证了本文算法是有效的。总结了本文模型和算法的优点。 本文主要工作： ( 1 ) 考虑了现实中普遍存在的一类需求时变且库存影响销售率的产品，针对该类 产品建立了联合选址库存模型，并将模型推广到该类产品与随机需求产品共存时的 双产品单目标模型和双产品双目标模型。 ( 2 ) 设计了基于k 均值聚类算法与遗传算法的混合算法。用m a t l a b 软件编写 了算法的具体程序，针对具体实例，通过与枚举法( 采用最近指派) 、贪婪取走算法 的比较验证了算法在离散型选址问题上的有效性。 4 硕士学位论文 m a s t e r st h e s i s 第二章库存影响销售环境下联合选址库存模型 某企业欲在某地区建立p 个物流配送中心以满足该地区客户的需求，企业在该 地区经过前期的调研确定了一些候选地点作为候选的配送中心，这些候选配送中心 的数量、地理位置己知，客户的数量、地理位置也已知。客户处需求的产品分为两 种类型，第一类产品需求时变且库存影响销售率，第二类产品需求为随机变量。客 户需求的两类产品都由惟一的一个供应商供货，供应商的供货能力可满足所有客户 的需求。配送中心在供应商处订购这些产品并且负责向客户配送产品，供应商不直 接向客户提供产品，客户只能在配送中心处订购产品。客户处的某类型产品只由特 定的某个配送中心配送。 在优化整个物流系统运营成本的意义下，企业需要决策在哪p 个候选配送中心 处选址，以及客户的每一类型产品由哪一个特定的配送中心配送。 本问题与传统的p 中值模型所解决的问题有一定的相似性，但本问题更为复杂 更符合物流实际。传统p 中值模型针对需求量确定的产品，以运输成本最小为目标。 而本问题针对两种需求规律不同的产品，并且是以系统运营成本最小为目标。 简要回顾传统的p 中值模型的基础上，根据上述具体问题的实际，本章先针对 需求时变且库存影响销售的产品，建立了以周期运营成本最小为目标的联合选址库 存模型。模型本质上属于一种改进的p 中值模型，在模型建立过程中，推导出了零 售商的库存水平函数、最优订货量、配送中心最优订货次数的具体表达式，写出了 成本目标的函数形式，建立了一个统筹考虑运输、库存、选址、缺货成本的联合选 址库存模型。然后对模型进行适当推广，考虑了时变需求和随机需求两类不同需求 特性产品同时存在时，以运营成本最小为单一目标的联合选址库存模型和以运营成 本最小、时间满意度最大为双目标的联合选址库存模型。 2 1 传统p 中值模型 p 中值模型是指在给定需求点的位置、数量、需求量和候选配送中心数量、位 置的条件下，确定p 个配送中心的位置并指派每个需求点到个特定配送中心，使 配送中心到需求点的运输费用最低。 p 中值模型的数学形式为： 硕士学位论文 m a s t e r st h e s i s 约束为： m i n g 巴巧 一二一一j uq i 越j a 巧= l ，w e d i a _ 置= p i 6 1 y q x i ，v i i ，、j j x j o ，1 ，v i i 2 1 0 ，1 ) ，v i ，v j ， 式中 ，候选配送中心集合，f 候选配送中心序号 ，需求点集合，需求点序号 q ，第_ ，个需求点需求量 g 候选配送中心f 到需求点的单位产品运输费用 p 预建立配送中心个数 yf 1 在备选配送f 处选址 2 10否则 y j 1 配送中心f 向需求蔚配送产品 1 扩一1o否则 由式2 1 及约束条件可以看到，求解一个p 中值模型需要解决： ( 1 ) 在合适候选配送中心处选址( 式中x 变量) ( 2 ) 指派需求点到配送中心处( 式中】，变量) 求解p 一中值模型，问题规模较小时常用枚举法，问题规模较大时常用启发式算 法和智能算法。一种常用启发式算法是贪婪取走启发式算法( g r e e d yd r o p p i n g h e u r i s t i ca l g o r i t h m ) ，算法步骤 6 硕士学位论文 m a s t e r st h e s s ( 1 ) 令当前选中配送中心个数c 等于备选配送中心个数，即所有备选都选中 ( 2 ) 将每个需求点指派到c 个选址点中距离其最近的一个选址点。求出总费用 ( 3 ) 若c = p ，则输出c 个选址点及指派结果，停止；否则，转步骤( 4 ) ( 4 ) 从c 个选址点中取走一个点，满足：假如若取走该点并将它的需求点指派到 其他最近选址点后，总费用增加量最小 ( 5 ) 从选址点集中删去取走点，令c = c 一1 ，转步骤( 2 ) 贪婪取走启发式算法思想简单、易于计算且能以较快速度得到满意解，在实际 使用广泛，但缺陷在于往往得到的是满意解，在某些情形下得到的解可能远非最优 解。 2 2 单产品单目标模型1 本节针对单一产品、需求时变且库存影响销售率情形，统筹考虑了运输、库存、 选址、缺货等诸多成本，建立了以系统周期周期运营成本最小化为目标的联合选址 库存模型。 模型的基本假设 1 所有零售商库存补充策略均为仃，q ) 策略，即每个周期r 期初补充固定批量 为q 的产品 2 某零售商所需产品只由单个配送中心配送。零售商处有服务水平约束。缺货 即构成损失，单位产品缺货损失等于单位产品利润。 3 零售商处实际销售率由其理论需求率和库存水平共同决定。 4 配送中心统一在每个周期r 的期初向零售商分别配送产品，且能在相对r 较 短的时间将产品运输到零售商处，该段时间零售商处缺货。 5 配送中心容量不受限制，配送中心的订货周期为丁的整数倍，每次订货量为 r 上需求量的相应倍数。 6 配送中心根据其订货周期和提前期确定发出订单时间。 7 硕士学位论文 m a s t e r s1 - h e s i s 模型参数和变量定义 ，候选配送中心集合，i 候选配送中心序号。 零售商集合，零售商序号。 丁零售商订货周期。c 单位产品缺货损失也即单位产品利润。v 配送中心配送 产品时的运输速度。 c ，从供应商到配送中心i 的单位产品单位距离运输费用。d ，配送中心f 到供应商 的距离。尸c i 备选配送中心i 处单次订货固定费用，k c j 配送中心f 处单位产品周期 丁的库存费用。霉为i 的订货周期，e 周期丁上f 的选址成本。 q ( f ) 为零售商处的理论需求率函数，i j ( t ) 为_ ，处库存水平函数，r j ( t ) 为处 实际销售率函数。口，为j 处库存影响销售系数，0 0 ，部分产品未售出，周期成本乃( 岛) ( 矿) 。 因此，在f 处实际订购量乌应不大于矿，即q f 矿。此时，q ：f 所对应 的库存水平为零时刻气满足勺t ，且由l ( f ，) = 0 得到q 与勺满足下式： q o = e x p ( - - a j 毛) j ：fq ( ”) e x p ( q “) 幽 由于q ( f ) 非负有界，当q 鳄戤时，q ：f 与勺一一对应 等叫e x p ( c t j t o - a j l ，j ) 零售商歹在配送中心f 处订货的最优周期订货量或的分析 由周期运营成本兀( q f ) 得到： 掣羽 等q 心h h c j 。 吩d 1 j ( u ) 协 令掣型：o 得到 m 若c 满足： 2 - 5 2 - 6 = d j ( t o ) ( ( c l o 吒等) e x p ( 口j t g - - g j ， ) - ( “2 7 = 乃+ 专n 琶： 黼 1 0 2 8 订货量为瓯 鱿= e x p ( - 口乃) e d ( “) e x p ( a j u ) d u 2 10 情形1 ：当c = c 1 f 吒时，毛= 毛，或= 0 。也即当，处单位产品的利润与单位 产品从i 到j 的运输费用相同时，零售商在每单位产品上无盈利，区 l l t j 在i 处不进 货，订货量为零。 情形2 ：当丁h c j 远大于c ，c 1 嘞时，由。 乇，或 。也即当 歹处单位产品利润大于单位产品从i 到j 的运输费用时，零售商在每单位产品上有利 可图，订货量大于零。 鉴于实际环境下，情形3 最为普遍和符合事实，情形1 、2 几乎不可能发生。 因此本文考虑情形3 下零售商处有服务约束的物流库存选址问题。 零售商，处为保证一定的服务水平岛，0 岛 1 ，贝u 栉；： 尚| ! 。若g f ( i ：譬喜i ：1 + 1 ) 模型1 以物流配送系统在z 上的成本最小为目标，建立的物流系统选址库存集成 规划模型： r a i n e ( n x , + g ，+ 兀巧) = 1 2 硕士学位论文 m a s t e r st h e s i s = m i n 善e 置+ e 耐e ，“r , j q ；( c 1 矿嘞+ c ，4 ) + ( 善等+ e 州。q ) +、l d矧| at d ”ij a e ，e ，e ，e jc 巧( rb ( ”) 幽+ q ( 甜) 幽) + 善若巧( 圭玛( 玎卜1 ) q ：+ h 丁c j f , ；i ，( ”) 咖母 2 1 5 约束为： 置= p 巧= l ，w ， 置 o ，1 ) ，v f ， 匕 0 ，1 ) ，v fe l ，we j 上式右端第一项为系统周期选址成本，第二项为周期运输成本，第三项为周期 订货的固定费用，第四项为周期缺货成本，第五项为周期库存成本。约束保证总 选址个数为给定值，保证每个零售商仅由一个配送中心供货，和表示选址变 量和分配变量的取值范围。 2 3 双产品单目标模型2 模型1 考虑的是一类需求时变且库存影响销售的产品，零售商对该类产品的 订货量受到其需求规律、库存成本、订货点等多个因素的影响。而对于周期上需求 为随机变量的产品，该类产品的需求量相对确定，零售商对此类产品的订货量并不 受到库存成本和订货点影响。本章章首提出的具体问题中这两类产品同时存在，因 此本节对模型1 进行适当推广，建立了时变需求和随机需求两类不同需求特性产品 同时存在的单目标联合选址库存模型。 基本假设： 1 零售商周期r 上第二类产品需求相互独立，服从正态分布，方差相对期望较 卜。 1 2 零售商周期丁上第二类产品订货次数不少于1 次。 3 某零售商的两类产品可由不同配送中心配送。 4 配送中心在周期丁上订货一次，订货量固定。 符号： ，i ，j ，j ，t ，1 ，p ，e ，x j 含义同模型1 。q ：为零售商j 处第二类产品的需求，服 从( 所，巧) ，密度函数为办。c 2 驴为从备选配送中心f 到零售商的单位产品单位 距离运输费用。m ：为，在f 处订购第二类产品的周期最优订货次数。 q ( f ) ，i j ( t ) ，r ( f ) 分别表示歹处第一类产品的理论需求、库存水平、实际需求函数。 y ，为i 处安全库存系数。k 产品类集，k 产品类型序号，k = 1 第一类产品，k = 2 第 二类产品。其余符号由模型1 中相应符号下标处添加k 而成，含义变为第k 类产品 的相应量 如： q 为单位第k 类产品缺货费用 厶为在f 处订货时由第七类产品引起的周期成本 为标示j f 在i 处是否订购第后类产品的变量 模型2 的建立 零售商_ ，在配送中心f 处订货时，订购的第一类产品周期r 上成本兀。分析同模 型1 。 零售商j f 在f 处订购第二类产品时周期成本厶：分析 设周期丁上第二类产品订货次数为m ， 期望运输费用：c 2 。毛一 订货固定费用：m ，o c 2 缺货成本： c 2 c _ ，勺 一j 一岛：仃，) 办( “) d u 1 4 配送中心f 处由第一类产品引起的周期成本啊。分析同模型1 配送中心f 处由第二类产品引起的周期成本魄：分析 i 处第二类产品周期t 上的需求服从( 巧：，y ；：司) ，周期安全库存量为 j aj a 7 i 孵， 周期订货量为巧：竹+ n 、巧：司 | 口、j 廿 周期订货运输费用 c a d ，( 巧：, t t j + 九、巧：盯；) ，毛，y j c , j 周期订货固定费用p c ，： 周期库存费用估计 1 l ，k c j ：( 巧：+ 儿、厮) 周期库存费用估计 ，：( 巧：+ 儿，匕z 仃j ) 厶l黾j、ij 弓j 配送中一l , i 处由第二类产品引起的成本为： gf2唰f(啪一，萨n+吉酬吾劬一，擂p；)jr= jv “ 一 j q j ” 2 - 1 8 模型2 两类产品同时存在情形下，以物流配送系统在r 上的成本最小为目标，建立 的物流系统选址库存集成规划模型： 硕士学位论文 m a s t e r st h e s l s m i n ( 只置+ + 厶) i dk t xk e xj 毛j 约束为： 置= p f e j = 1 ，j ，v k k 置 o ，1 ) ，v i ， 磁 o ，1 ) , v ie i ，v jej ，v 七ek 2 4 双产品双目标模型3 实际问题中，零售商常常对产品的配送时间有一定的要求。配送时间越短，零 售商满意度越大。对于一些特殊产品如易腐产品和应急产品，零售商的时间满意度 更是处在核心地位。因此，在联合库存选址模型中考虑零售商的时间满意度很有必 要。 模型1 ，2 建立的联合选址库存模型都是以单一的成本最小化为目标，并没有 考虑到零售商的时间满意度对物流配送中心选址和配送网络设计的重要影响，本节 将在模型2 的基础上引入时间满意度目标，建立双目标模型。 一般用时间满意度函数来量化时间满意度。时间满意度函数定义为响应时间的 非增函数。对于具体的时间满意度函数是如何表示的，马云峰、杨超等【2 3 】在2 0 0 5 年给出了5 种连续函数来定义，本文采用其中的凹凸时间满意度函数，该类型函数 能较好的刻画零售商歹在等待时间阈值肠w ，和u p ，附近时对时间满意度较敏感的情 形。 零售商，处时间满意度函数为 l 1，sz d 姒f ) = 1 - ( i t - l o 瓦w j 严z d w i t 2 _ 2 0 【0 t u p - ， 1 6 式中聊为，处的时间敏感系数，m - ， 1 时是凸的，聊j 21 时是线 性的。 函数图像如下图： 0 8 时 间0 6 满 意0 4 度 o 2 o 响应时间 u p 模型3 两类产品情形下，同时以系统周期运营成本最小和总时间满意度最大为目标 建立的物流系统选址库存集成规划模型： ( m i n ( e k + e g 肪+ 厶) ，m a xe ：e e h ，( 乃) 珞) 2 - 2 1 i e l k e kk 毫xj 毛jj 毛jk e kt e 1 约束为： 五= p 珞= l ，w j ，v k k x ， 0 ，1 ) ，v i ， 】，& o ，1 , v ie l ，w j ，v k k 1 7 本文第二章所建立的三个模型本质上都属于一种改进的p 中值模型。由于所建 立模型的目标函数、约束条件的复杂性，模型并不存在形式解。求解p 一中值模型设 施问题，当问题规模较小时常用枚举法，当问题规模较大时常用的方法是启发式算 法和智能算法。枚举法一般只能求解规模较小的p 中值问题，当问题规模较大时， 枚举法运算量比较大，解题效率不高，在时间上就难以承受。而一般的启发式算 法和智能算法得到的解在某些情形下远非最优解，并且在确定选址方案后往往将零 售商直接指派给距离最近的选址点，对指派方案优化不足。 现实中，多数情形下，地理位置相近的零售商趋向于在相同的配送中心处订货。 受此现象启发可以使用多元统计中的聚类算法对零售商聚类，对每类零售商选出优 越的少数几个各选配送中心，所有零售商类的优越配送中心的组合就得到较优备选 选址方案。此处理方式可以得到问题的一组较优备选选址方案，与枚举法相比大大 减少了待搜索的选址方案。备选选址方案确定后，将零售商直接指派给距离最近的 选址点的指派方案很多情形下并不是最优的，需对指派方案进行全局搜索寻优。一 种较优的全局寻优方法是遗传算法。遗传算法是一种采用概率的变迁规则来指导搜 索方向的随机搜索算法，能以很大的概率找到全局最优解。 基于以上考虑，本文设计了基于k 均值聚类和遗传算法的混合算法，算法可分 为四步： ( 1 ) 用k - 均值聚类算法对零售商聚类 ( 2 ) 用评价函数评价配送中心对零售商类的优劣，得到备选选址方案 ( 3 ) 用改进的遗传算法确定备选选址方案下的最优指派方案 ( 4 ) 比较目标函数值找到最优解 3 。1 遗传算法、k 均值聚类算法简介 遗传算法简介 遗传算法是由j h o l l a n d 教授1 9 7 5 年首先提出的，是一种建立在自然选择学说 硕士学位论文 m a s t e r st h e s i s 和群体遗传学基础上的一种随机全局搜索与优化的智能算法。算法模拟了生 过程的繁殖、交配、遗传和变异现象，根据适者生存、优胜劣汰的自然法则 传算子作用下使群体逐代优化，产生优秀个体，最终搜索到最优解。 简单遗传算法的基本步骤及简要说明： ( 1 ) 编码及定义适应度函数