（机械制造及其自动化专业论文）改进蚁群算法研究及其在车辆调度中的应用.pdf

硕= ：学位论文 摘要 随着市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益明显， 越来越引起了人们的高度重视，已成为当前“最重要的竞争领域”之一。未来的市场 竞争，物流将起到举足轻重的作用。物流配送中的车辆调度优化方法和系统，是实现 快速、准确和低成本物流配送的重要手段和途径，是现代物流系统必不可少的重要部 分。 然而，现有的物流系统大多采用人工或计算机辅助的方法进行车辆调度，因此， 不仅调度时间长，而且，不可能综合多目标多约束调度需求进行科学的量化分析和优 化处理。因此，研究物流配送中的车辆调度需求，建立多目标多约束环境下的车辆调 度数学模型，提出有效的、对一般车辆调度问题具有一定适用性的智能优化方法，并 研制车辆凋度系统具有重要的理论意义和实用价值。 本文的主要工作和贡献在于： 1 、在对智能路径优化算法进行分析对比的基础上，深入研究了基本蚁群算法的 基本原理、模型、实现方法及其仿真效果，分析了基本蚁群算法的优点及其不足。 2 、针对基本蚁群算法存在的计算时间长、易于陷入局部最优等缺点，提出和实 现了基于模式学习的动态小窗口蚁群算法( d 忪c a p l ) 和融入遗传算法的 d l w a c a p l ( h a c a g a ) ，并通过案例测试，证明了上述两种改进蚁群算法的有效性 和适应性。 3 、研究了面向能力约束的车辆路径问题( c v i 冲) 和面向时间窗的车辆路径问题 ( v r p t w ) 数学模型、求解方法以及车辆调度的多目标优化策略，包括多目标体系、 数学模型和多目标的综合优化方法。 4 、基于本文提出的改进蚁群算法( d l w a c a p l 和h a c a g a ) 进行了车辆调度 系统的研制，包括车辆调度系统的主要功能设计、软硬件环境配置和关键算法的编码 与实现。 5 、对多目标多约束车辆调度工程问题进行了测试，验证了本文提出的改进蚁群 i v 硕士学位论文 算法的有效性和适应性。 关键词：物流配送，车辆调度，智能优化，蚁群算法，多目标 v 硕士学位论文 s t ud yo ni m p r o v e da n tc o l o n ya l g o r i t h ma n d i t sa p p l i c a t i o ni nt h ev e h i c l es c h e d u l i n g a b s t r a c t w i t ht h ed e v e l o p m e n to fm a r k e te c o n o m y , i th a sb e e n p a i dm o r e a t t e n t i o nt h a tl o g i s t i c s ，t a k e na st h et h i r dp r o f i tr e s o u r c e ，h a so b v i o u s l y a f f e c t e dt h ee c o n o m ya c t i v i t y a st h em o s ti m p o r t a n tc o m p e t i t i v ef i e l d ，i tw i l l p l a ya ni m p o r t a n tr o l ei nt h ef u t u r em a r k e tc o m p e t i t i o n t h ev e h i c l e s c h e d u l i n go p t i m i z a t i o na n ds y s t e mo fl o g i s t i c sd e l i v e r yi so n eo fi m p o r t a n t a p p r o a c h e st h a ti m p l e m e n tf a s t ，a c c u r a t ea n d l o w - c o s tl o g i s t i c sd e l i v e r y a n d t h e ya r ei n d i s p e n s a b l ep a r t so fm o d e r nl o g i s t i c ss y s t e m i nc u r r e n tl o g i s t i c ss y s t e m ，m a n u a lo rc o m p u t e r - a i d e da p p r o a c h e sa r e m o s t l ya d o p t e d o no n eh a n d ，i tw i l lc o s tm u c ht i m e ，o nt h eo t h e rh a n d i ti s h a r d l yt os y n t h e s i z em u l t i - o b j e c t i v ea n dm u l t i - c o n s t r a i n ts c h e d u l i n gd e m a n d s t op e r f o r ms c i e n t i f i cq u a n t i t a t i v ea n a l y s i sa n do p t i m i z a t i o nd i s p o s a l s oi ti s d e s i r e df o rt h e o r ya n d p r a c t i c et op r e s e n te f f e c t i v ea n da d a p t a b l ei n t e l l i g e n t o p t i m i z a t i o nf o rg e n e r a lv e h i c l es c h e d u l i n gp r o b l e m s ，r e s e a r c ho nv e h i c l e s c h e d u l i n gr e q u i r e m e n ti nl o g i s t i c sd e l i v e r y , e s t a b l i s ht h em a t h e m a t i c a lm o d e l o fv e h i c l es c h e d u l i n gi nc o m p l i c a t e de n v i r o n m e n tw i t hm u l t i o b j e c t i v ea n d m u l t i c o n s t r a i n t v 1 硕士学位论文 t h em a i nc o n t r i b u t i o n so ft h i st h e s i si n c l u d e ： 1 t h et h e o r y , m o d e l ，t o o la n ds i m u l a t i o no fb a s i ca n tc o l o n ya l g o r i t h m a r ed i s c u s s e di nd e t a i l sb ya n a l y z i n ga n dc o m p a r i n gi n t e l l i g e n tr o u t i n g o p t i m i z a t i o n s 2 t w on o v e li n t e l l i g e n to p t i m i z a t i o n s ，n a m e dd y n a m i cl i t t l ew i n d o w a n tc o l o n ya l g o r i t h mb a s e do np a t t e r nl e a r n i n g ( d l w a c a p l ) a n d d l w a c a p l i n t e g r a t e dg e n e t i ca l g o r i t h m ( h a c a g a ) ，a r ep r o p o s e dt o a v o i dt h ed e f i c i e n c yo fb a s i ca n tc o l o n ya l g o r i t h mw h i c ho f t e nc o s t sl o n g t i m ea n dg e ti n t ot h el o c a lo p t i m i z a t i o ne a s i l y a n dt h ev a l i d a t i o n sa n d a d a p t a t i o no ft h et w oi n t e l l i g e n to p t i m i z a t i o n sh a v eb e e np e r f o r m e dw i t h b e n c h m a r k 3 t h em a t h e m a t i c a lm o d e l sa n da p p r o a c h e so ft w ot y p i c a lv e h i c l e s c h e d u li n gp r o b l e m so i lc a p a c i t a t e dv e h i c l er o u t i n gp r o b l e m s ( c w da n d v e h i c l er o u t i n gp r o b l e m sw i t ht i m ew i n d o w s ( v r p t w ) a r ei n v e s t i g a t e d f u r t h e r m o r e ，t h em u l t i o b j e c t i v eo p t i m i z a t i o ns t r a t e g i e so nv e h i c l es c h e d u l i n g i n c l u d i n gm u l t i o b j e c t i v ef r a m e w o r k ，m a t h e m a t i c sm o d e la n dm u l t i o b j e c t i v e c o m p r e h e n s i v eo p t i m i z a t i o na r er e s e a r c h e d 4 v e h i c l es c h e d u l i n gs y s t e mb a s e do nt h ei m p r o v e da n tc o l o n y a l g o r i t h m s ( d l w a c a p l a n dh a c a g a ) h a sb e e nd e v e l o p e d ，i n c l u d i n gt h e d e s i g no f m a i nf u n c t i o nm o d e l s ，t h ec o n f i g u r a t i o no fs o f t w a r ea n dh a r d w a r e a sw e l la sc o d i n ga n dr e a l i z a t i o no ft h ek e ya l g o r i t h m s 5 as t u d yo fh o wt h e s em e t a h e u r i s t i c sp e r f o r mi sc a r r i e do u to nt h e v i i 硕十学位论文 e n g i n e e r i n gb e n c h m a r k a n dt h ee x p e r i m e n t a lr e s u l t sh a v ei n d i c a t e d t h e v a l i d a t i o na n da d a p t a t i o no f t h ei m p r o v e da n tc o l o n ya l g o r i t h mp r o p o s e di n t h i st h e s i s l a ns h i h a i ( m e c h a n i c a la n de l e c t r i c a le n g i n e e r i n g ) s u p e r v i s e db y k e y w o r d s l o g i s t i c sd e l i v e r y , i e e h i c l es c h e d u l i n g ，i n t e l l i g e n to p t i m i z a t i o n ， a n tc o l o n ya l g o r i t h m ，m u l t i o b je c t i v e v i i i 硕士学位论文 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在 导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外， 本论文不包含任何其他个人或集体己经发表或撰写过的作品及成果的内容。论文为本 人亲自撰写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。 学位论文作者签名：至二肯塑 日期：年写月心日 硕j ：学位论文 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权 东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密口。 学位论文作者虢互馑汝 慨岬年专月咖 燧名菇弛 日期：刁够月f 泊 改进蚁群算法研究及其在车辆调度中的应用 i l l 硕- 上学位论文 1 1 研究背景 第1 章绪论 随着市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益明显， 越来越引起了人们的重视，成为当前“最重要的竞争领域”，未来的市场竞争，物流 将起到举足轻重的作用。美国物流管理协会( 1 1 1 ec o u n c i lo f l o g i s t i c sm a n a g e m e n t ， c l m ) 对物流的定义是：物流是对货物、服务及相关信息从供应地到消费地的有效率、 有效益的流动和储存进行计划、执行与控制，以满足客户需求的过程【2 】。 配送是物流系统中一个重要环节，由于它直接与消费者相连，因而其地位十分突 出。配送的一般定义为：按用户的订货要求，在物流配送中心进行分货、配货等工作， 并将配好的货物按时送达指定的地点和收货人的过程，是“配”和“送 的有机结合 形式。配送的一般流程如图1 1 所示。 图1 1 配送流程图 随着电子商务的发展以及新的物流配送模式的出现，存贮的要求趋向弱化，配送 成为最重要的环节，直接与用户相连。配送主要包括以下几个部分： ( 1 ) 集货作业。从生产工厂( 或供应商) 进货并集结的过程。 ( 2 ) 配货作业。配货即货物的分拣作业，根据各用户的不同要求，在配送中心 将所需要的货物挑选出来的过程。 ( 3 ) 车辆货物的配装作业。由于配装作业本身的特点，配装工作所需车辆一般 为汽车，由于配送货物的质量和体积的差异，在配装货物时要考虑车辆的载重和容积， 硕l ：学位论文 为使车辆的载重和容积得到充分利用，还要考虑一趟多送几户的问题。 ( 4 ) 配送路线的确定。即按预先确定的配送线路和时刻表将货物送到用户的手 中。其中，配送线路合理与否对配送速度、成本、客户满意度的影响很大，特别是多 用户配送线路的确定更为复杂。采用科学合理的方法来确定配送路线，是配送活动中 非常重要的一项工作。 随着物流配送集约化、一体化的发展，常将配送的各环节综合起来，核心部分为 配送车辆的集货、货物配装以及送货过程。进行配送系统优化，主要就是配送车辆调 度优化，包括集货线路优化、货物配装、送货线路优化以及集货、货物配装和送货一 体化优化。 物流配送车辆的线路优化，是物流配送优化中关键的一个环节，也是电子商务活 动不可缺少的内容。正确合理的安排车辆的配送线路，实现合理线路运输，从而降低 运输成本，节约运输时间，提高客户满意度和经济效益，达到物流科学化管理【l 】。 1 2 国内外研究现状 1 2 1 车辆路径优化问题的提出 国外将物流配送车辆路径优化问题归结为或称之为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 ) 。物流配送车辆优化调度问题最早是 由d a n t z i g 和r a m s e r 【3j 于1 9 5 9 年提出的，很快引起运筹学、应用数学、组合数学、 图论与网络分析、物流科学、计算机应用等学科专家与运输计划制定者和管理者的极 大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科的专家对该问题 进行了大量的理论研究及实验分析，取得了很大进展。该问题是t s p 问题的一个特 例，而t s p 问题是一个著名的n p h a r d 组合优化问题，因而v r p 问题也是n p h a r d 问题。该问题般定义为：对一系列装货点和( 或) 卸货点，组织适当的行车线路， 使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、交发货时 间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标( 如路程最短、 费用最少、使用车辆数量尽量少等) 【1 1 。国外对物流配送车辆路径优化问题作了大量 而深入的研究，例如早在1 9 8 3 年b o d i n ，g o l d e n 等【4 】在他们的综述文章中就列举了 7 0 0 余篇文献。在c h r i s t o f i d e s ( 1 9 8 5 ) 【5 】，g o l d e n 和a s s a d ( 1 9 8 8 ) 1 6 编辑的论文集 2 一一 堡圭兰堡垒苎 中，以及a l t i n k e m e r 和g a v i s h ( 1 9 9 1 ) 【7 】，l a p o r t e ( 1 9 9 2 ) i s ，s a l h i ( 1 9 9 3 ) 例等的综 述文章中都做了详尽的阐述。 1 2 2 车辆路径优化问题的分类 在v r p 的基础上，车辆路径优化问题在学术研究和实际应用上产生了许多不同 的延伸和变化型态，包括： ( 1 ) 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 。t s p 可看作v r p 的一个 特例，即当v r p 只包括一条路径，且车辆载重量足够大时就成为t s p t z 0 11 1 1 1 ： ( 2 ) 面向能力约束的车辆调度问题( c a p a c i t a t e dv e h i c l er o u t i n gp r o b l e r n s , c v r p ) 1 1 2 1 j 3 】： ( 3 ) 面向时间窗的车辆调度问题( v e h i c l er o u t i n gp r o b l e m sw i t ht i m ew i n d o w s ， v r p t w ) 1 4 l 1 5 1 ； ( 4 ) 动态车辆路径问题( d y n a m i cv e h i c l er o u t i n gp r o b l e m s ，d v r p ) 1 6 1 1 7 1 ： ( 5 ) 考虑装卸货的车辆路径问题( v e h i c l er o u t i n gp r o b l e m sw i t hp i c k u pa n d d e l i v e r y ) 【1 8 】【1 9 1 ： ( 6 ) 多车场的车辆路径问题( m u l t i p l ed e p o tv e h i c l er o u t i n gp r o b l e m s ，m d v r p ) 2 0 1 2 1 ； ( 7 ) 随机车辆路径问题( s t o c h a s t i cv e h i c l er o u t i n gp r o b l e m ，s v r p ) 2 2 1 ，包括 随机客户( s t o c h a s t i cc u s t o m e r s ) ，随机需求( s t o c h a s t i cd e m a n d s ) ，随机时间( s t o c h a l s t i c t i m e s ) ； ( 8 ) 考虑收集的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hb a c k h a u l s v r p b ) 2 3 1 2 4 1 ； ( 9 ) 周期性的车辆路径问题( p e r i o d i cv e h i c l er o u t i n gp r o b l e m ，p v r p ) p 5 1 2 6 1 。 1 2 3 车辆路径问题的研究方法 目前针对车辆路径优化问题的求解算法可以说是相当丰富，m a g n a n t j ( 1 9 8 1 ) 【2 7 1 ， b o d i n 和g o l d e n ( 1 9 8 3 ) 【2 8 】，g o l d e n ( 1 9 8 4 ) 【2 9 】，l a p o r t e ( 1 9 9 2 ) 【3 0 】，l a p o n e 和o s m a n ( 1 9 9 5 ) 等许多学者对v r p 求解方法的分类进行了研究，认为就其本质， 基本上可以分为精确算法和启发式算法两大类。精确算法将车辆路径优化问题，通过 3 一 硕，i 二学位论文 严谨的数学模型或计算机数据结构规划，利用数学法则或数据结构搜寻的方式，求得 问题的解。由于精确算法是在所有可行解集合( f e a s i b l es o l u t i o ns e t ) 寻找最优解， 所以所求的解均为最优解。精确算法主要包括：分枝定界法( b r a n c ha n db o u n d a p p r o a c h ) ，割平面法( c u t t i n gp l a n e sa p p r o a c h ) ，网络流算法( n e t w o r kf l o w a p p r o a c h ) ，动态规划法( d y n a m i cp l ：o g r a m m i n g a p p r o a c h ) 。但是随着变量的增加， 车辆路径问题的解集合会有组合爆炸( c o m b i n a t o r i a le x p l o s i o n ) 的现象，求解时间也 呈指数函数的趋势增长，不能在有限的时间( p o l y n o m i a lt i m e ) 给予决策者一个可行 解。而启发式算法( h e u r i s t i c s ) 是指一种基于直观或经验构造的算法，目标是在可接 受的花费( 计算时间、占用空间等) 下得出待解决问题的满意解，而不是最优解。这 主要是考虑到：( 1 ) 一些问题本身不存在严格意义的最优解；( 2 ) 对某些问题，得到 它的最优解所需的花费太大；( 3 ) 根据实际需要，很多时候并不要求解具有过高的精 度。考虑到v r p 是n p h a r d 问题，而启发式方法能够比较快地得到满意解，这对解 决n p h a r d 问题来说有着不可估量的作用。大部分文献中阎【3 9 】，学者主要是在构造 各种高质量的启发式算法。因此，这里也主要介绍启发式算法。启发式算法又分为传 统启发式算法( c l a s s i c a lh e u r i s t i c s ) 和现代启发式算法( m e t a h e u r i s t i c s ) ，现代启发 式算法又称智能优化算法( i n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m s ) 或亚启发式算法、元 启发式算法。 ( 1 ) 传统启发式算法 传统启发式算法主要包括：路径构造启发式算法和路径改进搜索的启发式算法， 其中，路径构造启发式算法主要包括节约法( s a v i n gm e t h o d ) 4 0 】、扫描法( s w e e p i n g ) 4 1 】、最邻近法( n e a r e s tn e i g h b o r ) 4 2 】、插入算法( i n s e r t i o n ) p 3 1 等；路径改进搜索的 启发式算法主要包括七一o p tt 删【4 5 1 、2 一印f + 【4 6 1 、c r o s s e x c h a n g e 4 7 】、o r 一印f 【4 引、 旯一e x c h a n g e 4 9 】、e j e c t i o nc h a i n s 5 0 】、g e n i u s 【5 1 】等。 ( 2 ) 现代启发式算法 现代启发式算法有一些共同的特点【5 2 】：( 1 ) 它们大都引入了随机因素，因此具有 不确定性，不少计算过程实际上是在计算机上作随机过程的模拟；( 2 ) 它们大都具有 自适应机制，在计算过程中体系结构在不断地进行调整；( 4 ) 它们都是针对通用的一 般目标而设计的，它们不同于针对特殊问题而设计的算法。现代启发式算法主要包括 一些人工智能算法，如：禁忌搜索算法( t a b us e a r c h ，t s ) 【5 3 】、模拟退火算法( s i m u l a t e d 4 硕十学位论文 a n n e a l i n g ，s a ) t 5 4 1 、遗传算法( g e n e t i ca l g o r i t h m ，g a ) 【5 5 1 ，粒子群算( p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) 5 6 】，蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 【5 7 1 及人工神经网 络算法( a r t i f i c i a ln e u r a ln e t w o r k ，a 卜小i ) 。 1 3 论文研究的目的主要内容及拟解决的关键技术 1 3 1 研究目的 本文的研究目的是：通过研究智能路径优化方法，尤其是蚁群算法，改进现有智 能优化方法，以满足现代物流配送中车辆调度的最优化需求。 1 3 2 研究内容 主要研究内容： ( 1 ) 深入研究现代智能路径优化方法，尤其是蚁群算法； ( 2 ) 提出和改进蚁群算法； ( 3 ) 研究物流配送中多目标车辆调度数学模型、优化策略及解决方法； ( 4 ) 研制智能车辆调度原型系统； ( 5 ) 对提出和实现的改进蚁群算法和车辆调度原型系统进行测试和验证。 1 3 3 拟解决的关键技术 ( 1 ) 基本蚁群算法的改进目标及策略； ( 2 ) 改进蚁群算法的构造及其实现； ( 3 ) 改进蚁群算法对解决车辆调度问题的适应性和有效性。 1 4 论文章节安排 根据本文的研究目标、主要研究内容及拟解决的关键技术，作者在对智能路径优 化方法进行深入研究的基础上，提出和实现了改进蚁群算法，并以单目标和多目标车 辆调度为例，验证了本文提出和实现的基于模式学习的动态小窗口蚁群算法 ( d 队c a p l ) 及融入遗传算法的基于模式学习的动态小窗口蚁群算法( h a c a g a ) 硕士学位论文 的有效性和适应性。论文框架如图1 2 所示。 论文的主要章节及其内容安排如下： 第1 章：绪论。首先介绍了车辆路径问题在物流配送中的重要作用，然后介绍了 车辆路径问题的研究现状，重点介绍了车辆路径优化问题的分类及其研究方法，最后 阐述了论文的研究目标、主要研究内容、拟解决的关键技术和论文结构。 第2 章：智能路径优化方法分析。首先分析了几种智能路径优化方法，然后介绍 了基本蚁群算法的原理、模型及实现方法，最后对基本蚁群算法的优点及其不足进行 了分析。 第3 章：改进蚁群算法的研究与实现。首先针对基本蚁群算法计算时间长，易于 陷入局部最优等缺点，提出和实现了基于模式学习的动态小窗口蚁群算法 ( d 删队c a p l ) 和融入遗传算法的d l w a c a p l ( h a c a g a ) ，并通过案例测试，证 明了上述两种改进蚁群算法的有效性和适应性。 第4 章：智能车辆调度方法的研究。首先介绍了车辆调度对降低物流成本的重要 性，然后研究了面向能力约束的车辆调度问题( c v r p ) 和面向时间窗的车辆调度问 题( v r p t w ) 数学模型、求解方法以及车辆调度的多目标优化策略，包括多目标体 系、数学模型和多目标的综合优化方法。 第5 章：车辆调度系统的研制及其工程测试。首先介绍了基于本文提出的改进蚁 群算法( d l w a c a p l 和h a c a g a ) 的车辆调度系统主要功能、软硬件环境及其部分 功能的运行界面。然后，为了验证本研究提出的改进蚁群算法和研制的系统的有效性 和适应性，对单目标车辆调度问题进行了测试和验证，在此基础上，添加目标和约束 及其相关参数，进行了多目标、多约束的车辆调度问题的测试和验证。 图1 - 2 本文框架结构 粤囵磊l | 蒜型磊= 磊塑 詈 獭薰粼 一黼一 一一一 1 = | 锴 一 一章 = = 章 一 臣三竺臣二鬯 硕士学位论文 2 1 引言 第2 章智能路径优化方法分析 随着科学技术的发展，目前科学技术正处于多学科相互交叉和渗透的时代。特别 是计算机科学与技术的迅速发展，从根本上改变了人类的生产与生活。同时，随着人 类生存空间的扩大以及认识与改造世界范围的拓宽，人们对科学技术提出了新的和更 高的要求，其中对高效的优化技术和智能计算的要求日益迫切。 2 0 世纪8 0 年代以来，一些新颖的智能算法，如人工神经网络、遗传算法、模拟 退火、禁忌搜索、蚁群算法、粒子群算法等，通过模拟或揭示某些自然现象或过程而 得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学等方面， 为解决复杂问题提供了新的思路和手段。这些算法独特的优点和机制，引起了国内外 学者的广泛重视并掀起了该领域的研究热潮，且在诸多领域得到了成功应用。在优化 领域，出于这些算法构造的直观性与自然机理，因而通常被称作智能优化算法 ( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) ，或称现代启发式算法( m e t a h e u r i s t i c a l g o r i t h m s ) 。 目前搜索算法广泛使用的智能优化算法有禁忌搜索算法5 3 1 、模拟退火算法【5 4 】、 遗传算法【5 5 1 、粒子群算法 5 6 1 、蚁群算法【5 7 1 以及由上述两种或多种算法结合各自的优 点混合而成的混合优化策略。 2 2 智能优化方法概述 ( 1 ) 禁忌搜索算法。 禁忌搜索算法最早由g l o v e r 5 3 1 在1 9 8 6 年提出，进而形成一套完整算法。为了回 避局部领域搜索陷入局部最优的主要不足，禁忌搜索算法用一张禁忌表记录下已经到 达过的局部最优点，在下一次的搜索中，有选择地或禁止搜索这些点，以此来跳出局 部最优点；同时遗忘又使得这些禁忌是弱禁忌，即在一定的时间后这些禁忌将失效， - 7 硕上学位论文 最终达到全局最优的目的。国外已经有许多专家用禁忌搜索算法成功求解了v r p 问 题【5 8 】【5 9 1 。 优点：禁忌搜索算法采用了禁忌搜索技术，禁止重复前面的搜索工作。为了回避 局部邻域搜索陷入局部最优的主要不足，禁忌搜索算法使用禁忌表来记录己经到达过 的局部最优点，在下一次的搜索中，利用禁忌表中的信息不再或者有选择的搜索这些 点，以此来跳出局部最优点。 缺点：禁忌搜索算法对初始解具有较强的依赖性，质量较差的初始解会降低算法 的收敛速度；禁忌搜索算法的搜索过程是串行的，仅仅是单一状态的移动，非并行搜 索。 ( 2 ) 模拟退火算法 模拟退火算法是由m e t r o p o l i s 等【5 5 1 在19 5 3 年提出的，是局部搜索算法的扩展。 模拟退火算法用于优化问题的出发点是基于物理中物质的退火过程与一般优化过程 的相似性。它通过模拟固体退火过程，综合了统计物理学和局部搜索方法的思想，采 用m e t r o p o l i s 接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多 项式时间内给出一个近似最优解。近年来，也有不少专家研究发展了模拟退火算法在 v r p 问题中的应用【6 0 】【6 l 】。 优点：模拟退火算法在迭代搜索过程以m e t r o p o l i s 接受准则接受目标，所以模拟 退火算法突出地具有跳出局部最优的能力，具有高效、鲁棒、通用、灵活的优点。 缺点：模拟退火算法对初始温度和退温系数这两个参数的依赖性较强，这两个参 数选择恰当与否将直接关系到算法性能。 ( 3 ) 粒子群算法 粒子群算法( p s o ) 是由k e n n e d y 和e b e r h a r t 等【5 6 】于1 9 9 5 年提出的一种进化计 算技术( e v o l u t i o n a r yc o m p u t a t i o n ) ，其基本思想来源于对鸟群简化社会模型的研究及 行为模拟。群体中的鸟被抽象为没有质量和体积的“粒子”，通过这些“粒子”的相互协 作和信息共享，其运动速度受到自身和群体的历史运动状态信息的影响，以自身和群 体的历史最优位置来对粒子当前的运动方向和运动速度加以影响，能较好地协调粒子 本身和群体运动之间的关系，在复杂的解空间寻找最优解。粒子群算法自从提出之后， 由于其概念简明、实现方便，在短期内迅速得到了国际进化计算研究领域的认可，并 在算法实现模式及应用领域得到了很大的发展。有不少学者尝试将粒子群算法应用于 r 硕j ：学位论文 v r p 问题的求解【6 2 j 【6 3 】。 优点：简单、易于实现，没有许多参数需要调整。 缺点：每个粒子根据自身的最优位置和群体全局的最优位置更新自己的速度和位 置，各粒子由于群体全局的最优位置的影响，很快收敛到全局最优位置附近。但是如 果全局最优位置是一个局部最优值，则整个粒子群很容易陷入局部最优。 ( 3 ) 遗传算法 遗传算法是美国m i c h i g a n 大学的教授h o l l a n d 等5 8 1 于1 9 7 5 年提出的人工智能算 法。遗传算法是源于自然界的生物进化过程。生物是通过自然选择和有性繁殖两个基 本过程不断进化的。通过自然淘汰、变异、遗传进行进化，以适应环境的变化，产生 最适个体。人们将搜索和优化过程模拟成生物体的进化过程，用搜索空间中的点模拟 自然界中的生物个体，将求解问题的目标函数度量成生物体对环境的适应能力，将生 物的优胜劣汰过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过 程。遗传算法已经被广泛应用于v r p 问题，并取得了较好的效果删【6 5 】。 优点：遗传算法是将问题的控制变量或决策变量，编码成染色体形式字符串后， 直接在染色体上演化求解。对于问题本身在求解空间上是否连续，可否微分都没有影 响，故适用性较强；遗传算法采取随机搜寻法则，在求解空间上任意的跳动而不受限 制，其全局搜索能力较强。 缺点：对于结构复杂的组合优化问题，搜索空间大，搜索时间比较长，往往会出 现早熟收敛的现象；对初始种群很敏感，初始种群的选择常常直接影响解的质量和算 法效率。 ( 4 ) 蚁群算法 蚁群算法是通过模拟自然界蚂蚁搜索食物的行为由意大利学者d o r i g o 等6 1 】在 1 9 9 1 年提出的仿生优化算法。仿生学家经过大量细致观察研究发现，蚂蚁个体之间 是通过一种称之为外激素( p h e r o m o n e ) 的物质进行信息传递的。蚂蚁在运动过程中， 能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质， 并以此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种 信息正反馈现象：某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越 大。蚂蚁个体之问就是通过这种信息的交流达到搜索食物的目的。人们通过模拟蚂蚁 搜索食物的过程来求解一些组合优化问题。近年来，应用蚁群算法来解决v r p 问题 0 硕上学位论文 以逐渐成为学者的研究热点6 2 】【6 3 1 。 ? 。、 一 优点：蚁群算法具有采用分布式并行计算机制，易于与其他方法结合，具有较强 的鲁棒性等优点。 缺点：蚁群算法搜索时间长，易陷入局部最优解。 遗传算法虽然存在不足，但是遗传算法经过几十年的发展，已经成为具有系统优 化，适应和学习的高性能计算和建模的优秀智能优化方法。蚁群算法虽然是近年来才 发展的仿生优化算法，但是蚁群算法在求解旅行商问题，车辆路径问题等复杂的组合 优化问题已经显示出了强大的生命力。因此，本章主要研究基本蚁群算法，并在第3 章对基本蚁群算法进行改进并与遗传算法融合，汲取两种算法的优点，克服各自的缺 点，实现算法的优势互补。 2 3 基本蚁群算法的研究 生物学家经过大量细致的观察研究发现，蚂蚁个体之间是通过一种称之为外激素 ( p h e r o m o n e ) 的物质进行信息传递的【5 7 1 。蚂蚁在运动过程中，能够在它所经过的路 径上留下这种物质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运 动方向。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象 【6 9 j 【 1 ：某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大。蚂蚁 个体之间就是通过这种信息的交流达到搜索食物的目的【7 2 】，如图2 1 所示。 在现实生活中，大量蚂蚁在巢穴与食物源之间形成近乎直线的路径，如图2 1 ( a ) 所示。蚂蚁群体不仅能完成复杂的任务，而且还能够适应环境的变化，如在蚁群运动 路线上突然出现障碍物时，刚丌始各只蚂蚁分布都是均匀的，不管路径长短，蚂蚁总 是先按相同的概率选择各条路径，如图2 1 ( b ) 所示。蚂蚁在运动过程中，能够在其 经过的路径上留下信息素，而且能够感知这种物质的存在及其强度，并以此指导自己 运动的方向，蚂蚁倾向于信息素浓度高的方向移动。相等时间内较短路径上的信息量 就残留的比较多，则选择较短路径的蚂蚁也随之增多，如图2 1 ( c ) 所示。正如前面 所述，大量蚂蚁组成的蚁群集体行为表现出了一种信息正反馈现象，即某一条路径上 走过的蚂蚁越多，则后到蚂蚁选择该路径的概率就越大，在一定的时间内，越短的路 径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被其它的蚂蚁 硕士学位论文 选中的可能性也越大。这个过程会一直持续到所有的蚂蚁都走到最短的那一条路径为 止，如图2 1 ( d ) 所示。 巢穴一一曲嘶鬻絮嚆懈每邕瓣尝桫一m 亭物源 挈噼拳铲锄源 巢穴“世辩蔼喙：势嚣忡h食物源 欺。惭巍。，燃 图2 1 现实中蚁群寻找食物的过程 2 3 1 基本蚁群算法基本原理 蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 是一种随机搜索算法，它基于对自然界 真实蚁群的集体觅食行为的研究，模拟真实的蚁群协作过程。算法由若干个蚂蚁共同 构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。 硕十学位论文 该算法最早由意大利的d o r i g om 等【5 7 1 在1 9 9 1 年提出。d o r i g om 对基本蚁群算法的 ：t ， 论述如图2 2 所示，设a 为巢穴，e 为食物源，h c 为- 二障碍物。由于障碍物的存在， 蚂蚁要想从a 到达e ，或者由e 返回a ，只能由h 或c 绕过障碍物。各点之间的距 离，如图2 2 ( a ) 所示。设每个时间单位有3 0 个蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到达d ，蚂蚁过后留下的信息素为1 。为方便，设信息素停留时间为1 。在初始时刻， 由于b h ，b c ，d h ，d c 均无信息存在，位于b 和d 的蚂蚁可以任意随机选择路径。 从统计的角度可以认为它们以相同的概率选择b h ，b c ，d h ，d c ，如图2 2 ( b ) 所 示。经过一个时间单位后，在路径b c d 上的信息量是b h d 上信息量的两倍。t = l 时 刻，将有2 0 只蚂蚁由b 和d 到达c ，有1 0 只蚂蚁由b 和d 到达h 。随着时间的推 移，蚂蚁将会以越来越大的概率选择b c d ，最终完全选择b c d ，如图2 2 ( c ) 所示。 从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正 反馈过程。 7 纠 d = 1 e l d b l 0 2 3 2 基本蚁群算法模型 回卜 蕊b d 谚n 1 5 hc 蕊b 磁 卜a 回卜 一o 2 0 hc 公 桑 卜a b )c ) 图2 - 2 蚁群算法的原理示意图 蚁群算法最早被用来解决旅行商问题，所以这里我们也以旅行商问题为例，来建 立蚁群算法模型及描述算法实现过程。 2 3 2 i 旅行商问题 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p