基于PSO算法的飞行保障车辆调度问题研究

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　基于ＰＳＯ算法的飞行保障车辆调度问题研究　田　丰　，邢清华　，张威　ＴＩＡＮ　Ｆｅｎｇ　．ＸＩＮＧ　Ｑｉｎｇｈｕａ　．ＺＨＡＮＧ　Ｗｅｉ　１．空军工程大学导弹学院，陕西三原７１３８００　２．徐州空军学院航空兵军交运输指挥系，江苏徐州２２１０００　１．Ｍｉｓｓｉｌｅ　Ｉｎｓｔｉｔｕｔｅ，Ａｉｒ　Ｆｏｒｃｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓａｎｙｕａｎ，Ｓｈａａｎｘｉ　７１３８００，Ｃｈｉｎａ　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆＡｖｉａｔｉｏｎ　Ｍｉｌｉｔａｒｙ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｃｏｍｍａｎｄ，Ｘｕｚｈｏｕ　Ａｉｒ－ｆｏｒｃｅ　Ｃｏｌｌｅｇｅ，Ｘｕｚｈｏｕ，Ｊｉａｎｇｓｕ　２２１０００，Ｃｈｉｎａ　

ＴＩＡＮ　Ｆｅｎｇ，ＸＩＮＧ　Ｑｉｎｇｈｕａ，ＺＨＡＮＧ　Ｗｅｉ．Ｒｅｓｅａｒｃｈ　ｏｎ　ｓｕｐｐｏｒｔ　ｖｅｈｉｃｌｅｓ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ　ｉｎ　ｆｌｉｇｈｔ　ｓｕｐｐｏｒｔ　ｐｒｏｃｅｓｓ　ｗｉｔｈ　ＰＳＯ　ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１２，４８（１）：２４２—２４４．　Ａｂｓｔｒａｃｔ：Ｃｏｎｓｉｄｅｒｉｎｇ　ｔｈｅ　ｃｏｎｖｅｎｔｉｏｎａｌ　ａｎｔｉｃｉｐａｔｉｏｎ　ｍｅｔｈｏｄ　ｗｈｉｃｈ　ｄｅｐｅｎｄｓ　ｏｎ　ｅｘｐｅｒｉｅｎｃｅ　ｏｆ　ｔｈｅ　ｃｏｍｍａｎｄｅｒ　ｔｏ　ｓｃｈｅｄｕｌｅ　ｔｈｅ　ａｖｉａｔｉｏｎ　ｓｕｐｐｏｒｔ　ｖｅｈｉｃｌｅｓ，ｉｔ　ｈａｓ　ｔｈｅ　ｄｉｓａｄｖａｎｔａｇｅ　ｏｆ　ｌｏｗ　ｅｆｆｉｃｉｅｎｃｙ，ＰＳＯ—ｂａｓｅｄ　ｌｉｎｅａｒｌｙ　ｄｅｃｒｅａｓｉｎｇ　ｗｅｉｇｈｔ　ｔｏ　ｆｌｉｇｈｔ　ｓｕｐｐｏｒｔ　ｖｅｈｉｃｌｅｓ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｔｈｒｏｕｇｈ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｓｕｐｐｏｒｔ　ｖｅｈｉｃｌｅ　ｓｃｈｅｄｕｌｉｎｇ．Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｔｈｅ　ｐｒｏｂｌｅｍ，ｔｈｅ　ＰＳＯ　ｃｏｄｉｎｇ　ａｎｄ　ｏｐｔｉ—　ｍｉｚａｔｉｏｎ　ａｒｅ　ｓｔｕｄｉｅｄ　ｔｏ　ｄｅｔｅｒｍｉｎｅ　ｔｈｅ　ｗａｙ　ｏｆ　ｐａｒｔｉｃｌｅｓ’ｃｏｄｉｎｇ　ａｎｄ　ｏｐｅｒａｔｉｏｎ，ｗｈｉｃｈ　ｉｓ　ｍｏｒｅ　ａｄａｐｔａｂｌｅ　ｔｏ　ｆｌｉｇｈｔ　ｓｕｐｐｏｒｔ　ｖｅｈｉｃｌｅｓ　ｓｃｈｅｄｕｌ—　ｉｎｇ．Ｔｈｅ　ｓｕｐｐｏｒｔ　ｖｅｈｉｃｌｅｓ　ｓｃｈｅｄｕｌｉｎｇ　ｐａｒｔ　ｏｆ　ｔｈｅ　ｆｌｉｇｈｔ　ｓｕｐｐｏｒｔ　ｐｒｏｃｅｓｓ　ｉｓ　ｐｒｏｇｒａｍｍｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｓｏｆｔｗａｒｅ　Ｍａｔｌａｂ．Ｓｉｍｕ’　ｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｉｔ　ｃａｎ　ｐｒｏｖｉｄｅ　ｂｅｔｔｅｒ　ｐｌａｎｅ　ｓｕｐｐｏｒｔ　ｓｅｑｕｅｎｃｅｓ　ｔｏ　ｓａｔｉｓｆｙ　ｔｈｅ　ｒｅｑｕｉｒｅｍｅｎｔ　ｏｆ　ｄｙｎａｍｉｃ　ｆｌｉｇｈｔ　ｓｕｐｐｏｒｔ　ｖｅｈｉｃｌｅｓ　ｓｃｈｅｄ－　ｕｌｉｎｇ　ｂｙ　ｓｅｔｔｉｎｇ　ｔｈｅ　ｓｕｉｔａｂｌｅ　ｐａｒａｍｅｔｅｒｓ　ｉｎ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｆｌｉｇｈｔ　ｓｕｐｐｏｒｔ　ｓｙｓｔｅｍ；ｖｅｈｉｃｌｅ　ｓｃｈｅｄｕｌｉｎｇ；Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　０ｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）　

