（计算机应用技术专业论文）第四方物流信息平台设计与实现.pdf

中文摘要 随着世界经济的快速发展和现代科学技术的进步，第四方物流( f o u r t h p a r t yl o g i s t i c s ，简称4 p l ) 成为全球物流业的发展热点，为我国物流业的发展 提供了良好契机。本文针对国内外物流信息系统发展的现状，提出了面向第四方 物流信息系统的解决方案，并对实际应用系统进行了详细的分析，解决了开发过 程中的一些具体问题。 本文在介绍第四方物流业务流程和功能特性的基础上，重点叙述了系统软硬 件的整体设计、详细设计以及实现技术。该系统将物流信息管理平台与呼叫中心 相结合，把计算机网络和电信网络有机的融为一体，使信息传递更加及时、准确， 使物流配送更加高效、科学；运输线路是否合理直接影响到配送速度、成本和效 益，是物流系统中的重要环节，本文采用遗传算法解决了配送中的核心问题一车 辆路径优化问题。 遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适 应的人工智能，它具有思想简单、易于实现、应用效果明显等优点而被应用在车 辆路径问题上。本文认真分析了国内外对v r p 的求解，将遗传算法加以改进， 如采用整数编码、对交叉算子进行改进，保证了种群的多样性，并将其应用到实 际的运输路径优化上。 本文实现了理论知识和实际工程项目的结合。这对实现配送路径优化、降低 成本和提高物流经营管理水平具有重要的参考价值。 关键词： 第四方物流呼叫中心车辆路径遗传算法 a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ew o r l de c o n o m ya n dm o d e mt e c h n o l o g y , t h e f o u r t hp a r t yl o g i s t i c sh a sb e c o m ea g o o do p p o r t u n i t yf o rt h ed e v e l o p m e n to fc h i n e s e i n d u s t r y i nv i e wo ft h er e c e n td e v e l o p m e n to fl o g i s t i c si n f o r m a t i o ns y s t e ma th o m e a n da b r o a d ，t h i sp a p e rs u g g e s t sas o l u t i o nt oi n f o r m a t i o ns y s t e mo ft h ef o u r t h p a r t l o g i s t i c st h a th a sb e e na n a l y z e da tl e n g t h ，a n dap r a c t i c a la p p l i c a t i o ns y s t e mi sa l s o p r e s e n t e di nd e t a i l ，a n ds o m ep r a c t i c a lp r o b l e m sa r es o l v e d t h i sp a p e rb e g i n sw i t ht h ei n t r o d u c t i o no ft h e f o u r t h p a r tl o g i s t i c s ，a n dt h e e m p h a s i si sp u tu p o nt h ea n a l y s i so ft h es o l u t i o na n dt h eo b j e c t i v e so ft h ed e s i g n ，t h e t e c h n i q u e so fg e n e r a la n dd e t a i ld e s i g no fs y s t e m i n f o r m a t i o nm a n a g e m e n tp l a t f o r m w i t hc a l lc e n t e r st a k e sf u l lu s eo fc o m m u n i c a t i o na n di n f o r m a t i o nt e c h n o l o g yt om a k e t h et r a n s m i s s i o no fl o g i s t i c si n f o r m a t i o nm o r ei m m e d i a t e ，a c c u r a t ea n de f f i c i e n t w h e t h e rt h et r a n s p o r t a t i o nr o u t ei sr a t i o n a lw i l la f f e c tt h es p e e d c o s ta n db e n e f i to f d i s t r i b u t i o n ，w h i c hi sa ni m p o r t a n tl i n ki nl o g i s t i c s t h i sp a p e rr e a l i z e st h ec o r e p r o b l e mo ft h ed i s t r i b u t i o n v r pb yu s i n gg e n e t i ca l g o r i t h m g e n e t i ca l g o r i t h mi sa na r t i f i c i a l i n t e l l i g e n c et e c h n o l o g yo fs e l f - o r g a n i z a t i o n a n da d a p t a t i o n ，w h i c hi m i t a t e sn a t u r a l o r g a n i s m s e v o l u t i o n a r yp r o c e s s a n d m e c h a n i s mt os o l v ep r o b l e m s b e c a u s eo ft h e a l g o r i t h m ss i m p l ee l e m e n t s ，a c h i e v i n g e a s i l ya n do b v i o u sa p p l i c a t i o ne f f e c t ，i ti sw i d e l ya p p l i e di nv e h i c l er o u t i n gp r o b l e m o nt h eb a s eo f a n a l y z i n go ft h er e s e a r c ho nv r pi nc h i n aa n da b r o a d t h ei m p r o v e d g e n e t i ca l g o r i t h mu s e si n t e g e rc o d i n ga n di m p r o v e sc r o s s o v e ro p e r a t o r s i nt h i sp a p e r , g e n e t i ca l g o r i t h m sa r ea p p l i e dt ot h ed e s i g np r o c e s sw i t ht h e t h e o r e t i c a la n dp r a c t i c a lp r o j e c t sc o m b i n e d t h i sr i g h tc h o i c eo fv e h i c l er o u t i n gi s g o o df o rr e d u c i n gc o s t sa n di m p r o v i n gl o g i s t i c sm a n a g e m e n tl e v e l k e y w o r d s ：f o u r t h _ p a r t yl o g i s t i c s ，c a l lc e n t e r , v e h i c l er o u t i n g ，g e n e t i c 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤叠盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 秀磊 签字日期： 二砌7 年月13 日 学位论文版权使用授权书 本学位论文作者完全了解基鲞盘堂有关保留、使用学位论文的规定。 特授权叁鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：毒毳 签字日期：知。7 年多月岁曰 导师虢千秒簪 签字日期：l - 力年占月f 卜日 笫一章绪论 1 1 研究背景 第一章绪论 第四方物流( 4 p l f o u r t hp a r t yl o g i s t i c s ) 是一种介于供需企业和运输 企业之间的电子物流平台，同时又是链式管理的结合体。它是通过信息网络、全 球定位系统g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 、地理信息系统g i s ( g e o g r a p h i c a l i n f o r m a t i o ns y s t e m ) 、安全认证中心等方面的结合，并将管理运筹学和计算机技 术有效融合起来的物流平台。 随着现代信息技术的不断发展和市场竞争的日益激烈，第四方物流成为了企 业降低物流成本、改善供应链结构、提高对顾客响应的速度和缩短生产周期的战 略手段。国际上大部分著名的管理咨询公司都把第四方物流作为它们咨询业务的 拓展，一些著名的第三方物流提供商也努力使自己成为第四方物流的主体。第四 方物流平台的优势在于它通过现代信息技术将信息综合起来，能够科学地设计物 流方案，加大了更为方便的软件投入，为客户提供了更多的增值服务。 未来几年里，由于我国经济发展过程中的一些独特机遇，我国将成为全球制 造基地，迫切需要建立起与之配套的强大物流配送体系。作为能对客户的制造、 市场及分销数据进行全面在线连接的一个战略伙伴，第四方物流必将成为我国物 流产业进一步发展和提升的助力器，而并得到广泛应用。本文课题即在此背景 下提出。 1 1 1 第四方物流的定义 二十世际九十年代在欧美国家，为了减少成本和提高效率，大部分企业将自 身的物流业务外包，从而产生了第三方物流3 p l ( t h i r dp a r t yl o g i s t i c s ) ，但随 着物流市场国际化进程的加快，第三方物流企业由于其自身缺乏市场所需的综合 技能、集成技术以及全球扩展能力，而无法满足客户的全部要求，在供应链管理 中所体现出的实际作用与理想目标相比有较大差距，出现了物流瓶颈。正是在第 三方物流发展过程中出现了这种不协调的背景与条件下，随着信息技术和电子商 务的迅猛发展，一个全新的物流理念第四方物流被世界物流界普遍认同。 第四方物流( 4 p l ) 概念首先是由安德森咨询公司提出，并将其定义为“一 个调配和管理组织自身的及具有互补性的服务提供商的资源、能力与技术，来提 供全面的供应链解决方案的供应链集成商”。从定义上来看，第四方物流是有领 导力量的物流提供商，它可以通过整个供应链的影响力，提供综合的供应链解决 第一章绪论 方案，为其顾客带来更大的价值；它不仅控制和管理某项特定的物流服务，而且 对整个物流过程提出解决方案，并通过电子商务将这个过程集成起来。它是在主 要委托客户企业与服务供应商之间通过签订合资协议或长期合作协议而形成的 组织机构。第四方物流是委托客户企业与服务供应商之间唯一的中介，它应拥有 全面的综合管理和协调能力以及超常的整合能力。 按照安德森咨询公司的说法，4 p l 存在3 种可能的应用模式： ( 1 ) 知识密集型模式，也称“协助提高者”，第四方物流为第三方物流工作， 提供第三方物流缺少的技术和战略技能； ( 2 ) 方案定制模式，也称“方案集成商”，第四方物流为货主服务，是所有 第三方物流提供商及其它提供商联系的中心； ( 3 ) 整合模式，也称“产业革新者”，即第四方物流通过对同步与协作的关 注，对众多的产业成员运作供应链。 1 1 2 第四方物流信息平台概述 第四方物流与传统物流的最大区别在于“信息”，第四方物流以互联网为基 础，结合管理运筹学与现代信息技术，将世界各地的业务伙伴联结起来置于同一 个信息管理平台上，确保物流信息快速、可靠地传递，同时结合运筹管理学知识 对供应链进行合理的管理，减少各环节的成本，做到更加高效、更为科学的物流。 可见，第四方物流的优势就在于信息管理平台的建立。 第四方物流信息管理平台主要涉及的信息技术有条码( b a rc o d e ) 技术，电 子数据交换技术( e d i e l e c t r o n i cd a t ai n t e r c h a n g e ) ，全球定位系统g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) ，地理信息管理系统g i s ( g e o g r a p h i c a l i n f o r m a t i o ns y s t e m ) ，射频技术r f ( r a d i of r e q u e n c y ) 。此外，结合中国的实 际国情还可能涉及到计算机电信集成( c t i c o m p u t e rt e l e c o m m u n i c a t i o n i n t e g r a t i o n ) 技术等。 1 1 3 我国第四方物流的发展现状 随着第四方物流被全球物流界普遍认可，国内企业也逐渐认识到2 1 世纪的 竞争将不再是单个企业的竞争，而是供应链和供应链之间的竞争，从而开始办理 自己的第四方物流企业，例如2 0 0 2 年1 2 月1 2 日大众日报报道，海尔集团 物流有限公司与寰宇空港物流签订了北京首都机场的物流合作项目协议，标志着 海尔物流已进入第四方物流领域。但是与发达国家的物流业相比，中国的物流业 还尚处于起步阶段，总体发展水平还相对较低，主要问题在于：第一，我国物流 企业缺乏良好的信息共享平台，无法实现信息共享；第二，第四方物流缺乏客户 第一章绪论 的认可和信任，这一点又是以良好信息平台为基础的。 冈此，信息技术的进步，以及由此形成的信息流能否更好的与物流保持同步， 已成为检测物流服务水平的关键因素之一。要想成功的运作一个第四方物流，必 须靠一个良好的信息平台来支撑，这样才能高效的利用整个供应链和各参与者的 物流资源呛1 。这样的平台不仅要实现信息共享，还要充分地结合物流运筹学和信 息技术等。只有建立这种具有足够供应链管理能力和信息共享能力的信息管理平 台，才是解决当前我国物流问题的关键。 1 2 选题背景和论文任务 本文课题的提出是在对国外著名企业第四方物流平台案例研究的基础上，针 对我国当前物流业所存在的不足及信息业发展的特殊条件提出的改进系统构架 方案： 1 ) 将整个信息管理平台分为两个相对独立的子系统：呼叫中心业务平台和物流 业务平台，两个子系统之间通过网络层传递消息来相互通信。而且每个子系 统也都采用了模块化设计方案，根据业务逻辑的不同构建不同的业务模块， 增强了系统的稳定性。同时也方便客户根据具体需要对业务模块进行修改， 提高了系统的重用性。 2 ) 主体结构采用c s 结构，并采用图形化界面的管理方式，提供了系统参数设 置、系统状态监听、数据库维护、物流路线管理等功能，最大程度上简化了 设备管理人员和业务管理人员的工作。 3 ) 采用无线传呼和网络广播相结合的方式实施物流信息的共享，实现了信息的 实时交互。 本文在为天津市某物流信息咨询公司开发的物流信息管理平台上实现。课题 内容涉及到c t i 、计算机网络通信、无线传呼、数据库、面向对象的模块化编程 等技术。论文主要完成了以下任务： 1 ) 根据用户需求和业务流程，进行信息管理平台的体系结构、网络结构和软件 结构的设计。 2 ) 采用遗传算法的相关原理，对“多旅行商”问题设计相关算法进行求解，从 而解决单点到多点的最佳物流路径求解问题。 3 ) 完成对系统各模块的设计和实现，其中应用到c t i ，遗传算法，u d p 、t c p i p 网络协议，无线传呼、数据信息检索、信息加密等多种技术。 第一章绪论 1 3 论文的组织结构 本文以实际工程项目为背景，讨论了一种有效的第四方物流信息管理平台的 设计与实现过程。全文共分为六章，主要内容如下： 第一章绪论，简要介绍了第四方物流的分类、优势及其在我国的发展现状， 说明了建立信息平台的迫切需要，这一部分为本文后面的内容提供了必要的研究 背景。 第二章相关技术，介绍v r p 问题的相关求解算法和计算机遗传算法的相关知 识，简要介绍a d o n e t 技术和网络协议。 第三章系统的总体设计方案，从项目中的客户现状和业务需求分析入手对系 统的体系结构、网络结构和软件结构作了总体设计。 第四章呼叫中心平台子系统的设计与实现，着重介绍呼叫中心的设计方案和 部分模块的设计和功能。 第五章信息业务平台的设计和实现，介绍运用遗传算法解决优化物流路径的 具体实现，描述系统各模块的具体实现过程，并对涉及到的关键技术进行说明。 第六章总结与展望，对系统的进一步优化提出了作者的意见，结合我国国情， 展望第四方物流信息平台未来的发展方向。 第- 二章相关技术 第二章相关技术 第四方物流信息管理平台的主要任务就是对其整个物流供应链进行科学化 的管理。而物流配送是物流中的一个重要的直接和消费者相关的环节，也是物流 供应链的最后环节，研究运用科学方法合理组织物流配送，以提高企业的服务质 量、减少库存、降低经营成本、增加经济效益是十分必要的。其中的车辆路径问 题( v r p ，v e h i c l er o u t i n gp r o b l e m ) 则是物流配送优化中的关键问题，与电子商 务活动中不可缺少的内容之一。 2 1v r p 问题的提出 物流活动中的运输，是指为了克服物品的空间障碍所进行的场所移动。制定 最优运输计划，包括对运输工具、运输线路、运输时间等的最佳选择。当车辆不 满载或者客户的需求为多次、小批量时，为了节约费用，车辆一次装载的货物包 括若干个客户的需求量，并且在一次运输过程中依次对这些客户进行访问，此类 运输问题称为配送问题b 1 。物流配送是在集货、配货基础上，按货物种类、品种 搭配、数盘、时间等的要求所进行的运送，是“配”和“送”的有机结合n 1 。物 流配送问题主要包括以下几个部分： 1 集货作业，从生产工厂进货、并集结的过程。 2 配货作业，即货物的分拣作业，并根据各用户的不同要求，在配送中心将所 需要的货物挑选出来的过程。 3 配装作业，将不同质量和体积的货物装载到不同载重和容积的车辆上的过程。 由于其自身的特点和配送货物的质量和体积的差异，在配送货物时要考虑车 辆的载重和容积，以使车辆的载重和容积得到充分的利用，同时还要考虑一 趟送几户的问题。 4 配送路线的确定，在配送过程中如何科学的确定配送路线，这就是我们所说 的v r p 问题。 优化配送路线对3 p l 供应商而言，可以提高配送效率，尽可能的降低配送成 本，可以准时、快速地把货物送到客户的手中，能极大地提高供需客户的满意度， 有利于供应商提高效益；对于供需客户而言，可以减少运输费用，减少货物运输 中出现的风险；对社会而言，它可以节省运输车辆，缓解交通紧张状况，减少噪 声、尾气排放等运输污染，为保护生态平衡、创造美好家园做出贡献。 第二章相关技术 2 2v r p 问题的概述 2 2 1 多旅行商问题的描述 旅行商问题( t s p ，t r a v e li n gs a l e s m a np r o b l e m ) 的形象化描述是指一个 商人从驻地出发，想要到多个城市推销商品，所有的城市至少要访问一次且仅一 次，最后回到原地。问题的目标是帮助这个商人找到最短的路径，使得总的旅行 距离( 或时间、费用等) 最少。 t s p 以图论的形式描述为：给定图g = ( v ，a ) ，其中v 为顶点集，a 为个定点 相互连接组成的边集，设d = d o ) 是由顶点i 和顶点j 之间的距离所组成的距离矩 阵，要求确定一条长度最短的h a m i l t o n 【旦i 路，即当且仅当一次遍历所有顶点的最 短距离6 m 。 t s p 是一个典型的组合优化问题，并且是一个非线性问题( n p ，n o n i n e a r p r o b l e m ) 完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式， 并且已成为各种启发式的搜索、优化算法的问接标准。因此，快速、有效地解决 t s p 有着重要的理论价值和极高的实际应用价值汨1 。但是由于其所谓的“组合爆 炸”现象，对其的准确求解是十分困难的。例如，对于n 个城市的t s p 问题，状态 数量随着问题规模呈超指数增长。n = 2 0 的时候，使用穷举法求解，即使计算机 每秒能够处理1 亿种排列，也需要大约几百年的时间。 多旅行商问题( m t s p ) 是旅行商问题的推广和深化，是指多个旅行商要到多 个城市推销商品，要求所有的城市至少要访问次且只有一次，最后回到原地。 问题的目标是帮助商人安排旅行路线，使这些旅行商的总旅行距离( 或时间、费 用等) 最少。 m t s p 以图论的形式描述为给定图g = ( v ，a ) ，其中v = 0 ，1 ，1 ) 为顶点 集表示旅行商需要经过的需求点，a 为各定点相互连接组成的边集。设d i i 表示顶 点i 和顶点j 之间的距离，若旅行商k 通过( i ，j ) ，贝1 j d i j k = d i i ；若旅行商k 不通过( i ， j ) ，贝, u d i j k = o 。因此所有m 个旅行商经过路径之和的最短距离z ，如( 2 1 ) 式1 ： ，所、 z = m i n i m x d 驰l ( 2 1 ) l 一一一 v 4 l i = o 户ok = l 基于t s p 和m t s p 的问题特性，构造型算法成为最先开发的求解算法，如最近 邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但由于构造性 算法优化质量较差，迄今为止已开发出许多性能更好的改进型搜索算法阻1 ，主要 有：模拟退火算法、禁忌搜索算法、h o p f i e l d 神经网络优化算法、蚁群算法、混 合优化算法等。 第二章相关技术 2 2 2v r p 问题的提出及概述 物流配送车辆优化路径问题的原型就是旅行商问题，它最早是由d a n t z i g 和 r a m s e r 于1 9 5 9 年首次提出，是对一系列特定位置和需求量的客户点，调用一定 数量的车辆，从中心仓库出发，选择最优的行车路线，使车辆有序的访问各客户 点，在满足特定的约束条件( 如客户需求量、发送量、时间限制、车辆容鼍限制) 下，使得货物尽快到达客户点，并使总费用最低。v r p 问题实际是具有某些特定 条件的t s p 或m t s p 问题，例如在每个城市添加了一个固定的需求量，同时每个 旅行商都有一定的容量限制等等。 图2 1 ( a ) 、( b ) 分别显示了在满足车辆运载的容量下，传统物流车辆路径 与基于v r p 问题的配送物流车辆路径的对比，可见，v r p 问题的解决将多个用户 联合在一条线路上，并为车辆选择优化绕行次序，可以大大满足降低成本提高效 率的要求。 ( a ) 传统物流路径( b ) v r p 物流路径 图2 1 配送中心向9 个物流客户点的车辆运输路径比较 从图论的角度来看，v r p 问题可以描述为基于图g = ( v ，a ) ，其中v 代表顶点 集合，v = v o ，v 1 ，v 。) ，e 代表连接两两项点的边的集合，e = ( v i ，v j ) i v i ， v j v i = o ，1 ，n ；j = o ，l ，n ；i c j ) 。在e 上可以定义一个非负的成本矩阵d = d i i ) ， 此处d i i 代表从顶点i 到顶点j 的成本u 刨。 v r p 问题根据不同的标准可以分为不同的类别。根据车场或配送中心等的数 目份，有单车场问题和多车场问题；根据货运任务的性质，有纯装问题、纯卸问 题或装卸混合问题；根据车辆是否有容量约束，可分为有容量约束的v r p 问题和 无容量约束的v r p 问题；根据运输车辆的种类多少，可分为单车型的v r p 问题( 所 有车辆容量相同) 和多车辆型的v r p 问题( 车辆的容量不全相同) ；根据货运任 第二章相关技术 务的完成是否有时问要求，又可分为软时间窗问题、硬时间窗问题和无时间窗问 题。由于v r p 的原型是t s p 和m t s p ，其差别在于v r p 问题是有约束条件( 例如 车辆的最大容量、运输时间的严格规定等) 的t s p 或者m t s p 问题，所以v r p 问 题也是n p 完全问题，很难求出精确解，并且更为复杂。 2 2 3v r p 问题的相应算法 v r p 问题由d a n t z i g 和r a m s e r 提出以后，就有不少学者对它的计算复杂性进行 了研究。l e n s t r a 和r i n n o o yk a n 在1 9 8 1 年的文章中n 对v r p 问题的计算负载性进 行了综述；k a r p 在1 9 7 2 年证明了旅行商问题和有向旅行商问题为n p 难题； p a p a d i m i t r i o u s 在1 9 7 6 年证明了m t s p 为n p 难题；s a v e l s b e r g h 和s o l o m o n 在1 9 8 6 年提出有时间窗约束的v r p 比一般的v r p 更为复杂；并且早在1 9 8 3 年b o d i n 和 g o l d e n 等人在他们有关v r p 问题的综述文章中就列举了7 0 0 余篇文献u 引。由于这 一个问题的理论涉及许多学科，许多实际问题的理论抽象都可以归结为这一类问 题，应用前景广阔，例如物流配送问题或者a t m 网路由规划问题，所以很快引起 了运筹学、应用数学、组合数学、图论与网络分析、物流科学、管理科学与工程、 计算机应用技术等学科的学者及工程技术人员和管理者的极大重视，成为了运筹 学与组合优化领域的前沿与研究热点问题。目前，国内外研究用于解决v r p 问题 的现代数学方法主要分为以下几类： 1 精确算法。主要针对v r p 图模型和数学模型的求解方法，引入了严格 的数学手段，运用线性规划和非线性规划等数学规划技术来求最优策略。算 法主要包括制定下界及相关分支定界算法、k 度中心树及相关算法、动态规 划和整数规划等。精确算法虽然在可以求解的情况下是优于其他算法的，而 且在实际中应用广泛，但是其计算精度要求高，只能有效求解小规模的v r p 问题，随着节点数n 的逐渐增加和调度条件的多目标要求，一般很难精确求 出v r p 问题的最优解，另外应用精确算法很难真实处理一些物流配送的相关 数据，例如道路流量和堵塞情况等即时交通情况，这样在物流过程中不能体 现出运输环节的重要影响，这些都必然使分析结果的可信度受到影响。 2 启发式算法n 引。它是由j h o l l a n d 教授在1 9 7 5 年提出来的一种从生 物进化规律中得到灵感和启迪的自适应全局随机搜索方法u4 l 。主要通过经验 法则来求取运输过程满意解的数学方法，它能够更好地满足描绘问题，主要 算法包括：节约法、两阶段法、扫描法、并行算法、亚启发式算法等。各种 启发式算法的区别主要在于收敛的速度和程度的不同。亚启发式算法主要有 禁忌搜索算法、模拟退火算法、遗传算法、神经网络算法等。节约算法是目 前针对v r p 问题提出来的启发式算法中最广为人知的一种，运算速度较快，但 第二章相关技术 是存在组合点零乱，边缘点难以组合且只适合求解小型、简单的v r p 等缺点： 禁忌搜索是对局部邻域搜索扩展后的一种全局逐步寻优算法，虽然有优越性， 但是运行时间较长，效率较低；模拟退火算法是由k i r k p a t r i c k 在1 9 8 3 年提 出来的，将路径规划的目标函数视作能量函数，模拟物理学中固体物质的退 火处理而形成的，该方法实用领域较多，但是要求反复求解才能得到满意的 截获，不便于实际应用；遗传算法的基本原理是通过多个个体间的选择、交 叉、变异等操作对解空间进行搜索，目前遗传算法在v r p 问题中的应用已经取 得了一定成果，已有一些文献利用遗传算法对v r p 进行求解，但是有时候要得 到问题的全局最优解需要以延长计算时间为代价；而神经网络的发展促进了 t s p 的较好解决，但在v r p 中的应用还刚刚开始。 3 模拟算法。利用数学公式、逻辑表达式、图标图形等抽象概念表达实 际运输系统内部状态和输入输出的关系，以便通过计算机对模型进行实验， 通过实验取得改善运输系统或者设计新运输系统所需的信息，但模拟办法在 模型构造、程序调试及数据整理方面的工作量较大。 4 交互式优化法。它是一种把人为的知识经验结合到问题的求解过程中 去的方法。其思想足有经验的决策者应具有确定和修改参数的能力，并且根 据知识直观感性，把主观的估计加到优化模型中，但这个方法明显的缺陷就 是需要决策者相当强的个人能力，人为因素太强。 下表是各种算法的优缺点的对比，从表中我们可以看到启发式算法的优势， 虽然得到的未必是最优解，但是可以高效率地得到高精度的解，且易于应用到各 种实际问题中。近年来一些新的启发式算法被采用，已经为解决大规模、多目标 车辆调度问题提供了新的辅助手段。在下面的研究里，我们将详细介绍最近常用 的启发式算法中的遗传算法。 表2 - iv r p 问题相关算法的优缺点对比 求解算法精确度收敛速度程序实现适用问题 数学规划法精确解慢较难简单、确定 启发式算法近优解较快易较复杂、确定 模拟法 较优解 慢 难 复杂、不确定 交互式方法满意解快易 较复杂、确定 第二章相关技术 2 3 遗传算法 2 3 1 遗传算法的基本概念 生命科学与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发展 的一个显著特点，遗传算法的蓬勃发展就体现了科学发展的这一特点和趋势。随 着世界范围形成的进化计算热潮，计算智能已经成为人工智能研究的一个重要方 向。 遗传算法，简称g a ( g e n e t i ch l g o r i t h m ) 是一类借鉴达尔文的自然选择和 自然淘汰生物进化机制的随机搜索算法，由美国j h o l l a n d 教授首先于1 9 7 5 年提 出的，他和他的研究小组利用生物进化特性来模拟生物进化论中的“优胜劣汰、 适者生存 的自然法则，即若当前个体的性能越优，则越容易传到下一代，从而 将个体的优良基因继承下去，直至搜索到近似最优解或者满意解。围绕遗传算法 进行研究的宗旨有两个：一是抽取和解释自然系统的自适应过程，二是设计具有 自然系统机理的人工系统。为了更好的理解遗传算法的基本思想，我们将先详细 介绍遗传算法涉及的几个主要概念n 引。 1 遗传。它是指父代与子代之间，在性状上存在的相似现象。 2 变异。它是指父代和子代之间，以及子代个体之间，在性状上或多或少存在 的差异现象。在生物体内，遗传和变异的关系十分密切，一个生物体的遗传 性状往往会发生变异，而变异的性状有的可以遗传。 3 染色体。染色体是生物学中的概念，在遗传算法中有两种表示模式：基因型 和表现型。表现型对应问题的候选解或参数集，基因型对应遗传算法直接处 理的一种数据结构如数组等。个体或染色体是种群p ( t ) 中的元素，在遗传算 法中通常用一个所谓的串表示：x = x l ( t ) ，x 2 ( t ) 。其q b x i ( t ) 是串x 的基本单元， 称为基因，i 称为基因数，染色体上的一个有效信息段叫基因组。 4 种群( p o p u l a t i o n ) 。记为p ( t ) ，即为个体的集合，遗传算法是从随机选择的 多个初始解开始进行迭代搜索，这多个初始解的集合以及每次迭代生成的一 组新解就构成了一个种群。 5 种群规模n 。它表示群体p ( t ) 中所含个体的数量，当n 过小时，可以提高算 法的运行速度，但是降低了种群的多样性，有可能引起遗传算法的早熟现象， 而当1 3 过大时，又会降低算法的运行速度，所以一般将取值设在1 0 到1 6 0 之间。 6 进化代t 。表示种群的代数。 7 编码和解码。由于遗传算法不能直接应用于实际的解空间，所以需要将解空 间转换到遗传空间。编码就是指从表现型映射到基因型，从而将实际的解空 第二二章相关技术 间映射为相应的遗传空间；解码就是指从基因型映射到表现型，从而将遗传 空问映射到实际的解空问。 8 。适应度。生物学上，适应度是用来量度某个物种对于其环境的适应程度。遗 传算法中，用它来度量种群中各个个体在优化计算中有可能达到或接近于找 到最优解的优良程度。度量个体适应度的函数叫做适应度函数，适应度用来 评价个体优劣的程度，是遗传操作的依据，并指导遗传算法的搜索方向。基 本遗传算法按与个体适应度成正比的概率来决定当前种群中每个个体遗传到 下一代种群中的机会有多少。 9 遗传算子。它作用在基因串上，是模拟种群进化过程的主要手段，常用的遗 传算子有三种：选择算子、杂交算子、变异算子，其中杂交算子又分为点式 杂交和杂交交叉，表2 - 2 简要介绍了各个算子的操作和常用方法。 表2 - 2 遗传算法中遗传算子的对比表i 1 6 j 遗传算子操作方式常用的方法 按照个体适应度的大小选择赌盘选择法、随机联赛选择 进入下一代的个体，或者选择 法、最佳个体保留选择法、精 选择算子 直接进行交叉变异的个体英策略等等 将两个相对配对的染色体按单点杂交、双点杂交、均匀杂 杂交算子 照某种方式相互交换部分基 交、顺序杂交、循环杂交等等 因形成新的个体 将个体中某个或某些基因按基本位变异、均匀变异、倒置 小概率扰动，维持种群的多样变异、对换变异、k 交换变异 变异算子 性，增强遗传算法的全局搜索等等 能力 选择算子即从当前群体中选择适应度高的个体以生成交配池的过程，它是自 然选择，生存竞争的动力，个体适应值是选择的主要依据。适应值大的个体 会不断在种群中繁衍，而适应值小的个体则会逐渐被淘汰，适应值大的个体 繁殖到下一代，为杂交和变异提供了良好的基础。 杂交算子是模拟自然界繁殖的基因重组过程，起作用是将原有的优良基因遗 传给下一代个体，并生成包含更复杂基因结构的新个体。 变异算子模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改 变染色体的结构和物理形状。它的作用是使种群成为一个开发的系统。选择 第二章相关技术 算子和杂交算子不会产生新的基因，而变异算子可以使种群内的基因发生随 机的变异，使利，群内不断加入新的基因，弥补因为选择算子的筛选作用所引 起的基因缺失，同时也使种群成为一个开放的系统。 2 3 2 遗传算法的基本结构 遗传算法可以形式化的描述为：g a = ( p ( 0 ) ，n ，l ，s ，g ，p ，f ，t ) 。其中： p ( o ) - - - ( a j ( o ) ，a 2 ( o ) ，a 。( 0 ) ) i “，表示初始种群，a i ( o ) 表示初始种群中的个体。 n 表示种群中含有个体的数量； i = b 1 = 0 ，1 ) 1 表示长度为1 的二进制串全体，称为位串空间，1 表示二进制串的 长度； s ：i “一i “，表示选择策略； g 表示遗传算子，它通常包括选择算子o ，杂交算子o c ，变异算子o m ； p 表示遗传算子的操作概率，包括选择概率p ，、杂交概率p 。以及变异概率p m ： f ：i r + ，是适应函数； r ：i + 一 0 ，1 ) ，是中止准则。 2 3 。3 遗传算法的基本组成部分口刀 传统的遗传算法由编码方法、控制参数、适应度函数和遗传算子四部分组成。 1 编码方法，是遗传算法g a 的基础。g a 不是对研究对象直接进行讨论，而是 通过某种编码机制把对象统一赋予由特定字母按一定顺序排成的串，在目标 问题实际表示与遗传算法的染色体位串结构之间建立联系，即确定编码和编 码运算。主要是二进制编码、序列编码、树编码、自适应编码等等。 2 控制参数，在遗传算法的运行过程中，存在着对其性能产生重大影响的一组 参数，主要包括染色体的位串长度m 、群体规模n 、杂交概率p 。、变异概率p m 等 等。 3 适应度函数，描述每一个个体的适应程度。优胜劣汰是自然界进化的原则， 适应度就决定了个体在此环境下的生存能力。对于优化问题，适应度函数和 目标函数可以建立一个单调函数，可以分为最小化问题和最大化问题。 4 遗传算子，是模拟遗传过程中发生繁殖、杂交和突变现象的载体，由此可以 分为三种，分别就是以上所说的选择算子o r 、杂交算子o 。和变异算子o m ，遗 传算子的选择也是遗传算法好坏的关键。 2 3 4 遗传算法的基本流程 遗传算法的基本流程参见图2 - 2 ，算法设计应在适用性、可靠性、收敛性、 第二章相关技术 稳定性等原则下对g a 算法的编码方案、适应性函数、算子选择、控制参数选择 等改进措施进行设计，基本步骤如下： 步骤1 ：构造满足约束条件的染色体，确定编码方案，通过编码将解表示成 适当的染色体，选择何种编码表示有时会对算法的性能、效率等产生很大的影响。 步骤2 ：设定控制参数，随机产生初始群体，其数量要适当选择，参数的设 置和数量的合适都会对算法性能产生影响。 步骤3 ：计算每一个染色体的适应度，适应度是反应染色体优劣的唯一指标， 遗传算法就是要寻求适应度最大的染色体，因为适应值最大的解有着较高的存活 概率。 步骤4 ：使用选择、杂交和变异算子产生子群体，它们是遗传算法的基本算 子。选择体现了优胜劣汰的自然规律，从中选择最好的n 个个体作为父代重新繁 殖下一代群体；杂交是两个染色体之间随机交换信息的一种机制，以事先给定的 杂交概率p 。在选择出的个体中任意选择两个个体进行杂交运算，产生两个新的个 体，重复此过程直到所有要求杂交的个体杂交完毕；变异增加了遗传算法找到最 优解的能力。根据需要可以用事先给定的变异概率p 在n 个个体中选择若干个体， 并按一定的策略对选中的个体进行变异运算。 步骤5 ：重复步骤4 ，直到满足停止条件，每一次进化过程就产生新一代的 群体。群体内个体所表示的解经过进化最终达到最优解或者近似最优解；若不满 足，返回步骤4 。 第二章相关技术 0 么三滁是 输出结果 o 丫否 上 厂、 复制 ( 结束 ) 杂交 i 变异 i 图2 - 2 遗传算法基本流程图 2 3 5 遗传算法的应用领域以及特点 目前遗传算法在规划设计、优化组合、机器学习、图像处理、信号处理、数 据挖掘等许多领域都有广泛的应用，主要在于g a 算法有着以下几个不同于传统 优化算法的显著特点： 1 遗传算法不直接作用于参变量上，而是在编码空间内执行，不受函数约束条 件的限制，对所求问题没有太多的数学要求： 2 遗传算法的搜索始于一个种群，可以同时搜索多个区域，适合于大规模并行， 有较好的全局搜索能力； 第二章相关技术 3 遗传算法只使用适应度函数，不采用其他的推导和函数，对问题的依赖性较 小。 4 采用基于自然选择的策略，适应值大的个体具有较高的生存概率，进行交叉 和变异等遗传操作时就可能产生与环境更为适应的后代来； 5 遗传算法使用的选择、杂交、变异等算子都是随机操作，而不是确定规则， 这样使得算法具有更强大的搜索能力，可以高效地找到最优解，同时采用3 种不同作用的基本算子进行搜索，解随时间的增加趋于稳定，不受初始解的 影响，不因实例的不同而蜕变。 2 4 网络传输协议 数据传输协议的作用是允许创建和维护与远程计算机的连接，连接的两台计 算机就可彼此进行数据传输。现在主要的网络协议有t c p 和u d p 两种协议，u d p 是 一个简单的面向数据报的运输层协议：进程的每个输出操作都正好产生一个u d p 数据报，并封装成一份待发送的网络层( i p ) 数据报，它是无链接、不可靠的。 而t c p 虽然使用相同的i p ，却向应用层提供不同的服务，它提供了一种面向连接、 可靠的字节流服务引。t c p 提供可靠的运输层，使用的方法之一就是确认从另一 端收到的数据，但数据和确认都有可能会丢失，设置定时器的办法不能够很好地 解决这个问题。t c p 与u d p 的区别在于： 1 t c p 基于连接，而u d p 基于无连接。 2 对系统资源的要求上，t c p 要求系统资源较多，而u d p 要求相对较少。 3 u d p 程序结构较t c p 简单。 4 t c p 基于流模式，u d p 基于数据报模式。 5 t c p 保证数据正确性，通过接收端发送的a c k 包确认数据已经发送成功，而 u d p 却不发送，可能丢包；同时，t c p 保证数据顺序，u d p 不保证。 关于传输中使用t c p 协议还是u d p 协议，业界争论很多。鉴于该4 p l 公司用 户较多，客户端在线的情况比较复杂，大多数客户上网的方式都是用调制解调器 或者a d s l 上网，因此本文选用u d p 协议作为业务信息数据库与客户端交换系统 的传输协议更为合适，而且能够减少网络负载。 2 5m s8 0 l2 0 0 0 $ 1 1 1 a d o n e t u 引 本系统采用客户服务器( c s ) 的开发方