（载运工具运用工程专业论文）基于jit供应的集货车辆路线问题研究.pdf

摘要 随着生产和物流技术的发展，j i t ( j u s ti nt i m e ) 理论已逐步得到了广泛的应用。采 用j r r 供货管理模式能够大大降低存货水平，最大限度地减少库存成本，但是，由于库 存与运输存在着二律背反关系，减少库存的同时会导致运输成本的增加。因此，高效率、 低成本的运输是j 1 1 r 供货成功实施的保障。基于j 1 1 r 供应的车辆路线问题，提高了对中 心站点的库存约束，服务时间的要求更为严格，其优化目标除考虑运输成本之外还应考 虑到库存成本。对于实现运输线路合理化、保证j 1 1 r 供货的运输服务质量、降低物流成 本，都有重要意义。 本文对基于j r r 供应的集货车辆路线问题进行了研究。考虑到实施j i t 供应的工 厂处只能有较低的库存，首先，采用以固定频次运行的路线来服务客户的方案，每个客 户只能被一条路线访问，但每条路线具有最优化的集货频次( 路线被重复的次数) 执行 多次集货。本文主要对这种情况下的车辆路线问题，即循环取货( m i l kr u n ，m r ) 的车 辆路线问题的优化进行了研究，建立了数学模型，设计了解决m r 模型的禁忌搜索算法 ( t a b us e a r c h ) 。该算法采用节约法的思想来构造初始解，用o r - o p t 交换以及 a i n t e r c h a n g e 进行邻域操作以实现路线的改进。为便于实际求解，用c 语言进行编程 实现了上述禁忌搜索算法，同时用实例进行了验证，论证了算法的可行性及有效性。其 次，本文还研究一种用不同于m r 的路线方案求解基于j r r 供应的集货车辆路线问题， 其主要思想是允许多条路线交叉访问多个节点，而每个节点都有它自己的集货频次，即 一般频次路线( g e n e r a lf r e q u e n c yr o u t i n g ，g f r ) 方案，建立了该方案的数学模型，并 对上述两种方案进行比较，总结了各自的优缺点，为今后深入研究基于j 1 1 r 供应的集货 车辆路线问题提供了参考。 关键词：j r r ，车辆路线问题，供应，集货，时间窗，禁忌搜索 a b s t r a c t w i t ht h et e c h n i q u ed e v e l o p m e n to fp r o d u c ea n dl o g i s t i c s ，t h et h e o r yo fj u s ti nt i m e ( j i t ) h a sa p p l i e d u n i v e r s a l l y t h ei m p l e m e n t a t i o n o fj i tm a n a g e m e n tm o d e mc a nr e d u c e i n v e n t o r yl e v e la n dc o s tf u r t h e s t b e c a u s et h er e l a t i o n s h i po fi n v e n t o r yc o s ta n dt r a n s p o r tc o s t a r ea n t i n o m y , i tw i l lr e s u l ti nm o r et r a n s p o r tc o s tw h i l er e d u c ei n v e n t o r ya m o u n t s o ，t h e t r a n s p o r t a t i o no fg r e a te f f i c i e n c ya n dl o wc o s ta r et h ee n s u r e n c e st oi m p l e m e n tj i ts u p p l y s u c c e s s f u l l y t h ev e h i c l er o u t i n gp r o b l e m ( v r p ) w h i c hb a s e do nj i ts u p p l y , i n c r e a s et h e r e s t r a i n to fi n v e n t r o ya tm a n u f a c t u r e r , a n dp r e s e n tam o r es t r i c tr e q u i r e m e n to ft i m ew i n d o w s b e s i d e st h et r a n s p o r tc o s t ，t h eo p t i m u mo b j e c ta l s oi n c l u d e st h ei n v e n t o r yc o s t i te x e r t sa n i m p o r t a n ts i g n i f i c a n c eo nt h er a t i o n a l i z a t i o no fv e h i c l er o u t e ，e n s u r i n gt h eq u a l i t yo ft r a n s p o r t s e r v i c eo fj i ts u p p l y , a n dr e d u c i n gt h el o g i s t i c sc o s t t h i sp a p e rs t u d i e dt h et h ep i c k u pv e h i c l er o u t i n gp r o b l e m ( v r p ) w h i c hb a s e do nj i t s u p p l y c o n s i d e r e dt h er e s t r a i n to fl o w e ri n v e n t o r ya tm a n u f a c t u r e r , t h i sp a p e rd e s i g n e dt h e p l a nt h a te a c hp a r ts o u r c ew a sb e i n gs e r v e db yas i n g l er o u t er u na taf i x e df r e q u e n c y , b u t s u c hr o u t e sh a da no p t i m i z e dp i c k u pf r e q u e n c yt h a tp e r f o r m sm u l t i p l ep i c k u p s t h i sp a p e r m a i n l ys t u d i e dt h eo p t i m i z a t i o no fv e h i c l er o u t e su n d e rt h i ss i t u a t i o n ，v i z m i l kr u n ( m r ) p r o b l e m a f t e rt h a t ，t h i sp a p e rs e tu pt h em a t h e m a t i c a lf o r m u l a t i o no fm r ，d e s i g n e dt a b u s e a r c ha l g o r i t h mt os o l v et h i sf o r m u l a t i o n h a v i n ga d o p t i o ns a v i n g sh e u r i s t i c sa p p r o a c ht o g e n e r a t et h ei n i t i a ls o l u t i o nf o rt h et a b us e a r c h ，u s i n go r - o p ta n da - i n t e r c h a n g et o r e a c h n e i g h b o u r h o o do p e r a t i o n ，i no r d e rt oi m p r o v et h er o u t e s t h et a b us e a r c ha l g o r i t h mw a s i m p l e n t m e n t e dw i t hcc o m p i l e ro nc o m p u t e r , a n da p p l i e dt h et e c h n i q u e st oar e a lp r o b l e m ， p r o v e dt h ef e a s i b i l i t ya n dv a l i d i t yo ft h i sa l g o r i t h m a n de l s e ，t h i sp a p e ru s e dad i f f e r e n tp l a n f r o mm rt os o l v et h ep r o b l e mo fv r pw h i c hb a s e do nj i ts u p p l y t h em a i nc o n c e p to ft h i s p l a nw a st h a tp e r m i tm u l t i p l er o u t e sv i s i ts e v e r a ln o d e s ，a n dt h o s er o u t e sm a yc r i s s c r o s si n t i m ew i n d o wo fas a m es u p p l i e r i nt h i sp l a n ，e a c hn o d eh a di t so w nf r e q u e n c y , v i z g e n e r a l f r e q u e n c yr o u t i n g ( g f r ) a n dc o m p a r e dt h et w op l a n s ，s u m m e du pe a c hc h a r a c t e r i s t i c s ， p r o v i d e dr e f e r e n c ef o rl u c u b r a t i n go nv r pb a s e do nj i ts u p p l yi nt h ef u t u r e k e y w o r d s ：j u s ti nt i m e ；v e h i c l er o u t i n gp r o b l e m ；s u p p l y ；p i c k u p ；t i m ew i n d o w s ；t a b us e a r c h 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名： 否暂 一 珈) 年5 月枷日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：零鹊 导师签名：哮r 氧f ，。 a 弦) 年5 月如日 沙哆年厂月岁夕日 长安大学硕士学位论文 第一章绪论 1 1 研究背景 按照国际物流术语的定义，物流是指物品从供应地向接收地的实体流动过程。 在物的流动过程中，根据实际需要，它包括运输、储存、装卸搬运、包装、流通加工、 配送、信息处理等功能要素。 作为一种实践活动，自从有了商品的交换，物流活动就存在了，它是与人类的生产、 生活活动紧密联系在一起的。从这个意义上讲，物流本身并不是一种新的活动或新的现 象。2 0 世纪5 0 年代前后，人们才将物流作为一种经济活动，从理论的高度加以分析和 研究，尤其是将物流作为企业经营管理的基本职能之一，并对物流活动实施系统化的科 学管n t l l 。 物流发展到今天，激烈的竞争要求企业必须降低成本以求生存，因而，物流作为企 业的“第三利润源泉 日益受到社会的重视。 国际社会一般以物流成本占g d p 的比重来衡量一个国家的物流发展水平，比重越 低越先进。1 9 9 1 - - 2 0 0 3 年物流成本占g d p 的比重，美国从1 0 6 降到8 5 2 ，期间平 均值为9 7 9 ；中国从2 4 下降到2 1 4 ，期间平均值为2 1 6 2 ，2 0 0 4 年继续保持在 2 1 3 的水平，平均值比美国多十几个百分点【2 1 。2 0 0 5 年，我国物流费用占g d p 的比率 为1 8 5 1 2 1 ，物流费用占g d p 的比率虽有所下降，但同比发达国家物流水平，仍明显滞 后。这反映出我国物流运作水平是极为粗放的，社会化、专业化水平低，经济增长付出 的物流成本太高。根据中国物流信息中心的核算，中国物流成本每降低1 个百分点，就 可以新增1 3 0 0 亿元的社会经济效益。因此，降低企业巨额物流成本，挖掘“第三利润 源泉对我国企业有着重要的意义。 物流诸内容中，运输与仓储是最重要的两个环节。有数据说明，从物流成本构成上 看，运输、库存、管理成本平均达到5 2 6 、3 1 8 和1 5 6 1 3 l 。由此可见，运输成本和 库存成本是影响物流成本的重要因索。 企业物流管理者通过学习、实践和总结，一直在探索降低物流成本的途径。目前， 日本丰田公司提出的准时化( j u s ti nt i m e ，j i t ) 理论已逐步得到普遍的应用。j i t 以订 单驱动，通过看板，采用拉动方式把供、产、销紧密地衔接起来，使物资储备，库存成 本和在制品大为减少，提高了生产效率。在过去的1 0 一2 0 年中，随着交通和通讯技术 第一章绪论 的发展，市场竞争已经跨越国境且有愈演愈烈之势，那些传统的大批量生产、高生产准 备成本的制造公司，迫于强大的市场竞争压力不得不放弃对原材料、零部件的经济订货 批量模型，转而采用j l t 系统来管理存货。事实证明，j 1 1 r 存货管理模式的成功实施能 够改进产品质量，提高生产力，缩短生产周期，大大降低存货水平，缩短设备调整时间， 降低生产成本，提高生产率。因而，j i t 管理技术和管理理念已被诸如沃尔玛、英特尔 公司、通用汽车公司、福特、摩托罗拉、惠普等国际知名大公司所采用，力求使物流系 统维持在最低的库存水平，甚至库存为零，以求达到降低库存成本的目的。9 0 年代，国 内一些企业亦开始应用j r r ，例如第一汽车制造厂、第二汽车制造厂、上海大众汽车有 限公司等企业。 另外，市场订单的多元化和对供货时间的及时性需求对企业物流提出更高的要求， 原来的物流模式已经无法满足订单拉动式生产的需求，企业必须更改原有的物料供货模 式，才能不被市场淘汰，于是为满足新的准时化生产方式的需求，j 1 1 r 物流就应运而生 了。 1 2 研究的意义及目的 由于库存与运输存在着利益背反关系，实施j i t 供货减少库存的同时很可能导致了 运输成本的增加。物流管理的目的是，在总成本最低的条件下，满足既定客户服务水平。 所以，在这种情况下，就对运输成本和运输服务的时间性提出了很高的要求。实施j r r 供应，最重要的是取决于物流水平。只有当生产企业需要什么样的原材料、零部件；什 么时间需要就能什么时间供应，需要多少就能供应多少时，企业才能真正实现库存为零。 因此采用j i t 管理体系，需要运输服务保证既不滞后，也不提前，按质按量地把所需要 的物品运到所要求的地方。这一方法在制造业和商业邻域的广泛应用，无疑对运输服务 提出了更高、更苛刻的要求。 车辆路线优化，是为车辆安排合理的运输路线。可以有效的减少车辆的空驶率，实 现合理线路运输，对加快运输速度、提高服务质量、降低运输成本及增加经济利益都有 较大影响，并能达到物流的科学化管理。但是，一般的车辆路线问题对库存没有限制， 使得配送到工厂的量较大，造成不必要的库存浪费，在优化目标中只考虑了运输成本进 行车辆路线的优化。基于j i t 供应的车辆路线选择，增加了对工厂的库存约束，并对服 务时间提出了更严格的要求，优化目标除考虑运输成本之外还考虑到了库存成本，从系 统的角度对实施j i t 供应的车辆路线进行优化。所以，研究基于j i t 供应的车辆路线选 2 长安大学硕士学位论文 择问题，具有很大的现实意义，是实现库存成本与运输成本联合优化的最好方法之一， 对降低物流系统的成本具有重要作用。 本研究的目的是设计出优化的车辆路线，即能保证j r r 供货的顺利实施，又能使物 流成本最小化。 1 3 国内外研究现状 1 3 1 国内外v r p 、v r p t w 的研究现状 车辆路线问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是g d a n t z i n g 和j r a m s e r l 4 1 于1 9 5 9 年提出的运筹学邻域中一大类重要问题，是实现效率化配送的重要支撑技术【5 】o 在经典 v r p 的基础上，车辆路线问题在学术研究和实际应用上，随着约束条件的不同，产生了 许多不同的延伸和变化型态。v r p 演化出的模型有，如非对称v r p ( a v r p ) ，带时间窗 的v r p ( v r f l w ) 及多配送中心的v r p ( m d v r p ) 等等。带时间窗的车辆路线问题 ( v r p t w ) 是在v r p 问题上加上了客户要求访问的时间窗口约束1 5 1 。而本文基于j 1 1 r 供应的车辆路线选择，又是在v r p t w 的基础上衍生而来，在基本v r p t w 中加入库存 约束。v r p 问题是一个典型的有约束的组合优化问题，也是离散优化的重要内容之一， 对其计算复杂性的研究表明几乎所有类型的v r p 均为n p ( 非确定型的多项式算法) 难 题1 6 1 。 国外，许多学者针对v r p 、v r p t w 问题已进行了大量深入的研究。例如，1 9 8 3 年b o d i n 和g o l d e n 在他们的文章中列举了7 0 0 余篇文章；c h r i t o f i d e s 、g o l d e n 、a s s a d 在编辑的论文集中进行了详尽的阐述等【6 1 。国外针对v r p 的求解算法有：1 9 6 2 年， b a l i n s k i 等人首先提出的v r p 的集分割；1 9 7 1 年，e i l o n 等人提出将动态规划法用于固 定车辆数的v r p ；1 9 7 4 年，w r e n ，g i l l e t 等人提出s w e e p 算法( 扫描法) ；1 9 8 1 年， c h r i s o f i d e s 等人提出了k 度中心树和相关算法；1 9 9 1 年，g e n d r e a u 等人将禁忌搜索方法 应用于v r p ；1 9 9 6 年，j l a w r e n c e 将遗传算法用于v r p 的研究等。针对v r p t w 的研 究有：1 9 6 4 年c l a r k 和w r i g h t 提出成本节约法；1 9 6 8 年，r a o 等人在b a l i n s k i v r p 集分 割的基础上引入了列生成方法进行求解；1 9 8 1 年，f i s h e r 等人针对带能力约束、时间窗 以及无停留时间的v r p ，提出了三下标车辆流方程，并基于b e n d e r s 的分解方法，提出 了一种启发式算法；1 9 9 1 年t h a n g i a h 和1 9 9 3 年j o e 分别用遗传算法求解v r p t w ，等 竺【7 】 可o 在国内，亦有很多专家都对于v r p 、v r p t w 进行了广泛的研究。例如，李大卫等 3 第一章绪论 1 8 1 ( 1 9 9 8 ) 提出了一个求解v r p t w 的启发式算法；姜大立等( 1 9 9 9 ) 1 9 】建立了v r p 的 遗传算法；谢秉磊、李军等【1 0 l ( 2 0 0 0 ) 设计了满载v r p t w 问题的遗传算法；张丽萍等 1 1 l 】( 2 0 0 2 ) 应用改进的遗传算法来求解v r p t w 问题；郎茂祥、胡思继【1 2 】( 2 0 0 4 ) 研究 了求解v r p 问题的禁忌搜索算法；许国平、叶效锋等【1 3 1 ( 2 0 0 4 ) 将基于模拟退火和遗 传算法的混合算法应用于求解v r p 问题中来，等等。 1 3 2 国内外基于j r r 供应的v r p 研究现状 j r r 思想自2 0 世纪6 0 年代由日本丰田公司提出，在7 0 年代以后才开始被应用于日 本的汽车及电子工业1 1 引。由此可知，j r r 的发展时间较短，基于j i t 的研究尚处在发展 阶段，还不成熟。国外基于j i t 供应的循环取货( m r ) 的研究及应用较为广泛，但由 于发展时间短，也尚不成熟。对该问题的其他运输模式的研究也是非常少。其主要研究 包括美国肯塔基州大学的c h u a h ，i c h ( 2 0 0 0 ) ，在其硕士论文中对j i t 配送系统的车辆 路线问题进行介绍f 1 5 1 ；c h u a h ，k h ( 2 0 0 5 ) 在其博士毕业论文中，对此问题进行了详细 论述，建立了基于j l t 供应的集送货一体化车辆路线的多种数学模型，并应用蚁群( a n t c o l o n y ) 算法进行求解【1 6 l 。其后，c h u a hk h 和j c y i n g l i n g ( 2 0 0 5 ) ，就该问题应用了 列生成( c o l u m ng e n e r a t i o n ) 再次求解【1 7 1 。 国内针对基于j i t 供应的车辆路线问题的研究也非常少。而针对此问题的循环取货 ( m r ) 的运输模式虽然在国外已得到较为广泛的共识，但在国内还属于较为新颖的命 题，理论上的研究非常少。主要研究包括：徐秋华【1 8 l ( 2 0 0 2 ) 介绍了循环取货( m r ) 方式在上海通用汽车有限公司的规划及实施；张蕾【1 9 】( 2 0 0 5 ) 在其硕士论文中，论述了 循环取货对实施j i t 供应的重要作用，但这些研究并没有给出循环取货的车辆路线设计。 这说明，国内对于基于j r r 供应的车辆路线选择的理论研究尚处于初始阶段，成功应用 的案例就更少了。 1 4 本文主要研究内容及框架 1 4 1 主要研究内容 按照配送任务的特征，v r p 问题可分为( 1 ) 仅考虑站点到客户的送货，为送货问 题；( 2 ) 仅考虑站点到各个客户点收取货物运送回站点，为集货问题；( 3 ) 在考虑将客 户需求的货物送到各个客户点的同时，考虑将客户供应的货物从客户点处取回站点的问 题，为集货送货一体化问题。其中，( 1 ) 和( 2 ) 的问题实质是一样的，只有单纯的取 货或送货业务。可一般描述为：一站点，有k 辆容量为q 的车辆，现有，个客户点有货 4 长安大学硕上学位论文 物运输任务需要完成，每个客户点都有一项送货( 取货) 任务，以1 ，2 ，z 表示， 已知客户点i 的货运需求量为皿，求满足货运需求且成本最小的车辆运输路线。 本文主要研究第( 2 ) 类情况下的车辆路线问题，即：基于j r r 供应的集货车辆路 线问题。它是v r p t w 的一个延伸，在基础的v r p t w 问题之上，考虑到了j n 供应 方式小批量、多频次、低存货的限制条件，以及时间窗的严格限制。本文以运输成本与 库存成本联合优化为目的，以多个供应商对单个制造商的服务模式为基础，以从制造商 处出发的集货为配送形式，建立了解决该问题的两种数学模型，给出了其中一种模型的 禁忌搜索算法( t a b us e a r c h ) ，并通过实例验证该算法的可行性。 1 4 2 论文框架 本文共分为五章。 第一章为绪论。分析了我国物流水平，指出影响物流成本的重要因素是运输与库存。 指出，国内外大型制造企业为达到降低物流成本的目的，很多采用了j r r 理论技术，由此 引出基于j 1 1 r 供应的车辆路线选择的重要性。其后，简述了国内外针对v r p 、v r p t w 以 及基于j 1 t 供应的v r p 的研究现状，呈现出目前对这一问题还缺乏大量深入的理论研究， 进一步阐述了研究本课题的意义所在。 第二章为基于j l t 供应的集货车辆路线问题的理论基础。在这一章中首先介绍了与本 课题相关的概念，讨论了j r r 的概念、理论及核心思想，j i t 供应的概念、基本原理，配 送中的集货、送货等重要概念。另外，介绍了v r p 、v r p t w 的研究内容以及问题的描述， 按照各类约束条件的不同对v r p 的分类进行介绍。最后，总结了已经普遍采用的v r p 问 题的求解算法，包括各类启发式算法( 如节约法、最近邻域法、插入法、扫描法等) 和现 代优化算法( 如禁忌搜索算法、模拟退火算法、遗传算法等) ，并总结出各种算法的优缺 点。为本课题的研究奠定了理论基础。 第三章为基于j i t 供应的循环取货的车辆路线问题研究。考虑到j i t 供应要求制造 厂只能有较低的库存，采用一种以固定频次运行的路线来服务客户的方案，每个客户只能 被一条路线访问，但是这样的一条路线有最优化的集货频次( 路线被重复的次数) 执行多 次集货；对这种情况下的车辆路线进行安排来获得最优化目标的问题，就是循环取货( m i l k r u n ，m r ) 路线问题。并建立了该方案的数学模型，设计了解决m r 模型的禁忌搜索算法 ( t a b us e a r c h ) 。用c 语言进行编程实现了上述禁忌搜索算法，并给出实例进行验证，论 证了算法的可行性及有效性。 5 第一章绪论 第四章为基于j r r 供应的一般频次的车辆路线问题。介绍了一种不同于m r 的路线方 案求解基于j i t 供应的车辆路线问题的方法，该方案的主要思想是允许多条路线交叉访问 多个节点，称这种路线问题为一般频次路线问题( g e n e r a lf r e q u e n c yr o u t i n g ，g f r ) 。并 建立了g r p 的数学模型，分析了与m r 的不同之处，指出这两种模型各自的优缺点。 第五章为结论。总结了本课题的主要工作及研究结果，并指出论文中的不足与有待进 一步改善的问题。 6 长安大学硕士学位论文 第二章基于j i t 供应的集货车辆路线问题研究的理论基础 2 1 基本理论 2 1 1 配送 2 0 0 1 年4 月，中国国家标准物流术语将配送定义为：“在经济合理区域范围内， 根据用户要求，对物品进行拣选、加工、包装、分割组配等作业，并按时送达指定地点 的物流活动。 【刎 配送是物流中一种特殊的、综合的活动形式，是商流与物流紧密结合，包含了商流 活动和物流活动，也包含了物流中若干功能要素的一种形式。 从物流角度看，配送几乎包括了所有的物流功能要素，是物流的一个缩影或在某小 范围中物流全部活动的体现。一般的配送集装卸、包装、保管、运输于一身，通过这一 系列活动完成将货物送达的目的；特殊的配送则还要以加工活动为支撑，所以包括的方 面更广。但是，配送的主体活动与一般物流却有不同，一般物流是运输及保管，而配送 则是运输及分拣配货，分拣配货是配送的独特要求，也是配送中有特点的活动，以送货 为目的的运输则是最后实现配送的主要手段。 从经济学资源配置的角度，配送是以现代送货形式实现资源最终配置的经济活动。 第一，配送是资源配置的一部分，因而是经济体制的一种形式。第二，配送的资源配置 作用是“最终配置 ，因而是接近顾客的配置。接近顾客是经营战略至关重要的内容。 美国兰德公司对幸福杂志所列的5 0 0 家大公司的一项调查表明“经营战略和接近顾 客至关重要，证明了这种配置方式的重要性。第三，配送的主要经济活动是送货，这 里强调现代送货，表述了与旧式送货的区别，其区别以“现代”两字概括，即以现代生产 力、劳动手段为支撑的，依靠科技进步的，实现“配”和“送”有机结合的一种方式。第四， 配送在社会再生产过程中的位置是处于接近用户的那一段流通邻域，是一种重要的方 式，有其战略价值。 配送实际是一个物品集散过程，这一过程包括集中、分类和散发三个步骤。这三个 步骤由一系列配送作业环节组成，通过这些环节的运作，使配送的功能得以实现。通常 将这些作业环节称为功能要素。 配送的基本功能要素包括集货、分拣、配载、送货等。 集货和送货的主体活动都包括运输，只是在方向上相反。本文中，集货( p i c k u p ) 7 第二章基于j i t 供应的集货车辆路线问题研究的理论基础 是指车辆由站场出发，到各个客户点处收集货物并运送回站场，是把供应商处的零件集 中到工厂处的过程，即指运输终点为生产企业的物资流，属于供应链上的采购物流。采 购物流是指将采购的原材料、零部件由供应商处运入厂内，采购是企业物流的起始点， 采购物流的科学管理对于企业生产、运作的科学系统管理有着极其重要的作用。企业生 产部门对采购物品的要求不仅仅局限于数量方面，还有质量、性能与时间等方面的要求。 时间要求是指当生产需要某些物资时能够及时得到供应。采购部门为了满足这个需求， 往往会采取大批量采购的办法来应付，这样又造成了过高的库存水平和较高的资金占 用。现代物流管理要求做到准时化采购，即j i t 采购，基本原理是按照生产部门或客户 的需求数量和时间，及时安排采购计划，对于采购数量与采购时间，尽量做到既不要过 量又不要提前，能够准确及时地满足需要，最大限度地降低采购物资的库存水平。在满 足一定的约束条件下，按什么路线行驶可使总费用最少即为集货车辆路线优化问题。 配送是在集货、配货基础上，完全按用户要求，包括种类、品种搭配、数量、时间 等方面的要求所进行的运送。其一般流程如图2 1 所示： 图2 1 配送流程图 合理的配送模式对于提高物流企业的经营水平、降低物流成本具有重要作用，我国 物流企业在发展的初期如何选择合适的配送模式对于企业的发展具有重要的意义【2 2 1 。 2 1 2j i t 基本原理 2 1 2 1j r r 概念的提出 准时化( j u s t i n t i m e ) 思想2 0 世纪5 0 年代首创于日本丰田汽车公司。 随着市场环境向多样化方向的变化和竞争的同益加剧，日本丰田汽车公司的经营管 理者认为，为了提高生产率，为了提高企业竞争力，应该消除各种浪费的途径，使生产 系统的库存达到最小。这种理念促使他们提出了准时化的生产方式( j u s t i n t i m e ) b 4 1 。 8 长安大学硕士学位论文 1 9 7 2 年后j r r 生产方式被广泛应用于日本汽车和电子工业。1 9 7 3 年以后，这种方式对 丰田公司渡过第一次能源危机起到了突出的作用，后引起其它国家生产企业的重视，并 逐渐在欧洲和美国的日资企业及当地企业中推行开来。现在这一方式与源自日本的其它 生产、流通方式一起被西方企业称为“日本化模式”，其中，日本生产、流通企业的物 流模式对欧美的物流产生了重要影响，近年来，j 1 1 不仅作为一种生产方式，也作为一 种物流模式在欧美物流界得到推行。 2 1 2 2j i t 理论的核心思想 准时化生产方式的基本思想是：“只在需要的时刻，按需要的量生产需要数量的产 品 ，也就是通过生产的计划和控制及库存的管理，追求一种无库存，或库存达到最小 的生产系统。在倡导j i t 生产方式以前，世界汽车生产企业包括丰田公司均采取福特式 的“总动员生产方式”，即一半时间人员和设备、流水线等待零件，另一半时间等零件 一运到，全体人员总动员，紧急生产产品。这种方式造成了生产过程中的物流不合理现 象，尤以库存积压和短缺为特征，生产线要么不开机，要么一开机就大量生产，这种模 式导致了严重的资源浪费。丰田公司的j i t 生产采取的是多品种、少批量、短周期的生 产方式，大大减少了库存，优化了生产物流，减少了浪费。这种生产方式使生产系统的 库存达到最小，在此思想引导下开发了包括“看板”在内的一系列具体方法，并逐渐形 成了一套独具特色的生产管理体系。j i t 生产方式的应变能力以及对质量、成本、制造 周期的有效控制方法，越来越强烈地影响着制造业【1 4 l 。 2 1 2 3j 1 1 r 的目标f 2 3 】 j i t 生产方式将“获取最大利润 作为企业经营的最终目标，将“降低成本 作为 基本目标。在福特时代，降低成本主要是依靠单一品种的规模生产来实现的。但是在多 品种中小批量生产的情况下，这一方法是行不通的。因此，j l t 生产方式力图通过“彻 底消除浪费 来达到这一目标。所谓浪费，在j r r 生产方式的起源地丰田汽车公司，被 定义为“只使成本增加的生产诸因素”，也就是说，不会带来任何附加价值的诸因素。 任何活动对于产出没有直接的效益便被视为浪费。这其中，最主要的有生产过剩( 即库 存) 所引起的浪费。搬运的动作、机器准备、存货、次品的重新加工等被看作浪费；同 时，在j i t 的生产方式下，浪费的产生通常被认为是由管理不完善所造成的。比如，大 量原物料的存在可能是由于供应商管理不善所造成的。 j i t 的目标是彻底消除无效劳动和浪费，具体达到的目标为： ( 1 )质量目标：废品量最低。j i t 要求消除各种引起不合理的原因，在加工过程 9 第二章基于j 1 1 r 供应的集货车辆路线问题研究的理论基础 中每一工序都要求达到最好水平。 ( 2 )生产目标：库存量最低，零件搬运量低，机器损坏低，批量尽量小。j 1 1 r 认 为，库存是生产系统设计不合理、生产过程不协调、生产操作不完善的证明；零件送进 搬运是非增值操作，如果能使零件和装配件运送量减少，搬运次数减少，可以节约装配 时间，减少装配中可能出现的问题。 ( 3 )时间目标：准备时间最短，生产提前期最短。准备时间长短与批量选择相联 系，如果准备时间趋于零，准备成本也趋于零，就有可能采用极小批量；短的生产提前 期与小批量相结合的系统，应变能力强，柔性好。 2 1 3 配送与j i t 生产方式的关系 传统生产方式是建立在对市场需求预测基础上，即通过需求预测制订生产计划和采 购计划。在传统生产方式下，一个重要的观念就是用库存来保证需求，用库存来保证生 产。因为市场需求是随机的，变化莫测，如果生产系统不能适应需求的变化，就只能依 靠库存来保证需求。因此，生产系统要能适应需求的变化，原材料、零部件的及时供应 就显至关重要。海尔集团首席执行官张瑞敏指出：“现代企业运作的驱动力是订单，如 果没有订单，现代企业就不可能运作。要实现这个订单，就意味着靠订单来采购，为订 单去制造，为订单去销售。 张瑞敏指的订单就是用户的需求，“强调的就是按需求 组织生产制造，组织采购和销售。”张瑞敏还进一步指出：“如果要完全实现订单去销售、 采购、制造，那么支持它的最重要的一个流程就是物流。 ( 2 0 0 1 年在“海尔现代物流同 步模式研讨会”上的讲话) o 准时化生产方式，就是以订单为基础的一种生产方式。这种生产方式生产的品种多、 批量小，其目的是减少浪费特别是由于库存造成的浪费。实现准时化生产的重要条件之 一是高效率、低成本的运输和配送。由于品种多、批量小、变化频繁，因此要求原材料、 零部件的供应也应及时，而且必须是小批量、多批次。又由于小批量、多批次运输成本 高，必须做到合理组配和寻找集运机会。同时，生产系统为了提高反应速度，适应需求 的变化，还会将某些生产准备活动向外委托，即交由专业的第三方物流企业承担，如原 材料的初加工、零部件检测、包装物的拆除和回收等。这就要求配送功能更加完善，能 够提供更多的增值服务，使供应物流与生产物流的衔接紧密无缝。 海尔集团2 0 0 1 年提出“定制冰箱”的概念，以订单为中心，依托物流技术和计算 机信息管理技术，实行j i t 采购、j i t 配送、j i t 分销与生产流程同步，采购周期由过去 1 0 长安大学硕士学位论文 的1 0 天减到3 天，生产过程降到1 周之内。产品一下线，中心城市在8 小时之内、辐 射区域在2 4 小时内、全国在4 天之内可送达到用户手中，完成客户订单的全过程仅为 1 0 天时间。如果没有高效率、低成本、多功能的运输与配送，这种生产方式是不可能实 现的【2 4 1 。 2 1 4j 1 1 r 理论在企业中的应用 2 1 4 1j l t 物流 全部工业产品生产过程和制造过程，除了加工和生产的时间以外，其他的都是物流 过程的时间。以机械产品的制造为例，生产过程中，加工时间仅占1 0 左右，而物流时 间竞占到9 0 ，很大一部分生产成本消耗在物流过程之中【2 5 1 。 物流管理面临的挑战就是找到既避免非经济性成本增加又能满足变化的需求的方 法，这需要进行诸多方面的权衡，但必须以提高整个供应链的成本效益为目标。面对增 大的压力以及经营中的问题，许多企业逐渐接受了创新的j r r 管理方法并应用于物流邻 域【2 6 1 。j i t 是一种生产方式，其核心是消减库存，直至实现零库存，同时又能使生产顺 利进行。这种观念本身就是物流功能的一种反应，而j 1 1 r 应用于物流邻域，就是指要将 正确的商品以正确的数量在正确的时间送到正确地点，这里的“正确就是“j u s t ”的 意思，既不多也不少、既不早也不晚，刚好按需要送货。这当然是一种理想化的状况， 在多品种、小批量、多批次、短周期的消费需求的压力下，生产者、供应商及物流配送 中心、零售商者要调整自己的生产、供应、流通流程，按下游的需求时间、数量、结构 及其它要求组织好均衡生产、供应和流通，在这些作业内部采用看板管理中的一系列手 段来减少库存，合理规划物流作业。这是为适应2 0 世纪6 0 年代消费需要变得多样化、 个性化而建立的一种生产体系及为此生产体系服务的物流体系。 j i t 物流是伴随着制造业准时生产而产生的，随着准时生产的发展与普及，准时化 物流亦得到了迅速发展和广泛应用。j i t 物流是精益思想的表现，是一组活动的集合， 其目的在于原材料、在制品及产成品保持最小库存的情况下，能保持连续、高节奏的大 批量生产【2 6 l 。 j r r 生产方式及j i t 物流，是为适应2 0 世纪6 0 年代消费需要变得多样化、个性化 而建立的一种生产体系及为此生产体系服务的物流体系。 2 1 4 2j r r 供应 任何企业进行生产经营活动，都要消耗各种物品。为了生产经营不间断地进行，就 第二章基于j i t 供应的集货车辆路线问题研究的理论基础 必须不问断地以新的物品补充生产经营过程的消耗，这种以物品补充生产经营消耗的过 程，就称之为供应。供应过程包括采购、储存、供料等环节，涉及商流、物流、信息流 和资金流。 企业为保证生产节奏，不断组织原材料、零部件、燃料、辅助材料供应的物流活动。 这种物流活动对企业生产的正常、高效进行起着重大作用。企业供应物流不仅是一个保 证供应的目标，而且必须在以最低成本、以最少消耗、以最大保证来组织供应的限定条 件下实现该目标。 准时化供应这种精益的供货方式是把物流、资金流、信息流合理组织到一起，成为 一个高度统一、高度集中的整体，使生产活动组织严密，没有多余的库存，也没有多余 的人员，实现库存成本大幅度下斛1 4 】。 准时化供应就是根据生产需求，在给定的时间范围内，将所要供应的零部件按照需 求送达指定的地点的供货方式。准时化供应要做到五个“准确 ：准确的物料、准确的 时间、准确的数量、准确的质量、准确的地点。只有做到这五个准确，准时化供应才能 顺利实施【1 4 1 。 准时化供应可以达到大幅度减少原材料和外购件的库存，提高物料供货的质量，降 低采购价格等目的【2 刀。 2 1 4 3j i t 采购【2 8 1 j i t 采购，即准时化采购，也是由j i t 生产的思想转化而来的。j r r 采购的基本思想 是与供应商签订在需要的时候提供需要数量的物品的协议。这意味着一天一次、一天两 次，甚至每小时数次地提供采购品。这种方法与传统的早在生产之前就把采购品大批量 送到的方法形成鲜明对比。 j i t 采购的核心要素包括：减少批量；频繁而可靠地交货；始终保持采购品的高质 量。其中每一方面都将使购货公司受益匪浅，而不仅仅是缩短了采购周期。 j i t 采购的最终目标是为每种物品或几种物品建立单一可靠的供应渠道，其结果是 从总体上大大减少了供应商的数量。用户可能把过多的精力与时间花费在与成百上千个 供应商建立伙伴关系上，对少数有限的供应商的资格进行严格的筛选评定，巩固彼此的 业务联系，变得非常重要。例如，摩托罗拉公司经常考察供应商的工厂，把他们在供货 质量和及时性等方面的指标与竞争者比较。供应商也欢迎这种做法，因为它有助于促进 自身管理水平的不断进步完善。 1 2 长安大学硕上学位论文 2 2 车辆路线问题 2 2 1 概述 车辆路线问题( v r p ) 是现实中十分普遍的一种调配问题，特别是对于有大量服务 对象的实体，例如一个拥有众多客户或供应商的公司。解决此类调配问题时，核心问题 是如何对车辆进行调度。在配送业务中，配送车辆调度问题的涉及面较广，需要考虑的 因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。该 问题包括集货线路优化、货物配送及送货线路优化等，是配送系统优化的关键【2 9 l 。 在日常生活和实际生产中，有许多问题都可以归为配送问题。如有一个中心站点， 需向多个连锁分店配送货物，每个分店对货物的需求量不同，但都小于仓储中心所拥有 的配送车辆的单车容量，配送车辆在仓储中心装货后出发，把货物送至各个分店，完成 后返回中心。又如，若干厂家生产一些产品，需要运到中心站点，每个厂家的产品量小 于运输车辆的容量，车辆从中心站点出发，到各个厂家去装货，装满后返回中心。类似 的问题都可以归结为v