基于GIS的城市物流配送路径规划研究.pdf

《基于GIS的城市物流配送路径规划研究.pdf》由会员分享，可在线阅读，更多相关《基于GIS的城市物流配送路径规划研究.pdf（71页珍藏版）》请在三一文库上搜索。

1、华中师范大学 硕士学位论文 基于GIS的城市物流配送路径规划研究 姓名：姚娟 申请学位级别：硕士 专业：情报学 指导教师：李玉海 20060605 硕士学位论文 M A S T E R ST H E S I S 摘要 随着计算机和网络技术的进一步发展和应用，现代物流配送正步入一个信息 化、自动化、网络化、智能化的发展阶段。特别是近年来G I S 在理论和应用中的发 展为解决现代化物流配送提供了有利的条件。本文结合电子商务环境下的第三方物 流企业的需要，对物流配送中的配送车辆的路径优化问题进行了研究。在借鉴前人 研究成果的基础上，将G I S 应用于物流配送路径分析中，利用G I S 强大的空间

2、分析 功能来完善物流分析技术，通过一系列物流配送优化算法模型，开发了基于G I S 的 城市物流配送路径分析系统，从而为物流配送管理者提供科学的决策依据。 在解决城市物流配送路径规划问题时，本文采用分解的思路把整个路径规划问 题分解成为配送区域划分子问题和单车辆路线优化子问题。在配送区域划分的求解 过程中，本文首次提出了利用V o r o n o i 图对配送区域进行区划的方法，避免了其他 区划方法出现的区域半径确定的随意性以及配送区重叠或配送盲区的问题。在单车 辆路线优化的求解过程中，本文采用启发式的方法遗传算法来实现，并在遗传算 法框架中加入局部搜索能力很强的贪婪算法，利用贪婪算法邻域搜索

3、原则建立了一 种新的遗传交叉算子一贪婪交叉算子，从而改善了遗传算法的局部搜索能力，达到 了快速收敛的效果。 最后本文提出了基于G I S 的城市物流配送路径分析系统的总体设计思路和详细 的功能设计，并利用A R C I N F O R 的M a p O b j e c t s 控件和V B 为开发平台，开发了基于 G I S 的城市物流配送路径分析系统。 关键词：物流配送；路径规划；V o r o n o i ；遗传算法；贪婪算法；G I S 硕士学位论文 M A S T E R ，ST H E S I S A b s t r a c t W i t ht h ef a r t h e rd

4、e v e l o p m e n to fc o m p u t e rs c i e n c ea n dn e t w o r kt e c h n o l o g y , m o d e m l o g i s t i c sd i s t r i b u t i o n i ss t e p p i n gi n t oq u i c k l yp r o g r e s sp e r i o d E s p e c i a l l y , i nt h e r e s e n ty e a r s ，t h em o r ew i d e l ya p p l i c a t i

5、o no fG I Sp r o v i d e saa d v a n t a g e o u sc o n d i t i o nt o t a k et h el o g i s t i c sd i s t r i b u t i o np r o b l e m T h i sp a p e rs t u d yo nh o wt oo p t i m i z et h ep l a n n i n g o fv e h i c l er o u t i n gt om e e tt h ed e m a n do ft h et h i r dp a r tl o g i s t

6、i c sc o m p a n y I no r d e rt o r e s o l v et h i sN Pp r o b l e m ，t h i sr e s e a r c hi n t r o d u c e sG I Si n t oc i t yl o g i s t i c sd i s t r i b u t i o n p l a n n i n gs y s t e m ，m o d e l i n ga s e t so f o p t i m i z a t i o na l g o r i t h m sb a s e do nt h es p a t i a

7、 la n a l y s i s f u n c t i o n so fG I Sa n da c t u a l i z ei to nG Sp l a t f o r m I nt h er e s e a r c ho nt h ev e h i c l er o u t i n gp l a n n i n g ，t h ew h o l ep r o b l e mi sd i v i d e di n t o t w op h a s e si nt h ep r o c e s so fb u i l d i n gm o d e l ，w h i c ha r ea r e

