（交通信息工程及控制专业论文）基于多AGENT的机组配对算法及实现技术研究.pdf

南京航空航天大学学位论文 i 摘摘 要要 航空公司机组排班是一项复杂、庞大和连续的工作，具有多变量、强耦合 和多目标等特点。目前国内大部分航空公司的机组排班工作主要依靠人工操作 或者引进国外系统。因此，提高机组排班过程的自动化水平，已成为国内航空 公司提高竞争力和成本控制的重要内容。 本文应用人工智能的多 agent 技术，研究并开发了基于多 agent 的机组排 班系统。论文首先分析了机组排班的基本过程，着重研究了机组配对（crew pairing）算法的实现技术。在分析目前机组配对几种典型算法特点的基础上， 对其性能进行了分析对比。考虑到机组配对的数据量大，配对影响因素和配对 目标多，本文选择了具有高效并行全局搜索特点的遗传算法对配对过程进行优 化。其次，根据目标函数建立算法数学模型，利用遗传算法对其进行优化调度， 在确定了遗传算法的染色体编码方式之后，设计了与配对目标对应的适应度函 数以及遗传算法的各项算子。建立了基于多 agent 的机组配对模型，利用多个 agent 协作实现了遗传算法的各算子的功能， 并讨论了基于多 agent 的机组配对 系统的流程、系统基本构成和各主要 agent 的设计与实现。本文最后对系统性 能进行了分析和评估，并提出了进一步改进建议。 关键词：机组排班，机组配对，遗传算法，多 agent 系统 基于多 agent 的机组配对算法及实现技术研究 ii abstract crew scheduling is a complex, large-scale and continual work, characterized of multivariable, close coupling and multi-objectives and so on. but in most of domestic airlines, the process of crew scheduling is still on the stage of the manual level or depends on overseas system. therefore, that how to increase the computer application in the process of crew scheduling comes to be an important job of demestic airline to enhance competition and to control cost. this thesis presents a modal for the crew scheduling based on the multi-agent technology, an advanced a.i. one. first, the characterization of the crew scheduling is analysied, especially the realization technology of crew pairing in this process. the basic principles of typical algorithms which used in the crew pairing are evaluated based on the study of the capabilities of these algorithms. considering the huge data quantity and the plentiful objectives of the crew pairing, genetic algorithm is selected to slove the problem, which can realize the overall searching efficiently. next，the mathematical model , built according to the target function, is optimized and scheduled by the means of genetic algorithm. after the chromosome coding method is designed, fitness function is established corresponding to the crew pairing objects and the arithmetic operators of genetic algorithm is designed. then, the crew pairing modal based on the multi-agent is built. the agents cooperate with each other to realize the operators function. the design of the modal, including the system flow, system basic constitution and the realization of most agents is introduced. finally, in the end of the dissertation, some further suggestions are given to improving the modal. key words: crew scheduling, crew pairing, genetic algorithm, multi-agent 承诺书承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本 学位论文的研究成果不包含他人享有著作权的内容。对本论文所涉及的研 究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。 论文作者： （签名） 二六年 月 日 南京航空航天大学硕士学位论文 v 图表目录图表目录 图 2.1 航空运输生产计划生成流程.4 图 2.2 机组人员执勤行程图.6 图 2.3 机组勤务分配示意图.7 图 2.4 勤务组合示意图.8 表 2.1 一名或两名驾驶员的飞行时间限制 .8 表 2.2 三名驾驶员的飞行时间限制.9 表 2.3 航班信息示例.10 图 2.5 机组配对示意图.10 图 2.6 分枝定界法示意图 .13 表 2.4 人员的工作消耗时间对应表.14 图 2.7 变数产生法示意图 .15 图 2.8 遗传算法基本思想 .16 图 2.9 遗传算法交叉机制 .17 图 2.10 遗传算法变异机制.18 图 2.11 遗传算法构造过程 .18 图 3.1 典型的 agent 结构图.24 图 3.2 多 agent 组织结构 .26 图 3.3 混合式 agent 组.27 图 3.4 安全 agent 的基本结构.29 图 4.1 机组配对算法设计 .34 图 4.2 mas 结构设计.42 图 4.3 多 agent 搜索群体的分割.43 图 4.4 对话模式示意图.44 图 4.5 管理 agent 与执行 agent 之间对话协作过程 .45 图 4.6 管理 agent 与执行 agent 组的交互 .46 图 4.7 执行 agent 内部交互 .47 图 4.8 机组配对在 gasoms 中的作用 .49 图 4.9 航班计划编排主界面.50 图 4.10 机组人员安排主界面.51 图 4.11 机组人员调整界面 .51 基于多 agent 的机组配对算法及实现技术研究 vi 注释表注释表 1iata：international airline transport association，国际航空运输协会 2agifors： airline group for international federation of operation research， 国际运筹学联合会的航空公司工作组 3ai：artificial intelligence ，人工智能 4mas：multi-agent system，多智能体系统 5spki：simple public key infrastructure，简单公开密钥基础建设 6spp：set-partitioning problem，集合划分问题 7kqml：knowledge query and manipulation language，知识查询与处理语言 8 gasoms ： general airflight scheduling ieee comp soc press,1995:176184 15陶世群,蒲保兴,基于遗传算法的多级目标非平衡指派问题求解j, 系统工程理论与实 践，2004 年 8 月第 8 期:8085 16 jianghai hu，multi-agent coordination:theory and applicationsd，the degree of doctor of philosophy in engineering-electrical engineering and computer sciences，berkeley， university of california，fall2003 17dehuqi，multi-agent systems: integrating reinforcement learning ,bidding and genetic algorithmsd，the degree of doctor of philosophy，columbia，university of missouri，2002 南京航空航天大学硕士学位论文 57 18panait liviu，luke sean，cooperative multi-agent learning: the state of the artj， autonomous agents and multi-agent systems，2005 年 11 月，11 卷 3 期 19 g. desaulniers, j. desrosiers, y. dumas et al , crew pairing at air francej,european journal of operational research 97 (1997) 245-259 20 francisco p. maturana, pavel tich, petr lechta.etal，distributed multi-agent architecture for automation systemsj，expert systems with applications, volume 26, issue 1, january 2004： 49-56 21黄文培，多 agent 专家系统安全性设计与研究m，计算机工程与应用，2005.22 22 harry kornilakis and panagiotis stamatopoulos, crew pairing optimization with genetic algorithmsj, i.p. vlahavas and c.d. spyropoulos (eds.): setn 2002, lnai 2308, pp. 109120, 2002,springer-verlag berlin heidelberg 2002 23 f. buccafurri, d. rosaci, g. m. l. sarn and l. palopoli，modeling cooperation in multi-agent communitiesj ，cognitive systems research, volume 5, issue 3, september 2004： 171-190 24 sooyong park and vijayan sugumaran，designing multi-agent systems: a framework and applicationj ，expert systems with applications, volume 28, issue 2, february 2005：259-271 25 s. yan, t. -t. tung and y. -p. tu， optimal construction of airline individual crew pairingsj ， computers & operations research, volume 29, issue 4, april 2002：341-363 26 dennis huisman and albert p.m. wagelmans，a solution approach for dynamic vehicle and crew schedulingj ，european journal of operational research, in press, corrected proof, available online 16 december 2004 27 maikol m. rodrigues, cid c. de souza and arnaldo v. moura，vehicle and crew scheduling for urban bus linesj，european journal of operational research, volume 170, issue 3, 1 may 2006： 844-862 28anne mercier and franois soumis，an integrated aircraft routing, crew scheduling and flight retiming model j， computers & operations research, in press, corrected proof, available online 15 november 2005 29何汉明 李永强，多 agent 社会的结构模型j，计算机应用与软件，2005 年 4 月，第 22 卷 4 期 30高志军 颜国正 丁国清， 多 agent 协作环境下的任务分配j， 系统工程与电子技术， 2005 年 1 月，第 27 卷,第 1 期 31黄康 许志伟 董迎晖，改进的遗传算法及其在多目标优化设计中的应用j，机械设计， 2 0 0 5 年9 月，第22卷第9 期 32杨文恺 李海刚，基于多 agent 技术的企业协同框架研究j，计算机工程，2005 年 6 基于多 agent 的机组配对算法及实现技术研究 58 月，第 31 卷 ,第 11 期 33何汉明 何华灿，一种多智能体组织模型j，计算机应用与软件，2005年3月，第22卷 第3 期 34董红斌 孙羽，多 agent 系统的现状与进展j.计算机应用研究，2001.1 35赵龙文 侯义斌，多 agent 系统及其组织结构j，2000.12 36 sanghyun kim, adaptations of constraint programming to aircraft scheduling problemsd,degree of doctor of science，washington university,august，2001 37李军 张卓,多 agent 系统中 agent 的协作机理与模式j, 青岛大学学报(工程技术 版),vol20.no3. sep.2005 38 jay michael rosenberger，topics in airline operationsd，for the degree of doctor of philosophy in industrial and systems engineering，geo