（管理科学与工程专业论文）基于遗传算法的物流配送优化研究.pdf

摘要 随着信息技术的飞速发展，电子商务正越来越受到世界各国的关注，并已成 为2 l 世纪经济新的增长点。随着电子商务的进一步推广与应用，物流的重要性对 其影响日益明显，物流配送时间过长、成本过高己成为目前制约我国开展电子商 务的“瓶颈”。论文研究的目的就在于探索物流配送优化的理论和方法，降低物流 成本、优化社会库存配置、提高服务质量，从而提高企业的经济效益及社会效益， 保障电子商务物流系统以适当的规模和速度健康发展。 物流配送是一项复杂的系统工程，其中许多优化问题所建立的模型和算法复 杂，大都具有n p 难性质。论文首先介绍了选题背景及意义，阐述了电子商务和 物流的关系，提出了建设我国电子商务物流配送体系的构想；然后，对物流配送 优化中的两个典型问题配送中心选址和车辆路径优化进行了理论分析，在一 定的假设前提下建立了数学模型，并简单介绍了具有全局随机搜索能力的解决问 题的工具遗传算法；最后，将基本遗传算法在选择、交叉、变异等操作方面 进行了一系列改进，将其用于对物流配送优化问题做一些探索性的工作，进行有 益的尝试和分析。为了检验所提出的改进遗传算法是否有效，编制了c s g a c 和 v r p g ac 源程序，并用两个程序对实际问题进行了实证分析。 通过实证分析的结果可以看出，采用所提出的改进遗传算法能够大大提高整 个算法的收敛速度，从而提供了一条解决与之相关优化问题的有效途径。 关键词：遗传算法配送中心选址车辆路径优化 a b s t r a c t w i t ht h eq u i c kd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，e l e c t r o n i cc o m m e r c e i s g a i n i n gm o r e a n dm o r ea t t e n t i o nw o r l d w i d ea n dh a sb e c o m et h en e wi n c r e a s i r i gp o i n t o f e c o n o m y i nt h e2 1c e n t u r y a l o n gw i t ht h ef u r t h e re x p a n s i o na n d a p p l i c a t i o no f t h e e l e c t r o n i cc o m m e r c e ，t h ei m p o r t a n c ea n di n f l u e n c eo f l o g i s t i c sb e c o m em o r e a n dm o r e o b v i o u s t h e l o n g t i m ea n d h i g h c o s to fl o g i s t i ca l l o c a t i o nh a v eb e c o m et h e “b o t t l e n e c k ”o f t h ee x p a n s i o no f t h ee l e c t r o n i cc o m m e r c ei no u rc o u n t r y t h er e s e a r c h t a r g e to f t h ep a p e ri st oe x p l o r e t h et h e o r i e sa n dm e t h o d st oo p t i m i z el o g i s t i c s ，l o w e r t h el o g i s t i cc o s t ，o p t i m i z et h es o c i a ls t o c ki n s t a l l a t i o n ，i m p r o v et h es e r v i c eq u a n t i t y a n ds e q u e n t i a l l yi n c r e a s ee c o n o m i ca n ds o c i a lb e n e f i to ft h eb u s i n e s se n t e r p r i s ea n d g u a r a n t e e t h eh e a l t h y d e v e l o p m e n to f l o g i s t i cs y s t e mw i t ha p p r o p r i a t es c a l ea n dp a c e t h e l o g i s t i ca l l o c a t i o ni s ac o m p l i c a t e ds y s t e m se n g i n e e r i n g m a n ym o d e l sa n d a l g o r i t h m se s t a b l i s h e dt oo p t i m i z ep r o b l e m sa r ec o m p l e xa n dm o s th a v et h en a t u r eo f n p f i r s t l y ，t h ed i s s e r t a t i o ni n t r o d u c e dt h eb a c k g r o u n da n dm e a n i n g o f s e l e c t i n gt h e t o p i c ，e l a b o r a t e dt h er e l a t i o n s h i p b e t w e e ne l e c t r o n i cc o m m e r c ea n d l o g i s t i c s a n d p r o p o s e dt h ec o n c e p t i o no fb u i l d i n gt h el o g i s t i c sa l l o c a t i o ns y s t e mo fe l e c t r o n i c c o m m e r c ei no u rc o u n t r y ；a r e r w a r d s ，i t t h e o r e t i c a l l ya n a l y z e dt h et w ot y p i c a l p r o b l e m s i nt h e o p t i m i z a t i o n o fl o g i s t i c a l l o c a t i o n ( t h e s e l e c t i o no fs i t e sa n d o p t i m i z a t i o no fv e h i c l er o u t e s ) ，e s t a b l i s h e dt h em a t h e m a t i c a lm o d e lu n d e rc e r t a i n a s s u m p t i o np r e r e q u i s i t ea n db r i e f l yi n t r o d u c e dt h et o o l ( g e n e t i ca l g o r i t h m ) w i t hw h o l e r a n d o ms e a r c hc a p a b i l i t yt os o l v e p r o b l e m s ；f i n a l l y ，i tm a d e as e r i e so f i m p r o v e m e n t s t ot h ef u n d a m e n t a lg e n e t i ca l g o r i t h mi no p e r a t i n ga s p e c t so fs e l e c t i o n ，c r o s s o v e ra n d m u t a t i o n ，a p p l i e di t t ot h ep r o b l e mo f o p t i m i z a t i o no fl o g i s t i ca l l o c a t i o na n dc a r r i e d o u tb e n e f i c i a le x p e r i m e n ta n da n a l y s i s i no r d e rt oc h e c kt h ev a l i d i t yo f t h e p r o p o s e d i m p r o v e dg e n e t i ca l g o r i t h m ，t h ep a p e rw o r k e do u tt h es o u r c ep r o g r a m so f c s g a c a n dv r p g a ，ce n c l o s e di nt h ea a n e xa n dm a d es u b s t a n t i a l a n a l y s i so fp r a c t i c a l p r o b l e m sb y t h et w o p r o g r a m s t h r o u g h t h er e s u l to fs u b s t a n t i a la n a l y s i s ，i tc a nb es e e nt h a tt h e c o n v e r g e n c e r a t e o ft h ew h o l ea l g o r i t h mc a l lb eg r e a t l yi m p r o v e db ya d o p t i n gt h ei m p r o v e dg e n e t i c a l g o r i t h ma n dt h e r e b yt h ea r t i c l es u p p l i e da ne f f e c t i v em e t h o dt os o l v et h er e l a t e d p r o b l e m so fo p t i m i z a t i o n k e y w o r d s ：g e n e t i c a l g o r i t h m s i t es e l e c t i o no f a l l o c a t i o nc e n t e r o p t i m i z a t i o no f v e h i c l e r o u t e s 1 1 选题背景及意义 第一章绪论 随着信息技术的飞速发展，经济全球化、一体化趋势不断加快。信息技术在 网上的广泛应用，使得通过计算机网络实现商务活动的国际化、信息化和无纸化 己成为各国商务发展的一大趋势。电子商务受到世界各国的普遍关注，成为2 1 世纪世界经济新的增长点。 电子商务的运作过程包括三个基本“流”，即信息流、资金流和物流。随着电 子商务的进一步推广与应用，物流的重要性对电子商务活动的影响日益明显。我 国电子商务发展尚处初级阶段，正在向规范、务实方向推进。由于我国物流业的 专业化、社会化程度较低，物流配送时间过长、成本过高已成为目前制约我国开 展电子商务的“瓶颈”p l 。 实践证明，市场经济需要更高程度的组织化、规模化和系统化，因此迫切需 要物沉业尽快加强建设具有信息功能的物流配送中心，原国内贸易部早在1 9 9 6 年就发出了关于加强商业物流配送中心发展建设工作的通知1 2 。物流配送中 心是指为促进货物从制造厂商至零售商之间的迅速流转而设置的中间储存据点 1 3 。为了达到高效率配送，在最少的时间、最短的距离，以最低的成本完成配送 过程，这就要进行配送过程的优化。在物流系统中，配送中心设置地点的选择是 物流配送优化中一个具有战略意义的问题，合理选址可以有效节省费用，促进生 产和消费两种流量的协调与配合，保证物流系统的平衡发展【4 】。正是基于配送中 心位置的重要作用，迫切需要对其选址问题开展研究。在配送中心地址已经确定 的情况下，管理人员如何采取有效的配送策略，在满足需求点所要求需求量的前 提下合理安排车辆路径，是物流配送优化的又一个重要方面。 配送中心选址和有时间窗车辆路径问题的模型及其算法复杂，具有n p 难性 质p 】【6 】。启发式随机搜索方法( r a n d o mh e u r i s t i cs e a r c h ，r h s ) 是目前关于复杂优 化问题求解的一类有效方法，不需要或需要很少的关于问题的先验信息，该类方 法具有很强的鲁棒性，即能适应不同领域的优化问题求解，并在大多数情况下都 能得到比较满意的解。r h s 一般统称为弱方法( w e a km e t h o d s ) 。遗传算法就是一 种典型的弱方法，与其它搜索算法相比，具有独特的算法形式和运行机理，在复 杂优化问题求解中有着比较显著的优势川。 正是在以上背景下，笔者确定“基于遗传算法的物流配送优化研究”作为硕 士论文选题。 基于我国电子商务物流配送的现状，积极探索物流配送优化的理论和方法， 对降低物流成本、优化社会库存配置、提高服务质量，从而提高企业的经济效益 及社会效益具有重要的意义。这既是我国经济和社会发展的需要，也是保障电子 商务物流系统以适当的规模和速度健康发展的重要保证。 1 2 国内外研究状况综述 电子商务的优势之一是能大大简化业务流程及降低企业运作成本，而电子商 务环境下企业成本优势的建立和保持必须以可靠和高效的物流运作为保证，这一 观点已得到业界的广泛认同。在物流系统的建设中，物流配送的优化越来越引起 国内外学者的高度重视。根据论文选题，以下从三个方面进行历史回顾并陈述国 内外研究动态。 1 2 1 电子商务与物流的研究方面 物流的概念最早出现于1 9 1 5 年的美国，由阿奇萧在市场流通中的若干问 题一书中提出。现代物流是指物质实体从供应者向需求者的物理移动，它由一 系列创造时间价值和空间价值的经济活动组成，包括运输、保管、配送、包装、 装卸、流通加工及物流信息处理等多项基本活动，是这些活动的统一i ”。物流是 电子商务运作过程的三大基本“流”之一。 针对我国经济发展和物流业改革现状。借鉴发达国家走过的道路和经验，我 国从1 9 9 2 年开始了物流配送中心的试点工作，近年来，随着市场经济的快速增长， 特别是连锁商业的发展，各种形式的配送中心如雨后春笋发展起来。据不完全统 计，目前我国共有各种类型的物流配送中心2 0 0 0 多家。但大部分配送中心在层次 上仍是传统意义上的物流配送，即处于物流配送的初级阶段，国家有关部门已认 识到这些问题，正从宏观调控上努力引导我国物流配送业朝着信息化、现代化、 社会化的新型物流配送方向发展，一些有识的政府官员、企业界、理论界人士也 在共同进行着这方面的探讨，并已开始实蹦g 】。 物流配送优化的核心是降低物流成本，美国物流成本占国内生产总值( g d p ) 的比重在= 十世纪九十年代大体保持在1 1 4 1 1 7 范围内，而进入二十一世 纪，通过对物流配送体系进行优化，这一比重有了显著下降，由1 1 以上降到9 左右，从而成为经济效益提高的源泉。目前我国物流成本占g d p 的l v , 重r 大体保持 2 在2 3 2 5 的范围，因此，迫切需要我们通过优化物流配送的运作过程来降低 流通成本，从而给企业带来更大的利润1 9 】。 对我国电子商务下的物流进行深入探讨的学者主要有吴清一、丁俊发、张铎 等。吴清一教授最早将物流的概念引入中国，长期与有关部门、学会合作从事中 国物流事业的开拓与启蒙工作，组建了北京科技大学物流研究所，并创办了“物 流技术与应用”季刊；丁俊发教授长期从事流通经济学、消费经济学和现代物流 学等方面的研究工作，著有流通经济学、国内贸易经济管理、商品流通热 点探索、跨世纪中国流通发展战略、中国加入w t o 流通业面临的挑战、 机遇与发展、中国物流等著作；张铎教授是我国电子商务、物流管理领域建 树颇多的资深学者，1 9 9 2 年开始在北方交通大学物流科学研究所专门从事物流条 码与电子数据交换的研究，后定位于电子商务的物流与供应链管理研究，主要著 作有：电子商务与物流、国际物流学、条码技术与电子数据交换、电子商 务教程，以及物流管理丛书等，近年来在国内外学术会议及多种刊物上发表 论文百余篇，已经主持开发并投入使用的软件有：基于w e b 的第三方物流配送 管理系统、电子商务企业远程物资调度系统、电子商务企业物资进销存管理系统 等。 1 2 2 遗传算法的研究方面 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 的产生归功于m i c h i g a n 大学的j o h n h o l l a n d 在2 0 世纪6 0 年代末期的开创性工作，其本意是在人工适应系统中设计一 种基于自然演化原理的搜索机制，从试图解释自然系统中生物的复杂适应过程入 手，模拟生物进化的机制来构造人工系统的模型。随后经过3 0 余年的发展，取得 了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热 潮，使遗传算法受到广泛的关注。人们对遗传算法兴趣的日益增长有两个背景， 其一是工程领域，不断涌现超大规模的非线性系统，在这些系统的研究中存在着 大量的经典优化方法所不能有效求解的优化问题，其二，遗传算法本身就是一种 模拟自然演化这一学习过程的求解问题的方法，它能以独立或与其它方法相结合 的形式用于智能机器学习系统设计。从1 9 8 5 年在美国卡耐基梅隆大学召开的第 一届国际遗传算法会议( i n t a r n a t i o n a l c o n f 岛 e n c e o n g e n e t i c a l g o r i t h m s ：i c g a 8 5 ) 至今，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究 渐趋成熟【。 我国有关遗传算法的研究，从2 0 世纪9 0 年代以来一直处于不断上升的趋势， 3 特别是近年来，遗传算法的应用在许多领域取得了令人瞩目的成果，该类研究获 得不同渠道的经费资助比例也在逐年上升。武汉大学的刘勇、康立山等于1 9 9 5 年出版了非数值并行算法( 第2 册) 遗传算法；周明、孙树栋于1 9 9 9 年 出版了遗传算法原理及其应用；同济大学的王小平、曹立明于2 0 0 0 年出版了 遗传算法理论、应用与软件实现。国内有关遗传算法的b b s 电子公告牌有国 家智能中心曙光站b b s n e i c a cc n 、北京大学阳光创意站b b s p k u e d u c n 、清华大学 水土清华站b b s n e t t s i n g h u a e d u c n 、西安交通大学兵马佣站b b s x a n e te d uc r 等。 总之，遗传算法在理论上已经借鉴生物进化理论及遗传学机理形成了一套较 为完整的算法体系，然而在实践上还有很多问题有待于进一步研究、探讨和完善。 它们主要反映在以下方面：( 1 ) 控制参数选择问题；( 2 ) 成熟前收敛问题；( 3 ) 遗传算法的性能评价问题；( 4 ) 遗传算法的适应性问题；( 5 ) 混合算法问题；( 6 ) 从生物进化或遗传工程中不断汲取新的知识获得新的启发，从而对现有遗传算法 进行改进或提出新的算法问题等【1 l 】。 1 2 3 遗传算法在物流系统优化的应用研究方面 物流配送是一项复杂的科学系统工程，涉及到生产、批发、配送、运输和消 费者的整体结构，许多优化问题所建立的模型和算法复杂，大都具有n p 难性质， 其中配送中心选址问题和车辆路径优化现己成为物流配送优化研究的两个重要方 向，目前国内外对它们的理论研究和应用正处于探索阶段。 在我国，最近5 年的中国科学、系统工程理论与实践、系统工程、物 流技术、信息与控制及西南交通大学学报等刊物上，姜大立、谢秉磊、 王战权等学者发表了大量的采用遗传算法或改进的遗传算法解决与物流配送组合 优化相关的求解背包问题和车辆路径问题的文章。 综上所述，在基于遗传算法的优化方面，国内外进行了一些分散、独立的研 究，主要侧重于采用基本遗传算法对经典的巡回旅行商问题、背包问题、作业调 度问题等的探讨。目前尚难见到采用改进的遗传算法全面系统地针对具体的物流 配送优化问题的理论研究和实证分析。 1 3 论文的创新探索目标 。 在前人关于电子商务下的物流配送、遗传算法、组合优化问题的求解等方面 所做大量工作的基础上，论文在建设我国电子商务物流配送体系、遗传算法的改 进、改进遗传算法的应用等方面迸行探索与尝试。 4 ( 1 ) 针对基本遗传算法在优化应用中遇到的诸如局部搜索能力差、计算量大、 对较大搜索空间适应能力差和早熟收敛等问题，根据物流配送问题的不同情况， 通过对基本遗传算法进行改进，提出相应的改进遗传算法。 ( 2 ) 把改进遗传算法应用于物流配送优化中实际问题的求解，并采用c 语 言完成对其算法的实现。 ( 3 ) 通过实证分析，验证改进遗传算法用于物流配送优化的有效性。 第二章电子商务与物流 2 1 电子商务与物流的关系 电子商务的本质是商务，商务的核心内容是商品的交易，而商品交易会涉及 到三方面：有关信息的获取与应用，货币的支付，商品本身的转交。即信息流、 资金流、物流。其中信息流既包括商品信息的提供、促销行销、技术支持、售后 服务等内容，也包括诸如询价单、报价单、付款通知单、转账通知单等商业贸易 单证，还包括交易方的支付能力、支付信誉等。资金流主要是指资金的转移过程， 包括付款、转账等过程。在电子商务环境下，信息流和与资金流都与传统情况有 所不同。它们的处理可以通过计算机和网络通讯设备实现。物流，作为最为特殊 的一种“流”，是指物质实体的流动过程，具体指运输、储存、配送、装卸、保管、 物流信息管理等各种活动。对于少数商品和服务来说，可以直接通过网络传输的 方式进行配送，如各种电子出版物、信息咨询服务等。而对于大多数商品和服务 来说，物流仍要经由物理方式传输1 1 2 】。 电子商务是一场商业领域的根本性革命，然而，它在中国发展的实际情况却 远没有预想中的那样好，其中物流能力的滞后是一个重要的原因。过去，人们对 物流在电子商务中的重要性认识不够，对于物流在电子商务环境下应发生的变化 也认识不足，认为对于大多数商品和服务来说，物流仍然可以经由传统的经销渠 道。但随着电子商务的迸一步推广与应用，物流能力的滞后对其发展的制约越来 越明显。物流的重要性对电子商务活动的影响被越来越多的入所注意。 物流在未来的发展与电子商务的影响是密不可分的，可以这样理解这种关系： 物流本身的矛盾促使其发展，而电子商务恰恰提供了解决这种矛盾的手段；反过 来，电子商务本身矛盾的解决，也需要物流来提供手段，新经济模式要求新物流 模式。 2 2 电子商务对物流的影响 由于电予商务与物流间密切的关系，电子商务这场革命必然对物流产生极大 的影响。这个影响是全方位的，从物流业的地位到供应链管理，再到物流各作业 环节，都将在电子商务的影响下发生巨大的变化。 2 2 1 物流业的地位大大提高 电子商务是一次高科技和信息化的革命。它把商务、广告、订货、购买、支 付、认证等实物和事务处理虚拟化、信息化，使它们变成脱离实体而能在计算机 网络上处理的信息，又将信息处理电子化，强化了信息处理，弱化了实体处理。 这必然导致产业大重组，原有的一些行业、企业将逐渐压缩乃至消亡，同时也会 扩大和新增一些行业、企业。产业重组的结果，可能使得社会上的产业只剩下两 类行业，一类是实业，包括制造业和物流业；一类是信息业，包括服务、金融、 信息处理业等。在实业中，物流企业会越来越强化，其原因是在电子商务环境里 它必须承担更重要的任务：既要把虚拟商店的货物送到用户手中，而且还要从生 产企业及时进货入库。物流公司既是生产企业的仓库，又是用户的实物供应者。 物流企业成了代表所有生产企业及供应商对用户的唯一最集中、最广泛的实物供 应者。物流业成为社会生产链条的领导者和协调者，为社会提供全方位的物流服 务。可见，电子商务把物流业提升到了前所未有的高度，为其提供了空前发展的 机遇。 2 2 2 供应链管理的变化 在传统的供应链渠道中，产品从生产企业流到消费者手里要经过多层分销商， 流程很长，由此造成了很多问题。现在，电子商务缩短了生产厂家和最终用户之 间供应链上的距离，改变了传统市场的结构。企业可以通过自己的网站绕过传统 的经销商与客户直接沟通。虽然目前很多非生产企业的商业网站继续充当了传统 经销商的角色，但由于它们与生产企业和消费者都直接互连，只是一个虚拟的信 息与组织中介，不需要设置多层实体分销网络( 包括人员与店铺设施) ，也不需要 存货，因此仍然降低了流通成本，缩短了流通时间。 供应链中货物流动方向由“推动式”变成“拉动式”，传统的供应链由于供销 之间的脱节，供应商难以得到及时而准确的销售信息，因此只能对存货管理采用 计划方法，存货的流动是“推动式”的。它有两个明显的缺点：第一是缺乏灵活 性，销路好的商品，其存货往往可得性差，销路不好的就积压；第二是运转周期 长。在电子商务环境下，供应链实现了一体化，供应商与零售商、消费者通过 i n t e r n e t 连在了一起，供应商可以及时准确地掌握产品销售信息与顾客信息。此时 存货管理采用反应方法，按所获信息组织产品生产和对零售商供货，存货的流动 变成“拉动式”，完全可以消除上述两个缺点，并实现销售方面的“零库存”。 2 2 3 电子商务对物流各作业环节的影响 电子商务对物流各作业环节的影响主要表现在采购和配送两方面，下面分别 7 予以介绍。 ( 1 ) 对采购的影响 传统的采购极其复杂，采购员要完成寻找合适的供应商、检验产品、下订单、 接取发货通知单和货物发票等一系列复杂繁琐的工作。而在电子商务环境下，企 业的采购过程会变得简单、顺畅。近年来，国际上一些大的公司已在专用网络上 使用e d i 以降低采购过程中的劳务、印刷和邮寄费用。通常，公司可由此节约5 至1 0 的采购成本。因特网与之相比可进一步降低采购成本。与专用增值网相比， 大公司能从因特网的更低传输成本中获得更多收益。因特网也为中小型企业打开 了一扇大门。 ( 2 ) 对配送的影响 。 b 2 c 的物流支持要靠配送来提供，b 2 b 的物流业务会逐渐外包，其供货方式 也是配送制。没有配送，电子商务物流就无法实现，电子商务也就无法实现，电 子商务的命运与配送业联在了一起。同时，电子商务使制造业与零售业实现“零 库存”，实际上是把库存转移给了配送中心，因此配送中心成为整个社会的仓库。 由此可见，配送业的地位大大提高了。实际上，对于电子商务交易方式本身来说， 买方通过轻松点击完成了购买，卖方势必要把货物配送到家，否则买方选择这种 交易方式的意义何在呢? 所以，从某种程度上说，电子商务时代的物流方式就是 配送方式。原来，物流、信息流是“二流分立”的，而信息化、社会化和现代化 的物流配送中心把二者有机地结合在一起【1 2 l 。 2 3 物流配送对电子商务发展的重要作用 物流配送是对整个物流过程实行统一的信息管理和调度，按照用户订货要求， 在物流基地进行理货工作，并将配好的货物送交收货人的一种物流方式。它对电 子商务发展的作用主要体现在以下几个方面： ( 1 ) 物流配送能有效降低电子商务物流成本 电子商务的交易过程有大量的中介参与，交易主体往往把一个交易过程分为 几个交易环节实现，并在诸环节中把一定的业务转移给中介行业来实现，主要目 的就是通过分工实现接个交易过程的低成本。从社会宏观上看，在整个交易的构 成中，实体物品的运输费用占据了很大一部分，因此交易主体通过各种途径努力 降低费用。信息的及时传递和正确地进行物流规划，可以尽量减少不必要的实物 转移，从而降低物流费用；而借助于物流配送能有效地降低从一方转移到另一方 的实物运输成本。 r ( 2 ) 物流配送能提高电子商务对客户需求的快速反应能力 配送中心不仅与生产企业保持紧密的伙伴关系，而且直接与客户个体保持联 系，能及时了解客户的需求信息，并沟通企业和客户双方。对于现在这样一个信 息高速传递、技术进步快、消费需求多样且多变的环境，消费者要求所选购的商 品能快速获得，以便能获取时间效用；而对生产企业来说，为快速满足消费者的 需求，同时为了降低生产成本而采用零库存生产、敏捷制造等先进生产方式，更 要求加快物流速度。缩短物流周期比缩短制造周期更重要，这就要求在物流整个 供应链上，各环节之间信息传递畅通，衔接紧密且传递环节少，强调协作以提高 整体协同效用。 ( 3 ) 物流配送是实现电子商务“以顾客为中心”理念的保证 电子商务要求提供全方位的服务，既包括仓储、运输服务，又包括配货、分 发及与各种客户需要的配套服务，因此物流成为连接生产企业与最终用户的重要 环节。电子商务的出现最大程度地方便了最终消费者，他们可以在网上方便地搜 索、查看、挑选、支付完成购物过程。但一旦网上购买的商品迟迟不能送达，消 费者必然会转向更可靠的传统购物方式，我国曾经轰动一时的“7 2 小时网络生存 测试”充分说明了这一点。欧洲的电子商务开展的比日本早，但他们的电子商务 公司普遍不如日本好，其原因就在于他们缺乏像日本流通网络中的2 4 小时便利店 这类送货网络的支持。面对发展电子商务对发达的物流配送的需求，物流业可以 说面临着巨大的机遇。 “全球经济一体化”、“电子商务网络化”的趋势决定了2 1 世纪将是物流业蓬 勃发展的世纪。2 l 世纪我国物流业所要面对的现代物流经济、加入w t o 后国内 物流市场的对外开放等现象，就像经济全球化发展一样，已经不是一个选择的问 题，而是一个必须接受的事实。因此，面对新的机遇和挑战，我们必须制定新的 政策和措施，在创新和竞争中实现新的发展。 2 4 建立我国电子商务物流配送体系的构想 基于我国电子商务物流配送的现状，积极构建既符合国际潮流，又符合我国 实际的电子商务物流配送体系己成了当务之急。 ( 1 ) 加强物流基础设旌建设，制定物流产业发展政策 现代物流体系建立的前提是先进的物流基础设施，因而政府应统筹规划，建 立以重要经济区域、中心城市、沿海港口城市为依托的，与我国经济发展水平相 适应、具备一定国际竞争力的现代物流网络系统。继续加大物流基础设施的投资 9 力度，并积极引导社会各方力量涉足物流业的投资建设，促进我国物流业发展和 整体水平的提高。 为有准备地引导和促进我国物流产业的发展，政府还应制定规范的物流产业 发展政策、总体目标，以形成良好的制度环境。政策的制定应着重考虑我国物流 产业的发展应以市场为导向，企业为主体，以物流服务需求为依托，最大限度地 降低全社会的物流总成本，提高物流效率。 ( 2 3 建立城市大型综合物流中心，形成有核心能力的第三方物流 所谓大型综合物流中心，是指多功能、集散能力强、辐射能力广的社会化物 流中心。我国物流业发展中最重要的问题之一是物流规模化、社会化程度低，而 综合物流中心正是解决这一问题的有效途径。 目前，对于我国物流业，一方面供应商感觉物流资源缺乏，难以找到满意的 物流代理企业，而自己又没有足够的入力、财力、物力建立全国范围的现代物流 体系，物流滞后使电子商务步履维艰。另一方面国内实体物流企业数量有余，物 流网络资源丰富，利用率却低。因此，在探索我国电子商务物流模式时i 可以借 鉴第三方物流模式。业界把既不属于供应商，也不属于销售商的独立物流配送公 司称为第三方物流。它既能充分利用国内已有的物流资源，避免了重复建设，又 能把有限资金用于对现有物流企业进行信息化、网络化建设。 ( 3 ) 建立全国物流公共信息平台，发展第四方物流 全国物流公共信息平台可以认为是我国业界和理论界所说的“第四方物流”， 这是一个全新的物流理念【1 3 l 。第四方物流是一个供应链集成商，它调集和管理组 织自己的以及具有互补性的服务提供商的资源、能力和技术，以提供一个综合的 供应链解决方案。它的主要作用是：对制造企业或分销企业的供应链进行监控， 在客户和它的物流与信息供应商之间充当唯一“联系人”的角色。显然，第四方 物流必须满足三个条件：不是物流的利益方、能实现信息共享、有能力整台所有 的物流资源。而真正满足这些条件的只有一种虚拟的物流网络平台，这就是全国 物流公共信息平台。它能提供综合的供应链解决方案，以整合社会物流资源，提 高我国物流产业的综合协同能力。 建立在i n t e x n e t 上的物流公共信息平台，可让所有用户输入的资料都直接进 入数据库以便进行各种各样的数据处理。所有的数据可以永久储存，所有的用户 都可以在这个平台上互动式经营。物流公共信息平台整合了社会资源，解决了物 流信息充分共享、社会物流资源充分利用的闯题。它作为客户间的联接点，通过 合作或联盟提供快速、优质、高效、低耗的多样化服务。它作为新的生产方式所 产生的时空概念，可以大大缩短物流时间，为企业带来盈利来源和利润的新增长 点。目前日本、美国等些发达国家已经在宏观上建立了比较完善的物流网络体 系，并且在企业运作过程中也能提供网络化服务，我国应尽快建立这种公共物流 信息平台，重点培育已经具有第四方物流雏形及有一定物流基础的物流信息平台， 促使我国的物流产业真正成为“第三利润源泉”【8 】。 ( 4 ) 加快物流产业标准化、规范化进程 要实现物流的现代化，首先要实现物流的标准化、规范化。对物流行业来说， 需要用标准化、规范化的方式将供方干线物流配送送达需求方等物 流环节有机链接起来。如果没有相适应的物流接口标准，很难想象其链接的难度 和成本。物流业的规范和标准，还应对有关细节作出明确规定，如物流用语、计 量标准、包装标准、装卸标准等。对物流企业来说，标准化是提高内部管理、降 低成本、提高服务质量的有效措旅；对消费者而言，享受标准化的物流服务是消 费者权益的体现。 为适应国际贸易的需要，网上信息传输应采取国际通用的标准。如目前国际 物品编码协会( e a n ) 成员间通用的、基于互联网的电子数据交换( e d i ) 技术。 它能在某一公司的计算机与用户或卖方等贸易伙伴的计算机之间传递和接受具有 标准格式的贸易单据。我国已成为e a n 组织的会员国，然而在国内却没有使用 e d i 这种灵活方便的技术。所以e a n 的e d i 技术应引起我国的足够重视。 此外，我国还应加快物漉人才培养，积极引进物流人才；鼓励物流企业技术 创新：在适当的时候，也应考虑建立“注册物流师”制度；加强国际合作，积极 借鉴国外先进的物流理念和物流技术，促进我国物流产业的发展和整体水平的提 高1 4 1 。 第三章物流配送优化中的典型问题及其理论分析 3 1 物流配送优化中两个典型问题的描述 ( 1 ) 配送中心选址问题的描述 配送中心选址问题可描述如下： 给定某一地区所有需求点( 用户) 的地址集合，要求从中选出一定数目的地 址建立配送中心，从而建立一系列的配送区域，实现各个需求点的配送，使得在 选出点建立的配送中心与各个需求点所建立的配送系统总配送费用最小。其目的 在于加快货物流动速度并避免不必要的配送成本【1 5 】。 ( 2 ) 车辆路径优化问题的描述 一般车辆路径问题可描述如下： 有g 个货物需求点，己知每个需求点的需求量及位置，至多用k 辆汽车从配 送中心到达这批需求点，每辆汽车载重量一定，安排汽车路线使运距最短且满足 每条路线不超过汽车载重量和每个需点的需求必须且只能由一辆汽车来满足的约 束条件。其目的是使总成本( 如距离、时问等) 为最小。 有时间窗车辆路径问题( 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 w ， v r p t w ) 是在上述一般车辆路径问题中加上了客户被访问的时间窗约束。它要求 每项任务f 在时间范围h ，明内完成，并可根据时间约束的严格与否，分为软时 间约束的v r p 和硬时间约束的v r p 。软时间约束的v r p 要求车辆尽可能在规定 时问范围内访问需求点，否则将产生等待或延迟损失，从而求得成本最小的车辆 路径；硬时间约束的v r p 要求车辆必须在给定的时间范围内访问需求点，如果超 出这个时间范围，所得到的车辆路径为不可行解【1 6 】【1 7 】。 3 2 配送中心选址问题的理论分析 ( 1 ) 配送中心选址模型的假设 为了便于建立模型，作一定的假设，假设系统满足如下一些条件m 1 在一定的被选范围内考虑新的配送中心设置； 运输费用与运量和距离成正比： 需求点的需求按区域总计； 一个需求点仅由一个配送中心供应； 12 配送中心容量可以满足要求； 各需求点的需求量一定且为已知； 各需求点需求的物品一次运输完成，所有点间运输速度一样，均为常数； 系统总费用不考虑仓库存储费用，只考虑固定的仓库建设费和运输费用。 ( 2 ) 配送中心选址模型的建立1 1 9 】 配送中心选址问题的模型可以考虑两种： 第一类问题模型：只包含一级运输，其目标函数是从被选地点中选出最佳 的配送中心，使包括配送中心的投资费用及运输费用的总和最小。 目标函数： m i n u = d f h s f a f + f , z j ( 3 1 ) j = l i 爿 ，= 1 约束条件： a # z = 1 f = 1 , 2 ，棚； i = l 式中： ( 3 2 ) m 需求点的个数、配送中心被选地的个数； 巧在j 点建设配送中心的费用； 4 需求点i 的需求量： 町配送中心j 到需求点i 的距离； 厅一运费率； f 0在用户f 处不设置配送中心； z ，= i 1 在用户，处设置配送中心； f 0用户f 的需求不由设在，处的配送中心负责； a f = i l用户f 的需求由设萄处的配送中心负责； 其中，约束条件可以保证一个需求点仅由一个配送中心供应。 第二类问题模型；第二类问题比第一类问题增加了从工厂到配送中心的运 输。因此，建立目标函数时应该考虑使包括工厂到配送中心的运输费在内的总费 用为最小。 目标函数： l3 m i nu ：妻艺d i 加，爿，+ 窆z ，+ 妻艺w ：h s 业b 业 ( 3 3 ) ，= 1 j = 1 j = lk = l ，= t 约束条件： 爿v z ，= 1 i = l 一2 ，珊； ( 34 ) = z ， = 1 ，2 一职 ( 35 ) k = l 式中： 埘需求点的个数、配送中心被选地的个数； p _ 供应工厂的数目； v 广_ 配送中心，的需求量； 毋一在- ，点建设配送中心的费用； 玉一需求点f 的需求量； 曲配送中心，到需求点f 的距离； 断从工厂k 到配送中心_ ，的距离： h 运费率； f 0在用户，处不设置配送中心； z j = i i在用户，处设置配送中心； f 0用户坩需求不由设萄处的配送中心负责； 一f = 1 1用户f 的需求由设萄处的配送中心负责； f 0配送中，町的需求不由设在i 处的工厂负责； 岛= 【l 配送中，町的需求由设在j 处的工厂负责； 其中，式( 34 ) 可以保证一个需求点仅由一个配送中心供应；式( 35 ) 可以保 证一个配送中心仅由一个工厂供应。 3 3 车辆路径优化问题的理论分析 、 ( 1 ) 一般车辆路径问题的数学模型 假定配送中心最多可用世辆车对g 个货物需求点进行运输配送，每部车辆的 载重量为b k ( k = l ，2 ，k ) ，每个需求点的需求量为吐o = 1 ，2 ，q ) ，需求点i 到需 14 求点_ ，的运距为勺，设吼为第k 辆车所包含的需求点数( 若，栌o 表示未启用第k 辆车) ，用集合风表示第i 条路径，其中的元素表示需求点憎在路径k 中的顺 序为i ( 不包含配送中心) ，令。= r k ( 叫) = 0 表示配送中心，则有如下表示的车辆 路径问题的数学模型。 目标函数： k月ik m i n u = = c ，。( 。) ，。+ c ，。，。+ 。，s i g n ( ，2 1 ) ( 36 ) po li o lr l 约束条件： d 。b t j 】 = 1 , 2 ，k ( 3 7 ) i = l 0 ”t qk = 1 , 2 ，k( 3 8 ) f 仇= g ( 3 9 ) k = l r = k i 珞她，一g i = 1 , 2 ，。n k ) ( 3 10 ) r 。n r ：= 庐v k 如( 3 1 1 ) 其中： f 1以l s f g n ( n 一1 ) = ( 3 1 2 ) 【0 其它 式( 3 7 ) 保证每条路径上的各需求点的总需求最不超过此条路径的配送车容 量；式( 3 8 ) 表明每条路径服务的需求点数不超过总需求点数；式( 3 9 ) 要求每个需 求点都得到车辆的配送服务；式( 3 1 0 ) 表示每条路径需求点的组成情况；式( 3 1 1 ) 则限制每个需求点的需求仅能由一个车辆来完成( 2 1 】。 ( 2 ) 有时间窗车辆路径问题的数学模型【2 2 】 以函表示车辆到达需求点i 的时刻，表示车辆在需求点i 的等待时间，b 表 示车辆由需求点f 行驶到需求点，的时间，则有以下关系式： t ，= m a x 口j 一5 p0 ( 31 3 ) 墨+ f f + 勺2 “2 0 1 ，qf 叫( 3 1 4 ) 口，5 ，b j j = 1 , 2 ，g( 3 1 5 ) 软时间窗v r p 指车辆如果不能在要求的时间范围内到达，则给予一定的惩 罚。若车辆在q 之前到达需求点，则车辆在此等待，发生了机会成本损失，此时 寺大于o ；若车辆在西之后到达需求点，则服务被延迟，须支付一定的罚金。以d 表示车辆等待损失的单位机会成本，e 表示车辆在要求时间之后到达所处以的单 位罚值，若车辆在印之前到达需求点歹，则产生成本d 以，一s j ) ：若车辆在匆之后 到达需求点j ，则处以罚