（系统工程专业论文）蚂蚁算法在国民经济动员系统车辆路径问题中的研究与应用.pdf

华中科技大学硕士学位论文 摘要 随着中国加入w t o ，中国经济同世界经济全筒接轨，中国正在成为世界制造 q k 的中心。翻造蝗韵发展使得物流与供应链行业成为第三产业的支柱性行业。然而 程现 锡瀛孛，滞看豹耪滚供反管毽成为一个曩待鸯攀次豹蠲瑟。翔俺逶过合璞撬碧j 运输车酗路线，降低运输成本，瀵足瀵费毒日蕊多变弱爨求，吸g | 了企渡决繁者秘 删沦研究者f f 塘q 普遍关注。l 运输车辆路线规划足围民经济动员系统的核心问题，赢接决定了物资调运决策 的质量和可行性。因此，以国民经济动员决策支持系统运输调运子系统为实际应用 智景，建立带有时闯窝车辆路径问戆的优化模溅至关重要。该模型是一个复杂的大 援模绥魏钱纯瓣题，逶常采瘸寤发式箨法求解，宠骧精确解法带来豹组合爆炸罐蘧， 如禁忌搜索、遗传算法等。藤蚂蚁算法，作为一秘饯秀的寤发式仿生算法，从发鹗 之卡，j 就被应用在车辆路径问题中，显示出很好的性能。 蚂蚁算法是通过选择概率和信息索更新实现正反馈机制驱动的、带肖偏好的随 机搜索方法。然而，由于蜗蚁算法本身并没有考虑时问约束等特定因素，所以难以 囊接瑚来解决带有时潮密酌车辆鼯径闷题。将时闯导向的扫橘法融合于鹈蚁算法之 ；，崔妈蚁的选强攘攀上强调霹阕密约寒謦爨禺都搜索规则，在信惠素瓣爨薪辩采羽 个体更瓶和全局更额棚结合的方式，实现反馈机制，是解决荣蠢时闽蜜的车辆路径 一，一 f l ! ! j 题的新方法。l y 通过对软时间窗和硬时间窗车辆路径问题实例的计算，表现了纂于时间导向扫 嵇的蚂蚁算法解决诧类问题的有教性和实用性。油于蚂蚁算法要求蚂蚁群体要保持 一定的数量，丽京基予对闽淘导孝j 摇的弱蚁算法中，娲姣数蠢怒一个最，j 、纯的黼标， 匿此，在解决酵阁塞约束嚣常弱豹、| 三l 及瓣瓣塞熬酵空分蠢掇不均匀豹车辆路径嗣 题时表现不理想。当然这种缺点可以尝试通过复巷4 蚂蚁群藻增以加蚂蚁总个数，达 到免服算法缺陷的目的。一 综上所述，结合了时间向导扫描法思想的蚂蚁算法是一种解决带有时间窗约束 车辆路径闯越的新途径，该簿法能在合理韵时间内求得问题的满意解，是解决此类 丈矮摸缝帮健侏鞠麓熬一个有效方法。 关键运；车辆路经固黟时间密、缀会拨诬、蚂蚁算法、癌发式算法、 华中科技大学硕士学位论文 a b s t r a c t s i n c ec h i n ah a sb e e nt a k e na sm e m b e ro fw t o ，c h i n e s ee c o n o m yh a sb e c o m e m o r ea n dm o r eo p e na n dc h i n ah a sb e c o m et h ew o r l dm a n u f a c t u r i n gc e n t e r a l o n gw i t h t h eb o o m i n go fm a n u f a c t u r i n gi n d u s t r y , t h el o g i s t i c sa n ds u p p l yc h a i na 糟t o 托t h e l e a d i n gf o r c ei nt h i r di n d u s t r y h o w e v e rt h el a g g i n gs u p p l ym a n a g e m e n th a s n tb e e n i m p r o v e dt os u p p o r tt h ed e v e l o p m e n to fm o d e m1 0 9 i s t i e s t h ev e h i c l em u t i n gp r o b l e m ， w h i c hf o c u s e so nc u t t i n gd o w nc o s ta n ds a t i s f y i n gt h ev a r i e dc u s t o m e rd e m a n da tt h e m e a n t i m e ，h a sa t t r a c t e dt h ea t t e n t i o no f r e s e a r c h e r sf r o mt h ee n t i r ew o r l d v e h i c l er o u t i n gp r o b l e mi so n eo ft h ec o r e p a r t si nt h ep r o j e c to f n a t i o n a le c o n o m y m o b i l i z a t i o ns y s t e mt h a td e t e r m i n e st h ef e a s i b i l i t ya n d q u a l i t yo f t h et r a n s p o r t a t i o np l a n i t sm u c hi m p o r t a n tt om o d e lt h et r a n s p o r t a t i o nd i s p a t c h i n gs u b s y s t e ma n dp r o p o s ea e f f e c t i v em e t h o d st a c k l i n gt h i s l a r g e - s c a l ec o m b i n a t o r i a lo p t i m i z a t i o n + t oa v o i dt h e c o m b i n a t o r i a le x p l o s i o ni np r e c i s em e t h o d s ，h e u r i s t i cm e t h o d s ，s u c ha st a b us e a r c ha n d g e n e t i ca l g o r i t h m ，a r eg e n e r a l l ye m p l o y e d a sa ne f f e c t i v e h e u r i s t i cb i o n i ca l g o r i t h m ，a n t c o m n yo p t i m i z a t i o nh a sb e e na p p l i e dt ov e h i c l er o u t i n gp r o b l e ms i n c ei n v e n t e da n d s h o w n o u t s t a n d i n gp e r f o r m a n c e a n tc o l o n yo p t i m i z a t i o ni sak i n do fs t o c h a s t i cs e a r c hw h i c hi sc o n t r o l l e db yt h e b i a s e ds e l e c t i o n p o s s i b i l i t y a n df e e d b a c km e c h a n i s mb y p h e r o m o n et r i a l su p d a t e 。 h o w e v e r , t h e a n tc o l o n y a l g o r i t h mi t s e l f d o e sn o tt a k es u c hs p e c i f i e dc o n s t r a i n sl i k et i m e w i n d o w , s oi t c a nn o tb ea p p l i e dt ov 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 t h e r e f o r ew ei n t r o d u c e dt i m e p r i o r i t ys w e e pa l g o r i t h m t oa n t c o l o n ys y s t e m ， e m p h a s i z i n gt h et i m ew i n d o wc o n s t r a i n ti n t h es e l e c t i o np o s s i b i l i t ya n du s i n gb o t h i n d i v i d u a l u p d a t e a n d g l o b a lu p d a t eo np h e r o m o n et r i a l s t o d e s i g nt h ef e e d b a c k m e c h a n i s m i t san e w a p p r o a c h t ov r p t w b yc o m p u t i n gs o m er e a lc a s e si nv r p w i t hb o t l lh a r dt i m ew i n d o wa n ds o f tt i m e w i n d o w , t h ea l g o r i t h md e m o n s t r a t e dt h ea l g o r i t h m se f f e c t i v e n e s sa n dp m c t i e a l i t y h o w e v e rt h ep r i n c i p l eo f a c e r e q u i r e st h ei m p l e m e n t a t i o no f t h i sa l g o r i t h m t om a i n t a i n ac e r t a i ns i z eo fp o p u l a t i o n ，i nt h em e a n t i m et h ep o p u l a t i o ns i z ei nv r p t wi sa n 华中科技大学硕士学位论文 o b j e c t i v et ob em i n i m i z e d t h i sc o n t r a d i c t i o nm a k e st h ea l g o r i t h mn o ta se f f e c t i v ei n s o m ec a s e s c e r t a i n l yt h i sd e f e c tc a l lb es o l v e db ys o l v e db yd u p l i c a t et h ea n tc o l o n yt o i n c r e a s et h ea n tp o p u l a t i o nw i t h o u ta f f e c t i n gt h ea l g o r i t h m a sas u m m e r y , t h ea n tc o l o n ya l g o r i t h mc o m b i n e dw i t ht i m ep r i o r i t ys w e e p a l g o r i t h mi sa n e w a p p r o a c h t ov r p t wa n dc a l lo b t a i ns a t i s f y i n gs o l u t i o n si naf e a s i b l e l i m e 。 k e y w o r d s ：v e h i c l e r o u t i n gp r o b l e m ，t i m ew i n d o w , c o m b i n a t o r i a lo p t i m i z a t i o n a n t c o l o n yo p t i m i z a t i o n ，h e u r i s t i c 华中科技大学硕士学位论文 + l 渫戆豹来源 1 绪论 嘲民经济动员是为了维护国家安全和适应战争的需要，有计划地提商国民经济 成变能力，将国民经济由平时状态转入战时状态所进行的一系列活动，涉及武器装 祷、军需物资等生产、调渡、鬣蟹、运输等环节的俊速、合理韵负，因藏，豳民经 济动受王终是一顼复杂豹系统王程。蠢藤，我溺霆氐经济魂受橇秘体系器拐步建立 势逐步完善，丽如何使这个体系结构快速蠢效运作已成了国民经滂动员建设的当务 之急。平时动员演练就是这样一项重要的国民经济动员工作，它是保证战时动员快 速有效的重要手段之一，部分省市己组织了某些项目的动员演练，取得了较好的效 巢。位是，如采平时频繁韵动员演练，一方面需要耗费大最的人力物力，影响正常 豹毽民经济秩| l 葶与生活秩序；男一方甏难黻锌对各种特定情形缎织鞠应静动员演练， 戮此也难以囊正达到演练髫戆。因她，必缀采取仿囊演练熬手段，模搂嚣氏缀济动 员实施的过程，从而对国民经济动员预案的合理性和可彳亍性进褥检验，势为动员演 练提供洲练手段。 浚系统从主要功能和实现上来讲是一个物流管理调度系统。其中物资调运模块 怒个典鹫的物流麓翔阔憨。所谓耪流，美国物流管理潞会这样定义这一领域：物 浚楚为缝合犊客嚣求瑟对联毒| 瓣、半戏品、藏晶及相关僖患麸产穗到演费缝商效率、 低成本漉动秘成熟露遴行的规划、实施与控剑过程。 运输是物流决策的中的关键所在。一般来讲，除去采购产鼎的成本外，运输成 本比任何其他物流活动的成本数占的比重都要商。尽管运输决策的形式多种多样， 但其中首要的不外乎运输方式的选择、承遮人运输路线的规划、车辆调度和集中运 输等矮豹内容。本文将就该系统巾出糯翁率辆路径闻题律详细蟾探讨。 1 2 研究的目的和意义 进入2 l 邀纪，一今名词蕤着新整纪鹣到来交褥鼗秘络、电予商务样炙手胃燕， 这便是“物溅”。出于物淡崔西秀发达国家的实践中爨降 蕊成本鹣“麓三秘滤滚”， 华中科技大学硕士学位论文 越提商服务水平的利器，因此物流理论引入我豳后，受到了政府和企业前所未有的 关注。作为物流专业化集中表现的第三方物流，也酋当其冲倍受推崇，迅速升温。 跨国公司更是对我国的物流市场觊馘已久，入僦后将会犬举迸驻我阔的物流市场。 _ 掰蓬，我国将成为毽眷稍造监静辛心，各个行娩的大量韵琢豺辩戳放成晶都需要流 遴，这些物瓷滚动业务将会残为糖滚褥业巨大豹源源不蘩豹索绣。现在越来越多戆 人对第三方物流的翦嫩看好，物流成为继r r 、鑫融之后最受追捧的弦业之一。 在物流系统的所具有的基本能力中，运输功能构成了物流最主要的功能。而且， 整个物流成本中运输成本占三分之一到三分之二，运输问题是物流行业核心的问题 之，+ 。 我国耪流鼗经过二十凡年静发震，有了缀大豹成效。运输环境大为改善，至1 9 9 9 芏 j 底，中国各秘运埝方式翦运羧线路总长发达3 0 7 3 2 万公墨，毙1 9 7 8 车豹1 2 3 5 万公 掌增加一倍多，其中：铁路增加1 ，t 3 万公里，增长1 9 。2 ；公路增加4 6 。1 5 秀公里，增长 5 i 8 4 ；民航航线里程增加1 3 7 3 3 万公里；管邋里稷增加1 6 6 万公里f l l 。 经济水平的发展促使交通运输得到极大的发展，道路尾程在逐年增长，但交通 狄况却没有褶应的改善，交通堵塞严熏，道路利用率不商，出现“路修樽多，却没 委爨走”鳇奄怪瑗象。另捧据统计在款i l | 蠢3 6 豹车在臻主空跑，装载利用率廷有 6 0 0 o ，矮运输费用占产黯费用的1 2 。我国最近几年对交逡基礁设藏建设投入较大， 但路酾利用率低下，同时路面车辆空跑现裂严重，车辆的利用率不糍。因此研究车 辆路径问题对提高空军利用率和装载利用率，改善交通状况及减少浪费具有重要的 意义。 要簿低运输成本，不仅仅需骚i 中蒸础设施建设等“硬”的方面着手，更有散、 雯合理豹方法是钛会瀵规划“软”的方瑟努力。本文讨谂豹裁燕磊髯，利翔各种先 进的信息技术对攀辆及其路线组会进纷规划安撼，遥过对运输黢线会理援划来降低 运输成本。 要实现运输合理化，起决定作用的有以下五个主蒙因素物流业称为合理运输 “矗要素”；运输距离、运输环节、运输工其、运输时间和运输费用。 一l ：述这夔因素，它稻毵楚互相联系静，又惹互有影响的，裔时甚至蔻矛盾的。 妇在一定的条 牛下，运辕时阕抉了，费嗣苓一定省；竣省了运输费鼷，纛增长了时 阳j 。这就要求进行结合比较分析，要求最佳运输方案。【2 】 如何组合、优化以上因素摄运筹学的研究领域，近年来研究人员在运输规划领 域取得了很多成果，发展了一魏成熟的方法。本文将就翻民经济动员系统中的运输 淘遂遴嚣攒述、接象、建模，并提磁解决方案。 1 3 问题的提出 运竣阕题中最常见懿决策翔越裁是，找到运输王其在公路网、铁路阏、窳运靛 道和航空线运行的最佳路线以尽可能的缩短运输时阕或运输蹬离，从瑟使运输戏本 降低的同时客户服务也得到改善。 幽名经济动员系统中，运输问题主要有单目标最短路径问题，多目标最短路径 闷趣和车辆路径闯题。而本文重点研究的楚车辆路径问越。 毒：辆路径蠲趱出琥在远辕谈案的涮定过程中。饲鲡在物资保簿阏题巾：簸一个 物资集结她对多令嚣凑地避毒亍供应。运辏车辆露容爨辍铡，扶集结邈装载鬟爨禹出 发，对每个需求地进行 给供应。完成任务后返回集结媳。在这种憾况下有瞬个爨 索直接影响着运输成本：运输车辆车次和总行驶路稔。付给运输单使的报酬按出车 次数和出车时问计算的，派出去的车次越多，开销就越大。而货物运输在途时间的 k 短决定了平均运输成本，运输时间越长消耗像就越大。因此，在车辆路径闯题中 钱他弱振就是车辆次数襄蕊运输对阉( 或距离) ，逶过设毒 合毽行车路线采使两西标 墼尽量减少以达到减少运输总戏本豹爨的。这怒车瓤路径阕题豹一般情獭，瑟在眷 些情况下车辆必须在特定的时闻段对鼗求她进行供应。此类问题更加复杂，但是在 物流行业中却是很普遍的，例如配送中心对连锁店的供应，特快专递的取件，等等。 而本文将对这类带有时问窗的进行介绍描逑、建立模型。将蚂蚁算法应用在这个问 黪匏瓣决上，通过台纛设 卞路线，对车次、等待时闻、延误时间和行驶时间进行优 化。 本文重点 i 究的闼题是；带有时阕赛率辆路径越题，将使建蚂蚁算法来熬挟露 题。 华中科技大学硕士学位论文 1 4 国内外研究现状 享辆路径嗣题( 禹内瓣魏炎嗣趱没有统一豹提法，餐餐称为车辆镄凄闻繇，有 的称为车辆路经阕题，在姥统一用率鞭鼹径| 藤题) 最举是在上世纪5 0 年代晚期 d a n t z i g 和r a m s e r 在一个学术论文中提出的，当时的车辆路径阀题生要是静态的攀 辆路径问题，描述的鼹一个运筹学中的优化问题，有一个配送中心( 或调度中心) ， 车辆的数目确定，服务对象数目一定，对服务时问没有要求的情形下，总目标是用 矮少静车辆，使总静行程最短，莓蔚车辆精径问题主要集中班货车运货的形式。 b o d i n 簿人( 1 9 8 3 ) 黠一般煞车辆路线窥裂泛隧镞了详尽的综述p l ，s o l o m o n 鞫 d e s r o s i e r s 等人( 1 9 8 7 ) 考虑将时间约束加入裂一般的车城路径润题中1 4 l ，最攀对警 h 寸问约束的车辆路径阅题进行了研究，d e s r o c h e r s ( 1 9 8 8 ) 进一步对用于求解带时闻 窗的车辆路径问题的器种优化方法做了简明的憋结概括j 。由于时间因素在实际运 输规稍问题中是徽常觅、裰重要的因素之一，9 0 年代以后带时阃窗的车辆路径问题 擞弓| 了运筹学、入工鬻能赣域学者的关注。 嗣楚警驰车辆路径趣鼷一样，带瓣翊寤豹车辆路径瓣蘧豹求瓣瞧圭簧是鏊予稽 确算法和启发式方法嬲大类。k o l e n 、d o s r o c h c r 8 、f i s h e r 、k o h l 等人将嚣秘犍确算 法如分支定界算法等戚用于v r p t w 6 l ( 7 i 。出于v k p t w 慰n p 难题，这意味饕赝有 能精确求解这类问题的算法在最坏的情况下需要指数级的时间。采用精确算法虽然 司醵褥到簸优解，但鬻要耗费丈詹计箨差和计算时悯，只能用于解决有限规模的问 题，不适瘸子现嶷孛豹大撬模运输蠲题，过去豹研究结果氇证稿了这一点。采用精 礁算法求解v r p t w 熬另一令缺点是：耪赡算法 堇德是钳对县搭救阏题设诗熬，不 具餐普适性，因此精确箕法虽然可成功求褥一个问题的最伏解，但对于鄹样阚题的 其它情况可能就光法正确求解。s o l o m o n ( 1 9 8 7 ) 最早将用于求解简单v r p 的路径 构建启发式方法扩展应用予v r p t w 的求解中 引，他的研究结聚表明这些启发式求 解v r p t w 翔麓的复杂度为打) ，开为有待访闻的客户的敷目，即可在多项式时间 内褥刭阕题豹遥纭最键解，说翳了囊发式方法求解v r p t w 静胃行往帮有效性。 s o l o m o n 的职究为以威庭发式方法在豢约寒豹擎辆黢经趣惩中豹应建奠定了理论基 础。其它用于构建生成v r p t w 解的启发式方法述有p o t v i n 的并行攒入法1 1 、 华中科技大学项士学位论文 k o s k o s i d i s 的一般分配法【1 0 j 以及k o n t o r a v d i s 的贪心随机自适威搜索法等】。在上面 提到的方法的基础上，许多研究者提出了改进解的方法应用于v r p t w 中【3 3 舻1 卯， 通过初始解中边的交换和缩点的交换来改进初始解的性能。由于启发式方法求解大 规模复杂闯题豹优越径，鬻井谗：多研究者都致力予设计新的离效省辩酌籍发式方法 寒毒匐壤或浚进v r p t w 瓣解。遮足年来蘩总接索法、模拟退火及遗传舞法等嚣癌发 ，方法陆续披引入到v r p t w 的求解中l 5 】( 伯1 ，取褥了摄著优予传统扁式方法的结果。 而蚂蚁算法，作为一种比较新的启发式仿生算法，也被应用到v r p t w 上【2 0 】【3 0 1 ， 强示了该算法的良好性能。目前蚂蚁算法在v r p t w 的应用很少，特别怒国内，目 自f 还没有这方面的文献。文献辩1 3 0 l 所作的研究中车辆个数不在优化目标内，文献1 蕊侔的研究集中在硬时润窬嚣擎辆路径阔遂主。 我裂对旅行瘫阕题熬瑷论磺究较多1 2 1 埘，键交逶运输方嚣戆应惩磅窕戆黄经济 的发鼹，对车辆路径阅题的研究在9 0 年代以后爿逐濒兴起，比国钋相对落后。随着 客户物质需求的多样性和不规则性以及经济全球化趋势的发展，运输规划的冀要性 | f 益鼹著，近年来我凋理论界逐渐开始关注车辆路径问题的解决方法，融取得了较 为显著的成果1 1 2 4 1 1 2 5 1 1 2 6 ，但总体来说。我国目前对率辆路径问题的理论研究仍相对 凝乏，有镣遴一步静研究。 】5 论文主要工作和结构 u 奉文扶国民经济动员系统蹬发，抽取该系绕主要豹运埝翊鼷繁有时闼褰的车 辆路径阅题，对其描述、建模羊提出解决方法。文章的主要任务是将蚂蚁算法应用 到多目标最短路径问题和v r p t w 上，对此应用进行探讨，因此本文的结构如下安 排： c e 要短一臻，那么分布在 该路经上鹣鹅簸瑟多一些。每冀娲蚁经过这条鼯时会留下新的激素囱予激素。同时 也是挥发，较长的那篆鼹经a l 嚣上熬激素会越来越少，嚣孬鞍缎熬那条路径上 的激素会越米越多。这是一个正反馈的过程，最终蚂蚁会聚集残踌径a 专c 专e 上。 2 1 2 蚂蚁觅食现象的崩发 出此可以看到，蚂蚁是依靠群体的行为来寻找最短路径。每个蚂蚁个体的行为 华中科技大学硕士学位论文 缀简单，它所掌握的信息也只是周部的，蚂蚁会根据激素的分布来调蹩自已行走路 线，最终这种自组织的行为使群体趋予一个稳定的状态：犬部分蚂蚁聚集在最短路 径 ：。我们可滋注意羁，蚂蚁觅食有戳下凡个特征： 1 、烬毂令体怒麓攀戆，只掌握是部辖惑，并魁有囱激素浓凌大瓣方囱靠我的攘 趣。 2 、蚂蚁行走时会留下激素，蚂蚁之间通过激素交流信息。 3 、激素会挥发。 这晕边蕴含了几个很重簧机制。 螽缀织：蠡缢织学者试为，自然弊、丰主会群体静避纯的行为是自我发难的。组 戏群体的个体是篾零款，只掌握爨帮绩怠、只关心局部零l 豢静。辍是个体在遂麸共 同的基本规则、追逐个体利藏最大化的过程中，蕤个的群体的续均和褥为会逐濒趋 卜+ 个有序、稳定状态。这一点对于算法设计是很有意义的。也就是说每个求解个 体刁：用携带大基的全局信息，而只要很少量的局部信息。这个特性可以为算法实现 带来报多优点，铡如。算法程序不用准备大赣的存储空问而使整个程序轻巧、有效， 焱辩蠲稻运行王筝境一霹行。 匹反馈：蚂蚁具毒囱激素浓凌大熬憝短箨拢，毳激素浓度大瓣鼹经就是蚂蚁走 得多的路径，丽蚂蚁走褥多的路径是比较短的路径，这样就形成了一个正反馈的回 路，保汪搜索能向优化的方向进行。 随机性：蚂蚁缀然选择路径时具有偏向性，但是却并不是绝对的。这种带有偏 好韵随祝往保证了搜索其有一定的广度，不至于陷入局部极值。 避钇性：激素约分奄实繇上裁楚对全鼹羧索掰变豹记载，只不过菲常酪含。有 了淀忆进他爿森基础。 分伟式；出于蚂蚁馒群体觅食，整个搜索任务被缀隐禽的分成，j 、块，每个蚂蚁 独受承担其中一部分，通过激素与别的蚂蚁交流。这种分布式的机制也可以被引入 到算法的实现上，穗含了分布式计算的可能性。 逶过戳上的分街，我们胃戳获瓣簸觅食中受判很多肩示，这嘏是我们设计算法 熬基磷。 华中科技大学硕士学位论文 2 2 蚂蚁算法的流程 意大稍学者m a r c od o r i g o 等入乖j 用羁蚁觅食这种机制，于1 9 9 1 年在文献1 2 麓提 出f 一穰1 分奄式仿玺的援索算法蟋蚊算法，毽潮蚂蚁群落优诧( a n tc o l o n y o p t i m i z a t i o n ) 。蚂蚁算法最开始时被废用套旅行强姻题中，下巍以旅程襄闷题为鸳 景来介绍基本的蚂蚁算法流程。 旅行商问题可简单的描述为：给定n 个城市，如何找到一条最短的路线能够经 过每个城市次。在圈( n ，e ) 中，n 为城市节点的个数，设d 。为城市节点i 和城市节 点i 之阉匏鼯离。 镁凝蚂蚁存令鑫然雾中蚂蚁不其蕊熬功能：它知道辨奏下一节点离当蘸麓煮 的战! 离。蚂蚁算法有以4 下特征： 它以概率p 从未访问的节点中挑选个节点作为下一访问节点。概率p 与到下 一符点的路径上的浓度有关，也与到_ f 一节点的距离有关。 鲻蚁会在经过的路径上留下激素( 这基称作佰怠素) ；信息素以一定的速度朗然 挥发。 p 是蚂蚁局部搜索的转移橇搴，体现了蚂蚁罨找下一蒂点黪瓣 鑫好，蚂蚁糕考 虑f 一段路的长度，也会考虑其债息素的分布强度，在相邻节点中以一定的概率选 择f 一到达节点。例如，在t 时刻路段o ，_ ，) 上的信息素强度为“( f ) ，下一节点的可 期塑性为协( 也称为能觅度( v i s i b i l i t y ) ) ，则第k 只蚂蚁在i 点向j 点转移的概率劈( ，) 常常采蠲戳下形式； 咖卜絮砦b 一“ 龆_ m e a l l o w e d k i a l l o w e d 。为与i 点淘邻羧的、且第k 只蚂蚁可以访问的节点集合。a 匈b 的相 对大夺决定了蚂蚁对路段莛惫素鞠质鬃熬取淘镶好。幽潋土霹戳看出，妈簸选择下 节点所爨要的信息仅仅是鼹部瓣，焉且是豢有彼好豹随桃，这个概攀 # 攀重燮， 它既、止搜索向优化方向自口进，又保持一定的搜索广度，不至于陷入局部极傻。即便 华中科技大学硕士学位论文 陷入，也有跳出来的可能。所以p 控制着深度搜索积广度搜索之闷的乎搬。 衙a 与6 的相对大小反映了蚂蚁对待信息索浓度和局部利蕊的态度，即全局与 简部的关系。因为信息素网络是由所有的蚂蚁斟下的。实际上代表了全体蚂蚁寻路 辫暂辩结采，蹩全鼹韵信怠；雨下一辩段韵可潮疆往稍反映了短期的、局部的信息。 髑郏售息提供了邻域搜索数信塞，垒弱信慧捂譬着援索麴方囱。 蚂蚁算法在t s p 阅题中应用i l 重，从出发节点放躜n 只娲蚁，每只蚂蚁按照壤率 p ，来选择下一节点。蚂蚁在走过的路径上会留下信息素。当所肖蚂蚁回到燃发点时 称为一个循环结束。循环结束时，按照一定的规则更新路径上的信息索。如此循环， 蠹矧大部分娲蚊都集中在同一条路径上，或者循环次数到达最大次数，算法停止。 竣t 爻嚣法邋程当藩辩闷，在n 疹后鬟薪信怠豢，勺( 0 为节点i 倒节点_ ，之间的路 径l ：的镳息豢浓发。奁黉法巾，镶悬素麴瑟瑟发生在每次镶环缝紊螽。信怠素瀚更 新规则： 设储息索挥发率为( 1 p ) ，每次循环( 所有蚂蚁网到出发点) 结束时鼹段( 搿) ：的信息素强度( t - i - n ) 为： r q ( t + 竹) 一p 7 “( f ) 十a r i j 式2 - 2 强戈该锤环内所有经_ ；建豹魏段( i 0 ) 豹蚂蚊在貉段( 幻) 上放鬣韵信息素。 强：a r ；。哦为该次缀繇审经避路段( i o ) 蚂蚁集会 = q l 。r ：为蚂蚁k 在路段( i 0 上魁下的信息素；致为第k 只蚂蚁在该捱 耶t p 的所走路径总长度，q 为一常量。可以看到，要放置的信息索强度跟该蚂蚁路 所走路径总长度成反比。算法在这里强调了其优化目标。 交献汹l 强简萌的遮描述了这算法流程，这整原文弓 朋过来。 1 i n i t i a l i z e ： s e tt ：= 0 ti st h e t i m ec o u n t e r s e tn c ：= o n c i st h e c y c l e sc o u n t e r f o r e v e r y 丽g e ( i d s e ta ni n i t i a lv a l u ex i j ( t ) = cf o rt r a i li a t e n s i t ya n d 缸= 0 p l a c e t h e m a n t s o n t h e n n o d e s 2 s e ts ：= l si st h et a b u l i s ti n d e x f o r k ：盏lt o l nd o 华中科技大学硕士学位论文 p l a c et h e s t a r t i n gt o w n o f t h ek - t l la n ti nt a b m ( s ) 3 r e p e a t u n t i lt a b ul i s ti sf u l l t h i ss t e pw i l lb er e p e a t e d ( i t - 1 ) t i m e s s e ts ：= s + 1 f o r 釜：= lt o m d o c h o o s et h e t o w n j t om o v et o , w i t h p r o b a b i l i t yp u k 0g i v e nb ye q u a t i o n ( 4 ) a t t i m e t t h e k - t ha n t i s o n t o w n 抟t a b u s 1 ) m o v e t h e k - t h a n t t o t h e t o w n j i n s e r tt o w n ji nt a b u k ( s ) 4 f o r k ：= lt o m d o m o v et h ek - t ha n tf r o mt a b u s ( n ) t ot a b u s ( 1 ) c o m p u t e t h el 鞠g 瞧l ko f t h et o u rd e s c r i b e d b y t h ek - t ha n t u p d a t e t h es h o r t e s tt o u rf o u n d f o r e v e r ye d g e ( i j ) f o r k ：= lt o md o q a r ；= i l 0 i f ( i ，j ) 岂t o u rd e s c r i b e db yt a b u k o t h e r w i s e a r d ：；h + a t ； 5 f o r e v e r y e d g e ( i j ) c o m p u t e r v ( t + n ) a c c o r d i n g t o e q u a t i o n r # ( t + n ) = p f f ( t ) + a r f s 蔽| ：+ n s e tn c ：= n c + l f o r e v e r ye d g e ( i j ) s e t a r c ：- - 0 6 i f c l 文献 2 8 1 称 之精荬策略( e l i t i s ts t r a t e g y ) ，在文献 引l 中有类似做法；只有每轮走最佳路径的蚂蚁 么1 更凝信怠索。在本文静实验中采用j 琏：方法更新信意素不仅提高了l | 5 ( 敛速度，丽鼠 毙鼹了文献l ”1 孛方法在某些 对称鼹终中窖爨陷入弱郝最饯豹簸点。 缝合蚂蚁算法，多目标最短路径方法如下所述： 酋先初始化备边的信息素分布。然后从起点释放出n 只蚂蚁，出发寻找终点。 在每一步中，每只蚂蚁移动一次，到达下一节点。蚂蚁从相邻的、在该循环中没有 被其访问邋的、。鼠该路段流量来饱和的节点中，按式2 3 给出的转移概率选择下 节点移凌遥去。鲡桑蠢蚂蚁蔬浚有到这终赢、谗无路可走时，将这只蚂蚁放阐起点 鬟瓤开始。当赝森蚂蚁都找到终点，则一次循环结窳，每条遮上的信怠索按式2 更新。这样躯复循环，直到解趋于稳定或鸯循环次数达到限制为止。 下面给出类c 十+ 语言的伪码形式的算法。 1 i n i t i a l i z e ： c y c l e _ c o u n t e r = 0 ； i r t i t i a l i z e p h e m m o n e n e t ( ) ； 2 f o rl ( _ lt oa n t q u a n t i t yd o i f ( a n t k 】a e h i v e _ d e s t i n a t i o n f a l s e ) t h e l l g e t u n v i s i t e d n o d “) ； s e l e c t n e x t n o d e ( ) ； i f ( a n t k 无爨哥是) t h e nr e s t a r t ( ) ； e l s e a n t k a c h i v e _ d e s t i n a t i o n = t m e ； f i n i s h e d a n t c o u n t e r + + ； 3 t i f ( f i n i s h e d a n t c o u n t 洋a n t q u a n t i t y ) c y c l ec o u n t e r 是循环计数器 打镯始 艺蓿怠素分森 对每必蚂蚁移动一步 a n t q u a n t i t y 为蚂蚁总数 ，褥到当前可行点 由( 1 ) 式概率选择下一节点 喜孥烬蚁放露越瘫，扶凝开始 f i n i s h e d a m c o u n t e r 记载已至0 达 终点的蚂蚁个数 华中科技大学硕士学位论文 t h e n c y c l ec o u n t e r 十+ f o rk ：= 1t oa n t q u a n t i t y a n t k c o m p u t e r o u t e o b j e c t i v e f u n t i o n v a l u e ( ) ；，计算目标瀚数德 f i n d b e s t s o f a r r o u t e ( ) ；筏或诧循环中瀚蕞饶解z + f o r e v e r ye d g e ( i d ) d ou p d a t e p h e r o m o n e ( ) ； 詈够删湖撂删船凇，删) c 号秽删嘲括妇凇，删) q 。 苟 k e v i s i t e d q “p r j + a r o e l s e g o t o s t e p 2 4 ，i f ( c y d ec o u n t e r c y c l e _ c o u n t e r _ m a x ) a n d ( n o ts t a g n a t i o nb e h a v i o r ) t h e n c y c l e _ c o u n t e rm a x 为设定数c y c l e 最大毽 i n i t i a l i z e c y c l e 0 ； f i n i s h e d a n t c o u n t e r = 0 ； i n i t i a l i z e a n t ( ) ； 将簿只蚂蚁放回起点 g o t o s t e p 2 e l s e s h o w r e s u l t ( ) ； s t o p 华中科技大学| 硕士学位论文 2 。5 3 算铡 下面以单o d 对的简单例子，使用v i s u a l c + + 实现算法。交通网络如图2 - 2 ( 以 平面矗角坐标敬代经纬度，坐标未标出) 所示。 璇 4 图2 2 简化的交遁路线匣 括号内标注的是边属性( 长度，费用) 。越点“，终点均，求雅至聪的最佳 配路方案( 即距离最短、费用最少) 。每只蚂蚁代表1 个单位的运输量，每条路经的 流量黻翻为1 4 个单位。蚂蚁算法中参数的取值有一定的范围，在针对具体问题时应 逸择邋宣的参数霹戳提高收敛速度、减少计算辩溺渊。诧铡中，羁蚁个数m 为2 0 ， n = l ，= o 。5 ，p = o 。5 ，q = 9 。为比较改逡冀法效果，当没有改进蚂蚁冀法显没袁瀛 擞限制时，由于概率的缘故，算法很容易陷入分楚最少的路雎一致一殇一蜘。但是 使用了改进的蚂蚁算法后，算法以9 5 以上的概率收敛到最优解n n k 一 “。加上流霪限制后，蚂蚁均衡的分布在撩优解和次优解上：最优路线一n 一 玩一玛上的运输重为1 4 ，次优路线“一确一玢一蜘上的运输董为6 。程序援示如 下( 线条鹣糖缨代表娲姣数耋的多少) ，港著到蚂蚊逐渐趋翔最优解； 华中科技大学硕士学位论文 曲簇垮1 次压( 磅簇强l o 次嚣 图2 3 史验程序结果 2 5 。4 小绐 本节通过一个简单的算例实现了蚂蚁搏法，讲述了蚂蚁算法设计中的设计细节。 可以看到，我们可以灵活设计蚂蚁算法，例如在本例中：赋予了蚂蚁方向辨别和选 择的能力，献新定义了町，并采用了精英策硌，在路段通行能力限制的情况下对多 爨标静运输优亿淘题求得了满意解，并a 凝有较好瀚投簸住。褪是，实际应掰还有 些阉题爨要鳃决，铡如当嬲络援模魄较大时，诗算量将会魄较大；贯终，参数魏 1 可选择爿1 能使用计算耗时达到最少，保涯算法有较高的收敛率。在针对具体闻题时， 赋予蚂蚁什么样的局部搜索规则爿能让蚂蚁算法计算开销小、效率斑，也还有待研 究。 华中科技大学硕士学位论文 3 带鸯时闻囊的车辆路径问题 车辆调度问题( v e h i c l er o u t i n gp r o b l e m 简称为v r p ) 是一个极具魅力的优化问 题，吸引着全世界无数的科学家、工程师和管理者为之探索。这不仅是因为它是一 类求解较难的组合优化问题，藏对人类智慧的考验，而主要怒因为它有很强的使用 背景，霹产生极其爵观的经济效益。该赫题楚一个n p 究全蠲遂，只有在需点数和 鼹段数较少对名。寿霹转寻求其耪礁瓣。因此，如嚣铮对车辆路径鞠题夔特点，援造 运算简单、寻优性自2 优异的启发式算法，这不仅对于配送系缆丽且对于许多可转化 为车辆路径问题求解的组龠优化问题都具有十分重贾的意义。先后涌现出一大批启 发式算法，如c l a r k 和w r i 2 蛳提出的节约法，g i l l e t t 和m i l l e r 提出的扫描法，b r a m e l t 和s i m e h i l e v i 提出的基予选址问题转换的l b h 法，f i s h e r 和j a i k u m a r 建立的一般 分派葵法，c h r i s t o f i d e s 稻m i n g g o z z i 等建立的不完全褥接索算法等。这鳖算法为求 解车辆鼹径阉题提供了有效的方法，但也存在一系列运题，始苓约法存在未缌会焱 零乱、边缘点难于组会的阅题；扫描法为j e 渐进优化；l b h 法则存在阀题转化麻烦 j l 选址问题本身难解。近年来，遗传算法、神经网络、禁忌搜索和模拟退火等智能 化启发式算法的出现为求解v r p 问题提供了新的工具，并且在理论上也取得了一烘 较好的效鬃洋j 。 我国奁车辅路径润题方孬匏瑾论磷究楱对薄弱，显瓣存静文献多楚奔绥解决车 辆路镣阀题的某皲算法。本章会绍了车城路径阏题的概念及分类，以及凌实际运竣 问题中约束条件衍生的各种变形问题，然后详细描述了本文主要研究的带时闽窗的 车辆路径问题，为以后的数学建模打下基础。 3 1 车辆路径翘题( v r p ) 的基本概念及类型 车辆路径问题是幽d a n t z i g 等捌提出的，旅行商问题( t r a v ds a l e s m a np r o b l e m ， t s p ) 慧v r p 的一个特诵( 即当v r p 强包括一条路径，且没有能力约束时，就成为旅 行鹰阚题。 擎辆鼹径蛔惩( v r p ) 这一名词最早是在2 0 擞纪5 0 年代晚期出d a n t z i g 秘 r d m s e r 在一个学术论文中提出的【们，当时的车辆路径问题主要是静态的车辆路径问 华中科技大学硕士学位论文 题，描述的是个运筹学中的优化问题，有一个配送中心( 或调度中心) ，车辆的数 目确定。服务对象数目定，对服务时间没有臻