基于多AGENT的机组配对算法及实现技术研究
|
摘要
航空公司机组排班是一项复杂、庞大和连续的工作,具有多变量、强耦合和多目标等特点。目前国内大部分航空公司的机组排班工作主要依靠人工操作或者引进国外系统。因此,提高机组排班过程的自动化水平,已成为国内航空公司提高竞争力和成本控制的重要内容。
本文应用人工智能的多Agent技术,研究并开发了基于多Agent的机组排班系统。论文首先分析了机组排班的基本过程,着重研究了机组配对(Crew Pairing)算法的实现技术。在分析目前机组配对几种典型算法特点的基础上,对其性能进行了分析对比。考虑到机组配对的数据量大,配对影响因素和配对目标多,本文选择了具有高效并行全局搜索特点的遗传算法对配对过程进行优化。其次,根据目标函数建立算法数学模型,利用遗传算法对其进行优化调度,在确定了遗传算法的染色体编码方式之后,设计了与配对目标对应的适应度函数以及遗传算法的各项算子。建立了基于多Agent的机组配对模型,利用多个agent协作实现了遗传算法的各算子的功能,并讨论了基于多Agent的机组配对系统的流程、系统基本构成和各主要Agent的设计与实现。本文最后对系统性能进行了分析和评估,并提出了进一步改进建议。
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 oversea’s 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.
本文应用人工智能的多Agent技术,研究并开发了基于多Agent的机组排班系统。论文首先分析了机组排班的基本过程,着重研究了机组配对(Crew Pairing)算法的实现技术。在分析目前机组配对几种典型算法特点的基础上,对其性能进行了分析对比。考虑到机组配对的数据量大,配对影响因素和配对目标多,本文选择了具有高效并行全局搜索特点的遗传算法对配对过程进行优化。其次,根据目标函数建立算法数学模型,利用遗传算法对其进行优化调度,在确定了遗传算法的染色体编码方式之后,设计了与配对目标对应的适应度函数以及遗传算法的各项算子。建立了基于多Agent的机组配对模型,利用多个agent协作实现了遗传算法的各算子的功能,并讨论了基于多Agent的机组配对系统的流程、系统基本构成和各主要Agent的设计与实现。本文最后对系统性能进行了分析和评估,并提出了进一步改进建议。
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 oversea’s 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.
引文
[1]于贵桃,南航机组排班系统的研究与应用[J],中国民航学院学报,2003 年 10 月,第 21卷增刊 2
[2] B.E. 吉勒特著,蔡宣三、陈伟基、 王永县译,运筹学导论[M],机械工业出版社,1982
[3]Zichao Wang , A Critical Study of Multi-Agent Systems: Models,Architectures and Applications[D],[the Degree of Master of Computer science ],Montreal,Quebec,Canada,Concordia University,2003
[4]王凌,《智能优化算法及其应用》(Intelligent Optimization Algorithms with Applications)[M],清华大学出版社,springer 出版社,2001
[5]聂亚杰, Agent 的体系结构[J],计算机应用研究,2001 年第 9 期
[6]周立柱、赵洪彪.Internet 环境中的软件 Agent[J].计算机科学.No.3.1999
[7]刘弘、周林.软件 Agent 的构筑[J].计算机科学.No.2.1998
[8]于江涛 .多智能体模型、学习和协作研究与应用[D]. 万方数据源,浙江大学博士论文.2003.6
[9]Xiaobin Wei,Rainer Unland. An XML-Based Agent Communication Framework[C].In:Workshop 0n Agents And CSCW : A Fruitful Marriage.The German Conference 0n Computer-Supported Cooperative Work (D-CSCW 2000).Munich.Germany,2000
[10]魏晓斌 周盛宗 Boris Bachmendo. Rainer Unland .Agent 通信机制探讨[J].计算机工程与应用 2002.5
[11]何炎祥.陈莘萌.Agent 和多 Agent 系统的设计与应用[M].武汉大学出版社.2001.6
[12]张维明.姚莉.只能协作信息技术[M].北京:电子工业出版社.2002
[13]Poslad S,Calisti M.Towards Improved Trust and Security in FIPA Agent Platforms[c].In the Fourth Conference on Autonomous Agents,Barcelona,Spain,2000
[14]Thirunavukkarasu C,Finin T,Mayfield J.Secret Agents-a security Architecture for the KQML Agent communication language[C].In the Fourth International Conference on Information and Knowledge Management CIKM’95,Baltimore;IEEE Comp Soc Press,1995:176~184
[15]陶世群,蒲保兴,基于遗传算法的多级目标非平衡指派问题求解[J], 系统工程理论与实践,2004 年 8 月第 8 期:80～85
[16] Jianghai Hu,Multi-Agent Coordination:Theory and Applications[D],[the Degree of Doctor of Philosophy in Engineering-Electrical Engineering and Computer Sciences],Berkeley,University of California,Fall2003
[17]DehuQi,Multi-Agent Systems: Integrating Reinforcement Learning ,Bidding and Genetic Algorithms[D],[the Degree of Doctor of Philosophy],Columbia,university of Missouri,2002
[18]Panait Liviu,Luke sean,Cooperative Multi-Agent Learning: The State of the Art[J],Autonomous Agents and Multi-Agent Systems,2005 年 11 月,11 卷 3 期
[19] G. Desaulniers, j. Desrosiers, y. Dumas et al , Crew pairing at Air France[J],European Journal of Operational Research 97 (1997) 245-259
[20] Francisco P. Maturana, Pavel Tichy, Petr lechta.etal,Distributed multi-agent architecture for automation systems[J],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 Algorithms[J], I.P. Vlahavas and C.D. Spyropoulos (Eds.): SETN 2002, LNAI 2308, pp. 109–120, 2002,Springer-Verlag Berlin Heidelberg 2002
[23] F. Buccafurri, D. Rosaci, G. M. L. Sarnè and L. Palopoli,Modeling cooperation in multi-agent communities[J] ,Cognitive Systems Research, Volume 5, Issue 3, September 2004:171-190
[24] Sooyong Park and Vijayan Sugumaran,Designing multi-agent systems: a framework and application[J] ,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 pairings[J] ,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 scheduling[J] ,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 lines[J],European Journal of Operational Research, Volume 170, Issue 3, 1 May 2006: 844-862
[28]Anne Mercier and Fran?ois 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月,第 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 problems[D],[degree of Doctor of Science],Washington University,August,2001
[37]李军 张卓,多 Agent 系统中 Agent 的协作机理与模式[J], 青岛大学学报(工程技术版),Vol20.No3. Sep.2005
[38] Jay Michael Rosenberger,Topics in Airline Operations[D],[for the degree of Doctor of Philosophy in Industrial and systems Engineering],Georgia Institute of Technology,November 2001
[39] Diego Klabjan, Karsten Schwan,Airline Crew Pairing Generation in Parallel June 8, 1999
[40]Joyce W.yen,A Stochastic Programming Formulation Of The Stochastic Crew Scheduling Problem[D],[for the degree of Doctor of Philosophy ],Industrial and Operations Engineering,the University of Michigan,2001
[41] Tina L.shaw,Hybrid Column Generation for Large Network Routing Problems:with Implementations in Airline Crew Scheduling[D] , [for the degree of doctor of Philiosophy]Georgia Institute of Technology,April 2003
[42] Diego Klabjan,Ellis L.Johnson and Georgel L.nemhause,Solving Large Airline Crew Scheduling Problems:Random Pairing Generation and Strong Branching[J],Computational Optimization and Applications, 20, 73–91, 2001
[2] B.E. 吉勒特著,蔡宣三、陈伟基、 王永县译,运筹学导论[M],机械工业出版社,1982
[3]Zichao Wang , A Critical Study of Multi-Agent Systems: Models,Architectures and Applications[D],[the Degree of Master of Computer science ],Montreal,Quebec,Canada,Concordia University,2003
[4]王凌,《智能优化算法及其应用》(Intelligent Optimization Algorithms with Applications)[M],清华大学出版社,springer 出版社,2001
[5]聂亚杰, Agent 的体系结构[J],计算机应用研究,2001 年第 9 期
[6]周立柱、赵洪彪.Internet 环境中的软件 Agent[J].计算机科学.No.3.1999
[7]刘弘、周林.软件 Agent 的构筑[J].计算机科学.No.2.1998
[8]于江涛 .多智能体模型、学习和协作研究与应用[D]. 万方数据源,浙江大学博士论文.2003.6
[9]Xiaobin Wei,Rainer Unland. An XML-Based Agent Communication Framework[C].In:Workshop 0n Agents And CSCW : A Fruitful Marriage.The German Conference 0n Computer-Supported Cooperative Work (D-CSCW 2000).Munich.Germany,2000
[10]魏晓斌 周盛宗 Boris Bachmendo. Rainer Unland .Agent 通信机制探讨[J].计算机工程与应用 2002.5
[11]何炎祥.陈莘萌.Agent 和多 Agent 系统的设计与应用[M].武汉大学出版社.2001.6
[12]张维明.姚莉.只能协作信息技术[M].北京:电子工业出版社.2002
[13]Poslad S,Calisti M.Towards Improved Trust and Security in FIPA Agent Platforms[c].In the Fourth Conference on Autonomous Agents,Barcelona,Spain,2000
[14]Thirunavukkarasu C,Finin T,Mayfield J.Secret Agents-a security Architecture for the KQML Agent communication language[C].In the Fourth International Conference on Information and Knowledge Management CIKM’95,Baltimore;IEEE Comp Soc Press,1995:176~184
[15]陶世群,蒲保兴,基于遗传算法的多级目标非平衡指派问题求解[J], 系统工程理论与实践,2004 年 8 月第 8 期:80～85
[16] Jianghai Hu,Multi-Agent Coordination:Theory and Applications[D],[the Degree of Doctor of Philosophy in Engineering-Electrical Engineering and Computer Sciences],Berkeley,University of California,Fall2003
[17]DehuQi,Multi-Agent Systems: Integrating Reinforcement Learning ,Bidding and Genetic Algorithms[D],[the Degree of Doctor of Philosophy],Columbia,university of Missouri,2002
[18]Panait Liviu,Luke sean,Cooperative Multi-Agent Learning: The State of the Art[J],Autonomous Agents and Multi-Agent Systems,2005 年 11 月,11 卷 3 期
[19] G. Desaulniers, j. Desrosiers, y. Dumas et al , Crew pairing at Air France[J],European Journal of Operational Research 97 (1997) 245-259
[20] Francisco P. Maturana, Pavel Tichy, Petr lechta.etal,Distributed multi-agent architecture for automation systems[J],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 Algorithms[J], I.P. Vlahavas and C.D. Spyropoulos (Eds.): SETN 2002, LNAI 2308, pp. 109–120, 2002,Springer-Verlag Berlin Heidelberg 2002
[23] F. Buccafurri, D. Rosaci, G. M. L. Sarnè and L. Palopoli,Modeling cooperation in multi-agent communities[J] ,Cognitive Systems Research, Volume 5, Issue 3, September 2004:171-190
[24] Sooyong Park and Vijayan Sugumaran,Designing multi-agent systems: a framework and application[J] ,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 pairings[J] ,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 scheduling[J] ,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 lines[J],European Journal of Operational Research, Volume 170, Issue 3, 1 May 2006: 844-862
[28]Anne Mercier and Fran?ois 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月,第 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 problems[D],[degree of Doctor of Science],Washington University,August,2001
[37]李军 张卓,多 Agent 系统中 Agent 的协作机理与模式[J], 青岛大学学报(工程技术版),Vol20.No3. Sep.2005
[38] Jay Michael Rosenberger,Topics in Airline Operations[D],[for the degree of Doctor of Philosophy in Industrial and systems Engineering],Georgia Institute of Technology,November 2001
[39] Diego Klabjan, Karsten Schwan,Airline Crew Pairing Generation in Parallel June 8, 1999
[40]Joyce W.yen,A Stochastic Programming Formulation Of The Stochastic Crew Scheduling Problem[D],[for the degree of Doctor of Philosophy ],Industrial and Operations Engineering,the University of Michigan,2001
[41] Tina L.shaw,Hybrid Column Generation for Large Network Routing Problems:with Implementations in Airline Crew Scheduling[D] , [for the degree of doctor of Philiosophy]Georgia Institute of Technology,April 2003
[42] Diego Klabjan,Ellis L.Johnson and Georgel L.nemhause,Solving Large Airline Crew Scheduling Problems:Random Pairing Generation and Strong Branching[J],Computational Optimization and Applications, 20, 73–91, 2001