（管理科学与工程专业论文）集成化物流管理中随机库存路径问题研究.pdf

，嚣、 硕士学位论炙 m a s t e r st h e s i s 摘要 随着市场业务竞争的愈演愈烈，企业需要不断的适应现代市场的生存规律，快 速的响应市场的需求，加强对企业成本的控制，提高整体的运营效率，这样才能在 竞争中立于不败之地。在企业的成本降低和整体性能提高的过程中，物流环节的成 本降低将会大大提高企业的利润。于是，众多企业将其注意力转向了“物流过程优 化”、“供应链整体设计”，更加重视“第三利润源”的挖掘。基于这种现实意义的考虑， 本文将创造时间价值的库存控制和创造空间价值的运输活动的两个具有“悖反效益” 的因素联合到一个问题中，即库存路径问题( i n v e n t o r yr o u t i n gp r o b l e m ，瓜p ) 中加以 考虑，通过对这两个影响物流成本的重要因素的协调优化，来达到整体效益提高的 目的。本文从系统化、集成化的角度出发，对二级配送系统的随机库存路径问题 ( s t o c h a s t i ci n v e n t o r yr o u t i n gp r o b l e m ，s i r p ) 进行研究。 本文首先对i r p 的理论( 如：i r p 概念、i r p 与其他相关问题的区别等) 进行了归 纳，然后从常见模型、求解算法和策略三个方面综述了当前国内外关于i r p 的主要 研究进展，指出了该研究领域在未来研究中应予以重视的几个研究方向，为进一步 的研究奠定了基础。 根据第二部分研究现状的分析，结合s i r p 本身所具有的马尔可夫、随机等特 性，在本文的第三部分，运用经典马尔可夫决策理论建立s i r p 数学模型，使得问 题的研究更能体现实际情况。在第四部分，本文提出了两种启发式算法对模型进行 求解，并且给出了求解的详细步骤。在第五部分，采用前人提供的一组数据对建立 的模型和提出的两种启发式算法进行演算。 在本文的最后部分，即总结和展望部分，给出了本文所作工作的扼要总结和 未来工作的方向。 关键字：随机需求库存路径问题马尔可夫决策过程启发式算法 ： 硕士学位论文 m a s i e r st h e s i s a b s t r a c t 、i t ht h ei n c r e a s i n gm a r k e tc o m p e t i t i o n ，e n t e r p r i s e sn e e dt oa d a p tt ot h el a wo ft h e s u r v i v a lo ft h em o d e mm a r k e tc o n s t a n t l y , r e s p o n s et om a r k e td e m a n dq u i c k l y , s t r e n g t h e n t h ec o n t r o lo ft h ec o s to fd o i n gb u s i n e s s ，i n c r e a s i n gt h eo v e r a l lo p e r a t i o n a le f f i c i e n c y , s o i tc a nb ei na ni n v i n c i b l ep o s i t i o ni nt h ec o m p e t i t i o n i nt h ep r o c e s so fr e d u c i n gt h ec o s t o ft h ee n t e r p r i s ea n di m p r o v i n gt h eo v e r a l lp e r f o r m a n c e ，l o g i s t i c sc o s tr e d u c t i o nw i l l g r e a t l ye n h a n c ep r o f i t s a n dt h e n ，m a n ye n t e r p r i s e st u r ni t sa t t e n t i o nt ot h e “l o g i s t i c s p r o c e s so p t i m i z a t i o n a n d “o v e r a l ld e s i g no ft h es u p p l yc h a i n ”，p a ym o r ea t t e n t i o nt o “t h et h i r dp r o f i ts o u r c e ”o ft h ee x c a v a t i o n f o rt h e s er e a s o n s t h i sd i s s e r t a t i o ni n t e g r a t e s t w op r i n c i p a lp r o b l e m sn a m e dt h ei n v e n t o r yc o n t r o lp r o b l e ma n dt h et r a n s p o r t a t i o n o r g a n i z a t i o np r o b l e mi n t oo n ep r o b l e m ，a n dt h e ns e e k st h eo p t i m a ls o l u t i o no ft h i s c o m b i n e dp r o b l e mi n s t e a do fe a c hs i n g l ep r o b l e m f r o mt h e s ep o i n t so fv i e w , t h ep a p e r a d d r e s s e st h eo p t i m a ls o l u t i o no ft h ei n t e g r a t e dp r o b l e ma b o u tt h ei n v e n t o r yc o n t r o la n d t h e o p t i m i z a t i o n o ft r a n s p o r t a t i o n r o u t i n gp r o b l e mb u tn o t i t so n ea s p e c ti nt h e d i s t r i b u t i o nl o g i s t i c ss y s t e m n i sp a p e rs t u d i e st h ei n t e g r a t e di n v e n t o r y t r a n s p o r t a t i o n p r o b l e ms y s t e m a t i c a l l y , w i t hs i m u l t a n e o u sd e c i s i o n sm a d eo ni n v e n t o r ya n d t r a n s p o r t a t i o np o l i c i e si nt h eg r a d e 一2s u p p l yc h a i n f i r s t l y , w ee x p a t i a t e dt h ei n v e n t o r yr o u t i n gp r o b l e m sb a s i cc o n c e p ta n dc h a r a c t e r s ， i n t e g r a t e sm a n yr e f e r e n c e so f h o m ea n da b r o a d ，s u m m a r i z et h em o s t l yr e s e a r c h i n g c i r c so ft h en a t i v ea n da b r o a da tp r e s e n tf r o mt h r e ep a r t s ( c o m m o nm o d e l ，m a i n l y a l g o r i t h ma n ds t r a t e g y ) ，a n df i n a l l yi n d i c a t es e v e r a lr e s e a r c h i n gd i r e c t i o no ft h i sd o m a i n i nf u t u r e ，w h i c hl a y saf o u n d a t i o nf o rf u r t h e rr e s e a r c h e s a c c o r d i n gt ot h er e s e a r c hp r e s e n ta n a l y s i so ft h es e c o n dp a r t ，i n t e g r a t et h e m a r k o v i a na n ds t o c h a s t i cc h a r a c t e r i s t i c so ft h es t o c h a s t i ci n v e n t o r yr o u t i n gp r o b l e m ，s e t u pam a r k o vd e c i s i o np r o c e s sm o d e lf o rt h ep r o b l e m i nt h ef o u r t hp a r t ，w ep u tf o r w a r d t w oh e u r i s t i ca l g o r i t h m s ，t h a tb a s e do nc l i e n ti n s e r ta n db a s e do np o l i c yi t e r a t i o n ，t os o l v e t h em o d e l ，a n dg a v et h ee x h a u s t i v es t e p s i nt h ef i f t hp a r t ，w es e l e c tt h es a m ed a t e sa st h e p r e d e c e s s o r sf r o mt h ee x a m p l ed a t a b a s et ov e r i f i c a t i o n i nt h el a s tp a r to ft h i s p a p e r t h a ti s ，s u mu pa n do u t l o o ks e c t i o n ，g a v eab r i e f s u m m a r yo f t h ew o r ka n df u t u r ew o r kd i r e c t i o no ft h i sa r t i c l e k e yw o r d s ：s t o c h a s t i cd e m a n d ；i n v e n t o r yr o u t i n gp r o b l e m ；m a r k o vd e c i s i o n p r o c e s s ；h e u r i s t i ca l g o r i t h m i i 硕士学位论文 m a s t e r st h e s l s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：试专l 良 日期：励7 年多月争日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：武专l 康 日期：劢7 年6 月争日 名：密吁 日期钞7 年月辱日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。圃童途塞握童后进唇；旦圭生；堕= 生；旦三生筮血! 作者签名：试瘫瞧 日期：柳7 年月日 孙抛稚吁 日期：加吁年月p 日 硕士学位论文 m a s t e r st h e s l s 1 1 研究背景与课题来源 1 前言 当前，全球经济的一体化、顾客需求的多样化及其个性化、产品生命周期的缩 短和快速响应市场的压力、新的生产与物流管理模式的不断涌现，使得与物流相关 的战略和作业决策变得越来越困难，而集成化物流管理( i n t e g r a t e dl o g i s t i c s m a n a g e m e n t ，i l m ) 理念的提出成为解决这一复杂问题的可行选择。i l m 的思想主张 将所有的物流活动整合在一起视为一个完整的系统，并在理想的客户服务水平下追 求总成本最低【1 1 。随着物流管理的逐步深入和系统化，越来越多的管理者开始认识 到：如果各种职能性的物流活动可以被统筹管理并协同运作的话，那么企业将可以 在提高客户服务水平和减少部f j 之i 刈冲突的同时降低物流总成本【2 j 。上个世纪朱国 外的一项调查表明：超过5 0 的物流管理者已经接受了i l m 的概念；i l m 正成为 物流管理中越来越重要的管理手段，是物流管理发展的必然趋判3 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 ) 贝o 是i l m 研究的一个重要的领域和关键技术，对它 的研究目前已成为组合优化、集成化物流管理等领域的前沿与热点。 此外，伴随市场竞争的不断加剧，如何在生存和发展中立于不败之地，对于企 业来说是亟待解决的一大难题，许多企业纷纷将其注意力转移到“物流系统”、“供应 链设计”等的优化，更加强调物流系统中各个环节的相互协调和物流整体性能的提 高，试图通过物流成本的降低来提高企业的利润，而将库存控制和运输活动这两个 具有“悖反效益”的因素联合到一个问题中，即i r p 中加以考虑，寻找这两个影响物 流成本的重要因素的协调优化方案，无疑将会提高企业的整体效益，是解决企业面 临问题的一个较好方法。 基于对以上理论主张和现实要求的考虑，本文从系统化、集成化的角度出发， 对二级配送系统的随机库存路径问题( s t o c h a s t i ci n v e n t o r yr o u t i n gp r o b l e m ，s i r p ) 展 开研究。 本论文的研究受到了多个基金项目的资助，其中包括： ( 1 ) 李延晖副教授主持的教育部人文社会科学研究项目：基于时间竞争的集成 物流管理研究( n o ：0 5 j c 6 3 0 0 7 4 ) ： ( 2 ) 李延晖副教授主持的国家自然科学基金项目：时间竞争环境下选址一库存 一路径问题优化模型与算法研究( n o ：7 0 8 7 1 0 5 0 ) 。 本文的研究为各资助项目中的i r p 优化子模块的部分内容，解决了库存控制和 硕士学位论文 m a s t e r st h e s | s 运输活动两个环节的优化问题，在理论研究、企业实践及社会效益上都具有重要意 义。 1 2 研究意义 库存成本和运输成本是企业整个社会物流成本的两个主要组成部分，降低库存 和运输环节的成本已成为企业获取竞争优势的重要源泉之一，而在传统物流管理模 式下，库存和运输这两个领域是分别进行决策的，整个物流过程按照物流活动的功 能被人为地分割成彼此独立的部分进行研究，而i r p 将创造时间价值的库存成本和 创造空间价值的运输成本的两个具有“悖反效益”的因素整合在一个问题中系统地加 以考虑，更有实际意义。 在理论研究上，s i r p 作为一类典型的具有广泛应用的n p 难题，它涉及的领域 非常广泛，主要有物流科学、运输管理、工业上程、运筹学、应用数学、计算机软 件、计算机应用等，是整合优化等领域的前沿问题和当前研究热点。本研究是运用 马尔可夫决策过程的思想对s i r p 的优化进行建模和求解，来进一步丰富优化理论 与方法的研究范围和内容。 在企业实践上，对s i r p 进行研究是降低企业成本、提高运行效率、建立智能 化物流网络和先进管理系统的基础和前提条件；此外，伴随供应商管理库存( v e n d o r m a n a g e di n v e n t o r y ，v m i ) 思想的不断深入及其在实际中的应用，s i r p 的研究更显出 了它的深刻意义。 在社会效益上，对s i r p 进行研究是社会网络化和电子商务发展的迫切需要， 有利于从社会经济可持续发展的角度解决资源紧缺、交通拥挤等诸多的社会问题， 带来巨大的经济和社会效益。 1 3 本文的主要研究内容和创新点 1 3 1 研究内容 本文在对i r p 内涵、研究现状以及马尔可夫决策理论进行详细描述的基础上， 建立数学模型，并提出两种不同的方法对模型进行求解，通过实例演算，证明了这 两种求解方法的实用性和有效性。 本文在供应链管理、物流管理、系统工程、计算机程序设计等理论与方法的指 导下，对由一个配送中心和n 个客p ( o n e m a n y ) 组成的两级配送系统的s i r p 进行 研究。全文共分六章，主要内容如下： 2 f f 硕士学位论丈 m a s t e r st h e s i s 第一章：前言。介绍本文的研究背景与课题来源、研究意义、本文的研究内容 和主要的创新之处。 第二章：i r p 研究综述。介绍i r p 的涵义、i r p 与其他相关问题的区别；从模 型、策略及算法三个不同的角度对国内外相干研究进行详细的综述，并进行简单的 评述。 第三章：基于马尔可夫决策过程的s i r p 模型。本章首先介绍了马尔可夫决策、 无限阶段折扣模型等基础理论，然后结合i r p 本身所具有的随机、马尔可夫等特性， 从实际出发，建立s i r p 数学模型。 第四章：模型的求解方法。本章首先对模型求解过程中需要的状态转移概率进 行求解，然后，提出了求解此模型的基于客户插入和基于策略迭代算法的两种启发 式算法。 第五章：实例分析。本章运用第四章提出的两种启发式算法对给出的实例进行 s i r p 演算，并对所得结果进行比较。 第六章：总结和展望。对本文所作的工作进行了扼要总结，同时，指出未来的 工作方向。 1 3 2 创新点 1 对i r p 领域的研究做了详尽的综述。作者通过阅读大量的书籍，综合国内外 多种参考文献，介绍了i r p 的基本概念及其主要特征，从常见模型、求解算法和策 略三个方面综述了当前国内外关于i r p 的主要研究进展，指出了该研究领域在未来 研究中应予以重视的几个研究方向，为进一步的研究奠定了基础。 2 考虑到s i r p 本身所具有的马尔可夫、随机等特性，从其现实意义出发，运 用马尔可夫理论将s i r p 描述为一个马尔可夫决策过程，建立数学模型。与前人研 究所不同的是本文没有将s i r p 分解成库存和路径两个问题进行分阶段求解，而是 将库存与路径安排联合起来寻找算法进行优化。 3 提出两种基于搜索算法的启发式算法( 基于客户插入的启发式算法和基于策 略迭代的启发式算法) 对所建立的i r p 数学模型进行求解，并运用实例进行演算，通 过演算来证明所提算法的优越性和实用性。 3 硕士学位论文 m a s t e r st h e s i s 2 1i r p 的内涵 2i r p 研究综述 2 1 1i r p 的涵义 在通常意义下，i r p 指的是：在满足一定的约束条件( 需求时间的长短，库存水 平的大小，货物需求量的多少等1 的情况下，为一系列需求点，确定其补货时间、数 量及其配送路线1 4 l ，使得整个配送系统的运行费用( 存贮费，订货费，运输费，缺货 损失费等) 极小或总收益最大。它具有研究对象、拓扑结构、货物种类、费用因素、 限制因素和需方需求等六个的研究特征1 4 j 。在对i r p 进行研究时，可以根据具体问 题的侧重点不同，将其进一步分解为三种情况：即r s y s t e m ( r 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 ) 和d r s y s t e m ( d e p o ta n dr e t a i l e rs y s t e m ) 一j 。在解决i r p 时，上层决策者或者组织通常必须要确定的三个方面是：配送时间和配送频率、客 户当前的库存量和为其配送的数量、运输策略。 2 1 2i r p 与其他相关问题的区别 1i r p 与库存一运输问题的区别 从本质上讲，i r p 是库存一运输联合优化问题中的一个分支，它也是有关库存 控制和运输路线选择的优化问题，但又因其自身的一些特征使得它又不同于库存一 运输联合优化问题中的其他问题，这些特征主要表现在研究对象、货物种类、拓扑 结构、需求特性、决策目标、费用因素、限制因素等七个方面1 5 1 。 2i l 冲与车辆路径问题的区别 车辆路径问题( 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 主要是将战略层次的决策与战术层次的库存控制和路径优化集成，此过程涉 及到客户所在的位置、客户的需求量、客户当前的库存水平、配送系统所有的车辆 数目、每辆车的运输能力以及单位运输成本等多个变型5 1 。 2 2i r p 的模型 目前，国内外学者研究比较多的主要是类似e o q ( e o q l i k e d ) 的模型、混合整数 规划模型和随机动态规划模型等三大类。 4 硕士学位论文 m a s t e r st h e s i s 2 2 1 类似e o q ( e o q 1 i k e d ) 公式的模型 1 9 1 5 年，美国的电气工程师h a r r i s 首次提出经济批量( e c o n o m i co r d e rq u a n t i t y , e o q ) 模型，随后许多研究学者将其作为经典的物流问题解决方法加以运用。w i k o n 也提出了与其相同的公式，并将其应用于库存管理，从而产生了多种由e o q 演变 的扩展模型。运用演变而来的e o q 模型( 即( e o q 1 i k e d 模型) 来解决问题的思想，也 被多位研究学者应用于i r p 。 早期对i r p 的研究主要采用的就是e o q 1 i k e d 模型对i r p 的各种问题进行分析。 b u m s 6 】建立了一个e o q 1 i k e d 模型来解决战术层的i r p 。他们主要研究的是由一个 供应商和多个客户组成的无限时间长度且配送货物为一种的物流系统。在假设客户 的需求率确定、所有客户的库存维持费用相同且运输费用仅与距离相关的前提下， 分别对零担运输和直达运输两种运输模式下使库存成本和运输费用之和最小的配 送策略进行了研究。h a l l 主要研究的是多对一( m a i l y t o o n e ) 的采购系统，在需求确 定、品种单一的假设条件下，建立了一种e o q 1 i k e d 模型，同时使用四舍五入近似 取最合理频率的方法来对i r p 进行分析 7 1 ；b l u m e n f e l d 为多对多( 多源点多汇点， m a n y t o m a n y ) 的多品种货运网络，建立了一种综合平衡库存、运输和生产准备费 用的e o q 1 i k e d 模型【8 】；d a g a n z o l 9 】所建立的模型与b l u m e n f e l d 8 】相似，但所考虑的 问题则更加细化：需方的需求是己知的，生产和运输能力无限，车辆行驶路线长度 不受限制以及大吨位货车的行驶区域也不受限$ i j t g j 。d a g a n z o 等【1 0 】和d a g a n z o 等【1 1 】 在需求确定、品种单一、运输费用仅与行走距离有关、存在库存费用的假设条件下， 分别从不同的角度为一对多( o n e t o m a n y ) 和多对多( m a n y t o m a n y ) 的配送系统建立 e o q 1 i k e d 模型；e 1 h o u s s a i n e 等为由一个配送中心和一系列需求确定的零售组成 的配送系统建立了一种e o q 1 i k e d 模型，同时把单一v r p 拓展为多v r p ，并使用 基于近似于列生成( c o l u m ng e n e r a t i o n ) 的算法，解决其产生的一系列子问趔1 2 】。 采用e o q 1 i k e d 模型所刻画的i r p ，较为直观且易于求解，但是有时使用这种 方法所求得的配送时间间隔可能为任意的非负实数，这在实际运作中不好操作或者 可能导致操作过程不合理。针对这种不足，h a l l 提出将由e o q 公式求得的值四舍 五入，取近似值为最合理的频率1 1 。还有一些其它的方法：如在离散频率集中寻优 【1 3 1 ，或利用p t ( p o w e ro ft w o ) 特性1 1 4 - 1 6 】规则来获得理想解，这些都是对特定问题的 一种近似处理方法。 2 2 2 混合整数规划模型 在解决i r p 时，使用纯整数规划模型和o 1 规划模型获得的最优解往往不是很 5 硕士学位论文 m a s t e r st h e s i s 理想，所以大多数的研究学者侧重于建立混合整数规划模型来解决这类问题。g l o v e r 等运用实例证明了建立混合整数规划模型较建立纯整数规划模型的优越性【r 7 1 。 f e d e r g r u e n 等研究了一种单周期配送系统下的i r p ，在客户需求随机、费用因 素包括有库存保管费用、缺货损失费用和可变运费构成的非线性库存费用的假设条 件下，为所研究的i r p 建立了一个非线性混合整数规划模型【1 8 】。c h i e n 等也对单周 期的i r p 进行了研究，作者首先假设所研究是由一个供应能力固定的配送中心和多 个需求确定的客户组成的配送系统，同时假设配送中心在为客户送货的时候可以不 完全满足客户的需求，但是必须承担因此所需支付的惩罚费用【1 9 l ，然后，在假设基 础上建立了一个混合整数规划模型，并通过对第一天与第二天之间的信息传递的了 解提出了一种比f e d e r g r u c n 等【1 9 j 开发的算法更有效的解决方案。d r o r 等则研究了多 周期i r p ，侧重于如何将长时段( 如每年) 的多周期问题简化为短时段( 如每天) 的单周 期问题。通过引入惩罚和激励因子柬反映相邻周期决策的相互影响，并且建立了相 应的混合整数规划模型【2 0 1 。g i e s e n 等通过在线实时信息来了解配送系统的随机需求 信息，然后通过设定滚动范围( r o l l i n gh o r i z o n ) 的方法建立了一个混合整数规划模型， 同时通过对滚动范围三种情况下的比较，得出一个基准的滚动范围【2 1 】。 2 2 3 随机动态规划模型 建立顾客需求未知的动态系统模型，是进行i r p 研究时一种较难处理的情况。 有关这方面的研究要追溯到g l o v e r 等i l7 j 的研究，他们所探讨的重点主要集中于时间 间隔未知情况下的动态配送问题。而后，b l a n c h i n i 等对这类问题进行了重新考虑， 建立了离散时间状态下的配送系统的随机动态规划模型1 2 2 1 。 对于库存路径随机动态规划模型，研究较多的学者是以b l a n c h i n i 为核心的研究 团队。b l a n c h i n i 等在建立随机动态规划模型时将单品种、多对多的物流系统看成是 一个网络，在这个网络中，节点代表客户所具有的需求( 一定范围内的某个随机值) 和存储能力，弧则代表运输路线，并且弧上的流量是随时间变化而变化的【2 3 1 。其后， 他们又在此基础上扩展了模型的限制条件，增加了对节点存储能力、弧的运输能力 以及客户需求最大值的限制，并求解出了可以满足所有顾客需求的最优的初始库存 水平】。进一步的，他们通过对两个相互独立的凸规划问题进行求解来建立随机动 态规划模型，并指出这两个独立的凸规划问题可以归纳为一个简单运筹学问题与一 个是典型的n p h a r d 问题1 2 5 j 。 虽然现有的很多研究文献已经表明：采用随机动态规划模型可以很好的刻画现 实状况，有利于i r p 的解决，但是，由于动态规划需要处理大量数据，并且约束条 件是指数增长的，很难应用于实际问题。因此，现有的随机动态规划模型多数只是 6 硕士学位论文 m a s t e r st h e s i s 侧重于理论研究。此外，随机动态规划模型对于一些更复杂的问题，如多商品流或 系统有限延迟的情况，都还无法刻画。 2 3i r p 的求解策略及算法 2 3 1 策略 在i r p 的求解策略方面，目前研究学者使用较多的是固定划分原贝j j ( f i x e d p a r t i t i o np o l i c i e s ，f p p ) 和马尔可夫决策( m a r k o vd e c i s i o np r o c e s s ，m d p ) 两种。 1 ) 固定划分原, 贝l j ( f i x e dp a r t i t i o np o l i c i e s ，f p p ) 在设计i r p 的求解方法时，研究学者讨论的一个重点策略是b a i t a 等所提出的 基于f p p 的策略，f p p 思想就是预先将客户划分到不同区域中，形成策略集f ，在 考虑车辆运载能力的前提下，f 中的最优策略是指具有最小的平均总库存和运输费 用的策略【2 6 j 。采用f p p 策略可以讲i r p 分为3 个求解过程： 1 ) 把将要研究区域的所有客户划分成包含一组某些客户的子区域。 2 ) 对已经划分好的每个子区域，运用旅行商问题的求解方法来确定最优的路线 长度和车辆行驶路线； 3 ) 把运输费用看成是固定不变的，运用变形e o q 公式来确定每个子区域的最优 配送频率及其配送数量。 b r a m e l 等在对无限车辆、动态的i r p 进行研究时，就选择了f p p 策略，作者 首先运用求解约束集中器选址问题( c a p a c i t a t c dc o n c e n t r a t o r l o c a t i o np r o b l e m ， c c l p ) 方法选择固定区域，然后提出一种基于地址的启发式算法对i r p 进行优化【2 刀。 a n t l y 等【2 9 】、c h a r t 等【3 0 1 等也采用f p p 方法对其所研究问题中的客户区域进行划分， 各个研究学者都从不同的角度对无限车辆i r p 进行了研究。 与以往需求确定的假设条件下运用f p p 思想分析i r p 有所不同，杜文等【3 1 】主要 研究的是在客户需求是随机情况下，如何运用f p p 思想来求解i r p ，文章中作者给 出了随机需求的近似确定化处理过程，建立了一种基于f p p 的s i r p 的数学模型， 同时将s i r p 转化为c c l p 问题，并给出了模型的具体求解步骤、求解方法的框架 结构的设计技巧的等1 3 ，但是在此研究中作者没有给出求解方法的渐进最优性证明 过程和相应的算例演算。 因f p p 策略的主要思想是首先把所有客户的总需求量抽象为n 个需求点，然后 将它们划分到不同子区域中形成策略集f ，那么，在一个客户有多个需求点的情况 下，就会出现一个客户可能同时存在于多个子区域中的现象，这样，运用f p p 就不 7 硕士学位论文 m a s t e r st h e s i s 能保证对存在于多个子区域中的这个客户进行协调服纠3 2 】。h a l l 在文献【3 2 】中指出 了f p p 策略的这种不足，并用算例说明如果采用协调服务来进行调节的话，将会进 一步降低物流系统长期的运行费用【3 2 1 。另外，也有相关的研究表明f p p 策略对处理 规模较大的i r p 很有效，但在处理较小规模的i r p 时，结果不是很理想，这样就使 得我们在选择运用f p p 策略的时候要谨慎考虑。 2 ) 马尔可夫决策过程( m a r k o vd e c i s i o np r o c e s s ，m d p ) m d p 是基于马尔可夫过程理论的随机动态系统的最优决策过程，它是马尔可 夫过程与确定性动态规划相结合的产物【5 0 l 。在m d p 中，决策者连续地或周期地观 察具有马尔可夫性的随机动态系统，序贯的做出决策。即决策者根据决策时刻观察 到的情况，从当前可用的目标行动集合中选择一个动作作出决策【5 0 j ，而此决策之后 的下一步的状态是随机的，其状态转移概率具有马尔可夫性，其后，决策者再根据 新观察的情况作l 叱新的决策，重复此过程直到为随机动态系统找到最优解【5 0 】。 k l e y w e g t 4 j 等将i r p 描述为m d p ，因以前的研究学者所使用的启发式算法不容 易解决m d p ，所以作者在文献【4 】中提出一种基于直接配送的动态规划方法，用其 解决i r p 。除此之外，k l e y w e g t 又做了更深的研究，他将每次直接配送的顾客从一 个增加到多个，同时为s i r p 建立一个一个马尔可夫模型，然后运用一般的方法求 解此模型，但是因为计算资料的限制，使得问题的求解结果不是很理想，于是 k l e y w e g t 又在文献【3 3 】提出了一些分解方法，使得s i r p 可以得到近似最优解1 3 引。 a d e l m a n 从价格导向的角度对s i r p 进行研究，作者首先将s i r p 描述为m d p ， 然后把问题转化成两个线性规划问题，并运用不同的方法从不同的角度进行求解， 得出最优的函数值【3 4 1 ，最后，运用m i n k o f f l 3 5 】提出的方法将各个最优函数值相加得 出整个问题的最优目标解。 赵达在对s i r p 进行研究时，将每个客户作为一个单位，把问题分解为几个子 问题，并将其描述为一个离散时间的m d p ，考虑到报酬的时间价值及动态s i r p 时 的无限特性，将动态s i r p 描述为一个无限期折扣模型，然后运用随机模拟技术得 到每个客户的状态转移概率，求解每一个m d p 过程，最后运用求解非线性背包问 题的方法，得到整个配送系统的满意解【3 酬。 2 3 2 算法 从对i r p 模型的求解方法来看，多数采用的是精确法、分解法和启发式算法。 对于阶段数少、规模小的i r p 一般采用精确法，例如：分支定界法、网络流方法以 及动态规划等即可以得到最优解：但是对于多阶段、规模较大的问题，上述算法的 求解时间会极剧增加，并且求解质量也会快速下降。因此，人们目前往往采用分解 8 一， 硕士学位论丈 m a s t e r st h e s i s 法来简化问题，或者采用遗传算法等启发式算法来求解。 1 精确算法 在求解i r p 时经常采用的精确算法包括解析法1 9 】1 1 0 】【1 1 1 、分枝定界法1 3 7 】1 3 8 1 、网络 流算法【2 3 】1 2 4 l 【3 9 】、动态规划【2 2 】【2 5 l 等几种。其中，解析法主要用来求解e o q 1 i k e d 模 型，这种方法实质是在不影响所研究问题的本质特性的前提下，采用有代表性的统 计数据而非繁杂的具体数据来寻求实际问题的解决方案【1 0 j 。由于这种思想建立的模 型易于理解和求解，尤其对于大规模物流系统，所以许多研究学者采用这种方法来 寻找模型的最优解，但是这种方法的使用是在特定的条件下进行的，需要一定的数 学技巧，不具有通用性，在采用时需要特别注意。对于另外的几种求解方法，因其 都是比较常见的运筹学问题解决方法，在这里对其具体的应用不再赘述。 2 分解算法 分解算法指将整个问题分解为一系列容易求解的小问题。前一问题的输出是后 一问题的输入。然后将这些解归纳、合并成一个完整解。这种方法在求解i r p 过程 中经常用到。 c a m p b e l l 等在求解客户需求确定的i r p 的时候，就提出了一种两阶段分解算法： 第一阶段用一个整数规划来决定计划期内每次对各个客户配送的时间和数量；第二 阶段在已知计划期内每次对各个客户配送的时间和数量的情况下决定每次的配送 路线 4 0 l 。不同于c a m p b e l l 的研究，b e r t a z z i 等【1 3 】在s p e r a n z a 等研究方法的基础 上，提出了一种3 步启发式算法解决多货物种类、一对多的配送物流系统，他们的 分解算法具体描述为：第一步是求解单连接问题，通过求解一个混合整数规划模型， 得到在某频率下运送的产品数量及所需的车辆数；第二步是对具有相同配送频率的 客户进行分组，同时以改善目标值为原则，来调整某些客户的配送频率；第三步是 对第二步确定的每一客户组合，分别通过求解节约法来确定配送路线和减小运费。 对于分解算法的使用，相关研究还有很多，譬如：f e d e r g r u e n 等采用广义斑德 分解算法( b e n d e r sd e c o m p o s i t i o na p p r o a c h ) 对其所建立的非线性混合混合整数规划 模型进行了求解1 1 8 j ；d r o r 等使用基于分层分解( h i e r a r c h i c a ld e c o m p o s i t i o n ) 思想的算 法对其建立的一个二阶段整数规划模型进行求解【4 引。 3 启发式算法 1 ) 构造法 优化问题的解是由若干个构造元素组成的，构造性启发式算法通过逐个增加解 的构造元素来求得可行解。目前，研究学者使用最多的种构造性启发式算法是贪 婪算法( g r e e d ym e t h o d ，g m ) ，这种算法的思想是：算法在一定的标准下求出每个阶 9 a ： 一， 硕士学位论交 m a s t e r st h e s i s 段的最优决策，决策一旦做出，就不可再更改。 s a v e l s b e r g h 等引入随机的g m 来解决动态i r p ，其使用的g m 与典型的v r p 的插入式启发式解决方法非常相似，但因动态i r p 自身的特性，使得这种g m 又有 所不同。作者比较了基本的g m 、扩展的g m 以及扩展的随机g m 三者之间的异同 点，并使用扩展的随机g m 来确定动态i r p 中的运输路线、运输时间、运输数量以 及所要访问的顾客数副4 3 1 。s i n d h u c h a o 等1 3 6 】使用g m 结合大规模域搜索算法来寻找 日用品i r p 的近似最优解。 两阶段法 学者们通过对构造法的研究，认为由构造法求得的解可以被进一步改进，为此 提出了两阶段法。第一阶段得到一个可行解，第二阶段通过对第一阶段解的调整， 在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解来 代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。 两阶段法可应用于复杂的i r p ，尤其是多源点、多汇点或者是两者兼有的情况 ( 如：d a g a n z o 【9 】) 。c a m p b e l l 认为i r p 实质上是v r p 的一种变异，因此，他从这一 角度出发，提出了一种基于分解策略的两阶段方法：第一阶段使用整数规划的方法 建立一个运输时间表，并据此确定运输路线；第二阶段使用启发式算法确定路径和 行程安排，以此来解决大规模的实际配送问题【删；蒋赛在具体求解i r p 时采用的是 传统的两阶段方法，即将原问题分解为库存补充问题和运输路线问题两个基本问 题：在第一阶段决定当前周期为哪些客户补货，包括每一天为哪些客户服务，各自 的配送量应该为多少等；而配送的具体细节，比如哪辆车应该选择哪条线路，每条 线路的起始时间如何，为哪些客户服务，经过不同客户的先后顺序应该如何等，这 些细节问题放到第二阶段来处理，即第二阶段给出运输调度计划【矧。 3 ) 改进的启发式算法( 亚启发式算法) 启发式算法的最新发展主要体现在以禁忌搜索算法( t a b us e a r c ha l g o r i t h m t s ) 、 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 、模拟退火算法( s i m u l a t i o na n n e a l i n ga l g o r i t h m s ， s a a ) 、神经网络方法( n e u r a ln e t w o r k sa l g o r i t h m ，n i 蛆) 、蚁群算法( a n tc o l o n y a l g o r i t h m ，a c a ) 等为主的一批亚启发式算法在旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 、选址问题、v r p 及其组合问题中的应用，但这些新方法在i r p 及其 相关问题中的研究还冈j j 刚开始，并且仅仅只是t s 、g a 等在这些问题上的运用。 t