8、 ap a r t i t i o np r o b l e ma n ds i n g l e v e h i c l er o u t i n gp r o b l e m T h i sp a p e rp r o v i d e san e wm e t h o dc a l l e dV o r o n o i - p a r t i t i o n a p p r o a c ht od e a lw i t ht h ea r e ap a r t i t i o np r o b l e m A st os i n g l ev e h i c l er o u t i n g

9、p r o b l e m ，a n e wk i n do fh y b r i dg e n e t i ca l g o r i t h mi sp u tf o r w a r d T h ei d e af o rt h i sh y b r i dg e n e t i c a l g o r i t h mi st oa d dab r a n n e wg r e e d yo p e r a t o ri n t ot h ef r a m e w o r ko fg e n e t i ca l g o r i t h m t oi m p r o v et h ee f

10、f i c i e n c yo ft h ea l g o r i t h m A tl a s t ，t h i sp a p e rd i s c u s s e sa b o u tt h ef r a m e w o r kd e s i g na n dd e t a i l e df u n c t i o nd e s i g n f o rt h ee i t yl o g i s t i c sv e h i c l er o u t i n gp l a n n i n gs y s t e mb a s e do nG I Sa n da c t u a l i z e

11、t h i s s y s t e mu s i n gm a p o b j e c t sA c t i v e X c o n t r o la n dV i s u a lB a s i cp l a t f o r m K e y w o r d s ：c i t yl o g i s t i c sd i s t r i b u t i o n ； v e h i c l er o u t i n gp l a n n i n g ；V o r o n o i ；g e n e t i c a l g o r i t h m ；g r e e d ya l g o r i t h

12、m ：G I S I I 硕士学位论文 M A S T E R ST H E S I S 华中师范大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中己经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 学位论文作者签名：埘 日期：占删；毋月r 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件

13、和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：匀嘲指导教师签名毋铴 日期沙够多月夕日 日期：游月) 日 本人已经认真阅读“C A L L S 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“C A L L S 高校学位论文全文数据库”中全文发布，并可按“章程” 布。 澎h幕 寺口 年签化)糕撇心 提 ， 恻磷 群恢日 丽勿f 关 者 默储纾 硕士学位论文 M A S T E R ST H E S I S 1 绪论 1 1 研究背景及意义 随

14、着经济全球化和信息技术的快速发展，电子商务作为商业贸易领域中一种先 进的交易方式在全球迅速蔓延，并对商贸领域中传统的观念和行为方式产生着巨大 的冲击和影响。在电子商务环境下，一个完整的商务活动是由信息流、商流、资金 流和物流等4 个流动过程有机的构成1 。信息流、商流、资金流可以在互联网上实 现的，这属于“虚拟“ 的经济过程，但是它的最终实现还是需要依赖于高度发达的 物流配送体系，所以在一定意义上说物流配送是电子商务的重要组成部分，是信息 流和资金流的基础与载体，也是决定电子商务成败的关键因素。 配送作为物流体系的重要环节，对于整个物流系统的效率起着关键性的作用。 在我国现阶段，物流配送的发展

15、还比较落后，基本上还停留在“只送不配“ 的水平 上，造成了配送效率低下，配送成本高，服务质量差，这已成为制约电子商务健康 发展的瓶颈乜1 。高成本、低效率的物流配送使得在网上瞬间完成的电子商务所节约 的时间、费用已变得毫无意义。因此如何实现快速而准确的配送是企业在经营方面 必须解决的重要课题。鉴于此，研究运用科学方法合理组织物流配送，建立一个高 效率、低成本的物流配送体系来支撑和保障电子商务的快速发展己成为当务之急。 随着计算机和网络技术的进一步发展和应用，特别是数字城市，数字地球的进 一步深入，地理信息系统( G I S ) 的社会化，将加速电子商务经济的发展，同时也 将在物流配送的实现中发

16、挥其重要作用。G I S 对配送中心和配送点、交通路线等地 理信息进行提取、加工，依靠其强大的空间分析和网络分析功能实现配送对象的自 动选择、运输路线的动态确定。同时G I S 结合G P S 和G S M 等技术，实现信息采集、 命令发送及信息共享，实现物流配送监控的实时智能化，为物流配送决策服务，从 而实现企业物流管理的可视化，动态化。G I S 、G P S 、城市物流配送以及其他相关 信息技术的有机结合构建的城市物流配送系统，将使物流配送企业在提高配送速 度，降低运作成本，提高信息处理能力、拓宽服务内容方面达到新的水平。 1 2 研究的动机与目的 X X 公司是一家从事物流配送业务的公

