（计算机应用技术专业论文）车辆路径问题的量子进化算法研究.pdf

浙江工业大学硕士学位论文 车辆路径问题的量子进化算法研究 摘要 物流业已成为国际经济体系的重要组成部分，是推动经济全球化的重要服务业。但是 物流费用居高不下，特别是运输费用占社会物流费用的比重达到一半以上，是影响物流成 本的重要因素。车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 主要研究物流配送环节车 辆路线的优化，是物流配送优化中的关键一环。该问题是运筹学和组合优化领域著名的n p 问题，随着问题规模的增加会产生指数爆炸，目前的求解方法主要是亚启发式算法。本文 主要研究了一种新型的进化算法一量子进化算法( q u a n t u me v o l u t i o n a r ya l g o r i t h m ，q e a ) 在车辆路径问题中的应用，具体求解以下四类问题：有能力约束车辆路径问题( c a p a c i t a t e d v e h i c l er o u t i n gp r o b l e m ，c v r p ) ，开发式车辆路径问题( o p e nv e h i c l er o u t i n gp r o b l e m ， o v r p ) ，动态网络车辆路径问题( d y n a m i cn e t w o r k sv e h i c l er o u t i n gp r o b l e m ) ，动态需求 车辆路径问题( d y n a m i cd e m a n d sv e h i c l er o u t i n gp r o b l e m ) 。本文的主要成果如下： 1 研究了有能力约束车辆路径问题的量子进化算法求解方法。提出0 一l 矩阵的编码 方法，通过量子旋转门实现进化，引入灾变操作保证解的多样性；分析了算法复杂度；选 用基准实例进行测试，并与其它算法进行了比较。实验结果表明量子进化算法是求解有能 力约束车辆路径问题的有效算法。 2 建立了开发式车辆路径问题的数学模型，研究了求解开发式车辆路径问题的量子 进化算法。算法采用动态调整旋转角机制，混合了最邻近算法和2 o p t 方法增强局部搜索 能力；分析了算法复杂度；讨论了算法参数对于优化结果的影响。选用基准实例进行了测 试。 3 研究了量子进化算法求解动态网络车辆路径问题。建立了动态网络车辆路径问题 的数学模型；构造了测试实例并进行了求解，并对量子进化算法的收敛性进行了证明。 4 研究了量子进化算法求解动态需求车辆路径问题。建立了动态需求车辆路径问题 的两阶段数学模型；第一阶段为预优化阶段，对于已知的需求信息，采用量子进化算法进 行预优化；第二阶段为实时优化阶段，对于实时需求信息，采用遗传算法进行实时优化。 构造测试实例并进行测试。 浙江工业大学硕士学位论文 关键词：车辆路径问题，量子进化算法，开放式，动态网络，动态需求 浙江j 二业人学硕士学位论文 q u a n t u m e v o l u t i o n a r ya l g o r i t h mf o r v e h i c l er o u t i n gp r o b l e m a b s t r a c t t h el o g i s t i c si n d u s t r y ，a ni m p o r t a n ts e r v i c ei n d u s t r yf o rp r o m o t i n ge c o n o m i cg l o b a l i z a t i o n ， h a sb e c o m ea ni m p o r t a n tp a r to fi n t e r n a t i o n a le c o n o m i cs y s t e m t r a n s p o r t a t i o ni st h ek e yp a r ti n t h el o g i s t i c si n d u s t r y t h et r a n s p o r t a t i o nc o s t sa c c o u n tf o rm o r et h a nh a l fo ft h et o t a lc o s to f l o g i s t i c s ，s ot h a ti th a sag r e a ti n f l u e n c eo nt h et o t a lc o s to fl o g i s t i c s v e h i c l er o u t i n gp r o b l e m ， w h i c hi sr e s e a r c ho nh o wt op l a nt h ev e h i c l er o u t e si no r d e rt os a v et h et r a n s p o r t a t i o nc o s t s ，i sa w e l lk n o w nn pp r o b l e mi nt h ef i e l do fo p e r a t i o nr e s e a r c ha n dc o m b i n a t i o no p t i m i z a t i o n f o r l a r g eo rm e d i u ms c a l ep r o b l e m s ，t h e r ei sap r o b l e mt h a tc o m b i n a t o r i a le x p l o s i o nw i l lh a p p e n f o rn pc o m p l e x i t y ，m o s tr e s e a r c h e r sc o n c e n t r a t eo nt h er e s e a r c ho f m e t a - h e u r i s t i ca l g o r i t h m t h ed i s s e r t a t i o nm a i n l ys t u d i e dq u a n t u me v o l u t i o n a r ya l g o r i t h mi ns o l v i n gf o u rv r p m o d e l s ：c a p a c i t yv e h i c l er o u t i n gp r o b l e m ，o p e nv e h i c l er o u t i n gp r o b l e m ，d y n a m i cn e t w o r k s v e h i c l er o u t i n gp r o b l e m ，d y n a m i cd e m a n d sv e h i c l er o u t i n gp r o b l e m t h em a i nc o n t r i b u t i o n s o ft h ep a p e ra sf o l l o w s ： 1 q u a n t u me v o l u t i o n a r ya l g o r i t h mf o rc a p a c i t yv e h i c l er o u t i n gp r o b l e mi sd e e p l ys t u d i e d 0 - 1m a t r i xe n c o d i n gi su s e dt oc o n s t r u c tc h r o m o s o m e s ，q u a n t u mr o t a t i o ng a t ei su s e dt or e a l i z e e v o l u t i o n ，c a t a c l y s mi si n t r o d u c e dt oe n s u r et h ed i v e r s i t i e so ft h es o l u t i o ns p a c e s ，n e a r e s ti n s e r t a n d2 - o p ta lea d o p t e dt oo p t i m i z es u b - r o u t e s c o m p a r e dt ot h er e s u l t so fo t h e ra l g o r i t h m sa l e r e p o r t e d ，t h ee x p e r i m e n t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi sa ne f f i c i e n tm e t h o df o rs o l v i n g 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 m 2 t h em a t h e m a t i c a lm o d e lo fo p e nv e h i c l er o u t i n gp r o b l e mi sf o u n d e d ，a n dq u a n t u m e v o l u t i o n a r ya l g o r i t h mc o m b i n e dl o c a ls e a r c ha l g o r i t h m sa r ep r e s e n t e d r o t a t i o ng a t ew i t h a d a p t i v e l ya d j u s t i n gr o t a t i o na n g l ei su s e dt or e a l i z ee v o l u t i o n ，n e a r e s tn e i g h b o r sa n d2 - o p t a r e i n c o r p o r a t e dt of u r t h e ri m p r o v es o l u t i o n s t h ea l g o r i t h m sp a r a m e t e r sa r ed i s c u s s e d b e n c h m a r k p r o b l e m sa r ec h o s e nf o re x p e r i m e n t 3 q u a n t u me v o l u t i o n a r ya l g o r i t h mf o rd y n a m i cn e t w o r k sv e h i c l er 0 u t i n gp r o b l e mi s s t u d i e d t h eb a s i cc o n c e p t so fd y n a m i cn e t w o r k sv e h i c l er o u t i n gp r o b l e ma r ei n t r o d u c e d t h e m a t h e m a t i c a lm o d e lo fd y n a m i cn e t w o r k sv e h i c l er o u t i n gp r o b l e mi sf o u n d e d b e n c h m a r k p r o b l e m sa r em o d i f i e da n d t e s t 浙江工业人学硕士学位论文 4 t h et w o - s t 印m a t h e m a t i c a lm o d e lo fd y n a m i cd e m a n d sv e h i c l er o u t i n gp r o b l e mi s f o u n d e d t h ef i r s ts t a g ei sp r e - o p t i m i z a t i o ns t a g e ，q u a n t u me v o l u t i o n a r ya l g o r i t h mi sa d o p t e d f o rk n o w ni n f o r m a t i o n t h es e c o n ds t a g ei sr e a l - t i m eo p t i m i z a t i o ns t a g e ，g e n e t i ca l g o r i t h mi s a d o p t e df o rr e a l t i m ei n f o r m a t i o n a tl a s t ，i n s t a n c e sa led e s i g n e da n dt e s t e d k e yw o r d s ：v e h i c l er o u t i n gp r o b l e m ，q u a n t u me v o l u t i o n a r ya l g o r i t h m ，o p e nv e h i c l e r o u t i n gp r o b l e m ，d y n a m i cn e t w o r k s ，d y n a m i cd e m a n d s 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 储虢瓣 吼冲步月站日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 f 。 2 、不保密囱。 ( 请在以上相应方框内打“) 作者签名： 导师签名： 日期：谚件专月劣e l e tl 蓼i ：砷年专月站e t 浙江上业人学硕士学位论文 第1 章绪论 1 1 选题背景及意义 物流业是融合运输、仓储、货运代理和信息等行业的复合型服务产业，涉及领域广， 吸纳就业人数多，促进生产、拉动消费作用大，被誉为经济发展动脉的“加速器”和产业结 构演变的“润滑剂”，现代企业的“第三利润源泉”。近年来，世界现代物流业呈稳步增长态 势，欧洲、美国、日本成为当前全球范围内的重要物流基地。中国物流行业起步较晚，随 着国民经济的飞速发展，物流业的市场需求持续扩大。进入2 l 世纪以来，在国家继续加 强和改善宏观调控政策的影响下，中国物流行业保持较快增长速度，物流体系不断完善， 行业运行日益成熟和规范。 2 0 0 8 年，全国社会物流总额8 9 9 万亿元，同比增长1 9 5 ，保持了较快增长态势。但 是我国物流成本占g d p2 0 ，这种消耗大大高于发达国家1 0 的水平。物流成本的高低， 反映一个国家的经济发展水平。2 0 0 8 年，全国社会物流费用为5 4 5 4 2 亿元，同比增长1 6 2 ， 社会物流费用与g d p 的比率为1 8 1 ，高出发达国家一倍左右。也就是说，这个比率每降 低一个百分点，就等于创造2 8 0 0 亿元的经济效益。因此通过提高物流管理水平和效率， 降低物流成本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率，提高国 际竞争力。从社会物流费用的构成看，运输费用为2 8 6 6 9 亿元，同比增长1 3 2 ，占社会 物流费用的比重为5 2 6 ，是影响物流成本的重要因素。可见该问题对现代物流业发展的 重要性，以及解决好该问题所产生的巨大经济利益。 物流配送是物流系统中的核心功能，在物流配送业务中，配送车辆调度问题的涉及面 较广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的 影响也较大。作为物流配送优化中的关键环，车辆路径问题( v e h i c l er o u t i n gp r o b l e m ， v r p ) 的研究受到人们的广泛关注。该问题是由d a n t z i g 和r a m s e r t l 】于1 9 5 9 年首先提出的， 近五十年来，一直受到运筹学、物流科学、计算机应用等学科的专家极大重视，成为运筹 学与组合优化领域的前沿与研究热点问题。现实生产和生活中，邮政投递问题、飞机、铁 路车辆、水运船舶及公共汽车的调度问题、电力调度问题等都可以抽象为v r p 。随着电子 商务和物流配送的发展，v r p 在各种连锁店、大型商场、快递等领域有广泛的应用前景。 因此对v r p 的深入研究，有较高的科学意义和工程应用价值。 1 浙江上业人学硕七学位论文 1 2 车辆路径问飚概述 l21 车辆路径问题的定义与分类 车辆路径问题又称车辆调度问题( v e h i c l es c h e d u l i n g p r o b l e m ，v s p ) ，通常可以描述为： 对一系列装货点和( 或) 卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足 一定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、 时问限制等) 下，达到一定的目标( 如路程最短、费用晟少、时间最少、使用车辆数最少 等) 。 馓认为不涉及时间的是路径问题，涉及时间的是调度问题。如下图1 - 1 所示。 烈蛔黜 姆 一 遗一憩 姒，温 婚r 喃。嚼， # 9 i 赫神2 * c 图1 - 1 车辆路径问职的示意图 v r p 问题涉及的因素众多，产生很多的模型。根据分类标准不同，这些模型存在不同 的分类方式，具体可见表1 1 所示。 浙江上业大学硕士学位论文 表1 1 车辆路径问题分类表 分类标准模型 路由过程中相关信息是否可变静态车辆路径问题，动态车辆路径问题 确定性车辆路径问题，不确定性车辆路径问题；不确定性 己知信息的特征 车辆路径问题可分为随机、模糊、韫糙三类 约束条件有能力约束车辆路径问题，有时间窗约束车辆路径问题； 时间窗可分为硬时间窗和软时间窗两类 配送中心多少单配送中心车辆路径问题，多配送中心车辆路径问题 行驶路线是否封闭 封闭式车辆路径问题，开放式车辆路径问题 优化目标单目标车辆路径问题，多目标车辆路径问题 1 2 2 车辆路径问题的国内外研究现状 车辆路径问题的研究经过5 0 多年的发展，衍生出众多模型，求解算法更是层出不穷。 早在1 9 8 3 年，b o d i n 等人在关于v r p 的研究综述的文章中，列举了6 9 9 篇相关参考文献。 在1 9 9 5 年出版的运筹学与管理科学手册中，第八卷专门用来讨论车辆路径问题。2 0 0 2 年，p a o l ot o t h 和d a n i e l ev i g o l u 在其出版的著作中，对v r p 的最新研究进展和发展趋势 进行了全面的分析。车辆路径问题是n p 难题，具有较强的实际应用背景，研究者们提出 了许多求解的方法，力图求出该问题的最优解，近似解或满意解。基本上这些方法基本上 可以分为三类： 1 2 2 1 精确算法 精确算法又称为最优化算法，指能够通过有限的计算和推理得到优化问题的最优解的 算法【2 卅。研究的比较多的精确算法有：最小k 树法，分支定界法，割平面法，网络流法， 动态规划法等。这一类算法能够碍到问题的精确解，计算复杂度很大，只能用来求解小规 模的问题，较大规模的问题无法避开指数爆炸问题，求解时间过长，因而不能很好地满足 实际应用的需要。 1 2 2 2 经典启发式算法 启发式算法意为通过对过去经验的归纳推理以及实验分析来解决问题的方法。启发 式方法要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而比较基本的模型 及算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径。用启发 式方法解决阀题时强调“满意”，常常是得到满意解，决策者就认为可以了，两不去一味的 浙江：l 业人学硕士学位论文 追求最优性。之所以这样，一方面很多问题不存在严格最优解( 例如目标之间矛盾的多目 标问题) 。另一方面对有些问题，得到它的最优解所花的代价太大，而且从实际决策的需 要出发，有时要求最优解没有意义。车辆路径问题研究至今，研究者提出了众多的启发式 算法，大体可以分为三类： 1 构造启发式算法 构造启发式算法根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有 的点都被安排进线路为止。该类算法的每一步，需要把当前的线路构形( 很可能是不可行 的) 跟另外的构形( 也可能是不可行的) 进行比较并加以改进，后者或是根据某个判别函 数( 例如总费用) 会产生最大限度的节约的构形，或是以最小代价把一个不在当前构形上 需求对象插入进来的构形。比较著名的构造启发式算法有：节约法，插入法等。 2 两阶段启发式算法 学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，为此提 出了两阶段法。第一阶段得到可行解，第二阶段通过对客户的调整，在始终保持解可行的 情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数 的值得到改进，一直持续到不能再改变目标函数值为止。两阶段算法又可分为两类： ( 1 ) 先安排线路后分组的方法( r o u t ef i r s tc l u s t e rs e c o n d ) 这种方法首先构造一条或几条很长的线路( 通常不可行) ，它包括了所有需求对象， 然后再把这些很长的线路划分成一些短而可行的线路。具体求解时，一般是先解一个经过 所有客户的旅行商问题，形成一条线路，然后根据一定的约束( 如车辆容量等) 对它进行 划分。 ( 2 ) 先分组后安排线路的方法( c l u s t e rf i r s tr o u t es e c o n d ) 这种方法先把节点和弧的需求进行分组，然后对每一组设计一条经济的线路。如g i l l e r t 和m i l l e r 的s w e e p 算法，其目的在于形成需求点的径向区域，从车场发出的射线扫过这个 区域，使不超过车辆容量的需求点组成一个区域，一个区域就是一个组，当形成一系列这 样的组后，再对每一组中的各点安排线路。 比较著名的两阶段法有：分派启发式算法，s w e e p 扫描法，f i s h e r 的广义分配算法。 3 改进启发式算法 改进启发式算法一般是对构造算法和两阶段法求得结果进行改进的算法。有针对单条 路线改进的2 - o p t ，3 - o p t ，o r - o p t 等，针对多条线路的串交换( s t r i n gc r o s s ) ，串重新分 配( s t r i n gr e l o c a t i o n ) 等方法。 一4 一 浙江j 业人学硕士学位论文 1 2 2 3 亚启发式算法 亚启发式算法包括禁忌搜索( t a b us e a r c h 。t s ) 算法、模拟退火算法( s i m u l a t e d a n n e a l i n g , s a ) 、遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 、粒子群算法( 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 ) 、蚁群算法( a n tc o l o n ya l g o r i t h m ，a c o ) 和人工神经网络( a r t i f i c i a l n e u r a ln e t w o r k ，a n n ) 等。 1 禁忌搜索算法 1 9 9 4 年g a r c i a 等人【7 】首先将t s 算法用于v r p t w 问题。运用s o l o m o n 的插入启发式 算法构造初始解，然后用2 - o p t 和o r - o p t 改进解。此后研究者提出了诸多的改进算法，如 增加多样化策略，减少车辆数目的策略，各种复杂的后优化过程，或者与模拟退火，遗传 算法结合，并行t s 算法，在搜索过程中允许部分非法解存在等等。 t s 算法对初始解有很强的依赖性，多数研究者采用和g a r c i a 等人一样的方法，即 s o l o m o n 插入法作为初始化算法，但也有不少学者使用不同的初始化方法如：c o r d e a u 等 人【8 】用改进的扫描法( s w e e ph e u r i s t i c ) 产生初始解，l 锄等人9 】建立一个未访问客户的候 选表，通过对表中客户进行换位等操作产生初始解，b r a n d a o t l 0 】使用下界算法和k t r e e 算 法产生初始解。为了降低搜索的复杂性，研究者提出一些特殊的策略，来限制领域的范围， 如t a i l l a r d 等人【1 1 】用将线路按照在极坐标中的重心进行分组等。为了减少线路和改进线路， 各种改进启发式算法如2 - o p t ，3 - o p t ，o r - o p t ，c r o s s e x c h a n g e ，g e n i e x c h a n g 等被采 用，这些算法的使用虽然对提高解的质量有很大的帮助，但同时也增加了大量的计算时间。 大多数t s 算法都运用了多样化的搜索引导策略。r o c h a t 等人【1 2 1 提出的“适应性记忆法 ( a d a p t i v em e m o r y ) ，其思想是将搜索过程中找到的优秀解存储起来，然后通过这些解的 组合，产生t s 的初始化新解。g e h r i n g 等人【1 3 】将t s 与演化策略( e s ) 混合使用，研究了 两阶段优化方法。第一阶段用演化算法来优化车辆数目，这一阶段初始解通过节约法产生， 演化规则主要通过基于2 - o p t 和o r - o p t 的变异算子进行。第二个阶段用t s 来优化总的路 线长度，这里是使用并行协同化的思想，几个求解进程通过交换解信息互相协作。 2 遗传算法 t h a n g i a h 等人【1 4 】于1 9 9 1 年首先将遗传算法应用于有时间窗的车辆路径问题。他们使 用先分组后线路的策略，首先用遗传算法搜索客户的排列顺序，然后用廉价插入法构造分 组内的线路，使用九i n t e r c h a n g e 改进线路。b e r g e r 等人【1 5 】采用双种群算法，让两个种群并 行进化，第一个种群最小化行车路线，第二个种群最小化时间约束。p o t v i n 等人【1 6 】提出了 一种g e n e r o u s 的遗传算法，提出两种专用的交叉算子：顺序交叉和路径交叉用于车辆 一5 一 浙江上业人学硕士学位论文 路径问题的求解，变异算子用来减少线路数，选择策略使用了所谓的“线性等级模式” ( l i n e a rr a n k i n gs c h e m e ) ，每个个体的选择概率和它的等级有关。而等级的平定是根据种 群规模和适应度的情况。g e h r i n g 等人【1 7 】研究了两种进化策略在车辆路径问题中的应用。 在他们的算法中，个体用一个所谓的“参数策略”的矩阵表示，这个矩阵不仅包括解向量， 还包括进化需要的因素，如交叉和变异操作。这些策略包括随机局部搜索策略实施的频率； 用一个二元参数控制算法在最小车辆数目和最短的距离之间轮流搜索。b e r g e r 等人【1 8 】使用 随机插入算法产生初始解，使用改进的大领域搜索算法( l n s ) 和改进的s o l o m o n 插入算 法作为交叉算子和变异算子，来重新分配客户以减少线路，线路内使用最邻近算法重新排 序。j u n g 等人【i9 】使用s o l o m o n 插入法初始化，交叉算子定义为根据解的二维映像和最近 邻居来选择弧，变异算子使用o r - o p t ，2 - o p t 。b o u t h i l l i e r 等人【2 0 1 使用结合2 - o p t ，3 - o p t 等的构造算法产生初始解，交叉算子使用边重组交换，变异算子使用2 - o p t ，3 - o p t ，o r - o p t 。 3 模拟退火算法 模拟退火算法也是一种局部搜索算法，但和禁忌搜索不同，s a 是概率性的搜索算法， 而t s 是确定性的。模拟退火算法是局部搜索算法的扩展。不同于局部算法之处是以一定 的概率选择邻域内费用最大的状态。t i a n 等人【2 1 】使用一种基于最优接受策略的s a 算法求 解车辆路径问题，使用前推插入算法构造初始解，将s a 与2 - o p t 结合共同优化，在算法 过程中使用温度重启机制，在到达最终温度后，根据初始温度和当前最优值对应的温度重 新启动算法。“等人【2 2 】研究了s a 结合t s 的混合优化算法，使用s o l o m o n 插入算法构造 初始解，使用t s 算法中的移位和交换算子对线路内和线路间的客户排列，s a 算法作为控 制程序，根据当前的最优解和设定的温度进行搜索。b e n t 等人【2 3 】提出了一个两阶段混合优 化算法，第一个阶段使用s a 优化车辆数，使车辆数最少，第二个阶段使用大领域搜索算 法( l a r g en e i g h b o u r h o o ds e a r c h ) 优化客户的排序，使线路距离最短。c z e c h 等人【2 4 】研究 了并行s a 在车辆路径问题中的应用，在求解s o l o m o n 实例中有很好的表现。s a 算法结合 最邻近算法还在多车型车辆路径问题中得到引用 2 5 】。s a 算法的收敛速度比较慢，在车辆 路径问题中的应用比较少。 4 蚁群算法 b e m db u u n h e i m e r 等人【2 6 之7 】首先将蚁群算法应用于车辆路径问题，针对冲问题，设 计了专门的蚁群转移选择策略；在蚁群搜索完后，用2 - o p t 法优化路径。j o h n 等人【2 8 】在蚁 群算法中使用2 - o p t 和候选表对线路进行改进，并对多种群蚁群算法进行了研究实验。a n n e 等人【2 9 1 研究了蚁群算法在有回程载货的车辆路径问题中( v r p b ) 的应用。m a r e 等人【3 0 】 一6 一 浙江工业大学硕士学位论文 用节约法构造蚁群算法的初始解，取得了比较好的结果，在此基础上，研究了分解蚁群算 法，首先使用s w e e p 算法将客户分组，然后使用节约蚁群算法求解各个分组内的排序，最 后将各个分组解进行合并，并将信息素进行更新。g a m b a r d e l l a 等人1 3 1 】将蚁群算法用于有 时问窗的车辆路径问题。在论文中，作者用两个种群来优化问题，一个优化车辆数目，一 个优化总路线长度。m o n t e m a n n i 等人【3 2 】研究了蚁群算法在动态车辆路径问题中的应用，提 出了事件管理，蚁群算法，信息素保存策略这样由三个元素组成的一个系统框架。此外， 刘志硕1 3 3 出】、刘云忠f 3 5 1 、张涛【3 6 】等人研究了改进的蚁群算法在车辆路径问题中的应用。 5 粒子群算法 黄岚在其博士论文中将粒子群算法应用于有能力约束的车辆路径问题的求解，论文中 借鉴粒子群算法在t s p 问题中的编码和速度状态定义规则，是按照先线路后分组的模式进 行求解。李宁【3 7 3 8 1 研究使用两维实数编码方案的粒子群算法求解有能力约束和有时间窗两 类车辆路径问题，这种编码方式，解码的过程比较复杂。肖健梅等人【3 9 加1 分别研究了实数 编码和整数编码两种方案的粒子群算法在车辆路径问题中的应用，实数编码方面按照客户 和车辆总数统一编码，每个元素值的大小表示客户在总路径中的访问顺序。整数编码是在 不同的线路中加入分隔符，然后将其作为t s p 问题求解，但文中对如何在状态更新和计算 速度时处理分隔符，作者没有明确阐述。c h e n 等人研究了离散粒子群算法在车辆路径问 题中的应用，与启发式算法结合进行全局和局部搜索，同时用模拟退火算法改进。邱晗光 等人1 4 2 】将遗传算法、模拟退火算法与粒子群算法结合，求解开放式的定位分配车辆路径问 题。为了便于遗传算法的交叉操作，使用一种三维的整数编码方法。徐杰等人【4 3 1 将带变异 算子的粒子群算法用于多目标车辆路径问题。赵燕伟等人m 4 7 】运用粒子群算法求解了多种 车辆路径问题，取得了不错的效果。 6 其他优化算法 除了上述的智能优化算法，人工神经网络，约束规划方法( c o n s t r a i n tp r o g r a m m i n g ) ， 引导领域搜索算法( g u i d e dl o c a ls e a r c h ) ，随机适应贪婪算法( g r e e d y r a n d o m i z e d a d a p t i v e s e a r c h ) ，门槛接收法( t h r e s h o l da c c e p ta l g o r i t h m ) 等算法在车辆路径问题中也有应用，有 兴趣的读者可以查看相关资料。 1 3 量子进化算法的国内外研究现状 量子计算( q u a n t u mc o m p u t i n g ) 是量子力学和计算机科学相结合的产物，是一种新兴 计算理论。自2 0 世纪8 0 年代初b e n i o f f 和f e y n m a n 提出了量子计算的概念后，1 9 9 4 年s h o r 一7 一 浙江：l 业人学硕士学位论文 提出大整数质因子分解的量子算法【4 引，1 9 9 6 年g - r o v e r 提出无序数据库的量子搜索算法【坝， 量子计算以其独特的计算性能引起了广泛瞩目，并迅速成为研究的热点【5 0 1 。 量子计算利用了量子理论中有关量子态的叠加，纠缠和干涉等特性，通过量子并行计 算( q u a n t u mp a r a l l e l i s m )来求解问题。进化算法是模拟自然界生物进化机制的一种启发 式搜索算法。而量子进化算法是将量子系统中的量子叠加性和并行性与传统的进化算法相 结合，将量子的概率幅表示应用于染色体的编码，使一个染色体能够表征多个不同态的叠 加，比传统的进化算法更具并行性。量子进化算法具有一系列众多优点：算法通用，不依 赖于问题信息；算法原理简单，容易实现；种群分散性好，小种群个体可以对应多个个体 编码；群体搜索，具有极强的全局搜索能力；协同搜索，具有利用当前最优个体信息算法 进一步搜索的能力；收敛速度快，能够很快地发现最优解；易于与其他算法混合等。 1 3 1 量子进化算法的理论研究 进化算子设计是量子进化算法的重要研究内容。基本量子进化算法中没有传统的遗传 操作，因此可通过引入交叉、变异、灾变等遗传算子提高算法的性能。李斌等【5 i 】对量子遗 传算法进行了改进，提出基于量子概率表达的遗传算法，其核心是利用量子概率编码个体 的独立搜索能力，通过多个个体同时搜索以增强算法的搜索性能，同时还设计了一种新的 交叉算子并定义了一个单量子比特变异算子。y a n g 掣5 2 j 引入量子非门作为变异操作，依 一定的概率从种群中选择一个或多个个体，随机选择一个或多个位置实施量子非门操作进 行变异。 f a n g 等【5 3 j 借鉴量子相干特性提出了一种全干扰交叉算子，同时引入多个个体进 行交叉操作，即将多个个体的染色体拆开，依照预先拟定的准则重组以构造新的个体，即 使在多个交叉个体完全相同的极端情况下也可以产生新个体。l i 等【5 4 1 指出基本的量子遗 传算法利用量子旋转门进行种群的进化，又通过观察量子染色体的状态来生成所需要的二 进制解，这一概率操作过程具有很大的随机性和盲目性，引入免疫算子并应用于待评价种 群。l i 等【5 5 】在基本量子遗传算法中引入了量子交叉和变异以克服早熟收敛并增强算法搜 索能力。王凌等【5 钳8 1 研究了量子遗传操作，通过灾变操作避免陷入局部极小。 改进量子门以实现量子门旋转操作。h a r t 等【5 9 】对原有量子旋转门在概率幅趋近于1 或 0 时的情况进行了修正，提出了一种h a d a m a r d 门的旋转门操作以避免算法陷入局部极小。 c h e n 等【删提出了一种混沌更新旋转门以替代原有的量子旋转门操作。量子旋转门操作需要 多次的比较和计算以确定旋转角，算法的计算量和复杂性较大。同时，c h e n 等也在j o r d a n 6 1 】 构造的理论框架下证明了该混沌旋转门量子遗传算法的完全收敛性。杨淑嫒等提出了一种 算术形式的量子旋转门操作，采用当前最好个体作为量子旋转的指导并将该指导个体所带 一8 一 浙江上业人学硕士学位论文 有的信息在下一代种群中进行分享。 构造新型算法框架一直是量子进化研究的热点。h a r t 等【5 9 】研究发现，量子位的初始值 对量子进化算法的性能有着显著的影响，由此提出了一种两阶段的复合量子遗传算法框 架。在第一阶段中随机初始化量子位，经过若干次量子进化搜索后，将得到的优良结果用 于第二阶段量子遗传算法的初始化，进行进一步的解空间的全局搜索。王凌等 5 6 - 5 s 】提出了 混合量子遗传算法的框架，在该混合算法中，纵向为量子遗传算法基于量子门更新的搜速 过程，横向则是传统遗传算法基于二进制、实数编码或者组合空间的遗传搜速过程。基于 不同的解表征空间上搜索的混合，有利于丰富搜速行为和增强搜速能力，进而避免早熟。 李士勇等【6 2 】提出一种求解连续空间优化问题的量子粒子群优化算法，用量子位的概率幅对 粒子位置编码，用量子旋转门实现粒子移动，完成粒子搜索：用量子非门实现变异，提高 种群多样性，优于基本粒子群算法。冯斌等【6 3 】提出将一种基于量子行为的粒子群优化算法 应用于作业车间调度问题。将该问题中的每个调度组成一个多维向量，以此向量作为量子 粒子群优化算法中的粒子进行进化，由此在解空间内搜索最优解。实例仿真结果表明，该 算法收敛速度快、全局收敛性能好，可以得到比遗传算法、粒子群优化算法更佳的调度效 果。俞洋掣删提出了两种混合量子进化算法。第一种算法叫做嵌入式粒子群量子进化算法， 其主要思想是将简化的p s o 进化方程嵌入q e a 的进化操作中，简化了q e a 算法的结构， 增强了q e a 跳出局部极值的能力。第二种算法叫做量子二进制粒子群算法，其主要思想 是将q e a 中的量子染色体的概念引入二进制粒子群算法( b p s o ) ，提高了b p s o 算法保 持种群多样性的能力和运算速度。y a hw a n g 等【6 5 】提出了一种基于量子进化算法的量子粒子 群算法，采用量子角代替以往的量子比特编码，将量子角表示的粒子群进化机制代替传统 的量子门进化，计算结果优于基本的量子进化算法。 种群规模的可变体现了量子进化算法的灵活性。传统的遗传算法中染色体与解之间是 一对一关系，而量子进化算法则可以采用一个染色体表示多解。因此，算法可以用较小的 种群规模表示多个的问题的解。t a l b i 等 6 6 - 6 7 将“小生境”概念引入基本量子遗传算法中，并 应用于旅行商问题中。该算法中，初始种群仅包含4 个路径生成矩阵，且每个矩阵的每个 元素均用量子位表示。算法运行中，量子位表示矩阵生成若干个可行路径矩阵，进行交叉、 变异、矩阵内各行随机移动等操作，生成新的个体。种群更新时，选取三个最优个体，并 随机选择一个个体以保持种群多样性。该算法充分利用了量子位表示方法可以表示多个解 的特性，保持解种群的分散特性。 实现并行算法体现了量子进化的快速高效性。量子进化算法的表示形式决定了种群中 浙江上业人学硕士学位论文 的每个个体可以同时表示多个状态，但在基本的量子进化算法中，种群中的每个个体仅由 其本身概率幅和当前最好解个体决定，个体与个体之间的联系不紧密。因此，将整个种群 划分为若干个子种群，每个子种群独立进行进化操作，并在一定的进化代数之后进行个体 的交换，即所谓“移民”操作以传递信息，如此可实现并行算法。h a n 等【5 9 】在基本量子遗传 算法的基础上引入了两种“移民”策略以加强种群个体之间信息的交互，其中包括“局部移 民”操作和“全局移民”操作。前者用于将搜索得到优秀解包含的信息在种群个体间进行交 互，后者用于将搜索得到优秀解包含的信息在种群个体于最优解个体间进行交互。另外， h a r t 等【5 8 1 分别设计了针对4 个和1 6 个处理单元信息“星型”交互结构，采用粗粒度并行策 略进行最优解个体的交互。z h a n g 等p 9 】也提出了一种新型的粗粒度并行量子遗传算法，采 用一种“分等级环形模型”的交互式结构。杨俊安等【| 7 0 】提出一种多宇宙并行量子遗传算法， 将所有个体按照一定的拓扑结构分成一个个独立的子群体。李映等基于粗粒度模型也提出 了一种并行量子进化算法和局部搜索算法相结合的混合算法。 1 3 2 基于量子进化的组合优化与调度研究 鉴于量子进化算法的若干优越性，它已在组合优化领域得到应用如下： 背包问题：k a z a k o v a y a 7 1 】将一种改进的量子算法应用于背包问题；h a r t 等【5 9 】将所提 出的量子遗传算法应用于背包问题2 0 0 4 ；y a n g 等【5 3 】将所提出的基于简单算术量子旋转门 操作的量子遗传算法应用于背包问题2 0 0 4 ；l i 等唧】将所提出的免疫量子遗传算法应用于 背包问题；t a l b i 等【删将所提出的基于“小生境”的量子遗传算法应用于背包问题；w a n g y a n 7 2 1 提出了一种混合的粒子群量子进化算法用于求解0 1 背包问题：k i my e h o o n 7 3 】提出 了一种多目标量子进化算法用于求解多目标0 1 背包问题；邢焕来等【_ 7 。刀提出了一种解决组 合优化问题的改进型量子遗传算法( n i q g a ) 。 t s p 问题：t a l b