（应用数学专业论文）基于固定分区策略的库存路径问题研究.pdf

基于固定分区策略的库存路径问题研究 摘要 本文的研究内容来源于国家自然科学基金( 7 0 7 7 1 0 3 4 ) ：基于非一体化供应 链的库存与配送协调模型与方法研究。 库存路径问题是在两级供应链系统中同时研究库存与运输两方面问题，货 物通过一群有车载容量限制的货车由供应商运到零售商处。在供应链管理的不 同阶段都能够使用i r p ，可以提高系统的性能，降低供应链成本。 本文主要针对由单个供应商和多个零售商组成的两级供应链系统，分别研 究一体化供应链的p o t 时间订货周期策略、整数倍时间订货周期策略以及非一 体化i r p 的协调问题。 针对一体化的两级供应链系统，首先研究了在需求确定的情形下，供应商 对零售商进行固定分区，并将传统的相同区域相同p o t 订货周期的策略进行延 伸，设计出相同区域不同p o t 订货周期的新方法，从而达到降低整个供应链成 本的效果。其次在比较供应商与零售商订货周期的大小关系后，通过引入周期 比例向量，设计了一个全新的整数倍时间策略，给出了详细的理论分析，证明 该策略是最优的整数倍时间策略。 针对非一体化的两级供应链系统，在比较单独订货和联合订货的费用情况 下，得出协调的必要性，采用量折扣策略对整个供应链进行了协调。 算例验证了以上策略在处理库存路径问题方面的有效性。 关键词：库存路径问题；供应商管理库存；订货周期；量折扣 r e s e a r c ho ni n v e n t o r yr o u t i n gp r o b l e m b a s e do nf i x e dp a r t i t i o np o l i c y a b s t r a c t t h er e s e a r c hc o n t e n to ft h i sp a p e rc o m e sf r o mt h en a t i o n a ln a t u r a ls c i e n c e f o u n d a t i o n ( 7 0 7 710 3 4 ) i n v e n t o r yr o u t i n gp r o b l e mr e s e a r c h e si n v e n t o r yp r o b l e ma n dt r a n s p o r t a t i o n p r o b l e mi nt w o e c h e l o ns u p p l yc h a i ns y s t e m t h ep r o d u c t s a r ed e l i v e r e dt ot h e r e t a i l e r sb yaf l e e to fv e h i c l e sw i t hl i m i t e dc a p a c i t y i r pc a nb eu s e di nd i f f e r e n t s t a g e so fs u p p l yc h a i nm a n a g e m e n t i tc a ni m p r o v et h ep e r f o r m a n c eo f t h es y s t e m p e r f o r m a n c ea n dr e d u c et h ec o s to fs u p p l yc h a i n f o rat w o e c h e l o ns u p p l yc h a i ns y s t e mm a d eo fs i n g l e s u p p l i e rm u l t i 。r e t a i l e r , t h ep a p e rs e p a r a t e l ys t u d i e sp o w e r - o f - t w oa n di n t e g e r - r a t i op o l i c i e si ni n t e g r a t e d s u p p l yc h a i n ，s t u d i e sc o o r d i n a t i o np r o b l e mi nn o n - i n t e g r a t e ds u p p l yc h a i n f o ra ni n t e g r a t e dt w o - e c h e l o ns u p p l yc h a i ns y s t e m ，t h ep a p e rf i r s t l yd e s i g n sa r e g i o np a r t i t i o na l g o r i t h mf o rt h er e t a i l e r s w ee x t e n dt r a d i t i o n a lp o w e r - o f - t w o r e p l e n i s h m e n ti n t e r v a ls t r a t e g y w h i c ho n er e g i o no n ei n t e r v a l ，a n dd e s i g na d i f f e r e n tr e p l e n i s h m e n ti n t e r v a lp o l i c yi nt h es a m er e g i o n b yt h i sw a y ，t h ec o s to f t h ew h o l es u p p l yc h a i nw a sr e d u c e d s e c o n d l y ，t h ep a p e rc o m p a r e s t h e r e p l e n i s h m e n ti n t e r v a lb e t w e e nr e t a i l e r sa n dt h es u p p l i e r b yu s i n gi n t e r v a l r a t i o 4 v e c t o rw ed e s i g nan e wi n t e g e r - r a t i op o l i c y w i t hap a r t i c u l a rt h e o r e t i c a la n a l y s i s ，i t i sp r o v e dt h a tt h i ss t r a t e g yi st h eo p t i m a lo n e f o ran o n i n t e g r a t e dt w o e c h e l o ns u p p l yc h a i ns y s t e m ，b yc o m p a r e dt h ec o s t b e t w e e ni n d i v i d u a lo r d e ra n du n i t e do r d e r ，w ek n o wt h en e c e s s i t yo fc o o r d i n a t i o n ， a n du s eq u a n t i t yd i s c o u n tm e c h a n i s mt oc o o r d i n a t et h ew h o l es u p p l yc h a i n n u m e r i c a le x p e r i m e n tv e r i f i e st h ee f f e c t i v e n e s so ft h ea b o v ep o l i c i e s i n d e a l i n gw i t hi n v e n t o r yr o u t i n gp r o b l e m k e y w o r d s ：i n v e n t o r yr o u t i n gp r o b l e m ；v e n d o rm a n a g e di n v e n t o r y ；r e p l e n i s h m e n t i n t e r v a l ；q u a n t i t yd i s c o u n t i i 表2 1 表3 1 表4 1 表4 2 表4 3 表4 4 列表清单 p o t 策略下相同与不同订货周期费用比较1 4 i r 策略与p o t 策略费用比较2 3 单独订货与联合订货费用比较2 6 协调前后费用比较2 8 供应链协调前后数据比较2 9 联合订货与协调订货路径比较2 9 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得 金目曼王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：奚飞 签字日期：刃。7 年? 月咿日 学位论文版权使用授权书 本学位论文作者完全了解金g 曼王些太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授权金魍王些太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：要飞 签字日期：刃。7 年年月7 日 e l j 学位论文作者毕业后去向： 工作单位： 通讯地址： i l l 导师签名： 夕司疵参 签字日期山声尹月 电话： 邮编： 致谢 时光飞逝，三年的硕士学习生活转眼即将结束，这三年宝贵的时间是我人 生的重大转折点也是新的起点。我首先要衷心感谢我的导师周永务教授，周老 师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚 师德，朴实无华、平易近人的人格魅力深深地影响了我，承蒙恩师的悉心指导 和敦促，为我们营造了良好的学习氛围，我才能顺利地完成论文的研究工作。 除了做学问，周老师还时时教育我们要踏实工作、诚实做人。在此谨向周老师 表示衷心的感谢和深深的敬意。 完成论文期间，还得到王圣东师兄、闵杰师兄、赵菊老师、刘桂庆老师和 张芬蕙老师的倾力帮助，在此感谢各位在繁忙之中不厌其烦的指点和支持。 另外还要特别感谢我身旁的同窗好友马成、张凯清、丁虹、裴红云、梁培 培、孟令全、廖金稳、吴丽娜、杨玲玲以及姚卫坤、朱晓玲等师弟师妹们，谢 谢他们在我求学期间给予的鼎立支持与无私帮助。 感谢数学系的老师们多年来的教导和帮助，感谢管理学院为我们提供如此 优越的学习环境! 感谢多年来含辛茹苦将我养育成人的父母，是他们无私的关怀和鼓励让我 能顺利的完成我的研究生学业。 i l l 奚飞 2 0 0 9 年2 月 第一章绪论 1 1 库存路径问题简介 传统各自为政的库存管理方法难以适应快速响应客户需求的供应链管理环 境，导致供应链总成本的增加，制约着整体运行的优化，削弱了企业竞争优势。 供应商管理库存( v e n d o rm a n a g e di n v e n t o r y ，v m i ) 这一新兴的供应链管理库存 思想改变了这一状况，由数目有限的上游企业对众多下游企业的流通库存进行 统一管理和控制，主动安排合理的补货，降低供应链上供需双方的运作成本。 v m i 是个复杂的大系统，具体运作需要相当繁杂的作业来制定客户补货策略和 车辆调度计划，避免出现缺货的情况，发生潜在销售损失的风险，或是出现货 物囤积过多，造成多余的库存维持费用，这类规划最优补货策略的问题一一库 存路径问题( 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 管理模式下的核心问 题之一。 i r p 问题实质上是库存控制与运输计划之间的协调，它将隔断的信息孤岛 集成起来，在供应商与客户之间架起信息协调桥梁，在单个供应商对多个分散 客户库存进行统一管理的模式下，制定使得供应商的运输成本与客户库存成本 总和最低的最佳运输计划和最优库存策略，这里的成本包括订货成本、库存成 本、缺货损失成本和运输成本等。 由于i r p 问题的复杂性，使得对该问题的分类种类较多。可以按配送时间 分为按频率配送和按时间间隔配送；可以按决策层次分为战略层，战术层；按 计划周期长度分为单周期、简单长期和长期；按需求类型分为确定型与随机型； 按产品种类分为单产品和多产品：按路径分为静态和动态；按拓扑结构分为一 对一、一对多和多对多；按时间特性分为计划期和带时间窗；按车辆因素分为 车载数量和承载能力。 一般来说，不同的实际问题有其重点要解决的关键决策变量，但总的来说 库存路径问题所需解决的要点有以下四个方面： 1 ) 补货频率及补货时刻。在配送策略上，需要确定在整个计划期内以什么 样的补货频率为客户补充货源；若可确定具体的补货时刻，则需要决策何时为 客户提供配送服务是最合适的。 2 ) 所需车辆数及配送区域的确定。在具体实施配送计划之前，必须首先确 定所需的车辆数及每辆车的配送范围。启用车辆数太多，因对每辆车都要付出 车辆固定启动费用和可变行驶费用，从而增加总的运输费用；启用车辆数太少， 则会因受制于运输车辆的总的装载量而导致每辆车的行驶线路过长。在确定所 需车辆数时往往是与确定每辆车的配送范围同时进行的。 3 ) 最优配送量的确定。在具体实施配送之前，必须确定好每个客户点的最 优配送量。 4 ) 运输线路的确定。确定了每辆车的配送对象以后，若需要联合配送，则 需要决策每辆车的最优行驶线路，该线路满足：既能完成配送任务，又能使总 的运输费用达到最小。 1 2 固定分区法简介 固定分区法( f i x e dp a r t i t i o np o l i c y ，f p p ) 是研究库存路径问题的一种非常有 效的方法。所谓f p p 策略就是预先将客户划分到不同区域中，形成策略集， 对每个分区指派一辆车送货。即：1 ) 将分布于某区域的所有客户划分到一系列 子区域中，对子区域的服务( 送货) 是彼此独立的，2 ) 当某个子区域中的一个 客户被服务时，此区域中的其它客户也须同时依次得到服务，也就是每个子区 域中的所有客户都采用相同的配送频率。在考虑车辆运载能力的前提下，矽中 的最优策略是指具有最小的平均总库存和运输费用的策略。确定矽的最优策略 显然是n p 难题，因为这需要寻找一个供货方与某个区域中的所有客户之间的 哈密尔顿回路。 但是，以客户数和最优的哈密尔顿回路长度表达的每个区域的长期平均费 用结构非常类似于e o q 问题的费用结构。在库存控制问题的研究中，利用经济 订货批量( e o q ) 来确定最佳的库存策略是一种常用和有效的方法。实际上e o q 公式所求得的两个主要指标就是最佳的一次订货量和订货时间间隔，比较而言， 这有些类似于战术库存路径联合优化问题最终希望得到的结果中的主要指标， 它们分别被称为最佳的配送量和配送周期。此外，最优的运输策略也是战术库 存路径联合优化问题需要给出的。实质上这两类问题的主要区别在于所研究对 象的不同。库存控制问题是针对仅由仓库构成的系统而言的，并不涉及具体的 运输优化，而战术库存路径联合优化问题所研究的系统是由一个仓库和n 个客 户( 如零售商、批发商等) 组成的。在这个系统中，需要确定的是库存如何经济 合理地分配给每个客户，使这个系统整体的性能最优。所以利用费用函数这样 的结构特性，无论是从建模角度还是从算法设计角度，都使得处理库存路径问 题变得简单些。 因此，采用基于f p p 的方法求解库存路径问题的过程可分为3 个阶段：1 ) 对欲研究区域的所有客户进行划分，形成一组包含某些客户的子区域。划分的 标准可以是距离等；2 ) 对每一子区域，采用某种求解t s p 问题的算法确定最优 的车辆行驶路线及路线长度；3 ) 将运费看作一固定费用，采用变形e o q 公式确 定每一子区域的最优配送量和配送频率。 1 3 库存路径问题的国内外研究现状 f e d e r g r u e n 和z i p k i n i l l 在1 9 8 4 年的文章中，称他们的研究是首次用一个模 型同时表述这两个问题。实际上，关于此类问题的论述最早出现在7 0 年代末， 如h e r r o n l e l 2 1 在1 9 7 9 年曾论述过同时优化库存和路径问题的重要性和由之所 2 带来的经济效益，但并没有提出具体的解决办法。可以说对于库存路径问题的 广泛研究是从8 0 年代开始的。 国内关于i r p 的研究较少。文献【3 】提到了此类问题在配送系统设计中的重 要性，但是没有具体进行研究。文献 4 】编译了一篇关于配送系统设计中的选址、 运输和库存综合决策方面的文章侧重点在于运输方案的选择。下面将国外关于 i r p 问题的代表性研究成果和解决方法进行简单的介绍。 1 ) 以一天为周期的问题 f e d e r g r u e n 和z i p k i n l l l 将i r p 视为计划期为一天的规划问题，并利用求解 v r p 的方法来求解。这是关于i r p 问题的第一篇文章，其问题的假设为有一个 工厂，其可获得的产品库存是有限的，在运输成本、库存成本与缺货成本综合 最小的情况下，有效率的将产品分配给所有的顾客。因为可获得的产品数量有 限，在库存保管费用与缺货成本平衡下，不是所有的顾客每天都分配到产品。 因此作者将问题建构为非线性的整数规划问题，在模型里设置了一个包含所有 未被服务的顾客的虚拟空线路，并将非线性整数规划为您提分解为两个子问题： 一个是库存分配问题，其主要考虑的是库存保管费用与缺货成本最小；另一个 是对每一辆车的t s p 问题，其主要考虑的是使运输成本最少。在取得一个初始 可行解后，反复将线路间的顾客作交换，对初始解进行了改善。在每一次交换 之后将会产生一个新的库存分配问题与t s p 问题。这样求解的方式比一般标准 的v r p 问题需要更复杂的计算。 f e d e r g r u e n 5 1 则在f e d e r g r u e n 和z i p k i n q 一文的基础上将产品特定为易逝 品，如粮食、血液等，因此除之前考虑的成本之外，系统目标函数值还设计到 过期成本。论文给出了两类配送策略，第一类采用直接配送策略，因此仅需要 通过单纯形法求解库存分配问题就能得到原问题解；第二类采用零担配送策略， 通过v r p 问题出来得到原问题解。 g o l d e n ，a s s a d 和d a h l t 6 】采用启发式算法解决周期为一天的i r p 问题，即 在充分满足所有顾客库存需求的前提下使总成本最小。在开始求解前，首先计 算客户剩余库存与预期需求能力的比率，来定义客户的“需求紧迫性 。若是客 户“需求紧迫性”小于设定的标准值，此顾客将排除此次配送。其次，根据“需 求紧迫性 与所需送货时间的最高比率，选择客户直接配送，通过反复迭代建 立一个大型的t s p 。在总旅行时间符合最大旅行时间的限制下，反复进行t s p 求解，不断的加入新的顾客直到最大旅行时间的限制，或是没有新的顾客可以 加进来为止。在不允许送货不足的条件下，得到一组可行路径，共同构成最终 的优化配送线路；若此条件无法满足，则减少最大旅行时间的值，再使用上述 启发式方法。 c h i e n 7 j 等研究的尽管也是周期为一天的问题，但其不将每一天视为独立的 时间周期，而是用前一天的优化结果调整次日的收入，模拟连续几天的库存和 运输情况，通过单位送货收益和单位缺货损失计算日利润。在建立的混合整数 规划模型中，以日利润最大化为目标，并通过拉格朗日松弛法求解。 2 ) 简单长时间 所谓简单长时间是指在有限周期的前提下进行优化，而后以上述有限周期 为基数进行周期的滚动，进而得到类似与无限周期的结果，大量研究集中在这 种简单长周期的处理方式上。 d r o r 、b a l l 和g o l d e n 引，d r o r 和t r u d e a u 9 j 研究了基于( j ，s ) 库存策略的以 年为周期的随机需求i r p 问题；模型中将客户的需求定义为独立同分布服从于 正态分布的随机变量，并且考虑当前周期做出的决策对于该周期后的库存路径 问题的影响，进而提出改进方法，将i r p 分解为两阶段问题。他们利用周期内 的客户日缺货概率，计算每个客户的平均配送成本、期望缺货成本以及使总成 本最小的最优配送周期。若在上述规划周期内，则在此周期内必须完成该客户 的配送，如果某一客户不在最佳补货日期补货而是在第二天，则用表示其引起 的未来费用增加值。如果落在短期计划区外，则用表示在短期计划内的第天为 客户补货带来的未来收益增加值。通过还可以反映出短期计划决策对长期计划 决策的影响。在第一阶段，通过整数规划模型来解决以总成本最小化为目标的 库存路径问题；第二阶段要解决的即是旅行商问题或者是车辆调度问题。 上述方法在路径优化方面得到了t r u d e a u 和d r o r 1 0 j 的改进，d r o r 和l e v y 1 1 j 也用类似的方法提出以周为周期的i r p 问题的解决方法，同时还运用节点弧互 换方法减少计划期的成本。 d r o r 和b a l l 1 2 】将以年为周期转化为一个较短周期的随机需求i r p 问题，强 调短期据称对于长期成本的影响。基于此作者提出了一种混合整数规划，并涉 及了启发式算法进行了求解。 c a m p b e l l ，c l a r k e 和k l e y w e g t t l 3 】假设顾客每天的需求是随机且彼此独立的， 已知其联合概率密度函数为f ，供应商能够计算每个顾客n 在时间点t 的存活 水准。并且要考虑在实际应用上的限制，例如：车辆配送时间的限制、配送到 顾客点的时间窗限制、车载容量与顾客存储空间的限制。由于顾客的需求为变 动的，所以顾客点可能会有缺货情况发生，当发生缺货时给予其处罚，将缺货 视为流失的需求而不再进行补货。在最佳的配送策略下使用期望的总成本最小 ( 或是期望收益最大) 。 b a r d ，h u a n g ，j a i l l e t 和d r o r 1 4 , i s 研究了一个基于( s ，s ) 库存策略，计划期为两 周的i r p s f 问题，首先在第一周确定每天服务的客户群，通过对客户群进行调 整已达到每天需求量平衡，然后在此基础上重复上述流程进行下一周的计划此 文特殊之处在于车辆在计划期内可以在就近的卫星工厂装载货物，不需返回到 配送中心。 g a l l e g o 和s i m c h i l e v i 1 6 】强调了直接配送的优势，而h a l l 1 7 则认为多次停 4 留的路径策略还可以提供更多的节省。e 1 一h o u s s a i n e 1 8 】在客户点不允许缺货的 前提下，采用传统的e o q 策略管理客户点的库存，但是在解决路径问题时，在 上述两种观点的前提下，引入了更新的车辆多线路的概念，并采用列生成算法 对其进行求解。r u s d i a n s y a h t l 9 】在带时间窗的周期车辆路径问题的基础上，提出 了一个新的i r p 模型。该模型被称为库存和带时间窗的周期车辆路径问题的整 合( i n t e g r a t e di n v e n t o r ya n dp e r i o d i cv e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s ， 简称i p v r p t w ) 。其目标是最小化一段时间内的平均库存费用和运输费用之和。 文中将客户点的访问频率作为决策变量，并且为了保持算法的稳定性，引入固 定间隔性求解一段时期内客户点的配送频率，并采用启发式算法求解该 i p v r p t w 问题。 3 ) 长( 无限) 周期 l a r s o n 2 0 1 和w e b b 2 l 】分别对战略型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 2 2 】验证了直接配送策略的有效性，给出了长期运 行成本( 库存与配送成本之和) 的一个下界，通过模拟证明了当需求服从正态分 布且其均值与车辆的运载能力接近时，直接配送策略是一种好的运输策略。 q u 2 3 】研究了一个多品种、车辆容量无限的随机需求i r p 问题，他建立了基于 ( s ，z ) 的多品种周期盘点库存策略与旅行商问题( t s p ) 结合的数学模型，给出 了求解的启发式算法，并给出了该问题的下界。 对于固定分区策略国外也有很多的学者对其进行了研究。b a i t a 和 u k o v i c h 2 4 1 较早的介绍了固定分区策略。a n i l y 和lf e d e r g r u e n 2 5 , 2 6 1 研究了一类客 户( 该文中指零售商) 需求确定、无限时间长度的库存路径联合优化问题，并且 假设每个客户的需求率不小于1 。文中首先将所有客户的需求简化为具有相同需 求率的n 个需求点，然后通过一个所谓的扇形区域划分方法来得到对整个服务 区域一组划分。当客户到供货方的距离具有独立同分布的特性，且需求点的总 数足够大时，文中所设计的算法是渐近最优的，计算复杂度为o ( n l o g n ) 。 a n i l y 2 7 】等采用f p p 方法研究了一个单物品，从单源点到多汇点的配送问 题。在文献 2 5 】的基础上，他们设计了在集中渐近最优的启发式算法。首先 是对所有零售商的总需求点进行分组，与文献【2 5 】不同的是在本文中以距离和 库存保管费用的比率而非仅用客户的地理分布特征作为标准，然后再将每组划 分为不同的子区域。研究的目标是得到使系统长期运行的平均运费和库存费最 小的运输策略和库存策略。关于文中所提启发式算法的渐近最优性的理论基础， a n i l y 和f e d e r g r u e n 列j 进行了论述。 g a l l e g o 和s i m c h i l e v i 2 9 】为整体需求设计了一个特定的策略被称为直接送 货策略。根据这个策略每个零售商被单独服务且采用最优的补货频率。这样就 不存在将不同的零售商分到一条路径的想法了。作者指出虽然这个策略很简单， 但是只要每个零售商的订货量大于车载的7 1 时这个策略的成本就可以比最小 策略成本节省6 。b r a m e l 和s i m c h i l e v i t 3 0 j 发展了启发式算法并设计了一个有 效的f p p 策略。他们的启发式算法是基于详细说明分区问题为布局问题，为方 便地选择成本和参数，被称为能力集中布局问题。这个解决布局问题的方法通 过一系列计算实例显示是有效的。这个问题还有其他一些方法和分析，如h e r e r 和r o u n d y 3 1j 考虑了采用p o w e r o f - t w o 策略解决不受车载限制问题。 v i s h w a n a t h a n 和m a t h u r 3 2 l 发展了这个方法解决多产品问题。 固定分区策略能引起大家的兴趣有两个主要原因：一是简单的结构，二是 能够节省成本。其简单性是由于每个零售商接受服务都遵从等距的时间间隔， 每个车子服务相同的零售商时载货都相同。除此之外，文献 3 0 】的计算结果表 明只要严格执行c h a n l 3 3 】等的方式就可以节省成本。他们考虑了f p p 并且得出 最优的f p p 比最小策略可以节省4 1 的成本。文献【3 3 】同样证明了在特定条件 下，f p p 策略是近似最优的。 1 4 论文研究主要问题 1 ) 供应商与零售商订货周期的计算。在以往研究中，关于库存路径问题的 订货周期分为p o t 时间策略和整数倍时间策略两种，但是对于p o t 时间策略， 大部分学者只考虑在一个固定分区中所有的零售商都采用相同的订货周期，而 相同的订货周期必然使一些订货周期长的零售商运输费用增加，使那些订货周 期短的零售商库存费用增加。这时我们就考虑让每个固定分区中的零售商的订 货周期不同，从而避免这种情况的发生，进而降低整个供应链的费用。对于整 数倍时间策略，以往的文献中一直没有找到最优的策略，本文将对此予以考虑。 2 ) 非一体化库存路径问题的协调。目前对非一体化的库存路径问题的研究 还很少，行之有效的协调策略更是寥寥，本文将考虑用量折扣来协调这个问题。 3 ) 固定分区策略的寻求。分区策略有根据零售商的订货周期来分，将周期 相近的分到一起，也有根据零售商地理位置进行分区，将地理位置相近的分到 一起。但这都不是最有效的方法，本文将综合考虑结合这两种方法。 下面介绍一下本文的结构安排。本文共分五章，主要内容归纳如下： 第一章绪论。对库存路径问题、固定分区法进行了简单阐述，并给出了 本文所要解决的主要问题。 第二章p o t 时间策略下的库存路径问题研究。本章针对单供应商多零售 商的两级供应链系统，给出了零售商的固定分区法，研究了同一分区中零售商 采用相同订货周期策略和不同订货周期策略。 第三章整数倍时间策略下的库存路径问题研究。本章在固定分区的基础 6 上确定出零售商订货周期与供应商订货周期的大小关系，通过引入周期比例向 量，设计了一个最优的整数倍时间策略。 第四章非一体化库存路径问题研究。对非一体化的库存路径问题设计量 折扣策略，协调整个供应链。 第五章总结与展望。总结了全文的做的主要工作，指出本文的不足之处， 并提出有待研究的方向。 7 第二章p o t 时间策略下的库存路径问题研究 2 1 问题的提出 随着供应链协调在今天不断被重视，库存与运输这两个以往被单独考虑的 问题在近年来逐渐被联合起来，这就形成了库存路径问题。i r p 所追求的目标 是在综合平衡运输费用和库存费用的前提下，来优化物流系统，确定系统范围 的运输方案和库存策略。i r p 思想在不同决策层次的具体应用会因具体问题的 不同而不同，但可以肯定的一点是基于联合优化的决策必然会提高系统的性能， 无论是在减少费用支出方面还是在提高作业效率方面。 以往的学者在使用p o t 时间策略解决i r p 问题时大部分是将零售商进行分 区后让每一块中的零售商都采用相同的订货周期，然而事实上由于零售商的订 货周期的差异性，必然使那些订货周期长的零售商缩短订货周期，这样的零售 商订货费用就会增加，而那些订货周期短的零售商就要延长订货周期，其库存 费用就会增加。为避免这种情况的发生，本章将采用一种不同订货周期的方法， 让同一块中的零售商采用不同的订货周期来优化这个问题。 本章考虑一个由单个供应商和多个零售商组成的两级供应链系统。运输成 本由零售商承担。以运输费用、订货费用和库存费用之和最小为目标，构建配 送中心一体化决策模型，对客户点的库存方案和配送中心的配送方案进行整体 优化。该系统的主要假定如下； ( 1 ) 供应商具有仓储和运输功能，并且由供应商决策整个供应链： ( 2 ) 零售商不允许发生缺货，且需求率是确定的； ( 3 ) 不考虑零售商的库容约束； ( 4 ) 供应商有多辆相同型号有车载容量限制的车辆用于配送，且每条路径只允 许一辆车进行配货。 本章主要符号如下： 刀一一零售商个数； 一一分区后区域个数； 瓦一一供应商单位次数的订货成本； k 一一零售商f 单位次数的订货成本，= 1 ，2 ，玎) ； 谚一一零售商f 单位时间的需求率，( f = 1 ，2 ，刀) ； t 一一零售商f 与供应商之间的距离，( f = 1 ，2 ，刀) ； p 一一单位距离的运输费用( 本文设为1 ) ； y 一一车载容量； 一一供应商单位时间单位数量的库存成本； 危一一零售商f 单位时间单位数量的库存成本，( 扛l ，2 ，刀) ； r ，一一第条路径，( 歹= 1 ，2 ，) ； r f 一一路径r ，的t s p 路径长度，( 歹= 1 ，2 ，n ) ； 8 瓦一一供应商的订货周期； 弓一一区域，的共同订货周期，u = 1 ，2 ，) ； 2 2 基于相同p o t 订货周期的一体化库存路径问题研究 在一体化的库存路径问题中，零售商的订货周期由供应商决定，这样供应 商就可以从整个供应链的总成本最小化出发进行决策。整个供应链的费用包括 供应商和零售商的固定订货费用，库存费用以及供应商的运输费用。每个零售 商单位时间的固定订货费用为k 巧，每个零售商单位时间的库存费用为 圭红z z ，供应商单位时间的固定订货费用为瓦，运输费用为喜厶互，库存 费用为去z m a ) 【( 瓦一乃，o ) 。 整个供应链的平均费用为： c 等+ 啦+ 扣一c 纠朋哼+ 扣z ， 。 协。 我们假设零售商被分成了n 个区域，z = l ，2 ，n 为零售商对应的区域集 合，其中每个区域用一辆车进行配货，并假设每个区域内的零售商订货周期相 同，这样，当一块区域中有零售商被服务时，这块区域中其他的零售商也会被 服务。我们将找到一个p o t 时间策略，使整个供应链的成本最小。 设在固定分区下的订货周期策略为t = t o ，互，瓦) ，则供应链平均费用为： c ：争+ 兰( 乃，名) ， 1 0j = l 其中根据r o u n d y 【3 4 】得到 粥脚= 学+ 如影枷娟矧驴 ， ( 2 2 ) ( 2 - 3 ) 其中屯= k ，红= 玛一，f 弓表示路径弓上的零售商，即第j 块区域上的 i e r j 零售商。 设厶，：，2 刁兹磷弓，：川艮明显， u ( t o ) = k oi t o + 厶( ，：) 是平均费用c = l 的一个下界棚u ( t o ) = i n f c 邪v 善珥，j 小，n ) 。 的一个下界，即 ，乃珥，= 1 ， 。 9 由( 2 3 ) 很容易判断出当t o 乃时，零售商最优订货周期为 巧= 2 c 乃+ 乃吾囊西 j ，当瓦 弓时，零售商的最优订货周期为 乃= 2 c 。+ t ) 吾c 噍7 + ，喀 i 。 在给定t o 时，当我们放松车载容量这个条件时，我们得到区域，的最优周 期巧( 瓦) 为 棚= 忙 因为我们考虑的是使用p o t 时间策略，现在用最优的p o t 时间0 t 和0 来代 替0 和乃。但是要得到0 和0 必须对乃和0 进行舍入操作，使其成为i 拘p o t 倍。方法很简单，对于任一0 ，我们很容易得到乃 2 - 一，2 勺) 瓦，当乃2 _ 一1 玩 时，令0 = 2 _ 。；否则0 = 2 _ 瓦。求0 方法与之相同。 f rc h u 3 5 】知道区域j 的最优p o t 订货周期为 粥，= 隹 下面就给出求解最优订货周期的算法： s t e p l 计算g 和f ，( 歹= 1 ，2 ，) ，找出t i n = i i l i n 心，j f = 1 ，2 ，) 和 k = m a x ( g ，歹= 1 ，2 ，) 。令i = 0 ，瓦= 0 。，r o = ，e ( r o ) = ； s t e p 2 根据( 2 5 ) 式计算乃。令f ，= ( 瓦，五，瓦) ，根据( 2 - 2 ) 式计算e ( r ，) ， 如果a ( r ，f f - 1 ) o ，进入s t e p 3 ；否则最优的订货周期策略就是f = i ； s t e p 3 如果r o k ，令i = i + 1 ，t o = 2 写，进入s t e p 2 ；如果t o = f 一，则最优的t o 1 0 4 2，_ ， o ， 一 瓦瓦瓦 乃 jc j - 2 (o 0 0 一 嚣瓦瓦 k ，对所有的，乃都是相同的。这样 在知道了所有的乃时通过最小化( 2 - 2 ) 式求得t o ，然后对其进行如下舍入操作 2 k - l 玩- 瓦， z - t o( 江1 ，n - 1 ) ，z 4 矿，再根据m a t l a b 中函数f m i n c o n 对目标函数 最优化。求得目标函数最小值乞及对应的t ，若乞 乞，令艺= 乞，t = 丁； s t e p 4 令r o 依次位于下列的区间，依照上面的方法，直到最后得到最优的艺与 r 。 2 4 零售商的固定分区算法 上文中所谈到的算法都是在已知零售商分区情况下进行的，但是我们并不 知道具体的分区情况。下面我们就将给出这个具体的固定分区算法。 分区可以按照时间和位置来分，但是当根据时间分区时，库存费用降低的 同时运输费用就增加了，而根据位置来分区时，运输费用降低了，但是库存费 用却又增加了，我们采用了一种较为合理的方法。 1 2 s t e p l 根据e o q 模型计算出每个零售商的订货周期互，扣l ，刀，对其进行排 序，设排序后的序列为互互s 乙； s t e p 2 从r l 开始一条新的路径墨，依上面排序将后面零售商加入此路径中来， 当总的需求量超过了y ，这个点就开始一条新的路径马，依次类推到所有的点 都加入路径b ，凰中。对每条路径计算下面的两个值， 丁( 弓) = m i n v l 丽f 旭吩 j o ( r a - - - ( r + 巧) 乃+ 去乃忍吐； i e r j s t e p 3 选取路径墨中的第一个点r j ，确定其所在区域中其余零售商所在路径， 考虑将其插到墨以外该区域其他路径中，计算墨中删除点，i 后的丁( r 一，i ) ， d ( 局一，i ) 及该区域其他路径插入点后的r ( r ju ，i ) ，d ( bu ，i ) ，选出最小的 d ( 吩u ，i ) + d ( 墨一，i ) ，若满足d ( q u ，i ) + d ( 墨一，i ) d ( 玛) + d ( 墨) ，将此点插入路 径r ，并从原来的路径墨中删除，且新的t ( r ，) = 丁( 墨一) ，o ( r 。) = d ( 墨一) ， r ( 毛) = r ( 玛u ) ，o ( r j ) = o ( r ju 吒) ；若没有路径满足以上条件，则为此点新开 一条路径氐+ i ，计算t ( r 1 ) ，d ( ，i ) ，若满足d ( ，i ) + d ( 置一五) 一琅 堑屿 j 近的订货周期，可以节省库存费用，其次考虑了根据地理位置对其进行改进， 是相距不远的零售商分成一组，这样又可以节省运输费用，最终得到一种较为 合理的分组。 2 5 算例分析 本节通过一些实例对前文中的两种启发式算法进行比较。算例被分别考虑零售商 个数为l o ，2 0 ，5 0 ，7 5 及1 0 0 个，零售商的位置与需求量数据来自c h r i s t o f i d e s 和e i l o n 的文章【3 6 1 ，对于每种情况还考虑了库存成本、订货成本以及车载容量的限制的变化。 表2 1p o t 策略下相同与不同订货周期费用比较 参数点数 p o t lp o t 2 c参数点数 p o t lp o t 2 c k o = 1 0 01 02 8 4 62 8 0 24 4 x o = 1 0 0 1 03 9 1 5 3 7 8 61 2 9 墨= 1 0 2 05 5 2 35 4 2 79 6k s = 1 02 07 6 1 37 4 0 92 0 4 = 0 1 5 01 3 5 5 7 1 3 1 6 53 9 2 ；0 2 5 01 8 6 3 91 8 2 4 63 9 3 矗= 0 2 7 5 1 9 9 9 3 1 9 2 4 96 4 6 吩= 0 4 7 52 7 5 8 42 6 8 4 87 3 6 v = 5 0 0 1 0 02 4 6 2 42 3 9 9 31 6 1 1 v = 5 0 0 1 0 03 3 9 5 53 3 0 5 7 8 9 8 x o = 3 0 01 03 0 9 63 0 1 68 ox o = 3 0 01 04 3 9 24 3 5 24 0 瓦= 3 0 2 06 0 4 35 8 6 11 8 2 局；3 0 2 08 6 5 38 5 5 01 0 3 = 0 1 5 01 5 1 5 01 4 7 2 44 2 6 | i j b ；0 2 5 02 0 7 9 72 0 3 1 74 8 0 | i | l = 0 2 7 52 2 2 6 72 1 5 7 66 9 1 = 0 4 7 53 1 0 0 03 0 2 4 17 5 9 v = 5 0 0 1 0 02 7 6 4 52 6 6 4 89 9 7 矿= 5 0 0 1 0 0 3 7 8 6 3 3 7 0 9 27 7 1 k o = 1 0 0l o2 7 0 3 2 6 7 3 3 0 k o ；1 0 0 1 03 9 1 73 7 8 41 2 9 e = 1 0 2 0 5 2 6 2 5 1 4 9 1 1 3墨；1 02 0 7 4 7 5 7 2 1 52 6 0 = 0 i 5 01 2 7 9 51 2 3 7 54 2 0 j i | b = 0 2 5 01 7 7 9 01 7 2 7 35 1 7 | | j l = 0 2 7 51 9 4