17、司，主要为电子商务网站和电视购物频道 承担某市内物流配送业务。公司目前在市内设有四个配送仓库，拥有2 吨左右的货 运车辆1 0 多辆，客户覆盖整个市区。由于电子商务环境下的物流配送具有动态的 硕士学位论文 M A S T E R ST H E S I S 特性，消费者可以不受营业时间与地点的限制通过网络进行交易，网络上供需信息 不断的在更新，交易与买卖的双方也不停的在变动。对于传统的物流配送方式，将 无法在实时订货信息下提供最佳的配送效率。该公司原有配送活动是以人工的经验 法则决定，通常是出货人员依据订单将货物装运上车，然后车辆调度人员依据订单 及需求点的位置，指派配送路线或是司机依本身经验来

18、完成配送。但是由于配送活 动的不断扩张以及道路网的错综复杂，以往人工的方式己渐渐不能负荷目前的需求 而且在车辆的监控与调度管理上无法进行，因此需要建立一套现代化的物流配送系 统以实现快速、准确、有效的配送路径规戈0 及车辆的调度与监控。 本研究根据X X 公司物流配送业务的运作及管理需求，研究开发一套以满足企 业的物流配送运作要求为目的基于G I S 的物流配送路径分析的初级系统，实现了配 送作业的智能运作和控制。在整个系统的建立和应用中，主要针对企业的实际情况 和要求，选择和开发合适的系统架构、运算模型以实现系统在企业中的实际运作。 1 3 物流配送路径规划问题的研究现状 物流配送路径选择及

19、车辆优化调度是整个物流配送系统优化中关键的环节，也 是电子商务活动不可缺少的内容。该问题最早是由D a n t z i n g 和R a m s e r ：于二1 9 5 9 年提 出的，由于这一问题的理论涉及多学科，应用前景广阔，所以很快引起了运筹学、 应用数学、图论与网络分析、物流学、交通运输工程、管理科学与工程、计算机应 用等学科的专家、工程技术人员的极大重视。自此一直成为运筹学与组合优化领域 的前沿与研究热点，各学科专家对该问题进行了大量的理论研究及试验分析，取得 了很大进展。 学者B o d i n 于1 9 8 3 年根据物流配送路径规划问题的空间特性和时间特性的相对 重要性作了划

20、分：当不考虑时间要求，仅根据空间位置安排线路时称车辆线路安排 问题( V e h i c l eR o u t i n gP r o b l e m ，简记V R P ) ；考虑时间要求安排线路时称为车辆调 度问题( V e h i c l eS c h e d u l i n gP r o b l e m ，简记V S P ) ；同时考虑空间位置和时间要求 称为R o u t i n g 和S c h e d u l i n g 混合问题( V e h i c l eR o u t i n ga n dS c h e d u l i n gP r o b l e m ， 简记V R P &

21、V S P ) 。 物流配送路径规划问题是组合优化领域中著名的N P ( N o n d e t e r m i n i s t i c P o l y n o m i a lP r o b l e m ，即非确定型多项式问题) 难题。不少专家学者对其计算复杂 性进行了研究，这是确定其求解算法研究方向的基础。近二十年来，无论在国内还 D a n t i z i gG ，R a m s e rJ ，T h et r u c kd i s p a t c h i n gp r o b l e m M a n a g e m e n tS c i e n c e 。1 9 5 9 ( 6 ) ：8

22、0 9 1 2 硕士学位论文 M A S T E R ST H E S I S 是国外，物流配送路径规划问题都是一个非常活跃的研究领域。目前国内外用于解 决该问题的方法主要分为精确算法和启发式算法两大类。 1 、精确算法。精确算法是指可求出其最优解的算法，主要有：动态规划法、 分枝定界法、切平面法、直接树搜索算法、网络流算法、整数线性规划法等。总的 来说，精确算法基于严格的数学手段，在可以求解的情况下，其解通常要优于启发 式算法。但由于引入了严格的数学方法，因而无法避开指数爆炸问题，即精确算法 的计算量会随着问题规模的增大而呈指数增长。因此在实际中其应用范围很有限。 2 、启发式算法。启发式算

