（系统工程专业论文）基于启发式算法的库存路径优化问题研究.pdf

中文摘要 摘要：供应商管理库存( v m i ) 思想的创建，为供应商通过统筹规划运输和库存计划 来解决运输和库存之间“效益悖反( t r a d e o f 0 的矛盾，实现降低物流成本的目标 提供了新的契机。本文所提出的库存路径问题( i r p ) 是从管理运筹学的研究视角出 发，通过关注库存和运输两个物流环节的集成优化，解决物流管理在作业操作层 面上的焦点问题如何制定库存管理计划和车辆配送路线安排计划。 目前，在国内无论是研究学者对库存路径问题( i r p ) 的理论探讨还是物流实践 者对综合考虑库存控制和运输路线计划的物流策略的实际应用在目前热的物流理 论研究和物流实践中都显得有些弱。因此，本文试图对库存路径问题( i r p ) 进行有 益的理论探讨，并展现理论探讨结论在实践中的应用。 论文首先在对大量相关文献进行总结提炼的基础上，分别回顾了国内、外对 库存路径问题的研究成果，总结了近年来有关求解库存路径问题所建立的基于启 发式理论的模型及算法。然后，借用模拟退火算法的理论和方法，分析与建立m t o 1 库存路径模型，利用启发式算法确定求解流程及关键环节，同时为了证明算法的 正确性，进行了算例分析。最后，在算例分析的基础上进行实例研究，佐证理论 探讨的结论并体现求解方案的有效性、各个成本要素中的对应关系以及解决方法 对制定实际配送作业计划的指导价值。 图1 6 幅，表l o 个，参考文献3 7 篇。 关键词：库存路径问题( i r p ) ；启发式算法；模拟退火算法( s a ) 分类号：u l l 6 2 a bs t r a c t a b s i r a c t ： v e n d o rm a n a g e di n v e n t o r y ( v m i ) p r o v i d e sa l ln e wc h a n c ef o rs u p p l i e r st o o v e r c o m et h ep r o b l e mo f “t r a d e o f f b e t w e e nt r a n s p o r t a t i o na n di n v e n t o r ya n dr e d u c e l o g i s t i c sc o s t sb ym e a n so fw h o l ep l a no ft r a n s p o r t a t i o na n di n v e n t o r y f r o mt h ea n g l e o fm a n a g e r i a lo p e r a t i o n a lr e s e a r c h ，t h ei n v e n t o r yr o u t i n gp r o b l e m ( i r p ) i nt h i sp a p e r i sd e v o t e dt os o l v e ，t a k i n gi n t oc o n s i d e r a t i o nt h ei n t e g r a t i o na n do p t ：i m i z a t i o no f i n v e n t o r ya n dt r a n s p o r t a t i o n ，i n v e n t o r ys u p p l e m e n ta n dv e h i c l er o u t i n gp r o b l e mw h i c h h a v et ob ed e t e r m i n e di np l a nf u n c t i o ns t e pa tt h el e v e lo fo p e r a t i o ni n1 0 百s t i e s m a n a g e m e n t i nc h i n a ，h o w e v e r ，w h e t h e rt h er e s e a r c ho ni i 心o rt h ea p p l i c a t i o ni nt h e l o g i s t i c ss t r a t e g i e si n v o l v i n gi n v e n t o r yc o n t r o la n dt r a n s p o r tr o u t i n ga p p e a rw e a ki n c u r r e n tr a p i d l yd e v e l o p i n gl o g i s t i c sr e s e a r c ha n dp r a c t i c e c o n s e q u e n t l y ，t h i sp a p e ri s m e a n tt od i s c u s si l 强t h e o r e t i c a l l y ，a n di l l u s t r a t et h ec o n c l u s i o no fd i s c u s s i o ni n p r a c t i c e i no r d e r t oa c h i e v et h i sg o a l ，t h i sp a p e ra r r a n g e sc o n t e n t sa sf o l l o w s i nt h ef i r s tp l a c e ，t h i sp a p e ri n t r o d u c e si t sr e s e a r c hb a c k g r o u n d ，t h e o r e t i c a la n d p r a c t i c a ls i g n i f i c a n c e i na d d i t i o n a l ，t h ea r t i c l er e v i e w e dd o m e s t i ca n df o r e i g n r e s e a r c h e so i li r pb a s e do nt h ec o n c l u s i o n sf r o ml o t so fc o r r e s p o n d i n gl i t e r a t u r e i nt h e m e a n w h i l e ，t h i sp h r a s ed e s c r i b et h ep r o b l e mw i l lb er e s o l v e da n db u i l d st h es t r u c t u r e o ft h ep a p e r s e c o n d l y ， i no r d e rt od e v e l o pa nu n d e r s t a n d i n go fi r p ， i t sr e s e a r c ho b j e c t s ， s p h e r ea n dc h a r a c t e r i s t i c so nt h eb a s i so ft h ea n a l y s i sa n ds u m m a r yo fc o r r e s p o n d i n g l i t e r a t u r e t h ep a p e rm a k e sas u m m a r yo fw i d e l yu s e dh e u r i s t i c st h e o r ya n di n t r o d u c e s i t sg e n e r a t i o n ，d e v e l o p m e n t ，m e c h a n i s ma n dc h a r a c t e r i s t i c si nd e t a i l t h i r d l y ，o n em t o - l m o d e lf o rl i 强i sb u i l d ；t h ea i ma tt h a tp r o b l e m ，t h ep a p e r c o n s t r u c t e da ni m p r o v e dh e u r i s t i ca l g o r i t h mt os o l v ei t t h e n ，t h ea r t i c l el i s t sa n e x a m p l eo ft h ea l g o r i t h mf o re x p l a i n i n gt h ed e t a i l e dp r o c e s s m o r e o v e r ，t h i sp a p e rt e s t i f i e st h ec o n c l u s i o n so ft h e o r e t i c a ld i s c u s s i o nb ya l o g i s t i c sc a s e ， a n di l l u s t r a t e st h ee f f i c i e n c yo fs o l u t i o n si ne v e r yp h a s e ，t h ed e c i s i o n c o n t i n u i t yb e t w e e np h a s e sa n dt h eg u i d a n c es i g n i f i c a n c eo ff i n a ls o l u t i o nt op r a c t i c a l d i s t r i b u t i o no p e r a t i o n k e y w o r d s ：i l 冲；h e u r i s t i cs e a r c h ； s a ：i a s s n 0 ：u 1 1 6 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：画禹破 导师签名： 签字同期：加g 年占月；日 签字日期：枷牌占矽日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：磁，穆诹 签字日期：矽。g年石月；日 5 2 致谢 本论文的工作是在我的导师王喜富教授的悉心指导下完成的，在论文的写作 过程中，王老师倾注了大量的心血，从论文的选题、资料查询、开题、研究到最 后的完稿，都提出了许多的宝贵意见。王老师严谨的治学态度和科学的工作方法 给了我极大的帮助和影响，在此衷心感谢两年来王老师对我的关心和指导。 王喜富教授悉心指导我完成了实验室的科研工作，在平时的学习生活中，王 老师时时关心着我，激励着我，教我要勤奋做事，踏实做人，他以自身做楷模， 为我指明了今后的奋斗方向，他广博的学识、严谨的治学态度和善于从宏观把握、 分析问题实质的方法，都给我留下深刻的印象，值得我永远学习，激励我不断进 取。再次向王老师表示衷心的谢意。 在撰写论文期间，同学们对我论文中的研究工作给予了热情帮助，在此向他 们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 同时，感谢审阅此论文的各位专家和评委，谢谢各位老师。 1 绪论 1 - 1 论文背景及选题意义 2 0 世纪9 0 年代以来，由于科学技术的不断进步和经济的全球化，以顾客为中 心的供应链管理面临着更为复杂的竞争环境，企业之间由单纯产品质量、性能方 面的竞争转向企业所在的供应链之间的竞争。传统地将企业看成独立个体的观点 早己过时，企业只有参与合作才能获得更大的竞争优势，才能有更大的生存空间。 供应链的管理理念强调企业应将有限的资源用于发展自身的核心竞争力。通过终 端客户需求的拉动，使得整个供应链上的信息流、物流、商流得以和谐的运作， 从而发挥整条供应链的最大效用，以达到提高企业的竞争力与适应力的目的。 在整个供应链管理中，被视为“第三利润源泉 的物流管理更是倍受企业和 学术界关注。现代物流管理的范围早己超出了单个企业的范畴，已向上、下游不 同企业联合协作、共同进行物流管理( 即供应链管理) 的方向发展。但在r m i ( r e t a i l e r m a n a g e di n v e n t o r y 零售商自己管理库存) 的传统库存管理模式运作中由于供应链中 信息在不同阶段之间传递的过程中发生扭曲，使得在供应链内，由零售商到供应 商订货量的波动逐层递增，即牛鞭效应( b u l l w h i pe f f e e 0 。 近年来，在国外出现了一种新的库存管理方法供应商管理用户库存方式 ( v e n d o rm a n a g e di n v e n t o r y ，v m i ) ，这种库存管理策略打破了传统的各自为政、 条块分割的库存管理模式，以系统的、集成的思想进行库存管理，使整个供应链 系统获得同步化的运作，增强了企业的敏捷性和响应性，解决了供应链中信息扭 曲的问题。从而有效地解决了牛鞭效应( b u l l w h i pe f f e c t ) 。 库存路径问题( i n v e n t o r yr o u t i n gp r o b l e m ，i r p ) 就是在如何联合优化配送和库存 这两个往往被独立考虑的物流环节的现实需求推动下成为崭新的研究领域，它是 实施v m i 策略过程中的核心问题，是企业节能增效的重要途径。 库存路径问题是对一系列已知需求量的客户，组织适当的行车线路进行服务， 在不违反任何约束条件下，优化路线使得总成本达到最小。有效地解决该问题可 以提高车辆的利用率，降低配送成本，提高配送时间的准确率，从而提高物流服 务水平。由于库存路径问题是典型的n p 难题，使用传统的优化方法很难得到问题 的最优解或满意解，因此构造高质量的启发式算法成为研究该问题的主要发展方 向。 1 2 库存路径问题的研究现状 随着发达国家供应链管理的升温，国外对库存路径问题( i r p ) 的研究越来越热， 而在国内，无论对库存路径问题的理论探讨还是物流策略的实际应用都还比较薄 弱。特别是在对于更加贴近现实的客户的库存路径问题更是寥寥无几。 1 2 1 国内研究现状 目前，国内有关库存和运输方面的研究文献比较少，但是这并不是说在国内 没有相关研究。事实上就研究对象和内容而言，在为数不多的有关库存运输联合 优化问题的研究文献中，有的文献已经涉及到i r p 问题。其中包括：系统工程学 报的崔雪丽，系统工程理论与实践的邹彤心1 ，以及系统工程理论与实践的符卓口1 等，这些文章大多都是在假设客户需求在计划期内已知的条件下进行研究的，并 且其考虑的计划水平一般为有限的一段时期( 一天或几天) 。 1 2 2 国外研究现状 国外对库存路径问题( r a p ) 的研究要早于国内，而且研究文献更为丰富。根据 计划的长度和需求类型可将这些研究文献分为以下几类： ( 1 ) 单日i r p 模型 单日i r p 模型就是计划期长度仅为一天( 又可以分为需求确定或随机需求两 种) 。f e d e r g r u e n 和z i p k i n ( 1 9 8 4 - - ， 4 1 将i r p 视为计划期为一天的规划问题，并利用求 解v r p 的方法来进行求解，这是有关随机需求i r p 问题的第一篇文献，其问题的 假设为有一个工厂，其可获得的产品库存是有限的，在运输成本、存货成本与缺 货成本总和最小的情况下，有效率的将产品分派给所有的顾客。因为可获得的产 品数量是有限的，在库存保管费用与缺货成本的平衡下，不是所有的顾客每天都 会分配到产品。因此作者将问题构建为非线性的整数规划问题，在模型里设置了 一个包含所有未被服务的顾客的虚拟空路线，并将非线性整数规划问题分解为两 个子问题：一个是库存分配( t a ) t 洒- j 题，其主要考虑的是库存保管费用与缺货成本最 小；另一个是对每一辆车的t s p 问题，其主要的考虑是使运输成本最少。在取得 一个初始可行解后。反复的将线路间的顾客作交换，对初始解进行了改善。在每 一次交换之后将会产生一个新的队问题与t s p 问题。这样求解的方式比一般标准 的v r p 问题需要更繁杂的计算。 f e d e r g r u e n ( 1 9 8 6 ) 1 5 在f e d e r g r u e n ( 1 9 8 4 ) t 4 一文的基础上将产品特定为易逝产 2 品，如粮食、血浆等，因此除之前考虑的成本之外，系统目标函数值还涉及到过 期成本( o u t o f - p u tc o s t ) 。论文给出了两类配送策略，第一类采用直接配送策略， 因此仅需通过单纯形法求解认问题就能得到原问题解；第二类则采用零担配送 ( m u l t is t o p ) 策略，通过v r p 问题处理得到原问题解。 g o l d e n ，a s s a d 和d a h l ( 1 9 8 4 ) t 6 】采用启发式方法解决周期为一天的i r p 问题， 即在充分满足所有客户库存需求要求的前提下使总成本最小。在开始求解前，首 先计算客户剩余库存与预期需求能力的比率，来定义客户的“需求迫切性若是 客户“需求迫切性 小于设定的标准值，此顾客将排除此次配送。其次，根据“需 求迫切性 与所需送货时间的最高比率，选择客户直接配送，通过反复迭代建立 一个大型t s p 。在总旅行时间符合最大旅行t m a x 的限制下，反复的进行t s p 的 求解，不断的加入新的顾客直到最大旅行时间的限制，或是没有新的顾客可以加 进来为止。在不允许送货不足的条件下( 即只要送货，必须完全满足收货客户的需 求) ，得到一组可行路径，共同构成最终的优化配送线路，若此条件无法满足，则 减少t m a x 的值，再使用上述启发式方法。 ( 2 ) 多日i r p 模型 多日i r p 模型就是计划期长度超过一天，但不超过一季度或一年( 又可以分为 需求确定或随机需求两种) 。d r o r 、b a l l 和g o l d e n ( 1 9 8 5 ) 7 】，d r o r 和t r u d e a u ( 1 9 9 6 ) t 8 】 研究了基于( s ，s ) 库存策略的以年为周期的随机需求i r p 问题；模型中将客户的需 求定义为独立同分布服从于j 下态分布的随机变量( i i d ，n o r m a ld i s t r i b u t i o n ) ，并且 考虑当前周期做出的决策对于该周期后的库存配送优化问题的影响，近而提出改 进方法，将i r p 分解为两阶段问题。他们利用周期内的客户日缺货概率，计算每 个客户的平均配送成本、期望缺货成本以及使总成本最小的最优配送周期t 。若t 在上述规划周期内，则在此周期内必须完成该客户的配送，并可计算出周期内每 天的成本e ，表示配送不是发生在日t 时，未来成本增加值的期望；若t 不在上 述规划周期之内，则可以计算出周期内的预期收益g ，它表示配送发生在周期内 的t 日时的收益。由此可以反映出短期计划决策对长期计划决策的影响。在第一阶 段，通过整数规划模型来解决以总成本( 折扣成本，d r o r 和t r u d e a u ( 1 9 9 6 ) 最小化为 目标的库存分配问题；第二阶段要解决的即是旅行商问题( t s p ) 或者是车辆调度问 题( v r p ) 。 上述方法在路径优化方面得到了t r u d e a u 和d r o r ( 1 9 9 2 ) t 9 】的改进，d r o r 和 l e v y ( 1 9 8 6 ) 1 0 】也用类似的方法提出了以周为周期的i r p 问题的解决方法，同时还运 用节点一弧互换( n o d e & a r ce x c h a n g e ) 方法减少计划期的成本。 d r o r 和b a l l ( 1 9 8 7 ) i l l j 将以年为周期转化为一个较短周期( 天) 的随机需求i r p 问 题，强调了短期决策对于长期成本的影响。基于此本文提出了一种混合整数规划， 3 并涉及了启发式算法进行了求解。 c a m p b d l ，c l a r k e 和k l e y w e g t ( 1 9 9 8 ) 【1 2 】假设顾客每天的需求是随机且彼此独立 的己知其联合概率密度函数为f ，供应商能够计算每个顾客，在时间点t 的存货水 准x 。，并且要考虑在实际应用上的限制，例如：车辆配送工作时间的限制、配送 到顾客点的时间窗限制、车容量与顾客储存空问的限制。由于顾客的需求为变动 的，所以顾客点可能会有缺货的情况发生，当发生缺货时给予其处罚成本，将缺 货视为流失的需求而不再进行补货。在最佳的配送策略下使期望的总成本最小( 或 是期望收益最大) 。 b a r d ，h u a n g ，j a i l l e t 和d r o r ( 1 9 9 8 ，2 0 0 2 ) t 1 3 】【1 4 】研究了一个基于( s ，s ) 库存 策略，计划期为两周的i r p s f ( i n v e n t o r yr o u t i n gp r o b l e ms f ) 问题，首先在第一 周确定每天服务的客户群，通过对客户群进行调整已达到每天需求量平衡，然后 在此基础上重复上述流程进行下一周的计划。此文特殊之处在于车辆在计划期内 可以在就近的卫星工厂装载货物，不需返回到配送中心。 ( 3 ) 无限期i r p 模型 无限期i r p 模型，也称为永久路线问题( p e r m a n e n tr o u t i n g ) ，是即一旦确定了 车辆的巡回路线，则在以后的配送服务中，车辆的行驶路线不会发生变化。l a r s o n ( 1 9 8 8 ) 和w e b b ( 1 9 9 5 ) t 1 5 】【1 6 】分别对战略型i r p 问题( s i r p ) 进行了研究。文章首先采 用客户需求的均值将问题转化为一个确定需求下的s i r p ，并设计了启发式算法对 最小车辆数进行了估计，而后设计了一个线性规划对估计值进行了修正得到了系 统长期运行的最小成本或最小的车队数量。 b a r n e s s c h u s t e r 和b a s s o k ( 1 9 9 7 ) t 1 7 】验证了直接配送策略的有效性，给出了长期 运行成本( 库存与配送成本之和) 的一个下界，通过模拟证明了当需求服从正态分布 且其均值与车辆的运载能力接近时，直接配送策略是一种好的运输策略。 q u ( 1 9 9 9 年) 【l8 】研究了一个多品种、车辆容量无限的随机需求i r p 问题，他建 立了基于( s ；正) 的多品种周期盘点库存策略与旅行商问题( t s p ) 结合的数学模型， 给出了求解的启发式算法，并给出了该问题的下界。 不同的研究文献除了对计划期长度以及需求类型这两个关键因素采用不同的 处理方式外，在“如何考虑短期决策对长期决策的影响”这一问题上也表现出较 大的差异性，从而也丰富了库存一路线问题( i r p ) 研究。 纵观i r p 的研究历史会发现有关i r p 研究呈现出如下的研究趋势： ( 1 ) 计划期长度增加。从早期的单同模型发展到多日模型乃至无限期模型； ( 2 ) 决策层次提高。从以作业层计划决策为主到兼顾战略层决策( 如供方需 要的车辆数目) ； ( 3 ) 需求特性更为复杂的。从研究确定需求i r p 问题到研究随机需求乃至 4 动态随机需求。 1 3 论文研究的主要内容 本文研究的是由多个供应商，一个中心仓库，一个单独的组装场和一支数量 可无限扩充的货车车队组成的i r p 问题。车队先由仓库出发，从多个供应商处收 集运输部件到组装厂，最后返回仓库，其中若不是特定时期需要的部件则储存在 仓库里，导致库存产生费用。随着单个货车所运货物数量的增加，运输的成本大 大减少，但是库存的成本也同时增加了，因此研究的目标是使库存总数量以及运 输成本最小化。 1 4 论文的结构 第一章是绪论部分，主要介绍库存路径问题研究的目的及意义，介绍了目前 国内外库存路径问题的研究现状。阐明了论文研究的主要内容，列出论文的体系 框架和各章主要内容。 第二章是基于启发式算法的库存路径问题的研究概述，先对库存路径问题进 行了模型化的分析，指出了研究的主要问题，对其研究特性作了重点描述。其次， 对启发式算法作了系统的阐述，介绍了启发式的求解过程，其次介绍了启发式的 研究策略，最后介绍了启发式方法的评价标准。之后详细阐述了模拟退火理论， 并对目前基于启发式算法研究库存路径问题的研究做了总结。 第三章是库存路径问题的启发式算法研究，分析了关于库存路径问题的模型 建立过程。利用以模拟退火理论为基础的启发式算法对模型进行探讨研究，理清 求解步骤，并详细介绍了求解库存路径问题的理论思想和实现步骤，并用流程图 和算法描述的形式展现出来。 第四章是库存路径问题在实际物流企业中的应用，通过一个典型的案例首先 提出建立相应的v m i 供应商库存管理，之后对v m i 的核心作业环节建立相应的库 存路径优化问题模型，并用前文相应的启发式算法进行求解，之后用图表对结果 进行详细的分析，从而证明了算法在实际应用中的可行性。 第五章陈述了研究的结论，提出了未来的展望。 5 2 基于启发式算法的库存路径问题的研究概述 2 1 库存路径问题 库存路径问题i r p ( i n v e n t o r yr o u t i n gp r o b l e mi r p ) 1 9 1 研究的中心就是：如何同 时优化运输和库存两个物流环节。但是，如何制定有效的库存补充和运输路线安 排计划来满足客户的需求并不是一项轻松的任务。尤其在客户数量较多、地域分 散的情况下，作业计划制定者将面临巨大的挑战。 2 1 1 库存路径问题( i r p ) 的描述 通常，库存路径问题( i r p ) 主要是研究这样一类问题：在有限( 或无限) 计划期 t 内，由一个供方向n 个客户提供配送服务，客户c 每天的需求量为u ，最大库存 容量为c ，初始库存为i ，有m 辆最大载重为q 的车辆供供方调度安排，在保证每 个客户不出现缺货的前提下使由供方和需方组成的物流系统在整个计划期内的运 作成本最小。 库存路径问题( i r p ) 计划决策者一般必须对三个主要问题进行决策： ( 1 ) 时间或频率 如果计划期长度己经确定，则需要决策在什么时候为哪些客户提供配送服务； 如果计划期长度未知，则需要决策在整个计划期内以什么样的频率为客户提供配 送服务。 ( 2 ) 配送量 在了解客户需求信息后，决策者需要确定在每次配送时为配送路线上每个客 户提供的配送量是多少。 ( 3 ) 运输路线 配送车辆选择怎样的运输路线依次访问不同的客户从而完成配送任务。 其中前两个决策主要考虑的是库存控制问题，第三个决策涉及运输路线安排 问题。 2 1 2 库存路径问题( i r p ) 研究特性 从本质上讲，库存路径问题( 1 r p ) 是库存控制和运输路线选择的集成优化问题， 是库存运输联合优化问题领域中的一个分支。其自有的研究特征使其区别于库存 运输联合优化决策家族中的其它问题。下面从7 个方面来介绍库存路线问题( i r p ) 6 的特性。 ( 1 ) 决策目标 从决策者进行决策时所要解决的问题来看，库存路线问题( i r p ) 主要解决客户 的配送时间或频率、配送量以及配送车辆的行驶路线及时间安排等几个问题。不 涉及诸如运输方式( 火车、航空、水运、汽车) 和运输批量等其它运输决策。 ( 2 ) 研究对象 研究对象是由供货方( 工厂、中央仓库、配送中心) 和需求方( 零售商、小的区 域性配送中心等) 组成的物流配送系统。根据不同的文献研究的侧重点不同，通常 可将物流系统进一步分为三种情况：r - s y s t e m ( r e t a i l e rs y s t e m ) 、d r s y s t e m ( d e p o t a n dr e t a i l e rs y s t e m ) 和d s y s t e m ( d e p o ts y s t e m ) 。建立在这三个物流系统上的各种 数学模型所涉及的运输优化决策基本相同，不同的是对有关库存方面的问题采用 了不同的处理方法。其中，r s y s t e m 是基于这样一种假设，即所有的需求方由一 个决策者( 或组织) 管理，属于集中型策略，不考虑供货方的库存保管费用和订货费 用，或供货方没有库存( 如沃尔玛的转运中心) ，但考虑需方库存费用。此时决策者 需要确定的是货物如何在需求点间分配( 库存分配) 和如何将货物运送到需求方( 运 输优化) 。d r - s y s t e m 则是在r - s y s t e m 的基础上要考虑供货方的库存保管费用和订 货费用，同时供货方的再订货点也是个决策变量。决策者一般管理由供需双方所 组成的整个物流系统。d s y s t e m 则是不考虑供方和需求方的库存费用，此费用由 供方或需求方自己负责。决策者往往以保证所有需求方不出现缺货为前提，以为 所有需求方补货的运输费用整体最小或系统的运营绩效最大为目标来规划数学模 型。 ( 3 ) 拓扑结构 拓扑结构指的是由供方和需方所组成的物流系统的网络拓扑结构，可能是单 对单( o n e - o n e ) 、单对多( o n e m a n y ) 、多对单( m a n y - o n e ) 或多对多( m a n y - m a n y ) 。 由于受求解算法的影响，目前有关库存路线问题研究的文献大多致力于研究拓扑 结构为单对多( o n e m a n y ) 的物流系统。 ( 4 ) 货物种类 指在供方和需求方之间运输的货物种类的数量，可以是一种货物或多种货物。 当处理多种货物种类时，一般也是首先对每种货物单独处理。 ( 5 ) 费用因素 主要涉及运输和库存费用。运输相关费用包括启用运输工具的固定费用及与 行驶距离相关的可变费用，有时也包括运载工具在需方停留的费用。库存相关费 用主要由货物保管费用、缺货损失费和订货费构成。 ( 6 ) 限制因素 7 涉及的其体问题不同，求解问题的限制也不同。一般都包含几个主要因素， 如运载工具的载重量，供方的供应能力，需方的存储能力，可执行运输任务的运 载工具数量，运载工具每天的最大行驶距离，需方的时间窗限制等。 ( 7 ) 需求特性 需求可分为三种情况：需方的需求量己知；需求量是随机的，但需求的概率 分布特性己知；需求特征完全未知。 在库存路径问题( i r p ) 的决策变量中虽然也涉及到车辆路线安排，但是库存路 径问题( r a p ) 与常见的车辆路线安排问题( v r p ) 有很大的不同。 首先，传统的车辆路线安排问题( v r p ) 只有在客户发生订货行为时发生，其解 决的主要问题是如何将提出订货要求的客户分配到车辆的巡回路线上以及在同一 巡回路线上车辆访问客户的先后顺序。而在库存路径问题( i r p ) 中，没有客户定单， 完全由供应商而不是客户决定配送的数量以及在计划期内的每一天为哪些客户补 充库存。虽然供应商具有完全独立自主的库存控制和车辆调度权利，但是供应商 要保证客户不会出现库存短缺现象，否则会损害供应商与客户之间的信任关系。 其次，库存路径问题( i r p ) 与车辆路线安排问题( v r p ) 的计划期长度不同。v l 冲 研究的是在给定的某一天内如何安排车辆行驶路线来提供配送服务，从而满足客 户的定单要求，模型的计划期大多为一天。在i r p 问题中，尽管有的文献研究的 是单日i r p 问题，但更多的文献研究的是计划期长度为一周或一个月乃至一年的 i r p 问题，不仅要确定每天访问的客户名单和配送的数量，而且要考虑当日所做出 的库存补充和车辆路线安排计划对以后作业计划的影响。由于供应商在选择服务 客户及确定客户库存补充数量的决策上具有较大的自由度，所以使求解该类问题 相对困难。 2 2 启发式理论 启发式源于英文单词h e u r i s t i c s ，启发式意为通过对过去经验的归纳推理以及 实验分析来解决问题的方法，即借助于某种直观推断或试探的方法。启发式方法 要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而较基本的模型 及算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径。 用启发式方法解决问题时强调“满意 ，常常是得到满意解，决策者就认为 可以了，而不去追求最优性和探求最优解。之所以这样，其原因是： ( 1 ) 很多问题不存在严格最优解( 例如目标之间矛盾的多目标问题) ，这时， 对目标的满意性常比最优性更能准确地描述人们地选择行为。 ( 2 ) 对有些问题，得到它的最有解所花的代价太大。 8 ( 3 ) 从实际决策的需要出发，有时要求解具有过高的精度没有意义。启发 式方法能够比较快地得到满意解，这对解决n p 难题来说有着不可估量的作用。 2 2 1 启发式方法的求解过程 用启发式方法求解问题是通过迭代过程实现的，因而需拟定出一套解的搜索 规则。为能得到满意解，在整个迭代过程中要不断吸取新的信息，必要时改变原 来拟定的不合适的策略，建立新的搜索规则，注意从失败中吸取教训，并逐步缩 小搜索范围。具体求解过程可参见图2 一l 启发式求解流程： ny 2 2 2 启发式策略 图2 - 1 启发式求解流程 f i g 2 - 1h e u r i s t i c ss o l u t i o nf l o w c h a r t 用启发式方法求解问题时，需采用一定的策略。下面列出几个常用的策略， 9 可根据问题的性质和要求选用。 ( 1 ) 逐步构造解策略 逐步构造解策略是指每次增加解的一个元素( 如节点、弧等) ，直到得到完整可 接受解。 ( 2 ) 改进解策略 从初始解( 初始解不一定可行) 开始，通过一系列替换分解和合并过程来逐渐修 正解，以提高解的可接受性。 ( 3 ) 数学规划策略 运用数学模型和优化算法，并通过对解的判断和修j 下以提高对问题的适用性， 常会得出高效的启发式算法。 ( 4 ) 分解策略 把一个复杂问题分解成一系列易于处理的子问题来求解，一个子问题的输出 常是下一个子问题的输入。 ( 5 ) 分割策略 把一个复杂的问题分割成一些平行的小的子问题，然后求解每一个子问题， 最后在相容原则下进行综合，把子问题的解合并成原问题的一个解。 ( 6 ) 可行解空间的限制策略 在某些情况下，把可行解集限制在一个可应用己存在高效算法的解集上。然 后再求解问题。 ( 7 ) 松弛策略 有时扩展问题的可行域( 即放松约束) 以得到一个易于处理的松弛问题，然后求 解松弛问题，就能直接得到或者容易得到原问题的一个可行解，然后再对得到的 解进行修正。 ( 8 ) 搜索学习策略 包括在解空间的定向搜索以及在搜索过程中发现和收集新的信息，并根据对 新信息的分重新确认或改变搜索方向。修正搜索参数，消去不必要的搜索范围， 以有效提高搜索效率，尽快获得问题的解。 在构造启发式算法时，一般都采用上述的某一种策略，或者是几种策略的组 合形式。有时在启发式算法的某一步也可采用优化算法来提高算法的精确度。 2 2 3 启发式方法的评价标准 对启发式方法，怎样来衡量它是优还是劣，主要有以下几个评价标准。 ( 1 ) 目标函数值与最优值的近似性 1 0 ( 2 ) 算法产生可行解的能力 测度启发式方法得到的解与最优化方法所得解的接近程度有许多方法，如实 例分析、统计分析、对“好 的及“差”的问题的求解结果以及许多经验分析方 法。测度时还应明确解的质量对问题特征的依赖关系。 ( 3 ) 运行时间和所需存贮量 启发式方法的好坏与算法所需的存贮量大小及求解问题的运行时间长短密切 相关。在测度时可应用概率分析、经验分析和对最坏情形下的分析等方法。 ( 4 ) 灵活性 指启发式方法能否容易地处理模型、约束和目标函数的变化。一个好的启发 式方法，一般来说应具有适应性广和比较灵活的特点。 ( 5 ) 实现难度 指编码的复杂程度及对数据的需求情况。 ( 6 ) 可靠性 启发式方法应具有进行灵敏度分析和产生解的界值的能力一个好的算法可以 使用户能利用得到的信息确定所得的解与最优解的接近程度，避免得出错误结果。 ( 7 ) 简洁性和可分析性 算法应该能够用简洁明了的语言陈述出来，而且易于分析。 ( 8 ) 交互式特性 在大多数情况下，算法都应便于人机交互式处理，以更好的反应决策者的愿 望。 2 3 模拟退火理论 2 3 1 模拟退火理论的原理 在热力学中，退火( a n n e a l i n g ) 现象是指物体逐渐降温的物理现象，温度越低， 物体的能量越低；温度足够低时，液体开始冷凝并结晶，在结晶状态时，系统的 能量状态达到最低，如图2 2 所示。这说明自然界在缓慢降温( 亦即退火) 时，可 以“找到 最低的能量状态：结晶。但是，这个过程中也存在一个问题，如果降 温过程仓促，下降的非常快( 即沾火，q u e n c h i n g ) 时，会导致不是最低能量状态 的非结晶体的出现。因此，与之相对，温度缓慢降低的过程，即退火是最理想的， 缓慢降温的过程有利于形成一个结构统一的晶体，这种更稳定的晶体结构使得金 属更加耐用。可以这样比喻，“慢工出细活 ，缓慢降温，使得物体分子在每一温 度时，能够有足够的时间找到自己的位置，则逐渐的，到最后可得到最低的能量 状态，同时系统达到最稳定的情况。【2 0 】【2 1 】这种完美的物理现象，是否能给人类在 寻求最优解( o p t i m a ls o l u t i o n ) 的道路上以启发呢? 美国物理学家n m e t r o p o l i s 等在1 9 5 3 年发表研究复杂系统、计算其中能量 分布的文章，他们使用蒙特卡罗模拟( m o n t ec a r l os i m u l a t i o n ) 计算多分子系统中 的能量分布。 后来，美国i b m 公司物理学家k i r k p a t r i e k 于1 9 8 3 年在科学上发表了一 篇颇具影响力的文章：“以模拟退火算法求最优解 ( o p t i m i z a t i o nb ys i m u l a t e d a n n e a l i n g ) 。他们借用了k i r k p a t r i c k 等人的方法探讨一种旋转态系统( s p i ng l a s s s y s t e m ) 时，发觉其物理系统的能量和一些组合优化问题的目标函数相当类似：即 寻求最低成本相似于寻求最低能量。于是，他们发展出以m e t r o p o l i s 方法为基本 的一种算法，可用于组合优化问题寻找最优解。k i r k p a t r i c k 等人受到m e t r o p o l i s 等 人用蒙特卡罗模拟的启发而创造了“模拟退火”这个名词，因为它和物体退火过 程相类似。寻找问题的最优解类似于寻找系统的最低能量。因为，系统降温时， 能量也逐渐下降，而同样意义地，问题的解也“下降 最小值( 最优解) 。所以模 拟退火算法来源于固体退火过程，将固体温度加至充分高，再让其徐徐冷却，加 温时，固体内部粒子随着温度上升变为无序态，内能增大，而徐徐冷却时粒子渐 趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 表2 1 物理过程与优化过程的对比 t a b l e2 - 1c o m p a r i s o no f p h y s i c a la n do p t i m i z a t i o np r o c e s s 缓二纛纛。纛物理过程，鬟：篡纛纛；， t 。：薹趸z 麓i 毫z 量。，j 镰专￥j 譬器。量纛：。k 。：甏 状态可行解 菱。：量：，。，三一，甚乏鲢，一? ：寥，： 。i j 。i 。j 麓麓篓纛j 毽皤馥z ? ：- | ? ? 沾火局部搜索 k 纛磊琵纛乏篡纛，退火。巍；二募纛。二滋。自。! 纛蠡鑫菇刍模拟邋：怒；。i 纛纛。i 纛纛么 豢 囊 图2 - 2 有缺陷的固体转变为晶体结构 f i g2 - 2f r o ms o l i dt oc r y s t a l 1 2 2 3 2 退火过程的物理图像 在加热固体时，固体粒子的热运动不断加强，随着温度的升高，粒子与其平 衡位置的偏离越来越大。当温度升至溶解温度后，固体的规则性被彻底破坏，固 体溶解为液体，粒子排序从较为有序的结晶态转变为无序的液态，这个过程称为 溶解。溶解过程的目的是消除系统中原先可能存在的非均匀状态，随后进行的冷 却过程以某一平衡态为使点。冷却时，液体粒子的热运动渐渐减弱，随着温度的 徐徐降低，粒子运动渐趋有序。当温度降至结晶温度后，粒子运动变为围绕晶体 格点的微小振动，液体凝固成固体的晶态，这个过程成为退火。退火过程之所以 必须徐徐进行，是为了使系统在每一温度下都达到平衡态，最终达到固体的基态。 退火过程中系统的熵值不断减小，系统能量也随温度的降低趋于最小值。冷却时 若急剧降温，则引起沾火效应，即固体只能冷凝为非均匀的亚稳态，系统能量也 不会达到最小值。 退火过程中系统在每一温度下达到平衡态的过程，可以用封闭系统的等温过 程来描述。根据b o l t z m a n n 有序性原理，退火过程遵循应用于平衡封闭系统的热 力学定律一自由能减少定律： “对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变 化总是朝着自由能减少的方向进行，当自由