（管理科学与工程专业论文）易腐品配送中的库存—路径问题研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 鉴于易腐品的特性 对其储存 运输等物流环节进行优化管理 可有效减少变质 损耗 实现易腐品的及时配送 具有重要的理论和实际意义 在易腐品配送系统中 库存成本和运输成本占有很大的比重 且相互间具有密切的联系 因而有必要对两者 进行集成优化研究 以便提高易腐品配送系统的整体绩效 即研究易腐品配送的库存 一路径问题 i n v e n t o r y r o u t i n gp r o b l e m i r p 为此 本文从以下两个方面对易腐品配 送系统的i r p 进行了研究 首先 考虑了由配送中心和需求点组成的两级配送系统的i r p 把i r p 分解为库存 问题和路径问题两部分分别求解 最后采用提前配送的方法 对所求解进行迭代调整 以协调库存费 订货费 订购费用与运输费之间的关系 通过配送策略和订货策略的 变换的不断迭代从而求得原问题的近似最优解 在制定库存策略时 就需求确定环境 下考虑易腐品变质率建立了总成本包括订货费用 订购费用和库存费用在内的库存模 型 为不同的需求点求得其最佳配送周期和配送量 算例结果表明 配送周期越短的 客户越有可能通过提前配送产生成本节约 而全局调整成本的节约值是依靠尽可能地 满足车辆的最大容载量来实现的 其次 针对易腐品配送中的运输问题 考虑城市路网中不同路段在不同时间段具 有不同的行车速度 因此会对车辆的行驶时间造成影响 进而导致车辆在到达各个需 求点时的到达时间也会因为跨时段而不同 因而在考虑具体每一天的配送策略时 需 考虑时变因素 在此 论文采用了考虑时变因素的跨时段处理模型以及遗传算法 解 决时间依赖条件下的v r p 关键词 易腐品 库存一路径问题 遗传算法 时间依赖 西南交通大学硕士研究生学位论文 第1 i 页 a b s t r a c t i nv i e wo ft h ec h a r a c t e r i s t i c so fp e r i s h a b l ei t e m s o p t i m i z i n gt h em a n a g e m e n to f l o g i s t i c sl i n k sl i k es t o r a g ea n dt r a n s p o r t a t i o nw o u l dr e d u c ed e t e r i o r a t i o ne f f e c t i v e l ya n d d i s t r i b u t ep e r i s h a b l ei t e m si nt i m e s ot h eo p t i m a lm a n a g e m e n th a ss i g n i f i c a n tt h e o r e t i c a l a n dp r a c t i c a lm e a n i n g i np e r i s h a b l ei t e r n sd i s t r i b u t i o ns y s t e m i n v e n t o r yc o s t s a n d t r a n s p o r t a t i o nc o s t sa c c o u n tf o ral a r g ep r o p o r t i o n a n dt h e r ei sa c l o s er e l a t i o n s h i pb e t w e e n 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 no r d e rt oi m p r o v et h e o v e r a l lp e r f o r m a n c e i ti sn e c e s s a r yt o s t u d yi n v e n t o r ya n dt r a n s p o r t a t i o n f r o mt h ep e r s p e c t i v eo fi n t e g r a t i o n t h a ti st os t u d yo n i n v e n t o r y r o u t i n gp r o b l e m i r p i np e r i s h a b l ei t e m sd i s t r i b u t i o ns y s t e m t h e n t h i sp a p e r s t u d yo ni r pi np e r i s h a b l ei t e m sd i s t r i b u t i o ns y s t e mf r o mt w oa s p e c t sa sf o l l o w s f i r s t l y t h i sp a p e rs t u d yo ni r pi na t w o l e v e ld i s t r i b u t i o ns y s t e mw h i c hi sc o m p o s e do f d i s t r i b u t i o nc e n t e r sa n dd e m a n dp o i n t s a n di r pi s d i v i d e di n t ot w os u b p r o b l e m s i n v e n t o r y c o n t r o l l i n gp r o b l e ma n dv e h i c l er o u t i n gp r o b l e m t h e naa d v a n c e dd i s t r i b u t i o n a p p r o a c h i s p r o p o s e dt oi t e r a t ea d j u s t i n g o nt h es o l u t i o n a i m e dt oc o o r d i n a t et h e r e l a t i o n s h i p sa m o n gi n v e n t o r yh o l d i n gc o s t o r d e r i n gc o s t p u r c h a s i n gc o s ta n ds h i p m e n tc o s t t h e nt h ea p p r o x i m a t eo p t i m a ls o l u t i o nc a l lb eo b t a i n e db yi t e r a t i n go nt h es o l u t i o nu n d e r d i f f e r e n td i s t r i b u t i o ns t r a t e g ya n do r d e rp o l i c y i nm a k i n gi n v e n t o r yp o l i c y c o n s i d e r i n gt h e d e t e r i o r a t i o nr a t eo fp e r i s h a b l ei t e m su n d e rd e t e r r n i n i s t i cd e m a n de n v i r o n m e n t ai n v e n t o r y m o d e li se s t a b l i s h e d i nw h i c ht h et o t a lc o s ti sc o m p o s e do fo r d e r i n gc o s t p u r c h a s i n gc o s t a n di n v e n t o r yh o l d i n gc o s t b a s e do nt h em o d e lw ec a l lg e tt h eo p t i m a ld e l i v e r yc y c l ea n d q u a n t i t yf o re a c hd e m a n dp o i n t t h ee x a m p l es h o w st h a tt h es h o r t e rd e l i v e r yc y c l e t h e c u s t o m e r sa r em o r el i k e l yt om a k ec o s ts a v i n gt h r o u g ha d v a n c e dd e l i v e r y w h i l et h ec o s t s a v i n gb yg l o b a la d j u s t m e n ti sa c h i e v e db ym e e t t i n gt h e v e h i c l e sm a x i m u ml o a dc a p a c i t ya s m u c ha sp o s s i b l e s e c o n d l y f o rt r a n s p o r t a t i o np r o b l e mi np e r i s h a b l ei t e m sd i s t r i b u t i o ns y s t e m v e h i c l e s p e e do nd i f f e r e n ts u b s e c t i o n si nu r b a nt r a n s p o r t a t i o n n e t w o r ki sv a r i e da c c o r d i n gt o d i f f e r e n tp e r i o do ft i m e w h i c hw i l la f f e c tt h et r a v e l l i n gt i m ea n dl e dt od i f f e r e n ta r r i v a lt i m e s o c o n s i d e r i n gd i s t r i b u t i o ns t r a t e g yi ne a c hd a y i ti sn e c e s s a r yt oc o n s i d e rt i m e v a r y i n g p a r a m e t e r i nt h i sp a p e r at i m e c r o s sp r o c e s s i n gm o d e li n c o r p o r a t i n gt i m e d e p e n d e n t p a r a m e t e ri sp r o p o s e da n das a t i s f y i n gs o l u t i o ni s f o u n df o rt i m ed e p e n d e n tv i 冲b yu s i n g g e n e t i ca l g o r i t h m k e yw o r d s p e r i s h a b l ei t e m s i n v e n t o r y r o u t i n gp r o b l e m g e n e t i ca l g o r i t h m t i m e d e p e n d e n t 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索 可以采用 影印 缩印或扫描等复印手段保存和汇编本学位论文 本学位论文属于 1 保密口 在 年解密后适用本授权书 2 不保删使用本授权书 请在以上方框内打 v 学位论文作者签名 多衔 日期 龇 6 7 指导老师虢写砰 日期 2 咖 哆 西南交通大学硕士学位论文主要工作 贡献 声明 本人在学位论文中所做的主要工作或贡献如下 1 研究了确定需求条件下的易腐品配送中的库存一路径问题 考虑变质率的影响 建立了相应的数学模型 并设计了一种两阶段算法求解 见第2 2 和2 3 节 2 研究了基于时间依赖的易腐品配送v r p 建立了相应的数学模型 并设计了一 种遗传算法求解 见第3 2 和3 3 节 本人郑重声明 所呈交的学位论文 是在导师指导下独立进行研究工作所得的成 果 除文中已经注明引用的内容外 本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果 对本文的研究做出贡献的个人和集体 均已在文中作了明确说明 本人完全了解违反上述声明所引起的一切法律责任将由本人承担 学位论文作者签名 岁彳垂帝 日期 洲o 斗 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景及意义 第1 章绪论 易腐品指的是随时间推移会发生腐烂 损坏 挥发或过期的产品 如奶制品 鲜 花 水果 熟食 海鲜等产品 一般易腐品具有易过时或易变质的特性 以生鲜产品 为例 生鲜产品在生产 储存 运输和消费的过程中损耗比率高达2 0 尤其在城市 的流通环节损失更为惊人 随着连锁超市 大型商场 便利商店等新型商业零售模式 的持续发展和现代都市人生活节奏的提高 使得生鲜 冷冻食品区在各卖场所占的面 积比重不断增加 众多商家把生鲜 冷冻产品作为其重要的经营项目 不断加大采购 和销售力度 从而扩大了冷藏 冷冻产品的市场容量 所以 对易腐品的存储 运输 等物流环节进行控制研究 有效地减少变质损耗 及时实现易腐品的配送 具有重要 的理论和现实意义 易腐品配送属于冷链物流的一种 b e r n a r dc o m m e r e 2 0 0 3 在研究保证食品质量的 冷链控制时 对冷链物流 c o l dc h a i n 定义为 将生鲜 易腐食品在生产 存储 运输 销售直到消费前的各个环节过程中 始终处于特定的温度环境条件下 以保证食品质 量安全 减少数量损耗 防止污染的供应链系统 l 冷链物流的特殊性体现在两个方面 一是特殊的作业环境 冷链物流的运输和作业必须是限制在适宜的低温环境下 冷藏 链中各个环节的设备 设施都必须装有冷藏设备和冷冻装置 二是对象的特殊性 冷 链物流的对象是容易腐败变质的生鲜食品 鲜活农产品或医疗药品 相比其他美 日 等国 我国还没有建立起比较完善的冷链物流配送体系 现存的冷链供应链系统的各 个步骤都存在着不规范管理的现象 所以浪费现象非常严重 进而造成冷链物流成本 的巨大损失和产品的质量的安全隐患 按照国际通用标准 食品类的物流成本最高不 能超过所有总成本的5 0 而我国生鲜易腐品在整个物流费用占到其总成本的7 0 以 上 运输过程中的低效率 高损耗现象明显 2 0 0 9 年9 月2 3 日 仲量联行发布其研究报告一 潜力无限的中国冷链物流市场 该报告指出 中国是全世界人口最多的国家之一 其食品消费近年来保持较快增长 随着城乡人均收入的增长和现代生活节奏的加快 中国人的饮食习惯正在发生变化 进而导致了具有易变质特性的速食食品消费快速上升 如动物蛋白和奶制品 还有冷 冻食品 速冻食品和鲜活农产品 与此同时 中国的消费者也越来越意识到食品安全 的重要性 中国面临亟需建立一个完善冷链物流基础设施的现状 中国的冷链市场十 分不发达1 2 j 据估计 在中国 需要温控介入的产品 有8 5 是以不正确方式进行操 作的 其结果导致大量的蔬菜水果因存储不当而损毁 而大众健康也处于潜在风险之 中 这个问题的症结可归结为以下几点 规范标准不成熟 意识不足及经验缺乏 落 西南交通大学硕士研究生学位论文第2 页 后的基础设施 服务提供商短缺 以及人力资源匮乏 易腐品具有容易腐烂 不易保鲜 较难运输等特点 决定了其在物流组织和实施 过程中与其它一般产品具有很大的区别 长期以来 我国的易腐品由于在流通过程中 缺乏有效的管理体系和制度安排 对物流的运行效率大打折扣 有数据显示 我国鲜 活农产品的物流成本达到总成本的6 0 以上 而发达国家的物流成本比重较低 一般 控制在1 0 左右 我国水果蔬菜等鲜活农产品在采摘 运输 储存等物流环节上的损 失率为2 5 3 0 而发达国家的损失率则控制在5 以下 因此 如何建立完善高效 的易腐品配送系统对提高产品质量和安全 降低易腐品流通环节的损耗 降低易腐品 的物流成本 充分发挥其经济效益具有重大的理论意义与现实意义 1 2 易腐品配送系统分析 易腐品的物流配送系统的优化是从物流系统的总体目标出发 以物流总成本最小 为目标 运用系统理论和系统工程的原理 方法 制定合适的库存控制策略 选择 规划每个需求点的配货周期和配货量 确定合理的运输路线和运输工具 以最短的运 输途径 最精确的配送时间和最少的费用 整体优化易腐品的物流作业 使得易腐品 的物流系统达到效率化 目前的易腐品配送 大都分为库存问题和路径问题的独立研 究 而实际上两者之间是相互影响 相互联系的 因此有必要对易腐品的库存和路径 问题进行集成优化研究 既能保证每个需求点的需求按时保质地运到 又要使得整体 的花费成本最优 供应商管理库存 v e n d o r m a n a g e di n v e n t o r y v m i 是在供应链管理思 想的基础上产生的一种新的库存管理模式 利用先进的数据库获取用户的库存数据 保证实时监控产品的库存水平 确定什么时间补货以及补货的数量来优化供应链的运 作绩效 从而既能获得较高的需求点满意度 有效降低需求点的缺货成本和库存成本 又能实现系统整体成本的最优 它摒弃了传统配送中需求客户与供应商之间按照发出 订单进行补货的库存模式 以整体优化的思想制定库存补货计划以适应市场变化和消 费需求 集中体现了供应链横向一体化的战略思想 使整个供应链获得同步化的运作 增强企业的市场响应能力和核心竞争能力 增强了企业之间的合作 在供应商管理库存的战术操作层面上 易腐品供应商和需求客户可以通过信息决 策系统实现共同监管控制 从整体上对下级分销商的需求进行控制 实现供应商和批 发商成本的降低 制定供货库存的相关协议 合理安排发货时间和数量 这样既满足 了下游企业的需求 降低了的库存成本水平 提高了商品的流通速度 同时也避免了 传统库存管理模式下的各级库存环节的大幅度波动引发的对供应链环节产生的牛鞭效 应 能够使生产商有效地制定生产计划 提高整个供应链上的供应速度和物流绩效 综上所述 通过对供应商管理库存机制下供应商的易腐物品库存控制问题进行分析研 究 能够为供应商的实际运营配送提供实际决策的依据 通过v m i 管理模式 不仅能 西南交通大学硕士研究生学位论文第3 页 够降低成本 增加企业的竞争能力 而且还能够解决实际配送中因下游企业的计划期 变动 需求不确定等因素带来的影响 众多的下游零售商也能从供应链的库存优化中 尽可能地实现自身库存和订货成本最小化 1 3 国内外研究现状 1 3 1 易腐品配送问题研究 对易腐品库存问题的研究最早是由t m w 1 l i 咖在1 9 5 7 年对时尚物品在库存周期末 发生过时开始进行研究的 3 之后的研究者认为易腐品库存的消耗量与时间呈负指数函 数 在此研究的基础上提出了易腐品的负指数函数库存模型 这个库存模型为后续的 易腐品库存问题研究者所引用 之后很多研究易腐品库存水平变化的学者都是以这个 公式作为参考对于易腐品库存研究模型进行研究的 r a a f a t 4 1 s k g o y a l 5 分别在1 9 9 1 年 2 0 0 1 年对易腐品的库存研究现状进行了综述 g o y a l 还研究了需求随时间变化的 易腐品库存策略 对易腐品库存问题进行研究的目的是制定相应的库存策略 研究的 决策变量主要是易腐品的补货周期 时间间隔 以及补货数量 在决策时常以成本 一 般包括订购成本 订货成本 存储成本 变质成本 缺货成本 等为标准来设置目标 函数 在易腐品库存研究中变质率是某一易腐品独有的区别于其他易腐物品的因素 是表征易腐品变质特性的重要参数 早期的研究人员如g h a r e 和s e h r a d e r s h a h 和 a i s w a l l 6 a g g a r w a l 7 1 g p a d m a l l a b h a n a f 8 a k b h u n i a 9 在开始研究易腐品库存问题时 模型中涉及到的变质率大都假定为常数 而另外的一些研究人员则考虑了变质率与库 存时间及库存数量之间的关系 其中主要有变质率为时间的线性函数 1 0 1 1 变质率为 含有两个参数 1 2 以3 和三个参数 1 4 的w e i b u l l 函数 以及需求随库存量变化且变质率为时 间的非线性函数i l5 等几种情况 在有关易腐品需求特性方面的研究 b h a b a r s a r k e r 等 16 1 c h u n t a oc h a n g 等 l7 1 k u n j e nc h u n g 等 1 8 k u o n a nh u a n g 等 l9 1 张冲等在需求与变质率己知且均为常数的 情况下研究了单一供应商向下游企业提供支付时 供应商的最优库存策略 对易腐品 随机需求进行模拟较常见的一种情况为假定其需求服从洎松 p o s s i o n 分布 2 0 1 s k a l p a k a m s s h a n t h i 2 1 2 2 i e y l e mt e 妇n 2 3 研究了需求服从泊松 p o s s i o n 分布的 易腐品基本库存策略和修正的 s 一1 s 库存研究 吕大昭 2 4 研究了易腐品需求分别服从 正态分布和极小极大自由分布的两种情况下的易腐品基本库存策略 在模型中 假定 易腐品变质率为常数 模型的目标函数设置为库存费用值最小 其他的一些研究者同 时也把通货膨胀 资金的时间价值以及价格折扣等因素加入模型 进行考虑 针对不 同的易腐品种 模型参数的侧重点也会不同 2 引 有关多品种易腐品的库存策略的研究 大部分集中于多种易腐的物体一起存放是 西南交通大学硕士研究生学位论文第4 页 否会影响相互的变质方面的研究 k a r 等研究了拥有两个分店的水果零售商的库存补 充策略 提出了在有限资源条件下的如何求解利润使之最大化的优化算法 并且指出 该算法同样也适应于其它的易腐商品 2 6 1 对于含有多种易腐商品的库存策略研究 b h a t t a c h a r y a 认为同一库存中的不同易腐商品会对彼此的需求关系和变质量会产生相 互影响 在上述研究的基础之上 b h a t t a c h a r y a 研究了单一库存中两种商品的库存竞争 模型 该模型要进行求解的问题是确定多大的连续性供给率 使得一个周期内的利润 最大 由于产品之间对于需求率和变质率具有相互影响关系 使得该模型不具备可解 性 2 7 在易腐品供应链的研究方面 p o c h u n g y a n g h u i m i n gw e e 等对一个供应商多个 买方构成的二级供应链环境下 易腐品的库存问题进行了一系列研究 总成本结构中 包括制造商成本和订货商成本 实验结果表明 相对于供应商和订货商独立作出决策 来说 这种供应链一体化的库存决策更有利于总体系统成本的降低 2 8 2 9 1 其中p o c h u n g y a n g 等构造了基于供应链一体化和的最优定价和订购问题 研究供应商按照j i t 的运 行机制向买方供货时 使得整个供应链成本最小的生产 库存问题 算例结果表明 买 方成本随着供应链成本降低而降低 他认为面临全球化的趋势 资源的紧缺 供应链 的一体化的研究应该将成为未来研究的重点 2 引 杜少甫等在考虑产品变质特性的前提 下 基于v m i 管理思想对供应商补货与发货策略进行了研究 文章构建了一个由一个 制造商 一个供应商和众多零售商构成的易腐品供应链系统 假定零售商需求随机并 服从p o i s s o n 分布 在v m i 的运作模式下 供应商要解决对众多零售商的库存补货以 及相应的装运调度问题 即求解零售商的补货订购点 订货数量和订货周期p 目前 的学者研究的供应链库存策略都是在不允许缺货的基础上进行的 今后的研究方向会 更多得侧重于延期支付 价格折扣 通货膨胀以及供应链中的利益分配机制等因素 1 3 2 库存一路径问题研究 h a r r i s 是最早提出库存与运输进行组合优化的研究者 h a r r i s 早在1 9 1 3 年就提出 对库存和运输进行系统整合研究具有重要意义 但是在后续研究中 库存和运输的整 合研究一直少有关注 原因在于整合研究的复杂性及当时供应链中库存和运输两个环 节的相对分离 后来随着全球市场竞争的加剧以及规模化运输的发展 高效率 高效 益的配送一体化战略开始凸显其重要性和必要性 实践证明 将库存和路径整合考虑 时 会减少大量的成本 国外学者研究的重点又重新转移到库存问题和运输问题的整 合方面来 到1 9 8 4 年 f e d e r g r u e n 和z i p k i n 首次在研究车辆路径问题的同一优化模型 中讨论了这两个彼此悖反的问题 他们把库存成本合并进一个车辆路径模型中 结果 比那些单独考虑考虑车辆路径问题的方案节省大约6 7 的运行成本 3 1 1 随着众多学者对1 r p 的广泛研究和关注 刘立辉 叶春明在库存一路径问题 西南交通大学硕士研究生学位论文第5 页 i n v e n t o r y r o u t i n gp r o b l e m i r p 的综述中 按i r p 的不同特性 将其分为三个类型 战略i r p 有限时间i r p 和无限时间 长期 i r p 3 2 赵达 李军在随机需求的库存一 路径问题研究现状和展望中 就i r p 按决策层次 需求类型 产品种类 路径策略 分配策略 补货策略 拓扑结构 时间特性 车辆因素等方面的不同进行了分类 3 3 1 按照i r p 的研究周期的不同 一般可以分为以下的三种情况 1 周期为一天的i r p f e d e g r u m e 和z i p k i n 所研究的是随机需求条件下将单一货物从 个供应中心配送 到多个客户需求点的i r p 问题 在参考了车辆路径方法后 集中解决了作为非线性整 数规划的近期单阶段问题1 3 1 1 g o l d e n a s s a d 和d a h l 在分析大规模车辆路径问题时 采用启发式算法解决了在 充分满足所有需求点存货需求的前提下使库存成本和路径成本最小的一类问题 3 4 1 在 问题求解时 对每一个需求点的 需求急切度 进行判断 当其急切程度小于某给定 的标准值时 对该顾客不予配送 然后根据其急迫程度与送货需求时间的综合评价来 选择给哪些需求点进行直接配送 2 周期为几天的i r p f i s h e r 等人是以某一家公司的实际情况为基础对1 r p 问题的研究 研究了计划期长 度为几天的库存一路径问题 研究所定义的目标函数为在长达几天的计划期内使供应 方获取的利润值最大化 3 5 1 需求点需求而是根据每一周期内向每个需求点配送量的上 下限 来给定需求范围 使用整数规划确定配送数量 车辆路线的起始时间以及访问 不同需求点的配送路线 在求解该整数规划时使用了拉格朗日松弛算法 d o r r b a l l 和g o l d e n 研究的主要内容是如何将计划期较长的多周期问题转化为时 间跨度较短的单周期问题 同时对短期计划决策对下一周期的影响进行了考虑 这为 解决无固定分区策略的有限时间i r p 提供了一种思路 3 6 3 7 该文献通过计算出现缺货 的概率值来计算每次配送过程中产生的运输成本和缺货损失的期望成本 运用两阶段 算法对模型进行求解 即首先确定需求点补货的日期丁 补货数量q 然后通过对 廿 问题进行求解 得到每一天内车辆配送路线 该方法的关键在于把配送时间确定为能 使补货和运输成本最小化的那一天 j j a i l l e t 3 8 等人采用了滚动周期法来解决了周期为两周的i r p 问题 即规划中虽然 以两周为周期 但是在实际求解中 只对第一周的配送进行了求解 他们采用了与上 述d o r r 等人相似的方法确定对每一需求点送货的最佳配送时间 与d o n 等人的方法的 主要区别在于 在规划中 只考虑最佳送货时间在随后两周内的需求点 3 长期 无限期 i r p 无限时间的i r p 指的是从一个供应中心向一组需求点进行补给配货 目标为在长 期的库存持有成本 订货成本 惩罚成本以及运输成本之和最优 无限期的i r p 可以 西南交通大学硕士研究生学位论文第6 页 在有限时间的基础上 进行滚动求解 不断推动 对无限期的i r p 进行近似求解 w 曲b 和l a r o s n 3 9 1 所研究的长期i r p 是基于公司实际运营的基础上进行的 公司由 于不具备足够的运输车辆 需要对需求点需求进行了解的基础上 购买或租赁配送车 辆 由于车辆有限 他们采用固定分区的方法对长期i r p 进行求解 w e b b 采用需求点 随机需求的均值将问题转化为确定需求下的i r p 问题 用启发式算法对所需的最小车 辆进行了估计 根据车辆数把需求点分成互不相交的组 然后求解每一组的配送路线 最后运用线性规划对估计值进行修正 得到了使得维持系统长期运行的最小车队数量 a n i y 和f e d e g r r u e n 研究了处于恒定且确定需求率以及不限车辆的条件下无限期库 存一路径问题研究 改研究的出发点是通过固定分区策略确定长期配送线路模式 1 0 n g t e r mr o u t i n gp a t t e r n 使长期平均库存成本和运输成本最小 为了进行分区 他 们设计了一种环状区域划分法的启发式算法 4 们 在这种算法方法中 长期配送线路模 式是通过修正的循环分组计划来确定的 即对需求点按照需求率不同而进行分组 接 下来 a n i y 还提出了长期平均成本的下限对这种长期配送模式进行了评价 g a l l e g o 和s i m c h i l e v i 的求解方法与a n i l y 和f e d e r g r u e n 相似 对直接配送方式 每 次只对一个需求点进行配送 的长期效果做出了评估 并得出结论 对于所有i r p 需 求点 当需求比较大 接近或大于一辆货车运输能力时 采用直接配送方式是合理的 4 b a r m e l 和s i m h c i l v e i 4 2 j 在上述思路的基础上作了适当调整 针对需求点库存能力 无限 不限车辆数量的确定性i r p 他们的思路是 首先将实际问题转化为集电器选址 问题 c c l p 通过求解c c l p 问题选择了一个固定分区 将需求点分成互不相交的组 然后再将其结果转化为原i r p 的结果 在此基础上 c h a n f e d e g r r u e n 和s i m c h i l e v i 进一步分析了零库存订货策略 只有在需求点的库存被消耗尽以后才对其进行补充 和固定分区策略 并通过研究 得出最坏情形 w o r s t c a s e 的下限 目前国内有些学者对i r p 也进行了上述相关方面的研究 袁庆达 2 0 0 1 在作业层 的库存一运输联合优化 s i t i o 的问题研究中 就战略层次和战术层次分别对随机需求 下的库存运输问题进行了联合优化研究 在解决战术层问题时 基于客户分组的方法 借鉴了通讯领域的约束集中器选址问题 设计了求解模型的启发式算法 4 3 1 高梦昭 张文杰 2 0 0 3 在研究物流成本探析时 就运输成本与库存成本之间的关系进行分析研 究 证明了两者之间存在着线性强相关关系m 赵达 李军 4 5 对于库存一路径问题的 研究现状进行综述和展望 给出了i r p 的定义 分析了i r p 的特征以及与常见的车辆 路径问题 旅行商问题的联系与区别 并将库存一路径问题按照不同的特性进行了分 类 总结了近年来有关于求解随机需求库存一路径问题所建立的模型及算法求解 梁蔚 2 0 0 2 年 一6 j 主要从零售商和生产商的角度对对i r p 进行研究 作者主要采用 随机需求确定化的研究方法 构造以系统总成本最小为目标函数的优化模型 采用两 阶段算法 通过迭代 解决了库存与运输系统的集成优化问题 西南交通大学硕士研究生学位论文第7 页 赵达 47 对于r s y s t e m 物流系统下的o n e m a n y 的基于马尔可夫决策过程无限期折 扣模型库存 存路径问题 d y n a m i ci n v e n t o r yr o u t i n gp r o b l e m d m 2 进行了研究 提出 了一种两阶段算法求解这一问题 即将原问题分成库存问题和路径问题进行求解 于 涛 4 引 着重分析了基于供应商管理库存下的库存管理 运输联合优化与传统意义上的 区别 建立的库存与运输联合优化模型以系统总费用最小为目标函数值 并采用了迭 代算法和遗传算法对简历的模型进行了求解 王莺 4 9 基于d r s y s t e m 的存贮路径问题 进行了研究 首先 把i r p 分解为配送中心的订货策略问题和需求点的配送策略问题 然后分析当需求点配送策略 包括车辆路线和需求点配送量 变化时对配送中心订货策 略 运输费用 库存费用和订货费用的变化 的影响 即再将配送中心和需求点整合后的 决策与单独决策 初始解解 进行比较 算例验证表明总费用的节约是靠最大限度地实现 车辆的满载来实现的 综上所述 目前已有一些学者对i r p 进行了研究 但仍然存在着一些问题有待进 一步探讨 如随机需求环境下考虑时间窗限制的i r p 多品种配送i r p 考虑不同时段 道路交通状况的时变i r p 等 而这些都是城市易腐品配送i r p 要考虑的问题 1 3 3 动态车辆路径问题研究 对于传统的车辆路径问题 v e h i c l er o u t i n gp r o b l e m v r p 的研究 文献 5 0 进行了 详细的总结 本文不再赘述 与此同时 国内外许多专家学者对动态车辆路径问题与 时间依赖车辆路径问题进行了丰富的研究 取得了丰硕的成果 动态车辆路径问题 d y n a m i cv e h i c l er o u t i n gp r o b l e m d v r p 指的是由于道路网络 性能的不确定性引起的v r p 目前对动态网络v r p 研究主要集中在时间依赖车辆路径 问题 t i m e d e p e n d e n tv e h i c l er o u t i n gp r o b l e m t d v r p 的研究方面 t d v r p 指的是车 辆在路网的行驶时间依赖于车辆的出发时间和其行驶过程中行车速度随行驶时间的变 化程度 从2 0 世纪9 0 年代开始 已有学者对t d v r p 的模型和算法进行研究 目前的 研究一般分为 只考虑网络时间依赖性的t d v r p 有时间窗约束的t d v r p 动态随 机需求且有时间窗约束的t d v r p 三种类型 目前研究者在解决t d v r p 问题时采用的 算法主要是禁忌搜索算法 贪婪算法 蚂蚁算法和遗传算法等亚启发式算法 在时间 依赖性质运行时间的计算方法上 用连续的速度 时间函数来求得行驶时间比较接近实 际 但是涉及分布函数以及积分计算比较复杂 所以现有的研究大多都是用分段的行 驶速度 时间函数或行驶时间 时间函数来计算求得行程时间 5 1 1 h i l l a v 和b e n t o n 1 9 9 2 提出了p a r s i m o n i o u s 模型用来估计具有时间依赖性质的两 点之间的行驶速度 并通过算例对模型的有效性进行了验证 5 2 1 m a l a n d r a k i 等 1 9 9 2 建立了静态需求不带时间窗的t d v r p 的混合整数规划模型 在模型中 采用了阶段函 数表示时间的依赖特性 在研究中他把一天分为几个时间段 在每个时间段内的行驶 西南交通大学硕士研究生学位论文第8 页 时间是恒定的 但是其跨时段的处理方法没有考虑行驶时间随时间的连续变化 会出 现先出发而后到的现象 不满足先进先出的原则 f i f o 5 3 1 在算法方面 他们采用贪 婪算法解决t d v r p 和t d t s p m a l a n d r a k i 等 19 9 6 在后续的研究中 采用动态规划结 合贪婪算法的动态规划启发式算法用来解决t d t s p 但可以解决的结点数最多只有5 5 个 5 4 j w i e l 和s a h i n i d i s 对l k 启发式算法进行扩展 并将其应用于t d t s p 问题 算 例结果表明 l 广k 启发式算法能解决1 0 0 个节点的问题 而且算法运行的时间也较短 5 5 1 y a n g b y u n g 2 0 0 0 同样针对路径成本与需求点满意度两个目标建立了混合整数规划模 型 在c w 节约式算法基础上 提出了适合该模型的b c b i c r i t e r i a s a v i n ga l g o r i t h m 节约式算法 取得了一定的效果 5 6 1 2 0 0 3 年 d o n a t i 等人发表了关于应用蚂蚁算法解决目标函数为派车成本与行驶成 本t d v r p 的研究 57 5 9 为了解决具有服务时间的时间窗t d v r p 他们通过将具有时 间依赖型的动态信息素取代静态信息素的方法 以适应t d v r p 时间依赖特性的需要 j u n gs 6 0 2 0 0 0 在其博士论文中采用了随机数表示法 克服了一般序数表示法存在的 缺点 他在每个时段某一时刻保留原有路线已行驶部分同时以当时位置作为起点重新 安排路线 以适应随机需求的情况 进入2 1 世纪 随着t d v r p 的深入研究 一些有关时间依赖函数的准则也被众多 学者重视和采用 s o u m i a 等 2 0 0 3 首先提出了先进先出 f i r s t i n f i r s t o u t 准则 即车辆 在同一条路径上行驶从一点出发到相同的下一点 先出发的车辆比后出发的车辆应该 先到达 该准则比较符合现实情况 一直被后来的研究者所引用 作为评价建立的时 间依赖函数模型是否合理的一个标准 6 1 1 s o u m i a 等用行驶速度 时间的分段函数表示时 间依赖 再由速度和两点之间距离计算求得行驶时间 求得的行驶时间是随车辆出发 时间的连续函数 s o u m i a 建立了基于三时段函数下带时间窗的t d v r p 模型 采用改 进并行禁忌搜索算法进行求解 算例结果表明 时间依赖程度越高 时间依赖策略比 静态策略的平均节约成本越多 b y o n g h u n g 1 9 9 1 首次将t d v r p 与时间窗相结合 将时变函数设置为单调函数 以保证了节约 插入和弧交换等传统启发式算法的合理应用 但是这种单调函数的假 设与实际不太符合 6 2 在国内的时间依赖的研究方面 郑成武 6 3 考虑时变网络中的多目标带时间窗的车 辆调度问题 车辆在各路段的行驶速度随时间的变化而变化 建立的速度 时间函数模 型符合f i f o 原则 采用并行遗传算法对所建模型进行求解 并且与b c 节约算法进行 了比较 结果表明遗传算法比b c 节约算法在求解此类问题上显得更加优越 国内学 者王正国 刘振元等提出了采用适应性禁忌搜索算法求解带回程的带时间窗的时变速 度车辆路径问题 对双目标的问题的处理是通过转化为单目标问题进行处理 6 4 彤 李妍峰对基于时段的时间依赖型旅行商问题 t i m e d e p e n d e n tt r a v e l i n gs a l e s m a n 西南交通大学硕士研究生学位论文第9 页 p r o b l e m t d t s p 和时间依赖型车辆调度问题 t i m e d e p e n d e n tv e h i e l er o u t i n gp r o b l e m t d v r p 提出一种时变网络跨时段处理方法 计算车辆在任意跨时段 单时段 多时段 所对应路段的行驶时间 推导出的公式中不含路段距离和车辆的行驶速度 时间运行 函数只与出发时间 所跨时间分界点 不同时段的行驶时间这三个参数有关 推导出 的公式满足先入先出的准则 在传统近邻算法的基础上 一共给出了5 种改进邻域的 策略 分别通过实验比较了不同算法的性能 对算法的性能进行了分析 6 6 j 关于时间依赖且依概率变化网络下的v r p 张岩 贺国光 67 j 在动态车辆调度问题 的建模与算法的研究中给出了求解该问题的多目标随机机会约束规划模型 关于时间 依赖且依概率变化网络下的 冲问题 肖增敏f 6 8 在其硕士论文中对该类型的车辆配送 问题分为静态需求和动态需求两种情况建模 尝试用免疫遗传算法进行求解 1 4 本文的研究内容 1 易腐品配送系统中i r p 的特性分析 根据易腐品配送系统的特殊性和实际要求 分析易腐品物流配送系统中的i r p 在 问题属性 优化目标 约束条件和库存策略等方面区别于一般物流系统中i r p 的特性 2 模型研究 基于上述分析结果 根据实际应用背景 综合运用运筹学 优化算法等理论方法 建立确定需求环境下易腐品物流配送系统的库存控制和车辆路径安排集成优化模型 在此基础上进一步考虑时间窗限制 以及不同时段道路交通状况的时变要素 建立相 应的优化模型 3 算法研究 由于易腐品物流配送系统的集成优化模型结合了多种n p h a r d 问题 求解比较困 难 本文研制两阶段算法求解本文建立的模型 构造算例验证模型和算法的可行性及 有效性 西南交通大学硕士研究生学位论文第1 0 页 第2 章易腐品配送的库存一路径问题研究 本章主要研究供应商管理库存下的单品种易腐品库存一路径问题 它是基于需求 点需求量确定 单个配送中心和若干个需求点组成的物流配送系统 2 1 问题的提出 在易腐品配送系统中 在整个决策期开始之前 决策者首先需要确定配送中心和 需求点的易腐品库存策略 即规划每个需求点的配货周期和配货量以及配送中心向上 级供应商的订货周期和订货量 并且在每一周期中对需求点的运输路径做出合理决策 以确保易腐品需求点的需求能按时保质地运达 具体描述如图2 1 所示 供应商 口配送中心 0 客户需求点 叫卜周期1 配送路线 一 卜周期2 配送路线 图2 1易腐品库存一路径问题示意图 在图2 1 中 椭圆形代表的是供应商 其地理位置已知 它主要负责满足配送中 心的易腐品需