23、法指通过对过去经验的归纳推理以及实验分析来解 决问题的方法，它要求分析人员必须运用自己的感知和洞察力，从与研究问题有关 而较基本的模型及算法中寻求其中的联系，从中得到启发，去发现解决问题的思路 和途径H 1 。启发式方法作为一种逐次逼近的算法，与精确算法相比虽然在精度上不 占优势，但在求解大规模V R P 问题时，总可以在有限的时间内，找到满意的次优解 可行解，这也是精确算法难以做到的。因此，在实际应用中，启发式算法要更广泛。 为此，专家们主要把精力用在构造高质量的启发式算法上。启发式算法主要有：节 约法1 、扫描法瞄、插入法、分区配送算法口3 、禁忌搜索算法嘲、模拟退火 算法、人工神经网络算

24、法、遗传算法四1 等。 1 4 将G ls 引入物流配送路径规划的研究现状 地理信息系统是一种以地理空间数据为基础，实时提供多种空间、动态的地理 信息及决策服务的计算机技术系统，它依据地理对象的空间特征及属性特征，建立 各种空间分析模型，并在这些模型的基础上使用空间查询和空间分析来对地理数据 进行管理并通过对地理数据进行分析加工提取有用的地理信息，从而为辅助决策服 务n 训。具体来讲，城市物流配送的基础数据是由点和线组成的城市交通网，将G I S 应用于物流分析，主要是指利用G I S 网络分析功能对这些网状数据进行全面的描 述表达，对物流运输网络进行地理分析和模型化，通过一系列物流配送优化算

25、法模 型，为物流配送管理者提供科学的决策依据n 。在利用G I S 网络分析进行物流配送 路径规划研究，多集中于算法和特定的物流配送系统实现的研究。 最短路径、资源分配、结点或弧段的游历( 旅行商问题、中国邮递员问题) 以 及最小连通树、最大( 小) 流等问题，其相应的模型和算法已经比较多，以最短路 径算法为例，目前已经有很多最短路径查找算法：乐阳等人写的“D i j k s t r a 最短路 径算法的一种高效率实现”、王杰臣等人写的“图的结点一弧段联合结构表示法 乐阳：网络分析模型在G I S 中的实现与应用，册士论文 ，武汉：武汉测绘科技大学，1 9 9 9 ，第2 l 一3 4 页 硕

26、士学位论文 M A S T E R ST H E S I S 及其在G I S 最优路径选取中的应用”、王苏男等人写的“最短路径算法的比较”管、 陆锋写的“最短路径算法：分类体系与研究进展” 等等。但是，原有的这些方法 由于受到计算机硬件发展水平的限制，还存在某些局限性，而这些在目前条件下是 可以克服的。另外，对象关系数据库在G I S 中的广泛采用，使得空间数据在存储方 面发生了质的变化，需要算法实现做出相应的调整。 物流配送系统方面，目前最成熟的基于G I S 的物流配送管理系统是E S R I 公司 开发的A r c L o g i s t i c ，但该软件比较昂贵，模型单一，在具体运

27、用时和实际脱节比 较大，不适合中国中小企业的实际情况。国内在物流配送系统方面还处于理论研究 阶段，实际运用开发的不多。在现有的G I S 物流配送系统中，比较成熟的是海尔物 流监控系统，它成功运用了G I S 、G P S 、J 2 E E 和C O R B A 技术，实现了物流运输的 动态决策和监控。其他一些物流配送系统的研究还包括：达明公司物流配送系统n 明、 武汉中商家电连锁集团配送系统n “ 、杭州烟草物流配送系统n 町等。 1 5 研究工作的主要内容与章节安排 本研究从为物流配送企业提供智能决策支持的目标出发，对第三方物流企业物 流配送路径规划问题进行分析，将该问题划分为配送区域划分

