（管理科学与工程专业论文）基于设计模式的露天矿车辆调度模拟系统.pdf

中文摘要 摘要 露天矿生产是一个集采掘、运输、排卸等生产过程为一体的大型生产系统。 露天矿生产系统中的车辆调度又是影响其生产效率的关键问题。露天矿车辆调度 模拟系统在生产中的应用是评价车辆调度合理性的重要手段。本文通过以下工作 完成了一个基于设计模式的露天矿车辆调度模拟系统的开发与应用： ( 1 ) 采用蚁群算法解决露天矿车辆调度中的最短路径搜索问题。蚁群算法是 基于蚂蚁群体行为的一种仿生算法，具有许多优良特性，为解决旅行商问题f 1 1 p s ) 等组合优化问题提供了一种新思路。本文随后还针对蚁群算法求解最短路径存在 的收敛速度慢，易于陷入局部最小值等缺陷做出了几点改进，成功的解决了系统 中的路径优化问题。 ( 2 ) 通过对露天矿车辆调度模拟系统的研究，建立了露天矿生产系统模拟模 型，并针对系统中所发生的离散事件对系统进行分析。系统运输网络的生成与更 新是通过g p s 文件读取相关数据，经过整理插入到数据库中，最终绘制成可视化 地图并反映在屏幕上。 ( 3 ) 将设计模式应用于露天矿车辆调度模拟系统的分析与设计阶段。通过对 系统特点的研究，本文将工厂方法模式、策略模式、模板方法模式、观察者模式 等多种设计模式合理地运用于系统中。设计模式是针对面向对象的系统中重复出 现的软件设计问题提出的一种通用解决方案。通过运用设计模式，使系统在一定 程度上具备了可重用性和灵活性。 ( 4 ) 利用凹编程语言开发了一个可视化模拟系统，用a c c e 豁做后台数据库， 用a d 0 n l 玎和g d i + 技术绘制可视化地图。该系统具有操作简单和功能较完善 等优点，能为露天矿的生产决策提供了支持。在本文最后，利用模拟系统对生产 中的车辆调度方案进行了评价。 关键词：露天矿；车辆调度；蚁群算法；设计模式 英文摘要 s i 舢l a t i o ns y s t e mo fv e h i d e s d i s p a t c hi i lo p e n p i t b a s e do nd e s i g i lp a t t e m s a b s t r a c t t h eo p e n p i tp r o d u c t i o ni sal 盯g e - s c a l ep m d u d j o ns y s t e mi n d u d i n gm i n j n 岛 仃a 腿p o n a t i 蛐，u n l o a d i n ga n do t h e rp f o d u c t i o np l o c e s s e s t h ev e l l i d ed i s p a t c hi n o p c n p i tp r o d u d j s y s t e mi s t l i ek e y - p r o b i e ma 虢c l si t sp r o d u c t j 彻e f f i c i 朋c y t h e a p p l i c a t j o no f 咖u l a t j 咖s y s t e mo fv e h i d 嚣d i s p a t c hi n 叩蛐- p i ti s 柚i m 呻t i n s t m m e tt oe s t i m a t et h em t j o 加l i t yo ft h ev e h i d ed i s p a t c h t h i sp a p c rd e v e l o p sa s i m u l a t i 衄s y s t e mo fv e h i c l 嚣d i s p a t c hi no p e n p i tb a s c d 咖d c s i g np a t t e m st h r o u g ht h c w o r k sa sf b l l o w ： ( 1 ) n i sp a p c ru s e st l i e 锄tc o l o n ya 1 9 0 r j t h i nt 0s o l v et h es h o f t e s tp a t l ip r o b l e mo f v e h j c l cd i s p a t c hi n 叩e n p i t a n tc o l o n ya l g 嘶t h mi san o v e lb i o n i ca l g o d t h mi n s p 砌 b yt h ep o p u l a t i b 笛e db e h a v i o ro f 卸t s i ts h o w sm 柚yp r o m i s i n gc h 狮d e 墙蛆d 右n d sa 鹏wm e t h o dt os o l v e 湖b i l i a t 砸a l 叩t i n l i z a t i o np b l 咖s u c h 勰t s p 1 1 l c a j g o r i t h n li si m p r o v e d i t ss b o n a g c ss u c h 勰c o s t i n gt o om u c ht i n l e 柚dt c n d i n gt 0 s t i c ki nl o c a lb e s t a n ds o l v et l l ep r o b l e mo fm u t i n go p t i m i z a t i o ns u c c e 嚣f i l l l y ( 2 ) 1 1 l r o u 曲卸a l y z i n gt h es i m u l a t i o ns y s t e mo fv c h i d ed i s p a t c h 证叩c n - p j t t l l i s p a p c rb u 硼su pas i l i l u l a “彻m o d e lo f 叩锄p i tp 州u c i i o n ，加dd i s c i i s s 鼯t h ed i s 口c t c c 、，e n t si nt h eo p c n p j tp r 甜u c t i d e t a i l e d t h es y s t e ma l b u i l d sa n du p d a t e st h e t 伯n s p o r tn e t 、】l ，o r k nr e a d st h eg p sd o c u m t s d a t a 柚di n s e n st h e mi n t ot l l ed a t a b 够e t h e nt h e 劬n s p o nn e 佃o r ki sr e n e c t e di nm 砌t o rs c r c c n ( 3 ) d e s i 印p a t t e m sa 佗a p p l j c dt ot h cs i m u l a t i 伽s y s t 锄i nt h e 趾a l y s j s 柚dd e s i 印 p h a s e t h i sp a p c rd i s c u s 辩st h ec h a m c t c r i s “c0 fas i m u l a t i 彻s y s t e ma b o u tv e h i d c d i s p a t c hi no p 如p i t ，柚d 印p l i e s 跏el 【i n d so fd e s i 弘p a t t e m st ot h es i i l l u l a t i o ns y s t c m - e a s 咖a b l y ，s u c h 鸹f a c t o r ym e t h o d ，s t r a t e g y ，t e m p l a t em e t h o d ，柚d0 b s e r y c r d e s j 印 p a t t e n 略a 圮g e n e m l l u t j o 璐t ot l l e 舢玎i n g f t w a 佗 d e s i g np r o b i e m s i n o b j e c t 州c m c ds y s t e m s t l d u g ht h ea p p l i 训o fd e s i g np a t t e m s ，t h cs y s t e m p o s s e s st h ec h a m c t e r i s 6 co f ”u 锄da g i l j t y 英文摘鬃 ( 4 1 强sp a p c rd e v e l o p sav i s u a l i z a t i o ns i m u l a t i o ns y s t c mb yc 融t h es y s t e mu s e 氲端然静k 重| l eb 鑫c 羹嬲糕蝾d a 嫡a 辩，繇d 舔e 蹴弼强g 瓣专l o 氆a 掰珏鬈 v i 鲥a l i z a t i 册t e c h n o l o 画e s 溯出em a p 1 龟es y s l c mh 罄p c 曦娥孙n c i 册a n dc a nb 。 叩e r a t c de a s i l y nc 锄p r o v j d eh e l p sf b rt l l eo p e n - p i tp r o d u dd e c i s i o n f i n a l l y ，t l l i s p 印e ri l 辩t h es y s t e mt oe s t i m a t et h ev e h i d ed i s p a t c hi n 叩e n - p i t x 秽姆。瞻：o p 髓掰垂；懈l d e 璜s 弦商；a 瓣e 一姻y 越笋矗攮糖；淞l 乒魏l 据疆s 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士硕士学位论文 ! 堡i 滏过缝基西盈龆j 芒墨盖蟊曲疆丛歪盎：。除 论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己 在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已 经公开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：僻2 印7 年月2 7 日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密时请在以上方框内打“一) 论文作者签名：衙导师签名：强曩 日期：上。一7 年r ，月j 7 日 基于设计模式的露天矿车辆调度模拟系统 第1 章绪论 1 1 课题研究意义 露天矿是一个以采掘为中心，以运输为纽带的大型生产系统【l l 。生产计划指标和任 务的完成，生产过程的组织、实施是通过采运设备，尤其是对运输设备的实时调配来进 行的。车流调配是否合理，将直接影响着露天矿整个生产系统的生产效率和经济效益。 人工调度由于不易实时掌握采、运设备的位置、状态，以及工程发展和排卸点的生产情 况，在生产指挥调度中盲目性较大，往往造成卡车赶堆，增加了电铲、卡车的非工作时 间和卡车的空车行程，并难以实时监控设备运行和矿石质量。不利于设备效率发挥，不 便于生产管理，制约着露天矿经济效益的提高。采用大型卡车运输的露天矿山，其运输 费用占整个露天矿生产费的6 0 以上。而且随着开采深度的不断增大，这部分费用也在 不断增加。为此，许多从事露天矿的生产者和研究人员一直在深究影响运输费用的因素， 并寻求解决的对策。研究结果表明，运输卡车台班作业时间只占7 0 ，非生产时间占 3 0 。因此，得出结论，露天矿生产的高效率很大程度上取决于采、运设备的高效率， 对采矿生产的控制可转变为对采、运设备的控制，卡车优化调度是降低采、运设备非生 产时间、提高生产效率、从而降低整个采矿成本的最为行之有效的办法【”。 计算机控制卡车优化调度系统( c 锄p u t e rc o n 昀l l c dt m c kd i s p 砒c h i i l gs y s t 锄) 是基 于上述条件在6 0 年代末7 0 年代初提出的，经过许多专家学者近十几年的理论研究和不 断的实践尝试，于8 0 年代初在国外首先实施成功。计算机控制卡车优化调度系统从它 的产生到今天，经历了计算机辅助卡车调度系统、有线计算机卡车调度系统、数字通信 自动化卡车调度系统、带路边自动测位器的数字通信自动化卡车调度系统，直到今天的 全球卫星定位的自动化卡车调度系统等多个发展阶段。它的主要功能就是通过对露天矿 主要采、运设备的位置、状态、物料等信息的实时采集和分析处理，实现对采、运设备 的实时跟踪，优化调度卡车运行，及时准确地查询统计当前生产情况，从而起到降低采、 运设备的非作业时间和卡车空车行程、准确执行生产计划等作用，以此达到提高设备效 率、降低生产费用、提高经济效益之目的。到目前为止，它己在世界上1 4 0 多座露天矿 第l 章绪论 中得到应用，取的了驻著的经济效豢，据统计表明可提高生产效率6 3 2 ，表现出穰 强的生命力和广阔的臌用前景。 计算缆控割卡车傀他调度系统怒瑷援计算掇技拳、电子通傣技术、全球邋星定位技 术、矿娃系统工程、优化理论、管瓒信息系统理论等多项现代离新技术理论楣结合的产 物，是现代高新技术在采矿工业中的项成功应用。实践证明，它是提高矿山生产能力， 节省投资耱生产成本爨羯，强纯矿啦管理效率，掇凑矿出经济皴薤熬一释嚣鬻戒功豹先 进技术。 在网内8 0 年代初开始了这方蹴的研究工作，尤其在车流规划，优化调度方法方面 铮对具体矿出象传皴大量的研究王终。在系统软箨帮硬馋方瓣毽鼗撂了琴痧藏莱，同 时在个剐矿山上得到了初步应用。假从整体上来讲，计算机撩佑卡车调度系统在我国的 实际应用仍处于起步和尝试阶段。园内生产和拟建的大型露天矿几十座，大都采用单斗 铲专霉嚣采工艺，霆趣，诗霎极接潮专车调度爨纯决策技术纛我莓有广羯戆瘦弱蓑景。 国内外应用实践袭明，只要能使产量提高3 5 ，就足以证明采用计算机控制卡车 调度系统是经济合理的，事实上这种提高的幅度往往达到6 3 2 。表1 1 是卡车调度 系统应镄隽嚣统计爨糕旺在我嚣，谤算辍控潮专车调麦系绫擞然羯处予起步除段，毽 应用的前景十分广阔，需求十分迫切。目前，在煤炭、冶金、化工、有色众属等的矿山 企业都不同程度地开展了该项技术威用的筹划工作，因此该项技术的实施，必将在提高 矿由瓣经济效益霾警瀵零平，渍是妒丞鼹鑫蕴羧翻、产量均簿、设冬整控答方瑟豹多秘 要求发挥巨大的作用。因此加强该项技术开发研究和推广应用舆有重要的理论意义和实 用价值【。 纂予设计模式的露天矿车辆调度模拟系统 表1 1 调度系统应用情况 锄1 1a p 辩奴眭自哺s 拓啦| s 醴d l s p 蘸c h g 啦瞳 矿出位譬 矿由类型生产貔力提高率 巴利克金矿内华达州金矿 1 5 邦格铁矿利比里- 哑铁矿 l o 布干维尔矿融布弧新几内亚铜矿1 3 奄谨矿由公霹耨墨嚣哥搠镪矿 1 3 帝罾铁矿密撬安期 铁矿l 镰 加拿大铁矿公司纽芬兰省铁矿 2 3 l t v 钢铁公司 名尼苏达州 铁矿1 0 帕拉博拉南非铜矿 7 瑟泰特嫫矿毒论毙亚煤矿 l 溅 瓿c e r r e j o nz o n 8 煤矿 l 勰 d eb e e r sj 张n e n g 盒刚石矿 2 8 n a 帅e b众刚石矿3 2 德兴铜矿 江匿 铜矿 9 3 伊蕺露天矿 内蒙古1 9 9 88 雏 1 2 圈内外研究现状 1 2 1 露天矿车辆调度系统的研究现状 在犷渡孛，诗算援摸羧戆予上藿笼五+ 零钱，大多数睾裴懿壤羧蒸是峦用户浚 f 隙t r 脯语言在主视上实现的，主要用于分析铁鼹、汽车等运输系统，用来寻找合理豹 设备配餐、数量配合：评价逐输设备的调配原则；研究各种开拓运输系统的功能、运行 规律、限制和使用条件；分析系统的薄弱环节等。国外利用计算机模拟技术较早，很多 公司剩瘸邂霭的软俘解决矿内驰实际闯题，并铁巾褥到7 客鼹躬经济零l 麓，美国的g r e e n g r e 馥穗下矿垂采躅f 始i 黻t i 摸攘系绕软俘，孺予对薪建豹肇遴囊簇蒡运输豢 统进行模拟，确定了新建的斜井作为回车道的可行性p j ；澳大利难r e n i s o n 地下锡矿采 用了a r e 模拟系统对其矿山的运输提升系统进行模拟。确定了有效的矿井运输开采作 第l 章绪论 韭计划1 4 】；荚遏豹爨魏铜矿采用g e 硼i n 模拟系统进簿生产模攮，缡钊葬诞实了生产计划 的可行性垆“。 ：十世纪七十年代束，露天矿车辆优化调度系统在国矫问世，并在少数几个露天矿 骰了试验搜嚣发与应震玎j 。戴射黪专攀调度系绫燕攘夺、功戆单一，其疆蠡圭鬃在于提 高设备利用率，车辆的方位信号多用设在路旁信号采集器采集，信号的传输、调度指令 的发送为有线通讯。随后，美国的t y r o n e 露天矿成功的安装了迄今为臆世界上最先进 黎蚤l s 黼踩调度系凌，这也括恚羞车辆调度戆研究帮痤耀进入了一令金瑟夔发震除段 嘲。d i s p a t c h 调度系统怒由美围的模块( d u l a r ) 采矿系统公司研制开发的，其调度决 策理论的核心由三个部分构成：为适应矿山西己置形态变化的最佳路线子系统；为适应矿 由楣关变量变纯懿线性羧捌子系统彝为实瑰实时调配静动态鬟翔子系统。疯蔫证裙 d i s p a 丁c h 调度系统可以蠢效的提高露天矿的生产效率，随羲调度系统的不断发展，其功 能也不断完善。目前，世界上越来越多的国家在露天矿这一大型生产系统中运用此技术 来降低生产成本，获得了不镑斡效栗臻键。 计算机专车调发技术在我国起步较烧，在= 十世纪八十年代，限于国内计算机技术、 通讯技术、采运设备信息采集技术等发展水平，以及资金艇缺的附扰，在短期内开发戏 完全喾f 迸自渤住程度较高的调度系统膏穰大困难。许多有谈之士镁首先藏理论磷究上入 手来探讨这一翅题，在优化调度方法，车流热划，运输系绕约模拟等方聪进行了较为深 入的研究，提出了最小饱和度方法【i l l ，最小比值方蓑方法【，综合调度方法等一系列 优化调度方法与算法。困箍为二十世纪九+ 年代的应用研究奠定了基础。1 9 9 0 年由本锈 瘩芬铁矿、玛鞍出矿山磷究貌、泰j 工学院等单莲鳃戏豹联合攻关组开发了嘉芬露天矿 生产调度计算机辅助系统f 】3 】。这也是我国在这一领域一次突破性j 展，标志着我国露必 矿车辆优仡调度系统已经由理论研究阶段过渡到应用阶段。1 9 9 4 雄，霍林河矿物局与煤 辩慧院覆安分貌、孛晷矿业大学会终，舞发完成谤舅掇控剿囊动骰：专车调度系统。江嚣 德兴铜矿的d i s p a t c h 系统从1 9 9 8 年7 月投入使用，魁国内第一家引进模块公司 d i s p a t c h 计算机卡车调魔系统融。瑚。 基于设计模式的露天矿车辆调度模拟系统 1 2 2 蚁群算法的研究现状 筠熬纪5 0 年霞，入爨受瓣了生壤进纯瑾论瓣瘀发，建立了偿雯攀这门学辩，蒡提爨 了许多翔以解决复杂谯纯随繇的颓方法，鲡遗传算法、避纯蔑剜、遴经策路等。这些以 生物特饿为基础演化算法的发展，及对生物群藩行为的发现引导研究人员进一步开展了 对生物社会性的研究，从而出现了基于群智能理论的蚁群算法。 蚁鼗冀法由意太利学者m d 蕊g o 等于1 9 9 l 颦麓次提出，并用该方法解决了一系列组 台甓能 瓣逶“ 霹。酝d o 矗黼，v 潍i e 盈等入谯研究蚂蚊觅食行秀粒发现，臻蚊慧戆找 到巢穴与食物源之间的最缀路径，并能随环境的变化而变化的搜索新的路径。经研究发 现，蚂蚁这类社会性动物，化学通信是它们采取的基本信息交流方式之一。蚂蚁在食物 源与蚁穴之间往返的过程巾会在路径上释放出种叫信息素( p h 蹦黼e ) 的挥发性化学 耱震，瓣基麓藩袅这蘩物鬟豹存在及其强度，势渡诧雩l 雩自己黪适耱方彝h 霹，羁藏惑慧 倾向选撵经过信息素强度较巍的路径。菜一路径t 走过的蚂蚁越多，剐后来者选择该路 径的概率就越大，从而表现出了一种信息正反馈现象。 自1 9 9 1 年意大利学者m d 丽g o 首次提出了蚂蚁系统( a n ts y 呶撇，简称a s ) 开创了 蚁群优饯葵法研究的先秀1 1 9 】。_ l 魄蓐，经d c 畦g o 渊。蕊，s 蛀i t z l e ，琢，o s ，b i l 鼬晦g 锄硼e l 垂咎 等多彼攀蠹静发展，飙鹚簸系绕( a ms y s k 覆a s ) 嚣始，先螽有a 蝣q ! 1 2 a l 、姣群系统( a 娃t c 0 1 0 n y s y s c c m a c s ) 口、最大最小蚂蚁系统删姒一m i n a s ，h 州a s ) 戳烽，1 9 9 9 年d 谢喾0 在这些改避 的基础一l 提出了蚁群优化( a n tc o l o n yo 州m i z a l i o n ) 的通用框架咧，使之有 更坚实的基础和良好的性熊，其应用范围也由髑p 拓展到q a p 、车间调度、交通路由、 资滚分粼、整着色、大鬟骥熬残毫路设谤、遴谖弼终孛豹赣壹瓣透疆及受载平鬻等弱鬟 l 粥，】。砸因为如此，为进步促进世界范围内栩关领域的研究工作，难e e 进化计算会 刊于2 0 0 2 年8 月出版了蚁群优化算法特刊，襁其中以蚁群算法的成功应用领域一一离 散优化问题求解为重点，发寝了许多优秀的研究论文，集中体现了蚁群算法研究和应用 领域鹣成瑰进震嘲。 鑫1 9 9 9 年起，每隔两肇魏要在眈翻对鹣稚锫塞尔举行一次蚁群算法方面专门魏潮 际研讨会，2 0 0 6 年9 月4 号刹7 号第五届蚁群优化与群智能国际研讨会又将在比利时的 布鲁塞尔控开帷幕。会议的目的是将有着不同必趣爱好的研究人员和实践者聚在一起， 第l 章绪论 研究蚁群优化的本质及实现模式，涉及的学科领域从生物学到物理学、工程学、和计算 掇裂学。宅标志罄蚁饕算法豹研褒已经褥到了国骣上的广泛支持。疆| 寸会体现了蚁群算 法研究和应用的最新成果与研究方向，对推动蚁群优化算法的统一发展做出了骥要贡 激。 1 2 3 设计模式豹研究现状 设计模式( d e s i 驴p 删啪) 的恿想的最初起源不是软件领域，而是建筑学。c 晡蚍鳢i b e r 越e x 秘d 嚣说过：“每一个模式攒述了一个在我织躅强不羝重复发生豹翊遂，以及改羯 题的解决方案的核心。这样，你就能一次又一次地使用该方案而不必做熏复劳动。”他 豹愚鏊惫露群逶掰予瑟两瓣象竣诗模式，哭是在瓣自对蒙靛释决方案量，我爨霜) l 重象窝 接口代替了墙壁和门窗。两类设计模式的核心都在于提供了相关问题的解决方案。 1 9 8 7 年，w a 坩c 硼l l i l 礓盎锄和k 州b e 矗便焉s m a l l t e l l l c 来设计用户界面，纯稍用 a i e x 如d 料的方法描述了5 个模式来指导使用s m a l l 招l k 的初级程序员，并谯o o p s l a 8 7 会议上发表了论文口卯，它标志着软件界第一次系统地引入了m e x 黼d e r 的模式思想，但此 糖豹软髂模式仅仅铮对嚣淘对象程序竣谤，瑟且囊予s 棚l t a l j 【语言豹威月规模小和这 魑模式本身的局限性，并没有引起软件界的广泛踅视。 不久，嚣融e 神l i 鼯湃始编写e + + 习馁耀法豹霉录，势在1 9 9 1 年窭敝? 文献浏。它 所描述的习惯用法是抽魏层次比较低的面向对象设计模式，但是凼于c + + 语言的广泛流 行，文献f 3 缔对予编程模式的阐述深深逢影响了大毹进行磷向对象程序设计的设计者和程 序员。 1 9 9 0 年到1 9 9 2 年，g a 蛐a 、h e l m 、j o h i i s o n 和、，l i s s i d 船编碍了一本对模式工作者 影昀深刻豹书d 蠕i 驴期觚：e l 髓搬噍so f r c 璐曲l e 嗵e c t 撬锄自e ds o 蠹蹦瞄( 设计摸 试：可鬣用面向对象软件的基础) 。后来，人们把他们称为g o f ( g a n go ff o l 。g o f 编著豹謦被定义葳为一令“里程辩”，终者在这零每孛将设诗摸姣豹愚憋应用于软箨设 计描述了收录和描述设计模式的个结构。并收录了2 3 个设计模式，在这些模式的基 箍上提溺了面向对象策臻及方法的原羽。觚琵人们对设计模式的矫究上舞到理论阶段。 在1 9 9 3 年8 月，k e n lb e c k 和g 扭d yb c h 在科罗投多州象办了一个会议，其中 第一个会议就是后来非常著名的。山坡缀”( h i l l s i d c 舶u p ) 的蒺础。1 9 9 4 年4 月的 - 6 - 基于设计模式的露天矿车辆调度模拟系统 0 0 p s l a 9 3 会议上，“山坡组”再次汇集到一起，策划举办第一次p l o p ( p a t t c r ni 舢目l a g e o f p r o g r a md e s i 卿会议，即有关设计模式的研究会。 1 9 9 5 年，g o f 的著作成为设计模式方面的经典，为大家广为接受并被广泛应用于多 个领域的软件构造和设计、开发处理和组织中，直到现在，每年国际上都举办包括p l o p 、 e c 0 0 p 等在内的学术会议对g o f 的设计模式进行讨论朔。 1 3 本文的主要工作及组织结构 露天矿车辆调度系统是经过国内外数十年的研究与实践，已有了一套比较完善的体 系。本文是结合一个实际的露天矿车辆调度模拟系统的开发，将蚁群算法合理地用于求 解露天矿车辆调度的最短路径问题。并采用设计模式对露天矿车辆调度模拟系统进行分 析与设计。本文主要内容与结构如下： ( 1 ) 绪论：本章主要是对课题地研究意义进行阐述，并对本文所涉及的理论与技术 及其发展的历史作简短的介绍。 ( 2 ) 基于蚁群算法的最短路径的自适应求解：本章首先建立最短路径问题的数学模 型，介绍蚁群算法的基本原理以及如何运用蚁群算法对最短路径问题进行求解。接下来 对基本的蚁群算法进行合理的改进，来克服其搜索时间长、易陷于局部最优解等缺点。 最后通过实验对蚁群算法及其改进算法进行对比。 ( 3 ) 露天矿车辆调度模拟系统的分析与设计：首先介绍系统模拟的概念、应用领域、 模拟的分类、步骤及方法。然后分析所搜集的各项数据建立系统模型。最后分析设计其 计算机模型，包括系统数据库的分析与设计。 ( 4 ) 基于设计模式的车辆调度模拟系统：本章首先对面向对象设计模式的基本概 念、计模模式的要素及其分类做一个概要性的综述，然后选择适当的设计模式合理的运 用于本文所介绍的露天矿车辆调度模拟系统。本文主要介绍f a c t o r ym e t h o d ( 工厂方法) 模式、s t r a t e g y ( 策略) 模式、1 切1 p l a t em e i h o d ( 模板方法) 模式、o b s e r v e r ( 观察者) 模式等四种设计模式。 第l 章绪论 ( 5 ) 露天矿车辆诱度模撅系统斑用：本章怒一个应用静介绍，主要是介绍露天矿车 辆调度模拟系统包括墩短路径子系统的应用流稷以及系统对释调度算法算出的调度方 案合理魏验证。 在论文的最后，对所傲的工作遴行了总结，并封未来可熊的研究方向傲了扔步探讨 与展望。 基于设计模式的露天矿车辆调度模拟系统 第2 章基于蚁群算法的最短路径自适应求解 所谓最短路径问题s p ( s h o r t e s t p a t h ) 就是在给定的起始点到终止点的通路集合中， 寻找长度最短的通路，这样的通路称为起始点到终止点的最短路径。单一目标与确定环 境下最短路问题是运筹学中经典的研究问题，有着广泛的应用背景通信、计算机、交通 运输等学科的不断发展，为s p 的进一步应用拓宽了良好的应用领域，由此而带来的s p 的 派生问题也日益增多，如多权网络最短路问题，约束网络最短路问题，不确定环境下网 络最佳路径问题等。国内外学者对此给予了广泛的关注和深人的研究。 应用蚁群算法( a n tc 0 l 佃y m g 鲥t h m ) 来求解露天矿生产中的最短路径问题，是由于 在生产过程中，某路径经常会应为意外情况无法正常通行。这就要求在调度时选择其它 不包含此路径的最短路径。传统的算法通常需要重新建立路径进行计算，耗费大量时间。 而蚁群算法求解最短路径的过程决定了它不必重新计算，而是在计算结果中找出相应路 径即可，进而提高了生产效率。 2 1 蚁群算法 2 1 1 蚁群算法的诞生 蚁群算法是由意大利学者m d 嘶g o 等人于1 9 9 1 年首次提出。蚁群算法的诞生是从对 自然界中真正的蚂蚁群体的观察而得来的。蚂蚁这类社会性动物，虽然个体的结构和行 为极其简单，但由这些个体组成的整个群体却表现出极其复杂的行为特征，整个蚂蚁群 体表现为高度机构化的社会组织，他们通过有组织的协调分工，在许多情况下能够完成 的复杂任务要远远超出单个蚂蚁所具有的能力。 蚂蚁的觅食行为可以说是蚂蚁群体行为中的一个最重要且最有趣的行为之一，在蚂 蚁寻找食物时，它们总能找到从食物源到巢穴之间的一条最优路径，并能随周围环境的 变化而变化的搜索出新的最优路径。这是由于在其高级形式的社会行为不断发展的过程 中，蚂蚁获得了特有的控制自身环境的能力。蚂蚁有着奇妙的信息系统，其中包括视觉 信号、声音通讯、和更为独特的无声语言，即包括化学物质不同的组合、触角信号和身 体动作在内的多个征集系统，来策动其他个体1 3 叭。当蚂蚁们在食物源和其巢穴之间 第2 章基于蚁群算法的最短路径自适艨袋解 爬行的时候，能够沿途释放出一种叫做信息素( p h e r o m e ) 的挥发性化学物质，同时 墩就形成了一条倍想素孰迹。两这秘镲息素豹存在及其强发也能够被其袍蚂蚁掰感知。 瓣簸总是簇蠢选餐经过售惠素强菠较甏瓣路径。菜一臻经上走遘静鹅觳越多，樊| j 瑶来者 选择该路径的概率就越大，从而表现如了一种信息正反馈现象。 为了研究在收约束条件下蚂蚁的这种觅食行为，d e n e u b o u r g 等人曾提出了著名的双 支桥实验p 3 删。蚁穴和食物源被一座双支桥所分隔，桥的两个分支的长度相同飘没有信 爨素。羁致垂瘗：琢凌食物和巢穴之霾建褥，弱霹记录下务令辩鬻蚂蚁选择秀令零鬻分支 酌比例。经过初始斡个短暂的振荡阶段后，所有盼蚂蚁锻终选择了沿着圆一条分支寻 找食物。 在上述的实验中，初始在两条分支路径上没有任何信息豢。这样在开始时蚂蚁是以 等概率条件下选掭蹰条路径。且由于上述试验仅仅持续了大约一个小对豹时间，信息素 浆挥发量菲零夸，掰黻茸不考虑绩意索瓣挥发。经遂菘戆豹一令震荡嚣，越来越多豹蚂 蚁选择其中的一条路径寻找食物源。豳予蚂蚁是在爬行的过程中释放信息，因此较多蚂 蚁选择的那条分支上也就遗留了更多的信息素，从而更多的蚂蚁选择了这条路径。试验 表明，在某一时刻蚂蚁选择一个分支的概率取决于这个分支上残留的信息素的总蹙，而 信患素魏慧量与缀邋这一分支豹羯毅数爱残歪跑。 假设一个分支上的信息素与过去段时间从这个分支道桥的蚂蚁数量成碱院( 不考 虑信息素的挥发) ，在某一时刻一只蚂蚁选择一条分支的概率取决于曾经经过此分支的 蚂蚁的总数。曾经缀过这一分支的蚂蚁数越多，蚂蚁选择这一分支来寻找食物源的概率 瞧藏莲毫，反之亦然。d c 粒u b 舶嘤等刚入矛发了一个镶惩索摸型，它躲行为岛试验戆 瀵察+ 分吻合。设a i 釉b i 是第i 只蚂蚁过耩后已经走过分支a 与分支b 豹蚂蚁的数量， 则第i + 1 只蚂蚁选择分支似b ) 的概率如公式( 2 1 ) 所示； 只。万尝鼍皇i 。l 一岛 ( 2 1 ) 。氆+ ) 4 g + 置) 8 4 参数珏决定选择公式( 2 1 ) 的菲线经程度，当n 僵充分天的时候，鲡采一个分支的 信息素比另一个分支稍稍多一点，那么后续的蚂蚁选择经过这条分支的概率就会远大于 基于设计模式的露天矿车辆调度模拟系统 另一个分支。参数k 表示对未标记的是分支的吸引力程度。k 值越大，就有越多的信息 素使选择非随机化。 用同样的方法，很容易地可以将上面的双支桥实验修改成两个分支不等长的情况， 同时需要将公式( 2 1 ) 做一些调整以适应新的情况。在这里，蚂蚁释放信息素的机制和 上例是一样的，因此最短的路径更容易地被经常选中。最先到达食物的蚂蚁选择的是短 的路径，当它们返回时，在最短路径上会留下更多的信息素，这也就刺激着更多的蚂蚁 去选择这条最短路径。在本例中，初始的波动对整个过程的影响被大大地降低了。很显 然，上述的过程是一种分布式优化的过程，每一只单个的蚂蚁仅仅做出了一点点贡献。 有趣的是，尽管在理论上单个的蚂蚁可以找到一个解( 例如发现巢穴和食物之间的一条 路径) ，但只有整个蚁群可以表现出来。发现最优解”的性能。在某种意义上，这也是 蚁群所表现出来的最重要的性质旧。 2 1 2 人工蚂蚁与真实蚂蚁 为了解决一些工程实际中的优化问题，蚁群算法提出了人工蚂蚁的概念。人工蚂蚁 具有双重性质，一方面，它们是真实蚂蚁行为的一种抽象，通过对真是蚂蚁行为的观察， 将蚁群觅食中最为关键的部分赋予了人工蚂蚁，使它们可以像真实蚂蚁那样跟踪信息素 的轨迹以寻找到最优路径；另一方面，由于所提出的人工蚂蚁是为了解决一些工程实际 中的优化问题，因此为了使它们解决问题更有效，人工蚂蚁也可能具备了一些真是蚂蚁 所不具备的本领口羽。 由于人工蚂蚁的大多数行为特征都来源于真是蚂蚁，所以它们拥有以下共同特征： ( 1 ) 一群相互合作的个体 和真实的蚁群一样，蚁群算法的主体由一群并行的、不同步的实体构成，彼此之间 进行全局的协作以找到一个针对具体问题的解。尽管单个的人工蚂蚁可以找到一个解决 方案，但高质量的解决方案必须是整个蚁群中通过协作产生的结果。它们的协作方式为： 在访问过程中并行地读写问题的状态。 ( 2 ) 共同的任务和完成任务采用的移动方式 第2 章基于蚁群算法的最短路径自适应求解 人工蚂蚁和真实蚂蚁之间一个共同的任务就是寻找连接初始( 巢穴) 和目标( 食物) 之间的最短路径( 最小代价) 。真实蚂蚁只能通过相邻区域的状态进行，人工蚂蚁也是如 此，只是在针对具体问题时所表述的状态和相邻的定义会因问题而异。 ( 3 ) 通过使用信息素进行个体间的间接通信 和真实的蚁群一样，人工蚂蚁也在修改它们所处环境的某些因素。真实蚂蚁在爬行 过程中释放一种化学物质，称之为信息素；人工蚂蚁则改变在问题状态空间中存储的数字 信息。这些信息记录了蚂蚁当前和历史的表现，任何一只蚂蚁都可以获取状态，然后进 行作息的读写。作为比较，我们称这种数字信息、为“人工信息素轨迹”，这条轨迹是 所有人工蚂蚁之间仅有的且是唯一的联系渠道。这种刺激形式在利用已收集的知识方面 起到了重要的作用，主要是以函数的形式( 参数为整个蚁群过去的情况) 修改所得的路 径。通常在蚁群优化算法中，引入了挥发机制，定期地修改信息素信自、这来源于真 实的信息素的挥发。信息素的挥发使得蚁群可以慢慢地忘一记历史的信息，从可以搜索 新的方向，而不被过去的决定所羁绊旧。 ( 4 ) 均具有正反馈 真实蚂蚁依靠在最短路径上堆积越来越多的信息素来吸引更多的蚂蚁沿此路径前 进，而更多蚂蚁沿最短路径行进的同时又释放更多的信息素，进一步加强了该路径的吸 引力，形成了所谓的正反馈机制。蚁群算法中同样借鉴了这一机制，在蚂蚁构造解以后 会通过质量函数进行评估，好的解得到较多的加强，使下一次迭代中具有更强的吸引力； 不好的解被加强的程度较弱或者不被加强，由于信息素挥发而逐渐失去吸引力，即所谓 的正反馈机制。正反馈机制类似于“雪球效应”，越来越多的蚂蚁被吸引到某一路径上， 这对算法的收敛起到了至关重要的作用。但单纯的正反馈也有副作用，当蚂蚁发现的解 是局部最优时，大量的蚂蚁会被吸引到此路径上，阻碍了更优解的发现，导致算法出现 搜索停滞现象【4 3 】。 ( 5 ) 信息素的挥发机制 真实蚂蚁在其活动中所散发的信息素具有挥发机制。同样的，人工蚂蚁也存在此机 制。信息素挥发机制使人工蚂蚁不受过去经验的过分约束，有利于避免算法的早熟。 ( 6 ) 不预测未来状态概率的状态转移策略 基于设计模式的露天矿车辆调度模拟系统 和真实的蚁群一样，人工蚂蚁的状态转移策略只是利用了局部信息，并没有预测未 来的状态，因此转移策略在时间上和空间上是完全局部的，它既是一个由问题状态所表 示的函数，也是一个由过去蚂蚁引起的环境局部改变的函数。 人工蚂蚁同时具备一些真实蚂蚁所不拥有的性质： ( 1 ) 人工蚂蚁存在于离散世界，它们的移动导致了离散状态的变化； ( 2 ) 人工蚂蚁具有一个内部状态记忆该蚂蚁过去行为； ( 3 ) 人工蚂蚁释放的信息素是蚂蚁建立的问题解决方案优劣程度夫人函数； ( 4 ) 人工蚂蚁定时释放信息素是一个独立的问题，通常和真实的蚂蚁行为没有关 系。例如，在很多算法中，人工蚂蚁仅仅在发现了一个解之后才进行信息素的修改： ( 5 ) 为了提高整个系统的性能，人工蚂蚁被赋予了如前瞻性、局部优化、回溯等其 它特性。 2 2 蚂蚁系统 a s ( a n ts y s t 锄) 是d o r i g o 等人提出最早的，也是最基本的蚁群算法。为了说明蚂蚁 系统建立的模型，首先建立最短路径问题的模型。设网络g = ( n ，e ，w ) ，其中n ，e 分别 为图g 的节点和边的集合，w 为图g 的权。要求找出两个指定节点间的一条权值和最小 的路径。 引入以下记号： m 一蚁群中蚂蚁的数量； n 一无向图的节点集合； 氐一节点i 与节岗之间的距离( 玛= l ，2 神； t 1 ( t ) 一t 时刻边( i j ) 的能见度( 常量) ； 甸( 1 ) 一t 时刻边( i j ) 上的信息素强度； 缸# 一蚂蚁k 在边( i ，i ) 上留下的单位上度轨迹信息素量； p 日、t ) 一t 时刻蚂蚁k 的转移概率。 第2 章蓦于蚁群算法的最短路径自适斑求解 在初始时刻，各条路径上的倍息素强度相等，设t i i ( o 即( c 为常数) 。蚂蚁k ( 1 产l ，2 ，神 程运动过程孛，缀据各条路径上瓣羡患豢强疫决定其转移熬方爨。禁瑟表蛐珏国产l ， 2 ，m ) 是用来记录蚂蚁k 当前所走过的节点并能根据蚂蚁k 的移动动态的做出调整。 掰为在簸短路径瓣零释巾，经过翡苇熹楚不会被褥次经遥豹，辑黻翳觳是苓兔诲簿次经 过禁忌袭中的节点的。在一只蚂蚁的一次循环结束后，这只蚂蚁所建立的禁忌表即为它 所建立的解决方案。在搜索的过程中，蹋蚊选择器条路径的概率与各条路径上酶信息素 强度和扇发信息肖关，如果用如k ( t ) 来表示t 时刻蚂蚁k 由带点i 移动到节岗的状态移动概 犟，其假如公式( 2 2 ) 所乐： 彤彩= r ；缪孵缪 r ：叩：似 疆重b 柑吒 o j 酬洲e d t ( 2 。2 ) o t 氟l s e 其审，a l l o 獬盎秀羁缎象在辩猁胃激转移豹繁煮，a l l o w e 蠡= n 啦b 魄。谨、多为调节 倍息素强度t 和启发式倍息f i 相对重要饿的参数。n 越大蚂蚁越倾向与选择信息綮强度 高的路裰。蠡越大，该状态转移概率越接近子贪心规剜。f l i j ( t ) 为启发函数，其值与南 成反比，d # 越小，则i l # ( ) 越大，p 垆( ) 也麟越大。 为了使信息綮的强度不至于过多的残留，信息素的强度随时间的推移而逐渐挥发。 建参数l 一鼬( o ，1 ) 袭苯痿塞索挥发援度，当经过了次獯琢之后，务条路径上豹信 息素强度相应的做出调熬： 巧( f f + 1 ) = 鳊( f ) + 勺( f ，f 十1 ) ( 2 矗勺积f + 1 ) = 矗蝣辑f + 1 ) 穆4 ) - l 其中，鲰i 氇t + l 袋示蚂蚁在氇t + 1 ) 辩麴留程路径( 掰) 上的傣怠素强度。关予篷勺氇t + 1 ) 的 大小，目前有三釉不同的算法模裂： ( 1 ) a n t d e 燃时s y s t 啪模型 基于设计模式的露天矿车辆调度模拟系统 根据公式( 2 5 ) 可知，当蚂蚁k 经过路径( i j ) 时，a t - 删t ys y s t 锄模型，释放在此 路径上的信息素量与路径的质量无关，其值为每单位长度q ： 咖删= 侣鬻暾绁雅o 亿s ， ( 2 ) a n t 删t ys y s t e m 模型 在a 呲q l 均n t i 哆s y s b 锄模型中，当蚂蚁k 经过路径( 硒) 时，释放在此路径上的信息素 量释放的信息素量随着节点间距离( d i i ) 的不同而变化，其值如公式( 2 6 ) 所示： f ：( ，r + 1 ) ：j 詈第k 只蚂蚁经过路径( l d ( 2 6 ) 露( ，r + 1 ) = 由一一”“ ( 2 6 ) l o 否则 ( 3 ) a n t c y d es y s t c r n 模型 公式( 2 7 ) 所示的是a n t - c y c l e s y s 自锄模型信息素的更新策略，公式( 2 7 ) 与( 2 6 ) 的 区别在于它们的更新时机不同，a m q l 培n t i t ys y s i e m 模型是在蚂蚁k 完成对路径( 幻) 搜索 后，进行信息速的更新，而a m c y c l es y s t e i 模型是在蚂蚁k 完成一次路径搜索之后进行 信息速的更新： f ：( f ，+ 1 ) ：j 詈第k 只蚂蚁经过路径( f ，力 ( 2 7 ) f ：( f ，+ 1 ) = 厶1 一”7 ( 2 7 ) 【o 否则 三种模型的本质区别在于：前两种模型中，利用的是局部信息，而后者利用的是全 局信息，因后者在算法性能方面优于其它两者，所以通常采用a n t - c ”l es y s t e m 作为其 基本模型。a n t - c ”i es y s t c i n 模型又称为蚂蚁系统