摘要：通过对飞行保障车辆调度过程的分析，针对传统估算法依据指挥员经验进行飞行保障车辆调度效率低等缺点，提出了一　种基于线性递减权重ＰＳＯ的飞行保障车辆调度问题解决方案。根据飞行保障车辆调度问题解的特点，对粒子的编码及寻优操作　进行了深入研究，提出适合飞行保障车辆调度问题的粒子编码和寻优方式，并将算法利用Ｍａｔｌａｂ编程实现，应用于实际飞行保障　车辆调度过程中。仿真结果表明，通过对算法参数的合理设置，可以快速地得到较优的飞机保障工序排序结果，该排序结果能够　满足动态飞行保障车辆调度的需要。　关键词：飞行保障系统；车辆调度；粒子群算法　ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２０１２．０１．０６９　文章编号：１００２—８３３１（２０１２）０１．０２４２．０３　文献标识码：Ａ　中图分类号：Ｅ９１７　

飞行保障车辆调度是指航空兵场站在飞行保障过程中，　场站指挥员根据担负战斗或训练飞行任务部队的飞行计划，　在综合考虑不同机种（型）飞机首次出动（或再次出动）执行作　战任务需要的基础上，合理调度各种类型的保障车辆对各种　（型）飞机进行的适时、适地、适量保障过程。因此，提出科学　有效的保障车辆调度算法是实现精确化保障目标和提升航空　兵场站保障力的基础和关键。　１飞行保障车辆调度问题及其优化模型　１．１问题的提出　国内对于飞行保障车辆调度问题的研究已经有几十年的　历史，提出了许多定性研究成果；但关于该问题的定量化研　究，则开始于２１世纪初，且受认识、保密等因素影响，目前公开　发表的定量化研究成果较少　；方法上大多使用价格昂贵的　商业仿真软件及其集成的仿真优化工具箱，进行飞行保障车　辆调度的仿真优化，上述方法由于存在所建仿真模型复杂庞　大，场站后勤指挥员掌握使用困难，且购买相应的仿真平台价　格不菲，基层部队不易广泛推广使用等难题。因此，本文针对　仿真法存在的上述问题，利用现代智能优化算法中的粒子群　算法　１（ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ），来求解飞行保障车辆调　度这类ＮＰ完全问题，且给出的优化模型求解算法可以嵌入到　外场飞行保障组织指挥决策支持系统中，便于指挥员演练使　用，从而为解决飞行保障车辆调度问题提供了一种新的研究　途径。　１．２优化模型　在场站现有保障车辆资源约束下，针对场站担负的某项　具体飞行保障任务，结合飞行计划要求，合理地安排飞机作战　所需的各项保障及保障车辆调度，从而实现整个飞行保障车　辆调度过程效率较高、时问较短、费用较少等目标。　本文在借鉴柔性生产车间调度等国内外相关问题研究成　果的基础上　，结合场站日常飞行保障过程中车辆保障特点　和飞行计划要求，建立如下飞行保障车辆调度优化模型：　ｍｉｎｌｍ　ａ　ｘ

Ⅲ￣Ｉ１ｍ≤ｆａ　ｘｎ

Ｃ　．　｝　（１）　

ｓ．ｔ．ｅ　—ｔ　＋　（１一ａｉｈｋ）＞Ｃ　（２）　—ｃ　＋　（１一　眦）≥　（３）　Ｃ　≥０　（４）　ｘ瀚＝Ｏ或１　（５）　

基金项目：部委科研资助。　作者简介：田丰（１９８Ｏ一），男，博士生，主要研究领域为空军作战后勤运筹、空军作战保障模拟与仿真；邢清华（１９６６一），女，博士后，教授，博士生　导师。Ｅ—ｍａｉｌ：ｔｉａｎｆｅｎｇ８０７２７＠１６３．ｃｏｍ　收稿日期：２０１０—０６—１０；修回日期：２０１０—０８—０３　田　丰，邢清华，张威：基于ＰＳＯ算法的飞行保障车辆调度问题研究　＝　一ｆｌ，保障冼于保陶在车辆　上实施　一１０，其他　

，　２．２．２权重因子　一　惯性权重Ｗ主要用于保持粒子的运动惯性，使其有扩展　