28、子问题和单车辆路线 优化子问题，利用V o r o n o i 区划和贪婪混合遗传算法分别求解。最后将G I S 应用 于物流配送路径规划中，利用G I S 强大的空间分析功能来完善物流分析技术，开发 基于G I S 的城市物流配送路径分析系统，从而为物流配送管理者提供科学的决策依 据。 本文将着重从以下几个方面展开研究： ( 1 ) 第三方物流企业车辆路径规划问题的总体解决思路和方法。 ( 2 ) 基于V o r o n o i 的配送区域划分的解决方案( 创新点) 。 ( 3 ) 贪婪混合遗传算法求解T S P 车辆路线优化问题( 创新点) 。 ( 4 ) 基于G I S 的城市物流配送路

29、径分析系统的的设计和开发。 本文内容共分七个部分： 第一章介绍了论文的研究目的和意义，并对国内外的研究现状进行了综述；最 王杰臣，毛海城，杨得志：图的结点一弧段联合结构表示法及其在G I S 最优路径选取中的应用，测绘学 报，2 0 0 0 年第2 期，第2 4 - 2 8 页 王苏男，宋伟，姜文生：最短路径算法的比较，第三届中国人工智能联合学术会，1 9 9 3 ，第1 0 3 一1 0 7 页 陆锋：最短路径算法：分类体系与研究进展测绘学报，2 0 0 1 年第8 期，第4 5 4 8 页 4 硕士学位论文 M A S T E R ST H E S I S 后提出了本文的研究内容和思路。

30、第二章介绍了电子商务和物流配送的基本概念及其相关知识。 第三章对遗传算法进行了简单介绍，并且对遗传算法在解决物流配送路径规划 问题中取得的一些成果进行介绍，如编码、常见交叉算子、常见变异算子等。 第四章介绍了G I S 概念、功能、数据模型和G I S 系统的二次开发模式，最后 探讨了引入G I S 解决物流配送问题的意义和应用方法。 第五章提出了第三方物流企业所涉及到的路径分析问题的解决思路，提出了利 用V o r o n o i 图对配送区域进行区划的方法，并通过贪婪混合遗传算法解决了单车辆 路线优化问题。 第六章提出了基于G I S 的城市物流配送路径分析系统的总体设计思路和详细 的功能

31、设计，利用A R C I N F O R 的M a p O b j e c t s 控件和V B 为开发平台，实现了基于G I S 的城市物流配送路径分析系统。 结束语对研究内容进行概括总结，并指出存在的不足和今后有待完善的部分。 本章小结 本章论述了本文研究的背景、目的和意义，分析了国内外物流配送路径规划 问题以及将G I S 引入物流配送路径规划的研究现状。最后提出了本文的研究内容和 章节安排。 硕士学位论文 M A S T E R ST H E S I S 2电子商务与物流配送 随着信息技术的发展，一种新的企业经营方式一电子商务出现了，它在国内不 断升温，进入2 1 世纪后，更是达到炙手

32、可热的程度，已经逐渐成为推动经济发展 的关键。完整的商务活动，必须通过信息流、商流、资金流、物流等4 个流动过程 有机构成，电子商务的特殊性就在于信息流、商流、资金流可以在互联网上实现， 这属于“虚拟“ 的经济过程，而物流作为最为特殊的一种“流“ ，对于少数商品和 服务来说，可以直接通过网络传输的方式进行配送，如各种电子出版物、信息咨询 服务等，而对于大多数商品和服务来说，物流仍要经由物理方式传输。因此，从一 定意义上说，物流是电子商务的重要组成部分，是信息流和资金流的基础与载体， 也是决定电子商务成败的关键因素。 2 1 电子商务的概念 顾名思义，电子商务n 钔( E l e c t r o

33、 n i cC o m m e r c e ，E C ) 的内容包含两个方面， 即电子方式和商贸活动。电子商务简言之就是利用简单、快捷、低成本的电子通信 方式，不用买卖双方见面就可进行各种商贸活动。但是，对于电子商务还没有一个 统一的定义。比较多的专家学者认为电子商务是利用现有的计算机硬件设备、软件 和网络基础设施，通过一定的协议将电子网络环境连接起来进行各种各样商务活动 的方式。 2 2 电子商务的“物流瓶颈 电子商务的瓶颈问题，是现在谈论比较多的一个问题，实际上，网络安全问题、 网上结算问题虽然很多人称之为“瓶颈“ ，但是实际上，现在的科学技术、管理和 实践都已经证实，这些问题都构不成瓶颈

