（管理科学与工程专业论文）考虑时间因素的选址库存路径问题集成优化模型与算法研究.pdf

华中师范大学学位论文原创性声明和使周授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 拓者签名：蔓伊日期：如恽罗月日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：违但 日期：硎年歹月力6 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程”中的 规定享受相关权益。 作者签名：兰阻 日期烈年罗月二日 导师签名： 聱彳 日期：加l ，年厂月彩日 硕士学位论文 m a s t e r st h e s i s 摘要 随着经济的发展及社会的进步，人们需求的差异性和随机性越来越明显，为了 快速满足客户多变的需求，企业必须尽量缩短自己的产品生命周期，使得今天的企 业处于基于时间竞争的市场环境中。物流系统作为企业的一个重要组成部分，不可 避免的必须适应这一新的竞争环境，以此来满足客户需求。而设施选址、库存策略、 配送模式是影响物流系统的最重要的三个因素。基于这种现实意义的考虑，本文将 对考虑时间因素的选址库存路径问题展开研究。 本文首先介绍了本文研究内容的研究背景、研究意义及国内外研究现状，指出 了本文研究内容的必要性。 本文的第二部分简要介绍了本文后续部分中将会用到的三种算法。 本文的第三部分引入时间窗约束，建立了备件物流系统的带软时间窗的选址 库存路径问题模型，在禁忌搜索算法和改进的节约路程法的基础上，设计了一种两 阶段混合启发式算法来求解模型，第一阶段用来解决选址库存问题，第二阶段用来 解决带软时间窗的车辆路径问题，并通过禁忌搜索算法对解进行优化得到最终解。 本文的第四部分考虑到订货周期对物流系统成本的重要性，本文将订货周期作 为决策变量引入到模型中，建立了基于订货周期的选址库存- 路径模型，并设计了 基于拉格朗日松弛算法和禁忌搜索算法的混合式启发式算法来求解模型。首先，利 用拉格朗日松弛算法将问题分解成两个子问题并分别求解后得到了问题的初始解， 然后利用禁忌搜索算法来优化解直至得到最终解。 上述模型和算法都采用算例进行了演算，其结果证明了上述模型和算法的有效性。 本文第五部分对本文的研究内容进行了简明的总结，并指出了将来的改进方向。 关键词：选址库存路径问题；禁忌搜索算法；改进的c w 算法；拉格朗日松 弛算法 a b s t r a c t 晰t l lt h eg l o b a l i z a t i o na n dt h ep r o g r e s so fs o c i e t y , p e o p l e sd e m a n d sa r em o r ea n d m o r ev a r i a n ta n ds t o c h a s t i c ，e n t e r p r i s e sh a v et os h o r t e nt h e i rp r o d u c tl i f ec y c l et om e e t p e o p l e sv a r i a b l ed e m a n d s ，w h i c hm a k et h em a r k e tt i m e b a s e dc o m p e t e d i no r d e rt o m e e tp e o p l e sd e m a n d s ，l o g i s t i c ss y s t e ma so n ei m p o r t a n tp a r to fe n t e r p r i s eh a st oa d j u s t t o t h en e wc o m p e t i t i o ne n v i r o n m e n ti n e v i t a b l y f a c i l i t yl o c a t i o n , i n v e n t o r yp o l i c y , d e l i v e r yp l a na r et h r e em o s tk e yf a c t o r sw h i c hi n f l u e n c el o g i s t i c ss y s t e m f o rt h e s e r e a s o n s ，t h i sp a p e rw i l lr e s e a r c hl o c a t i o n - i n v e n t o r y - r o u t i n gp r o b l e mt a k i n gt i m ei n t o c o n s i d e r a t i o n i nt h ef i r s t c h a p t e r , t h i sp a p e ri n t r o d u c e si t s r e s e a r c hb a c k g r o u n d 、r e s e a r c h s i g n i f i c a n c ea n dr e s e a r c hs i t u a t i o no fh o m ea n da b r o a d ，i n d i c a t e st h a ti ti sn e c e s s a r yt o r e s e a r c ht h i st o p i c i nt h es e c o n dc h a p t e r , t h i sp a p e rp r e s e n t st h r e ea l g o r i t h m sw i l lb eu s e di nt h e f o l l o w i n gc h a p t e r s i nt h et b j r dc h a p t e r , t a k i n gt i m ew i n d o wc o n s t r a i n ti n t oc o n s i d e r a t i o n , am o d e lo f t h el o c a t i o n - i n v e n t o r y r o u t i n gp r o b l e m 、析t l ls o f tt i m ew i n d o wf o rs p a r ep a r t sl o g i s t i c s s y s t e mi se s t a b l i s h e d a n da t w op h a s eh y b r i dh e u r i s t i ca l g o r i t h mb a s e do nt a b o os e a r c h a n di m p r o v e dc - wa l g o r i t h mi sp r e s e n t e dt os o l v et h em o d e l n l ef i r s tp h a s ei st os o l v e t h el o c a t i o ni n v e n t o r yp r o b l e m ，t h es e c o n do n ei st os e t t l et h ev e h i c l er o u t i n gp r o b l e m w i 也s o f tt i m ew i n d o w , t a b o os e a r c ha l g o r i t h mi su s e dt oi m p r o v et h es o l u t i o nu n t i lg e t t h el a s ts o l u t i o n i nt h ef o u r t hc h a p t e r , g i v e nt h ei m p o r t a n c eo fo r d e rc y c l et ol o g i s t i c ss y s t e mc o s t , t h i sp a p e ri n t r o d u c e si ti n t om o d e la sad e c i s i o nv a r i a b l e ，a n db u i l dam o d e lo f l o c a t i o n - i n v e n t o r y r o u t i n gp r o b l e mb a s e do ni t ah y b r i dh e u r i s t i ca l g o r i t h mb a s e do n l a g r a n g i a nr e l a x a t i o na l g o r i t h ma n dt a b o os e a r c ha l g o r i t h mi sp u tf o r w a r dt os o l v et h e m o d e l n l ea l g o r i t h mh a v e3s t e p s ：f i r s t l y ，d i v i d i n gt h em o d e li n t ot w os u b p r o b l e m sb y l a g r a n g i a nr e l a x a t i o na l g o r i t h m ；s e c o n d l y ，s o l v i n ge a c ho ft h et w os u b p r o b l e m sa n dg e t t h ei n i t i a ls o l u t i o n ；f i n a l l y ，u s i n gt a b o os e a r c ha l g o r i t h mt oi m p r o v et h es o l u t i o nu n t i lg e t t h el a s ts o l u t i o n a l lt h em o d e l sa n da l g o r i t h m si nt h ea b o v ec h a p t e r sa r ec o n f i r m e dt ob ef e a s i b l e t h r o u g he x a m p l e s i nt h ef i 胁c h a p t e r ，w es u m m a r i z et h i sp a p e ra n dp u tf o r w a r dt h ed i r e c t i o no f i m p r o v i n g k e yw o r d s ：l o c a t i o n - i n v e n t o r y - r o u t i n gp r o b l e m ；t a b o os e a r c ha l g o r i t h m ； i m p r o v e d c wa l g o r i t h m ；l a g r a n g i a nr e l a x a t i o na l g o r i t h m h 目录 摘要一i a b s t r a c t 1 绪论 1 1 1 研究背景及意义一1 1 1 1 研究背景1 1 1 2 研究意义2 1 2 国内外研究现状2 1 2 1 国外研究现状2 1 2 2 国内研究现状3 1 3 本文的主要研究内容和创新点4 1 3 1 本文的主要研究内容4 1 3 2 本文的创新点5 2 相关算法介绍 6 2 1 节约里程法”6 2 1 1 基本理论6 2 1 2 算法流程7 2 1 3 算法的优缺点7 2 2 禁忌搜索算法“”7 2 2 1 基本理论7 2 2 2 算法的流程8 2 2 3 算法的优缺点8 2 3 拉格朗日松弛算法8 2 3 1 基本理论。8 2 3 2 算法的流程9 2 3 3 算法的优缺点9 3 带软时间窗的l i r p 集成优化模型与算法研究 1 0 3 1 问题描述l o 3 2 数学模型l l 3 2 1 模型假设”1 1 硕士学位论文 m a s t e r st h e s i s 3 2 2 符号定义1 2 3 2 3 数学模型1 3 3 3 算法设计1 3 3 3 1 算法描述：”1 3 3 3 2 算法流程”1 8 3 4 算例分析1 8 3 4 1 算例设计1 8 3 4 2 算法对比分析”2 l 3 5 本章小结2 2 4 考虑订货周期的l i r p 集成优化模型与算法研究 4 1 问题描述2 3 4 2 数学模型2 3 4 2 1 模型假设“2 3 4 2 2 符号说明”2 3 4 2 3 数学模型：”2 4 4 3 算法设计”2 6 4 3 1 寻找下界值2 6 4 3 2 计算上界值3 2 4 3 3 次梯度优化3 2 4 3 4 禁忌搜索算法3 3 4 4 算例分析3 5 4 4 1 算例设计3 5 4 4 2 算法对比分析3 8 4 5 本章小结3 9 5 总结与展望 5 1 全文总结4 0 5 2 研究展望4 0 参考文献 附录1 攻读硕士学位期间的论文工作 附录2 攻读硕士学位期间参加的科研项目 致谢 4 2 4 6 4 7 4 8 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景及意义 1 1 1 研究背景 1 绪论 ( 1 ) 当前的市场环境是基于时间竞争的，物流系统对缩短响应时间具有重要作用 随着市场竞争的加剧和全球经济一体化，经济活动的节奏越来越快，用户对产 品时间方面的要求越来越高，同时科技进步和个性化的顾客需求要求产品生命周期 不断缩短，因此，时间成为继成本、质量之后又一个影响用户需求的关键性竞争因 素。在基于时间竞争的市场环境下，对顾客需求的快速响应是企业成功的关键因素， 而高效、快捷的物流手段是迅速满足顾客需求的保证。调查显示：9 3 的欧美管理 者认为可靠的交付时间是十分重要的，其中8 9 的欧洲管理者和8 8 的美国管理 者认为全程交付速度是形成竞争优势的关键因裂。通过对供应链的研究可以发现， 产品对最终用户的响应速度应是供应链全过程的累积效应，而不是仅依靠某一个环 节【2 】。因此我们有必要通过对物流系统的优化设计与控制，有效地缩短产品在物流 系统中的停滞时间，从而使产品在整个供应链上形成基于时间的竞争优势。 ( 2 ) 集成优化是物流系统优化的发展趋势，其为建立基于时间的竞争优势提供 物流支撑 随着物流管理在我国的快速发展和系统化，越来越多的管理者开始认识到：在 设施( 制造厂、分销点或配送中心) 地址、客户位置、货物配送、运输货物的车辆 路线安排之间存在相互依赖的关系，应该根据这种关系来对物流网络进行集成优化 与物流管理活动【3 】，因此产生了集成物流管理( i n t e g r a t e dl o g i s t i c sm a n a g e m e n t ，i l m ) 的概念。上世纪末的一项调查显示：全球有超过5 0 的物流管理者已经接受了i l m 的概念，他们所在的企业正在逐步实施i l m 4 1 。对世界各地的许多企业而言，i l m 正日益成为物流管理中越来越重要的管理手段，集成优化是物流系统优化的必然 趋势。 本论文的研究受到国家自然科学基金项目( n o ：7 0 8 7 1 0 5 0 ) 和华中师范大学中央 高校基本科研业务费项目0 q o ：c c n u l 0 8 0 1 0 0 2 ) 的资助，属于l i r p 静态优化子模块 的部分内容。 硕士学位论文 m a s t e r st h e s i s 1 1 2 研究意义 ( 1 ) 理论研究方面 当前对集成物流系统的研究主要集中于选址路径问题( l o c a t i o nr 0 u t i n g p r o b l e m , l r p ) 、库存路径问题( i n v e n t o r yr o u t i n gp r o b l e m ，i r e ) 和选址库存问题 ( l o c a t i o n i n v e n t o r yp r o b l e m ，l i p ) - - - 个方面，并且主要是基于成本的优化，而对选址 库存路径问题( l o c a t i o ni n v e n t o r yr o u t i n gp r o b l e m ，l i r p ) 的研究还非常缺乏，对基 于时间优化的l i r p 研究更少。本文将在l i r p 模型中引入时间变量，设计相应的集 成优化模型和算法，从而将时间竞争和物流系统集成优化这两个领域综合起来进行 研究，也促进了优化理论和技术在这两个领域的应用。 ( 2 ) 企业实践方面 当前企业及其所属供应链的竞争已经从基于成本、质量、品种的竞争转向了基 于时间的竞争，新的竞争环境给企业生存和发展提出了严竣的挑战，如何适应环境 的变化并以较低的成本快速响应客户需求成为企业在竞争中获胜的关键。本文致力 于探索如何在缩短物流系统整体响应时间的同时降低物流运作成本、提高企业物流 运作效率、协调各物流活动参与方的决策与控制，从而帮助企业提高对客户需求的 响应速度，并因此为企业获得基于时间的竞争优势提供物流保障。 1 2 国内外研究现状 1 2 1 国外研究现状 目前国外关于l i r p 的研究还比较少，p e r l & s i r i s o p o n s i l p 【5 j ，j a y a r a m a n 【6 j ，n o z i c k & t u r n q u i s t 7 a m b r o s i n o & s c u t e l l a 8 】做了一些研究工作，但他们的研究还不能算是 真正的l i r p ，在运输问题上这些研究主要考虑直送模式而非巡回路线安排。一般认 为，l i u & l e e 【9 】是严格意义上最早研究l i r p 的文献，他们建立了一个单一产品、多 设施的l i i 冲非线性规划模型，并设计了一个两阶段的启发式算法，其中第一阶段通 过启发式算法得到模型的初始解，第二阶段通过优化选址来获得更优解。进一步的， l i u & l i n0 0 针对上文算法容易陷入局部最优的缺陷，设计了一种全局优化的启发 式算法：先用启发式算法求得l i r p 的一个初始解，再用基于禁忌搜索和模拟退火算 法的混合启发式算法分别对选址和路径进行优化，来改进解的质量。s h e n & l i a n i l l j 研究了随机需求下，工厂、配送中心、客户三层供应链系统的l i r p 模型，并用内嵌 拉格朗日松弛算法的分支定界法求解模型。z e y n e p 1 2 】建立了单一产品、多节点的 l i r p 模型，并给出了基于禁忌搜索的两阶段算法求解模型，其中第一阶段进行路径 2 决策，第二阶段进行选址决策。 上述文献都是基于成本优化的，“基于时间竞争”的概念在1 9 8 8 年由s t a l k l i j j 在其论文“时间下一个竞争优势资源”中首次提出，文章指出：由于市场需求 随机性的增大，企业的成功越来越取决于其对客户订单的响应能力，科技进步和多 样化的顾客需求要求产品生命周期不断缩短，时间已经成为影响竞争优势的一种新 的重要资源。此后，基于时间的竞争优势受到了人们广泛的关注，但是当前关于时 间竞争环境下物流系统集成优化的文献极少，k u t a n o g l u 及其领导的团队对其中的 l i p 进行了一系列的研究：k u t a n o g l ue ta 1 1 4 1 研究了时间竞争环境下具有随机需求的 l i p ，他们将随机响应时间作为模型的一组约束条件。j e e t i s 对集成物流系统设计中 基于时间服务的通用件l i p 进行了研究，他分别研究了单一产品、多产品和通用件 的问题，建立了两阶段模型、线性规划模型和混合整数非线性规划模型，求解方法 涉及两阶段算法、松弛算法和分解算法。c a n d a s & k u t a n o g l u 1 6 建立了一个l i p 优 化模型来揭示时间竞争策略下选址与库存控制之间的关系，他们的计算结果显示： 在保证时间竞争服务水平的前提下，相对于分步求解( 先求解选址分配问题，再求解 库存问题) ，采用集成的方法更可获得显著的成本节约。 1 2 2 国内研究现状 国内对l i r p 的研究也比较少，赵秋红【1 7 】对随机需求下配送中心选址、库存控制 与运输路线安排展开了集成研究。崔广彬，李一军【l8 】采用两层规划法建立了供应链 二级分销网络的l i r p 模型，其中上层规划用来得到初始巡回路线运输方案，下层规 划对初始方案进行优化。考虑到客户需求的随机性，崔广彬，李一军【l9 】在上文的研 究基础上，建立了基于单周期模糊需求存贮策略的l i r p 模型，并设计了求解该模型 的启发式算法。张波【2 0 】对成品油配送系统的l i r p 问题展开了研究。代颖，马祖军1 2 l 】 以逆向物流系统为研究对象，采用混合整数规划法，建立了基于回收商管理库存策 略( c o l l e c t o rm a n a g e di n v e n t o r y ，c m i ) 的多周期l i r p 模型，最后采用两阶段启发式算 法求解模型。唐燕，马祖军瞄】在上文的基础上，研究了废旧轮胎回收网络规范化问 题，建立了基于c m i 策略的多周期l i r p 模型，并提出了两阶段启发式算法求解模型。 国内关于时间竞争环境下物流系统集成优化的文献也比较少，黄春雨等1 2 3 j 建立 了一个以缩短物流多阶响应周期和降低成本为目标的多目标l r p 模型。郭伏等人瞄j 以城市配送系统为研究对象，建立了一个以准时到达和总成本最低为决策目标的多 目标l r p 模型，设计了一种两阶段启发式算法对模型进行求解，在第二阶段也是运 用遗传算法来优化运输路线。张潜等人 2 5 1 考虑了时间和成本两个目标，应用内嵌模 糊决策法则的改进遗传算法来求解多目标l r p 。杜丽敬，李延晖【2 6 j 建立了个带软 3 硕士学位论文 m a s t e r st h e s i s 时间窗的l i r p 模型，并采用遗传算法对该模型进行求解。唐琼，李延晖【2 7 】也以带 软时间窗的l i r p 模型为研究对象，将l i r p 分解成选址和带软时间窗的库存路径两 个子问题后，用内嵌禁忌搜索的改进模拟退火算法分别对两个子问题求解。 1 3 本文的主要研究内容和创新点 1 3 1 本文的主要研究内容 本文围绕着考虑时间因素的l i r p 集成优化这一主题，主要展开了以下三方面 的研究： ( 1 ) 带软时间窗的选址库存路径问题集成优化模型 以集成物流系统的供应链二级分销网络为研究对象，考虑到客户对货物送达时 间的要求，建立带软时间窗的l i r p 数学模型。从成本的角度来看，模型将涉及配 送中心选址费用、库存费用、车辆运输费用。其中选址费用包括配送中心的固定成 本以及从工厂到配送中心的产品运输成本；库存费用包括配送中心库存维持成本和 缺货成本；运输费用包括车辆固定成本、为客户配送货物的运输成本以及车辆违反 时间窗要求而额外支付的成本。 ( 2 ) 考虑订货周期的选址库存一路径问题集成优化模型 已有的集成物流系统研究文献很少考虑零售点的订货周期，事实上，在进行配 送路径安排时，在同一条配送路径上的零售点必须处于相同的订货周期内，否则， 将导致配送计划存在较大的执行困难。本文则考虑这一现实情况，建立考虑零售点 订货周期的选址库存一路径问题集成优化模型，对以下几个问题同时进行决策：( 1 ) 选址决策：从备选配送中心中选择哪些参与配送并确定最佳配送中心的数量；( 2 ) 路径安排：对于由同一个配送中心提供服务的客户，确定巡回路线；( 3 ) 库存决策： 每条巡回路线的最佳订货周期和最佳订货量。 ( 3 ) 求解模型的有效算法 由于本文的研究问题属于n p h a r d 问题，一般认为不存在完整、精确、而又不 是太慢的求解算法，现有文献大多数采用启发式和亚启发式算法求解此类问题。因 此，本文将借鉴前人已有的成熟的算法来设计相应的启发式算法。同时，鉴于禁忌 搜索算法、遗传算法、人工神经网络法等一些智能算法在求解此类问题中所表现出 的优势，本文也将借鉴这些智能算法的最新研究成果，与其他算法相结合构造混合 算法求解模型。 针对本文的主要研究内容，本文分为五个部分进行系统的研究： 4 第一章介绍了基于时间竞争的l i r p 问题的国内外研究现状，以及本文的主要 研究内容和创新点。 第二章简要介绍了本文后续部分中将会用到的三种算法的基本理论、算法流程 及优缺点。 第三章以制造业备件物流系统为具体的研究对象，建立了其带软时间窗的l i r p 问题模型。基于禁忌搜索及改进的节约里程法，设计了一种先选址库存后路径的两 阶段混合启发式算法来求解模型，并通过禁忌搜索算法对解进行优化得到最终解。 第四章考虑到订货周期对物流系统成本的重要性，将订货周期作为决策变量引 入到模型中，建立了基于订货周期的l i r p 模型，并设计了基于拉格朗日松弛算法 和禁忌搜索算法的混合式启发式算法。 第五章总结与展望。 1 3 2 本文的创新点 本文的创新点主要体现在以下两个方面： ( 1 ) 目前国内备件物流系统集成优化的研究文献还比较少，基于时间竞争的备 件物流系统集成优化的研究文献则少之又少，由于备件具有需求量小、随机性大、 单位时间的缺货成本高等特点，备件物流管理成为了制造型企业生产经营活动中的 难题。针对这一现实情况，本文建立了带软时间窗的备件物流系统l i r p 模型，设 计了一种基于禁忌搜索及改进的节约里程法的两阶段混合启发式算法来求解模型， 并通过现有的数据库中的算例演算证明了该算法和模型的有效性。目前，这一部分 的研究内容已经整理成稿，并在工业工程与管理2 0 1 0 年2 月刊中发表。 ( 2 ) 现有的集成物流系统研究文献大多数采用( q ，力库存策略，何时订货是以库 存量是否降到，- 值为依据的，由于需求的不确定性，对于同一个零售商，订货的时 间间隔是不同的。即使服务水平设置为相同，各个零售商的库存降低到各自的r 值 的时间点是不一样的，将这样的零售商捆绑到一起联合订货和配送，不会得到预定 的服务水平的目标。因此，在进行配送路径安排时，同一条配送路径上的客户必须 处于相同的订货周期内，否则，将导致配送计划存在较大的执行困难。本文基于这 一现实情况的考虑，将订货周期作为一个明确的决策变量，引入到l i r p 集成优化 模型中，使得模型更具有现实意义。同时设计了基于拉格朗日松弛算法和禁忌搜索 算法的混合式启发式算法来求解模型，而且通过已有的数据库中的算例演算证明了 该算法和模型的有效性。目前，这一部分的研究内容已经整理成稿，并已投稿至管 理科学学报。 硕士学位论文 m a s t e r st h e s i s 2 相关算法介绍 本章主要介绍第三章和第四章将要用到的几种算法，包括节约里程法、禁忌搜 索算法和拉格朗日松弛算法等的基本理论、算法流程及优缺点。 2 1 节约里程法 2 1 1 基本理论 节约里程法简称c w 算法，由c l a r k e 和w r i g h t 2 8 1 在1 9 6 4 年首次提出，自提出 以来得到了广泛应用，是求解车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 最常用 的启发式算法。c w 算法的基本原理是三角形两边边长之和必定大于第三边。为了 更好的解释该原理，下面给出一个实例来给予说明。 假设配送中心d c 需要向客户a 和客户b 送货，已知配送中心d c 到客户a 和 客户b 的距离分别为厶和厶，客户a 和客户b 的距离为厶，现有两种送货方案如 图2 1 所示 送货方案a送货方案b 图2 1 节约里程法理解图 在上图中方法a 的配送距离为2 ( l “6 ) ；方法b 的配送距离为池乜6 也c ) 。第二 种方案与第一种方案相比，路线的节约值为2 ( l 批6 ) - 犯口也批分吐a + l b - l c ，由三角 形的几何性质可知，三角形中任意一边边长一定小于另外两边边长之和，即三口也b l 。， 因此从运输路程角度来考虑，方案b 优于方案a ，节约了一6 0 的里程，这种通 过比较运输方案的运输距离长短来判断其优劣的思想，就是c w 算法的基本思想。 6 硕士学位论文 m a s t e r st h e s i s c w 算法的核心思想是依次将车辆路径问题中的两条回路合并为一条回路，每 次使合并后的运输距离减小的幅度最大，直到一条路线上的运输总量达到运输车量 的容量限制时，再对下一条路线进行优化。 2 1 2 算法流程 s t e p l 做出网络节点之间的最短距离矩阵，该矩阵包括配送中心与用户以及用 户之间的距离。 s t e p 2 按照c w 算法的基本思想计算用户之间的节约里程。 s t e p 3 将节约里程按从大到小的顺序进行排列。 s t e p 4 按节约里程大小和车辆容量限制得到配送路线图。 2 1 3 算法的优缺点 c w 算法简单、易于理解、灵活性好，一方面体现了运输过程优化，与其它方 法相比缩短了运输路程；另一方面，也体现了物流配送网络的优势，实现了企业物 流活动的整合。但是c w 算法也存在明显的不足，主要表现在两个方面：( 1 ) 采用 c w 算法设计配送路线时过于侧重节约路程，而忽略了运输过程中的时间因素，在 些情况下，时间比路程更能决定物流配送的成本和服务质量。( 2 ) 采用c w 算法 设计配送路线时不能对客户的需求进行灵活多变的处理。由于企业的制造、销售和 配送越来越倾向于小批量、多品种、多批次，而c w 算法更倾向于稳定需求，因 此c w 算法难以满足现代多变的市场环境。 2 2 禁忌搜索算法 2 2 1 基本理论 禁忌搜索算法( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 由美国科罗拉多大学教 授f r e dg l o v e r 在1 9 8 6 年提出，它是对局部邻域搜索算法的一种拓展，是一种全局 优化算法，是对人类记忆功能寻优过程的一种模拟 2 9 1 。t s 算法通过引入局部邻域 搜索机制和相应的禁忌准则来避免迂回搜索，并通过藐视准则来释放一些被禁忌的 优良状态，从而保证搜索的多样化，以最终实现全局优化。 禁忌搜索算法的基本思路是在搜索的过程中将已经进行的邻域移动存放在禁 忌表中，阻止这些移动在近期内返回，这样就有效的防止了搜索过程出现循环。t s 涉及到邻域( n e i g h b o r h o o d ) 、禁忌长度( t a b ul e n g t h ) 、禁忌表( t a b ul i s t ) 、候选解 ( c a n d i d a t es o l u t i o n ) 、藐视准则( d e s p i s e ds t a n d a r d s ) 、终止准则( t e r m i n a t es t a n d a r d s ) 7 硕士学位论文 m a s t e r st h e s i s 等概念。邻域结构的设计决定了当前解的邻域解的产生形式和个数；禁忌表是t s 算法的核心，用来防止搜索过程出现循环，避免陷入局部最优；禁忌长度给出了禁 忌对象的任期；藐视准则用来防止t s 算法遗失优良状态，激发对优良状态的局部 搜索；终止准则用来确定整个搜索过程的结束。 2 2 2 算法的流程 禁忌搜索算法的步骤可描述如下： s t e p l 给定初始参数，随机产生初始解x ，并令= x ，其中五耐为当前最优 解，令禁忌表为空。 s t e p 2 判断算法终止条件是否满足? 若满足，则转s t e p 6 ；否则，转s t e p 3 。 s t e p 3 利用邻域函数产生当前解x 的所有或若干邻域解，从中选出部分邻域解 作为其候选解。 s t e p 4 判断候选解是否满足藐视准则? 若满足，则用满足藐视准则的最佳状态y 替代x 成为新的当前解，即令冽，并用与y 对应的禁忌对象替换最早进入禁忌表 的禁忌对象，同时令托耐= y ，然后转s t e p 2 ；否则，转s t e p 5 。 s t e p 5 判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应 的最佳状态) ，l 为新的当前解，即令x = y l ，同时用与y l 对应的禁忌对象替换最早进 入禁忌表的禁忌对象元素，转s t e p 2 。 s t e p 6 结束算法并输出优化结果。 2 2 3 算法的优缺点 禁忌搜索算法的优点主要表现在两个方面：( 1 ) 在搜索过程中不会放弃劣解， 因此具备较强的“爬山 能力，从而提高得到更好的全局最优解的概率。( 2 ) 新解不 是从当前解的邻域解中随机选择，而是优于当前最优解的解，或者是非禁忌的最优 解，因此得到优良解的几率很大。但是禁忌搜索算法也存在一些不足，主要表现在 两方面：( 1 ) 算法对初始解依赖性较强，好的初始解能够提高获得最优解的几率， 而较差的初始解往往会导致得不到最优解；( 2 ) 迭代搜索过程是串行的，仅是单一 状态的移动，而非并行搜索【3 0 】。 2 3 拉格朗日松弛算法 2 3 1 基本理论 拉格朗日松弛算法( l a g r a n g i a nr e l a x a t i o na l g o r i t h m ) 的基本原理是将导致整 8 硕士学位论文 m a s t e r st h e s i s 数规划问题难以求出最优解的复杂约束吸收到目标函数中，同时保持目标函数的线 性，使得问题容易求解。拉格朗日松弛算法主要由次梯度优化算法( s u b g r a d i e n t 0 p t 砌z a t i o n a l g o r i t h m ) 和拉格朗日松弛启发式算 法( l a g r a n g i a nr e l a x a t i o nh e u r i s t i c a l g o r i t h m ) 组成，它们的两个主要应用是给出整数规划问题的下界和在拉格朗日松 弛算法的基础上设计启发式算法【3 l 】。 2 3 2 算法的流程 拉格朗日松弛算法步骤可描述如下： s t e p l 松弛原整数规划问题中的复杂约束，并给定初始拉格朗日乘子，得到原 问题的拉格朗日对偶问题。 s t e p 2 将该对偶问题分解形成较易求解的几个子问题。 s t e p 3 解根据子问题的特点设计相应的算法求解，得到原问题的一个下界解。 s t e p 4 如果该下界解不是原问题的可行解，则构造拉格朗日松弛启发式算法使 其可行化，进而得到原问题的上界解。 s t e p 5 通过次梯度优化算法更新拉格朗日乘子，并求出新的下界解和上界解， 直到达到次梯度优化终止原则。 s t e p 6 将最优上界解作为原问题的最优解。 2 3 3 算法的优缺点 拉格朗日松弛算法的优点主要表现在以下四个方面： ( 1 ) 由于拉格朗日松弛算法可以将问题按照多种不同的形式进行分解，因此该 算法十分灵活。正是因为这种灵活性，该算法和其他算法相比，能够用来解决多种 不同的问题网； ( 2 ) 在求解的过程中，拉格朗日松弛算法可以将原问题分解成多个容易求解的 子问题，然后设计相应算法解决这些子问题，有助于问题的快速求解； ( 3 ) 在许多应用中，我们能够设计出基于拉格朗日松弛的启发式算法来求解复 杂的组合优化问题； ( 4 ) 拉格朗日松弛算法实现简单，不仅可以用来评价算法的效果，还可以和其 它算法混合使用，提高算法的效率。 拉格朗日松弛算法的缺陷主要体现在次梯度优化算法的性能上，由于它不是一 种单调递减算法，因此在迭代过程中往往会出现振荡现象【3 3 1 ，而且随着迭代次数的 增加，收敛速度会变得越来越慢。 9 硕士学位论文 m a s t e r st h e s i s 3 带软时间窗的l i r p 集成优化模型与算法研究 近些年来，计算机、医疗、装备制造、电站等行业经常面临设备使用中的零部 件损坏问题，而工程备件的损坏将导致整个生产经营活动的中断，因此备件物流系 统逐渐成为人们的研究热点。在备件物流市场，客户对备件服务的时效性极为关注， 在较短的时间内提供可修复备件是备件物流的焦点阴】。而备件物流系统中配送中心 不合理的选址、库存、运输决策会对提供备件的时间造成重要影响。因此，备件物 流系统优化方案必须综合考虑库存控制策略、配送中心布局、运输路线、服务时间 等因素。本章内容充分考虑了备件需求的随机性和时间紧迫性，从系统集成的角度 出发，建立了带软时间窗的备件物流系统l i r p 模型，在降低备件物流系统成本的 同时提高物流系统成本的时间响应性。 3 1 问题描述 一般而言，客户对备件的需求具有较大的偶然性，很难预测，而且需求量不大。 备件服务的物流成本和单位时间的缺货成本较高，不能体现规模经济的效应。早期 的备件物流网络规划的研究文献主要从库存管理的角度出发来探讨实施库存共享 技术的可行性，最新的研究成果已经逐渐转向集成规划领域，将战略层的物流网络 规划问题和战术层的库存管理问题整合起来作为一个整体进行研究。c o h n t 3 5 j 认为一 般的整数规划模型在对考虑仓库容量限制的备件物流网络进行规划时存在困难，因 此提出了一种复合变量模型规划法来对低需求、高成本的备件进行选址决策和库存 控制。m e h m e t 3 6 】研究了考虑时间约束的备件物流网络规划问题，通过非线性整数 规划模型解决了选址分配问题和库存控制问题，并通过实验证明了这种集成规划方 法优于传统的先选址后库存的规划方法。l o n a r d o 37 j 建立了一个考虑备件产量和成 本约束的备件物流网络随机线性规划模型，该模型将计划期分解成多个连续的时间 段，并将这些时间段作为变量引入模型中，通过实例演算，证明了该模型的有效性。 w o n g t 3 8 1 研究了单一产品，多设施的备件物流系统模型，该模型考虑了各设施之间 可以水平补货的情况，并设计了一个两阶段算法求解该模型。t a g a r a s