基于多目标遗传算法的枢纽航线网络的鲁棒优化方法

交通运输系统工程与信息 ›› 2009, Vol. 9 ›› Issue (3): 86-92 .

基于多目标遗传算法的枢纽航线网络的鲁棒优化方法

黄佳^{* 1} ;王庆云²

北京航空航天大学经济管理学院,北京,100191;国家发展和改革委员会基础产业司,北京,100824

收稿日期:2008-12-27 修回日期:2009-03-30 出版日期:2009-06-25 发布日期:2009-06-25
通讯作者: 黄佳
作者简介:黄佳（1982-），女，上海人，博士生
基金资助:
国家自然科学基金（70521001）；教育部新世纪优秀人才资助（NCET-04-0173）

Robust Optimization of Hub-and-Spoke Airline Network Design Based on Multi-Objective Genetic Algorithm

HUANG Jia¹; WANG Qing-yun²

1. School of Economics and Management, Beijing University of Aeronautics and Astronautics, Beijing 100191, China; 2. Department of Basic Industries of National Development and Reform Commission, Beijing 100824, China

Received:2008-12-27 Revised:2009-03-30 Online:2009-06-25 Published:2009-06-25
Contact: HUANG Jia

摘要/Abstract

摘要： 枢纽航线网络在设计的过程中，容易受到需求和成本数据发生变化带来的影响。往往造成构建出来的最优网络，在需求发生变化的条件下，与实际对应的最优解存在较大的最低成本优化偏差。为了降低这种网络优化中的不确定性带来的风险，得到在多种可能的需求和成本条件下均可获得较好效果的鲁棒最优解，文中采用了一个多目标优化的遗传算法进行研究。首先将各种不同的需求和成本条件作为需要同时优化的多个目标函数，然后采用一个遗传算法来表示所有可能的枢纽航线网路结构，并搜索多目标优化的鲁棒最优网络解。最后本文对该搜索算法的收敛性进行了证明，数值实验结果表明了算法的有效性。

关键词: 航线网络, 枢纽机场, 多目标优化, 鲁棒优化, 遗传算法

Abstract: In the process of designing hub network, the selection of hub airports is influenced by the change of the demand and cost. Under the condition of changing in demand, this may lead to large minimum cost deviation between the designed optimal network and real optimal network, respectively. To reduce the risk caused by the uncertainty in network optimization and get the optimal robust solution of hub network under the multi-possible conditions of demand and cost, a method based on multi-objective optimization genetic algorithm is proposed in this paper. The convergence of the algorithm has been proved, and the experimental results demonstrate the availability of the algorithm. First, multiple objective functions needing to be optimized simultaneously are formulated from different conditions of needs and cost, then a genetic algorithm is used to provide all possible routes of the network hub structure, and robust optimal network solution for multi-objective optimization is searched. The convergence of the search algorithms is proved to be effective by the numerical results.

Key words: airline network, hub airport, multi-objective optimization, robust optimization, genetic algorithm

中图分类号:

F560

黄佳,王庆云. 基于多目标遗传算法的枢纽航线网络的鲁棒优化方法[J]. 交通运输系统工程与信息, 2009, 9(3): 86-92 .

HUANG Jia, WANG Qing-yun. Robust Optimization of Hub-and-Spoke Airline Network Design Based on Multi-Objective Genetic Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2009, 9(3): 86-92 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17816.shtml

http://www.tseit.org.cn/CN/Y2009/V9/I3/86

参考文献

[1]姜涛，朱金福. 非严格的中枢辐射航线网络设计的鲁棒优化方法[J]. 信息与控制，2007，5(36): 537-545.[JIANG T，ZHU J F. Robust optimization of nonstrict hub and spoke airline network design[J]. Information and Control, 2007，5(36): 537-545.]

[2]姜涛，朱金福. 航空公司选择枢纽机场的鲁棒优化方法[J]. 系统工程，2006, 6(24): 13-17.[JIANG T，ZHU J F. Robust optimization for airline company to select hub airports[J]. System Engineering. 2006, 6(24): 13-17.]

[3]柏明国，朱金福，徐进. P-枢纽航线网络设计问题的一种启发式算法[J]. 运筹与管理，2007, 4(16): 64-68.[BO M G, ZHU J F, XU J. A heuristic algorithm on p-hub airline network design problem[J]. Operations Research and Management Science, 2007, 4(16): 64-68.]