34、。中国1 0 0 0 多家上市公司，每天几百亿 人民币在网上交易和结算，已经成功运作多年，就已经证实了这些问题都不是所谓 的瓶颈。应该说，唯一的不可回避的是物流瓶颈眩。 在我国电子商务的物流瓶颈具体表现在：配送。配送问题是电子商务的一个 非常重要的制约因素，在电子商务推行的过程中，配送成本过高、配送速度过慢使 电子商务不能获得预期的效果。第三方物流。第三方物流是物流社会化的重要标 志，第三方物流发育不良，配送只能由电子商务企业自己去运作，而不能依托完善 的社会物流系统。这样一来，就必然制约电子商务的规模和专业化的进展。观念。 把网络联结看成是高水平的而把物流看作是可有可无的，因此只注重发展网络

35、和网 上交易而忽视物流，这是形成物流瓶颈的一个关键性的、思想性的因素。物流平 6 硕士学位论文 M A S T E R ST H E S I S 台。基础的物流平台难以提供社会化配送物流的有效动作，在这种情况下，既使解 决物流社会化问题，但是仍然没有办法解决配送的水平和效率问题。 2 3 物流配送概述 2 3 1 物流配送的概念 处于物流末端的物流配送，是挖掘第三方物流系统源泉的突破口，具有提高物 流经济效益，优化完善物流系统，改善服务，降低成本等功能，在物流系统中占有 重要的地位。按照国家质量技术监督局发布的中华人民共和国国家标准“物流术 语”，将配送解释为：在经济合理区域范围内，根据用户要

36、求，对物品进行拣选、 加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。 2 3 2 物流配送的类型 按物流配送的主体可划分为五大类n 叭： ( 1 ) 大型制造商主导型物流配送。指制造商直接将产品零售商的时间、数量等 要求送至零售商的一种配送方式。这要求这类生产商规模较大，有着分布较广的营 销网络。如我国知名企业海尔、联想、保洁、长虹、康佳、T C L 、美的、格力、科 龙等企业纷纷计划在其营销网络的基础上建设自己的物流配送体系，其中海尔、联 想、保洁等已率先通过与第三方物流公司合作进行网上销售与配送业务。 ( 2 ) 大型连锁企业自组型物流配送。连锁企业由于其统一采购和进货、统一

37、库 存和配送、统一管理和经营并且产生巨大规模经济效益而得以飞速发展。在连锁配 送方面，世界5 0 0 强排行第四巨头W a r M a r t 堪称是零售配送的典范。沃尔玛有近 2 0 个大型配送中心，拥有2 0 0 0 多辆长途运输卡车和1 1 万辆以上配送车并拥有私 家通讯卫星和完善的货物采购跟踪、库存、配送等管理系统。 ( 3 ) 大型批发企业主导型物流配送，亦即大型批发商从各生产企业批来商品并 将之批发配送给地域内小型超市、便民店、百货店等中小零售企业。 ( 4 ) 专业物流企业开展的社会化物流配送( 第三方物流企业) ，这主要指诸如中 国邮政以及快递公司等已有准物流企业、由原大型生产

