（系统工程专业论文）有时间窗和在前约束车辆路径问题的蚁群优化.pdf

西安建筑科技犬学硕士学位论文 有时间窗和在前约束车辆路径问题的蚁群优化 专业：系统工程 研究生：杨瑞臣 导师：云庆夏教授博导 摘要 车辆路径问题是物流配送领域的重要问题，蚁群算法是种新的元启发算法。本 文研究的就是把改造后的蚁群算法用于特殊的车辆路径问题一有时间窗和在前约束 车辆路径问题的求解。 本文对蚁群算法进行了改进。通过深入分析蚁群优化机制，针对时间窗车辆路径 问题，提出了基于单位节约值和时间紧迫性的可见度以及基于鬈优解的信息素浓度更 新规则，并综合运用了推广的2 一交换法进行邻域搜索。对基准问题的仿真实验表明， 能在3 个循环内得到优良结果。 本文还对在前约束提出明确定义，分析了含有在前约束的车辆路径问题研究的实 际价值。在给定了在前约束的数学表示法的基础上，根据约束关系的不同，对在前约 束进行了系统的分类。 本文实现了在前约束问题的算法。包括剖析在前约束关系、确定不可分集合，将 问题初始化为相对普通的问题。实现时，充分发挥禁忌表的禁忌作用，变在前约束为 禁忌约束并引入信息素突变规则来实现禁忌点解除禁忌届的搜索道路畅通性。通过在 基准问题s o l o m o n sv r p t wc 1 0 1 2 5 基础上加入不同的在前约束构造问题后，进行仿 真实验，结果十分理想。 本文探讨了特殊邻域搜索策略。在在前约束的限制下，给出了路段保护边交换法 的思想，描述了路径保护3 交换法词典搜索的实现原理及详细过程，实验验证了与蚁 群算法相结合的可行性，对比表明能使算法在较少的循环次数下收敛。 关键词：物流工程、车辆路径问题、时间窗、在前约束、蚊群算法、邻域搜索 论文类型：应用研究 西安建筑科技大学硕士学位论文 o p t i m i z a t i o nf o r v e h i c l er o u t i n gp r o b l e m w i t ht i m ew i n d o w sa n dp r e c e d e n c ec o n s t r a i n t sb ya n t c o l o n y s p e c i a l t y ：s y s t e me n g i n e e r i n g n a m e ： y m a gr u i c h e n i n s t r u c t o r ：p r o f y u nq i n g x i a v e h i c l er o u t i n gp r o b l e mf r e d ) i sa r ti m p o r t a n tp r o b l e mi np h y s i c a ld i s t r i b u t i o nw h i l e a n tc o l o n ys y s t e m ( a c s ) i san e wm a t e h e u r i s t i ca l g o r i t h m t h i sp a p e ru s e sa l li m p r o v e d a c st os o l y et h ev r p 、i t ht i m ew i n d o w sa n dp r e c e d e n c ec o n s t r a i n t sr v r p t w p c ) a s p e c i a lv r p a c si si m p r o v e di nt h i sp a p e r a f t e rd e e p l ya n a l y z i n ga c s ，t h ev i s i b i l i t yb a s e do nu n i t s a v i n ga n dt i m eu r g e n c ya n dt r a i lu p d a t er u l eb a s e do nk - o p t i m a ls o l u t i o n sf o rv r p t wa r c p u tf o r w a r d 2 - o p tc r o s s o v e ri sa l s ou s e dt of i n i s ht h el o c a ls e a r c h e x p e r i m e n to nt h e s t a n d a r dv r p p r o b l e ms h o w st h a tas a t i s t i e ds o l u t i o nc a nb ef o u n di nt h r e ec y c l e s p r e c e d e n c ec o n s t r a i n ti sa l s od e f i n e di nt h i sp a p e ra n dt h ew o r t h i n e s sa b o u tr e s e a r c ho n t h ev r p w i 也p r e c e d e n c ec o n s t r a i n t si si n v e s t i g a t e d p r e c e d e n c ec o n s t r a i n ti sc l a s s i f i e da f t e r t h em a t h e m a t i c a ln o t a t i o ni sg i v e n t h ea l g o r i t h mt os o l v et h ev r pw i t hp r e c e d e n c ec o n s 打a i n t si s p r o p o s e d w h i c h i n c l u d e sp r e c e d e n c ea n a l y s i s ，u n d i v i d e ds e tf i n d i n ga n dt r a n s f o r m a t i o np r o b l e mf r o ms p e c i a l t on o r m a l t a b ut a b l ei su s e dt od e a lw i t hp r e c e d e n c ea n d 订a i lm u t a t i o nr u l ei si n t r o d u c e dt o e n s u r et h a ti ti sp o s s i b l et or e a c ht h et a b up o i n ta f t e rt a b ub r o k e n v r p t w p ci sc o n s t r u c t e d t h r o u g ha d d i n gs o m ep r e c e d e n c ec o n s t r a i n t st os o l o m o n sv r p t wc 1 0 1 2 5 ，as t a n d a r d v r p p r o b l e m e x p e r i m e n t ss h o wt h a tt h ew a y t os o l v ev r p t w p ci sf e a s i b l e a s p e c i a l l o c a ls e a r c hi sd i s c u s s e di nt h i s p a p e r t h e i d e ao f p a t h - p r e s e r v e - - e d g e - - e x c h a n g e f o r p r e c e d e n c e c o n s t r a i n t si s g i v e n a n d l e x i c o g r a p h i c - p a t h - p r e s e r v i n g - 3 一e x c h a n g ei sd e p i c t e d ，e x p e r i m e n ts h o w st h a ta d d i n gt h e e x c h a n g et oa c si se f f e c t i v e c o m p a r i s o nt e s ti n d i c a t e st h a ts a t i s f i e ds o l u t i o n sa l w a y so c c u r d u r i n gf e w e rc y c l e s k e y w o r d s ：l 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 ，t i m ew i n d o w s ，p r e c e d e n c ec o n s t r a i n t s ， a n tc o l o n ys y s t e m ，l o c a ls e a r c h t y p eo f t h et h e s i s ：a p p l i c a t i o nr e s e a r c h i i 声明 v 、8 4 1 7 7 2 本人郑重声明我所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也刁i 包 含本人或其他人在其它单位已申请学位或为其它用途使用过的成果。 与我一同工作的同志对本研究所做的所有贡献均已在论文中作了明确 的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：杉绵厦日期：矽矿士乒。泞 j 关于论文使用授权的说明 本人完全了解西安建筑科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校 可以公布论文的全部或部分内容，可以采用影印、缩印或者其它复制 手段保存论文。 ( 保密的论文在论文解密后应遵守此规定) 论文作者签名：奶啤臣导师签名：扩久乏 目期：脚f 彳群 j 。 西安建筑科技大学硕士学位论文 1绪论 车辆路径调度方案的合理性与企业的经济效益密切相关，毫无疑问的成了现代物 流领域研究的重要课题。本章首先概括介绍了现代物流在经济发展中的重要地位以及 乍辆路径调度的重要性，然后具体分析了车辆路径调度问题( v r p ) 和旅行商问题( t s p ) 以及它们之间的约束关系。最后提出本文研究主要问题：有时间窗和在前约束的车辆 路径问题( v r p t w p c ) 。 1 1现代物流中的车辆调度问题 1 1 1 现代物流的经济地位 现代物流( l o g i s t i c s ) ，是指为了实现顾客满意，连接供给主体和需求主体，克服 空间和时间阻碍的有效、快速的商品、服务流动经济活动过程，是指以现代信息技术为 基础，整合运输、包装、装卸、搬运、仓储、流通加工、配送、回收加工及物流信息 处理等各种功能而形成的综合性物流活动模式。 现代物流是一个全新的系统概念，它包含了产品生命周期的整个物理性位移的全 过程，从采购物流开始，经过生产物流，再进入销售物流，到达消费者手中，最后还 有回收物流。在这整个物流过程中，要经过包装、运输、装卸搬运、仓储、流通加：工、 配送、信息处理等作业环节。因此，现代物流涵盖了国民经济的若干个行业，它既是 经济发展的产物，又是经济发展的支柱；既是一种增值性的经济活动，又是增加成本、 影响生态环境的经济活动。 现代物流作为一种先进的组织方式和管理技术，是对流通业的一场革命。现代物 流产业在国家经济发展中的地位和作用体现在三个方面： 现代物流产业是国民经济的支柱产业和新的经济增长点； 现代物流产业是流通业的物质基础； 现代物流产业是企业在降低物资消耗、提高劳动生产率以外的第三利润源泉。 1 1 2 我国物流业的现状及存在的问题 物流产业涉及铁路运输、公路运输、内河和海上运输、管道运输、航空运输、邮 政业、仓储业、装卸业、包装业、配送业、流通加工业、物流信息业等。这些产业的 发展情况如何，对国民经济发展举足轻重。 我国物流成本占g d p 的比重太高，降低社会物流总成本是中国经济发展模式转变 f 勺重要标志，是提高国民经济运行质量的综合性指标。物流的落后是中国粗放式经济 l 西安建筑科技大学硕士学位论文 发展模式的突出表现之一，物流水平是一个国家综合幽力的重要标志。发达幽家物流 胱务成本占g d p 的比重为1 0 左右，美国低于1 0 。世界银行估算，中国的物流成 木占g d p 的比重为1 6 7 。如果中国物流成本占g d p 比重能从1 6 7 降到1 5 ， 每年将为全社会直接节约2 4 0 0 多亿元物流成本，并为企业和社会带来极为可观的经济 效益。因此，提高物流的综合效益是中国经济发展的重大战略问题i 】”l 。 1 1 3 现代物流中的车辆路径问题 所谓的车辆路径问题，就是车辆和路径的恰当选取，运输规划的合理制定问题。 解决此问题，可用加快对客户需求的响应速度，提高服务质量，增强客户对物流环节 的满意度，降低服务商运作成本。 现代物流的基本涵义为“按用户要求，将物的实体从供应地到需求地转移的过程”。 深入分析物流问题，大部分都可以归类为车辆路径调度问题或者说车辆路径调度问题 在物流配送中占有绝对重要的地位，除了铁路、公路等运输业，装卸、配送等也可以 归类为车辆路径调度问题的有机组成部分。目前，我国物流产业效率较低，损失浪费 十分惊人，有专家估计，我国仅汽车空驶率就达3 7 ，相当于1 5 0 万辆载重汽车来回 空跑【3 ”。由此可见，车辆路径调度问题能否较好解决，直接关系到企业的经济效益， 影响我国整个物流产业的健康迅速发展。 在竞争日益激烈的今天，企业只有以市场为核心去适应不断变化的环境并及时对 市场作出反应，以低的成本、快的速度，在正确的时间和地点为消费者或用户提供满 意的产品和服务，才能在竞争中占有优势。产品分销渠道的优化是达到上述目标的关 键步骤之一。分销渠道是指产品在其所有权转移过程中从生产领域进入消费领域的途 径，而分销渠道中的物流管理则是指通过有效地安排产品的仓储、管理和转移，使产 品在需要的时间到达需要的地点的经营活动。实际也是车辆路径问题的应用研究。 可见车辆路径问题在物流领域占有相当重要乃至最重要的地位，问题的研究与解 决具有可观的经济效益。本文将对此加以探讨。 卜 面先对各类车辆路径问题进行简单介绍，并分析它们之间的约束强弱关系，然 后回顾v r p 问题的系列求解方法。 t2 车辆路径问题 车辆路径调度问题是由g d a n t z i g 首先提出的f 9 】，n c h r i s t o f i d e s 在后来总结深化| 6 。 车辆路径问题，或者称作车辆路径调度问题、物流配送路线问题、v e h i c l er o u t i n g p r o b l e m ( 简称v r p ) 问题等，是现代物流研究中的一项重要内容。 2 西安建筑科技大学硕士学位论文 车辆路径问题，顾名思义，主要解决的是派多少辆车走什么样的路线进行运输的 问题。给定了相互连通的若干有货物需求的顾客点，若干车辆从配送中心出发，完成 对所有顾客点的配送任务后回到配送中心，要求所走的路线不能重复，目的是找到最 小成本的配送方案。此问题即为v r p 问题。 车辆路径问题是组合优化领域中著名的n p h a r d 问题之一，与众多的实际问题都 有相似性，如铁路运输、公交调度、水道航线、路由选择等，v r p 研究具有相当大的 实际意义。 根据实际约束条件的差异，车辆路径闰题种类千变万化，并各具特色。 1 2 1 经典车辆路径问题( c v r p ) 所谓经典车辆路径问题，其实就是在车辆路径的调度中，仅仅考虑最基本的货车 载重量约束( 或容量约束) 的最一般化的运输问题，即有容量约束的车辆路径问题 ( 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 ，简记为c v r p ) 。 c v r p 涵义： 经典的v r p 是由一个服务中心( 或称为仓库、车场) 的车辆向多个服务需求点( 或 称为客户、顾客点) 进行配送服务，在已知待服务的客户和出发点的位置、顾客需求 及车辆的最大负荷的前提下，设计车辆配送路径，规划设计方案，使运输成本最小化， 即总代价最小( 车辆尽量少，行车总距离尽量短) 。可见v r p 闯题实际是多目标组合 优化问题，大多数的情况下，我们以派出车辆最少，即运输路线条数最少为首要目标， 行车总距离最短，即总代价最小为次要目标。 经典v r p 要求满足以下条件及假设： 所有的配送车辆以配送中心为起点并最终回到配送中心； 每条配送路径上各需求点的需求量之和不超过车辆的载重量； 每个需求点的需求由且仅由一辆车一次送货满足。 c v r p 模型： 我们用v = v o ，v 1 ，v 2 ，k j 表示一系列点的集合。元素v d 来表示配送中心， v ，( f - 1 , 2 ，h ) 表示各顾客，一= v 。，v 刊v 。v ，y ，i 暮 为一系列弧的集合，d ! l 与弧( v 。v j ) 相联系，表示u 到v j 的距离，对于顾客n 已知了需求量g f ( 其中q o = o ) 。 假定配送中心最多可用k 辆车对顾客点进行配送，每辆车载重量为 q ( k = 1 , 2 ，k ) ，设墩为第t 辆车所配送的顾客点数( 若墩= o 表示未使用该车) ， 此车所走的路径用集合r k 表示( 彤也可称为第k 条路径) ，其中的元素1 k i 表示顾客点 在路径k 中的顺序为i ( 不包含配送中心) 。令r o = ，( t 】= v 0 表示配送中心，我们建 1 西安建筑科技大学硕士学位论文 立如下模型： ( d ，t 。i 州，i 一) s i g ”( 一1 ) g ，。q ，k = l ，2 ，k 0 巩n ，k = 1 , 2 ，k 仇= ” r t ： 。i r t ，e l ，2 , - - - , n , i ：l ，2 ，n 。) r 。n r ：= 中，v 墨k 2 ，、1 1 1 5 劬( 旷1 ) 2 o妻它 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) 模型中，( 1 ) 为目标函数，不等式( 2 ) 保证每条路径上各个顾客点的总需求量 不超过此路径的配送车辆载重量，不等式( 3 ) 表明每条路径上的顾客点数不超过总顾 客点数，等式( 4 ) 要求每个顾客点都得到配送服务，等式( 5 ) 表示每条路径的顾客 点的组成及排列次序，等式( 6 ) 限制每个顾客点的需求仅能由一个车辆来完成。 1 2 2v r p 的扩展问题 v r p 扩展问题是经典v r p 加入各种约束条件后而形成的。如加入需求约束形成的 需求随机的车辆路径问题( s t o c h a s t i cv r p ，简记为s v r p ) ；加入对阔约束得到的带 时间窗的车辆路径问题( v r pw i t ht i m ew i n d o w s ，简记为v 瑚t w ) ：加入距离约束 的距离约束的车辆路径问题( v r pw i t h d i s t a n c e ，筒记为d v i 强) 。根据其它条件的不 同，还有多配送中心车辆路径问题( m u l t i p l ed e p o tv r p ，简记为m d v r p ) 、可切分 的车辆路径问题( s p l i t d e l i v e r y v r p ，简记为s d v r p ) 、先配送再收集车辆路径问题 ( v r pw i t hb a c k h a u l s ，简记为v r p b ) 、配送收集车辆路径问题( v r pw i t hp i c k u pa n d d e l i v e r i n g ，简记为v r p p d ) 、信息不完全的模糊车辆路径问题( f u z z yv r p ，简记为 f v r p ) 等。以下对几类v r p 作简单描述。 1 2 2 1v r p t w v r p t w 涵义： 给定了配送中心和若干顾客点，要求配送中心派出车辆对每个顾客点送货一次且 仅次，并尽可能( 或必须) 在规定的一定时间范围内到达顾客点( 当然有时配送中 心也有时间范围限制) ，否则将因停车等待或配送延迟而产生损失，目的是设计最小 成本的配送路线方案。其中时间范围即时间窗，此问题即为时间窗v r p 问题。比较丽 言，时间窗v r p 除了必须实现经典v r p 的要求，还要考虑访问时问的限制，这样才 d z 弧 r 珥 踟 其 d 安建筑科技大学硕上学位论文 能找剑合理方案。 根据时间约束的严格与否，v r p t w 分为两类：软时间窗的v r p 和硬时间窗的 v r p 。软时间窗v r p 要求尽可能在时间窗内到达访问，硬时间窗v r p 则要求必须在 时削窗内到达访问。 v r p t w 模型： 给定”个顾客点，嘞表示车辆从顾客点i 到顾客点，的行驶距离，白表示车辆从顾 客点强0 顾客点，所花费的时间。 d ，如为顾客点i 的时间窗，a ，为对顾客点i 服务最早 开始时间，b ，为服务最晚开始时间，s ，表示车辆到达顾客点i 的时刻，要求尽可能落在 时间范围 d ，蜘内，如果到达时间曲早于嘶，停车等待到a i 后开始服务( 如开始卸货) ， 当然要支付一定的停车费，如果s ，晚于b ，因延迟送货会给顾客造成损失，需接受一 定的惩罚值。配送中心的时间窗范围较大，基本可以不作约束。配送中心派出世辆车 配送。 目标函数： k + 月-月h m i n z = ( d ，+ t 伽川) ) + p z m f l x a 厂o ，0 + l y m a x s 厂b j ，o t 。ji 。j j ；uj = 0 目标函数由三部分组成，第一部分表示不考虑时间约束时的经典配送费用( 配送 总路程) ；第二部分表示若旅行商到达城市，的时间早于研，则在此停车等待，单位时 问停车费即所处的惩罚值为p ；第三部分表示若旅行商到达城市，的时刻晚于6 ，属于 推迟配送，推迟单位时间处以晚到罚金，。变量，的下限之所以从0 开始，是因为考虑 到配送中心的时间窗要求，假如配送中心无时间窗约束，则令其时间窗为【o 捌，其中m 为相当大的正数即可。 当e 和，都不是很大时，此时时间窗约束对目标函数值的影响在一定的可接受范围 内，此时的时间窗为软时间窗，当p 和，都相当大时，此时路径变为不可能，即软时间 窗变成了硬时间窗。 时间约束： s ，= s ，+ t 。+ m a x a , 一s j ，0 其中，为服务完i 后的下一个服务对象，如果车辆回到了配送中心后，记时可以 重新进行。 1 2 2 2m d v r p m d v r p 涵义： 所谓的多配送中心的车辆路径问题，就是顾客点的配送工作不再仅由一个配送中 心发出的车辆完成配送，而是由分散的多个配送中心供给的一种形式。多配送中心的 西安建筑利技大学硕士学位论文 车辆路径问题有以f 特点： 顾客点分散； 配送中心分散： 一个顾客点可由任一配送中心一次供给满足； 配送中心可服务任意的顾客点群； 衡量配送方案优劣的标准是配送总代价的大小。 m d v r p 模型： 不妨假定”个顾客点的配送任务由聊个位置各异的配送中心配送完成。 目标函数： m i n z = t o t d i s ， j = 1 其中t o t d i s 。为配送中心i 派出车辆行驶的路径总长。 多配送中心约束： v ，= n j = i 其中，y ，表示配送中心f 服务的顾客点的集合。约束保证任何顾客点都得到了配 送服务。 无回路约束： y l n 矿2 = v 2 n v 3 = = v 。一】n v ，= y 。n v l = 西， 约束保证每个顾客点仅由一个配送中心完成配送。 1 2 2 _ 3s v r p 需求随机的车辆路径问题即在未到达顾客点之前，此顾客点的货物需求量的多少 是不知道的。例如某畅销年货的供货问题，在车辆未到达之前，存货随时都在减少， 很难确定准确的需求量。此类需求随机的车辆路径问题从某种意义上来说，也可以归 并为信息不完全的模糊车辆路径问题( f v r p ) 的一种形式。 1 2 2 4s d v r p s d v r p 为可切分的车辆路径问题，所谓的可切分，即顾客点货物配送不再限制只 由一辆车一次配送满足，而是可以将配送货物分成几份，由不同的车辆多次配给。此 类车辆路径问题增加了运输的灵活性，降低了车辆的空驶率。 1 2 2 5 配送和收集v r p 与经典车辆路径问题比较，车辆除了需要完成顾客点货物配给之外，还必须将各 顾客点的某些货物回运到配送中心。此类问题分成两种，一种是先配送再收集车辆路 6 西安建筑科技大学硕士学位论文 径问题( v r p b ) ，在所有的顾客点的配送任务完成之后，再进行货物回收，其实可以 将此问题概略的分解成为两个经典车辆路径问题的叠加。另一种是收集与配送穿插结 合的配送收集车辆路径问题( v r p p d ) 【”】，在配送途中同时收集货物，此类问题车辆 容量的约束变的比较复杂，需要同时考虑车内货物的加减问题。 此外，还有路径重复v r p 以及非遍历的v r p 等。 1 3v r p 问题的优化方法 1 3 1 算法综合回顾 针对各种车辆路径问题模型，曾出现多种求解方法，如系统仿真法、人机互动法 以及精确解法等。尽管几类方法都提供了解决问题的思想，但由于它们各自都有自己 的不足之处，在系统仿真法中，将实际的配送情形逻辑化为仿真程序的可行性是否可 以保证，人机互动法中人专业知识的完备性是否具有不良影响，精确解法的求解时间 是否允许都成了非常实际的问题。而这些问题也确实严重影响了它们的存在价值，并 被后来出现的效率较高的启发式算法逐渐取代。 启发式算法，不要求必须获得精确的最优解，而是以获得可以接受的较优解为目 标，既节省了求解时间，又满足了解决问题的实际要求。启发式算法以其现实、高效 的优点引起了优化研究领域的高度重视，并在近年来取得了飞速发展。 以下简要回顾一下几种著名的启发式算法，遗传算法【5 【3 6 1 、禁忌搜索算法 l 】【3 5 以及 蚁群算法i 4 【2 4 】【2 2 1 1 2 6 1 1 3 2 l 等。此外，免疫算法也逐渐引起了人们的重视【2 1 】1 3 0 l 。 1 3 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是由h o l l a n d 在1 9 7 5 年受生物进化的启发 而提出的。它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”间的 复制、交叉和变异操作，一代代不断进化最终收敛到“最适应环境”状态，即问题的 满意解或最优解。 g a 优点： 遗传算法把问题参数编码成“染色体”后进行优化操作，不是针对参数本身，使 得g a 不受参数约束条件的限制，如连续性、可导性等。g a 具有一定的并行搜索特征 及全局搜索能力。 g a 局限性： 实际应用中，g a 往往会出现早熟或者收敛性能差的具体问题。对于有约束优化问 题的求解，目前一般限于简单的约束条件，对于高维、多约束、多目标的优化问题使 7 西安建筑科技大学硕士学位论文 用g a 求解依然有待更深入的研究。 1 3 3 禁忌搜索 禁忌搜索算法( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 是局部邻域搜索算法的推，1 ， 是一种全局逐步寻优算法。g l o v e r 在1 9 8 6 年提出此概念，进而形成套完整的算法。 简单t s 算法的基本思想是：给定一个初始解和一种邻域，然后在当前解的邻域中 确定若干候选解，若最佳候选解对应的目标值优于当前最好解，则忽视其禁忌特性， 用其替代当前解，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若 不存在上述候选解，则在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与 当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此 重复这种迭代搜索过程，直至满足停止准则。 t s 优点： t s 采用了禁忌搜索技术，禁止重复前面的搜索工作。为了回避局部邻域搜索陷入 局部最优的主要不足，禁忌搜索算法使用禁忌表来记录已经到达过的局部最优点，在 下一次的搜索中，利用禁忌表中的信息不荐或者有选择的搜索这些点，以此来跳出局 部最优点。 t s 缺点： t s 对初始解具有较强的依赖性，质量较差的初始解会降低算法的收敛速度；t s 的搜索过程是串行的，仅仅是单一状态的移动，非并行搜索。 1 3 4 蚁群优化 蚁群优化算法( a n tc o l o n yo p t i m i z m i o n ，简称a c o ) 是近年来刚刚出现的一种元 启发算法，历史较短，但以其优越的搜索性能很快在组合优化问题的解决中占据了重 要的地位。 a c o 是受蚂蚁觅食行为的启发而出现的。模仿蚂蚁爬行追踪信息素的特点，问题 解决的代理者人工蚁按照人工信息素的浓淡概率的选择下一到达的可行点，在所有蚂 蚁完成一次爬行后，进行全局信息素的更新以反映蚂蚁搜索的效果。接着蚂蚁再次出 发继续按以上规律爬行搜索直至问题收敛或出现停止条件。a c o 在下一章节将有详细 论述。 蚁群优化算法相对缺点不太突出，优点如下： 算法原理简单，相比较而言不易过早收敛或陷入局部最优解，可以方便有效地利 用基于问题本身的启发式信息，搜索能力强。 鉴于蚁群优化的优越性，本文将利以此算法为核心手段解决前面提到的v r p t w p c r 本文将重点解决一+ 种较为复杂的车辆路径问题，即带有时间窗和在前约束双重限 制的v r p 问题。 时间窗，即服务顾客点的时问范围。它对城市或顾客点得到服务的具体时间作_ 限制，要求车辆( 或人员) 到达顾客点开始服务的时间必须落在容许的范围之内，否 则就会影响顾客对服务的满意程度。时间窗反映了顾客需要提供服务的紧迫性，实际 是服务需求者和服务供给者之间的制约关系。 在前约束，有人称为顺序约束，它对某些城市或顾客点得到服务的前后顺序作了 限制，要求车辆( 或人员) 在到达某个顾客点之前，必须先由该车完成对另外一些客 户的服务，否则服务方案不能得到认可。在前约束反映的是顾客得到服务的先决条件， 实际上是服务需求者之间的制约关系，更反映了服务供给者和需求者之间的矛盾。详 细论述见第四章。 我们称带有时间窗和在前约束双重限制的v r p 问题为有时间窗和在前约束车辆路 径问题( t h ev e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w sa n dp r e c e d e n c ec o n s t r a i n t s ，简 记为v r p t w p c ) 。 为了更好的说明v r p t w p c 问题，这里采用框图将此问题与我们相对熟悉的经典 问题如t s p 之间的相互关系理清( 见图1 1 ) 。图中，实线框内是几个经典路线安排问 题，线框之间的箭头及文字表示了问题之间的联系或转换条件，虚线框内即是本文要 研究解决的特殊问题。由图示关系可见，所研究的目标问题具有相对其它问题更复杂 的约束关系，问题的解决具有更大的复杂性。 】5 本文的组织结构 本文首先概述了车辆路径问题研究的实际意义、问题的分类及求解方法，提出本 文研究的重点问题唷时间窗和在前约束的车辆路径问题( v r p t w p c ) ；第二章系 统介绍了蚁群优化算法，并在随后的第三章将之应用于v r p t w 的求解：第四章在对 基本的蚁群算法进行多方面的改进后，完成v r p t w p c 的蚁群系统优化；第五章对 v r p t w p c 初始解优化问题的邻域搜索算法进行了深入分析与探讨。第六章总结全文。 9 西安建筑科技大学硕士学位论文 图1 1 本文研究的问题 1 0 凸安建筑科技大学硕士学位论文 2 1 算法综述 2 蚁群算法 刈于v r p 问题，求解算法大致可分为精确算法和人工智能算法两大类。总的来说， 精确性算法基于严格的数学手段，在可以求解的情况下，其解质量较好。但由于算法 严格，运算量较大，尤其是规模大的问题几乎无法求解。从而使该类算法只能有效求 解中小规模的确定性v r p 。在求解中小规模v r p 时，人工智能算法与精确算法相比， 在精度上不占优势。但v r p 规模变大时，人工智能方法基本能在可接受时间里，找到 可接受的满意解，这是精确算法难以做到的。由于v r p 的实际问题，各种约束错综复 杂，人工智能算法显示出了巨大的优越性，也正因为如此，实际应用中，人工智能算 法要更广泛，也更为研究者所关注【2 】。 求解车辆路径调度问题的精确算法有动态规划法、分技定界法等。由于精确算法 只能求解一些小规模问题，人们开始寻求所得结果并非尽善尽美的所谓启发式算法， 以求处理各种实际问题。7 0 年代和8 0 年代是启发式算法的全盛时期，但由于绝大多数 启发式方法都是按照某种确定性的搜索规则来进彳亍的，想要改进所得解的可能性几乎 是零。近年，一些来自其他学科的新代优化算法相继出现，如禁忌搜索算法( t a b u s e a r c h ，简称t s ) ，遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) ，人工神经网络算法( a r t i f i c i a l n e u r a ln e t w o r k s ，简称a n r q ) p a 及近几年问世的蚁群算法( a n t sc o l o n ya l g o r i t h m ，简称 a c 等。以下重点介绍蚁群算法。 比较明确的蚁群优化算法是在1 9 9 6 年由m a r c od o r i g o 等首先提出的【1 5 j ，后来很多 学者又作了许多研究，使蚁群算法得到了进一步的深化与完善。当然这里包含了很多 不同版本的蚁群算法，诸如蚂蚁算法( a n t a l g o r i t h m ，简记为a a ) 1 1 1 ，蚂蚁系统( a n t s y s t e m ，简记为a s ) 15 ，蚁群系统( a n tc o l o n ys y s t e m ，简记为a c s ) f 1 3 1 8 1 ，最大 最小蚁群系统( m a x + m i na n tc o l o n ys y s t e m 简记为，m a x m i na c s ) f 27 j 等。一般来说， 各种不同的蚁群优化算法之间或多或少都有一些不同之处，但它们的基本原理是共通 的。正因为如此，本文使用“蚁群算法”一词代表与蚁群优化相关的系列算法。 2 2 蚁群算法的基本原理 2 2 1 生态学原理 蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出的。 生物学研究表明一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径，而单 西安建筑科技大学硕士学位论文 只蚂蚁则不能。蚂蚁究竟如何合作觅食的呢? 生物学家经过大量细致观察研究发现， 蚂蚁个体之间的行为是相互作用相互影响的。蚂蚁在运动过程中，能够在它所经过的 路径上留下一种称之为信息素的物质，而此物质恰恰是蚂蚁个体之间信息传递交流的 载体。蚂蚁在运动时能够感知这种物质，并且习惯于追踪此物质爬行，当然爬行过程 中还会释放信息素。一条路上的信息素踪迹越浓，其它蚂蚁将以越高的概率跟随爬行 此路径，从而该路径上的信息素踪迹会被加强，因此，由大量蚂蚁组成的蚁群的集体 行为便表现出一种信息正反馈现象。某一路径上走过的蚂蚁越多，则后来者选择该路 径的可能性就越大。蚂蚁个体之间就是通过这种间接的通信机制实现协同搜索最短路 径的目标的。 我们举例简单说明蚂蚁觅食行为1 8 】【14 】： ch t ：u卜l ( a ) 【b ) tc ， 图2 1 蚂蚁觅食原理 如图2 1 ( a ) 所示，各点及各点之间的距离已知，设a 是巢穴，e 是食物源，h c 为一障碍物。由于障碍物存在，蚂蚁要想由a 到达e ，或者由e 返回a ，只能由h 或 c 绕过障碍物。设每个时间单位有3 0 只蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到达d 点， 蚂蚁过后留下的信息素浓度为1 。为方便，设信息素停留时间为1 。在初始时刻，由于 路径b h 、b c 、d h 、d c 上均无信息存在，位于b 和e 的蚂蚁可以随机选择路径。从 统计的角度可以认为它们以相同的概率选择b h 、b c 、d h 、d c ，如图2 1 ( b ) 所示。 由于路径b h d 长度是路径b c d 的2 倍，所以经过一个时间单位后，在路径b c d 上的 信息量是路径b h d 上信息量的2 倍。t = 1 时刻，将有2 0 只蚂蚁由b 和d 到达c ，有 l o 只蚂蚁由b 和d 到达h 。随着时间的推移，蚂蚁将会以越来越大的概率选择路径 b c d ，如图2 1 ( c ) 所示，直至最终完全选择路径b c d 。这样也就找到了由蚁巢到食 物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正反馈过程。 蚂蚁觅食协作本质可概括成如下三点： 路径概率选择机制：信息素踪迹越浓的路径，被选中的概率越大； 信息素更新机制：路径越短，路径上的信息素踪迹增长得越快； 协同工作机制：蚂蚁个体通过信息素进行信息交流。 】2 西安建筑科技大学硕士学位论文 从蚂蚁觅食的生态原理可见，单个个体的行为非常简单( 蚂蚁只知道跟踪信息素 爬行并释放信息素) ，但组合后的群体智能又非常高( 蚂蚁群能在复杂的地理分布的 情况下，轻松找到蚁穴与食物源之间的最短路径) 。这种特点恰恰与元启发 ( m e l a h e u r i s t i c ) 算法的特点相一致，蚁群优化算法正是受到这种生态学现象的启发后 加以模仿并改进而来，觅食的蚂蚁由人工蚁替代，蚂蚁释放的信息素变成了人l 一信息 索，蚂蚁爬行和信息素的蒸发不再是连续不断的，而是在离散的时空中进行。 2 2 2 深层优化机制 从深层意义上来讲，蚁群算法作为优化的方法之一，属于人工群集智能领域。人 工群集智能，大都受自然群集智能如昆虫群和动物群等的启发而来。除了具有独特的 强有力的合作搜索能力外，还可以利用一系列的计算代理对问题进行分布式处理，从 而大大提高搜索效率【1 6 】。 在蚁群优化算法中，作为分布智能体( d i s t r i b u t ea g e n t ) 的人工蚁( a r t i f i c i a ta n t s ) 的行 为可以作如下描述：一群人工蚁相互协作在问题的解空间中搜索好的解。这些人工蚁 按照人工信息素踪迹( a r t i f i c i a lp h e r o m o n et r a i l s ) 和基于问题的启发式信息的指引在问 题空间移动以构造问题的解。在此，相对自然界蚂蚁分泌的信息素( p h e r o m o n e ) ，人工 蚁群设置了一种长期记忆，但这种记忆不是局部地存在于单个的人工蚁，而是全局地 分布在整个问题空间。当人工蚁在问题空间中移动时，他们在其经过的路径上留下信 息素踪迹，当然，留下信息素的多少与此次爬行( 构造解的过程) 所构造的解的质量 密切相关。这些踪迹反映了人工蚁在问题空间觅食( 即构造问题的解) 过程中的经历。各 个搜寻问题解的人工蚁恰恰是利用这些低水平的信息索的简单交流，从而一步步向问 题的最优解靠拢。换句话说，信息素在蚁群的协作和通讯中超到一种间接媒介的作用， 研究社会型生物种群的学者称这种媒介为协同机制s t i g m e r g y e 8 l f l l 】。人工蚁群在解空问 中一步一步地移动从而构造问题的解，同时，他们根据解的质量在其路径上留下相应 浓度的信息素，蚁群中的其他蚂蚁倾向于沿着信息素浓的路径前进，同样这些蚂蚁也 将在这段路径上留下自己的信息素，这就形成了一种自催化强化学习机制，也就是正 反馈。这种正反馈机制将指引蚁群找到高质量的问题解，在此意义上，蚁群算法是一 种基于蒙特卡洛方法的强化学习算法。 除人工蚁的觅食行为外，蚁群优化算法还包括另外两个机制：信息素挥发和后台 行为“。信息素挥发也可以称为遗忘，遗忘是一种高级的智能行为，作为遗忘的一种 形式，路径上的信息素随着时间不断挥发将驱使人工蚁探索解空间中新的领域从而避 免求解过程过早的收敛于局部最优解。后台行为包括邻域( 局部) 搜索过程以及问题全局 信息的收集。蚁群优化是一种基于种群的构造型自然启发式优化方法，这种构造性另 13 西安建筑科技大学硕士学位论文 法如果与改进型迭代方法相结合，例如邻域搜索，其效果将更好。此外，通过在解构 造过程中动态的收集基于问题本身的这种启发式全局信息，将引导蚁群在高质量豹问 题空间中搜索。 2 3蚁群算法框架 白蚁群算法提出以来，出现了多种不同的具体搜索方法。如a n ts y s t e m h 】， a s r a n k 3 1 ，m a x m i na n ts y s t e m 2 ”，a n tc o l o n ys y s t e m 1 3 】等等。 尽管具体实现过程略有差异，但就一般而言，蚁群算法都遵循如下的统一框架【3 l 】： p r o c e d u r e 组合优化问题的蚁群算法 设置参数，初始化信息素踪迹； w h i l e ( 不满足结束条件时o ： f o r 蚁群中的每个蚂蚁： f o r 每个解构造步骤，( 直到构造出完整解) ： 蚂蚁按信息素及启发式信息的指引构造一步问题的解； 进行信息素局部更新；( 可选) ； e n d e n d 以某些已获得的解为起点进行邻域( 局部) 搜索； ( 可选) 跟据某些已获得的解的质量进行全局信息素更新； e n d e n d 2 4 蚁群算法应用实例 由于旅行商问题( 简称为t s p ) 是计算复杂性理论、运筹学、最优化理论等领域 中的一个经典