（管理科学与工程专业论文）库存路线问题.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 供应商管理库存( v m i ) 的思想为供应商通过统筹规划运输和库存计 划来勰决运输和库存之间“效益悖反( t r a d e o f f ) ”的矛盾及实现降低 物流成本的目标提供了新的契机。本文所提出的库存一路线问题( i r p ) 是从管理运筹学的研究视角出发通过关注库存和运输两个物流环节的集 成优化来解决物流管理在作业操作层面上的计划职能必须回答的问题一 一如何制定库存补充计划和车辆配送路线安排计划。 然而，在国内无论是研究学者对库存一路线问题( i r p ) 的理论探讨 还是物流实践者对综合考虑库存控制和运输路线计划的物流策略的实际 应用在目前如火如萘的物流理论研究和物流实践中都显得有些孱弱。因 此，本文试图对库存路线问题( r p ) 进行有益的理论探讨，并展现理 论探讨结论在实践中的应用。以此为目标，本文组织安排了以下的内容。 酋先，介绍库存路线问题( i r p ) 的研究背景及其理论与实际意义。 在对相关文献研究分析和总结的基础上介绍了该问题的研究对象、范围、 特点等，其目的在于了解、认识i r p 。明晰了本文以具有d - - s y s t e m 特性 的o n e m a n y 拓扑结构的单物品物流配送系统为研究对象讨论客户需求 确定条件下的固定计如期长度库存路线问题( i r p ) ，并给出从该角度研 究i r p 的原因。介绍了本文舰划和求解库存一路线问题( 】r p ) 的总体解 决方案两阶段法，即将i r p 问题分解成库存补充计划和车辆路线安排 两个子问题，经过先后两个连续阶段来分别求解两个子问题，。 其次，在第一阶段使用整数规划数学模型来规划库存补充计划子问 题，以减少车辆巡回路线数目为求解该整数规划的突破口，提出与固定划 分策略( f p p ) 相似的客户分组思想，通过径一环切割法把整个配送区域 划分成多个客户子集，实现客户分组并确定服务整个配送区域的最佳车辆 数目。在客户分组的基础上建立了精简路线的整数模型，然后通过运用两 条基于实际经验的判断来进一步减少巡回路线数目，进而极大地减少了整 数规划的变量规模并利用专业的求解软件来求解该整数规划问题，从而 确定计划翔的库存补充计划。 然后，在第二：阶段借用车辆路线安排问题( v r p ) 的理论和方法，以 第一阶段的库存补充计划为基础，将第二阶段的子问题规划成有时l h j 窗约 束的车辆路线安排问题，利用混合遗传算法求解该问题，从而最终形成完 西南交通大学硕士研究生学位论文第1 | 页 整的库存补充和运输计划。 最后，本文以一个物流实例为对象进行实例分析，佐证理论探讨的结 论并体现各阶段求解方案的有效性、阶段之间决策的连续性以及解决方法 对制定实际配送作业计划的指导价值。 关键词：库存一路线问题( i r p ) ：供应商管理库存( v m i ) ；车辆路线问题 ( v r p ) ：遗传算法( g a ) 三 西南交通大学硕士研究生学位论文第1 | i 页 a b s t r a c t v e n d o rm a n a g e d i n v e n t o r y ( v m i ) p r o v i d e san e w c 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 “订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 d i n v e n t o r ya n d r e d u c el 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 f t 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 eo fm a n a g e r i a l o 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 g p r o b l e m ( i r p ) i nt h i sp a p e ri 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 e i n t e g r a t i o n a n d o p t i m i z a t i o n o f i n v e n t o r y a n d t r a n s p o r t a t i o n ，i n v e n t o r y s 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 hh a v et ob ed e t e r m i n e di np l a n f i m c t i o ns t e pa tt h el e v e lo f o p e r a t i o n i nl o g i s t i c sm 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 n1 r po 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 r w e a ki nc u r r e n t r a p i d l yd e v e l o p i n gl o g i s t i c s r e s e a r c ha n d p 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 r pt h e o r e t i c a l l y , a n di l l u s t r a t e t h ec o n c l u s i o no fd i s c u s s i o ni np r a c t i c e i no r d e rt oa c h i e v et h i s g o a l ，t h i s p 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 ，i no r d e rt od e v e l o pa r u n d e r s t a n d i n go fi r p , t h i sp a p e r i 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 dp r a c t i c a ls i g n i f i c a n c e ，i n a d d i t i o n ，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 e a 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 gl i t e r a t u r e t h er e s e a r c ho b j e c to ft h i s p a p e ri ss i n g l ep r o d u c tl o g i s t i c sd i s t r i b u t i o ns y s t e mo fo n e m a n yn e t w o r k w i t h t h ep r o p e r t i e so f d s y s t e m i tm a k e s ad i s c u s s i o na b o u tf i x e dp l a np e r i o di r p u n d e rd e f i n i t ec o n d i t i o no fc u s t o m e rd e m a n d ，a n de x p l a i n sw h yi td o e ss o t h e ni ti n t r o d u c e st h eg e n e r a ls o l u t i o no fi r p , t w o p h a s em e t h o d ，n a m e l y , d i v i d i n gi r pi n t o t w o s u b - p r o b l e m s o fi n v e n t o r y s u p p l e m e n ta n dv e h i c l e r o u t i n g ，t h e ns o l v i n gr e s p e c t i v e l yt h e s es u b p r o b l e m si n t h et w oc o n s e c u t i v e p h a s e s s e c o n d l y , i nt h ef i r s tp h a s e ，t h i sp a p e rs o l v e st h ei n v e n t o r ys u p p l e m e n t s u b p r o b l e mt h r o u g hi n t e g e rp r o g r a m m i n gm o d e l ，u s i n g t h er e d u c t i o no f v e h i c l er o u t e sa st h e b r e a k t h r o u g h t ot h i s p r o b l e m ，d i v i d e s aw h o l e d i s t r i b u t i o nr e g i o ni n t om a n yc u s t o m e rs u b s e t sb yr a d i u s c i r c l ep a r t i t i o n i n g m e t h o d ，d e t e r m i n e st h eo p t i m a ln u m b e ro fv e h i c l eo fs e r v i c e d i s t r i b u t i o n r e g i o n ，a p p l i e st w op r a c t i c e o r i e n t e d c o n c l u s i o n st or e d u c et h en u m b e ro f 西南交通大学硕士研究生学位论文 第f 、，页 r o u t e so nt h eb a s i so fc u s t o m e rg r o u p i n g ，t h u sd e c r e a s e s c o n s i d e r a b l yt h e v a r i a b l es c a l eo fi n t e g e r p r o g r a m m i n g ，a n d s o l v e st h e p r o b l e mt h r o u g h p r o f e s s i o n a ls o f t w a r e t o6 x i n v e n t o r ys u p p l e m e n p l a n i np l a np e r i o d a f t e r w a r d s ，i nt h es e c o n dp h a s e ，b a s e do nt h ei n v e n t o r ys u p p l e m e n tp l a n i nt h ef i r s tp h a s e ，t h i sp a p e rt r a n s f o r m st h e s u b p r o b l e mi nt h i sp h a s ei n t o v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o wc o n s t r a i n st h r o u g ht h et h e o r i e sa n d m e t h o d so fv r p , a n ds o l v e st h i sp r o b l e mb yw a yo fg e n e t i ca l g o r i t h m ，t o m a k eaf i n a lc o m p l e t ei n v e n t o r ys u p p l e m e n ta n d t r a n s p o r t a t i o np l a n m o r e o v e lt 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 y a 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 f s o l u t i o n si ne v e r yp h a s e ，t h e d e c i s i o n c o n t i n u i t y b e t w e e np h a s e sa n dt h e g u i d a n c es i g n i f i c a n c e o ff i n a l s o l u t i o nt op r a c t i c a ld 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 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 n d o rm a n a g e di n v e n t o r y ( v m i ) ：v e h i c l er o u t i n gp r o b l e m ( v r p ) ；g e n e t i c a l g o r i t h m ( g a ) 西南交通大学硕士研究生学位论文第1 页 第一章绪论 1 1 问题的提出 2 0 世纪8 0 年代以来，全球性市场竞争目趋激烈，企业为了提高竞争 力不断寻求各种措施提高企业对市场需求的响应速度、降低企业的运作成 本。在此背景下，供应链管理思想得到迅猛发展和广泛应用。供应链管理 强调企业应该将有限的资源用来持续提高企业自身的核心竞争力，同时在 不同企业问建立长期合作伙伴关系，在信息和知识共享、团结合作关系充 分发展的基础上，供应链伙伴将寻求更深层次的整合。由于供应链上的某 一个伙伴可能处于更适合的位置来执行某个通常由另一个伙伴拥有的决 策权，所以如果把这个决策权从这个合作伙伴转给更适合的合作伙伴，那 么整个供应链的效率将得到改善。在这一思想的指导下，处于同一供应链 中的不同企业开始在企业间交换某些决策权、工作职责和资源，以加强协 作，共同努力开拓市场。v f l i 思想正是在供应链管理快速发展的趋势下产 生并被广泛应用。 具体来说，供应商管理库存( v m iv e n d o rm a n a g e di n v e n t o r y ) 是一 种以用户和供应商双方都获得最低成本为目的，在一+ 个共同的协议下出供 应商管理供应商和用户的库存，并不断监督协议执行情况、修证协议内容， 使库存管理得到持续地改进的合作性策略。 v m i 的理念与r m i ( r e t a il e rm a n a g e di n v e n t o r y 零售商自己管理库 存) 的传统库存管理模式完全相反。在传统库存管理模式下需求的逐级放 大将导致供应链中各个环节库存的异常波动，这对供应链效率和响应速度 的影响是不言而喻的。作为对该f 1 题的解决方法，v m l 意味着供应链下游 企业放弃库存管理权，这对他们似乎是一种损失，但是他们从中得到的远 比要失去的多得多。 首先，相对于r m i 而言，v m i 克服了下游企业自身技术和信息系统的 局限。随着供应链各个环节的企业核心业务的迅猛发展，供应链上游对下 游的后勤管理( 包括库存管理) 也提出了更高的要求。但由于下游企业原 来的自营库存管理系统往往因为技术和信息系统的局限而严重滞后，制约 了其业务的发展。实施v m i 之后，库存由供应链上游企业管理，下游企业 可以放歼手脚进行核心业务的开发。 西南交通大学硕士研究生学位论文第2 页 其次，v m i 还可以满足下游企业降低成本和提高服务质量的需要。与 下游企业自己管理库存相比，供应商在对自己产品的管理方面更有经验、 更专业化。用户自己管理供应商存货很可能导致错误的产品储存和库存补 充决策。而供应商可以提供包括软件、专业知识、后勤设备和人员培训等 一系列的服务，供应链中企业的服务水平会因为实旖v m i 而提高，下游企 业不仅不必为何时订货、要订多少货物等库存控制决策投入人力，而且存 货投资和库存管理费用也会大幅度减少。 而且，由供应链管理思想衍生出来的v m i 本身追求的就是双赢的结局， 它同时也给处于供应链上游的供应商带来许多利益。v m i 允许供应商获得 下游企业的必要经营数据，直接接触真正的需求信息( 通过电子数据交换 ( e d i ) 来传送) 。供应商在取得自主库存补充决策的同时，便具有了运输 计划和库存控制的双重决策权，从而可以充分利用自己的资源，对运输路 线和库存补货做出更有效率、更加灵活的决策。 库存一路线问题( i n v e n t o r yr o u t i n gp r o b l e mi r p ) 就是在如何同 时优化运输和库存两个物流环节的现实需求推动下成为崭新的研究领域。 但是，如何制定有效的库存补充和运输路线安排计划来满足客户的需求并 不是一项轻松的任务。尤其在客户数量较多、地域分散的情况下，作业计 划制定者将面临巨大的挑战。 1 2 库存路线问题( i r p ) 的研究意义 库存成本和运输成本是企业乃至整个社会物流成本的两个主要组成 部分。无论库存控制研究还是运输优化研究，都成为运筹学研究的经典问 题。但是这些研究通常将库存和运输作为单独的问题来研究而没有将两方 面的影响因素规划到同一个模型中，所以本文将影响库存控制和运输路线 安排决策的两方面影响因素规划到同一个模型中，考虑两方面不同因素彼 此间的影响，同时尽可能使模型的描述和规划符合实际时操作要求，能对 有关库存运输联合优化问题的研究具有理论上的借鉴作用。 此外，由于v m i 管理的思想得到广泛应用，不仅在石化工业，而且在 零售业、服装业、软饮业、汽车制造等行业都有成功应有的案例。并且由 于通信技术和计算机技术的快速发展，对客户库存水平实时监控的目标比 以往任何时候都容易实现。所以给出具有实际指导意义的配送作业计划不 西南交通大学硕士研究生学位论文第3 页 仅是完全可能，并且能够带来库存成本和运输成本的大幅度降低。 1 3 库存一路线问题( ir p ) 的定义 通常，库存一路线问题( i r p ) 主要是研究这样一类问题：在有限( 或 无限) 计划期7 内，由一个供方向 个客户提供配送服务，客户c ，每天的 需求量为“，最大库存容量为c ，初始库存为，? ，有m 辆最大载重为q 的 车辆供供方调度安排，在保证每个客户不出现缺货的前提下使由供方和需 方组成的物流系统在整个计划期内的运作成本最小。 库存一路线( i r p ) 计划决策者一般必须对三个主要问题进行决策： 1 、时间或频率 如果计划期长度已经确定，则需要决策在什么时候为哪些客户提供配 送服务：如果计划期长度未知，则需要决策在整个计划期内以什么样的频 率为客户提供配送服务。 2 、配送量 在了解客户需求信息后，决策者需要确定在每次配送时为配送路线上 每个客户提供的配送量是多少。 3 、运输路线 配送车辆选择怎样的运输路线依次访问不同的客户从而完成配送任 务。 其中前两个决策主要考虑的是库存控制问题，第三个决策涉及运输路 线安排问题。 1 4 库存一路线问题( 1 r p ) 研究特性 从本质上讲，库存一路线问题( i r p ) 是库存控制和运输路线选择的 集成优化问题，是库存一运输联合优化问题领域中的一个分支。其自有的 研究特征使其区别于库存运输联合优化决策家族中的其它问题。下面从7 个方面来介绍库存一路线问题( i r p ) 的特性。 1 、决策目标 从决策者进行决策时所要解决的问题来看，库存一路线问题( i r p ) 西南交通大学硕士研究生学位论文第4 页 主要解决客户的配送时间或频率、配送量以及配送车辆的行驶路线及刚问 安排等几个问题。不涉及诸如运输方式( 火车、航空、水运、汽车) 和运 输批量等其它运输决策。 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 ta n dr e t a il 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 、费用因素 主要涉及运输和库存费用。运输相关费用包括启用运输工具的固定费 西南交通大学硕士研究生学位论文第5 页 用及与行驶距离相关的可变费用，有时也包括运载工具在需方停留的费 用。库存相关费用主要由货物保管费用、缺货损失费和订货费构成。 6 、限制因素 涉及的具体问题不同，求解问题的限制也不同。一般都包含几个主要 因素，如运载工具的载重量，供方的供应能力，需方的存储能力，可执行 运输任务的运载工具数量，运载工具每天的最大行驶距离，需方的时间窗 限制等。 7 、需求特性 需求可分为三种情况：需方的需求量已知；需求量是随机的，但需求 的概率分布特性已知；需求特征完全未知。 在库存一路线问题( i r p ) 的决策变量中虽然也涉及到车辆路线安排， 但是库存一路线问题( i r p ) 与常见的车辆路线安排问题( v r p ) 有很大的 不同。 首先，传统的车辆路线安排问题( v r p ) 只有在客户发生订货行为时 才发生，其解决的主要问题是如何将提出订货要求的客户分配到车辆的巡 回路线上以及在同一巡回路线上车辆访问客户的先后顺序。而在库存一路 线问题( i r p ) 中，没有客户定单，完全由供应商而不是客户决定配送的 数量以及在计划期内的每一天为哪些客户补充库存。虽然供应商具有完全 独立自主的库存控制和车辆调度权利，但是供应商要保证客户不会出现库 存短缺现象，否则会损害供应商与客户之间的信任关系。 其次，库存一路线问题( i r p ) 与车辆路线安排问题( v r p ) 的计划期 长度不同。v r p 研究的是在给定的菜一天内如何安排车辆行驶路线来提供 配送服务，从而满足客户的定单要求，模型的计划期大多为一天。在i r p 问题中，尽管有的文献研究的是单日i r p 问题，但更多的文献研究的是计 划期长度为一周或一个月乃至一年的i r p 问题不仅要确定每天访问的客 户名单和配送的数量，而且要考虑当日所做出的库存补充和车辆路线安排 计划对以后作业计划的影响。由于供应商在选择服务客户以及确定客户库 存补充数量的决策上具有较大的自由度，所以使求解该类问题相对困难。 1 5 库存一路线问题( 1 r p ) 研究的成果 目前，在国内尽管有关库存和运输方面的研究文献很多，但是还没有 发现有的研究文献引入i r p 这一术语。当然，这并不是蜕在国内没有相关 西南交通大学硕士研究生学位论文第6 页 研究。事实上就研究对象和内容而言，在为数不多的有关库存一运输联合 优化问题的研究文献中，有的文献已经涉及到i r p 问题。 国外对库存一路线问题( i r p ) 的研究要早于国内，而且研究文献更 为丰富。根据计划的长度和需求类型可将这些研究文献分为以下几类： ( 1 ) 单同i r p 模型，计划期长度仅为一天( 又可以分为需求确定或 随机需求两种) 。 ( 2 ) 多同i r p 模型，计划期长度超过一天，但不超过一季度或。年 ( 又可以分为需求确定或随机需求两种) 。 ( 3 ) 无限期i r p 模型，也称为永久路线问题( p e r m a n e n tr o u t i n g ) ， 即一旦确定了车辆的巡回路线，则在以后的配送服务中，车辆的行驶路线 不会发生变化。 不同的研究文献除了对计划期长度以及需求类型这两个关键因素采 用不同的处理方式外，在“如何考虑短期决策对长期决策的影响”这一问 题上也表现出较大的差异性，从而也丰富了库存一路线问题( i r p ) 研究。 纵观i r p 的研究历史会发现有关i r p 研究呈现出如下的研究趋势： ( 1 ) 计划期长度增加。从早期的单日模型发展到多日模型乃至无限 期模型； ( 2 ) 决策层次提高。从以作业层计划决策为主到兼顾战略层决策( 如 供方需要的车辆数目) ； ( 3 ) 需求特性更为复杂的。从研究确定需求i r p 问题到研究随机需 求乃至动态随机需求。 下面就对整个库存一路线问题( i r p ) 的研究发展做简短的回顾。 1 5 1 单日库存路线问题( i r p ) 文献 1 是较早研究库存一路线问题( i r p ) 的文章之一。其所研究的 是将一种稀有资源从单个供方配送到多个客户( o n e m a n y ) 的i r p 问题， 所研究的物流系统具有r s y s t e m 特性。其中，供方的库存有限，计划期 长度为天，并假设客户需求为随机变量，系统成本既考虑运输费用也考 虑了由库存保管费及缺货损失费构成的库存费用。在指定的某一天，该库 存路线问题( t r p ) 可以描述为如何在多个客户间分配有限的库存从而 使该日内所有客户的库存成本、缺货成本和运输费用总和最小。浚文献利 用了很多车辆路线安排问题的理论和方法，建立一个非线性混合整数规划 西南交通大学硕士研究生学位论文第7 页 模型，并且采用广义斑德分解算法( 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 ) 来求解，将该问题分解成库存分配问题( 目标函数为库存成本和缺货成本 最小) 和旅行商问题( 标函数为运输费用最小) 。 文献 2 讨论的是单对多的液态甲烷配送系统。假定每个客户的存储 能力和安全库存水平已知，系统目标是在单日内在保证所有客户有相对足 够库存的前提下，使由库存费用和运输费用构成的系统运作费用最小。该 文献假设作业计划的制定者每天要做的主要工作是：( 1 ) 预测客户需求： ( 2 ) 确定哪些客户需要补充库存；( 3 ) 安排每辆车的行驶路线。该文献 使用启发式算法来构造了一个模拟模型来均衡库存和运输相关要素之问 的相互影响。首先计算所有客户需要补充库存的紧急程度，补货紧急程度 是由库存水平与仓库容量的比值决定的，然后为那些库存补充紧急程度大 于某一定值的客户提供补货服务。 文献 3 也研究了单日库存一路线问题( i r p ) ，但是与文献 2 所研 究的不同之处在于连续两天的决策并非完全相互独立。通过信息传递，前 一天的决策会影响后一天的库存一路线计划，在此基础上该文献模拟了连 续几天的作业计划。首先假设每个客户每天的最大库存量已知，供方每送 出一个单位库存物资，就会增加相应收入，每少送一个单位库存物资，则 给出一个惩罚值，模型的目标函数为使供方每天利润最大。一旦前一天的 作业计划确定，则前一天没有满足的需求会在后一天得到满足，这样后一 天的目标函数也随之被修改。采用整数规划的方法给出库存分配、客户选 择和车辆路线安排。 1 5 2 多日库存一路线问题( i r p ) 文献 4 5 研究了计划期长度为多同的库存一路线问题( i r p ) 。该 文献所定义的目标函数为在长达几天的计划期内使供方获取的利润最大。 客户需求既不是随机变量，也不是确定的常量。该文献给出在计划期内每 一天客户需求的最大值和最小值。使用整数规划确定配送数量、访闻不同 客户的路线以及车辆巡回路线的起始时间，在求解该整数规划时使用了拉 格朗f 1 松弛算法。 文献 6 7 研究的主要内容是如何将计划期较长的多周期问题简化 为时间跨度较短的单周期问题，同时也要考虑短期计划决策对下一周期乃 至整个年度计划的影响。由于在短期计划期内，在确定每一天的配送路线 西南交通大学硕士研究生学位论文第8 页 和配送数量时都要考虑客户的未来需求，因此增加了问题求解的难度，所 以在此之前几乎没有相关的研究文献。该文献首先给出在计划期内的每一 天中每个客户出现缺货的概率、每次配送的运输成本、缺货损失的期望成 本，然后计算出使整个期望成本最小的每个客户的最佳库存补货日期f + 。 如果f 落在短期计划区间内，则在短期计划内一定要为该客户补货，如果 某一客户不在最佳补货同期，补货而是在第f 天，则用c 表示其引起的未 来费用增加值。如果f 落在短期计划区外，则用舟表示在短期计划内的 第f 天为客户补货所带来的未来收益增加值。通过c ，和譬，可以反映出短期 计划决策对长期计划决策的影响。最后使用整数规划的方法首先确定客户 补货的日期和提供补货服务的车辆，然后求解一个v r p 问题给出每辆车的 行驶路线。 文献 8 1 0 使用滚动规划的方法来确定连续两周的作业计划，在实 际运作中只执行第一周计划。其使用了与文献 6 7 相似的思想来确定每 个客户的最佳库存补充日期，如果某一客户不能在最佳库存补充日期补 货，则会增加运作成本，通过使增加的总成本最小来求出计划期内每一天 该为那些客户补货，然后求解每一天的v r p 问题。 1 5 3 无期限库存一路线问题( i r p ) 无期限i r p 问题研究文献在制定配送计划时通常采用“永久路线”的 处理方法，即假设一旦确定了车辆的行驶路线，则车辆的行驶路线不再改 变，每辆车所访问的客户集合及每次的配送数量也不发生变化。事实上， 只要知道车辆行驶路线的规律，就可以确定满足这些配送服务所需要的运 输能力，因此，有的研究文献从“确定满足配送服务需求的最少车辆数量” 这一角度来看待此类问题，并将该类i r p 问题称为战略库存一路线问题 ( s i r p ) 。文献 1 1 在运用节约算法的基础上构造了2 个称为s i r s a ( s t r a t e g i ci n v e n t o r y r o u t i n gs a v i n ga l g o r i t h m ) 的启发式算法，用 于帮助纽约市环卫局确定为其所拥有的港口提供配送服务所需要的驳船 数量，目标是希望用最少的船来完成所有的送货任务。其所采用的处理过 程是先将所有的客户( 港口) 进行分组，然后为每一组客户指派一艘船并 确定该船的最优行驶路线。文中假设每组中的所有客户以同样的频率接受 西南交通大学硕士研究生学位论文第9 页 补货服务。但基于此假设得到的解并不理想，如有一个港口每周接受凡次 补货，但实际上这个港口每4 0 天为其补一次货就足够了。针对文献 1 1 的不足，文献 1 2 提出了一种周期和阶段性的客户补货方法，首先采取了 与文献 1 1 相似的处理方法，即将所有的客户分成不同的客户集，然后为 每个客户集中的所有客户确定一条最优的访问路线，设计的算法也是基于 节约法的启发式算法，与文献不同的是将为客户送货的周期和阶段作为附 加的决策变量。 文献 1 3 1 4 也研究了无限期库存一路线问题( i r p ) ，并且假设每 个客户需求是确定的，需求率不小于l 。该文献首先将所有客户的需求简 化为具有相同需求率的n 个需求点，然后通过扇形区域划分法来得到对整 个服务区域的一组划分。每个区域内的客户总需求不超过一辆车的最大载 重，同时尽量使车辆满载。由于按客户的总需求划分，则某个客户可能出 现在两个或多个不同的区域内，各个不同区域分别负责满足一定比例的需 求数量i 一旦区域内的某个客户补充库存，则该区域内的所有客户都要补 充库存。 文献 1 5 在文献 1 3 的基础上设计了在。集中渐进最优的启发式算 法。首先是对所有零售商的需求点进行分组。与文献 1 3 不同的是该文献 以距离和库存保管费用的比率而非仅用客户的地理分布特征作为标准，然 后将整个配送区域划分为不同的子区域。研究的目标是使系统长期运行的 平均运输费用和库存费用最小的运输策略和库存策略。 以上各个研究无限期库存一路线问题( i r p ) 的文献都采用了基于固 定划分( f p p ，f i x e dp a r t i t i o np o l i c i e s ) 原则的研究方法。所谓f t p 的原则就是预先将客户划分到不同区域中，形成策略集中。在考虑车辆运 载能力的前提下，中中的最优策略是指具有最小的平均总库存和运输费用 的策略。确定中中的最优策略显然是n p h a r d 问题，因为这需要寻找一个 供货方与某个区域中所有客户之间的哈密尔顿回路。但是，以客户数和最 优的哈密尔顿回路长度表达的每个区域的长期平均费用结构非常类似与 e o q 问题的费用结构，这样的结构特性无论是从建模角度还是从算法设计 的角度都使得处理i r p 问题变得相对简单。采用基于f p p 的方法求解i r p 问题的过程可分为三个阶段：( 1 ) 对配送区域内的所有客户进行划分， 形成一组包含部分客户的子区域。划分的标准可以是距离等；( 2 ) 对每 一个子区域，采用某种求解t s p 问题的算法确定最优的车辆行驶路线及路 西南交通大学硕士研究生学位论文 第10 页 - _ _ _ _ _ _ _ _ _ _ - _ - _ _ _ _ - _ _ _ _ - _ _ _ _ - _ _ _ _ - _ _ _ - - - 一i - _ _ - _ - _ _ - - _ _ - - _ _ - 线长度：( 3 ) 将运费看作固定费用，采用变形的e o q 公式确定每一个予 区域的最优配送量和配送频率。 由于f p p 方法的主要思想是将所有客户的总需求量抽象为n 个需求点 并将他们划分到不同予区域中形成策略集m ，所以对于可能有多个需求点 的客户这容易导致该客户同时存在于多个子区域中，但f p p 方法并不能 保证对存在于多个子区域中的同一个客户进行协调服务。文献 1 6 指出了 f p p 方法的这种不足之处，并用算例说明如果采用协调服务会迸一步降低 系统的长期运行费用。该文献分析了服务的不协调导致系统费用升高的原 因，即：( 1 ) 运载工具的总行走距离会增加；( 2 ) 客户为了保证一定的 服务水平而需拥有的设备数量增多。文献 1 7 也采用f p p 方法对库存一路 行问题( i r p ) 进行研究。文中考虑的费用因素包括客户的库存保管费和 与走行距离相关的可变运输费用，客户需求确定且库存能力无限，供货方 的供应能力也无限。该文设计了一个基于选址问题的算法来确定对整个配 送区域的一组划分。 1 6 本文研究对象的主要特点和研究内容 1 ，6 ，1 研究的对象的主要特点 1 、物流系统特性 本文研究的物流系统具有d - s y s t e m 特性，即不考虑需求方的库存费 用，此费用由需求方自己负责。决策者以保证所有需方不出现缺货为前提， 以为所有需求方补货的运输费用整体最小为决策目标。系统拓扑结构为 o n e - - & l a n y ，以一个配送中心( 供方) 和多个零售商( 需求方) 为本文研 究得现实背景，物流系统示意图l 一1 。 2 、需求特性 在现实物流配送系统中通常无法准确预测客户需求，每个客户在每一 天、每个时段所需要的货物数量总是不断变化的，所以客户需求是一个随 机变量。为了准确地刻画客户需求所具有的随机性特点，越来越多的学者 研究了随机库存一路线目题( s i r p ) ，并有一些学者使用马尔可夫决策模 型( m a r k o vd e c is i o np r o c e s s e sm d p s ) 来求解该类问题。马尔可夫决策 模型通常包含以下决策变量：决策状态、转移概率等：但是当问题规模较 大、复杂度较高时使用马尔可夫模型来求解s i p r 问题异常困难。首先， 西南交通大学硕士研究生学位论文第1 1 页 图l l o n e - - m a n y 结构物流系统示意图 如果客户的数量较多且客户的最大库存容量差异较大，则用马尔可夫模型 描述的状态空间变量数目众多，导致不同状态空间之间转移的可能途径呈 几何级数增长。其次，难以确定状态之间合适的转移概率。 以上因素使马尔可夫决策模型的求解过程所涉及的计算量极大，从而 不具有较强的实用性。但由于其对库存一路线问题的描述更接近现实情 况，相信这将是未柬研究i r p 问题的一个方向。文献 1 8 就使用了马尔可 夫模型探讨了简单的i r p 问题的求解过程和方法。 此外也有一些其它的方法尽管不是采用马尔可夫模型但是也考虑到 客户需求的随机特性，比如文献 6 7 ，但是为了在充分考虑客户需求具 有随机性特点的同时使求解过程相对简单，该文献采取了依次单独为每个 客户确定最佳库存补充日期和配送数量的处理方法。例如，在确定某个客 户的最佳库存补充日期时，并没有考虑与该客户临近的其它客户在同一 天、同一车辆巡回路线上补充库存所带来的益处。 考虑到以上现有随机库存一路线问题( i r p ) 研究方法存在的不足， 并且为了能够在本文所提出的模型中包含其它更多的符合现实的复杂情 况并使求解过程较快，从而满足实际作业操作的要求，本文将以客户需求 确定型库存一路线问题( i r p ) 为研究对象。尽管需求确定型库存一路线 模型无法像随机库存一路线模型那样准确刻画客户的需求特性，但是以下 两种措施将有助于本文所给出库存一路线作业计划具有较强的实际指导 西南交通大学硕士研究生学位论文第12 页 价值。 ( 1 ) 采用滚动作业计划的方法。本文虽然主要研究需求确定型的库 存一路线问题( i r p ) ，但并不意味在给出作业计划后便在整个计划期内都 会不折不扣的完全执行该计划而不考虑其它可变因素。为了使作业计划更 具有灵活性并能够充分利用最新变化的数据最大限度地适应不断动态变 化的现实情况，本文将使用滚动作业计划技术。 ( 2 ) 根据以往的客户需求的历史数据，运用有效的预测工具和使用 高效、科学的预测方法，找出客户需求的规律，尽可能对客户需求做出近 似准确的需求预测。事实上，在某些行业( 如服装业) ，通过有效的预测 方法能够确定客户需求具有随季节变动的特点。此外，在大多数情况下， 短期预测较为准确，预测时间越长。准确性就会下降，预测的价值也随之 下降。所以，在i r p 模型中考虑的适当长度的计划期也将有利于提高作业 计划的准确性。 3 、计划期长度 如果能够准确预测在遥远的将来所有客户的需求状况，就可以在制定 当前计划时尽量考虑到未来的影响因素。在大多数情况下，可以非常准确 地预测未来短期内客户的需求情况，但是这种准确性随着时间的增加而递 减。对于计划制定者而言，随着预测准确性的下降，预测的价值则相应降 低。 但是为了求得使系统长期运作成本最小的作业计划，又希望计划期尽 可能长。尤其希望计划期无限长。 然而，毫无疑问，在解决一个无限期i r p 问题时，逐日最小化成本并 不是一个最好的方法，这种只顾眼前的短视计划极有可能导致次日配送任 务延迟，无法确