38、厂商、批发、零售企业等储 运部门脱离母体单独分化出去或通过不同企业间储运部门的联合兼并共同成立的 物流公司以及从公路运输、仓储企业转化而来的专门从事社会第三方物流服务企 业。 ( 5 ) 以交通运输业为主题的货物转运型物流配送，指从事交通运输业的航运、 港口、铁路和公路等企业依托港口、货运站、集装箱堆场、公路枢纽、机场及其后 方疏运网络通道将货物迅速地配送给用户，而不是等特约用户自行提取。 7 硕士学位论文 M A S T E R ST H E S I S 2 3 3 物流配送的特点 配送业务在美国、日本等国家开展比较早，近几年来，在我国也有较快的发展。 目前配送已经形成了自身的特点： ( 1

39、 ) 配送不仅仅是送货，而是送货、分货、配货等活动的有机结合体。是从物流 据点到用户之间的一种特殊送货形式。 ( 2 ) 配送是将商流与物流紧密结合，包含了商流活动，也包含了物流中若干功能 要素的一种形式。 ( 3 ) 配送是连接了物流其他功能的物流环节，提高了物流系统的价值增值部分。 ( 4 ) 配送是复杂的作业体系，通常伴随着较高的作业成本，但却能大大降低库存 成本和快速反应商品市场需求变化。 ( 5 ) 配送的全过程有现代化技术和装备的保证。 ( 6 ) 配送在固定设施、搬运设备、运送工具、组织形式、通信信息等方面可集成 系统化的动作体系。 2 3 4 物流配送的作用 相对于整个物流系统

40、而言，配送是系统的终端，是直接面对服务对象的部分。 因此，发展配送，对于物流系统的完善，流通企业和生产企业的发展，以及整个经 济社会效益的提高，无不具有重要的作用。 ( 1 ) 通过集中存储与配送可以实现企业组织的低库存或零库存的设想，降低整个 社会物资的库存水平，并提高社会物流经济效益。 ( 2 ) 通过配送可以解脱出大量的储备资金用来开发企业新的业务，改善企业财务 状况。 ( 3 ) 完善了干线运输中的社会物流功能体系。 ( 4 ) 配送提高了物流服务水平，简化了手续、方便了用户、提高了货物供应的保 证程度。 ( 5 ) 可以使企业扩大商品占有率，提高市场竞争力。 2 3 5 物流配送的功

41、能要素及配送流程 2 3 5 1 物流配送的功能要素啪1 ( 1 ) 备货。备货是配送的准备工作或基础工作，备货工作包括筹集货源、订货 或购货、集货、进货及有关的质量检查、结算、交接等。配送的优势之一，就是可 以集中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作，如果备 货成本太高，会大大降低配送的效益。 ( 2 ) 储存。配送中的储存有储备及暂存两种形态。储备是按一定时期的配送经 8 硕士学位论文 M A S T E R ST H E S I S 营要求形成的对配送的资源保证。暂存是指具体执行日配送时，按分拣、配货要求， 在理货场地所做的少量储存准备，以及在分拣、配货之后，形成的

42、发送货载的暂存。 ( 3 ) 分拣及配货。分拣和配货是配送不同于其他物流形式及特点的功能要素， 是完善送货、支持送货的准备性工作，也是关系配送成败的一项重要支持性工作。 ( 4 ) 在单个用户配送数量不能达到车辆的有效载运负荷时，如何集中不同用户 的配送货物，进行搭配装载以充分利用运载车辆的运能、运力。 2 3 5 2 物流配送的工作流程 为了发挥配送的作用，实现配送效益，配送流程包括拟订配送计划，下达配送 计划，按配送计划确定商品需要量，配送点向仓库运输、分货、包装及财务部门下 达具体配送任务，配送发运，送达等。 ( 1 ) 拟订配送计划。 配送计划的制定是按市场信息为导向、商流为前提、物流

43、为基础的基本思想， 这就是说要以商流信息为主要依据来制定配送计划，并且还要具体考虑以下的条 件：从商流信息的角度，订货合同所提供的信息是制定配送计划的重要依据。 研究分析所需配送的各种货物的性能、运输条件，并在考虑需求数量的条件下， 确定运输方式及相应的运载工具等。根据交通条件、道路等级，以及运载设备、 工具等条件，研究分析并制订运力配置计划，这对充分发挥运载设备、工具效率起 着重要作用。各配送点的运力与货物的资源情况，包括货物的品种、规格、数 量等。 ( 2 ) 下达配送计划与组织实施。 配送计划确定后，按照计划的职能，组织实施。将配送计划所确定的到货 时间以及到货品种、规格、数量通知用户和

