《基于GIS的城市物流配送路径规划研究.pdf》由会员分享，可在线阅读，更多相关《基于GIS的城市物流配送路径规划研究.pdf（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 SA b s t r a c tW i t ht h ef a r t h e rd e v e l o p m e n to fc o m p u t e
4、 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 ml o g i s t i c sd i s t r i b u t i o ni 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 er 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 o no fG I Sp r o v i d e saa d v a n t a g
5、e o u sc o n d i t i o nt ot 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 go 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 i c sc o m p a n y I no r d e rt or e s o l v
6、 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 np l a n n i n gs y s t e m，m o d e l i n gas e t so fo 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 la n a l y s i sf u n c t i o n so fG I Sa n da c
7、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 ot 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 ap a r t i t i o np r o b l e ma n ds i n g l ev e h i
8、 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 na 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 gp r o b l e m，an e wk i n do fh y b r i dg e n e t i ca l g
9、 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 ca 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 mt oi m p r o v et h ee f 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
10、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 nf 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 et h i ss y s t e mu s i n gm a p o b j e c t sA c t i v e Xc o n
11、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 ca l g o r i t h m；g r e e d ya l g o r i t h m：G I SI I硕士学位论文M A S T E R ST H E S I S华中师范大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：
12、所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研究成果。除文中己经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。学位论文作者签名：埘日期：占删；毋月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 S1绪论1 1 研究背景及意义随着经济全球化和信息技术的快速发展，电子商务作为商业贸易领域中一种先进的交易方式在全球迅速蔓延，并对商贸领域中传统的观念和行为方式产生着巨大的冲击和影响。在电子商务环境下，一个完整的商务活动是由信息流、商流、资金流和物流等4 个流动过
14、程有机的构成1。信息流、商流、资金流可以在互联网上实现的，这属于“虚拟 的经济过程，但是它的最终实现还是需要依赖于高度发达的物流配送体系，所以在一定意义上说物流配送是电子商务的重要组成部分，是信息流和资金流的基础与载体，也是决定电子商务成败的关键因素。配送作为物流体系的重要环节，对于整个物流系统的效率起着关键性的作用。在我国现阶段，物流配送的发展还比较落后，基本上还停留在“只送不配 的水平上，造成了配送效率低下，配送成本高，服务质量差，这已成为制约电子商务健康发展的瓶颈乜1。高成本、低效率的物流配送使得在网上瞬间完成的电子商务所节约的时间、费用已变得毫无意义。因此如何实现快速而准确的配送是企业
15、在经营方面必须解决的重要课题。鉴于此，研究运用科学方法合理组织物流配送，建立一个高效率、低成本的物流配送体系来支撑和保障电子商务的快速发展己成为当务之急。随着计算机和网络技术的进一步发展和应用，特别是数字城市，数字地球的进一步深入，地理信息系统(G I S)的社会化，将加速电子商务经济的发展，同时也将在物流配送的实现中发挥其重要作用。G I S 对配送中心和配送点、交通路线等地理信息进行提取、加工，依靠其强大的空间分析和网络分析功能实现配送对象的自动选择、运输路线的动态确定。同时G I S 结合G P S 和G S M 等技术，实现信息采集、命令发送及信息共享，实现物流配送监控的实时智能化，为
16、物流配送决策服务，从而实现企业物流管理的可视化，动态化。G I S、G P S、城市物流配送以及其他相关信息技术的有机结合构建的城市物流配送系统，将使物流配送企业在提高配送速度，降低运作成本，提高信息处理能力、拓宽服务内容方面达到新的水平。1 2 研究的动机与目的X X 公司是一家从事物流配送业务的公司，主要为电子商务网站和电视购物频道承担某市内物流配送业务。公司目前在市内设有四个配送仓库，拥有2 吨左右的货运车辆1 0 多辆，客户覆盖整个市区。由于电子商务环境下的物流配送具有动态的硕士学位论文M A S T E R ST H E S I S特性，消费者可以不受营业时间与地点的限制通过网络进行
17、交易，网络上供需信息不断的在更新，交易与买卖的双方也不停的在变动。对于传统的物流配送方式，将无法在实时订货信息下提供最佳的配送效率。该公司原有配送活动是以人工的经验法则决定，通常是出货人员依据订单将货物装运上车，然后车辆调度人员依据订单及需求点的位置，指派配送路线或是司机依本身经验来完成配送。但是由于配送活动的不断扩张以及道路网的错综复杂，以往人工的方式己渐渐不能负荷目前的需求而且在车辆的监控与调度管理上无法进行，因此需要建立一套现代化的物流配送系统以实现快速、准确、有效的配送路径规戈0 及车辆的调度与监控。本研究根据X X 公司物流配送业务的运作及管理需求，研究开发一套以满足企业的物流配送运
18、作要求为目的基于G I S 的物流配送路径分析的初级系统，实现了配送作业的智能运作和控制。在整个系统的建立和应用中，主要针对企业的实际情况和要求，选择和开发合适的系统架构、运算模型以实现系统在企业中的实际运作。1 3 物流配送路径规划问题的研究现状物流配送路径选择及车辆优化调度是整个物流配送系统优化中关键的环节，也是电子商务活动不可缺少的内容。该问题最早是由D a n t z i n g 和R a m s e r：于二1 9 5 9 年提出的，由于这一问题的理论涉及多学科，应用前景广阔，所以很快引起了运筹学、应用数学、图论与网络分析、物流学、交通运输工程、管理科学与工程、计算机应用等学科的专家
19、、工程技术人员的极大重视。自此一直成为运筹学与组合优化领域的前沿与研究热点，各学科专家对该问题进行了大量的理论研究及试验分析，取得了很大进展。学者B o d i n 于1 9 8 3 年根据物流配送路径规划问题的空间特性和时间特性的相对重要性作了划分：当不考虑时间要求，仅根据空间位置安排线路时称车辆线路安排问题(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
20、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&V S P)。物流配送路径规划问题是组合优化领域中著名的N P(N o n d e t e r m i n i s t i cP 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
21、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 0 9 12硕士学位论文M A S T E R ST H E S I S是国外，物流配送路径规划问题都是一个非常活跃的研究领域。目前国内外用于解决该问题的方法主要分为精确算法和启发式算法两大类。1、精确算法。精确算法是指可求出其最优解的算法，主要有：动态规划法、分枝定界法、切平面法、直接树搜索算法、网络流算法、整数线性规划法等。总的来说，精确算法基于严格的数学手段，在可以求解的情况下，其解通常要优于启发式算法。但由
22、于引入了严格的数学方法，因而无法避开指数爆炸问题，即精确算法的计算量会随着问题规模的增大而呈指数增长。因此在实际中其应用范围很有限。2、启发式算法。启发式算法指通过对过去经验的归纳推理以及实验分析来解决问题的方法，它要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而较基本的模型及算法中寻求其中的联系，从中得到启发，去发现解决问题的思路和途径H 1。启发式方法作为一种逐次逼近的算法，与精确算法相比虽然在精度上不占优势，但在求解大规模V R P 问题时，总可以在有限的时间内，找到满意的次优解可行解，这也是精确算法难以做到的。因此，在实际应用中，启发式算法要更广泛。为此，专家们主要把精力用在
23、构造高质量的启发式算法上。启发式算法主要有：节约法1、扫描法瞄、插入法、分区配送算法口3、禁忌搜索算法嘲、模拟退火算法、人工神经网络算法、遗传算法四1 等。1 4 将Gls 引入物流配送路径规划的研究现状地理信息系统是一种以地理空间数据为基础，实时提供多种空间、动态的地理信息及决策服务的计算机技术系统，它依据地理对象的空间特征及属性特征，建立各种空间分析模型，并在这些模型的基础上使用空间查询和空间分析来对地理数据进行管理并通过对地理数据进行分析加工提取有用的地理信息，从而为辅助决策服务n 训。具体来讲，城市物流配送的基础数据是由点和线组成的城市交通网，将G I S应用于物流分析，主要是指利用G
24、 I S 网络分析功能对这些网状数据进行全面的描述表达，对物流运输网络进行地理分析和模型化，通过一系列物流配送优化算法模型，为物流配送管理者提供科学的决策依据n。在利用G I S 网络分析进行物流配送路径规划研究，多集中于算法和特定的物流配送系统实现的研究。最短路径、资源分配、结点或弧段的游历(旅行商问题、中国邮递员问题)以及最小连通树、最大(小)流等问题，其相应的模型和算法已经比较多，以最短路径算法为例，目前已经有很多最短路径查找算法：乐阳等人写的“D i j k s t r a 最短路径算法的一种高效率实现”、王杰臣等人写的“图的结点一弧段联合结构表示法乐阳：网络分析模型在G I S 中的
25、实现与应用，册士论文，武汉：武汉测绘科技大学，1 9 9 9，第2 l 一3 4 页硕士学位论文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
26、 o g i s t i c，但该软件比较昂贵，模型单一，在具体运用时和实际脱节比较大，不适合中国中小企业的实际情况。国内在物流配送系统方面还处于理论研究阶段，实际运用开发的不多。在现有的G I S 物流配送系统中，比较成熟的是海尔物流监控系统，它成功运用了G I S、G P S、J 2 E E 和C O R B A 技术，实现了物流运输的动态决策和监控。其他一些物流配送系统的研究还包括：达明公司物流配送系统n 明、武汉中商家电连锁集团配送系统n 、杭州烟草物流配送系统n 町等。1 5 研究工作的主要内容与章节安排本研究从为物流配送企业提供智能决策支持的目标出发，对第三方物流企业物流配送路径规
27、划问题进行分析，将该问题划分为配送区域划分子问题和单车辆路线优化子问题，利用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 的城市物流配送路径分析系
28、统的的设计和开发。本文内容共分七个部分：第一章介绍了论文的研究目的和意义，并对国内外的研究现状进行了综述；最王杰臣，毛海城，杨得志：图的结点一弧段联合结构表示法及其在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后提出了本文的研究内容和思路。第二章介绍了电子商务和物流配送的基本
29、概念及其相关知识。第三章对遗传算法进行了简单介绍，并且对遗传算法在解决物流配送路径规划问题中取得的一些成果进行介绍，如编码、常见交叉算子、常见变异算子等。第四章介绍了G I S 概念、功能、数据模型和G I S 系统的二次开发模式，最后探讨了引入G I S 解决物流配送问题的意义和应用方法。第五章提出了第三方物流企业所涉及到的路径分析问题的解决思路，提出了利用V o r o n o i 图对配送区域进行区划的方法，并通过贪婪混合遗传算法解决了单车辆路线优化问题。第六章提出了基于G I S 的城市物流配送路径分析系统的总体设计思路和详细的功能设计，利用A R C I N F O R 的M a p
30、 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 S2电子商务与物流配送随着信息技术的发展，一种新的企业经营方式一电子商务出现了，它在国内不断升温，进入2 1 世纪后，更是达到炙手可热的程度，已经逐渐成为推动经济发展的关键。完整的商务活动，必须通过信息流、
31、商流、资金流、物流等4 个流动过程有机构成，电子商务的特殊性就在于信息流、商流、资金流可以在互联网上实现，这属于“虚拟 的经济过程，而物流作为最为特殊的一种“流，对于少数商品和服务来说，可以直接通过网络传输的方式进行配送，如各种电子出版物、信息咨询服务等，而对于大多数商品和服务来说，物流仍要经由物理方式传输。因此，从一定意义上说，物流是电子商务的重要组成部分，是信息流和资金流的基础与载体，也是决定电子商务成败的关键因素。2 1 电子商务的概念顾名思义，电子商务n 钔(E l e c t r o n i cC o m m e r c e，E C)的内容包含两个方面，即电子方式和商贸活动。电子商务
32、简言之就是利用简单、快捷、低成本的电子通信方式，不用买卖双方见面就可进行各种商贸活动。但是，对于电子商务还没有一个统一的定义。比较多的专家学者认为电子商务是利用现有的计算机硬件设备、软件和网络基础设施，通过一定的协议将电子网络环境连接起来进行各种各样商务活动的方式。2 2 电子商务的“物流瓶颈电子商务的瓶颈问题，是现在谈论比较多的一个问题，实际上，网络安全问题、网上结算问题虽然很多人称之为“瓶颈，但是实际上，现在的科学技术、管理和实践都已经证实，这些问题都构不成瓶颈。中国1 0 0 0 多家上市公司，每天几百亿人民币在网上交易和结算，已经成功运作多年，就已经证实了这些问题都不是所谓的瓶颈。应该
33、说，唯一的不可回避的是物流瓶颈眩。在我国电子商务的物流瓶颈具体表现在：配送。配送问题是电子商务的一个非常重要的制约因素，在电子商务推行的过程中，配送成本过高、配送速度过慢使电子商务不能获得预期的效果。第三方物流。第三方物流是物流社会化的重要标志，第三方物流发育不良，配送只能由电子商务企业自己去运作，而不能依托完善的社会物流系统。这样一来，就必然制约电子商务的规模和专业化的进展。观念。把网络联结看成是高水平的而把物流看作是可有可无的，因此只注重发展网络和网上交易而忽视物流，这是形成物流瓶颈的一个关键性的、思想性的因素。物流平6硕士学位论文M A S T E R ST H E S I S台。基础的
34、物流平台难以提供社会化配送物流的有效动作，在这种情况下，既使解决物流社会化问题，但是仍然没有办法解决配送的水平和效率问题。2 3 物流配送概述2 3 1 物流配送的概念处于物流末端的物流配送，是挖掘第三方物流系统源泉的突破口，具有提高物流经济效益，优化完善物流系统，改善服务，降低成本等功能，在物流系统中占有重要的地位。按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”，将配送解释为：在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。2 3 2 物流配送的类型按物流配送的主体可划分为五大类n 叭：(1)大型制造商主导型物流
35、配送。指制造商直接将产品零售商的时间、数量等要求送至零售商的一种配送方式。这要求这类生产商规模较大，有着分布较广的营销网络。如我国知名企业海尔、联想、保洁、长虹、康佳、T C L、美的、格力、科龙等企业纷纷计划在其营销网络的基础上建设自己的物流配送体系，其中海尔、联想、保洁等已率先通过与第三方物流公司合作进行网上销售与配送业务。(2)大型连锁企业自组型物流配送。连锁企业由于其统一采购和进货、统一库存和配送、统一管理和经营并且产生巨大规模经济效益而得以飞速发展。在连锁配送方面，世界5 0 0 强排行第四巨头W a r M a r t 堪称是零售配送的典范。沃尔玛有近2 0 个大型配送中心，拥有2
36、 0 0 0 多辆长途运输卡车和1 1 万辆以上配送车并拥有私家通讯卫星和完善的货物采购跟踪、库存、配送等管理系统。(3)大型批发企业主导型物流配送，亦即大型批发商从各生产企业批来商品并将之批发配送给地域内小型超市、便民店、百货店等中小零售企业。(4)专业物流企业开展的社会化物流配送(第三方物流企业)，这主要指诸如中国邮政以及快递公司等已有准物流企业、由原大型生产厂商、批发、零售企业等储运部门脱离母体单独分化出去或通过不同企业间储运部门的联合兼并共同成立的物流公司以及从公路运输、仓储企业转化而来的专门从事社会第三方物流服务企业。(5)以交通运输业为主题的货物转运型物流配送，指从事交通运输业的航
37、运、港口、铁路和公路等企业依托港口、货运站、集装箱堆场、公路枢纽、机场及其后方疏运网络通道将货物迅速地配送给用户，而不是等特约用户自行提取。7硕士学位论文M A S T E R ST H E S I S2 3 3 物流配送的特点配送业务在美国、日本等国家开展比较早，近几年来，在我国也有较快的发展。目前配送已经形成了自身的特点：(1)配送不仅仅是送货，而是送货、分货、配货等活动的有机结合体。是从物流据点到用户之间的一种特殊送货形式。(2)配送是将商流与物流紧密结合，包含了商流活动，也包含了物流中若干功能要素的一种形式。(3)配送是连接了物流其他功能的物流环节，提高了物流系统的价值增值部分。(4)
38、配送是复杂的作业体系，通常伴随着较高的作业成本，但却能大大降低库存成本和快速反应商品市场需求变化。(5)配送的全过程有现代化技术和装备的保证。(6)配送在固定设施、搬运设备、运送工具、组织形式、通信信息等方面可集成系统化的动作体系。2 3 4 物流配送的作用相对于整个物流系统而言，配送是系统的终端，是直接面对服务对象的部分。因此，发展配送，对于物流系统的完善，流通企业和生产企业的发展，以及整个经济社会效益的提高，无不具有重要的作用。(1)通过集中存储与配送可以实现企业组织的低库存或零库存的设想，降低整个社会物资的库存水平，并提高社会物流经济效益。(2)通过配送可以解脱出大量的储备资金用来开发企
39、业新的业务，改善企业财务状况。(3)完善了干线运输中的社会物流功能体系。(4)配送提高了物流服务水平，简化了手续、方便了用户、提高了货物供应的保证程度。(5)可以使企业扩大商品占有率，提高市场竞争力。2 3 5 物流配送的功能要素及配送流程2 3 5 1 物流配送的功能要素啪1(1)备货。备货是配送的准备工作或基础工作，备货工作包括筹集货源、订货或购货、集货、进货及有关的质量检查、结算、交接等。配送的优势之一，就是可以集中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作，如果备货成本太高，会大大降低配送的效益。(2)储存。配送中的储存有储备及暂存两种形态。储备是按一定时期的配送经8硕
40、士学位论文M A S T E R ST H E S I S营要求形成的对配送的资源保证。暂存是指具体执行日配送时，按分拣、配货要求，在理货场地所做的少量储存准备，以及在分拣、配货之后，形成的发送货载的暂存。(3)分拣及配货。分拣和配货是配送不同于其他物流形式及特点的功能要素，是完善送货、支持送货的准备性工作，也是关系配送成败的一项重要支持性工作。(4)在单个用户配送数量不能达到车辆的有效载运负荷时，如何集中不同用户的配送货物，进行搭配装载以充分利用运载车辆的运能、运力。2 3 5 2 物流配送的工作流程为了发挥配送的作用，实现配送效益，配送流程包括拟订配送计划，下达配送计划，按配送计划确定商品
41、需要量，配送点向仓库运输、分货、包装及财务部门下达具体配送任务，配送发运，送达等。(1)拟订配送计划。配送计划的制定是按市场信息为导向、商流为前提、物流为基础的基本思想，这就是说要以商流信息为主要依据来制定配送计划，并且还要具体考虑以下的条件：从商流信息的角度，订货合同所提供的信息是制定配送计划的重要依据。研究分析所需配送的各种货物的性能、运输条件，并在考虑需求数量的条件下，确定运输方式及相应的运载工具等。根据交通条件、道路等级，以及运载设备、工具等条件，研究分析并制订运力配置计划，这对充分发挥运载设备、工具效率起着重要作用。各配送点的运力与货物的资源情况，包括货物的品种、规格、数量等。(2)
42、下达配送计划与组织实施。配送计划确定后，按照计划的职能，组织实施。将配送计划所确定的到货时间以及到货品种、规格、数量通知用户和配送点，以便使用户按计划准备接，使配送点按计划准备发货。按配送计划确定需要的货物配送量。这一步主要是指对各配送点按配送计划库存货物保证配送能力情况的审定。如果不符合配送计划要求，或数量不足，或品种不齐等，需要组织进货。配送点下达配送任务。这里主要是指各配送点接到配送计划后，向其运输部门、仓储部门、分货包装部门，以及财务等部门下达具体的配送任务，并由各部门完成配送的各项准备工作等。(3)配送发运与送达。配送发运。这一步骤是理货部门按要求将各用户所需的各种货物进行分货与配货
43、，然后进行适当的包装，并印制包装标记和标志，包括用户名称、地址、配送时间、货物明细，以及输送装卸搬运过程应注意的事项等。同时，还需按计划将用户货物组合、装车，并将发货明细表交于随车送货人或司机。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 S3遗传算法在物流配送路径规划中的应用3 1 遗传算法简介遗传算法(G e n e t i cA l g o r i t h
44、m，G A)是模拟达尔文的遗传选择与生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。遗传算法是一种群体型操作，以群体中的所有个体为对象。选择(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 个主要因素：参数编码、初始群体的设定、评估函数(即适应函数)的设计、遗传操作的设计和算法控制参数的设定。遗传算法经过多年的发展，已
45、经能够应用于多种领域：函数优化、组合优化、自动控制、机器学习、图像处理、人工生命、遗传编程和机器人学等。3 2 遗传算法的基本结构遗传算法实际上是一个具有生成测试特点的迭代搜索算法。它首先生成一个可行解的群体，然后对这些解的质量进行测试(计算其评价函数值)。接着，再利用遗传算子生成新的群体，再对这个新群体进行重新的测试。重复这个过程，直至算法终止。算法的基本结构如下：b e g i nt 4-0：初始化群体p(t)：计算P(t)中每个个体的适应值：r e p e a t由P(t)应用遗传算子产生下一代群体P(t+1)：计算P(t+1)中每个个体的适应值：t t+1：u n t i l 满足终止
46、条件：指定算法的执行结果：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 H E S I S根据这个基本结构，目前已提出了很多具体的描述和实现方法。一个简单的遗传算法的流程图如
47、图3-1 所示。其中M 为群体大小、P c 为交叉概率、P m 为变异概率、P r 为复制概率、P(t)为第t 代群体。3 3 遗传算法的特点同传统的搜索和优化方法相比，遗传算法具有以下特点：(1)自组织、自适应和自学习性(智能性)。应用遗传算法求解问题时，在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。由于基于自然的选择策略为“适者生存，不适应者被淘汰，因而适应度大的个体具有较高的生存概率。通常，适应度大的个体具有更适应环境的基因结构，再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。进化算法的这种自组织、自适应特征，使它同时具有能根据环境变
48、化来自动发现环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结构化问题。(2)全局搜索能力和可选择性。遗传算法属于群体搜索算法。由于能够保持对解空间中不同区域的多个点的搜索，该算法不容易陷入局部最优。算法利用个体的适应值推动整个群体的演化过程，它能够把搜索的注意力集中到搜索空间中最有希望的部分，并能够以很大的概率找到问题的全局最优解。而且，算法的每一次运行都可以提供多个近似解。对于多目标搜索或者需要多个近似解作为参考的求解问题，这是一个非常重要的特性。
49、(3)遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的(i n h e r e n tp a r a l l e l i s m)，即遗传算法本身非常适合大规模并行。最简单的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果)，等到运算结束时才通信比较，选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对并行效率没有太大影响。二是遗传算法的内含并行性
50、(i m p l i c i tp a r a l l e l i s m)。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并芏小平，曹立明：遗传算法一理论、应用与软件实现，西安交通大学出版社，2 0 0 2 年，第9 页硕士学位论文M A S T E RST H E S I S相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模n 成比例的计算，但实质上已进行了大约O(n 3)次有效搜索，这就使遗传算法能以较少的计算获得较大的收益。(4)可扩展性。遗传算法还具有可扩展性，易于同别的技术混合。如将遗传算法和问题的原有算法混合在一起，我们就可以得到一个新的、效率更高的