（计算机应用技术专业论文）基于模糊规划和智能算法的飞机地面作业调度问题研究.pdf

摘要 飞机地面作业调度问题是当今民航业面临的一个热点问题，飞机数量的增加导致了 大型枢纽机场飞机地面作业量的急剧增加，只有高效快速地完成飞机地面作业，才能 确保飞机准时准点起飞，从而避免飞机延误或减少延误时间。飞机地面作业具有涉及 到的资源种类多，作业时间随机型、航班类别的不同差异较大等特点。本文在详细分 析飞机地面作业内容的基础上，重点对客舱清洁工调度问题和地面不同作业资源的凋 度问题作了研究。 本文首先介绍了当今调度优化问题领域常用的一些方法，对其中一些方法的特点做 了分析。然后对飞机地面作业内容以及工作流程做了较为详细的介绍。紧接着重点研 究了1 i 机客舱清洁工的调度问题，根据实际生产情况提出了基于时间控制的调度方法， 并作了实例分析。接下来，在文章中分别介绍了本文主要用到的模糊规划方法与粒子 群优化算法，并对粒子群优化算法做了标准函数测试分析，给出了实验数据，验证了 粒子群算法的些特性。最后，结合实际生产，提出了以模糊数表示作业时间，用基 于不同时间窗的提日口拖期调度方法建立模型，利用粒子群优化算法对模型进行求解的 解决飞机地面作业调度问题的方法，并应用该方法进行了仿真分析，仿真实验结果表 明该方法是解决飞机地面作业调度的一种可行的方法。 关键词：飞机地面作业，清洁 ：调度，模糊规划，粒子群优化算法，提前拖期 a b s t r a c t w i t ht h ei n c r e a s e m e n to fa i r c r a f t s ，h i n g ea i 印o n sa l lo ft h ew o r l da r ef a c i n gt h e p r o b l e m so fm o r ea n dm o r eh e a v i e rw o r ko fa i r c r a f t sf o u n do p e r a t i o n h o wt op r o m o t em e 、v o r ke m c i e n c ya n dr e d u c et h ed e l a yo fn i g h t si sah e a tt o p i ct o d a y a i r c r a rg r o u n d o p e r a t i o ns c h e d u l i n gp r o b l e mi sac o m p l i c a t e dp r o b l e m ，w h i c hi ss u q e c t e dt om a n y d i f r e r e n t t y p e so fr e s o u r c e s ，a n dt h ep m c e s s i n gt i m ei sw a v e dd u et od i 仃e r e mt y p e so fa i r c r a r so r n i g h t s a i r c r a rg r o u do p e r a t i o ns c h e d u l i n gp r o b l e m sa r es t u d i e di nt h i st h e s i s ，t h ec a b i n c i e a n e rs c h e d u l i n gp r o b l e ma n dt h eo t h e rk i n do fg r o u n ds c h e d u l i n gp r o b l e ma r es t u d i e di n r e s p e c t i v ew a y s t h r o u 曲t h ei n v e s t i g a t i o ni nb e d i n ga i 叩o r t ，t h e c o m e n ta n dw o r k n o w so fa i r c r a f t g m u n do p e r a t i o na r eg i v e ni nd e t a i l t h ec a b i nc l e a n e rs c h e d u l i n gp r o b l e mi s s t u d i e d t 1 1 r o u g ht h eo p e r a t i o n a lr e s e a r c hm e t h o d s ，d i f f e r e n tm e t h o d sa r ea n a l y s e du n d e rd i 艉r e n t s i t u a t i o n s t bs o l v et h eg r o u n do p e r a t i o ns c h e d u l i n gp m b l e mo fa i r c r a r ，t h em e t l l o do f e a r l i n e s sa n dt a r d i n e s ss c h e d u l i n gp r o b l e mw i t hd i s t i n c td u ew i n d o w sa r ei n t r o d u c e d i n o r d e rt od e n o t et h eu n c e r t a i np r o c e s s i n gt i m e ，f u z z yp m g r a m m i n gm o d e l sf o rt h et 1 1 r e e k i n d so fs c h e d u l i n gp r o b l e ma r ee s t a b l i s h e dh e r ea n dt h ep m c e s s i n gt i m ea r ed e n o t e db yt h e 如z z yn u m b e r s b a e s do nm ea l g o r i t h mo fm a x i m i z i n gt h em e m b e r s h i pf h n c t i o no fm i d d l e v a l u ea n dm ep a n i c l es w a r mo p t i m i z a t i o n ，t h ef u z z yp m g r a i l l m i n gm o d e l sa r et r a n s f b r n l e d i n t od e t e r m i n i s t i cp r o g r 邶m i n gm o d e l s ag r e a td e a lo fs i m u l a t i o nr e s u l t si s g i v e nt o i l l u s t r a t et h ee 伍c i e n c yo f m ep r e s e n t e dm o d e l sa n dt h eo p t i m a la l g o r i t h m s k e yw o r d s ：a i r c r a rg r o u n do p e r a t i o ns c h e d u l i n g ，f u z z yp r o g r a m m i n g ，p a n i c l es w a r m o p l j m i z a t i o n ，e 丁 中叫民用航空学院坝+ 学位论文 1 1 引言 第一章绪论 优化是指一个从组解中提取山最优解或最适应解的过程。优化方法涉及的工程领 域很广，问题种类与性质繁多。归纳而言，最优化问题可分为函数优化问题和组合优化 问题。其中函数优化的对象是一定区阳j 内的连续变量，而组合优化的对象则是解空间甲 的离散状态。函数优化问题通常可归纳为：令s 为月“上的有界子集( 即变量的定义域) ， f ：s _ + 月为n 维实数函数，所谓函数在s 域上全局最小化就是寻求点爿。s 使得 ( 。) 在s 域上全局最小，即x s ：，( 。，。) ! ，( x ) 。对函数优化的讨沦通常以无约 束问题为主。组合优化问题通常可描述为：令n = “，s ：t ，) 为所有状态构成的觯空间， c ( 一) 为状态的对应的目标函数值。要求寻找最优解s + ，使得v q q ，c ( s ) = m i n c ( s ，) 。 优化技术是一种以数学为基础，用于求解粹种工程问题优化解的应用技术。作为一 个重要的科学分支一直受到人们的广泛重视，并在诸多工程领域得到迅速推，和应川， 如系统控制、入工智能、模式识别、生产调度、v l s i 技术、计算机工程等等。实现生 产过程的最优化，对提高生产效率与效益，节约资源具自重要的意义。需要指出的是， 最优化分为最小化和最大化，由于两者可蚍互相转化，凼此一般所指的最优化仅指最小 化。优化算法是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规 则来得到满足用户问题的优化解。 调度是为了实现某一口的面对共同使用的资源实行时唰分配，一个调度满足问题( 调 度问题) 是一个约束满足问题。他的一个状态是集台r 和t 问的二元芙系。其r r lr 是 资源的集合( 资源卒问) ，t 是任务的集合( 任务空间) 。调度问题的定义很简单，但调 度问题本身并没有那么简单。调度问题可以况无时不有，兀处不再。它涉及到制造、k ， 交通运输业，经济金融业，管理领域等。现实世界中的调度问题各式各样，如t i m et a b l c s c h e d u l i l l g ( 时f 刊表调度) 、c r c ws c h e d u l i n g ( 人员调度) 、j o bs h o ps c h c d u l i n g ( 车间作业 调度) 等。整个人类社会的进化发展过程也是一个调度过程，其最终目标是一种低能平 衡态。调度和优化有着密切的关系，优化是调度的日的，l m 训度义是优化的一种具体表 现形j 。要想对某一问题进行成功的调度，势必要运用先进和可行的优化方浊。所以我 们常称调度问题为优化调度问题。调度问题研究方法所涉及的学科非常广，它们包括： 人l 智能、专家系统、进化计算、运筹学、优化技术等。 随着准时生产制，即儿t ( j u s t i n - t i m e ) 在同本获得成功之后，以准时生产为目标的生 随着准时生产制，即j r l ( j u s t i n _ t l m e ) 在几本获得成功之后，以准时生产为目标的生 中陶睫媚航空学院礁t 学位论文 间调度问题的方法与规则库的具体实现，分析了各种规则与性能指标的关系，对如何 台理遗逸麓攘爨挺基了建议：为了撬褰麓澍褒瘦瓣矮量，文拶l 邋过分毒厅撬羯时溜与巍令 作、监的调度决策间的关系，提出了种比较复杂的规则。 总的_ 柬说，启发式规则直观、简单、易于实现。但是近十年来的研究成果表明并不 存在一个全局最优的调度规则，他们静有效性依赖于对特殊性能需求的椿缓及生产条 牟。它是弱胬饯讫方法，难戬褥到会弱侥 乏结莱，并显不能霹褥蜀酶结果避 亍次 芄幢 的定量评估，顾客需求的个性化及鼹求企业响应市场的敏捷性，往往在生产加工过程 中加入了熙多的不确定性及复杂性约荣，寻求调度最优算法本身是一个n p 完全问题， 这些饺褥蕊手援粼静谖矮思想在某些方瑟渍足不了敏捷纯割遣黪要求。 3 、系统仿真的方 虫 基予仿真的方法不单纯追求系统的数学模型，侧重对系统中运行的逻辑关系的拙 透，笺够对生产调凄方案进行磁较，分褥系统簿动态往麓。并遮择系统的韵态结秘参 数，由于强示系统的翦杂性，很难用个精确的解析模型来进行描述和分析。而通过 运行仿真模型来收集资料，则能对实际系统进行性能、状念等方面的分析，从而，能 对系统罴耀合适豹接剿溺凄方法。仿粪方法最早拔用来终为测试调度窟发式藏建及分 派规刚的工具。后来，人们发现，通过将简单的优先权规则遴行组合，或髓一个简单 的优先权舰则将一些启发式规则进行组合，这样的调度优于单独的优先权规则。文【j 中提出了纂于纯仿真模型的酾度方法，即在一个较短的时闽段内用仿真来评价一个分 派鬟澍集。文h l l 运瑟缝仿真穰鍪，阂辩解决f m s 中作、蓝调_ | 妾秘搬运工具的瓷源努配蠲 题；文【l 引中提出了一种混合的仿真模型，用于分析和设计具有缓存的不可嚣生产线问 题。 基于缝仿真方法存在热下凡个勰邈：1 ) 鉴于蔟试验瞧，缀漆对生产调发鼗理论徽 出贡献：2 ) 应用仿真游行生产濒纛的费用很高，不仅在于生产谪度的计算时间上，而 且在于设计、建立、运行仿真模型的商费用上；3 ) 仿真的准确性受编程人员的判断和 技巧的限制，甚至很商精确度的仿舆模型也无法保证通过实验总能找到最优或次有的 调度。 4 、基于离散事件的解析模型方法 出于调度系绞一般可以香藏一类典型的裹散褰传系统，因此 巧以羁垂舅究褒数事件系 统的解析模型和方法来探讨调度问题，如排队论、极火极小代数模型、p e t r i 阿等。请 度中的排队论方法是一种随机优化方法，它将每个设备看成一个服务台，将每个作业 作为一个顾客。作业的各种复杂的町变特殊性及复杂的路径，可通过将其加工时间及 裂达时蠢缓设为一个涟橇分毒来遂行攘述。文h 3 畸对f m s 中一类蒋臻兹d 嚣蚤s ，秘爱 了极大代数方法对其进行建模，并i j | 行了系统的稳定性分析。文1 1 4 l 针对有阻塞的这类 调度问题，给出了调度闩标函数的具体形式，指出它不是凸函数，分别对个变量以 中固民糟航空学院硕士学位论文 应值( f l t n e s sv a l u e ) ，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子就追 涟奎藤款激後粒子在鳃黛闽中疆索。p s 0 镑始化为一舞莲祝粒予蘧辍鳃) ，然螽逶过迭 代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来殿新自己。第个就是粒 子本身所找到的最优解，称之为个体极值，另一个极值是整个种群目前找到的晟优解， 称之为全髑缀值。 其中，遗传雾法、虫蟊姣算法、粒子群算法遮三耱算法也逶常翊分蟊智能後佬算法鲸 范畴。 6 、纂予a 叠e 珏l 的滤发方法 近年来基于知识的智能调度系统和方法的研究敬得了很大的发展。基于知识的调度 方法使用专家系统自动产生调度。它是将传统的调度方法与基于知识的调度评价相结 合的方法。在八十年代矮期，几位学者先后开展r 基于调度系统处于不同的状态，采 蘑不丽酶瀵度鲠刘策酶的动态谖度疗法静醑究。冀方法是：龟支穗菜些活动发生静资 源条件具备时( 称为决策点) ，根据系统当时所处的属性状态，决定采取何种规则，确 定或选择活动发生的顺序和时间，即状态指导的智能调度方法。文【l6 】用黑板模型来组 织霹维妒动态数据疼，在趣划层矮数学疆划求甥，在调瘦控翱艨爰基于襄识茨调凄方 法。文【2 鄙中介绍了我国清华大学自动化系设计开发的具有机器学习能力的智能规则调 度系统。 总的来说，包括锷髓调瘦专家系统、基于稽能搜索的方法及基于多代理技术 ( m u l t i 壤g e n ts y s t e m ) 静合俸求躲静方法等。其中，智麓谎寝专家系统是入工智麓应 用的体现，由于专家系统中知识获取和推理速度这两个瓶颈，使得神经网络逐渐被采 用。基于多代理技术的台作求解方法是较新的智能调度方法，它提供了一种动态灵活、 抉速鸹应豢场戆生产调发壤铡，通过饯理( a 譬黥t ) 之囊豹台馋以及控剃系绞携调寒完 成生产任务的调度。在这种方法中，在a g e n t 内部也可采用蘩于规则及智熊推理相结 合的混合方法。文【2 6 j 中提出了综合运用多代理机制与规划调度实现敏捷化制造车间生 产过程动态调度的方法。 磊要撂窭静是，蓥予a 譬e n t 戆调鹰方法不蘑予筵它方法，它主婺镧重予系统俸系结 构的设计，便于分布式调度问题的求解。 7 、基予终衷程痔熬方法 这类方法把一个问题的解决明确划分为两个方面：一是待解决问题中的约荣的准确 定义；二怒关于算法和启发式的选择、排序、删除的求解决策过程。应用于实际的调 度问题，熬于约束的程序设计有助予生成精确、赢效、可行、可扩充的调度系统。i l o g s l o v e r 霸s c 魏e 菇l e 是舒对资源分配、诗翊饔谲度游题设谤夔e + + 库。l 己0 g 产晶是当 前最著名的用于求解商业领域中约束问题的工具。它可以减少复杂冗余的编码，缩短 产品生产周期。其跨平台的可扩充组件，允许用户求解各类的商业问题。 中国鼠糟航空学院硕学位论艾 2 。7 小结 整2 2 飞橇鳃霹俘韭诱发系统框袈 本章酋先介绍了飞机地面作业的概念，之后分析了研究飞机地面作业资源调度的意 义，接着根据首都机场地面作业实际运营情况，分析介绍了飞机地面作业的主要工作 遗容及工捧滚翟，最磊绘出了飞投筑嚣馋韭调度系绞框絮图。 中国民m 航空学院锨卜学位论文 第三章清洁工调度闰题 嚣究 3 1 清洁工调度问题的研究目的及意义 在清洁队员工资源有眼的条髂f ，懿俺合理安撵工人的上班辩阊，使褥p 能有效缝 利用清洁队人力资源，均衡工人工作负荷，又能满足航班起降高峰时间对清洁队的需 求，这些都有利于提高航班正点率，敬善清洁服务的质量。国内机场、航空公司清洁 敬静编缀簿疆，褒在基本是稷提缀验编蓑 魏，王久嚣上臻露阚安舞 ，较长辩闺痰没 有什么变化，采用分组轮换的办法。疆然现在的倒班方式是一定时间工作经验的结果， 具有一定的合理性，但随着航班生产计划的变动，由于航空运输市场动态变化频率的 加快，人_ = 】二经验式的计划方法难免不戆适应市场变化。因此，科学动态地编势 和调整 人力资源调度计划，台瑾利焉宝贵的入力资源，对于航空公司躲发展的竞肯定是有 利的，也娥科学管理的正确方向。 本章希望通过对清浩队的分组编排方案进行分析研究，利用优化技术计算清洁工值 班诗怒方寨，与理有方索进行比较，发王蹙露以改遴熬灌力，麸褥为飞瓿逡佟盐蠲囊 方法及其方案制订的数据分析做一个f i i 期研究，为机场、航空公司清洁队人力资源的 优化配置提供一个科学方法上的建议。在本章研究的问题下，清洁队人力资源的合理 配置方式，不仅仅可以节省资源，嬲盥对于满足靛班高峰对 袁洁入力豹需求，傈证航 班正点率鸯着很重要的彩哟。霹时，本章研究的方法可以应丽于其谴飞丰凡戆萄作监资 源的安排，例如车辆司机的安排、特殊设备的使用和维修计划等，因此具有定的典 型性，对憋个飞机地面作业系统资源姻优化利用，有比较重要的意义。 3 2 飞机客舱清洁作业的特点 飞机清洁工作是飞机地面作业系统中的一个工种，主要负责赋班飞机客舱的清洁工 作。当蘸，清洁工漾逶工俸管理方式主要是分缀管理，并虽按照航班任务瀚箨辊区经 安排到小组。第一级的任务派遣是调度中心把任务分配到小组。第二级安排是小组把 任务分配剐清洁工成员。第三级是各小组根据航班到达时间和安求完工时间安排作业 表。 清洁工作为飞机地蕊作业系统中涉及到员工调度阿题的一个工作项目，其工作性质 是简单作业，但是该工作的调度安排却具有很强的代表性，内容涉及到了人员分组， 上班时间划分，和选择飞机作业顺序等阉题。它热有如下特点： l 、工释豹摹一性 清洁工趋一个比较简单的工种，熟工作性质并不复杂，每个清洁工可以做任务中的 1 6 中国嫩掰航空学院倾士常位论文 任何部分工作。因此猩清洁工的安排中可以把每个清洁工番成为同质的，即在派遣 孛只有久爨数嚣兹确定，秀不具落烈每个潼滔工黪疑凝。 2 、资源的重组性和可分性 由于滂洁工的工作怒一种群体合作的工作方式，这要求每个航班任务需要多于一个 久魏集薅去完成一俘饪务。恧在具体游天委管璎模式孛，涛滂工籀互之蓠豹合作关系 不是固定的，而是根据任务的到来，根据具体的人员数目要求派遣相应数目的人员去 完成个任务。人员之间是任意组合的，每个小组合作关系可以随时被打破。 3 、搽作时闼的可控性 清洁工工作另一个特点是操作时间的可控性，即根据工作状态确定工作的强度方 式，相应的会有时间长短的变化。由于清洁工作都是由人柬完成的，而人员的工作速 度帮派逡麓久数是可以嶷纯静，这撵蚕弱静工 蕈遽凄籍会表凌为不阉豹工俸海阉，这 个特点为安排调度工作带来困难。因为在多数情j 兕下，考虑的工作完成时间长度应该 是固定的。同时，工作方式虽然根据实际的情况会加大工作强度，调整工作速度，但 这静加强矮螅工终方式不是正常匏王 蕈状态，长孵阀豹高受蕊馋会繁来其德爨问题， 因此，在实际安排中应尽量少使用这种方式。从中可以看出，问题的露标也是多方露 的。 3 。3 溥法王谖度褒状分辑 1 、结构组成 强裁潼浩工的人力资源派遣采取队稳班豹形式，一个酞出数个班组成，在一定的时 段内授入一定数量静斑。一个班由定数量的人受秘设备组成。如一个清洁搬由2 2 人 组成 2 、清浩工现在的调度情况 表3 j 现有清洁工调度排班表 班次时间人数 6 ：0 0 一1 2 ：0 0 一个壤2 2 久 6 ：3 0 一一1 2 ：3 0 一个班2 2 人 卑坍 7 ：0 0 1 3 ：0 0一个班2 2 人 9 ：0 一1 5 ：0 一个班2 2 a 中班 1 l ：0 0 一一1 7 ：0 0 两个班4 4 人 中国融用航空学院坝 学位论文 图3 1 提前3 0 分锌航班调度算法示意图 3 。3 。4 过戆靛凝饔废安撩： 设前面的- 1 个航班已经安排完毕，对航班女； 3 。3 。4 1 鲞；为一般魅骧，大数无耱妹霉求时： 3 3 4 1 1 清洁工人员的数目。( 杯准人数) ，工作时问为r 啊准人数) 2 0 中围民用航空学院硕士学位沦文 l 、计算满足人员要求( 标准人数) 最早可篓霉勿傍i i ，羹膨俺淹堪! 蜊濂溯错佶墨满；：| ! f 薹i 粤囊委龠i 翳蒸渊! i ! j 鬟引瓣龇晷算墼 羔鼙；稳姜i 蒌蠹r 蠢引羹骅i i ；i 鞋惹姒按 ；摹薯j 哇曩i 雾j 羹耋j 蔓畏夔冀； 型奎型| ；i 潲黉剩剐疑廷惹；：j i 翳蠢i 撰士f i j l 螽蘑渤腿淄惰嘣莲委薹! 篓孽薹盈i ? 庇霹稔模型 目标函数和约束条件不同，当二嚣中一个是清晰，另一个是模糊的时候，葵处理方法 也是不一样的。显然，这种模型是非对称的。其中系数全为模糊数的模型为： m a x0 7 x s ，直￥6 ( 4 ，8 ) o 其中，互5 ，0 全是模糊数 4 3 3 模糊线性规划的求解方法 模羧羧划是运筹学豹一个重要分支，己经被广泛趣应委裂缀多镶域。数学蠼划可以 描述为在些数学关系，包括等式戏者不等式约束条件下，求一个( 或一组) 黼数的极值 问题的方法。常见的数学规划有线性规划、非线性规划、多目标规划、目标规划、整数 规戈9 、多鼷规划、动态规划以及不确定规划的随机规划和模糊蠼划。随机规划和模糊规 划是分裂赴瑾随辊优化蠹霉题和模糨後纯闷题静舔大数学褒麓工其。 模糊线性规划的求解，主要的思想是运用某种数学和实际应用中可行的变换方法 将含有横糊线性规划问题化为清晰的线性规划问题求解。主要有容差法( t o l e r a n c e 如o h3 秘可戆法( p o s s 强i l i 燕oa p p h ) 嚣太类。本文瘸到熬兰要是可辘法，王趸薅可 中国民册航空学院预士学位论文 z z 攀z 强4 。2 三满意度戆隶蕊发爱鼗 l o 矿 乎 弘z l l x ( z 擘 z 擎曼x s z x z ：” z z z t 图4 3z 2 满意度的隶属度函数 如_ 簪 x ( z z s x 曼z x z 攀 1 8 ) ( 4 1 9 ) 中囝民绡肮空学院顿士学位论文 z ? sz ：”z l 鲞4 4 乏满意度麓隶攥度蘧数 4 4 粒子群优化算法( p a r t i c i es w a r mo p t i m i z a t i o n ，p s 0 ) 3 2 4 4 1 穰逡 p s o 初始化为一群随机粒子( 随机解) ，然后通过迭代找到最优解。在每一次迭代中， 墟子通过逡爨个蕊极 蠢秘嚣钵极毽寒更瑟自己。个体投僮是粒子所找到的本赛最饶鳃： 群体极值怒所找到的熬个稀群最谎解。假设在一个d 维的罾标搜索空闻中，由m 个粒 子组成一个群落，其中第i 个粒子表示为一个d 维的向量= ( 期满：，“。l bl ，2 ，m ， 帮第i 令粒子在d 缍懿羧豢空蠢中静位_ 萋：是x ，每令粒子夔燕鬟藏是一个可行瓣。褥为 带入一个目标函数计算出适应值，根据适应值的大小衡量而的优劣。第i 个粒子的”飞 雩亍”速度也是一个d 缨靛囱量，记为话= ( v 。v 。m 。) 。辽第 个粒子迄今为止搜索到 的最优位置只= ( 只。，麒2 ，p 。) ，整个粒子群迄今为止搜索到的最优位置为 疗印万蔹万：嚣窘等采耀下列公式嚣新粒子的遗废翻位置： 菇：嘛秘一嘲：v 。岫r ，( 一x 。) 忆r ：( p 州一x 对) ( 4 2 0 ) 戈“= x “+ v 甜 ( 4 2 1 ) 萁中，净l ，2 ，m ，( 扛l ，2 ，d ；学瑶因子# ，帮e 2 是 受害鼗；琏帮趣是费 于【o ，l 】之m 的随机数。【_ v 。，v 。】：v 是常数，根据具体问题设定。迭代中止条 件根据具体问题一般选为最大迭代次数或鞍子群迄今为止搜索到的最优适应值满足设 定的最小逶应阂篷。 标准p s o 模型收敛速度快，但很容易陷入局部极小，在原有的基础上，出现了几种 中固民用航空学院坝+ 学位论文 即p 6 8 观= 只x 6 p s t = x ； 4 、每个粒子的最好适应值p 6 e s t 与所有粒子最好适应值驴吲，进行比较，如果 p 6 船 驴甜，则用每个粒予的最好适应值取代原有所有粒子的适应值，同时保存粒 子的当前状态。即9 6 p s = 驴p m ，。= 。， 粒子群算法的流程图如图4 5 所示 4 4 5 测试函数 图4 5 粒子群算法流程图 本文采用r o s e n b o c k 函数作为测试函数 中国民用航宰学院碗+ 学位论文 ，( ；) ：艺1o o ( 鼽，。；) 2 + ( 。，一1 ) 2 ( 4 刀) r o s e n b o c k 函数具有一个全局极小点x = ( 11 1 ) ，其函数值厂( x + ) = o 。 4 4 6 参数设置 本文采用随机产生仞始种群，最大搜索速度取搜索空间的一半，如表4 1 所示。 表4 1 测试函数初始化表 函数搜索窄间初始化范围 v m a x r o s e n b o c k1 0 0 x 】0 01 5 x 3 01 0 0 最大进化代数g e n m a x 分别为2 0 0 0 ，1 5 0 0 ，运行次数m a x r u n 为1 0 0 次。测试 函数的维数n 分别为l o 、2 0 。初始的粒子群数为4 0 。各种p s 0 模型的参数设置如表 4 2 所示： 表4 2 各p s o 模型对r o s e n b r o c k 函数的参数设置 模型讹 w 1 c lc 2n，2 kv m a xv m n q p s 02 02 0r a n dr a n d1 0 0，1 0 0 p s 0 +2 o2or a n dr a n d1 0 0 w p s o ( 1 ) 1 4o 12 o2or a n dr a n dl o o1 0 0 w p s o ( 1 ) + 1 4o 1 2o 2 or a n dr a n d1 0 0 w p s o ( 2 ) o 9 o 42o2 o r a n d r a n d1 0 0 1 0 0 w p s o ( 2 ) + 0 9o 42 02 or a n dr a n d1 0 0 c p s o2 0 52 0 5c i r a n dc ，。r a n d0 7 0 51 0 0一l o o c p s o +2 0 52 0 5c 1 。r a n dc ，。r a n d0 7 0 51 0 0 表4 2 中，惯性权重模型w p s o 的w 0 、w 取不同的值时，分别表示为w p s o ( 1 ) 、 w p s o ( 2 ) ，r a n d 表示 o ，1 】之间的随机数，其中带+ 号的各p s o 模型表示只设最大速度的 模型，不带+ 的模型表示设定了最大最小速度的模型。惯性权重的变化采用如下公式： w ( ，) = 一( 一) 赫 ( 4 2 8 ) w 。为权重的初始值，w 为权重的最终值，t 表示进化代数。 中国民用航空学院硕上学位论文 4 4 7 仿真结果分析 表4 3r o s e n b r o c k 函数的运行结果 d i m g e n m a xm o d e l p b s ta v gm a x m i n p s o1 33 1 e + 0 2】0 】e + 0 4j oj e + 0 4 p s o + 4 5 1 0 l b + 0 41 0 0 e + 0 64 9 9 e 0 6 w p s o r l )2 6 2 1 0 e 十o l2 8 9 e + 0 10 0 0 e + 0 0 w p s o ( 1 ) + 8 9 2 8 2 e + 0 12 6 8 e + 0 30 0 0 e + o o 1 02 0 0 0 w p s o ( 2 ) 0 1 5 8 e + 0 65 5 0 e + 0 728 7 e + o l w p s o ( 2 ) + 7 3 4 7 e + 0 533 5 e + 0 60 0 0 e + 0 0 c p s o o 81 2 e + 0 4 4 18 e + 0 62 - 8 9 e 十0 l c p s 0 + 6 6 2 0 o e + 0 4 1 0 0 e 十0 6 1 3 1 e 0 s ， p s o7 2 2 0 e + 0 21 0 2 e + 0 49 1 8 e 0 4 p s 0 83 9 2 6 5 e + 0 22 5 9 e + 0 438 8 e 0 4 w p s o ( 1 ) 2 1 1 4 7 e + o i1 8 9 e + 0 10 0 0 e + 0 0 w p s o ( 1 ) + 9 3 9 5 8 e + 0 086 9 e + 0 2o0 0 e + 0 0 2 015 0 0 w p s o ( 2 ) 0 6 0 8 e + 0 49 0 9 e + 0 51 8 3 e + 0 1 w p s o ( 2 ) + 5 2 0 8 e + 0 51 2 8 e 十0 76 3 l e 0 8 c p s 00 1 5 2 e 十0 43 3 7 e + 0 5 1 8 8 e + 0 1 c p s o +6 4 3 1l e + o o1 9 0 e + 0 11 6 6 e 0 6 表4 3 对比了各p s 0 模型对r o s e n b r o c k 函数优化的1 0 0 均值、最大值、最小值。 可以得出：最大速度p s o 模型的优化效果要优于最大最小速度p s 0 模型。其中p s o 、 p s o + 、w p s o ( 1 ) 、w p s o ( 1 ) + 、c p s o + 均取得了非常好的优化效果，w p s o ( 2 ) + 的优化 效果最差。 中国民用航空学院倾十学位论文 图4 ，6 各p s 0 模型种群平均适应值的进化曲线 图4 6 显示在种群为4 0 ，维数2 0 ，进化代数2 0 0 0 ，对于r o s e n b r o c k 函数各p s o 模型的种群平均适应值的进化曲线。从图4 7 可以看出w p s o ( 1 ) + 模型的收敛效果是非 常好的，种群平均适应值和种群最优适应值都能收敛到令人比较满意的结果。 图4 7 种群最优适应值的进化曲线 图4 7 显示了w p s o ( 1 ) + 、p s o 、c p s o 模型种群最优适应值的进化曲线，w p s o ( 1 ) + 中国民用航空学院硕十学位论文 的进化效果最好，c p s o 次之，p s o 的效果最差。w p s o ( 1 ) + 进化6 0 0 代后，最优适 值就落在【o ，1 0 0 】之内，最终稳定在 o ，l 】区问内。 4 5 小结 本文介绍了模糊规划方法和粒子群优化算法，首先介绍了模糊数学的一些基本概 念，接着介绍了模糊规划的方法，并详细介绍了模糊规划建立模型的过程。之后，介 绍了粒子群算法基本模型、惯性权重模型( w p s o ) 、收敛因子模型( c p s o ) ，最后对粒子 群优化算法以r o s e n b r o c k 函数进行了测试，分析比较了最大速度和最大最小速度的 p s 0 、w p s o 、c p s o 模型。 4 l 中国民用航空学院硕士学位论文 题可以描述为：n 个工件在m 个机床上进行加工，每一个工件的加工顺序相同。问题 的目标是求n 个工件最优的加工顺序，使调度方案的某项评价指标最优化。类似的在 飞机地面作业资源调度问题中，我们可以把飞机抽象为工件，将各种地面作业抽象为 机床，每一个飞机的地面作业顺序相同。问题的目标是求n 架飞机的最优作、世顺序， 使调度方案的某项评价指标最优化。 由于在飞机地面作业时，对资源的调度有很多影响因素，我们可以把他们统称为不 确定性因素。描述不确定性信息的数学方法主要有以下几种：( 1 ) 不确定性因素服从 一定的概率分布规律，使用随机变量进行描述：( 2 ) 不确定性因素在一定的范围内变 化波动，使用模糊数进行描述：( 3 ) 不确定性因素表现为离散的值，使用离散的量来 描述。目前，使用随机变量描述不确定性信息的研究比较多，但在实际情况中，常常 很难对些不确定性信息做出概率分布规律的估计，而只能凭借经验或历史数据给出 大致的区间估计，这使得用模糊数来描述不确定信息变得十分重要。 一般的提前拖期调度问题都把任务的处理时间当作一个己知且固定不变的量，进而 考虑该任务的提前生产或拖期生产对惩罚函数的影响，但在有些情况下，提前拖期调 度问题的许多决策是在模糊的环境下判断出来的，例如目标函数、约束、决策变量等， 既不能够完全定义，也不能精确测量，因此考虑它的不确定性是合理而可行的。在实际 的飞机地面作业调度问题中，任务的处理时间一般都是非精确的，它受到许多因素的制 约，例如：作业工具性能、原材料、工作人员自身情况等诸多方面的影响，任务处理时 间的大小具有模糊性和非精确性。由于每项作业都有其自身的性质和特点，生产能力的 约束调整只能在定的范围内有效，例如某一项作业的处理时间如果少于一个固定的 值，完成对飞机的作业则是不可能的，而在能力不足时，使其处理的最长时间也不应超 过一定的值。因此，把作业时问考虑为一个模糊的区间数，只给了处理时间的某一个区 间范围是符合生产的实际背景的。所以我们采用模糊数来描述不确定的作业时间不仅方 便而且符合生产实际。 5 2 提前拖期调度模型 5 2 1 问题描述 本章研究的处理时问不确定条件下飞机地面作业提前拖期调度问题，就是在考虑飞 机地面作业时间不确定性条件下，研究地面作业时间的提前拖期调度，本章采用三角模 糊数来描述不确定的处理时间，研究带有不同交货期窗口的提前拖期问题。并且规定如 果飞机在其交货期窗口内完成地面作业所有工序，则没有惩罚；否则，无论是提前还是 拖期，都对飞机进行提前拖期惩罚。 中固民用航空学院颀士学位论文 5 2 2 定义 定义5 1 在本章如下的内容当中，定义飞机地面作业交货期窗口为作业完成时间 窗口。 在本章中，对用到的各种变量定义如下： j 航班的集合。l ，= 1 ，2 ， ) ，即航班总数为n 架； m 地面作业工序集合。m = 1 ，2 ，晰 ，即地面作业项目有m 种； 只地面作业时间。地面作业j 对航班i 的作业时间，包括作业车辆行驶到 飞机所在停机位时间、预备时间、作业时间等，是在一定区间变化的不确定量， 本文采用三角模糊数来表示； s ，地面作业j 对航班i 的作业开始时间，同上也为模糊数； z ，地面作业j 对航班i 的作业完成时间，同上也为模糊数： c 航班i 的地面作业完成时间。由于各作业时间模糊性，这里的值同上也 为模糊数； k ，f ，j 航班i 的作业完时间窗l _ ，其中p ，f ，分别为航班i 的最早和最晚 交货期；当c ， f ，称航班i 的地面作 业拖期完成。如果飞机地面作业在其作业完成时削窗口内完成，则没有惩罚； 否则无论飞机i 的地面作业提前或者拖其，都将对飞机i 进行惩罚； 航班i 的地面作业提前惩罚权重； 航班i 的地面作业拖期惩罚权重，一般 z ? i s x z 登 x z ( 5 1 6 ) ( 5 1 7 ) f 5 1 9 1 步骤三根据中间隶属度最大值”的思想【3 8 】，将规划( 5 1 0 ) 转化为如下的单目标非 线性规划： m a x r 口7 + ( 1 一1 1 ) d “) ( 5 2 0 ) j f 日“，乜7 f = 1 ，3( 5 2 i ) 2 口” ( 5 2 2 ) 口。，口“ o ，1 】 ( 52 3 ) 另一种形式为： m i n 1 一r a7 一( 1 一r ) 口“)( 52 4 ) s ，d “，口7 i = 1 ，3( 5 2 5 ) 卢2 口“ ( 52 6 ) a ，口“【o ，l 】( 52 7 ) 其中，h ( x ) ( f = l ，2 ，3 ) 分别是互( 扛1 ，2 ，3 ) 的满意隶属度，a 表示“( x ) ( f = l ，2 ，3 ) 中 的最小值，a “表示，( x ) ( f _ 1 ，2 ，3 ) 中的最大值。式( 5 2 0 ) 中采用了补与算子r ，r 由决 4 7 中国民用航空学院硕士学位论史 定义5 6 若干个交换序可以合并成一个新的交换序，定义。为两个交换序的合并 算子。 设置p s o 算法中的速度算式为如下形式： 一j = v do c l ( n d 一蕾d ) 0c 2 ( p 叫一。) ( 5 2 9 ) 期中c ，c ：( c ，c ：f o ，】j ) 为随机数。c ，( 助一) 表示基本交换序( 只。一) 中的所有交换 子以概率c ，保留：同理，c ：( p 鲥一强) 表示基本交换序( p 一一) 中的所有交换子以概 率c z 保留。由此可以看出，c ，的值越大，( 助一) 保留的交换子就越多，地影响就 越大；同理，c ：的值越大，( p 州一。衬) 保留的交换子就越多，p 州影响就越大。 5 3 2 算法步骤 1 、初始化粒子群，即给群体中的每个粒子赋一个随机的初始解序列和一个随机的 交换序，设定迭代次数： 2 、计算该序列的适应值，如果适应值满足结束条件，转到步骤5 ： 3 、根据粒子当前位置，计算其下一个位置妇，即新解： ( 1 ) 计算p 。和之间的差爿，爿= p 。一x 其中爿是个基本交换序，表示爿作 用于h 得到p 。； ( 2 ) 计算占= p “一妇，其中口也是一个基本交换序； ( 3 ) 根据( 52 9 ) 式计算速度屹，并将交换序屹转换为一个基本交换序； ( 4 ) 计算搜索到的新解 d = + v d( 5 3 0 1 ( 5 ) 如果找到一个更好的解，则更新； 4 、如果整个群体找到一个更好的解，更新p 硝，转步骤2 5 、显示求出的结果 中国民用航空学院硕 ：学位论文 进化代数 图5 1r = o 9 时适应度曲线图 图5 1 显示了当补与算子r = o 9 时的算法适应度函数进化曲线图，在运算6 0 0 代 以后收敛速度加快，在运算1 0 0 0 代以后收敛到最小值。 图5 21 1 = o5 时适应度曲线图 图5 2 显示了当补与算子r 取较小的值0 5 时，算法有了更好的收敛性，在运算不 到1 0 0 0 代时，已经收敛到最小值。 中国民用航空学院顾士学位论土 图5 3r = o 2 时适应度曲线图 图5 3 显示了当补与算子1 1 取值0 2 时，算法比以上两种情况有更加快速的收敛性。 表5 3 厂值不同情况下的目标函数值 义 l 2 345678910a v g 0 2o 1 3 4 60 1 4 7 501 1 8 20 1 6 0 40 1 5 4 70 1 3 6 50 1 5 7 8 0 1 6 5 40 1 2 3 20 1 2 8 30 1 4 2 7 0 50 1 6 7 30 1 7 4 20 1 9 8 7 0 1 9 8 20 1 8 2 30 18 5 40 1 7 8 90 1 8 2 50 1 9 3 60 1 9 6 20 1 8 5 7 0 902 1 5 30 2 2 1 4o 2 1 6 20 2 1 3 40 2 1 8 7o2 2 5 8o 2 2 6 302 4 5 lo 2 3 7 202 1 5 4 o 2 2 3 5 从表5 3 可以看出，当r 取不同的值时，从5 0 次运行中结果中随机选取其中l o 次进行 分析。可知，n 代表运行次数，i _ 取值越小，得到的目标函数值越小，其调度结果越好， 决策越积极；反之，得到的目标函数值越大，调度结果越差，决策越保守。在各种情况 下，算法都有良好的收敛性，调度结果都具有较大的满意度。当r = o - 2 时适应度函数值 最小，对应的调度结果为( 2 ，i ，4 ，3 ，5 ，6 ，9 ，1 0 ，7 ，8 ，即飞机地面作业顺序应 该为i 2 ，1 ，4 ，3 ，5 ，6 ，9 ，1 0 ，7 ，8 ，在这种情况下保证了最多的航班在地面作业 时间窗口内完工，使提前拖期惩罚值最小。 中国民用航空学院顺七学位论文 5 5 小结 本章对有不同时间窗的提前拖期调度方法应用于飞机地面作业调度的问题进行了 研究，并采用了