44、配送点，以便使用户按计划准备接，使 配送点按计划准备发货。按配送计划确定需要的货物配送量。这一步主要是指 对各配送点按配送计划库存货物保证配送能力情况的审定。如果不符合配送计划要 求，或数量不足，或品种不齐等，需要组织进货。配送点下达配送任务。这里 主要是指各配送点接到配送计划后，向其运输部门、仓储部门、分货包装部门，以 及财务等部门下达具体的配送任务，并由各部门完成配送的各项准备工作等。 ( 3 ) 配送发运与送达。 配送发运。这一步骤是理货部门按要求将各用户所需的各种货物进行分货 与配货，然后进行适当的包装，并印制包装标记和标志，包括用户名称、地址、配 送时间、货物明细，以及输送装卸搬运过

45、程应注意的事项等。同时，还需按计划将 用户货物组合、装车，并将发货明细表交于随车送货人或司机。 9 硕士学位论文 M A S T E R ST H E S I S 送达。按指定的路线将货物送达用户，并由用户在回执上签字。配送工作 完成后，通知财务部门结算。 本章小结 本章简要介绍了电子商务和物流配送的基本概念及其相关知识。 1 0 硕士学位论文 M A S T E R ST H E S I S 3遗传算法在物流配送路径规划中的应用 3 1 遗传算法简介 遗传算法( G e n e t i cA l g o r i t h m ，G A ) 是模拟达尔文的遗传选择与生物在自然环 境中的遗传和进化

46、过程而形成的一种自适应全局优化概率搜索算法。遗传算法是一 种群体型操作，以群体中的所有个体为对象。选择( S e l e c t i o n ) 、交叉( C r o s s o v e r ) 和变异( M u t a t i o n ) 是遗传算法的3 个主要操作算子，它们构成了所谓的遗传操作 ( G e n e t i cO p e r a t i o n ) ，使遗传算法具有了其他传统方法没有的特征。遗传算法的 实现涉及5 个主要因素：参数编码、初始群体的设定、评估函数( 即适应函数) 的 设计、遗传操作的设计和算法控制参数的设定。遗传算法经过多年的发展，已经能 够应用于多种领域：函数

47、优化、组合优化、自动控制、机器学习、图像处理、人工 生命、遗传编程和机器人学等。 3 2 遗传算法的基本结构 遗传算法实际上是一个具有生成测试特点的迭代搜索算法。它首先生成一个可 行解的群体，然后对这些解的质量进行测试( 计算其评价函数值) 。接着，再利用 遗传算子生成新的群体，再对这个新群体进行重新的测试。重复这个过程，直至算 法终止。 算法的基本结构如下： b e g i n t 4 - - 0 ： 初始化群体p ( t ) ： 计算P ( t ) 中每个个体的适应值： r e p e a t 由P ( t ) 应用遗传算子产生下一代群体P ( t + 1 ) ： 计算P ( t + 1

48、) 中每个个体的适应值： t t + 1 ： u n t i l 满足终止条件： 指定算法的执行结果： e n d 王江晴：符号智能与计算智能，湖北科学技术出版社，2 0 0 2 年，第9 3 9 5 页 硕士学位论文 M A S T E R ST H E S I S 由算法的基本结构可知，遗传算法对待求解问题本身一无所知，它所做的只是 对算法所产生的每一个个体进行评价，并通过遗传操作产生新一代的群体，使适应 值好的个体比适应值差的个体有更多的繁殖机会。如此一代代演化下去，直到算法 满足给定的终止条件。 图3 - 1 一个简单的遗传算法流程图 1 2 硕士学位论文 M A S T E R ST

49、 H E S I S 根据这个基本结构，目前已提出了很多具体的描述和实现方法。一个简单的遗 传算法的流程图如图3 - 1 所示。其中M 为群体大小、P c 为交叉概率、P m 为变异概 率、P r 为复制概率、P ( t ) 为第t 代群体。 3 3 遗传算法的特点 同传统的搜索和优化方法相比，遗传算法具有以下特点： ( 1 ) 自组织、自适应和自学习性( 智能性) 。应用遗传算法求解问题时，在编码 方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织 搜索。由于基于自然的选择策略为“适者生存，不适应者被淘汰，因而适应度大 的个体具有较高的生存概率。通常，适应度大的个体具有更适应环境的基因结构， 再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。进化算法 的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性 和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述 问题的全部特点，并要说明