（计算机应用技术专业论文）基于改进蚁群算法的有时间窗约束的车辆路径问题研究.pdf

摘要 有时间窗约束的车辆路径问题( v r p t w ) 是近几十年来运筹学、应 用数学、网络分析、图论、计算机应用及交通运输等学科研究的一个热 点问题。v r p t w i h - 题作为一个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 ) 多项式复 杂程度的非确定性问题) 难题，随着客户数量的增加，可选的配送路径 方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成 为人们研究的一个重要方向。 蚁群算法是一种新兴的启发式算法。它具有正反馈、并行计算、较 强的鲁棒性等诸多特点，在很多领域有着广泛的应用。然而，一般蚁群 算法在求解组合优化问题过程中容易出现过早收敛或停滞现象。为了解 决这些问题，本文针对v r p t w 问题给出了一种新的改进算法，通过对改 进蚁群算法的分析。利用面向对象的思想实现该算法，采用一系列 b e n c h m a r kp r o b l e m s 对算法进行测试，实验结果表明改进蚁群算法在 求解v r p t w 上是有效的。 本文研究成果对建立现代物流运输车辆优化调度系统有现实的理 论指导意义和应用价值，对蚁群算法的研究有一定的参考价值。 关键字：蚁群算法启发式算法时间窗车辆路径问题 a b s t r a c t v 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 s ( v i 心t w ) w a sa n i m p o r t a n tp r o b l e mi nr e c e n ty e a r si nt h ef i e l d so fo p e r a t i o n a lr e s e a r c h a p p l i c a t i o nm a t h e m a t i c s ，n e t w o r ka n a l y s i s ，g r a p ht h e o r y , c o m p u t e r a p p l i c a t i o n s ，t r a f f i ct r a n s p o r t a t i o ne t c a san p h a r dp r o b l e m 。v r p t w w i l li n c r e a s e e x p o n e n t i a l l ya l o n gw i t ht h ea d d i n go fc u s t o m e r s s oi t b e c o m e sa ni m p o r t a n ts t u d y i n gt r e n dt os o l v et h ev e h i c l es c h e d u l i n g p r o b l e mw i t hh e u r i s t i ca l g o r i t h m a n tc o l o n yo p t i m i z a t i o n ( a c 0 1a l g o r i t h mi san e wh e u r i s t i ca l g o r i t h m t ot h ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m 0 、树n gt oi t sp o s i t i v ef e e d b a c k a n de f f e c t i v ep a r a l l e l i z a t i o na n ds t r o n gl u s t i n e s s a c oh a sb e e na p p l i e di n m a n yf i e l d s h o w e v e r , t 1 1 et r a d i t i o n a la l g o r i t h m sh a v et h ep r o b l e m so f e a r l yc o n v e r g e n c e o r s t a g n a t i o n i nt h e p r o c e s so fc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s t os o l v et h e s ep r o b l e m s ，t h i sp a p e rp r o p o s e san e w i m p r o v e da n tc o l o n ya l g o r i t h mo fs o l v i n gt h ev r p t wp r o b l e m t h r o u g h t h ea n a l y s i so ft h ep r i n c i p l eo fa c s ，t h ei m p r o v e da c sw a sr e a l i z e db y o b i e c t o r i e n t e dt h o u g h t ，n l et e s tr e s u l to f as e r i e so fb e n c h m a r kp r o b l e m s i n d i c a t e dt h a tt h ei m p r o v e da c sw a se m c i e n ti ns o l v i n gv r p t w t h ec o n c l u s i o no ft h i st h e s i sh a ss i g n i f i c a n c eo fr e a l i s t i ct h e o r ya n d a p p l i c a t i o nv a l u et ot h ee s t a b l i s h m e n to fl o g i s t i c sd i s t r i b u t i o na n dv e h i c l e r o u t i n gp r o b l e m ，a n di ti sv a l u a b l ef o rt h es t u d yo fa n tc o l o n ya l g o r i t h m k e yw o r d s ：a c s h e u r i s t i ca l g o r i t h mt i m ew i n d o w sv e h i c l e r o u t i n gp r o b l e m 长春理工大学硕士( 或博士) 学位论文原创性声明 本人郑重声明：所呈交的硕士( 或博士) 学位论文，基于改 进蚁群算法的有时间窗约束的车辆路径问题研究是本人在指导 教师的指导下，独立进行研究工作所取得的成果。除文中已经注 明引用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果 由本人承担。 作者签名： 垒1 垒垂兰孝立月缉日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、 博士学位论文版权使用规定”，同意长春理工大学保留并向国家有 关部门或机构送交学位论文的复印件和电子版，允许论文被查阅 和借阅。本人授权长春理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复 制手段保存和汇编学位论文。 作者签名：主垒垄! k 三月望日 导师签名： 鞠咀月字 第一章绪论 1 1 研究背景及意义 物流( l o g i s t i c s ) “1 指在合适时间，将合适的物品以适当的数量准确 地送到顾客手中，它是供应链中最重要的组成部分。物流广泛存在于日 常生活、企业经营等活动中，它是社会化大生产和社会分工深化的产物， 它连接生产与消费，使货畅其流，物尽其用，促进生产不断发展，满足 日益增长的社会消费需要。在现代社会中，物流与商流、信息流并称为 经济的三大支柱，系统化、合理化的物流管理将创造巨大的经济利润， 因此物流被认为是继劳动力、资源之后的“第三利润源”。 当前，现代物流己被公认为是企业在降低物质消耗、提高劳动生产 率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高 产品市场竞争力的重要途径。据专家测算，现代物流成本约占企业经营 成本的3 0 5 0 ，当一个有效的物流系统与企业主要商业系统集成之后， 可使仓储量降低5 0 ，准时交货率提高4 0 ，营业收入增加1 0 以上。 在经济发达国家和一些经济水平较高的发展中国家，现代物流水平己成 为影响企业竞争力的关键因素。 与发达国家相比，我国的物流产业效率较低。根据全国第三产业普 查资料，我国交通运输、仓储、代理和批发等行业的成本费用之和占国 民生产总值的比重为1 5 左右，如果考虑其它相关流通环节的费用和流 通过程中的物流损失，则全社会物流费用支出约占园民生产总值的2 0 以上。而美国的全社会物流费用支出仅占其国民生产总值的1 0 左右。 在物流系统中，物流配送是一个重要环节，它是指按客户( 包括零售商 店、用户等) 的订货要求( 包括在货物种类、数量和时间等方面的要求) ， 在物流中心( 也称物流基地、物流据点，包括配送中心、仓库、车站、 港口等) 进行分货、配货工作，并将配好的货物及时送交收货人的物流 活动。物流配送过程主要包括以下作业环节：从生产工厂进货或运达并 集结的集货作业；根据各个客户的不同需求，在物流中心将所需要的货 物挑选出来的分货和配货作业；考虑配送货物的重量和体积，充分利用 车辆的载重和容积的货物配装作业；合理确定车辆配送路线并及时送货 的作业。可见，物流配送是一种集集货、分货、配货、配装、送货等多 种功能为一体的物资流通方式。 在物流配送业务中，配送车辆调度问题的涉及面较广，需要考虑的 因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的 影响也较大。随着市场经济条件下对配送服务水平要求的提高，时间因 素在配送过程中越发显得重要。鉴于此，本文将着重研究带时间约束的 物流配送车辆路径问题即v r p t w 问题。 有时间窗的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w $ ，u t w ) 是在车辆路径问题的基础上增加了客户要求访问的 时间窗口。由于现实生活中许多问题都可以归结为v r p t w 来处理( 如邮 政投递、电力及工业管理等) ，处理的好坏也直接影响到一个企业的效 益和顾客的利益，所以对v r p t w 的研究越来越受到人们的重视。 v r p t w 现已被证明为n p - h a r d t j ( 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 p r o b l e m ) 闯题，当问题规模较大时，将很难得到问题的精确解，探讨如 何经过少量的计算，得到一个相对满意的解，已成为现阶段学者研究的 重点。在这种背景下，启发式算法成为研究并解决该问题最有效的一种 途径。遗传算法和禁忌搜索算法以及模拟退火算法等都较好的解决了该 问题。但是通过分析我们不难发现：遗传算法存在着早熟和收敛慢；禁 忌搜索全局性差 模拟退火搜索速度慢等。因此寻求性能更优的启发式 算法，对于解决v r p t w 具有十分重要的意义。 蚁群算法“】【5 ，是一种新型的模拟进化算法，它是从对蚁群觅食行为 的研究中产生的。具有正反馈、分布式计算以及贪婪的启发式搜索等主 要特点，正反馈过程使得该算法能够发现较好解；分布式计算使得该算 法易于并行实现，更快得到较好解：与启发式算法相结合，使得该算法 易于发现较好解，这些特点为更好解决复杂的组合优化问题提供了可 能。实验表明，在求解v r p 时，和其他算法相比，蚁群算法更具优势。 不少学者己采用蚁群算法对v r p 进行了深入的研究，但是这些算法仍 然存在着容易陷入局部优化、搜索速度较慢等问题。因此本文针对有时 间约束的v r p 问题对蚁群算法进行改进。提高了算法的性能和收敛速 度。本文的成果可以降低物流成本、提高服务质量，对研究车辆调度具 有重要意义。同时本文的研究成果对蚁群算法在应用领域研究也有着重 要的意义，对蚁群算法在我国的推广普及也有着重要的意义。 1 2 国内外研究现状 国外将物流配送车辆调度问题归结为v r p ( v e h i c l er o u t i n g p r o b l e m ，即车辆路径问题) 、v s p ( v e h i c l es c h e d u l i n gp r o b l e m ，即车辆 调度问题) 和m t s p ( m u l t i p l e t r a v e l i n g s a l e s m a n p r o b l e m ，即多路旅行商 问题) 。一般认为，不考虑时间要求，仅根据空间位置安排线路时称为 2 车辆线路安排问题冲：考虑时间要求的称为车辆调度问题或者称为有 时间窗约束的车辆路径问题( v r p t w ) 。该问题于1 9 5 9 年由d a n t z i g 和 r a m s e r 提出m ，从此很快引起运筹学，应用数学、组合数学、图论与网 络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理 者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。在 现实生产和生活中，邮政投递问题、车船调度问题、电力调度问题、管 道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调 度问题”1 。可见，研究配送车辆调度问题具有重要的理论和现实意义。 国外v r p t w 研究己经广泛应用于生产、生活的各个方面，如报纸、 牛奶的投递及线路的优化、电话预订货物的车辆载货和线路设计、垃圾 车的线路优化及垃圾站选址优化、连锁商店的送货及线路优化等。目前， 研究水平己有很大发展，其理论成果除在汽车运输，在水运、航空、通 讯、电力、工业管理等领域也有一定的应用，还用于航空乘务员轮班安 排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安 排、生产系统中的计划与控制等多种组合优化问题“。 国内，随着物流业的兴起。对货物运输车辆调度提出了经济性、准 确性、灵活性的综合要求，因此，这方面的研究工作正在较大范围内展 开，在车辆调度的形式、分析、模型以及求解方法上进行研究，对建立 现代物流运输车辆优化调度系统有现实的理论指导意义和应用价值。 目前国内外用于解决该问题的方法主要集中体现在精确算法( 如分 枝定界法) 和启发式算法( 如蚁群算法、禁忌搜索算法、遗传算法等) 。 精确算法指可求出其最优解的算法，精确算法主要有： 分支定界法o 】、割平面法“”、网络流算法1 、动态规划法“”。 但是精确算法的计算量随着车辆优化问题规模的增大呈指数增长， 如当停车卸货点的数目超过2 0 个时，采用一般的精确算法求解最短运 输路径的时间在几个小时以上。因此，精确算法不适合于求解大规模的 车辆路径问题。 而目前的启发式算法中遗传算法n ”存在着早熟和收敛慢；禁忌搜索 算法“”需要的运行时间较长、效率较低；模拟退火算法田1 则搜索速度慢 等。因此寻求性能更优的启发式算法，对于解决v r p t w 具有十分重要 的意义。蚁群算法作为一种新兴的模拟进化算法，具有正反馈、分布式 计算以及贪婪的启发式搜索等主要特点，正反馈过程使得该算法能够发 现较好解；分布式计算使得该算法易于并行实现，更快得到较好解；与 启发式算法相结合，使得该算法易于发现较好解，这些特点为更好解决 复杂的组合优化问题提供了可能。实验表明，在求解v r p t w 时，和其 他算法相比，蚁群算法更具优势。然而目前蚁群算法在求解v r p t w 时 仍然存在着容易陷入局部优化、搜索速度较慢等问题，为克服上述缺陷， 本文提出采用改进的蚁群算法来求解v r f l w 。 1 3 蚁群算法研究现状 蚁群算法作为一种新型的模拟进化算法，是由意大利学者m d 喇g o 在2 0 世纪9 0 年代初首先提出的，并称之为蚁群系统( a n ts y s t e m , a s ) 。与其它优化算法相比，蚁群算法具有正反馈、分布式计算以及贪 婪的启发式搜索等主要特点，正反馈过程使得该算法能够发现较好解； 分布式计算使得该算法易于并行实现，更快得到较好解；与启发式算法 相结合，使得该算法易于发现较好解，这些特点为更好解决复杂的组合 优化问题提供了可能。由于在a s 中所有个体都要进行信息素更新，造 成了信息素分配的浪费和分配畸形，所以a s 的性能并不很理想。 m d o r i g o 等人又提出了a s 的改进算法蚁群系统( a n tc o l o n ys y s t e m ， 简称a c s ) 嘲，在蚂蚁选择下一城市时使用的转移概率中加入伪随机分 配概率，以避免出现a s 中的信息素分配畸形。尽管a c s 与a s 相比提 高了算法的性能，但它仍然使用同a s 中的全局信息素更新原则和局部 信息素更新原则，即对所有个体进行信息素更新，造成了信息素的大量 冗余，弱化了好信息素的强度，为此，t h o m a ss m t z l e 等人提出了最大 最小蚂蚁系统( m a x m i na n ts y s t e m ，简称m m a s ) “”，在信息素更新 规则中每次更新只使用最好的一只蚂蚁的路径进行信息素更新，并且限 定信息素的最大和最小限度。在解决t s p , q a p 等问题的上述算法中， m m a s 被证明是最好的一种a c o 类算法。 目前所有蚁群算法的改进基本上都是建立在上述蚁群算法之上 的。，国内开始研究蚁群算法是从9 9 年开始，吴庆洪等人“”首先提出 了具有变异特征的蚁群算法，这种方法克服了原有蚁群算法中选择次最 短距离的概率很小的缺点，增加了解的全局性。随后又出现了其它引入 启发式因子或策略的改进蚁群算法，如信息素更新分段化“”、引入扰动 因子“”、引入杂交策略“”、自适应进化算予、增强型信息素更新规则 m 1 等改进算法，这些启发式因子或策略的引入对于蚁群算法的改进途径 主要有三个：改进选择概率，增加选择概率的自适应性，使选择概率能 够以一定概率选择次好解；改进信息素更新原则，增加信息素的自适应 性，使信息素的分配合理，即不出现信息素分配畸形，又避免信息素分 配的大量冗余；使用其它启发式策略对蚁群算法得出的解进行进一步搜 索，实际上是多种邻域搜索结构的结合，增加了解的多样性啪】【删o ”。通 过这些改进算法，一些比较复杂的大规模组合优化问题得到了很好的解 决。自1 9 9 8 年，第一属蚂蚁优化国际研讨会召开以来，已经是第三届 4 了，大大推动了蚁群算法的发展。蚁群算法已经引起越来越多的关注， 尽管还缺乏完善的理论分析，对它的有效性也没有给出严格的数学解释， 但回顾模糊控制的发展历史，理论的不完善并不妨碍应用，有时应用是 超前于理论的，并推动理论的研究，伴随着研究的不断深入， c o 算法 必将迎来一个光明的前景 1 5 本文主要研究工作 本文对蚁群算法进行了系统的研究，针对算法在计算过程中存在的 缺点对其进行有效的改进，提高算法的性能，并将改进算法引入物流运 输领域，针对物流运输中有时间窗约束的车辆路径问题的复杂性和不确 定性等特点，设计新的算法，合理选择运输路径，加快运输速度、降低 运输成本及增加经济效益。 本文主要研究工作包括： ( 1 ) 蚁群算法研究，从算法的基本思想入手，研究算法原理、特征 及性能，并对算法在计算过程中容易出现过早收敛、停滞等缺点，对现 有的改进方法进行了分析。 ( 2 ) 在系统分析了车辆调度问题的基本理论后，针对有时间窗约束 的v r p 问题建立相关数学模型 ( 3 ) 针对v r p t w 问题，提出改进蚁群算法。通过对初始解算法、概 率转移公式进行改进、及信息素更新机制的优化并结合交换法进行路径 改迸来提高算法效率，改进算法收敛速度。 ( 4 ) 对本文设计的改进算法通过j a v a 语言编程实现，采用国际标准 b e n c h m a r k p r o b l e m s 来测试算法的优劣，并与其他算法进行了详细的比 较，证明本算法具有一定的竞争力。 ( 5 ) 本文对算法中参数进行了比较详细的分析，为以后的理论研究 工作提供了参考。 ， 第二章蚁群算法及车辆路径问题基本理论 蚁群算法是受自然界中真实蚁群觅食行为的启发而提出的一种模 拟进化算法，由意大利学者m d o r i g o 提出，其具有正反馈、并行性等 特点。尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可 广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领 域。车辆调度问题，由于其在现实生活中的实用性，一直为众多的研究 者所关注。从早期的精确算法，到9 0 年代的各种启发式( h c u r i s t i e s ) 算法，都对车辆调度问题进行了教详细的研究。由于车辆调度问题己被 证明是一个n p h a r d 问题，因而寻找其实际而有效的算法显得颇为重 要。下面就有关蚁群算法和车辆调度的基本理论及其研究算法做一个大 致的介绍。 2 1 蚁群算法基本原理 蚁群算法是由意大利科学家m d o r i g o 等人在2 0 世纪9 0 年代初提 出来的“】。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经 网络算法等启发式搜索算法后的又一种应用于组合优化问题的启发式 搜索算法。m d o r i g o 等人在观察蚂蚁觅食习性时发现，蚂蚁总能找到 巢穴与食物之间的最短路径。这个现象引起了他们极大的兴趣。于是蚂 蚁被捉到实验室，蚂蚁的群体智能开始为人们所重视。m d o r i g o 等人 在实验室中做了一系列实验，在蚂蚁己形成的最短路径上设置障碍，而 当蚂蚁在发现原来路径有障碍物后，它们会绕开这个障碍物四散的走 开，但是经过一段时间之后，m d o r i g o 等人又不断的在蚁群经过的新 路径上设置障碍，而惊奇的发现蚂蚁们总能根据障碍物的位置，分散开 来然后又重新聚集到当时条件下的从巢穴到食物源的最短路径。经研究 发现，蚂蚁的群体协作是通过一种叫做外激素( p h e r o m o n e ) 的化学物质 进行通信和协调的。虽然蚂蚁具有一定的视力，但是它们却将外激素作 为中介的化学通信作为基本信息交流方式之一。外激素在蚂蚁们的生活 工作习性中起着至关重要的作用。m d o r i g o 等人受蚂蚁觅食行为 ( f o r a g i n gb e h a v i o r ) 中基于外激素的间接通信机制的启发，提出并设计 了一种蚁群算法( a n ta l g o r i t h m ) ，该算法被先后应用于t s p 问题、资 源二次分配问题( q u a d r a t i c a s s i g n m e n t p r o b l e m ) 等经典优化问题，得到 了很好的结果。上个世纪9 0 年代后期，这种算法逐渐引起了很多研究 6 者的注意，他们对算法做了各种改进并应用到其他领域，取得了一些令 人鼓舞的成果。为了给算法提供一个重译的描述框架，m d o r i g o 等研 究者提出了名为蚁群优化( a n t c o l o n y o p t i m i z a t i o n a c o ) 的算法框架， 所有符合蚁群优化描述框架的蚂蚁算法都可称之为蚁群优化算法( a c o a l g o r i t h m ) ，或简称为蚁群算法。研究表明，蚁群优化算法在解决离散 组合优化问题方面有着良好的性能，并在多方面得到了应用”1 。 除了能找到巢穴和食物源之间的最短路径之外，蚁群对环境有着极 强的适应能力。例如当原有的最短路径由于一个新的障碍物的出现而变 得不可行时，蚁群能找到一条新的最短路径。如图2 1 所示。图2 1 ( a ) 显示蚂蚁在从巢穴到食物源的一条直线上移动。我们已经知道蚂蚁用于 交流的方式是在它所经过的路径上留下外激素。蚂蚁在行进过程中倾向 于朝向外激素较多的方向移动。蚂蚁的这种行为可以用来解释它们为什 么能在新的障碍物出现的情形下重新找到最短路径。如图2 1 ( b ) 所示， 当新的障碍物出现时，那些位于障碍物附近的蚂蚁不能再沿原有的留有 外激素的路径前进，所以它们必须选择左行或右行。这种情形下，我们 可以认为有一半的蚂蚁选择左行，而另外一半选择右行。而障碍物另外 一侧也是同样一种情形。从图2 1 ( c ) 中我们可以发现一个有趣的现象， 那些选择较短路径的蚂蚁会比那些选择另外一条路径的蚂蚁更快地创 建起被障碍物隔断的外激素路径。从而，较短的路径会在相同的时间内 得到更多的外激素，这又引起更多的蚂蚁选择这条路径。由于这个正向 回馈的过程，很快地，所有的蚂蚁都会选择这条较短路径，如图2 1 ( d ) 所示。 一一 c )( d ) 图2 1 蚂蚁觅食图 ( a ) 蚁群在巢穴和食物源之间的一条直线上行进。 ( b ) 路径上出现新的障碍物，蚁群以相同的概率选择左行或右行。 7 翌 蕾静 龋 学 蛾_ 掣 ( c ) 较短路径的蚂蚁较快的重建起被障碍物隔断的外激素路径。 ( d ) 所有的蚂蚁都选择较短路径。 2 2 基本蚁群算法模型 2 2 1 蚁群算法模型 蚁群算法首先成功应用于旅行商问题( i t s p ) 上，为了便于理解。下 面以t s p 问题为例详细介绍蚁群算法模型和具体的实现步骤。 t s p 问题o ”( 旅行商问题) 的描述：给定n 个城市的集合 0 ，i ， n - 1 及城市之间环游的花费( 0 s i 茎n - i ，0 ，n - i ，i ，) 。t s p 问题是指：找到一条经过每个城市一次且回到起点的最小花费的环游。 若将每个顶点看成是图上的节点，花费气为连接顶点v j 、1 ，边上的权， 则t s p 问题就是在一个具有n 个节点的完全图上找到一条花费最小的 h a m i l t o n 回路。 为模拟实际蚁群行为，首先引入如下符号： 1 1 1 ：蚁群中蚂蚁数量： 鱼( f ) ：t 时刻位于城市i 的蚂蚁的个数； 巩：两城市i 、j 之间的距离； 勺o ) ；t 时刻边( i j ) 上的信息素轨迹浓度： 嘞：边( i j ) 的能见度，反映由城市i 转移到城市j 的启发程度，这 个量在蚁群系统运行中不改变； 吒：蚂蚁k 在边( i j ) 上留下的单位长度轨迹信息素量： p ：蚂蚁k 的转移概率，j 是未访问的城市。 蚁群算法的基本描述：给定n 个城市的t s p 问题，蚂蚁数量为m ， 这些蚂蚁具有记忆功能，并具有以下特征： ( 1 ) 蚂蚁从城市i 到城市j 的运动过程中，在边( i j ) 上释放一定的信 息素，蚂蚁根据根据信息素浓度和启发式信息，用相应的转移概率选择 8 下一个城市。 ( 2 ) 将已经走过的城市放入禁忌表中，禁忌表里的城市将不再被选 择为下一个城市。 ( 3 ) 完成一次循环后，根据整个路径的长度来释放相应的信息素， 并更新走过的路径上的信息素。 初始时刻，各条路径上的信息素量相等，设l ( 0 ) = c ( c 为常数) 。 蚂蚁在运动过程中根据各条路径上的信息素量决定转移方向。蚂蚁系统 所使用的转移概率为伪随机比例规则，在t 时刻，蚂蚁k 在城市i 选择 城市j 的概率p ：( f ) 为； p t ( f ) = 矿j a l l o w e d k o t h e r w i s e ( 2 1 ) 其中j f ( ，) 为f 时刻连接城市，和，的路径上信息的浓度。a l l o w e d 。表 示蚂蚁k 尚未访问过的节点的集合，每次循环将已经访问过的节点从表 中删除，参数口表示残留信息的相对重要程度，口表示可见度的相对重 要程度。为了避免对同一个城市的重复访问，每一只蚂蚁都保存一个列 表t a b u ( k ) ，用于记录到目前为止蚂蚁已经访问过的城市集合。t a b u ( k ) 随着蚂蚁寻优过程作动态调整。 为避免残留信息素过多引起残留信息淹没启发信息的现象发生，在 每一只蚂蚁走完一步或者完成对所有盯个城市的访问后( 也即一个循环 结束后) ，对残留信息进行更新处理。这种更新模仿人类记忆的特点： 新信息素不断存入大脑的同时，存贮在大脑中的旧的信息素随着时间的 推移逐渐淡化，甚至忘记。这样得到t 十n 时刻在( f 力路径上的信息素浓 度： 吒( i + n ) 2 ( 1 一力气( t ) h - ( t ) n l a r u ( o = a r k u ( t ) k - i ( 2 2 ) ( 2 3 ) 其中p 表示信息素的保留率，1 - p 表示信息素的挥发因子，为了 9 r 一吼 坠卜吖一 券 防止信息的无限累积，p 取值范围限定在( 0 ，1 ) 之间。“( t ) 表示蚂蚁 k 在时间段t 到( h 1 1 ) 的过程中，在f 到_ ，的路径上留下的残留信息浓度。 根据信息素更新策略的不同m d o r i g o 曾提出三种不同的蚁群算法 模型t 2 5 j ，分别称之为a n tc y c l es y s t e m 、a n tq u a n t i t ys y s t e m 、a n td e n s i t y s y 娠釉【2 叼其差别在于表达式的不同。 在a n t c y c l es y s t e m 模型中： 衫：援，瓤只蚂蚁在本次循环中经过( i ，j ) 【0 ， e s e ( 2 4 ) 其中q 是常数表示信息素强度，在一定程度上影响算法的收敛速度；q 表示第k 只蚂蚁在本次循环中所走过路径的总长度。 在a n tq u a n t i t ys y s t e m 和a n td e n s i t ys y s t e m 中分别表示为： 耐；愕第职蚂蚁经过i j 【0 ， e s e ( 2 5 ) = 粼蚂蚁e s e 经过巧 ( 2 6 ) 这三种模型的区别在于信息素更新方式的不同：后两种模型利用 的是局部信息，蚂蚁在完成一步( 从一个城市到达另外一个城市) ，更 新所有路径上的信息素而第一种模型利用的是整体信息，蚂蚁在一个循 环( 对所有n 个城市的访问) 以后，更新所有路径上的信息素。因此在求 解t s p 问题时，a n tc y c l e 模型性能比前面两种模型好。 2 2 2 蚁群算法流程 下面以t s p 为例说明具体实现步骤如下： ( 1 ) 参数初始化，令时间t = 0 和循环次数m = o ，设置最大循环次数c 一， 将1 1 1 个蚂蚁置于n 个城市上，令有向图上每条边( 幻) 的初始信息量 1 0 毛( f ) = c o n s t ，其中c o n s t 为常数，且初始时刻( 0 ) = 0 。 ( 2 ) 循环次数札卜虬+ l 。 ( 3 ) 蚂蚁的禁忌表索引号k = l 。 ( 4 ) 蚂蚁数目k 卜k + l 。 ( 5 ) 蚂蚁个体根据状态转移概率公式( 2 1 ) 计算的概率选择下一城市j 并 前进，_ ，e c - t a b u k 。 ( 6 ) 修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市并把该城市 移动到蚂蚁个体的禁忌表中。 ( 7 ) 若集合c 中城市未遍历完，即k m ，则跳转到第( 4 ) 步否则到第( 8 ) 步。 ( 8 ) 根据公式( 2 2 ) 、( 2 3 ) 更新每条路径上的信息量。 ( 9 ) 若满足结束条件，即如果循环次数札2 也一则循环结束并输出程序 计算结果，否则清空禁忌表并跳转到第( 2 ) 步重新循环。 算法流程图如下： 图2 2 基本蚁群算法流程图 2 2 3 蚁群算法的参数分析 对蚁群算法性能有影响的参数主要有：信息素残留系数p 、信息启 发式因子口、期望值启发式因子和总信息量q 蚂蚁总数m 等。 ( 1 ) 信息素残留系数p 的大小直接影响着蚁群算法的全局搜索能力和收 敛速度。p 取得过小，将影响算法的全局搜索能力，容易陷入局部最小 值；p 取得过大，将影响算法的收敛速度。对于a n t c y c l es y s t e m 模型， p 一般取0 5 - - 0 7 之间比较合适。 ( 2 ) 信息启发式因子口的大小反映了蚁群在路径选择中随机性因素的强 弱，口的取值越大，则蚂蚁选择以前走过的路径的可能性越大，导致搜 索的随机性减弱，容易陷入局部最优解；口的取值越小，虽然可以提高 随机搜索能力，但是算法的收敛速度会受到影响。一般口取值在l 巧 之间计算效果比较好。 ( 3 ) 期望值启发式因子的大小反映了蚁群在路径选择中确定性因素的 强弱，其值越小搜索结果越差；其值越大，蚂蚁在选择局部最短路径的 可能性越大，虽然收敛速度加大，但是同样容易陷入局部最优解而停滞。 ( 4 ) 总信息量q 为蚂蚁循环一周时释放在所经过的路径上的信息素总 量。总信息量q 越大，则在蚂蚁己经走过的路径上信息素的累积加快， 可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛，缺点是容 易陷入局部最优解而停滞，但信息总量q 对算法的性能影响有赖于上 述三个参数的配置。 ( 5 ) 蚂蚁总数越多就越可以提高蚁群算法的全局搜索能力以及算法的稳 定性；但是，蚂蚁数目增多后，会使大量的曾被搜索过的解( 路径) 上的 信息量的变化比较平均，信息正反馈的作用不明显，搜索的随机性尽管 得到了加强，但收敛速度减慢；反之，蚁群数量越少，特别是当要处理 的问题规模比较大时，会使那些从来未被搜索到的解( 路径) 上的信息量 减小到接近于o ，搜索的随机性减弱，虽然收敛速度加快，但会使算法 的全局性能降低，算法的稳定性差，容易出现过早停滞现象。实验证明 蚂蚁数日m 一般取也到n 2 之间，算法的各项性能相对平稳【2 7 i 。 2 3 蚁群算法优缺点及改进 蚁群算法是一种有效的随机搜索算法，具有如下优点田1 1 2 4 1 ： ( 1 ) 蚁群算法是一种分布式的本质并行算法。单个蚂蚁的搜索过程 是彼此独立的，容易陷入局部最优。但通过个体之间不断的信息交流和 传递有利于发现较好解。 ( 2 ) 蚁群算法是一种正反馈算法。路径上的信息素水平较高，将吸 引更多的蚂蚁沿这条路径运动，这又使得其信息素水平增加，这样就加 快了算法的进化过程。 ( 3 ) 蚁群算法具有较强的鲁棒性。只要对其模型稍加修改，便可以 应用于其它问题。 ( 4 ) 易于与其它方法结合。蚁群算法很容易与其它启发式算法相结 合，以改善算法的性能。 虽然蚁群算法有如上优点，但它毕竟是一种新兴的算法，还存在一 些缺陷，如收敛速度慢、计算时间长，这点可以从算法的复杂度看出； 易于过早的陷入局部最优，出现停滞现象，即搜索进行到一定程度后， 所有个体所发现的解完全一致，不利于对解空间的进一步搜索，以发现 更好的解；在求解连续优化问题上相对较弱等。 针对上述基本蚁群算法的缺点，许多学者提出了改进算法，主要是 围绕选择概率模型和信息素更新规则的设计两方面的改进。其中包括了 对于纯粹的蚁群算法的改进，也包括了引入其他优化算法对蚁群算法的 性能进行提高。现有改进的算法有很多；如d o r i g o 和g a m b a r d e l l a 在 1 9 9 6 年提出的蚁群系统【5 ( a n tc o l o n ys y s t e ma c s ) 、最值蚂蚁系统 1 5 ( m a x m i na n ts y s t e mm m a s ) ，带精英策略的蚂蚁系统【2 s l ( a n t s y s t e m w i t he l i t i s ts t r a t e g y ) 基于优化排序蚂蚁系统 2 9 ( r a n k b a s e d v e r s i o no f a n ts y s t e m 等等。在本文中，对算法的改进主要参照了蚁群 系统和最值蚂蚁系统，下面将简单地介绍这两种改进算法。 2 3 1 蚁群系统 蚁群系统在蚂蚁算法( a c s ) 的基础上引入了三个主要方面的引进： 选择策略，全局更新策略和局部更新策略。 ( 1 ) 选择策略 引入随机转移概率： j ：ja r g 。三5 【f ( ，甜) r 协( r ，) r 如果? s ( 2 7 ) 【 s 。s e s 为下一个要移动到的城市，q 是【0 ，l 】区间内均匀分布的随机数，是 一个参数( 0 q os 1 ) ，s 是个随机数由公式( 2 1 ) 确定。参数g o 的大小 决定了利用先验知识与探索新路径之间的相对重要性；每当一个位于城 市r 的蚂蚁选择下一个要到达的城市s 时它选取一个随机数0 q l 如 果qs9 0 则根据先验知识选择最好的边，否则按照原来公式进行选择。 ( 2 ) 蚁群系统全局信息素更新只应用在最好的蚂蚁路径上。全局更 新在所有蚂蚁都完成他们的路径之后执行，应用式( 2 8 ) 对所建立的路径 进行更新 f ( ，j ) * - - ( 1 - 力f ( ，s ) + p a r ( r ，s ) ( 2 8 ) 嘶力一心0 如瓢暑铲最好黼 1 日州。 其中：k 为到目前为止找到的全局最优路径。 ( 3 ) 蚁群系统局部信息素更新 在蚂蚁遍历所有城市过程中，蚂蚁每走完一个城市后对所走过的边进行 局部信息素更新，按下式进行更新： r ( r ，s ) + 一( i 一) f ( ，s ) + f o ( 2 9 ) 其中为一个参数，0 妒s l 。 由实验发现，设置= 可以产生非常好的结果，其中n 为城市 ， 数量，k 是由最近邻域启发算法产生的一个路径长度。可以看出，局 部信息素更新规则是减少己选择的边对于其他蚂蚁的吸引，从而增加蚂 蚁对还未访问城市的搜索。实验表明局部更新规则可以有效的避免蚂蚁 1 4 收敛于同一路径。 2 3 2 最大一最小蚁群系统 最值蚂蚁算法( m m a s ) 是基于蚁群算法的改进，它与基本的a s 算 法主要有以下三方面不同： ( 1 ) 与a s 相似，为了充分利用循环最优解和到目前为止找到的最 优解，在每次循环之后只对一只蚂蚁进行信息素更新。这只蚂蚁可能是 当前循环中最优解的蚂蚁也可能是试验开始以来最优解的蚂蚁。更新规 则如下： o + 1 ) = p 乃( f ) + f 胁瞄 ( 2 1 0 ) 其中缸锄2 形( s 细) ( 2 1 1 ) 厂( s 妇) 表示迭代最优解或者全局最优解的值。 ( 2 ) 为避免搜索停滞，在每个解的元素上的信息素浓度被限制在 【f 。，f 。】区间内，而在蚂蚁系统中信息素轨迹量不被限制，使得一些 路径上的轨迹量远高于其他边，从而蚂蚁都沿着同条路径移动，阻止了 进一步搜索更优解的行为，m m a s 则有效的降低算法出现停滞的可能性。 ( 3 ) 在蚂蚁的搜索过程中，算法的设计思想添加了局部搜索策略。 2 - o p t 搜索法、3 0 p t 搜索法和l k 局部搜索法被运用，其中l k 局部 搜索法使用的效果最好，在测试过程中，解得的效果比遗传算法中使用 此l k 局部搜索解法求解同样的问题要好。在m m a s 算法中2 - o p t 搜索法取得的效果次于l k 局部搜索法。 ( 4 ) 最值蚁群算法中路径上的初始信息素浓度不是一个常数，而 是被设定为路径上被允许释放的信息素浓度的最大值的估计值。这样可 以在算法运行的初期，就能够鼓励蚁群探索更多的路径，从而进一步提 高最终解的质量。试验证明最值蚂蚁算法由于采用了一系列的方法减少 搜索停滞情况的发生，比蚁群算法的结果好一些。 2 4 车辆调度问题基本理论 2 4 1 车辆调度问题一般描述 车辆调度是现代化物流系统的一个重要环节，它是指按用户的订货 要求，在物流中心进行集货、送货，并将货物及时送交收货人的活动。 如有一个中心货场，需向几个顾客运送货物，每个顾客对货物有一定的 需求，运送货物的车辆在货场装满货后发出，把货送到各顾客处，完成 任务后返回货场，如何满足用户需求的费用最小的车辆行驶路线，即送 货车辆优化调度。又如，若干厂家生产一些产品，需要运到中心仓库， 车辆从仓库出发，到各厂家去装货，装满后返回仓库，在满足厂家发货 要求的清况下，按什么路线行驶，可使总费用最少，即集货车辆优化调 度。 这两个问题实质是相同的，只有装货任务或卸货任务。在货物量较 少的情况下，用一辆车完成一项任务时，车辆不能满载，这样，车辆的 利用率很低，因此可考虑用一辆车完成多项任务。 在物流运输业务中，存在许多优化决策问题，本文只讨论物流运输 车辆优化调度问题。合理选择运输路径，对加快送货速度、提高服务质 量、降低经营成本及增加经济效益都有较大影响。现代物流中心所进行 的集货、送货作业，最大的特点就是多品种，小批量、多批次，所以多 为非满载运输问题。在日常生活和生产实际中，许多类似的问题都可以 归结为这类问题。 2 4 2 车辆调度问题图论基础 设g = - ( m _ ) 是一个连通的混合网络，v = v o ，h ， 是顶点集，a 是连接两两顶点的( 有向) 弧集，彳= ( v ，)h ，叶e v ，f ，) 。 先引入下面几个概念； 定义1 g = a ) ，是一个连通的混合网络，q ，a je 彳是连通的两条 边，则口i 到q 的距离为q 的箭头指向q 的箭尾顶点的距离记为 d ( q ，吩) 。 1 6 定义2 0 = m ) ，是一个连通的混合网络，s = “，a 2 ，口。) 是 是一组有向边的有序集合，则定义s 的长度为： ，钆。) + r a , f j + f a i 。记为t e n ( s ) 。 1 “一i 定义3 g = ( v a ) ，是一个连通的混合网络，( q ，啦，口。) 是一组有 向边的有序集合v 是矿的任意顶点，定义v 到d o ：q ，o - 2 ，口。) 的距离 为v 到q 箭尾的距离，记为：d ( v ：q ，a 2 ，口，) ，d ( 1 ，：q ，a 2 ，a 。) 到v 的距离记为：d ( q ，a 2 ，