（计算机应用技术专业论文）优化物流中心配送方案的模型及算法设计.pdf

摘要 物流中心配送有着很强的应用背景，合理进行物流配送是实现运输规模经 济、节省运输费用的重要手段。本文主要研究了目标函数是最小化费用的物流中 心配送问题及其近优算法一遗传算法和免疫算法。 本文首先对现代物流进行概述，指出货物配送是物流的核心环节。运输分为 合理运输和不合理运输，其中推行配送制是组织合理运输的主要措施之一。本文 深入研究了配送问题的理论，并对配送问题及相关问题进行综述，并在一些模型 的假设下，建立了货物配送问题的数学模型。 对于上面所建立的货物配送问题的数学模型直接对其进行求解是相当困难 的，而我们可以虚拟一个运输网络，将原问题转化为一个带时间约束、能力约束 的最短路径问题，然而，对于虚拟后的网络，可能会有多余的节点，如果把这些 多余节点去掉，可以在很大程度上降低问题的复杂性，所以首先对这样虚拟的网 络进行优化。 为了有效解决此类优化后的问题，本文提出并实现了货物配送问题的遗传算 法。该算法与货物配送问题相结合，构造了染色体的适值函数；遗传操作采用两 点交叉和换位变异。结果表明，该算法能够有效的解决此类问题。 本文最后提出并实现了货物配送问题的免疫算法。该算法抗体采用序数编 码，采用合适的抗体与抗原的亲和力，构造了合适的抗体浓度和抗体生存力计算 方法。通过记忆细胞对那些与记忆细胞有较高亲和力的抗体产生抑制作用，使它 们的生存力降低。从而保证免疫算法不会陷入局部最优解。最后结果表明，该算 法也能够有效的解决此类问题。 关键词：物流配送虚拟网络优化遗传算法免疫算法 a b s t r a c t t h ed i s t r i b u t i o no fl o g i s t i c sc e n t e rh a sm u c hw i d ea p p l y i n gb a c k g r o u n d t h a tt h e d i s t r i b u t i o no fl o g i s t i c s p r o c e e d sr e a s o n a b l y i s i m p o r t a n tm e a n so fr e a l i z i n g t r a n s p o r t a t i o n s c a l e e c o n o m y a n d s a v i n gt r a n s p o r t a t i o nc o s t t h ed i s s e r t a t i o n c o n s i d e r st h ed i s t r i b u t i o no fl o g i s t i c sc e n t e rp r o b l e mw h i c ht h eo b j e c t i v ei st o m i n i m i z et h et r a n s p o r t a t i o nc o s ta n dd e v e l o p st h en e a r l yo p t i m i z a t i o na l g o r i t b m g e n e t i ca l g o r i t h ma n di m m u n ea l g o r i t h m f i r s tt h ed i s s e r t a t i o ns u m m a r i z e st h ep r e s e n tg e n e r a t i o np h y s i c a ld i s t r i b u t i o na n d p o i n t so u tt h a td i s t r i b u t i o no fl o g i s t i c si st h en u c l e a rl i n ko fp h y s i c a ld i s t r i b u t i o n 。sk e y e l e m e n t s t r a n s p o r t a t i o ni sd i v i d e di n t or e a s o n a b l et r a n s p o r t a t i o na n dr e a s o n l e s s t r a n s p o r t a t i o n d e l i v e r y sc a r r y i n go u ti so n eo ft h em a i nm e a s u r e so fr e a s o n a b l e t r a n s p o r t a t i o n t h ed i s s e r t a t i o nr e s e a r c h e sd e e p l yt h ed e l i v e r yp r o b l e m sb a s i ct h e o r y a n dg i v e sa no v e r v i e wo ft h ei i t e r a t u r ea b o u tt h er e s e a r c h e so f d e l i v c r yp r o b l e ma n s o m er e l a t e dp r o b l e m ，a n du n d e rs o m em o d e l a s s u m p t i o n ，d e v e l o p st h em a t h e m a t i c a t m o d e lo ft h ed i s t r i b u t i o no fl o g i s t i c sc e n t e rp r o b l e m i ti sv e r yd i f f i c u l tt os o l v et h em a t h e m a t i c a lm o d e lo ft h ed i s t r i b u t i o no fl o g i s t i c s c e n t e rp r o b l e md i r e c t l y , b u tw ec a nc o n s t r u c tad u m m yt r a n s p o r t i n gn e t w o r k ，a n d t r a n s f o r mt h ef o r m e rp r o b l e mi n t os h o r t e s tp a t hp r o b l e mw i t ht i m ec o n s t r a i n ta n d c a p a c i t yc o n s t r a i n t ，h o w e v e r , t h e r em a y b em a n ye x t r an o d e si nt h ed u m m yn e t w o r k , w h i c hw i l lm a k et h ec o m p u t em o r ec o m p l i c a t e d w ec a l lt h r o wo f ft h ee x t r an o d e st o r e d u c et h ec o m p l i c a t i o no ft h ep r o b l e ms of n s tw eo p t i m i z et h ed u m m yn e t w o r k f o rs o l v i n gt h i sp r o b l e ma f t e ro p t i m i z i n ge f f i c i e n t l y , g e n e t i ca l g o r i t h mw h i c h s o l v e st h ed i s t r i b u t i o no fl o g i s t i c sc e n t e rp r o b l e mi sp r o p o s e da n da c c o m p l i s h e di nt h e d i s s e r t a t i o n t h ea l g o r i t h mi sc o m b i n e dw i t ht h ed i s t r i b u t i o no fl o g i s t i c sc e n t e r p r o b l e m ，a n dc o n s t r u c t sf i t n e s sf u n c t i o no fc h r o m o s o m e ；i n h e r i to p e r a t i o nu s e st w o p o i n t s c r o s s o v e ra n dt r a n s p o s i t i o nv a r i a t i o n t h er e s u l ti n d i c a t e st h a tt h ea l g o r i t h m 啪s o l v et h ep r o b l e me f f i c i e n t l y t h ei m m u n ea l g o r i t h mo ft h ed i s t r i b u t i o no fl o g i s t i c sc e n t e rp r o b l e mi sp r o p o s e da t l a s t t h ea l g o r i t h m a n t i b o d yu s e so r d i n a ln u m b e rc o d i n ga n da p p r o p r i a t ea f f i n i t yo f a n t i b o d ya n da n t i g e n t h ed i s s e r t a t i o ng i v e sa p p r o p r i a t ec a l c u l a t em e t h o do ft h e a n t i b o d yc h r o m a w er e d u c et h es u r v i v a lc a p a b i h t yo ft h ec e l l sw h i c hh a v eh i g h a f f i n i t yw i l j lm e m o r yc e l l sb yr e s t r a i nf u n c t i o no fm e m o r yc e l l s t h ea l g o r i t h mc a n m a k es i l r et h a tt h er e s u l to ft h ep r o b l e mn o tg e t si n t ol o c a lb e s tr e s u l t a tl a s tt h e r e s u l ti n d i c a t e st h a tt h ea l g o r i t h mc a ns o l v et h ep r o b l e me f f i c i e n t l y k e yw o r d s ：p h y s i c a ld i s t r i b u t i o nd u m m yn e t w o r ko p t i m i z a t i o n g e n e t i ca l g o r i t h m i m m u n ea l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得云 洼堡王太堂 或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 学位论文作者签龟。签字日期：。f 年1 ，月谣日 弓细j 、 。 学位论文版权使用授权书 本学位论文作者完全了解丞洼堡王塞堂有关保留、使用学位 论文的规定。特授权云洼理王盍堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手 段保存、汇编，以供查阅和借阅。同意学校向国家有关部门或机构送 交论文的复本和电子文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 7 督棚飞。 签字目期：痧年i _ 1 - f i 朋日 导师签名：了，仑埘4 ， v 签字日期：d ，4 年f t 月l i 日 第一章绪论 第一章绪论 本章首先对现代物流进行概述，指出运输是物流的核心环节。运输分为合理 运输和不合理运输，本章接着介绍了合理运输的定义及组织合理运输的主要措 施，指出推行配送制是组织合理运输的主要措施之一，并对推行配送制的意义加 以分析。 1 1 现代物流的概述 1 1 1 物流的概念及作用 物流，泛指物质资料从供给者向需要者的物理性转移，是创造时问效用和空 间效用的经济活动。物流存在于生产、流通和消费领域，是一个范围很广的概念。 物流这一概念可分为狭义和广义两种情况。狭义的物流，仅指作为商品的物质资 料，在生产者与消费者之间发生的空间位移，它属于流通领域内的经济活动。广 义的物流，除此之外，还包括物质资料在生产过程中的活动，它既包括流通领域 又包括生产领域。根据物流活动的范围和业务性质，以及我国的实际情况，物流 由生产物流、供应物流、销售物流、回收、和废弃物流四部分构成”j 。 物流产业作为国民经济中一个新兴的服务行业，正在全球迅速发展。在国际 上，物流产业被认为是国民经济发展的动脉和基础产业，其发展程度称为衡量一 个国家现代化程度和综合国力的重要标志之一。被喻为促进经济发展的“加速 器”。物流在国民经济中的重要作用主要表现在：物流是国民经济的动脉系统： 物流是生产过程不断进行的前提条件；物流是保持商流顺畅进行，实现商品价值 和使用价值的物质基础；物流技术的发展是决定商品生产规模和产业结构变化的 重要因素；物流合理化是提高宏观经济效益和微观经济效益的熏要源泉1 2 j 。研究 物流的现实目的在于，通过综合运用科学技术手段和组织管理方法，来降低物流 流程的广义成本，从而提高商品生产和流通的效率及经济效益。 1 1 2 现代物流研究的主要任务 从现代物流的发展轨迹看，物流是一门在不同时代承担着不同要求和任务的 科学。6 0 年代，作为现代物流学起源地的日本，社会化生产的规模不断扩大， 生产成本以每年2 的增长率上升，反映出社会的物流系统已经满足不了产品数 量急剧增大的需求，降低物流成本是这一阶段物流研究及管理的主要内容。 第一章绪论 随着国民经济水平的发展，社会生活逐步改善，人们越来越追求个性化，产 品样式也越来越丰富多彩。商品的品种、小批量化使得整个物流活动更加复杂， 提高服务的质量，成了物流的主题。 近年来，电子商务在发达国家获得飞速发展，中国的电子商务也越来越热， 这种依托互联网的信息技术向社会物流提出了新的挑战。例如，人们亲自到商场 购物，可能会花上几个小时的时间和几元钱的交通费，网上购物也许可以轻轻一 点，几秒钟成交，但如果货送到家中，需要等几天甚至几十天，另外，还要在商 品价格上多付上十几元的“物流费用”，那么电子商务的便捷性就会大打折扣。 电子商务的全过程是一个闭环，各个环节缺一不可，配送不周，功亏一篑。因此， 如何保证物流系统运转的高效率，最大限度地“追赶”上电予的速度，是现代物 流系统研究的新任务例。 1 2 合理运输的组织 1 2 1 合理运输的定义 所谓合理运输，是指在实现社会产销联系的过程中，选取运距短、运力省、 运费低、速度快的最佳运输路径和运输方式所组织的货物运输。组织合理运输， 不仅可以节省运输能力，挖掘运输潜力，发挥各种运输方式的优势，提高运输效 率，而且可减少货物的中转环节和装卸次数，减少货物损耗，缩短货物在途时间， 加速货物周转，节省运输费用，提高社会经济效益。合理的生产力布局和运输网 配置，是保证合理运输的基础1 4 j 。 1 2 2 组织台理运输的主要措施 为了组织合理运输，在生产力布局和运输网配置既定的条件下所应采取的主 要措施【4 j ： 1 、首先应提高对组织合理运输重要意义的认识。运输费用在商品流通费用 中占有很大比例，组织合理运输是节约运输费用的有效措施。特别是在我国幅员 辽阔、生产力布局不合理、运距较远、运输力紧张的情况下，合理运输是一个永 久性课题。 2 、改革流通体制，实现流通社会化。 3 、按照合理流向组织运输。 4 、建立合理的运价制度。 5 、正确选择运输方式和运输种类。 6 、发展集装单元化运输。 2 第一章绪论 7 、推行物资配送制等。 1 3 配送问题及其研究状况 自从人类社会有了商品交换，就有了物流活动( 如运输、仓储、装卸搬运等) 。 而将物流作为- - n 科学，从系统的角度和观点来研究。却仅有几十年的历史。物 流概念的提出，最早始于美国，2 0 世纪3 0 年代初，美国使用了“p h y s i c , a l d i s t r i b u t i o n ”一词，建成“p d ”，直译为“实物配送”。除此之外，还使用了“企 业后勤”( b u s i n e s sl o g i s t i c s ) 和“后勤管理”( l o g i s t i c sm a n a g e m e n t ) 等用语。 在二战末期，如何组织军需品的供给，各供应基地、中间基地、前线供应点的合 理配置，如何确定最佳的运输路线以最大限度的减少浪费，降低军费开支。形成 了一系列综合性的研究课题。军需品供应不足，将影响到战争的成败，若供应过 量则会造成浪费。为了合理解决这些问题，美国军事部门运用运筹学和电子计算 机技术进行了科学研究，较好地解决了这一问题。这就是物流科学的萌芽阶副研。 5 0 年代，随着经济的复苏和生产的发展，产品数量急剧增长，生产成本相对 下降，而流通成本有相对上升的趋势。于是，人们开始对各种物流活动的规律进 行认真的研究，以图找出降低流通费用的途径。由于目标是降低整个流通过程盼 费用，因此，必须考察和研究物流的全过程，日口整个物流系统。研究物流系统内 各个环节之间的相互关系，从而使原来处于潜隐状态的物流系统显现出来。并开 始以物流系统为中心开展研究活动，从而形成了现代物流科学。 货物运输是物流的主题，而配送又是组织合理运输的重要内容，是一个小范 围的物流系统，是物流系统中由运输派生出的功能。1 9 6 4 年克拉克( c l a r k e ) 和 怀特( w r j i g h t ) 发表了制定配送计划的节约法论文，首次提出了如何从多条路径 中，选出最佳配送路径的方法【4 】。 近一二十年，随着科学技术的不断进步和新技术的开发及广泛应用，配送拽 术也日趋现代化。从世界范围来看，目前，在配送作业中以托盘化、集装箱化为 代表的集装系统已经普遍建立了起来，由此大大提高了配送作业中的装卸和运输 效率。 近几年，在欧美和日本，配送作业相继采用了自动分拣技术和自动配货技术， 并相应建立了自动化的操作系统，如：由高层货架、流动货架、自动取货机、传 送带、图像识别机、计算机等组合而成的自动化配送系统。在日本，许多企业在 编制配送计划及推行计划配送时，进一步应用了更为先进的v s p 方法。所谓的 v s p 方法系国际商用电子计算机公司研制成功的计算机软件。据介绍，应用v s p 设计运输计划，有如下功效：从几个配送据点向多家客户发送货物时，只要向计 算机输入现有车辆台数、所需时间、运距和货物需要量等数据，它便能输出效率 最高的送货路线和必须配备的车辆台数。 配送在我国豹发展是近十几年的事，进展缓慢、设备落后、信息化程度低是 目前的一个基本状况。具体表现在：配送规模小，物流网点没有统一布局；配送 3 第一章绪论 中心现代化程度低，机械化水平程度低，整体物流技术水平比较落后；配送中心 功能不健全，其中的信息没有得到充分的加工和利用，离信息化还有很大差距等 等。 技术是我国配送发展滞后的一个重要因素。目前国内的配送中心的计算机应 用程度仍比较低，大多情况下，仍只限于日常事务管理，对于物流中的许多重要 决策问题，如配送中心的选址、货物组配方案、运输的最佳路径、最优库存控制 等方面，还处于半人工化决策状态，适应具体操作的物流信息系统的开发滞后： 物流设施的技术和设备都比较陈旧，与国外已机电一体化、无纸化为特征的配送 自动化、现代化相比，差距很大；整体物流技术如运输技术、储存保管技术、流 通加工技术，以及与每个环节都密切相关的信息处理技术等，也都比较落后【5 】。 综上，目前对于配送相关的问题算法方面的研究很多，各种文献层出不穷， 但是完全针对配送问题算法方面的研究却很少。因此，针对这一现状本文提出并 实现了求解配送问题的遗传算法和免疫算法。 4 第二章配送问题的基本理论和数学基础 第二章配送问题的基本理论和数学基础 配送，作为一项特殊、综合性的物流运动，其运行和发展有着深刻的社会根 源和特殊的历史背景。从根本上讲，配送活动的普遍开展是社会化大生产的客观 要求，也是生产力发展的必然结果。 2 1 配送的基本概念 2 1 1 配送的定义 配送属于物流范畴，它是一种特殊的、带有现代化色彩的物流运动。配送 一词是中文对英文“d e l i v e r y ”的意译，是从日语中直接引用到我国流通界来的。 用最通俗的话来说就是既配又送。其中的“配”包括货物的分拣和配货等活动； “送”则泛指各种送货方式和送货行为。按照我国国家质量技术监督局发布的中 华人民共和国国家标准“物流术语”，其中关于配送的解释为：在经济合理区域 范围内，根据用户的要求，对物品进行拣选、加工、包装、分割、组配等作业， 并按时送达指定地点的物流活动。 在流通实践中，通常人们在城市( 或地区) 范围内从事配送活动，因而在某 些书籍中，配送常被说成是城市内的短距离运输。实际上，在某些交通条件较好， 交通发达、货物运输能力和组织能力较强的国家( 尤其是从事转口贸易的国家或 地区) ，配送的活动范密早已超出了城市界限。当前，“国际配送”已不再是个别 现象和个别行为。据此，不能把货物空间转移的距离长短作为区分一般运输和配 送的标准，亦即不能把配送视为“短距离、小批量”的送货活动。配送本身并不 限定距离。应当说，跨越国界的、长距离、大批量的货物配装和运送等活动同样 属于配送范畴。 此外，从配送对象来看，收货人可能是最终消费者( 如原材料配送) ，也可 能是批发商和零售店。日用消费品的配送对象往往是零售商店而不是居民个人。 在现实生活中，有不少生产资料( 原材料产品) 也经常配送到零售店( 专卖店) 。 据此，不能把配送理解为向最终消费者( 或称用户) 送货的经济活动；配送包含 着向中间商送货活动。 2 1 2 配送的特征 从以上配送的定义可以看出，配送活动具有以下几个基本的特征： 5 第二章配送问题的基本理论和数学基础 1 、配送不仅仅是送货，是流通加工、整理、拣选、分类、配货、末端运输 等一系列活动的有机结合。 2 、配送的全过程有现代化技术和装备的支持与保证。 3 、配送是一种专业化的分工方式。 4 、配送活动不仅仅是物流活动的终结环节，而且是营销或促销活动的重要 手段。 2 1 3 配送的分类 配送在长期的实践中以不同豹运作特点和形式满足不同的顾客需求，形成 不同的配送形式。按照配送的主体不同来分，可以把配送分为配送中心配送、仓 库配送、商店配送、生产企业配送；按照配送时间及数量的不同，可分为定时配 送、定量配送，定时定量葬己送、定时定量定点配送、定时定路线配送、即时配送、 快递配送；按照配送商品种类及数量不同，可分为少品种大批量配送、多品种少 批量配送、配套( 成套) 配送：按照配送企业专业化程度，分为综合配送、专业 配送。 2 1 4 推行配送制的意义 最近一二十年，配送制的实行范围已经扩大到了很多国家和地区。在发达国 家，配送不但广为实行，而且早已成为企业经营括动的重要组成部分。之所以会 出现这样的景象，原因之一就是：在社会再生产活动中，配送有其特殊功能：推 行配送能够优化经济结构、节约社会劳动及充分发挥物流的作用。就流通本身而 言，实行配送制则有益于物流运动快速发展嘲。具体如下； 1 推行配送有益于物流运动实现合理化。在现代社会，物流运动朝着科学 化、合理化方向发展乃是社会大生产发展的客观要求。从市场竞争的角度去分析 问题，物流科学化和合理化也是物流发展的必然趋势。物流合理化是指“维持合 理的物流结构”。“也就是说，实现低成本的物流结构”这种看法实际上是把效益 指标作为评价物流运动合理与否的客观标准。此外，物流合理化还包括这样一些 内容：其一，物流运动是一种建立在分工、协作关系基础上的社会化、专业化的 经济运动。其二，物流运动是一项“规模经济”运动，其总体运动及其效果均应 里现最佳状态，达到最高水平。经验证明，要想使物流运动达到上述标准，除了 要不断地发展生产力、改进物流技术以外，尚须按照发展社会化大生产的要求改 革流通体制，推行科学、先进的流通方式。而推行配送制实际上就是体制改革的 一项重要内容。作为一种物流方式( 或物流体制) ，配送不仅能够把流通推上专 业化、社会化道路，更重要的是，它能以其特有的运动形态和优势调整流通结构， 6 第二章配送问题的基本理论和数学基础 使物流运动演化为“规模经济”运动。要知道，配送的基本特点之一就是：运动 带有社会性。亦即：其运行是一种社会型的经济运动。从形态上看，则是以集中 的、完善的送货取代分散性、单一性的取货。在资源配置方面，配送则表现为 以专业组织的库存( 集中库存) 代替社会上的零散库存。很明显，采用这种方式 衔接产需关系，客观上可以打破流通分割和封锁的格局，改变家家户户设仓库及 流通分散的落后状态，进而能够很好的满足社会大生产的发展需要。从理论上说： 以集中社会劳动的方式来调整库存结构，改变分散和分割的流通格局，在此基础 上形成规模经济运动，实际上就是促使流通领域中的小生产方式向社会大生产方 式转化。从这个意义上说，配送是实现流通社会化、现代化的重要手段。推行配 送制可以形成高效率和高效益、从而形成合理化的流通格局。 2 推行配送制有利于合理配置资源。由于实施配送可以做到以配送企业的库 存取代社会上千家万户的零散库存，或者说，可以使库存相对集中，因此，有条 件、也有可能按照统一计划合理分配和使用资源，做到物尽其能。 此外，考虑到配送的运行效果( 即客观上能够改变仓储、运输分散的格局， 使库存和运力相对集中) ，实施配送，又有益于建立起合理的库存结构和运输结 构，进而能够提高物流设施的利用率和物流设备的工作效率( 据有关资料介绍， 在库存、运输结构分散的状态下，就汽车而言，汽车的货物实载率一般都比较低， 有的只有2 5 ，而在结构合理、运力集中的状态下，车辆的货物实载率可提高到 7 0 一8 0 ) 。显然，这也是资源配置合理化的一种表现。 3 推行配送制有利于开发和应用新技术，从而能够促进科学技术不断进步。 在现代社会，随着生产规模的不断扩大和市场容量的不断增加，配送的规模也在 相应扩大。在这样的形势下，用于配送的各种设备和设施，不但数量会越来越多， 而且其技术含量、技术水平也在不断提高。 在流通实践中，配送的实行既贯穿着技术( 包括管理技术) 的更新和设施、 设备的改造过程，从而必须依靠科学技术的进步来支撑；同时，配送的完善和不 断发展又为高新技术的开发与应用提供了良机。从这个意义上说，配送在一定程 度上可以起到促进科技进步的作用。 4 推行配送可以降低物流成本，可以促进生产快速发展。 降低物流成本有两重含义：其一，减少单项物流( 如仓储、运输等单项活动) 的投入，使z 物耗降低、费用减少。其二，减少物流整体运动运动的劳动消耗和 费用支出。推行配送不仅可以优化库存结构和运输结构，从而可以提高设备、设 施的利用率，而且能够大大降低物流成本和生产成本。这是因为：各种流通要素 相对集中，有益于开展规模经营活动。此外，流通的物质要素相对集中，也便于 合理安排各环节上的物流活动，使总体运动协调一致，最终会减少物流镁域内的 劳动消耗和费用支出。 配送的优势不仅表现在供应方面，同时也表现在库存结构的改变方面。而改 变库存结构、使之趋于科学合理，则意味着以总量较低的“集中库存”( 专业配 送组织的库存) 取代总量( 总合) 较高的“分散库存”( 指分散于各个用户的库 第二章配送问题的基本理论和数学基础 存总合) ，显然，发生这种变化，不但降低了物流总成本( 表现为减少了资金占 用、降低了物耗) ，而且优化了生产领域的资金结构，减少了企业储备的占用量， 进而可以起到降低生产成本、促进生产快速发展的作用。 5 推行配送能够充分发挥专业流通组织的综合优势，能够有效地解决交通问 题。从经济效益的角度来看，这种以配送作为媒介而形成的一体化运动较之各个 专业企业独立运作更能够发挥流通组织的攘体优势和综合优势。正因为在现实生 活中，通过推行配送制，客观上能够使社会上某些分散的经营活动协调运作，也 正因为配送有调整运输结构和集中运力的功能，因此，推行配送制又有助于解决 交通问题。具体说就是：通过实行配送，可以减少社会范围内的迂回运输、交叉 运输、重复运输等现象，由此，有助于缓解城市道路交通矛盾，解决交通拥挤问 题，还能减少运输费用。 过去，由于我国物流行业社会化程度低、条块分割严重，物流企业的规模 效益难以实现，普遍存在损失率大、资金沉淀严重，技术手段落后等问题，远不 能达到高效率、低成本、柔性化等要求。随着商品交易的电子化，电子商务的出 现给我国物流配送行业开辟出了巨大的市场空间，但同时，物流业成为制约电子 商务发展的一个主要瓶颈。著名物流专家王之泰教授指出，物流配送是影响中国 经济发展的一个重要因素。建立现代化的物流企业，除了要解决观念、体制等方 面的问题，信息技术的应用是关键。物流的灵魂是系统，系统的灵魂在于软件。 尤其是影响电子商务发展的城市物流配送行业，是当前急需采用信息技术的关键h 环节。应大力推进信息技术在城市物流领域的应用，发展中国自己的物流信息技! 术，避免中国的物流技术受制于人1 5 1 。由此可见，配送问题具有很强的使用价值 和一定的复杂程度，因此，对它的研究有重要的理论和实际意义。本文的工作就 是在充分了解配送问题的基础上，以最小化运输费用作为目标函数，展开对这一 问题的理论和方法的深入研究。 2 2 配送基本环节和流程 2 2 1 配送的基本环节 从总体上看，配货是由各货、理货和送货等三个基本环节组成的。其中每个 环节又包含着若干项具体的、支节性的活动。详细内容分述如下： ( - - ) 备货 备货即指准备货物的系列活动，它是配送的基础环节。严格说来，备货应当 包括两项具体活动：筹集货物和储存货物。 在不同的经济体制下，筹集货物( 或者说组织货源) 是由不同的行为主体去 完成的。若生产企业直接进行配送，那么，筹集货物的工作自然是由企业( 生产 者) 自己去组织的；而在专业化流通体制下，组织货源和筹集货物的工作则会出 8 第二章配送问题的基本理论和数学基础 现两种情况：其一，由提供配送服务的配送企业直击承担。一般是指通过向生产 企业订货和购货完成此项工作。其二，选择商流、物流分开的模式进行配送，订 货、购货等筹集货物的工作通常是由货主( 如生产企业) 自己去做，配送组织只 负责进货和集货( 集中货物) 等工作，货物所有权属于事主( 接受配送服务的需 求者) 。然而，不管具体做法怎样不同，就总体活动而言，筹集货物都是由订货 ( 或购货) 、进货、集贷及相关的验货、结算等一系列活动组成的。 储存货物是购货、迸货活动的延续。在配送活动中，货物存储有两种表现形 态：一种是暂存形态；另一种是储备( 包括保险储备和周转储备) 形态。1 暂 存形态的存储是指：按照分拣、配货工序要求，在理货场地储存少量货物。这种 形态的货物储存是为了适应“日配”、“即时配送”需要而设置的，其数量多少对 下一个环节的工作方便于否会产生很大影响。但不会影响储存活动的总体效益。 2 储备形态的储存是按照一定时期配送活动要求和根据货源的到期情况( 到货 周期) 有计划的确定，它是使配送持续运作的资源保证。如上所述，用于支持配 送的货物的货物储备有两种具体形态：周转储备和保险储备。然而不管是哪一种 形态的储备，相对来说，数量都比较多。据此，货物储备合理与否，会直接影响 配送的整体效益。 以上所讲的备货是决定配送成败与否、规模大小豹最基础的环节。同时，他 也好似决定配送效益高低的多穹键环节。如果各货不及时或不合理，成本较高，那 么，就会大大降低配送得整体效益。 ( 二) 理货 理货是配送的一项重要内容，也是配送区别于一般送活的重要标志。理货包 括货物分拣、配货和包装等项经济活动。 货物分拣采用适当的方式和手段，从储存的货物中分出( 或拣选) 用户所需 要的货物，此活动称为分拣。分拣货物一般采取两种方式来操作：其一是摘取式； 其二是播种式。所谓的摘取式分拣，就是像在果园中摘果子那样去拣选货物。具 体做法是：作业人员拉着集货箱( 或称分拣箱) 在排列整齐的仓库货架间巡回走 动，按照配送单上所列的品种、规格、数量等将客户所需要的货物拣出及装入集 货箱内。在一般情况下，每次拣选值为一个客户配装。在特殊情况下，也可以为 两个以上的客户配装。目前，由于推广和应用了自动化分拣技术，装配了自动化 分拣设施等，大大提高了分拣作业的劳动效率。 播种式分拣货物形似于田野中的播种操作。其做法是：将数量较多的同种货 物集中运到发货场，然后，根据每个货位货物的发送量分别取出货物，并分别投 放到每个代表用户的货位上，直至配货完毕。为了完好无损的运送货物和便于识 别配备好的货物，有些经过分拣、配备好的货物尚需重新包装。并且要在包装物 上贴上标签，记载货物的品种、数量、收货人的姓名、地址及运抵时间等。 ( 三) 送货( 发送) 送货是配送活动的核心。也是备货和理货工序的伸延。在物流运动中，送货 的现象实际上就是货物的运输( 或运送) ，因此，常常以运输代表送货。但是， 第二章配送问题的基本理论和数学基础 组成配送活动的运输( 有人称之为“配送运输”) 与通常所讲的“干线运输”是 有很大区别的：前者多表现为按适用户的“末端运输”和短距离运输，并且运输 的次数比较多；后者多为长距离运输( “一次运输”) 。由于配送中的送货( 或运 输) 须面对众多的客户，并且要多方向运动，因此，在送货过程中，常常进行三 种选择：运输方式、运输路线和运输工具的选择。按照配送合理化的要求，必绥 在全面计划的基础上，制定科学的、距离较短的货运路线，选择经济、迅速、安 全的运输方式和选用适宜的运输工具。通常，配送中的送货( 或运输) 都把汽车 ( 包括专用车) 作为主要的运输工具。 ( 四) 流通加工 在配送过程中；根据用户要求或配送对象( 产品) 的特点，有时需要在未配 货之前先对货物进行加工( 如t 钢材剪切、术材截锯等) ，以提高配送质量、更 好得满足用户需要。融合在配送中的货物加工是流通加工的一种特殊形式。其主 要目的是使配送的货物完全适合用户的需要和提高资源的利用率1 5 1 。 2 3 组合最优化问题 组合最优化研究那些含有有限个可行解的优化问题。在日常生活中，特别是 在工程实际应用中，有许多这样的问题。这其中有一个重要并且普遍的应用领域 就是考虑如何有效利用稀缺的资源来提高生产效益。典型的工程设计问题包括集 覆盖、装箱、背包、二次分配、确定最小生成树、机器调度排序与平衡、制造元 设计、车辆路径、网络密度、设备定位与布局、旅行推销员分配等。配送问题本 身也可以归结为组合最优化问题，在此，对组合最优化问题及其算法研究作一简 单概述f 6 l 。 根据不同原则对组合最优化问题进行分类，常见分类有如下形式： ( 1 ) 按目标函数和约束条件的类型，可分为线形和非线性的组合最优化问题。 ( 2 ) 按目标函数的个数，可分为单目标优化和多目标优化问蹶。 ( 3 ) 按决策变量的取值，可分为整数规划和非整数规划。 求解组合最优化闯题的算法渊源已久，自从d a n t z i g 在1 9 4 9 年提出了著名 的求解线性规划问题的单纯形法之后，就发现线性规划也能解决像运输问题这样 的整数规划问题。g o m o r y 对求解线性整数规划问题作出了开创性工作，于1 9 5 8 年提出了著名的割平面法，并带动了其他学者投身于线性整数规划算法的研究之 中。l a n d 和d o i n g 合作，于1 9 6 0 年开发出分支定界法，b a l a s 于1 9 6 5 年提出了 求解0 - 1 规划枚举法。可以说这三种方法构成了求解整数线性规划方法的基础。 此后在这方匾的研究成果基本上是对这三种方法的改进和扩展。这些方法均是精 确算法，即总能保证求得问题的全局最优解，这是它们的最大优势，其不足之处 在于计算量偏大，因此均受到求解问题规模的限制，通常它们求解问题的规模是 很小的。 由于社会生活和社会实际的需要以及计算机技术的迅速发展，是大规模的计 1 0 第二章配送问题的基本理论和数学基础 算成为可能，加速了组合最优化的发展，在7 0 年代初期，c o o k 提出了计算复杂 性理论，并证明了很大一类组合最优化问题的求解难度是相同的。特别是在一些 组合最优化问题被证明是n p 一完备的之后，寻找收敛于全局最优解的精确算法 相当困难。正是在这种背景下，遗传算法、模拟退火和禁忌搜索算法等智能优化 算法相继问世。为求解组合最优化问题提供新的途径。经过几十年的改进和发展， 日臻完善，并在实际中发挥着越来越大的作用。 配送问题的功能要素有：备货；储存；分拣及配货；配装；配送运输；送达 服务；配送加工。其中，配装问题可以建模为背包或装箱问题：配送运输问题可 以建模为车辆路径问题或旅行商问题。 二、背包问题 背包问题的一般提法是：已知n 个物品的重量及其价值分别为m ) o 和c i ，0 ( i = l ，2 ，n ) 如何选择哪些物品装入该背包可使得在背包的容量约束限制 之内所装物品的总价值最大? 前1 0 年，背包问题是一个典型的n p 完全难题，对该问题求解方法的研究 无论是在理论上，还是在实践中都具有一定的意义，如管理中的资源分配、投资 决策、装载问题等均可建模为背包问题。由于背包问题是整数0 1 线性规划问 题，可以用许多算法求解，此外，k o l e s a r 提出了求解该问题的分支定界算法。 背包问题的近似求解算法主要是一些启发式算法( 如贪婪算法) ，也可以用遗传 算法来求解该问题。 三、装箱问题 装箱问题的一般提法如下：设有n 个物品h ，如，“。要装箱发送，已知每个 物品的体积为k u , ) e ( q 1 1 ，( f 一1 2 ，i ) 现规定每个箱子的容量为1 ，问如何确定装箱 方案可是的装完这n 个物品所需要用的箱子数目为最少? 管理工程、工业工程等领域中的一些问题，如人力资源分配、运输计划等均 可建模为装箱问题，对其求解方法的研究具有一定应用价值。从计算的复杂性理 论来讲，装箱问题是一个n p 完全问题，很难精确求解。目前的求解方法主要是 一些近似算法，如n f ( n e x tf i t ) 近似算法、f f ( f i s tf i t ) 近似算法，f f d ( f i r s t f i td e c r e a s i n g ) 近似算法及由简单遗传算法和f f d 近似算法组成的混合遗传算 法。 四、旅行商问题 旅行商问题一般描述为：已知n 个城市之间的相互距离，现有一推销员必须 遍访这n 个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何 安排他对这些城市的访问次序，可使其旅行路线的总长度最短。 旅行商问题是一个典型的、易于描述却难于处理的n p 完全问题，其可能的 路径数目与城市数目r l 是呈指数增长的，所以一般很难精确求解出其最优解，因 而寻找其有效的近似求解算法具有重要的理论意义。另一方面，很多实际应用问 题，如印制电路板的钻孔路线方案、连锁店的配送路线等，经过简化处理后，均 可建模为旅行商问题，因而对旅行商问题求解方法的研究也具有重要的应用价 第二章配送问题的基本理论和数学基础 值。求解旅行商问题的近似算法有：插入算法、最近邻算法、c l a r k e & w r i g h t 算 法、双生成树算法、c h d s t o f i d c s 算法、混合算法、概率算法、神经网络算法、 模拟退火算法、遗传算法等。由于旅行商问题展示了组合优化的所有方面，它 已经成为测试新算法的标准问题，如模拟退火、禁忌搜索、神经网络以及进化方 法等都用它来测试。 五、车辆路径问题 车辆路径问题的一般描述如下：有1 个货物需求点( 或称顾客) ，已知每个 需求点的需求量及位置，至多用k 辆汽车从中心仓库( 或配送中心) 到达这批 需求点，每辆汽车载重量一定，安排汽车路线是运距最短且满足每条路线不超过 汽车载重量和每个需求点的需求必须且由一辆汽车来满足的约束条件。车辆路线 安排问题是一个n p 完全问题，只有在需求点数和路段数较少时才有可能寻求其 精确解。只能用启发式算法和现代优化算法对其求解。 第三章物流中心配送问题数学模型的建立 第三章物流中心配送问题数学模型的建立 通过前面对物流配送基本理论的深入研究，本章建立了物流中心配送的数学 模型。本章主要工作为：首先给出问题的描述，然后对模型作了一些假设，最后， 在模型假设的基础上，建立了物流中心配送的数学模型。 3 1 引言 通过前蘧对配送基本理论的深入研究可知，配送的基本环节为：备货、理货、 送货、流通加工。其中，送货是配送活动的核心，也是各货和理货工序的延伸。 本章所提出的物流中心配送问题即是指配送环节中的送货问题。配送环节中的遴 货问题实际上包含配装、运输和交货三项活动：( 一) 配装是在单个客户配送数 量不能达到车辆的有效载运负荷时，就存在如何集中不同客户的配送货物。进行 搭配装在以充分利用运能、运力的问题，这就需要配装；和一般送货不同之处在 于，通过配装送货可以实现运输规模经济，大大提高送货水平及降低送贷成本， 所以，配装是配送系统中有现代特点的功能要素，也是现代配送不同于以往送货 的重要区别之处。( 二) 配送运输。配送运输属于运输中的末端运输、支线运输， 和一般运输形态主要区别在于：配送运输是较短距离、较小规模、额度较高的运 输形式，一般使