（管理科学与工程专业论文）固定分区法在库存路径联合优化问题中的应用.pdf

固定分区法在库存路径联合优化问题中的应用 摘要 本论文研究来源于国家自然科学基金与新世纪优秀人才支持计划。 库存路径联合优化问题是将库存控制问题和运输问题集成到一系统中，用 一个目标函数来刻画。从研究和应用的现状来看，整合优化更有利于提高物流 系统的效率和节省费用支出。国外早在上世纪8 0 年代中期就开始研究库存路径 问题，在模型和算法方面已有了一些研究，但在国内对库存路径问题的研究很 少见。 固定分区法是研究战术层库存路径联合优化问题的一种非常有效的方法。 所谓固定分区原则就是预先将客户划分到不同区域中，对每个分区指派一辆车 送货。固定分区法中的费用函数有自己独特的结构特性，无论是从建模角度还 是从算法设计角度，都使得处理库存路径问题变得简单些。固定分区法的应用 非常广泛，不仅可以应用在v m i 中，还可以在非一体化供应链中应用。由于在 我国大多数情况是供应商与零售商为不同的企业，它们为了追求各自的利润最 大化，而不考虑与其它企业的合作。因此研究非一体化的库存路径问题具有更 大的实际意义。 总的来说，本文主要做了以下两方面工作： 第一部分分析了在允许缺货的前提下固定分区法在v m i 中的应用。为供应 商提出了一个配送计划，给出了整个系统的费用函数，以及求解费用函数的算 法。 第二部分分析了在不允许缺货的前提下固定分区法在非一体化供应链中的 应用。为供应商提出了一个配送计划，给出了整个系统的利润函数，以及求解 利润函数的算法。并且为了保证供应商与零售商都可以接受这个计划，提出了 一个价格策略，实现了对整个供应链的协调。 关键词：库存路径联合优化，固定分区法，配送，缺货 t h e a p p l i c a t i o no ff p p o ni n v e n t o r y - t r a n s p o r t a t i o ni n t e g r a t e d 0 p t i m i z a t i o np r o b l e m a b s t r a c t i n v e n t o r y t r a n s p o r t a t i o ni n t e g r a t e do p t i m i z a t i o np r o b l e mi n t e g r a t e si n v e n t o r y c o n t r o lp r o b l e ma n dt r a n s p o r t a t i o np r o b l e mi n t oas y s t e ma n du s e ao b j e c t i v e f u n c t i o nt od e p i c t i o n f r o mt h er e s e a r c ha n da p p l i c a t i o ns t a t u s ，o p t i m i z a t i o no f t h e s et w oa s p e c t st om a k ef o ri m p r o v i n gl o g i s t i c ss y s t e me f f i c i e n c ya n ds a v i n g c o s t s a s e a r l y a sm i d - 19 8 0 ， o v e r s e a ss c h o l a r sh a db e g u nt o s t u d y i n v e n t o r y - t r a n s p o r t a t i o ni n t e g r a t e do p t i m i z a t i o np r o b l e m t h em o d e la n da l g o r i t h m h a dan u m b e ro fs t u d i e s ，b u tt h es t u d i e sw e r er a r ei nt h ed o m e s t i c f p pi sa v e r y e f f e c t i v em e t h o dt o s t u d y t a c t i c a ll e v e lo f i n v e n t o r y - t r a n s p o r t a t i o ni n t e g r a t e do p t i m i z a t i o np r o b l e m t h es o - c a l l e df p pi s d i v i d i n gc u s t o m si n t od i f f e r e n tr e g i o n si na d v a n c e ，a n da s s i g n i n gav e h i c l et oe a c h r e g i o n c o s t sf u n c t i o n so ff p ph a v ei t so w nu n i q u es t r u c t u r ec h a r a c t e r i z a t i o nw h i c h m a k e sm o d e la n da l g o r i t h md e s i g ns i m p l e r f p ph a sb e e nw i d e l yu s e d i tn o to n l y c a nb ea p p l i e dt ov m i ，b u ta l s ot ot h en o n - i n t e g r a t e ds u p p l yc h a i n o w i n gt ot h e c a s eo fs u p p l i e r sa n dr e t a i l e r sf o rd i f f e r e n te n t e r p r i s e si no u rc o u n t r y ，t h e yd on o t t a k ea c c o u n to fc o o p e r a t i n gw i t ho t h e re n t e r p r i s e si no r d e rt om a x i m i z et h e i ro w n p r o f i t s t h e r e f o r e ，t h es t u d y i n gi n v e n t o r y t r a n s p o r t a t i o ni n t e g r a t e do p t i m i z a t i o n p r o b l e mo fn o n i n t e g r a t e ds u p p l yc h a i nh a sm o r ep r a c t i c a ls i g n i f i c a n c e o v e r a l l ，t h i sp a p e rh a sd o n es o m er e s e a r c hi nt h ef o l l o w i n gt w oa s p e c t s ： t h ef i r s tp a r ta n a l y s e sf p p sa p p l y i n go nv m ia l l o w e do u to fs t o c k w e d e t e r m i n ead i s t r i b u t i o np l a nf o rs u p p l i e ra n dg i v et h ec o s t sf u n c t i o no ft h ew h o l e s y s t e ma n da na l g o r i t h mo fs o l v i n gt h ec o s t sf u n c t i o n t h es e c o n dp a r ta n a l y s e sf p p sa p p l y i n go nn o n - i n t e g r a t e ds u p p l yc h a i n d i s a l l o w e do u to fs t o c k w ed e t e r m i n ead i s t r i b u t i o np l a nf o rs u p p l i e ra n dg i v et h e p r o f i t s f u n c t i o no ft h ew h o l es y s t e ma n da na l g o r i t h mo fs o l v i n gt h ep r o f i t s f u n c t i o n m o r e o v e r ，i no r d e rt oe n s u r et h a ts u p p l e ra n dr e t a i l e r sc a na c c e p tt h i sp l a n ， w ep u tf o r w a r dap r i c i n gs t r a t e g yt or e a l i z et h ew h o l es u p p l yc h a i nc o o r d i n a t i o n k e y w o r d s ：i n v e n t o r y - t r a n s p o r t a t i o n p o l i c i e s ；d i s t r i b u t i o n ；o u t i n t e g r a t e do p t i m i z a t i o n ； f i x e d p a r t i t i o n o fs t o c k 插图清单 图3 1 第，个分区的库存图1 3 图3 2 第，个分区的货物在供应商的库存图1 3 图3 3 第，个分区的货物在整个系统的库存图1 4 图3 4 第，个分区( 或整个系统) 的库存图1 6 列表清单 表3 1 不同缺货损失费对应的结果2 1 表4 1 协调前后结果比较2 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得 金妲工些太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 嚏榷 签字日期：缔月厂e l 学位论文版权使用授权书 本学位论文作者完全了解金月巴王些太堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权金壁王些太堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者躲桶 签字日期：嘲年6 月f 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 衣j ) 围妒 签字日期：妒8 年月f 日 电话： 邮编： 致谢 在这篇论文即将完成之际，我向所有那些曾经帮助过我的老师和同学们致 以真诚的谢意。 这篇论文是在导师周永务教授的指导下完成的，从论文的选题、资料搜集 以及整个的撰写过程，到后来的修改和定稿无不倾注了导师的心血。导师严谨 的治学态度、渊博的学术知识使我受益终生，并激励我不断前进。三年来，导 师在学习生活上给我很多帮助，在此本人致以崇高的敬意。 感谢合肥工业大学李文年、赵菊、刘桂庆等老师，这三年来他们对于我的 学习也给予了很大的帮助。 而且，在这三年中我也得到各位同学的热心帮助。与吴亦汉、孙茂、余国 峰、胡旭升、刘源、左妍妍以及汪磊、王圣东、闵杰等师兄、师姐们经常在一 起探讨，拓宽了我的视野，丰富了我的学术知识，使我受益匪浅。 还要感谢我的父母和家人，是他们一直以来给我无微不致的关怀和支持， 给予了我前进的力量，成为我的坚强后盾，使我得以顺利完成学业。 最后感谢论文评审委员会的老师们百忙之中还抽出时间仔细地对我的论文 进行评阅。 作者：李智 2 0 0 8 年4 月 第一章绪论 1 1 研究背景 物流是指原材料、产成品从起点至终点及相关信息有效流动的过程。现代 物流运用全新的管理理念，通过对物流全过程多要素的计划、实施和控制，将 运输、仓储、装卸、加工、整理、配送、信息等环节有机地结合，形成完整的 供应链，从而为用户提供高效率、多功能、一体化的综合性服务。它对加速经 济循环、降低成本和提高企业竞争力有着十分重要的作用。目前，国际上普遍 把物流称为“降低成本的最后边界，排在降低原材料消耗、提高劳动生产 率之后的“第三利润源泉。随着经济全球化和信息化进程的不断加快，物 流业作为具有广阔前景和增值功能的新兴服务业，正在全球范围内迅速发展， 掀起“现代物流革命。目前，世界上一些发达国家和地区的物流产业已成 为国民经济的支柱产业。 1 2 国内外研究现状 在物流系统管理过程中，战术层处理的决策一般每季度都要进行更新，如 采购和生产决策，库存策略和运输策略。战术层的库存运输联合优化问题所研 究的也是如何确定库存策略和运输策略，但不同的是它并非将两者分开考虑， 而是综合平衡与这两者相关的费用，在满足相应的限制条件和客户需求基础上， 去寻求使系统运行最好的库存和运输策略。例如，在一对多的配送物流系统中， 联合优化问题需要同时考虑所有需求方的库存相关费用( 如库存保管费和缺货 损失费) 和为所有需方送货的运输相关费用( 如与走行距离对应的可变费用和每 派出一辆车的固定费用) ，且不违反相应约束条件( 如运载工具的载重量和供货 方的供应能力) 和满足客户需求的前提下，来确定对每个客户的配送量和配送频 率，以及车辆的行驶路线。 关于战术层库存路径联合优化问题，b u r n i 】等是较早进行研究的学者。他 们的研究考虑的无限时间长度，单供方多需方的单物品配送系统。在假设需方 的需求率是确定的、所有客户的库存维持费用相同且运输费用仅与走行距离相 关的情况下，他们分别研究了两种使库存和运输费用最小的配送策略：直达运输 ( 每辆车每次为一个客户送货) 和零担运输( 每辆车每次为多个客户送货) 。文中 建立了类似于e o o 公式的模型并设计了相应的求解方法( 解析法) 。文中指出管理 者如采用他们设计的方法，用计算器就可以进行辅助决策和对系统进行敏感性 分析。他们所采用的解析法的实质是在不影响所研究问题的本质特性的前提下， 采用有代表性的统计数据而非繁杂的具体数据来寻求实际问题的解决方案。由 这思想建立的模型易于理解和求解，尤其对于大规模的物流系统。解析法和与 它类似的方法是研究战术层库存路径联合优化问题的一种常用方法。 研究战术层库存路径联合优化问题的另一种方法，文献b a i t af 【2 j 称之为基 于固定划分原贝, u ( f p p ，f i x e dp a r t i t i o np o l i c i e s ) 的方法也是一些学者讨论的重点。 所谓f p p 原则就是预先将客户划分到不同区域中，形成策略集痧。在考虑车辆运 载能力的前提下，矽中的最优策略是指具有最小的平均总库存和运输费用的策 略。确定矽中的最优策略显然是n p 难题，因为这需要寻找一个供货方与某个区 域中的所有客户之间的哈密尔顿回路。但是，以客户数和最优的哈密尔顿回路 长度表达的每个区域的长期平均费用结构非常类似于e o q 问题的费用结构，这 样的结构特性，无论是从建模角度还是从算法设计角度，都使得处理问题变得 简单些。采用基于f p p 的方法求解库存路径联合优化问题的过程可分为3 个阶 段：1 ) 对欲研究区域的所有客户进行划分，形成一组包含某些客户的子区域。 划分的标准可以是距离等；2 ) 对每一子区域，采用某种求解t s p 问题的算法确 定最优的车辆行驶路线及路线长度；3 ) 将运费看作一固定费用，采用变形e o q 公式确定每一子区域的最优配送量和配送频率。 在3 硪a n i l y t 3 j 中，作者研究了一类客户( 该文中指零售商) 需求确定、无限 时间长度的库存路径联合优化问题，并且假设每个客户的需求率不小于l 。文中 首先将所有客户的需求简化为具有相同需求率的n 个需求点，然后通过一个所谓 的扇形区域划分方法来得到对整个服务区域一组划分。当客户到供货方的距离 具有独立同分布的特性，且需求点的总数足够大时，文中所设计的算法是渐近 最优的，计算复杂度为o ( n l o g n ) 。类似的问题，文献a n i l y 4 】研究了子区域个数 是先验确定的情况。 a n i l y 等采用f p p 方法研究了一个单物品，从单源点到多汇点的配送问题 a n i l y 5 】在文献a n i l y 【3 】的基础上，他们设计了在矽集中渐近最优的启发式算法。 首先是对所有零售商的总需求点进行分组，不同的是以距离和库存保管费用的 比率而非仅用客户的地理分布特征作为标准，然后再将每组划分为不同的子区 域。研究的目标是得到使系统长期运行的平均运费和库存费最小的运输策略和 库存策略。关于文中所提启发式算法的渐近最优性的理论基础，在文献a n i l y 【6 】 中进行了论述。 上述求解战术层库存路径联合优化问题的方法，所采用的模型有许多是类 似于e o q 公式的模型。我们知道，e o q 公式求得的订货时间间隔可能是任何一 个非负的实数。但这样的数值在实际运作中不好操作抑或有些不合理，有许多 学者都发现了这个问题。文献r o u n d y t7 】提出当配送过程具有p t ( p o w e r o ft o w ) 特性时，可根据此特点来设计模型和算法来考虑带有中心库存的二级配送系统， 并且证明对于批量问题所求得的解与最优解的偏差在6 以内。 a n i l y & b r a m e l 驯考虑了一个配送中心、若干零售商的i r p 。配送由一队有 容量约束的车辆完成，提出一种根据最优配送率进行划分的固定划分策略，将 零售商划分成几个集合，每个集合中的零售商独立配送。 2 1 3 本论文的研究意义 传统物流主要表现在分开处理诸如运输、存储、装卸和信息处理等环节。 而现代物流将这些有机的环节结合在一起考虑，全面系统地研究和观察总体的 物流活动，其核心思想就是强调“系统性。比如物流中的运输和存储环节， 它们分别解决了供给者与需求者之间场所和时间的分离，分别是物流创造“场 所价值 和“时间价值”的主要功能因素，是物流系统中最重要的两个环节， 占物流费用支出的绝大部分。但对它们的优化和控制，到目前为止，依旧是分 别对待。这种情况在理论上表现为关于运输优化调度和关于库存控制的研究已 很深入和比较成熟，但将这两者结合到一起研究的却较少；实践中，作为现代 物流标志之一的计算机辅助管理系统，也是单独优化运输问题和库存问题。那 么，对于现代物流系统中联系如此紧密又如此重要的两个环节，将它们集成到 一起来研究不仅具有重要的理论价值，也具有极大的实际意义。 库存路径问题是研究在供应商管理用户库存策略下，供应商如何合理安排 长期库存及配送计划的一类问题，属于n p h a r d 类问题，也是运筹学领域中研 究最活跃的方向之一。它涉及到经济学、运筹学、应用数学、组合优化、计算 机软件、计算机应用、运输管理、工业工程与物流科学等众多学科，是组合优 化等领域的前沿与热点研究问题。尽管国外早在上世纪8 0 年代中期就开始研究 库存路径问题，在模型和算法方面已有了一些研究，但在国内对库存路径问题 的研究很少见。 现在大多数文献都是在供应商管理库存( 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 是一种以零售商和供应商双方都获得最低成本为 目的，在一个共同的协议下由供应商管理库存，并不断监督协议执行情况和修 正协议内容，使库存管理得到持续地改进的合作性策略。这种库存管理策略体 现了供应链的集成化管理思想，适应了市场变化的要求。然而v m i 的实施对于 企业的要求很高，国内很少有公司具备实施v m i 的能力。在现实上大多数情况 是供应商与零售商为不同的企业，它们为了追求各自的利润最大化，而不考虑 与其它企业的合作。因此研究非一体化的库存路径问题也有很大的实际意义。 总之，在v m i 和非一体化的模式下对库存路径问题的研究不但具有理论价 值，而且还有巨大的现实价值。 1 4 本论文的研究内容 本文的内容包括下面几个方面： ( 1 ) 研究v m i 模式下固定分区法在库存路径问题中的应用 ( 2 ) 研究非一体化模式下固定分区法在库存路径问题中的应用 ( 3 ) 结合实际算例进行比较分析 1 5 本文结构安排 本文一共分为五章，主要内容归结如下： 第一章，绪论。介绍了本论文的研究背景、研究现状、研究意义以及研究 内容。 第二章，基础知识。介绍了库存路径联合优化问题研究的内容，库存路径 联合优化问题决策的三个层次，固定分区法的知识，v m i 的理论知识和供应连 协调的简介。 第三章，固定分区法在v m i 模式下的应用。分析了在允许缺货的前提下， 固定分区法在一体化模式下的应用。为供应商提出了一个配送计划，使整个系 统的费用达到最省。 第四章，固定分区法在的非一体化供应链的应用。分析了在不允许缺货的 前提下固定分区法在非一体化供应链中的应用。给出了整个系统的利润函数， 为供应商提出了一个配送计划，使得整个供应链的利润明显的增加。并且提出 了一个价格策略，实现了对整个供应链的协调。 第五章，总结与展望。总结了全文的做的主要工作，指出本文的不足之处， 并提出有待研究的方向。 4 第二章基础知识 2 1 库存路径联合优化问题简介 库存路径联合优化问题( 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 e h i c l er o u t i n gp r o b l e m ，简称v r p ) 为基础，结合库存控制发展而来的。 i r p 研究供应商根据需求方的销售信息，更加合理地安排库存补充计划，削减 其库存成本；采用更加合理的运输策略和方式，采用更加有效的运输计划来降 低其运输成本，最终获得总体成本的降低。 无论库存控制问题还是运输问题，都可以称为运筹学研究的经典问题，但 将两个问题集成到一个系统中，用一个目标函数来刻画这两个相互矛盾、而在 物流系统优化中又如此重要的领域，则是一个较新的研究方向。从研究和应用 的现状来看，整合优化比分开考虑这两个环节更有益于提高物流系统的效率和 节省费用支出。 因此，我们可以认为库存路径联合优化问题主要是在研究这样一类问题： 在同时考虑运输和库存的相应要素的前提下，如何有效而经济的管理和组织配 送活动，在有限( 或无限) 周期内，将一种( 或多种) 货物从一个( 或多个) 供货点配 送给一个( 或多个) 客户，或其相反过程。 另外，我们也可以用以下几个方面进行进一步的说明： ( 1 ) 研究对象：由供应方( 可为生产商、供应商、配送中心等) 和需求方( 可为 零售商等) 组成的一个系统。 ( 2 ) 拓扑结构：可能是单对单( 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 ) 。 ( 3 ) 货物种类：可以是一种货物或多种货物。当处理多种货物种类时，一般 也是首先对每种货物单独处理。 ( 4 ) 费用因素：主要涉及运输和库存方面的相关费用。运输相关费用包括使 用配送车辆的固定费用，与走行距离相关的可变费用。库存相关费用主要包括 货物保管费、订货费和缺货损失费。 ( 5 ) 约束限制：涉及的具体问题不同，求解问题的限制也不同，但一般都包 括几个主要因素，如配送车辆的数量、载重量、每天最大行使距离，供应方的 供应能力，需求方的存储能力、时间限制等。 ( 6 ) 需方需求：需求方的需求量已知，需求量是随机的，但需求的概率分布 特性已知，需求特征完全未知。 ( 7 ) 决策目标：客户对应的配送频率、配送量以及配送车辆的行驶路线。其 中前两个决策问题主要是考虑库存控制问题，第三个决策则涉及运输调度优化 问题。 5 2 2 库存路径联合优化问题决策的三个层次 1 战略层 物流系统中战略层决策指的是对系统有着长远影响的决策，它包括关于仓 库和制造工厂等的数量、布局和能力，以及“物 如何在物流网络中流动等方 面的决策。战略库存路径联合优化问题是在实际系统的运作还没有开始或系统 重组时进行的对整个系统长远发展有决定作用的研究。它所涉及的决策发生在 物流系统设计的后期，即实际的物流配送网络已经组建好之后，去决策所需的 最佳运载工具数量和每个客户的库存能力：其次，这个决策的对象是由供需双方 形成的系统，所追求的“最佳”并不是仅从供货方或仅从客户的利益考虑，而 是指使系统性能最好的最佳。简单的说，战略库存路径联合优化问题主要是研 究在客户( 指零售商、批发商和制造工厂等) 规模、地理分布和需求己知，而执 行配送作业的车队还没有组建时，如何在保证服务水平的前提下购买或租借车 辆，使得投资在这方面的费用最省，或者组建的车队规模最小。它所研究的对 象是由中央仓库( 制造工厂、配送中心或物流中心等) 和多个客户组成的系统。 关于它的概念性描述，有的文献给出的定义是：在实际的配送活动开始之 前，确定为具有随机需求特性的所有客户提供配送服务的最小规模( 或费用) 的 车队。还有的学者指出了此类问题的两个主要特征：1 ) 决策与正式的配送活动 开始时间之间有一个很长的提前期( 几个月或几年) ；2 ) 侧重决策为客户配送货 物时所需要的最小车队规模。 2 战术层 战术层处理的决策一般每季度都要进行更新，如采购和生产决策，库存策 略和运输策略。战术层的库存运输联合优化问题所研究的也是如何确定库存策 略和运输策略，但不同的是它并非将两者分开考虑，而是综合平衡与这两者相 关的费用，在满足相应的限制条件和客户需求基上，去寻求使系统运行最好的 库存和运输策略。可见战术库存路径联合优化问题比单纯的库存问题( 或单纯的 运输问题) 要复杂的多。此类问题的最优解( 策略) 将是非常复杂的，用数学语言 来完美表达此类问题所有特征也将是非常困难的。因此在实际操作当中管理者 也不愿采用很复杂的策略。 在二级配送系统中，库存路径联合优化问题需要同时考虑配送中心和所有 客户的库存相关费用( 如库存保管费和缺货损失费) 和为所有客户送货的运输相 关费用( 如与走行距离对应的可变费用和每派出一辆车的固定费用) ，以及订货 费等，且不违反相应约束条件( 如运载工具的载重量和配送中心的供应能力) 和 满足客户需求的前提下，来确定对每个客户的配送量和配送频率，以及车辆的 行驶路线。 6 3 作业层 作业层决策指对日常活动的决策。在库存路径联合优化问题中，作业层决 策一般来说主要是确定运载工具的行驶路线和给每个需方的配送量。不同于战 术层决策的特征主要表现在战术层决策是从计划角度出发，具有“一劳永逸” 的特点，即当确定了配送频率、配送量和最优行驶路线后，在每个周期都按此 计划执行而作业层的决策侧重的是日常运作管理，在己知系统状态( 如库存水 平和需求) 的前提下，于每个时段( 如每天或每周) 做出本时段的运作决策( 如预 测客户需求，确定那些客户需要补货，安排配送车辆的行驶路线等) ，同时此时 段的决策会影响下一时段的决策，系统就在这种相互制约、相互影响的条件下 运行。 2 3 固定分区法简介 固定分区法( f p p ，f i x e dp a r t i t i o np o l i c i e s ) 是研究战术层库存路径联合优化 问题的一种非常有效的方法。所谓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 问题的算法确定最优 7 的车辆行驶路线及路线长度；3 ) 将运费看作一固定费用，采用变形e o q 公式确 定每一子区域的最优配送量和配送频率。 2 4 供应商管理库存( v m i ) 简介 供应商管理库存( 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 的 主要思想就是实施供应厂商一体化，供应商在用户的允许下设立库存，零售商 商品数据的任何变化随时传递给供应商，供应商根据这些数据决定未来的货物 需求数量、库存水平和补给策略，拥有库存控制权。 v m i 模式的管理理念源于产品的市场全过程管理思想，即只要一个产品没 有被最终消费者购买并得到满意的消费，那么这个产品就不能算作已经销售， 并构成供应商的一种潜在风险。一个典型的v m i 系统包括，供应商通过自动化 电子信息系统监控客户仓库的库存水平，并有责任把库存补充到相应水平。这 样，供应商就可以做出补货决定而不是等待客户的订单。供应商负有监控该产 品的流通状况的责任，而不管该产品的产权归属是怎样的。同传统的库存控制 方法相比，v m i 通过集成供应商和客户的库存控制职能，减少库存环节，达到 降低整体库存的目的。 v m i 在许多文献中又被称为寄售库存。在这种模式下，供应链上游成员寄 售方将商品配送给直接下游受寄方，以供受寄方使用或出售在商品被受寄方实 际使用或出售后，受寄方向寄售方支付货款。在此过程中，供应链流通库存主 要由供应商负责维护。最早成功实施的是美国的杂货日用品行业，而后在一些 跨国公司也相继取得了巨大成功。 它的成功之处在于：它提供了一种供应商与订货商间良好的集成和互动方 式，能有效控制渠道中信息失真，需求放大牛鞭效应等因素的不良影响，提高 客户服务水平，降低库存水平和库存相关成本，从而最终提升供应链的竞争力 和利润水平。 v m i 并不单纯是一种面向供应链的全新库存管理模式，更重要的是它还能 在供应链成员间建立起了互信共赢的集成环境。在此环境下，供应链运作的库 存以外环节如生产运输等也随之发生变革。 随着计算机网络技术的应用普及，许多现代信息技术得以在物流中应用。 v m i 管理策略打破了传统的各自为政的库存管理模式，体现了供应链的集成化 管理思想，这相应的需要企业间一定的技术平台支持，采用信息技术能够有效 改善供应链的动态特性。首先，采用信息技术可使供应链成员之间实现高效的 信息共享；其次，采用信息技术可以消除信息延迟，使得顾客订货信息能够立 即传送到供应链中的各个成员，极大地提高了客户响应速度；第三，采用信息 技术后，能够清楚地掌握每一种货物的状态信息( 下线、在途、仓库中等) ，以 确定合理的订货点和提前期；最后，电子商务技术使网上商店取代传统的批发 商和零售商，缩短了供应链长度，从而改善了供应链的动态特性。 配送是v m i 系统中一个重要的直接与消费者相连的环节。但是对v m i 系 统的研究多集中在库存管理上，忽略了配送环节的研究。配送一般定义为，将 货物从物流结点送达收货人的过程。配送是在集货、配货基础上，完全按用户 的要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配 和“送 的有机结合形式。随着物流配送集约化、一体化的发展，常将配送 的各个环节综合起来，核心部份为集货过程、存贮、配货及送货过程。进行配 送系统的优化，主要是集货、货物的配装及送货线路的优化等过程。 与运输成本和库存成本之间的权衡相关的两个基本决策为运输方式的选择 和库存集中。在供应链中，选择一种合适的运输方式，既是计划性决策又是操 作性决策。一种运费最低的运输方式，并不一定使供应链系统的总成本最低。 较低廉的运输方式通常拥有较长的供货期和较大的最小运输量，从而导致供应 链库存水平提高。允许小批量运送的运输方式能减少库存但价格却更贵。因此 运输方式的选择对运输成本和库存成本影响较大。而通过将库存集中于一点， 企业可以大大减少必备安全库存量。当库存和设施费用占供应链系统的总成本 的很大一部分时，集中库存就很有必要。尤其对价值一重量比很高的产品或者 需求量不确定的商品来说，集中库存非常有用。对于公路运输而言，每辆卡车 发生一些固定运行成本( 如：折旧、司机的工资) 和一些变动成本( 如汽油) 。 如果卡车总是满车发货，那么运行该卡车的成本可以在最大可能数量的产品中 进行分摊。同样，如果公司利用外部运输公司，外部运输公司通常会提供数量 折扣。通常整车( t l ) 运输比零担运输( l t l ) 要便宜一些。因此，在这种情 况下，使用整车运输也减少了运输成本。但是在许多情况下，需求数量要远远 小于整车数量。因此，当商品整车发送时，这些商品在消费之前需要等更长的 时间，从而导致了更高的库存成本。这种权衡的问题不能够彻底消除。但是可 以利用先进的信息技术方案来减少其影响。如使用配送控制系统可以把从仓库 运往商店的不同产品的运输结合起来。 在v m i 系统的配送中，运输与库存控制是相互影响、相互制约的两个问题， “运输”涉及到不同地理位置的商品的物理移动的相关的活动，包括集中运输 策略、运输路径规划，“库存 是被运输的商品的特征，如商品存贮的成本，要 求的服务水平，订货策略等，通常库存成本降低时，运输成本升高，而运输成 本降低时，则库存成本升高，若将两个问题集成到一个系统中，用一个目标函 9 数来刻画这两个相互矛盾的因素，如何协调均衡两者使得系统目标成本最小， 是当前合作型供应链系统研究的一个重要方向。运输与库存集成问题在供应链 管理的不同层次上都有所体现，在供应链的战略层决策时，可以应用联合优化 的思想来确定系统将来实际投入运营时所需的最佳运载工具数量；在规划中、 短期系统运营计划的战术层决策阶段，通过对集成的库存与运输问题的求解可 以获得较优的库存策略，发货策略；在作业层决策阶段，可以确定日常的车辆 运输路线，客户库存的分配情形。 2 5 供应链协调简介 供应链管理就是使供应链运作达到最优化，以减少成本，令供应链从采购 开始，到满足最终客户的所有过程，包括工作流，实物流，资金流和信息流等 均高效率的操作，饱和式的产品以合理的价格，及时准确地送到消费者手上。 因而供应链管理的重要内容之一就是去协调供应链系统中的各个组成部分，通 过强有力的措施和关键信息的控制协调企业的经营活动。 协调的概念本源于系统的研究。有的学者将协调定义为管理各种活动间独 立性的过程。系统协调的目的就是希望通过某种方法来组织或调控所研究的系 统，使之从无序转换为有序，使系统达到协同状态。系统协同程度越高，输出 的功能和效应就可能越大，系统的负效应就会越小，结果就越有价值。一般来 说，需要进行协调的系统往往包含若干个相互矛盾和冲突的子系统或者有自己 对各个目标有不同评价标准的参与者。对于这些系统，如果不能通过协调或协 商来妥善处理各种冲突以达成一项折衷方案，那么该系统总体功能将由于系统 宏观结构的失稳而无结果，甚至产生负效应，即出现系统的整体功能小于各部 分子系统功能之和。供应链是典型的、需要协调的系统。链中各节点企业不一 定能同时满足各自满意度最大的愿望，因而产生冲突竞争，但既然形成一条供 应链，他们就需要共同协作，使整个供应链获得的利益大于各节点企业单独获 得的利益之和。因此，供应链协调的目的是通过各种方法使供应链中各节点企 业减少冲突竞争及内耗，更好地分工合作，发挥供应链的优势以获取最大收益。 供应链协调的动因显而易见，是为了应对竞争加剧和环境动态性强化的局面， 谋求中间组织效应，追求价值链优势，构造竞争优势群和保持和新文化的竞争 力。而供应链协调的内容主要是各个节点企业的各种决策，包括订货数量、订 货价格、订货周期、库存数量等。 协调是一项艰难的工作。在供应链协调过程中，存在着许多影响因素，必 须给予足够的重视。这些因素主要包括： 1 相互依赖性程度。供应链活动的相互依赖性程度是指某一组织的活动和 产出受控于或依赖于另一组织的活动和产出的程度。这些活动可以概括为连续 的、相互的和同时发生的。连续的活动发生在生产线的各个阶段之中，或者发 生在将产成品从工厂运送到配送中心之时；相互的活动一般发生在分销渠道， 1 0 同时发生的活动是指几个同类组织为完成某一共同目标而进行的活动。 2 冲突程度。相互作用组织间的冲突可能是组织上的和文化上的动机或者 许多其他因素的结果。首先，供应链中各个组织都有各自的目标，在利益的追 求上是以自身利益为前提的，而各自利益往往具有排他性，即如果某一成员企 业如果获得了令其满意的利益，则其上游或下游的企业通常要受到利益的伤害， 形成利益冲突。其次，供应链的各个成员企业来自不同的组织，有着不同的背 景，无法实施单一的文化管理。因而，在合作过程中，会自觉或不自觉地产生 习惯性的防卫心理和行为，形成一定程度的心理和行为冲突。 3 不确定性程度。供应链中存在很多的不确定性因素，主要表现为衔接不 确定性和运作不确定。衔接不确定性是指供应链成员企业之间( 或部门之间) 合 作上的不确定性，而运作不确定性是指组织内部缺乏有效的控制机制所导致的 系统运行不稳定。 促进供应链协调的方法很多，有的学者总结出了下面的一些促进协调方法， 这些方法并不是相互排斥的，可以有机结合起来使用。 1 基于传统指令体制的直接管理方法； 2 利用规则、程序和标准的规范化方法； 3 基于计划分解或利用详细说明产出指标的目标制定方法； 4 基于管理者和工人团队或其他联系形式下联合决策的互动方法； 5 即使从自身利益出发也会导致独立管理者做出最佳决策的订价方法。 这些方法可以确保自治组织与其他组织共享包括信息的各种资源，并实现 公司的中短期供应链计划。 当不确定性程度较大时，协调要求更注重利用团队或管理者和工人之中的 其他组织形式。当然，无论何时何处只要有可能，公司都应该努力降低冲突和 不确定性。通过加强通讯与缩短更新数据与计划间的时间，i t 系统可以在很大 程度上服务于该目标，以便更好地实现供应链的协调。 2 6 本章小结 本章是对论文相关基础知识的简介。其中包括库存路径联合优化问题研究 的内容，库存路径联合优化问题决策的三个层次，固定分区法、v m i 和供应连 协调的相关理论知识。 第三章固定分区法在v m i 模式下的应用 3 1 问题的描述 本章考虑的是由一个供应商和多个零售商组成的两级配送系统的库存路径 联合优化问题，该系统采用v m i 的模式。为了方便起见，我们假设每个零售商 只需要一种产品，产品的种类可以不同。在这个配送系统中，供应商先向外界 的供货商订货，然后再对各个零售商进行配送。在配送中允许缺货，但缺货要 补。假设每个零售商的需求率是已知的并且是确定的。本章要为供应商确定一 个送货策略，使得整个系统的费用达到最小。其中费用包括供应商和零售商的 订货费用，供应商和零售商的库存费用，零售商的缺货损失费，以及配送所产 生的运输费用。 本章所使用的记号： h o = 供应商的单位商品单位时间的库存保管费； h i = 第f 个零售商的单位商品单位时间的库存保管费，( f = 1 ，2 ，忉； 为了方便起见以及反映实际情况我们假设忽 h o ，( i = l ，2 ，忉； e t = 第f 个零售商的需求率，“= 1 ，2 ，n ) ； k o = 供应商向外部供货商的定货费； k = 第f 个零售商向供应商的定货费，( f = 1 ，2 ，忉； p i = 第f 个零售商单位商品单位时间的缺货损失费，( f = l ，2 ，) ； w = 每辆车的最大载重量，( 假设都相同) ； 为了解决上述问题，我们先将区域中的所