（７）　式（１）至式（７）中，ｆ，Ｊ＝１，２，…，ｎ，ｈ，｜ｊ｝＝１，２，…，ｍ；其　中，ｎ为飞行计划中各架飞机需要完成的保障工序总数，ｍ为　场站列装的各类保障车辆资源的总数，ｔ　和ｃ　分别表示飞机　所需保障工序ｉ在保障车辆ｋ上的保障时间和保障完成时间；　符号　是一个足够大的正数；ａ　和　分别表示指示系数和　指示变量。目标函数式（１）为最小化最大单机保障完成时间，　ｃ　表示单架飞机所需保障的最后一项保障工序ｉ在保障车辆　ｋ上的完成时间。　约束条件中：式（２）表示出于安全考虑，在某一时刻单架　飞机只能有一项保障在飞机上进行；式（３）表示某台保障车辆　只要开始保障某架飞机，其保障过程不允许中断，必须等到本　次保障过程结束，该保障车辆才能保障其他飞机。同时，上述　问题还需满足下列假设条件：一是每架飞机所需保障的次序　严格按飞行保障计划的要求执行，不能随意改变；二是一台保　障车辆不能同时保障两架飞机；三是严格遵守飞行计划中对　于各类地面保障时间的要求。　２粒子群优化算法　粒子群优化（ＰＳＯ）算法是由美国社会心理学家Ｋｅｎｎｅｄｙ　博士和电气工程师Ｅｂｅｒｈａｒｔ博士于１９９５年共同提出的一种源　于群智能的智能优化算法　，它用无质量、无体积的粒子作为　个体，并为每个粒子规定简单的行为规则，从而使整个种群表　现出复杂的特性，可用来求解复杂的组合优化问题。粒子群　算法由于具有个体数目少、计算简单、鲁棒性好等优点，目前　已在多目标优化、模式识别、信号处理、机器人活动规划、决策　制定等领域取得了较好的效果。　２．１标准ＰＳＯ算法数学描述　设在一个ｎ维搜索空间中，由ｍ个粒子组成的种群　：　｛　１，ｘ２，…，ｔ，…，　｝，其中第ｉ个粒子位置　＝　ｆ１，　１２’…，　）　，　其速度　＝　ｖ　…，Ｖｉｎ）Ｔ它的个体极值Ｐ　＝（ｐ　Ｐｉ２，…，ｐ　）　，　种群的全局极值为Ｐｇ－￣（Ｐｇｌ，Ｐ　，…，　）　’。根据追随当前最　优粒子的原理，粒子ｘ　将根据式（８）和式（９）改变其自身的速　度和位置向量：　Ｖ　“＝ｗＶｔ　＋ｃ１×ｒａｎｄ１×（ｐ　一　）＋　Ｃ２×ｒａｎｄ２　Ｘ、，　ｔ—ｘ　ｔ）　（８）　”－Ｘ　ｔ＋ｙ　（９）　其中，　＝１，２，…，ｎ；ｉ＝１，２，…，ｍ，ｍ为种群规模，ｔ为当前　进化代数，ｒａｎｄＩ，ｒａｎｄ２为分布于［０，１】之问的随机数，ｃ＇，ｃ　为加速常数，Ｗ为惯性权重。　２．２算法参数设置　２．２．１最大速度　在式（８）和（９）中，粒子的速度ｖ　和位置％的绝对值有　可能过大，从而使得粒子一下飞出解空间。为此，需要限制ｖ，　和Ｘ　的值在一定的范围内，设定其范围分别为［一ｖ　ｖ一】和　［－ｘ　，　一］，本文Ｖ　设为１，　设为５。　搜索空间的趋势。相关文献表明［８－９］，当Ｗ取０．９到１．２之间固　定值时，算法能够取得较好的优化结果。Ｗ从０．９线性递减到　０．４时，算法能够很快地向最优解收敛。因此，采用线性递减权　重，即惯性权重Ｗ的值在ＰＳＯ搜索过程中线性变化。计算公　式如下　０】：　

一ｗ～一　（１０　其中，ｗ一为喷性权重的最大值，取０．９；ｗｍｍ为惯性权重的最　小值，取０．４；ｔ…为最大迭代次数；ｔ为当前迭代次数。　２．２．３加速度常数Ｃ　，　加速度常数ｃ１和ｃ　代表将每个粒子飞向Ｐ　。　和ｇ　。。　位　置的统计加速项的权重ｎ　。低的值允许粒子在被拉回之前可　以在目标区域外徘徊，而高的值则导致粒子突然冲向或越过　目标区域。根据经验，通常将ｃ　和Ｃ，取值为２。　２．３编码　由于飞行保障车辆调度问题具有离散、动态和多变量等　多种属性。因此，对于飞行保障车辆调度问题ＰＳＯ算法粒子　的编码具有一定的难度，很难确定一个自然表达。本文采用　基于工序的表达方法对粒子进行编码　，　”，把排序编码作为　保障工序的序列，则每一个粒子代表一种可行的保障方案。　本文用一个　维（　为总工序数ｎ）的向量表示一个粒子的　位置向量，实际上它是由两个三维的向量组成，即　。。　和　。　。。。［　，这两个向量在每一维上的分量相互对应，其中，