[4] Averbakh I. On the complexity of a class of combinatorial optimization problems with uncertainty[J].Math.Program 2001, 2(90): 263-272.

[5] Kasperski A, Zielinski P. An approximation algorithm for interval data minmax regret combinatorial optimization problems[J]. Information Processing Letters, 2006, 5(97): 177-180.

[6] 邹秀芬，刘敏忠，吴志健，等. 解约束多目标优化问题的一种鲁棒的进化算法[J]. 计算机研究与发展, 2004, 6(41): 987-990.[ZOU J F, LIU M Z, WU Z J, et al. A robust evolutionary algorithm for constrained multi-objective optimization problems[J]. Journal of Computer Research and Development, 2004, 6(41): 987-990.]

[7] Kalyanmoy D. Multi-objective optimization using evolutionary algorithms[M]. John Wiley＆ Sons，Inc，New York, 2001: 12-38．

[8] Knowles J D，Come D W．Approximating the non-dominated front using the pareto archived evolutionary strategy[J]. Evolutionary Computation, 2000, 8(2): 149-172．

[9] Rudolph G, Agapie A. Convergence properties of some multi-objective evolutionary algorithms[C]//. Proceeding of the IEEE Congress on Evolutionary Computation. 2000(2): 1010-1016.

[10]Iosifescu M. Finite markov processes and their applications[M]. Wiley, UK,1980.

[11]李敏强，寇纪凇，林丹．遗传算法的基本原理与应用[M]．北京:科学出版社,2003．[LI M Q, KOU J S, LIN D. The basic principle and application of genetic algorithm

[M]. Beijing :Science Press, 2003.]

[1]	刘忠波, 王淇娴, 郑红星. 海空协同的远海岛礁战储物资供给优化模型与算法[J]. 交通运输系统工程与信息, 2022, 22(2): 268-279.
[2]	张培文, 杜福民, 汪瑜. 基于链路预测的中小机场连接机制研究[J]. 交通运输系统工程与信息, 2022, 22(2): 298-304.
[3]	靳志宏, 焉红, 王小寒, 邢磊, 徐奇. 滚装甩挂运输牵引车调度优化及作业模式类比分析[J]. 交通运输系统工程与信息, 2022, 22(1): 142-151.
[4]	薛运强, 郭军, 钟蒙, 安静. 基于不确定理论的常规公交车辆调度优化[J]. 交通运输系统工程与信息, 2021, 21(6): 115-122.
[5]	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
[6]	杨华龙, 赵帅奇, 方旭, 段静茹. 考虑海上意外时间和合作协议的班轮运输船期设计鲁棒优化[J]. 交通运输系统工程与信息, 2021, 21(6): 210-216.
[7]	吕彪, 管心怡, 高自强. 地铁网络服务韧性评估与最优恢复策略[J]. 交通运输系统工程与信息, 2021, 21(5): 198-205.
[8]	楚金华, 李俊鹤, 王春娟, 陈超. 排放控制区下集装箱班轮航线路径规划与航速调度集成决策[J]. 交通运输系统工程与信息, 2021, 21(4): 230-238.
[9]	赵旭，张汇妍，黄瑞. 节点中断与需求不确定下的港口供应链整合[J]. 交通运输系统工程与信息, 2021, 21(3): 34-39.
[10]	徐智勇. 铁路电分相布设及纵断面协同优化研究[J]. 交通运输系统工程与信息, 2021, 21(3): 170-175.
[11]	刘显贵, 王晖年, 洪经纬, 郝雷. 网联环境下信号交叉口车速控制策略及优化[J]. 交通运输系统工程与信息, 2021, 21(2): 82-90.
[12]	汪茜，柏赟，李佳杰，朱巧珍，冯旭杰. 城市轨道交通地下线车站选址与平面线形优化[J]. 交通运输系统工程与信息, 2021, 21(2): 119-125.
[13]	尚春琳，刘小明，田玉林，董路熙，唐少虎. 基于分级多目标决策的干线公交速度引导模型[J]. 交通运输系统工程与信息, 2021, 21(2): 145-150.
[14]	薛守强，宋瑞，安久煜，王攸妙. 感知乘客心理的出租车动态合乘优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 205-210.
[15]	卢天伟，姚恩建，杨扬，郇宁，陈琳. 考虑弹性需求的城市枢纽间多方式时刻表优化[J]. 交通运输系统工程与信息, 2021, 21(1): 16-22.