（计算机软件与理论专业论文）免疫算法在物流配送车辆优化调度中的应用.pdf

太原理工大学硕士研究生学位论文 免疫算法在物流配送车辆优化调度中的应用 摘要 随着科学技术的日益进步，物流系统逐渐成为现代社会经济系统的重 要支柱，物流总成本已在国民生产总值中占有相当的比重。物流配送是企 业与消费者在物流活动中直接相连的环节，在物流的各项成本中，物流配 送成本又占了相当高的比例。因此，配送车辆调度的合理与否直接影响到 配送的成本和企业效益，特别是多用户配送车辆调度的确定更为复杂。运用 合理的，科学的方法进行配送车辆调度是物流配送中非常重要的一项活动。 在当前众多研究课题中，车辆调度问题已成为众多学者竞相研究的热门话 题。 生物免疫系统( b i o l o 西c a li m m u n es y s t e m , b i s ) 是一种具有高度分布性 的自适应学习系统，具有完善的机制来抵抗外来病原体的入侵，有很强的 学习、记忆、和自适应调节能力。由于自然免疫系统具有强大的信息处理 能力，尤其是在完全并行和分布的方式下实现复杂的计算，因而成为一个 很有研究价值的课题。人工免疫算法( a r t i f i c i a li m m u n ea l g o r i t h m , a i a ) 是 基于生物免疫系统启示而设计的新型算法，在智能化搜索最优解方面相对 于其他进化算法更具有优势，并且已经广泛应用于模式识别、人工智能， 故障诊断、优化调度等领域，表现出卓越的性能和效率。 本文在对车辆调度数学模型深入研究的基础上，将免疫算法中的克隆 选择算法( c l o n a ls e l e c t i o na l g o r i t h m ，c s a ) 应用到车辆调度模型中，针对山 太原理工大学硕士研究生学位论文 西省煤炭运销系统建立了基于免疫算法的车辆调度模型，并进行了具体的 实现。计算结果表明，利用免疫算法进行物流配送车辆优化调度问题求解， 可以方便有效地求得问题的近似最优解。此模型在实际的应用中表现出突 出的性能，具有巨大的应用前景。 关键字：物流配送，车辆调度，人工免疫系统，人工免疫算法，克隆选择 算法 i i 太原理工大学硕士研究生学位论文 a p p l i c a t i o no fi m m u n ea l g o i u t h mo n v e h i c l es c h e d u l i n gp r o b l e m o fl o g i s t i c sd i s t r i b u t i o n a b s t r a c t w i t ht h ed e v e l o p m e n ti ns c i e n c ea n dt e c h n o l o g y , l o g i s t i c ss y s t e mh a s g r a d u a l l yb e e nd o m i n a n tf o rt h es o c i e t ye c o n o m i c sa n dt h el o g i s t i c sg r o s sc o s t p l a y sa ni m p o r t a n tr o l ei ng d p l o g i s t i c sd i s t r i b u t i o ni s 锄o p e r a t i o nl i n k i n g b e t w e e ne n t e r p r i s ea n dc o n s u m e rd i r e c t l y ，a n di th o l d sc o n s i d e r a b l e h i g h p r o p o r t i o ni nv a r i a b l ec o s to fl o g i s t i c 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 ) i n d i s t r i b u t i o nt a k e sg r e a te f f e c to nd i s t r i b u t i o nc o s ta n db e n e f i to fe n t e r p r i s e ， e s p e c i a l l yi nd i s t r i b u t i n gf o rm u l t ic o n s u n l e r s u s i n gar e a s o n a b l ea n ds c i e n t i f i c m e t h o di nv e h i c l es c h e d u l i n gp r o b l e mi sav e r yi m p o r t a n ta c t i o no fl o g i s t i c s d i s t r i b u t i o n a tp r e s e n tv e h i c l es c h e d u l i n gp r o b l e mh a sb e e nf o c u so fm a n y s c h o l a r st os t u d y b i o l o g i c a li m m u n es y s t e m ( b i s ) i sah i g h l yd i s t r i b u t i v ea n da d a p t i v e l e a n i n gs y s t e m , h a v i n gp e r f e c tf u n c t i o nt or e s i s ti n v a d i n go ff o r e i g np a t h o g e n y a n dt h ea b i l i t yl e a r n ，r e m e m b e ra n da d j u s ta d a p t i v e l yt ok e e pt h es t a b i l i z a t i o n 鱼塔i d et h eb o d y a c c o r d i n gt ob i sh o l d ss t r o n ga b i l i t yo fi n f o r m a t i o nh a n d l i n g , e s p e c i a l l yi nc o m p l e t ep a r a l l e la n dd i s t r i b u t i v ew a yt oc a l t yo u tc o m p l i c a t e d c o m p u t a t i o n , 8 0i th a sb e c o m eav a l u a b l er e s e a r c h i n gs u b j e c t a r t i f i c i a li m m u n e a l g o r i t h m ( 灿a ) i sak i n do fn e wa l g o r i t h mw h i c hi sb a s eo nt h eb i o l o g i c a l i m m u n es y s t e m , i n t e l l i g e n t i z e ds e a r c ho p t i m u ms o l u t i o nh a so v e r w h e l m i n g i i i 太原理工大学硕士研究生学位论文 a d v a n t a g e so v e rt h ee v o l u t i o n a r ya l g o r i t h m , t h i sk i n do f a l g o r i t h mh a sb e e nu s e d i n m a n yf i e l d s ，s u c h a s p a t t e r nr e c o g n i t i o n , a r t i f i c i a li n t e l l i g e n c e ， u n c o n v e n t i o n a l i t ya n dm a l f u n c t i o nd i a g n o s i s ，t h i sm e t h o ds h o w se x c e l l e n t p e r f o r m a n c ea n dh i g he f f i c i e n c y o nt h eb a s i so fr e s e a r c h i n gt h eo p t i m i z i n gm o d e lo nl o g i s t i c sv e h i c l e s c h e d u l i n g , t h i sp a p e ri n t r o d u c e sc l o n a ls e l e c t i o na l g o r i t h m 化s a ) i n t ot h e m o d e lo ft h ev e h i c l es c h e d u l i n gp r o b l e mt oe s t a b l i s ha no p t i m i z i n gm o d e lo f f l o g i s t i c sv e h i c l es c h e d u l i n gp r o b l e mf o rt h ec o a lt r a n s p o r ta n dd i s t r i b u t i o n s y s t e mi ns h a n x ip r o v i n c e t h er e s u l to fe x p e r i m e n t a lc a l c u l a t i o n sd e m o n s t r a t e t h a tt h eo p t i m a lo rn e a r l yo p t i m a ls o l u t i o n st ot h el o g i s t i cv e h i c l es c h e d u l i n g p r o b l e mc a nb ee a s i l yo b t a i n e db yu s i n gi m m u n ea l g o r i t h m t h i so p t i m i z i n g m o d e l s h o w s p r o m i n e n tc a p a b i l i t y a n d s t r o n gf o r e g r o u n d i n p r a c t i c a l a p p l i c a t i o n k e y w o r d s ：l 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 es c h e d u l i n gp r o b l e m ，a r t i f i c i a l i m m u n es y s t e m ，a r t i f i c i a li m m u n ea l g o r i t h m ，c l o n a ls e l e c t i o n a l g o r i t h m 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下。 独立进行研究所取得的成果。除文中已经注明引用的内容外。本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：日期： 翌：三：兰 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 导师签名： 日期：1 2 ：主：! f 日期：嗥：! ) 太原理工大学硕士研究生学位论文 1 1 人工免疫算法的研究背景 第一章绪论 免疫学是研究集体免疫系统的组织结构和生理功能的科学，它起源于中国。中国古 代医师在医治天花的长期临床实践中，创造了最早的原始疫苗人痘苗，人痘苗传入 到中东，经过改良后得到显著的效果，后又被传入英国，并在整个欧洲普及开来。在欧 洲经过研究人员的一系列实验后，成功推行了世界上第一例疫苗，但是这种孤立的成功 并未得到理论上的升华。直到1 9 世纪后期，微生物的发展才为免疫学的形成奠定了理 论基础，直到1 9 0 1 年，“免疫学”一词首先出现在( i n d e x m e d i c u s 中。1 9 1 6 年( j o u r n a l o f i m m u n o l o g y 创刊，作为一门学科，免疫学才正式被人们所承认【n 。 生物免疫系统( b i o l o g i c a li n l x n u n es y s t e m , b i s ) 是一种具有高度分布性的自适应学 习系统，具有完善的机制来抵抗外来病原体的入侵，有良好的多样性、耐受性、免疫记 忆、分布式并行处理、自组织性、自学习、自适应和鲁棒性等特点【。由于自然免疫系 统具有强大的信息处理能力，尤其是在完全并行和分布的方式下实现复杂的计算，因而 成为一个很有研究价值的课题，引起了许多研究人员普遍关注。 近年来，随着科技革命的进行，各个学科之间相互交叉、渗透，人们不断把一个领 域的研究成果应用于另一个领域中。同时，随着计算机技术和阿络技术的飞速发展，以 计算智能或软计算为代表的计算智能技术也在迅速发展。计算机免疫学( c o m p u t e r i m m u n o l o g y ) 就是一门基于生物免疫学、人工免疫、以及计算机科学等的交叉学科。计 算机免疫学利用最新的计算机科学技术研究了人工免疫的理论、规则、算法、模型等， 并将这些理论应用于具体的应用系统中，解决实际应用课题。 人工免疫算法( a r t i f i c i a li m m u n ea l g o r i t h m ，a i a ) 就是基于生物免疫系统启示而设 计的新型算法，它抽取和反映生物机体免疫系统的反应机制，结合工程应用而摇述的一 种计算方法【2 】。在智能化搜索最优解方面相对于进化算法更具有优势，并且已经广泛应 用于模式识别、人工智能、故障诊断、智能优化等领域，表现出卓越的性能和效率 太原理工大学硕士研究生学位论文 1 2 人工免疫系统的发展现状 1 2 1 国外研究动态 ( 1 ) d rd r p a n k a r d a s g u p t a d rd r p a n k a rd a s g u p t a ，美国m e m p h i s 大学计算机科学和数学学院的教授，他的特 殊研究领域包括人工智能、遗传算法、人工神经网络、人工免疫系统，当前的主要研究 是把这些智能技术用在计算机和网络安全中。他的研究项目包括基于免疫学的入侵检测 系统和利用免疫系统启发的技术进行异常检测。 ( 2 ) d rf o r r e s t 在美国新墨西哥大学，f o r r e s t 领导的研究组织，包括h a j i m e i n o u e 、g e o f f h u n s i c k e r 、 a n i ls o m a y a j i 、s t e v e nh o f f m e y r 等研究人员。主要研究项目包括入侵检测计划，基于网 络的入侵诊断，分布式变化检测。 ( 3 ) 威尔士大学的i s y s 计划 该计划的基本目的是开发一种工具，建立基于免疫系统的学习系统。这些系统能够 解决工业和商业中的实际问题，包括进一步研究算法、表示法和人工免疫系统的操作。 ( 4 ) s t a r l a b 公司 人工免疫系统有极大的分布式和并行性，高度的适应性和反应性，并保持计算和生 物推理功能。s t a r l a b ( 比利时) 在这项技术的研究中走在前列。该公司完成一个功能完 善的人工免疫系统实验平台，用于商业和学术研究。 ( 5 ) s a n t a f e 研究所 在著名的s a n t af e 研究所，研究人员l e es e g e l 和s t e p a h n i ef o r r e s tc o m p u t e r ( s c i e n c e ，u n i v e r s i t y o f n e w m e x i c o ) 对使细胞能够在变化的环境中实现复杂的、可靠 的决策制定的分子网络的结构和动力学进行了研究，他们也对在新陈代谢和遗传线路层 次上为这些网络的规范变化所有的鲁棒性和能力做了观察，这里的目标是理解控制和调 节机制的组织如何能使其快速适应变化的环境条件而保持动态平衡。他们计划研究变化 的、可替代的组织范围和用于控制机制的原理。尽管有许多障碍，l e e 仍建立了个复 杂的发信号分子和细胞模型网络的初期模型。 ( 6 ) m m 公司 通过模拟生物免疫系统的各个功能部件以及对外来抗原的识别、分析和清除过程， 2 太原理工大学硕士研究生学位论文 m m 公司的j o k e p h a r t a 等研究人员设计了一种计算机免疫模型和系统，用于计算机 病毒的识别和清除。该免疫反病毒模型可以说是一个初步完整的免疫反病毒模型，具有 一定的影响。 1 2 2 国内研究动态 国内人工免疫的研究还处于起步阶段，研究较早并且有一定成果的有： ( 1 ) 武汉大学梁意文教授利用免疫原理对大规模网络入侵检测和预警技术进行了研究。 ( 2 ) 四川大学李涛教授提出了基于免疫的大规模网络入侵动态取证及网络安全风险检 测与控制等技术。 ( 3 ) 中国科学技术大学研制了一个“基于人工免疫的入侵预警系统”，该系统具有较好 的未知入侵预警能力。 1 3 物流配送车辆优化调度问题的提出 科学技术的日益进步、生产力和经济的飞速发展，以及需求的不断提高，使物流系 统已逐渐成为现代社会经济系统的重要支柱，物流总成本已在国民生产总值中占有相当 的比重。现代企业为了在市场中提高企业竞争力，加强物流管理就成为降低物资消耗。 提高劳动生产率之后的“第三利润源泉”。物流管理的核心问题就是物流配送，在物流 的各项成本中，物流配送是企业与消费者在物流活动中直接相连的环节，是货物从物流 节点送达收货人的过程。物流配送成本在企业成本中占了相当高的比例。配送的核心部 分为配送车辆的集约、货物配送及送货过程。进行配送系统优化，主要是配送车辆调度 的优化。因此，配送车辆调度( v e h i c l es c h e d u j i n gp r o b l e m ，简称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 l ) 难题，只有 在任务数和车辆数较少的时候，才能求得精确解。因此，用启发式算法求解该问题就成 为人们研究的一个重要方向，并涌现出多种启发式算法。如何针对物流配送路径优化问 题的特点，构造运算简单、寻优性能优良的启发式算法，是一个值得深入研究的课题。 免疫算法采用了随机搜索方式，对搜索空问没有特殊的要求。具有运算简单，收敛速度 快以及多样性搜索等优点。尤其适用于处理传统搜索方法难于解决的复杂和非线性的问 3 太原理工大学硕士研究生学位论文 题，因此是解决v s p 的一个良好算法。 1 4 本论文主要完成的工作 本文在对生物免疫原理及车辆调度数学模型深入研究的基础上，将免疫算法中的克 隆选择算法引进到车辆调度模型中。针对山西省煤炭运销系统建立了基于免疫算法的车 辆调度模型，运用此算法解决了系统的优化调度问题。 论文共分为七大部分； 第一部分：概述了本文背景以及课题研究的目的和意义。 第二部分：介绍了物流配送车辆优化调度概念、产生的原因、配送流程及分类；对 v s p 目前已有的解决方案作了简要介绍与比较。 第三部分：对人工免疫算法生物学基础及人工免疫系统理论做了详实的介绍。首先 介绍了生物免疫学的一般概念及系统功能，然后详细的介绍了免疫系统的生物原理及特 点。最后在生物理论的基础上描述了人工免疫系统。 第四部分：引进了克隆选择算法。首先介绍了免疫算法的描述和基本步骤，对免疫 算法和遗传算法作了简要的比较，总结出免疫算法的优点。其次重点介绍了克隆选择算 法，在理论研究的基础上对克隆选择算法进行了深入研究，对于算法存在的问题提出了 解决方法。 第五部分：对单源点，单车型的、封闭型的满载送货车辆调度问题建立了数学模型 及目标函数，运用克隆选择算法对函数进行求解。 第六部分：对山西省煤炭运销系统作了简要介绍，详细阐述了煤炭运输车辆优化调 度系统开发的目的及原则；将基于免疫原理的克隆选择算法作为系统后台的优化调度算 法，对系统加以实现，寻找出车辆完成配送任务的最佳运输路线。 第七部分：对本论文的工作进行了总结，对后续工作及研究前景作了进一步展望。 4 太原理工大学硕士研究生学位论文 2 1 物流的概念 第二章物流配送车辆优化调度 物流活动的历史也许和人类的历史一样长，但对物流研究的历史却很短。对于物流 尚没有统一的定义，但普遍认为物流有广义和狭义之分。狭义的物流，比较常用的是美 国物流管理协会的定义 3 1 ：“物流是为满足消费者需要而进行从起点到终点间的原材料、 中间过程库存、最后产品和相关信息有效流动和储存的计划、实麓和控制管理过程。 也就是说，物流是指与采购、供应、生产、销售等企业经营活动相对应的将信息传递、 运输、配送、库存控制、仓储、装卸搬运以及包装等物流活动综合起来的一种系统化集 成式管理。它的目的是提高企业的收益，它的任务是以尽可能低的成本为顾客做出最好 的服务，它的方法是在恰当的时间、在恰当的地点、以恰当的方式向顾客提供恰当数量 的服务。广义的物流是指从企业的经营战略角度出发，将物流过程与客户需求、企业内 部生产过程以及供应商的制造资源整合在一起，形成联合影响力量，从而达到快速反应 市场、降低风险成本、实现高收益、赢得竞争优势的一种管理过程。 2 2 物流配送的概念 我国现代物流学表述闭：配送是以现代送货形式实现资源最终配置的经济活动， 按用户订货要求，在配送中心或其它物流结点进行的货物配备并以最合理方式送交用 户。 一般认为物流配送是指物流过程的中转型送货( 也称为二次输送、支线输送、终端 输送) 。也就是在产品用户集中区域，按用户的订货要求和时间计划，在物流中心配货 并将配好的货物采用汽车巡回运送的方式交收货人的小范围、近距离、小批量、多品种、 为用户服务的运输。配送不是单纯的运输或送货，而是运输与其它活动的组成，除了各 种“运，、。送”活动外，还要从事大量的集货、分货、配货、配装等工作，是配与送 的结合。 5 太原理工大学硕士研究生学位论文 2 3 物流配送产生的原因 配送作为先进的物流形式，它的产生以及推广是随着现代商业经营环境和经营形式 的变化而出现的。这些变化主要体现在唧： ( 1 ) 消费者消费行为的变化 随着人们生活水平的提高，2 0 世纪9 0 年代以来，人们对生活的追求己逐渐从原来 的温饱型、数量型转向小康型，对生活质量的要求越来越高。伴随着这种生活观念的变 化，在经济社会向国际化、信息化急剧转变的基础上，消费者价值观趋于多元化和多样 化，喜欢购买具有差别化的商品。这种消费行为变化对企业的生产和经营产生了深远的 影响，使生产和销售企业在适应消费者消费行为变化的过程中，开始强化物流管理，通 过少批量、多品种、快速化、柔性化的生产和经营来满足消费者的需求。 ( 2 ) 生产商生产策略的转变及其对物流管理的强化 为改变这种状况，现代生产企业空前重视物流管理，要求其物流系统既讲求效率， 又能促进生产、销售战略的灵活调整和转换。为此，生产厂商一方面运用物料需求计划 ( m r p ，m a t e r i a lr c q u 曲p l a n n i n g ) ，准时生产制o i t ，j u s ti nt u n e ) 等先进系统加大对 生产和供应中的物流管理，另一方面更加重视销售中的物流管理，即配送资源计划 ( d r p ，d i s t r i b u t i o nr e s o u r c ep l a n m g ) 管理，通过构筑物流配送系统直接靠近客户并加强 与客户关系的管理，动态跟踪客户需求状况，以获取最前端的市场需求信息用以化解因 市场信息反馈缓慢、曲解、变形带来的生产、供应、库存决策的失误。这种将物流管理 过程延伸至上、下游环节并具有强大电子商务功能的系统，就是当今最先进的企业经营 系统企业资源计划饵r p ，e n t e r p r i s e s r e s o u r c ep l a n n i n g ) 系统。 ( 3 ) 电子商务的兴起 近年来，随着网络、通信和计算机技术的迅速发展，使用i n t e r n e t 从事商务活动已 经成为现实。电子商务以其相对低廉的成本、简化的贸易流程、超越时空限制的经营方 式以及其巨大的利润，吸引着世晃各国众多厂商。据有关资料显示，目前全世界已有几 十万家公司，1 5 0 0 多家银行介入这一领域。许多专家学者认为，电子商务将成为2 l 世 纪新的经济增长点。 在电子商务中，除了少数的电子出版物，如软件、c d 等可以通过网络以电子的方 式送给购买者，其他绝大多数商品仍要通过物流过程完成从供应商到购买者的空间转 移。因为网上购物的消费者地点分散、购物数量少，其配送费用无疑与快速送达相矛盾。 6 太原理工大学硕士研究生学位论文 如何低成本、高速度、准确无误地将商品送达，成为物流配送所要研究的对象 ( 4 ) 城市交通限制与燃油成本的上升 随着现代社会城市化的加速发展和私人拥有车辆的增多，城市尤其是大都市的人口 与车辆急剧增加，城市交通尽管通过构筑地面、地上和地下立体化的交通网络体系，但 仍然满足不了人口与车辆的交通需求，城市交通越发拥挤。此外，由于石油能源的严重 减少，燃油价格上涨很快，对汽车提高运营效率、降低运输成本提出挑战。传统收货人 直接从工厂接收货物，构成蛛网状交叉运输路线、运输混乱、效率很低。而配送的优点 就是消除了交叉运输、节约了运输费用，提高了运输工具的装载率，降低空驶，并及时 送货，提高服务质量 2 4 物流配送的流程 物流配送是物流系统中的一个重要环节，由于它直接与消费者相连，因而其地位十 分突出。物流配送的一般定义为；将货物从物流节点送达收货人的过程。配送是在集货、 配货基础上，完全按着用户的要求，包括种类搭配、数量、时问等方面的要求所进行的 运送，是“配”和“送”的有机结合形式 4 1 。物流配送的一般流程如图2 1 所示： 图2 一l 物流配送漉程图 f i g 2 1t h ef l o wc h a r to f l o g i s t i cd i s t r i b u t i o n ( 1 ) 集货 集货是物流配送的准备工作和基础工作。集货工作包括筹集货源、订货、采购、进 货及有关的质量检查、结算、交接等。 配送的优势就是可以集中若干用户的需求进行一定规模的集货。集货是决定配送成 败的初期工作，如果集货成本太高，会大大降低配送的效益 ( 2 ) 存储 配送中的存储有储备及暂存两种形态。 储备 7 太原理工大学硕士研究生学位论文 配送储备是按一定时期的配送经营要求，形成的对配送的资源保证。这种类型的储 备数量较大，储备结构也较完善，视货源及到货情况，可以有计划地确定周转储备及保 险储备结构及数量。配送的储备保证有时在配送中心附近单独设库解决。 暂存 另一种储存形态是暂存，是具体执行配送时，按分拣配货要求，场地所傲的少量储 存准备。由于总体储存效益取决于储存总量，所以在理货这部分暂存数量只会对工作方 便与否造成影响，而不会影响储存的总效益，因而在数量上控制并不严格。暂存主要是 调节配货与送货的节奏，暂存时间不长。 ( 3 ) 配装 在单个用户配送数量不能达到车辆的有效载运负荷时，即一趟多送几户的问题。就 存在如何集中不同用户的配送货物，进行搭配装载以充分利用运能、运力的问题，这就 需要配装。和一般送货不同之处在于，通过配装可以大大提高送货水平及降低送货成本， 所以配装也是配送系统中有现代特点的功能要素，是现代配送不同于传统送货的重要区 别之处。 ( 4 ) 配送运输 即按着预先确定的配送线路和时刻表将货物送到用户的手中。其中，配送线路合理 与否对配送速度、成本、客户满意度影响很大，特别是多用户配送线路的确定更为复杂。 采用科学合理的方法来确定配送路线，是配送活动中非常重要的一项工作。 ( 5 3 送达用户 配好的货运输到用户还不算配送工作的完结，这是因为送达货和用户接货往往还会 出现不协调，使配送前功尽弃。因此，要圆满地实现货物的移交，并有效地、方便地处 理相关手续并完成结算，还应讲究卸货地点、卸货方式等。送达服务也是配送独具的特 殊性。 ( 6 ) 回程 在执行完配送的使命之后，车辆需要回程，在一般情况下，回程车辆往往是空驶， 这是降低配送效益、提高配送成本的因素之一。在规划配送路线时，回程路线应当尽量 缩短；在进行稳定的、计划配送时，回程车辆可将包装物、废弃物、残次品运回集中处 理，或者将用户的产品运回配送中心，作为配送中心的资源，向其他用户进行配送。 8 太原理工大学硕士研究生学位论文 2 5 物流配送车辆优化调度及分类 v s p 问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年提出。其目的是在一系列已知装货 点和卸货点组成的运输网络中，组织适当的行车线路，使车辆有序地通过它们，在满足 一定的约束条件( 如货物需求量、发送量、交发货时问、车容量限制、行驶里程限制、 时间限制等) 下，达到一定的目标( 如路程最短、费用最少、使用车辆数尽量少等) s l 。物 流配送车辆优化调度问题涉及的面广，需要考虑的因素较多，对配送企业提高服务质量、 降低物流成本、增加经济效益的影响较大，是物流配送系统优化的关键。 v s p 被提出后，国内外许多学者按不同的标准对其进行了分类，综合起来可分为 以下几种【3 】。 ( 1 ) 非满载和满载车辆的优化调度问题 按车辆载货状况区分，有非满载和满载车辆的优化调度问题。 非满载问题指当货物量小于车辆容量时，用一辆车执行任务就存在不满载运行情 况，调度时可安排一辆车执行多项任务，即在一辆车上装载不同货主的货物。当然，这 类问题有一个前提条件，即不同货主的货物允许混装。 满载问题指当货物量不小于车辆容量时，执行每项任务需要的车辆可能不只一辆， 车辆为完成任务，需满载运行。这类问题可能有两种情况：一种是由一辆车往返多次运 送，另一种是由多辆车分别运送，可以将货运量大于车容量任务点的任务分割成多项任 务来完成，每项任务可看成非满载问题。 ( z ) 集货或送货和集送一体化的车辆优化调度问题 按任务目标分，有集货或送货和集送一体化的车辆优化调度问题。 集货或送货问题也称为纯装问题或纯卸问题，指所有任务全是集货点( 装货点) 或 全是送货点( 卸货点) ，车辆空车从配送中心出发，去各货主处装满货后返回配送中心， 或是车辆装满货物去各货主处卸货后返回配送中心，这种情况称为集货或送货的车辆调 度安排。 集送一体化问题也称为装卸混合问题，指每一项货运任务都有自己的集货点和送货 点，车辆从配送中心出发，去某一任务的集货地点装货后运至其送货地点卸货( 即装卸 混合) ，完成所有任务后返回配送中心。这种情况称为集货和送货一体化的车辆调度安 排问题。 ( 3 ) 单源点和多源点的车辆优化调度问题 9 太原理工大学硕士研究生学位论文 按车场数目分，有单源点和多源点车辆优化调度问题。 单源点车辆优化调度问题是指所有的车辆均从一个配送中心发出，完成各自的任务 后都返回该配送中心。 多源点车辆优化调度问题是指，存在着多个配送中心，车辆可以从任何一个配送中 心派出，完成任务后，车辆也可以返回其中的任何一个配送中心。随着供应链的集成一 体化，多源点的车辆优化调度问题将越来越多，越来越重要。对于这类问题可以通过一 定的方法将其转化为单源点的车辆优化 抗体的编码形式 抗原和抗体的匹配规则 抗体的评价方法 新抗体的产生和新群体的形成规财 记忆库的设计与使用 4 1 3 免疫算法与遗传算法的比较 ( 1 ) 遗传算法的基本思想 遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体 内部染色体的随机信息交换机制相结合的搜索算法。类似免疫算法，它在搜索之前，先 将变量以某种形式进行编码，形成若干条染色体，不同的染色体构成一个群体。对群体 中的染色体将以某种方法评估其适应值。根据染色体的适应值选择要保留的染色体并对 其进行复制，最后对被选择的染色体进行重组、变异、产生新的染色体，进入下一次循 环。 3 2 太原理工大学硕士研究生学位论文 具体步骤如下1 2 4 1 ： 1 ) 根据问题实际选择合适的解的表达形式以及各个参数( 群体规模、交叉率、变异 率等) 的值； 2 ) 随机产生初始解群体； 3 ) 对解群体中的各个解个体进行评价，由此得出各个解的适应值； 4 ) 按照解的适应值对解群体进行“遗传进化操作( 选择、交叉、变异) ”，以产生 新群体； 5 ) 判断是否满足结束条件，满足则结束；否则，则重复3 ) 4 ) 步。 ( 2 ) 免疫算法与遗传算法的共同特征 1 ) 搜索的是解空间里一系列的点，而不只是一个点； 2 ) 处理的对象是表示待求解的参数的编码数字串，而不是参数本身； 3 ) 使用的是目标函数本身，而不是其导数或其它附加信息； 4 ) 搜索方式是随机的，而不是确定的； 5 ) 它们都是从一定规模的种群( 初始解) 出发，经过进化算子( 选择、交叉或变 异) ，使潜在解演化到具有更好适应值的解，最终收敛到全局最优解。 ( 3 ) 免疫算法与遗传算法的不同特点 1 ) 评价标准：遗传算法以解对函数的适应值为唯一的评价标准；而免疫算法以解 对函数的适应值以及解本身的浓度的综合性作为评价标准，只有那些适应值高且浓度较 低的个体才是最好的解，保持了群体多样性。 2 ) 交叉和变异操作的应用：在遗传算法中交叉操作作为保留好的“基因”同时又 给群体带来变化的操作，是遗传算法中的主要操作，而变异操作由于其变化较为激烈， 只能作为算法中的辅助操作，从而保证算法的平稳全局收敛。在免疫算法中，为维持群 体的多样性，操作以变异为主，以交叉为辅 2 4 1 。 3 ) 记忆库：在遗传算法中没有记忆库这一概念。记忆库是受免疫系统具有免疫记 忆特性的启示，在免疫算法结束时，将问题最后的解及问题的特征参数存入记忆库中，以 便在下次遇到同类问题时可以借用这次的结论，从而加快问题解决的速度，提高问题解 决的效率刚。 综合上述，虽然免疫算法和遗传算法都源于生物系统的启示而构造出来的随机启发 式搜索算法，两者在实现形式上有着相似之处，但免疫系统和遗传进化系统从功能上讲， 3 3 太原理工大学硕士研究生学位论文 有着本质的不同，因此，免疫算法和遗传算法在功能上也有着本质的区别 4 1 4 免疫算法的优点 通过以上比较，可以得出免疫算法具有以下优点； ( 1 ) 它在记忆单元的基础上运行，对于曾经出现过的抗原，免疫算法产生相应抗体 的速度比以前快，确保了算法快速收敛于全局最优解； ( 2 ) 它的计算亲和力的程序，反映了真实的免疫系统的多样性： ( 3 ) 它通过促进或抑制抗体的产生，体现了免疫反应的自我调节功能。 因为免疫算法的记忆切l 练、多样性及自我调节等特点，所以使用它能够获得许多优 化问题的最优解。 4 2 典型的人工免疫算法 在认识和研究了免疫系统一些机理的基础上，人们将系统中这些特性应用到类似的 问题中，于是设计出了各种免疫算法。如基于信息熵的免疫算法口q 、否定选择算法嘲、 动态规模免疫算法口1 1 以及克隆选择算法【2 。本论文中重点引用克隆选择算法，将在4 3 节中详细介绍。 4 2 1 基于信息熵的免疫算法 算法实现的基本步骤： ( 1 ) 抗原识别：输入目标函数和各种约束作为免疫算法的抗原。 ( 2 ) 产生初始抗体：在第一次迭代时，抗体通常是在解空间中用随机的方法产生的。 ( 3 ) 计算亲和性：分别计算抗原和抗体v 之间的亲和性日t ，及抗体矿和抗体形之间 的亲和性吼。 信息熵：算法中为了表明全体中抗体的多样性，引入信息熵的概念。如图4 1 所示 个长度为m 的位串：每位可供选择的字母表中共有s 个字母与，屯，七j ， 则这个抗 体的信息熵为：- p u l o g p u 太原理工大学硕士研究生学位论文 日( 忉= 吉兰j - ! q ( ) 其中：易( 忉= 乃l o g 乃，缉( ) 为个抗体第歹位的信息熵，鳓为个抗体 i - i 中的第，位字母为岛的概率。 1 工压 工压 工压 等位基因k t , k 蕾- h 图4 - 1 基因的信息熵 f 埏4 - lt h ei n f o r m a t i o ne i i 仃。钾o f g e n e 抗体之间的亲和性缈。，定义如下： a y , ，= 1 【l + 日( 2 ) 】 以2 ) 是抗体矿和抗体形的信息熵，h ( 2 ) = 0 时说明抗体矿和抗体形的所有基因都 是相同的，毋。的值介于o 和l 之问a 抗原和抗体矿之间的亲和性，用a q 表示，表明抗体对抗原的识别程度。d t 定义 如下； 瓯= 1 1 + o p t , 】 这里，o p t , 表示抗原和抗体之间的匹配程度，戤的值也介于o * 0 1 之间。 ( 4 ) 记忆单元更新：将与抗原的亲和性高的抗体加入到记忆单元中。由于记忆单元数 目有限，所以在记忆单元中用新加入的抗体取代与其亲和性最高的原有抗体。 ( 5 ) 基于评价解的选择：计算抗体的期望值，期望值低的抗体将受到抑制。 印 式中，q 是抗体f 的密度( 即数目) 为了有利于优化过程的进行，在这一步中，某些与 抗原有较高亲和性但浓度过高的抗体也必须受到抑制。 3 5 太原理工大学硕士研究生学位论文 ( 6 ) 产生抗体：通过交叉和变异，产生进入下一代的抗体。 ( 7 ) 终止条件：终止条件满足后，优化过程结束 基于信息熵的免疫算法的优点： 1 ) 采用信息熵作为评价群体中解的相似度的指标，比采用海明距离等指标更能客观地 反映其含义。 2 ) 采用基于浓度的选择机制，即鼓励适应值高的解没，又抑制浓度高的解，从而保证 了算法的收敛及群体的多样性，适合多峰值函数的寻优鲫。 该算法流程如图4 2 所示 4 2 2 否定选择算法 图4 - 2 免疫算法流程图 f i g4 - 2t h ef l o wc h a r to f a i a 在生物免疫系统中，t 细胞表面存在能识别抗原的表面受体。在t 细胞产生初期， 它位于胸腺中，其受体由于基因重组和体细胞免疫等因素而随机产生。t 细胞经过一个 “否定选择”过程清除掉那些对自身成份发生免疫反应的t 细胞，从而使流出胸腺的成 熟t 细胞在免疫反应过程中能够对自身成份表现为免疫耐受状态，而对外部抗原产生免 疫反应并清除之。否定选择算法采用相同的原理，先随机产生检测器，然后删除与自身 对抗的，并保留能检测非己的细胞。否定选择算法流程图如图4 - 3 所示。 太原理工大学硕士研究生学位论文 图4 - 3 否定选择算法流程图 f i g4 - 3 t h ef l o wc h a r to f n e g a t i v es e l e c t i o na l g o r i t h m 算法实现的基本步骤： ( 1 ) 将所维护信息的正常模式或系统的静态行为定义为。自己”信息，并将其表示为自 体集s 。 ( 2 ) 随机生成一个候选检测器集胄。 ( 3 ) 对自体集s 中每一个元素和候选检测器进行匹配运算，即亲和力计算。 ( 4 ) 如个体元素和候选检测器匹配，则说明这个候选器识别出了自体集中的任何一个元 素，即将这个候选器消除掉，重新生成一个检测器，再和自体集进行匹配运算；如 个体元素和候选检测器不匹配，则对下一个元素进行匹配运算。 ( 5 ) 如果一个候选检测器和自体集中的每个元素都不匹配，将这个候选检测器收集到检 测器集中。 ( 6 ) 若检测器集达到规定的规模，则结束。 否定选择算法的优点：该算法中的检测算法是唯一的，且检测是概率性的。对一个 鲁棒性的系统能够随机地检测外来的活动而非搜索已知的模式【2 刀。 3 7 太原理工大学硕士研究生学位论文 4 2 3 动态规模免疫算法 重庆大学张著洪博士利用小生境概念，克隆选择算法的部分机制，借助抗体浓度概念， 设计抗体评价策略和特定的免疫算予，提出一种动态确定进化群体规模的免疫算法，解决 多模态函数优化问题。此算法突出了免疫系统的自适应能力，且具有自动确定群体规模 及并行搜索最优解等特点。仿真事例表明，该算法能快速搜索最优解，对于解决工程问 题有一定的有效性。 算法实现的基本步骤： ( 1 ) 确定进化代数刀卜0 ，随机产生规模为虬的初始群体4 。 ( 2 ) 复制4 中激励度最高的一个抗体作为抗原魄。 ( 3 ) 选择4 中胁 i4 ，i ) 个亲和度较高的抗体构成群体厶，其余部分构成4 。 ( 4 ) 对厶中每一抗体彳6 按突变率口突变，即设抗体4 6 表示为a b = “，而，x 。) ，抗 原一邑表示为a g = ( 靠1 ，只2 ，) 0 ) ，a b 按下式进行超突变 彳64 - a b + f l ( a g - a b ) ，【0 ，口】 r 口= 1 一e x p ( 一1 4 6 一彳岛，d 其中为【o 口】上的随机数，从而获如。 ( 5 ) 消除4 中相同的抗体，选择未被消去的抗体中肺仞1 4 。p 个抗体构成4 ，： ( 6 )