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

交通运输系统工程与信息 ›› 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]. 交通运输系统工程与信息, 2025, 25(6): 101-108.
[2]	刘斌, 赵靳辉, 田志强, 马超凡, 梁辉, 李和壁. 基于灵活编组的城市轨道交通大小交路列车开行方案优化[J]. 交通运输系统工程与信息, 2025, 25(6): 143-152.
[3]	闫菲, 姚向明, 韩梅, 陈超, 赵鹏. 跨线运营模式下城轨列车运行图协同编制模型[J]. 交通运输系统工程与信息, 2025, 25(6): 165-174.
[4]	高万晨, 路世昌, 赵娅彤, 刘锴. 考虑分段充电策略的电动公交时刻表和车辆调度整体优化[J]. 交通运输系统工程与信息, 2025, 25(6): 239-248.
[5]	胡宝雨, 刘文磊, 程国柱. 区间重叠下多线公交车辆调度和泊位设置联合优化[J]. 交通运输系统工程与信息, 2025, 25(6): 249-264.
[6]	张志坚, 张婷, 邸振, 郭军华. 考虑碳排放成本的轻型载货汽车-公交车协同配送问题优化[J]. 交通运输系统工程与信息, 2025, 25(6): 265-275.
[7]	程佳豪, 郝志丹, 李国旗, 刘思婧. 卡车-冲锋舟协同的山区洪灾应急物资配送多目标优化[J]. 交通运输系统工程与信息, 2025, 25(6): 294-304.
[8]	王彦, 王则恺, 宋美霞, 方力萱. 中转时间不确定下冷藏集装箱多式联运路径优化研究[J]. 交通运输系统工程与信息, 2025, 25(5): 124-134.
[9]	田帅辉, 陈安琪, 孙家正, 王柯杰, 张恒博. 考虑枢纽点失效的多分配多式联运快递网络优化[J]. 交通运输系统工程与信息, 2025, 25(5): 145-157.
[10]	刘长石, 万城, 王凤, 陈宝玺, 岳俊羽. 基于救援效用的洪灾物资配送与灾民转移路径规划[J]. 交通运输系统工程与信息, 2025, 25(5): 320-332.
[11]	杜婧涵, 李佳祥, 程擎, 朱新平, 尹嘉男, 张魏宁. 融合经济性与鲁棒性的多目标停机位动态分配方法[J]. 交通运输系统工程与信息, 2025, 25(4): 326-336.
[12]	郭姝娟, 许骁, 刘智, 董彦鹭, 华梦颖, 彭康真. 考虑东北海陆大通道的中欧多式联运路径选择研究[J]. 交通运输系统工程与信息, 2025, 25(3): 32-43.
[13]	刘长石, 万城, 王凤, 刘光洪, 陈宝玺. 洪涝灾害下考虑受灾点差异的应急物资分配-配送优化[J]. 交通运输系统工程与信息, 2025, 25(3): 335-345.
[14]	龚帅宇, 徐行方, 鲁玉. 省域铁路成网条件下列车开行方案优化[J]. 交通运输系统工程与信息, 2025, 25(2): 282-292.
[15]	高攀, 黄柳森, 赵旭. 考虑转港调度的内河港口群多泊位联合配置策略[J]. 交通运输系统工程与信息, 2025, 25(2): 328-337.