（管理科学与工程专业论文）基于网络优化技术的物流配送问题研究.pdf

内蒙古大学硕士学位论文 基于网络优化技术的物流配送问题研究 摘要 物流作为“第三利润源泉”在国民经济中的地位和作用越来越重要，它对于 发展经济、加强军事力量、改善人们物质和文化生活以及扩大国际技术、经济 文化的交流等都具有重要意义。因此，建立一个物流配送网络模型是具有实际 意义的研究。该模型不但适合于物流配送网络的研究而且也适用于很多网络问 题的研究，如水网、电网等。因此对该问题的研究具有相当广泛的应用背景。 本文结合运输问题建立一个物流配送网络的数学模型，此模型在运输路径 和配送中心容量受限时，在给定的限制时间内可以对配送网络的容量进行扩充， 在满足物流配送网络容量需求的条件下获得运输方案使得总的运输成本最低， 同时通过构造辅助网络的方法，将物流配送网络模型转化为最小费用流问题， 并且在对最小费用流进行求解的过程中，考虑到物流配送网络的特性对最小费 用流的求解方法进行改进和简化。 模型的目标就是在物流配送网络的容量可以在一个特定时间限制内进行扩 充的条件下，如何制定改造或扩建计划并安排物资的运输方案，使得既满足运 输网络的容量扩张要求，又使总的运输成本( 运输费用+ 改造或扩建费用) 最 小。 关键词：物流配送网络模型，配送中心，容量扩充，辅助网络，最小费用流 基丁二网络优化技术的物流配送网络研究 s t u d yo nl o g i s t i c sd i s t r i b u t i o nn e t w o r kb a s e do n t e c h n o l o g yo fn e t w o r ko p m i z a t i o n a bs t r a c t l o g i s t i c sa st h e “t h et h i r ds p r i n go fg a i n i sm o r ea n dm o r ei m p o r t a n ti nt h e n a t i o n a le c o n o m y i ti sp r o p i t i o u st od e v e l o pe c o n o m y , t oe n h a n c et h em i l i t a r ya f f a i r s ， i m p r o v et h es u b s t a n c ea n dc u l t u r el i f eo fp e o p l ea n de x p a n dt h ei n t e r c o m m u n i c a t i o n o f t e c h n o l o g ya n dc u l t u r e i ti sp r a c t i c a lt oc o n s t r u c tam o d e lo fl o g i s t i c sd i s t r i b u t i o n n e t w o r k t h em o d e ld o e s n to n l ya d a p tt ol o g i s t i c sd i s t r i b u t i o nn e t w o r kb u ta l s o a d a p tt oo t h e rn e t w o r k ，f o re x a m p l et h ew a t e rn e t w o r ka n de l e c t r i c i t yn e t w o r k t h e s t u d yo nt h em o d e li ss oa p p l i e d i nt h i sa r t i c l e ，w ec o n s t r u c tam o d e lo fl o g i s t i c sd i s t r i b u t i o nn e t w o r kw i t h l i m i t a t i o no f c a p a c i t y , a n dt h ec a p a c i t yc a nb ee x t e n d e dw i t hc o s ti nt h el i m i t e dt i m e w ew a n tg e tt h el o w e s tc o s tw h e ns a t i s f yt h en e e d e dc a p a c i t yo ft h el o g i s t i c s d i s t r i b u t i o nn e t w o r k w es o l v et h eq u e s t i o nb yu s i n ga u x i l i a r yn e t w o r k ，a n dt u r nt h i s p r o b l e mi n t om i n i m u mc o s tf l o wp r o b l e m t h i n k i n go ft h ec h a r a c t e r i s t i co ft h e l o g i s t i c st r a n s p o r t a t i o na n dd i s t r i b u t i o nn e t w o r k ，w ec a np r e d i g e s tt h em e t h o do f m i n i m u mc o s tf l o wp r o b l e m f r o mt h em o d e l ，w ec a nk n o wh o wt oa r r a n g et h et r a n s p o r ts c h e m et og e tt h e l o w e s tf i n a lc o s t ( t h et r a n s p o r tc o s ta d d st h ee x p a n dc o s t ) w h e nt h ec a p a c i t yo ft h e l o g i s t i c st r a n s p o r t a t i o na n dd i s t r i b u t i o nn e t w o r ki se x t e n d e dw i t hc o s ti nt h el i m i t e d t i m e k e y w o r d s ：l o g i s t i c s d i s t r i b u t i o n n e t w o r k ，t r a n s p o r tp o i n t s ，c a p a c i t y e x p a n s i o n ，a u x i l i a r yn e t w o r k ，m i n i m u mc o s tf l o w 1 1 内蒙古大学硕士学位论文 图表目录 图4 1 物流配送网络15 图5 薹算法流程图3 2 图5 2 辅助网络d ”3 8 图5 3 长度网络p ( f 。) 3 8 图5 4 长度网络p ( f 1 ) 3 9 图5 5 长度网络, ( f r o ) 4 0 表5 1 模型中己知参数3 7 表5 2 各弧流量4 l v 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 己经发表或撰写过的研究成果，也不包含为获得内蒙古大学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：多垂盔鸯指导教师签名：学位论文作者签名：盈缝鹭指导教师签名： 日 期：坦壁! ! 丕 日期： 在学期间研究成果使用说明书 学位论文作者完全了解内蒙古大学有关保留和使用学位论文的规定，即：内 蒙古大学研究生在校攻读学位期1 1 日j 论文工作的知识产权单位属内蒙古大学。学校 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查 阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。作者今后使用涉及在学期间主要研究内容 或研究成果，须征得内蒙古大学就读期问导师的同意：若用于发表论文，版权单 位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名： 日期： 指导教师签名： 同期： 古星匕 趑纰赶够 内蒙古大学硕士学位论文 1 1 物流配送问题研究背景 第一章绪论帚一早瑁下匕 随着我国市场经济体制的逐步完善，市场上的商品不断丰富，短缺经济基本结束，逐步 形成了买方市场，市场一体化、竞争国际化趋势十分明显。被普遍认为企业在降低物质消耗、 提高劳动生产率以外的现代物流业开始为各界广泛关注。物流科学已经成为当代最有影响的 新学科之一。物流是指按用户( 商品的购买者、需求方、货主等) 要求，将物的实体( 商品、 货物、原材料、零配件、半成品等) 从供给地向需求地转移的过程，是管理工程和技术工程相 结合的综合学科，它应用系统工程学科的原理和相关技术领域的最新成果，提高物流系统的 水平与效率，实现了物流的时间效益与空间效益。 实践证明，物流科学的应用能够给国民经济和企业的生产经营带来出乎预料的经济效益。 物流科学登上历史舞台只不过数十年时间，然而由于它对社会经济和企业经营具有强大的影 响力，己经引起了经济界和企业界的高度重视，而被称为经济领域“企业脚下的金矿”、“未开 发的黑大陆”、“第三利润源泉”【l 】。 物流能力是现代企业的核心竞争力，是一国综合实力的重要体现。有关资料显示，发达 国家的运输成本占国民经济总成本的1 0 ，而中国为3 0 ；在欧美发达国家，社会物流的总 成本一般占g d p 的比重为1 2 左右，随着物流管理的现代化，这个比例仍趋于下降。如美国 的物流成本占g d p 的比重由1 9 8 0 年的1 7 2 降到1 9 9 5 年的9 。据世界银行分析，中国的 物流成本占g d p 的比重为1 6 7 ，以我国2 0 0 0 年g d p l 0 0 0 0 亿美元计算，如果物流的总成 本占g d p 的比重降到一般发达国家1 2 的水平，那么每年可以为国家增加4 7 0 亿美元的利润。 然而从产品供应链的结构来看，9 0 左右的时间都消耗在流通环节，在生产环节的时间只占 1 0 左右。因此，优化运输物流，降低运输成本，是物流配送企业提高企业竞争力的有效途 径之一。 在对物流配送的研究中，以有效控制配送过程中发生的配送成本、配送时间等为主要内 容的车辆路线问题【2 1 ，即v r p ( v e h i c l er o u t i n gp r o b l e m ) i h - 题，成为研究的核心和目标。车辆 路线问题一般可以定义为：对于若干个配送中心和用户点，合理地安排车辆的配送路线，使 载货车辆有序地通过它们，在满足一定的约束条件( 如用户的需求量、发送量、车辆容量限 基于网络优化技术的物流配送网络研究 制、行驶里程限制、时间限制等) 下，达到一定的目标( 如配送里程最短、总费用最少、时 间尽量少、使用车辆数尽量少等) 。由于从事物流配送的车辆尤其是从事城市配送的车辆工作 条件复杂，不仅用户点多、货物种类繁多、道路网复杂，而且运输服务地区内的运输网点分 布也不均匀。因此，设计合理、有效的配送车辆路线方案，尽量减少车辆数量、配送里程以 及配送费用等就成为非常实际的问题。通过利用现代的数学方法，同时结合计算机来实现配 送调度计划是物流配送研究主要解决的问题，同时也是国内外专家学者普遍关注的重要课题 之一，它可以很好的实现降低配送成本、提高配送效率的要求。 1 2 问题研究的意义和目标 随着市场经济发展步伐的加快，作为“第三利润源泉”的物流对经济活动的影响日益明显， 越来越引起人们的重视，大量经营规模较大的制造企业和商业企业纷纷建立起自己的配送网 络，向商品流通效率化发起挑战。因此如何对物流配送进行优化，在提高物流配送效率的同 时降低成本成为一个非常重要的研究课题。 目前企业物流配送方式有三类：占了最大部分的是供应商自理物流，就是由供应商直接 进行商品配送。如国内的一些大卖场和综合超市，由总部确定统一的供应商，店铺向供应商要 货，由供应商直接将商品配送到店铺。第二类是零售企业自有物流配送中心。由于我国相当 数量的连锁企业是从传统的副食品公司、蔬菜公司、粮店以及其他配套网点的基础上建立起 来的，这些企业自身就拥有场地、设施、设备、人员等建立配送中心的资源和基础。第三类 是借助第三方物流。 ， 物流配送管理的本质就是在满足需要的前提下尽最大的可能降低成本。因此降低成本成 为关键的因素。而降低成本要考虑到的有好多方面：路线选择、信息、装卸、运输工具的选 择等等。可以通过利用模型对模型进行求解来获得成本最低的物流配送策略，在运筹科学中 提出了运输问题，可以求得成本最低的运输策略。最早研究这类问题的是美国学者希奇柯克 ( h i t c h c o c k ) ，1 9 4 1 年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的 基本模型 3 1 后来柯普曼( k o o p m a n s ) 在1 9 4 7 年独立地提出运输问题并详细地对此问题加以讨 论【4 】，从上世纪4 0 年代早期开始，康脱洛维奇( k a n t o r o v i c h ) 围绕着运输问题作了大量的研 究【5 j ，运输问题可以描述为：设某物品有m 个产地a ，彳：，a 。，各产地的产量分别是 a l , 口：，口。；有i 1 个销地马，b 2 ，吃，各个销地的销量分别为6 l ，b ：，b 。假定从产地a ， ( f = 1 , 2 ，m ) 向销地口，( = 1 , 2 ，拧) 运输的单位物品的运价是c l ：，问怎么调运这些物品 2 内蒙古大学硕士学位论文 才能使得总运费最小? 该问题为求解最佳的调运方案，即求解所有的嘞的值，使总的运输费 用c ，嘞达到最小。可以从运输问题模型的描述下看出，利用运输问题的模型可以得到运 i = 1 j = z 输费用也就是成本最小的运输方案，从而降低了成本。同时可以看出运筹科学提出的运输问 题有着自身的局限性，通常在现代物流配送过程中会考虑物流配送中心( 即转运点) ，而并不 只从供应商运送到经销商，另一方面在实际的货物运输过程中，货物的运输容量也不是无限 的，而是有限制的。同时，可必花费时间和成本对容量进行扩充。由于现实的物流配送过程 中存在着以上的实际情况，因此，运筹科学所提出的运输问题模型，对现实的物流配送并没 有实际的指导意义。需要一个新的物流配送模型，在该物流配送模型中考虑现实的物流配送 过程中存在的实际限制和约束，该模型与传统的运输问题相比较，更切合实际，对现实的物 流配送过程中如何求得最低成本具有更好的指导作用。 本文结合运输问题建立一个物流配送网络的数学模型，此模型在运输路径和配送中心容 量受限时，在给定的限制时间内可以对配送网络的容量进行扩充，在满足物流配送网络容量 需求的条件下获得运输方案使得总的运输成本最低，同时建立一种有效的方法对该模型进行 求解。模型的目标就是在物流配送网络的容量可以在一个特定时间限制内进行扩充的条件下， 如何制定改造或扩建计划并安排物资的运输方案，使得既满足运输网络的容量扩张要求，又 使总的运输成本( 运输费用+ 改造或扩建费用) 最小。同时，通过构建辅助网络的方法，将 问题转化为最小费用流问题，并且根据模型的特点对最小费用流问题的求解算法进行改进和 简化。降低了求解的复杂性。最后给出了该模型实现的代码，利用计算机语言对该模型进行 实现，使得该模型对实际的物流配送更具有实际的价值。 该模型不仅适用于物流配送问题，也适用于很多网络问题，如水网、电网等。因此对该 问题的研究是一个具有相当广泛应用背景的课题。建立这样一个运输模型并且用语言实现该 系统对相关问题的研究都是具有指导意义的。 1 3 论文的研究思路与框架 本文研究的内容就是结合运输问题建立一个物流配送网络的数学模型，此模型在运输路 径和配送中心容量受限时，在给定的限制时间内可以对配送网络的容量进行扩充，在满足物 流配送网络容量需求的条件下获得运输方案使得总的运输成本最低，同时建立一种有效的方 法对该模型进行求解。全文共由五章组成分别为：绪论、物流配送网络、网络优化、建立物 流配送网络模型、物流配送网络模型求解。第一章绪论阐述了问题研究的背景和现实意义。 3 基于网络优化技术的物流配送网络研究 第二章介绍了物流配送网络的产生和发展以及物流配送网络的经济效益，介绍了物流优化的 主要研究对象和物流配送网络的概念。第三章网络优化主要介绍了网络优化的背景知识，主 要介绍了论文中对模型求解要使用到最小费用流方法。第四章主要构建了在运输路径和配送 中心容量受限时，在给定的限制时间内可以对配送网络的容量进行扩充，在满足物流配送网 络容量需求的条件下获得运输方案使得总的运输成本最低的物流配送网络模型。第五章先对 一个基于运输问题的简单模型构建辅助网络对模型进行求解，然后逐步的对模型添加条件形 成新的模型，构建辅助网络对新模型进行求解，直至形成第四章构建的物流配送网络模型， 最后构建辅助网络将物流配送网络模型转换成最小费用流的问题并给出合适的算法对问题进 行求解。在问题的求解过程中由于物流配送网络自身的特性，对传统的求解最小费用的算法 进行改进，使得算法的更加的简便并具有针对性。在构建辅助网络时主要的工作包括：考虑 如何构造一个符合该模型的辅助网络使得可以将问题转化为最小费用流问题；如何在构造辅 助网络时表示运输路径扩充的容量；如何在构造辅助网络时表示配送中心扩充的容量；如何 在表示容量的扩充时体现容量的扩充是受给定的时间限制的；如何对辅助网络中的弧上的参 数进行设定。 4 内蒙古大学硕士学位论文 第二章物流配送网络 近些年物流热潮在我国持续升温，配送中心作为集物流、信息流和资金流为一体的流通 型节点，已经广泛在全国各地兴起。在现实生活的运输网络中，我们往往会在物资的运输途 径上设立配送中心，来实现物资的转运、分类、加工等一系列功能。配送中心是广泛存在于 西方发达国家的一种专业化的物流组织。日本物流手册1 9 9 1 年版认为：“物流配送中心 是从供应商手中接受大量的货物，进行倒装、分类、保管、流通、加工和情报处理等作业， 然后按照多需要者的订货要求备齐货物，以令人满意的服务水平进行配送的设施。”在社会化 大生产和社会化大流通的背景下，配送中心在商品实体由生产领域向消费领域的转移过程中 处于枢纽地位，已成为保证社会经济正常运转所必不可少的物流环节。其对于社会经济运行 效率和社会总体经济效益的提高意义重大，同时也对生产和流通等社会经济的各方面产生了 深刻的影响。 目前我国的配送中心发展热潮已历经多年，各地区、各领域兴建配送中心的积极性都很 高。北京、上海、天津、深圳等经济发达地区的政府有关部门，均在着手进行配送中心的规 划和建设工作，众多仓储运输企业和大型工商企业或部门也在抓紧运作配送中心的建设。近 年来试行配送的城市已扩大到近百个，出现了一批不同类型的配送中心。 配送中心在我国的兴起，充分说明了这种组织形式具备发展现代物流的战略优势。首先， 物流配送中心是最安全、最高效的流通组织者，一般拥有较完备的物流设施设备，有着丰富 的物流配送管理与运作经验及较强的专业技术力量，所以在物流配送方面有着雄厚的实力， 能够提供高效、优质的物流配送服务。再者，由于物流配送中心拥有广泛的、相对稳定的零 售及消费需求网络，能够保证产品顺畅地通过流通领域，有效地实现产品的价值，这种物流 资源的战略优势是生产企业自身难以形成的。另外，物流配送中心是产品市场需求信息的最 佳反馈渠道，因为它在处理大量订单的过程中，可以准确掌握某类( 种) 产品的市场需求情 况，了解消费者对产品的改进要求并且通过采购过程将这些信息及时地反馈给生产企业，以 便及时调整生产，改进产品，提高产品的市场占有率。 这种融管理与服务为一体的多功能、面向社会的货运配送中心，还可以提高运输的效率， 减少运输费用，节约运力、缓解交通紧张的矛盾等。以此为基础，发展地区间的联系，形成 运输网络，合理组织货源，优化运输线路，降低物流成本，以提高社会经济效益。 5 基于网络优化技术的物流配送网络研究 2 1 物流配送及产生发展 物流配送：物流配送是指以现代送货形式实现资源最终配置的经济活动，按用户订货要 求，在配送中心或其他物流节点经过分货、拣货等货物配备工作并以最合理的方式送交用户 p 】。配送几乎包括了所有的物流功能要素，是物流的一个缩影或在某个小范围中物流全部活 t 动的体现。一般的配送服务均集装卸、包装、保管、运输于一身，通过这一系列活动将货物 送达目的地货主。它是由送货逐渐演变过来的，资本主义经济的生产过剩，在买方市场情况 下，必然采取各式各样的推销手段，送货最初便是作为一种不得已的推销手段出现的。刚开 始，企业将配送作为推销手段而没有认识到它是企业发展的战略手段。 在市场竞争中，将货物送达用户的活动需要逐步降低成本、提高效率，以达到占领市场 和扩大市场、增加企业利润的目的。对小批量、多品种货物的快速分拣，运输车辆的合理配 置，运输规划的科学制订，并且将运送货物事先进行配货、配装措施的逐步完善，形成了现 代的物流配送活动。从配送的实施形态角度，配送的定义可以表述为：按照用户的订货要求， 通过在配送中心对货物进行各种处理，以最合理的方式将货物送交用户的行为或活动。 如今，配送经过四十多年的发展，现在的配送区域进一步扩大，配送中心数量规模增加， 配送的技术、手段得以提高，配送的形式出现多元化，独立的配送、直达配送、共同配送、 实时配送。在发达国家配送已经成为制造商和经销商普遍接受和采用的物流方式，而且这种 物流方式还在不断地向前发展。目前物流配送已经以专业化、机械化发展为特点的初级阶段， 发展到了以电子信息为基础，注重服务、人员、技术、信息和管理的综合集成为特点的现代 物流。配送中心、加工中心等物流中心遍布美国、日本和西欧，他们对物流配送的研究也较 多，已经形成比较成熟的理论体系，不论是硬件方面还是软件方面都具有相当高的水平。其 中美国在物流配送机械方面的水平较高；日本物流配送基础设施良好，物流配送社会化、组 织化程度较高，注重物流配送实用技术和方法，物流配送成本控制较好；西欧以德国为代表， 德国以物流配送中心而著称，政府参与物流中心的规划和设计。 近几十年来，随着现代经济的持续高涨，物流产业在市场经济的激烈竞争中运作质量越 来越高，规模也越来越强，配送规模及其范围在同步扩大。发达国家物流配送的发展呈现出 了以下特点：配送规模日趋扩大，配送中心数量明显增加；配送技术和设施更加先进，如条 形码识别技术、自动存货和补货技术、自动分拣技术等；配送方式多样化；配送共同化、计 划化；配送区域化、网络化；配送管理电子化等等。 纵观我国配送技术的发展，可以说经历了三次革命【引。第一次革命就是送货上门，可称 6 内蒙古大学硕士学位论文 之为传统配送。第二次物流革命是伴随着电子商务的出现而产生的。第三次物流革命就是物 流配送的信息化以及网络技术的广泛应用所带来的种种影响，使得物流配送更有效率。目前， 在我国物流配送已经引起政府部门和商业企业界的极大重视。关于物流配送的发展，国家有 关部门对商品物流和配送采取了积极鼓励和支持的政策。随着国家对物流业的重视，近年来， 我国配送行业在配送规模、配送形式、配送设施以及配送服务功能等方面都已经得到了一定 程度的发展。 2 2 物流配送系统的经济效益 物流配送的效益主要体现在社会规模效益上，通过配送中心先进的管理技术和现代化的 信息网络，合理地配置流通渠道，减少流通环节，降低社会库存，加快社会资金周转，使货 物流向更趋于合理化，从而实现最佳的经济效益。 物流配送实现了库存社会化和生产企业的“零库存”，能够大大提高库存的周转率、提高 仓容利用率，从而使资金周转速度加快，为均衡生产和扩大再生产创造有利的条件；改变了 产品的传统流通模式，在产品的流通程序上，由工厂产什么、批发商买什么，发展到用户订 购什么、配送中心向生产企业要什么，进一步确保了企业产品的销售成功率，同时对商品的 质量控制和信息反馈都相对有效，从而更有利于企业的发展壮大；在保证用户最佳订货量的 前提下，配送中心通过选择最佳的运输手段和工具，减少了运输次数，从而缩短了运输距离， 降低了运输费用，提高了流通效率；通过签订物流配送协议，物流部门可以了解、掌握生产 企业的生产和产品销售情况，从而利用其信息灵、渠道广、业务力强等有利条件，为生产企 业传递市场信息，同时承担部门产品的推销任务，也可以用产品抵物资货款；通过物流配送， 建立了稳定的供需关系，大幅度地降低了供需双方的交易次数，相应的增加了交易批量，这 样，在批量进货时配送中心可以获得优惠进价，并与客户分享这部分利润，从而产生规模效 益【9 1 。 2 3 物流优化的主要研究对象 物流系统是指在一定时间和空间里，由所需位移的物资与包装设备、搬运装卸机械、运 输工具、仓储设施、人员和通讯联系等若干相互制约的动态要素，所构成的具有特定功能的 有机整体。物流系统的目的是实现物资的空间和时间效益，在保证社会再生产顺利进行的前 提条件下，实现各种物流环节的合理衔接，并取得最佳的经济效益。物流优化是指对物流系 统进行规划和设计，通过降低成本、提高服务水平，达到实现最佳物流的目的。物流优化的 7 基于网络优化技术的物流配送网络研究 主要研究对象有设施选址、库存管理、运输与配送【1 0 1 。 2 3 1 运输与配送 物流活动中的运输，是指为了克服物品的空间障碍所进行的场所移动。制定最优运输计 划，包括对运输工具、运输线路、运输时间等的最佳选择。当车辆没有满载或者客户的需求 为多次、小批量时，为了节约费用，车辆一次装载的货物包括若干个客户的需求量，并且在 一次运输过程中依次对这些客户进行访问，此类运输问题称为配送问题。 2 3 2 库存管理 库存，就是在生产及流通领域中各个环节所持有的原材料、零部件和成品。有效的管理 库存、控制库存成本对于降低物流系统成本有非常重要的作用。库存管理的目的就是考虑生 产计划、顾客服务和经济性，使库存量合理和补充货物及时。 按照库存管理功能有以下的分类：为了满足连续补货期间的平均需求而存储的必要库存， 称为周期库存；为了满足具有明显的季节性消费特征产品的季节性库存；为了防止产品制造与 供应的意外情况而设立的安全库存。对库存决策提供的条件有：顾客的需求、库存策略、库存 成本、从订货到交货的时间等。按照顾客需求的不同有确定性需求模型和随机需求模型。 2 3 3 设施选址 选址在整个物流系统中占有非常重要的地位。设施主要指物流系统中的节点，如制造商、 供应商、仓库、配送中心、零售商网点等。选址决策就是确定所要分配的设施的数量、位置 以及分配方案。选址是最重要的长期决策之一，选址的好坏直接影响到服务方式、服务质量、 服务效率、服务成本等，从而影响到利润和市场竞争力，甚至决定了企业的命运。 选址的影响因素很多，包括宏观政治经济因素、基础设施及环境、竞争对手、企业的发 展战略、产品、技术和服务等。选址问题的模型有很多，根据设施允许安置的空间，可分为 连续选址、网络选址和离散选址。连续选址又称为平面选址，它允许在可行的连续空间的任 何地方选址，多半采用解析方法。网络选址允许在指定网络的顶点与边上选址，而离散选址 只允许在指定的一些离散点集上选址，后两者主要用组合方法研究。选址研究中的问题有 w b e e r 问题、中值问题、覆盖问题、中心问题、多目标选址、竞争选址、选址分配、选址 路线等。其中最典型三种模型是p 中值选址问题、覆盖选址问题和p 中心选址问题。 2 4 物流配送网络概念 配送( d i s t r i b u t i o n ) 即在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、 包装、分割、组配等作业，并按时送达指定地点的物流活动配送是物流中的一种特殊的、综 8 内蒙古大学硕士学位论文 合的活动形式，几乎包括了所有的物流功能要素。一般配送集装卸、包装、保管、运输于一 身，通过这一系列活动完成将货物送达目的地；特殊的配送则还要进行加工活动。它的目的指 向是安全，准确，优质的服务和较低的物流费用。 网络( n e t w o r k ) ：从网络拓扑学的观点来看，网络是由一组节点( n o d e ) 和链接节点的链路 组成。节点可分为两类，一类是转接节点；一类是访问节点，访问节点一般处在网络的末端， 所以访问节点又称为端点。所谓拓扑，是一种研究与大小、形状无关的线和面特性的方法， 由数学中的图论演变而来，图是由线所连接的点的集合。星形拓扑结构由一个功能较强的转 接中心以及一些各自连到中心的节点组成，转接中心通过所连接的链路转发信息。 配送网络( d i s t r i b u t i o n n e t w o r k ) ：配送网络是物流配送过程中相互联系的组织与设施的集 合。配送中心是配送网络的转接节点，接收供应商供货，并及时为客户配送。客户就是配送 网络的访问节点，即端点。配送中心为客户配货的运输线路即为连接转接节点和端点的链路。 配送网络由若干个星形拓扑结构构成，各星形结构的中心节点根据端点信息通过运输线路配 送货物，而且各拓扑结构之间不是孤立的，而是紧密相关的。 本文就是根据实际情况构造一个物流配送网络的模型，对模型进行网络形式的描述，通 过构建辅助网络，将配送网络转化，最后利用网络优化的技术对该配送网络模型进行求解， 得到最优的配送方案。 9 基于网络优化技术的物流配送网络研究 第三章网络优化 3 1 网络优化技术 叶。? 现代社会中网络无处不在，从运输服务网络、能源和物质分配网络、到计算机信息网络、 电话通信网络各种各样的网络构成人们的日常生活。网络优化就是研究如何有效地计划、管 理和控制网络系统，使之发挥最大的社会和经济效益。 网络优化是管理科学中的一个经典和重要的分支，它已经广泛地应用在管理、计算机科 学、信息论、控制论、物理、化学、生物学和心理学等各个领域，并取得了丰硕的成果。早 在1 7 3 6 年，瑞士数学家欧拉( e e u l e r ) 就发表了一篇题为依据几何位置的解题方法的论 文，有效地解决了哥尼斯堡七桥难题，这是有记载的第一篇图论论文，也是网络优化的典范， 欧拉因此也被公认为图论的创始人。国内在2 0 世纪5 0 年代中期开始了关于网络优化方面的 研究，尤其是近年来这个研究方向正在逐渐引起人们的重视，但是目前还没有得到广泛认可 的实际应用系统。目前国外已经把网络优化技术的研究成果广泛地应用到实际中，比如电讯 网络、交通控制以及生产管理等方面国内在规划设计和物流配送等方面也有初步的应用。 网络优化问题可以用经典的线性规划方法来解决，但是当网络的节点达到一定规模以后， 用传统的线性规划方法解决往往是比较困难的。对于节点很多的网络优化问题有一些专用的 算法，具有更高的效率。当然，这些专用算法本身有各自的特点，效率也不尽相同。网络优 化算法在解决经济和后勤等问题上，例如制造工具的生产、通讯网络中包的路由选择、运输 网络中的任务分配，是一类应用广泛的优化算法，是一种功能强大的工具。 网络优化研究的主要问题有：路径分析，即对最佳路径和最短路径的求解；资源分配， 即为网络中的网线和结点寻找最近( 这里的远近是按阻碍强度的大小来确定的) 的中心( 资 源发散或汇集地) ；连通分析，即寻找从某一结点或网线出发能够到达的全部结点或网线；流 分析；流分析的问题主要是按照某种最优化标准( 时间最少、费用最低、路程最短或运送量 最大等) 设计运送方案。 最小费用流问题是网络优化的一个主要的研究内容，它研究的对象是网络中的流，这类 问题是人们在生产过程或生活中为达到某个目的而选择一个“最优路径”方案或一组“得力”措 施而取得“最佳”效果这样一个宏观过程。在实际生活中，常常会遇到最小费用流的问题。如 1 0 内蒙古大学硕士学位论文 物流配送网络中规定了各个运输方向上的最大通过能力，又规定了各个方向上的单位物资运 输费，问应如何组织调运，才能使得从某一地到另一地运送最多的物资，而总的运输费用又 最少? 这就是一类最小费用流问题。在最小费用流问题的网络中，我们除了考虑每条弧上对 于流的容量限制外，还要考虑另外一个权，也即成本( 费用) 。为了描述最小费用流问题，我 们在这里提出“容量费用网络的概念【15 1 。 在以矿为节点集，么为弧集的有向图g = ( 矿，a ) 上，定义如下的弧上的权函数： 1 、c ：a 一 r 为弧上的权函数，弧( f ，) a 对应豹权c ( i ，) 记为，称为弧o ，) 的单 位流量的成本或费用； 2 、三：a 一 r 为弧上的权函数，弧( f ，) a 对应的权( f ，) i d e sl o ，称为弧( f ，) 的容量 下界； 3 、u ：a 一 r 为弧上的权函数，弧( f ，) a 对应的权u ( i ，j ) 记为甜。，称为弧( f ，歹) 的容 量上界，或直接成为容量； 4 、d ：a 一 r 为顶点上的权函数，节点f v 对应的权d ( i ) 记为z ，称为顶点f 的供需 量。 此时所构成的网络我们称之为容量一费用网络，可以记为n = ( v ；a ，c ，l ，u ，d ) 。可见，容 量一费用网络也是一种流网络，我们在后文中把这种容量一费用网络称为流网络或直接称为 网络，网络流的各种概念都可以引入到容量一费用网络中来。最小费用流问题就是在这样的 网络中，寻找流的容量一定时，总费用最小的可行流。 本文是根据物流配送的需求，构建一个物流配送网络模型，然后通过建立辅助网络，将 模型转化为网络流问题。最后通过对网络优化中的最小费用流问题的求解方法进行改进简化 来对模型进行求解。 3 2 网络容量的扩张 随着国民经济的发展，城市物流供给能力不足，已严重影响了经济发展中各种商品、物 资在自然空间上的合理流动，阻碍了一个国家或地区的物流业的快速发展，成为制约一个国 家或地区的国民经济快速发展的瓶颈。为了克服这一瓶颈现象，就需要增加交通运输能力， 也就是物流运输网络的容量扩张问题，为此必须增加对交通基础设施建设的投资力度。如何 从城市总体交通状况出发，提出科学的、系统的交通投资改进方案，通过这些合理的投资分 配方案，进一步促进城市交通状况的改善，带动城市各项经济活动的发展，达到交通建设与 基于网络优化技术的物流配送网络研究 有限资金的和谐统一，这是一个关系到国民经济长期、持续、快速、稳定发震的大问题。交 通运输网络的容量扩张问题研究，主要就是通过优化计算方法寻找最优的用于道路网络新建 或者改善的交通建设投资方案以及城市交道运输网络扩张方案，即用较少的资金投入达到交 通运输网络某项指标最优的目的，从而为交通运输规划决策以及城市规划提供有效的决策理 论依据。因此，交通运输网络的扩张模式研究可以为特大中心城市普遍存在的交通拥挤状况 提供对策和方法，为交通运输规划和城市规划部门提供决策依据，为资金投入产生最佳的投 资收益提供理论依据。 近年来，网络容量这个概念已经在交通问题，例如交通管制、交通控制、道路定价和交 通网络实际建设中得n t 广泛的应用。例如，f e r m r i ( 1 9 9 5 ) 和y a n g 与b e l l ( 1 9 9 7 ) 将网络 容量的模型与方法用于解决城市交通网络中交通信号控制的问题。网络容量指的是在给定的 网络中可达到的最大吞吐量，它对于有效的网络流量控制和需求管理非常重要。在传统的网 络流理论中，最大流问题或者网络容量问题是非常容易定义的：如果一个网络的链路上有容 量，我们如何才能使得特定的起讫点之间通过的流量尽可能的大，而不超过网络上两点之间 任何的链路上的容量值。这就是有名的单网络单商品容量问题，由这个问题引申，很容易扩 展到多商品最大流问题。渴原有的网络容量已经不能满足经济发展的需求，必须对其进行调 整与扩张。现实生活中我们还经常遇到需要扩充网络容量的情况，在很多实际应用中，我们 希望用尽量少的成本将网络的能力提升到预定的水平。例如，我们希望用最低的成本改造网 络，使其达到预期的标准，这种情况同样发生在电信等网络的扩张问题中。除此之外，很多 关于城市交通网络中的问题都得到了很大的发展，例如交通网络信号控制、公交系统规划、 交通设施选址问题等。除了传统的数理统计、运筹学等理论外，其他的数学方法和计算机技 术也得到了很大的应用，如神经网络、模糊数学、信息技术、g i s 技术等。一个好的网络容 量扩张模型可以让我们预测道路运输网络还可以容纳多少增加的需求，从两建立有效的政策 来约束或者刺激流量增加或减少。此外，网络容量扩张模型可以帮助我们决策，如果未来流 量增长的时候，应该采取一些什么样的措施。因此它对于现实生活中的运输阍题优化具有很 重要的理论意义和实际意义。 目前，网络系统的优化扩张阅题研究也已经逐步地运用到了除交通运输以终的透信、电 力等很多的领域。网络容量的扩张问题也成为了国内外学者研究的热点问题。现有的网络优 化扩张阀题研究，一般可归纳为两类基本问题：给定预算费用d ，如何使网络容量尽可麓的 扩大；给定一个预定容量r ，如何对网络进行扩张，使扩张后网络容量指标达到r 而扩张费 1 2 内蒙古大学硕士学位论文 用最小。各种网络优化扩张问题都是基于这两类基本问题来建模和求解的。 3 3 物流配送网络中的容量扩张 物流配送网络中货物的运输方案可能有许多个，从中寻求一个运输费最小的调运方案是 物流配送网络的一个很重要的研究内容。在物流配送网络中如果不考虑运输路径的运输能力 限制、配送中心的仓储能力或转运能力的问题。随着客观情况的发展变化，经常会出现运输 路径单位时间内的最优调运量超过实际的通行能力的情况。因此在建立物流配送网络的模型 时如果不考虑这种情况的出现就会限制该运输模型在实际中的应用。为此在建立模型时我们 就必须的考虑在增加运送货物的数量，就要在运输系统的原来基础上采取提高道路等级、修 建新线路、改进转运仓储设施等措施来扩大道路或转运点的容量。 如何制定改造或扩建计划并安排物资的运输方案，使得既满足运输网络的容量扩张要求， 又使总的成本( 运输费用+ 改造或扩建费用) 最省? 这就是本文建立物流配送网络模型所要 讨论的问题。这一问题不仅仅在理论上，而且在实际应用中都具有重要的意义，在通讯、电 路、石油管道等系统中广泛存在。实际情况往往是运输路径上的运输能力和配送中心的仓储 能力或转运能力是可以允许增大的，只要我们投入一定的人力、物力、资金和时间，便可以 解决这类容量扩张问题。 1 3 基于网络优化技术的物流配送网络研究 第四章构造物流配送网络模型 在物流配送网络中由于车辆的装载能力、以及城市交通供给能力、配送中心规模等一系 列的原因，物流配送网络路径和配送中心的容量是有限的，同时为了满足物流配送网络的容 量需求，则必须对在限制时间内对路径和配送中心的容量进行扩充，因此建立该物流配送网 络模型来求运输成本( 运输费用+ 改造或扩建费用) 最小的运输计划具有实际的指导意义的。 运筹科学中的运输问题是一个最简单、基本的一个物流配送网络模型。本文所研究的物 流配送网络模型是建立在运输问题的模型之上，结合当代物流配送的实际情况对运输问题模 型进行扩展和延伸建立一个新的物流配送网络的模型。1 9 4 1 年h i t c h c o c k 提出的运输问题模 型可以描述为：某种物资有若干个产地和销地，若已知各个产地的产量、各个销地的销量以 及各个产地到各个销地的单位运价，问应如何组织调运，才能使总运费最少。 将此问题更具体化，假定有m 个产地，n 个销地。 d 。一第j 产地4 。的供应量，i - 1 , 2 ，聊； b j 一第j 销地b ，的供应量，= 1 , 2 ，z ； 气一从产地f 到销地j f 的单位运费，扣1 , 2 9 1 9 m ，j = 1 , 2 ，聆； x j - 从产地f 到销地物资的调运数量，f = 1 , 2 ，m ，j = 1 , 2 ，刀。 该问题为求解最佳的调运方案，即求解所有的黾的值，使总的运输费用c f 达到 i = 1 j = l 最少，决策变量为x 一 该问题的数学模型的形式为： 所一 o b j ： r a i nz = c f 嘞 ( 公式4 1 ) l = ij = i 嘞= q ，i = 1 2 一，研 j = l 勤= b j ，= l 州2 一，刀 j = l h o ，i = 1 , 2 ，m ；j = 1 , 2 ，刀 1 4 内蒙古大学硕士学位论文 自从h i t c h c o c k 建立了基本的运输问题模型以来，根据不同的物资调运的实际状况对运 输问题进行了推广和变种建立了一些新的物流配送模型：比如在物流配送中需要同时考虑运 输成本最小、运输过程中货物损坏率最低的多个目标，因此，有研究多目标运输问题的数学 模型及其算法【2 0 ，2 1 】；对一些特殊的货物要求在配送时间最短的前提下求得最小成本，因此， 创建了最短时限的运输模型【2 2 2 3 2 4 1 ；对于供给量和需求量在某个区间变化的不确定性的运输 模型的建立【2 5 ，2 6 】；只考虑运输路径的容量限制以及道路使用的手续费的运输模型【2 7 1 。但是当 在物流配送网络中加入配送中心，同时运输路径和配送中心的容量都是有限，并且在一定的 限制时间内可扩充的情况下，现有的运输模型就无法对该情况进行求解给出费用最低的运输 策略。对于这种情况需要创建一个新的物流配送网络模型，对该种情况进行求解给出费用最 低的运输策略。 在物流配送网络中加入配送中心，不是像运输问题那样直接从供应地运输到目的地，而 是要经过配送中心，再由配送中心来实现物资的转运、分类、加工等一系列功能再从配送中 心发往各个目的地。带有配送中心的物流配送网络