基于改进遗传算法的航空运输路径优化问题研究  

Research on air transportation route optimization based on improved genetic algorithm

作　　者：先梦瑜[1] XIAN Meng-yu(Xi’an Aeronautical Polytechnic Institute,Xi'an 710089,China)

机构地区：[1]西安航空职业技术学院,陕西西安710089

出　　处：《电子设计工程》2020年第15期101-105,共5页Electronic Design Engineering

基　　金：陕西省教育厅规划项目(SGH17V013)。

摘　　要：针对航空物流领域对路径进行精确计算以降低配送成本的需求,文中对路径的优化方法进行了研究。通过建模分析,将该问题被抽象为数学中的枢纽位置问题(HLP),然后使用遗传算法进行求解。为了解决大规模的复杂HLP,文中对传统的遗传算法进行了改进,将单一种群的遗传算法扩展成双种群模式。通过为两个种群设置不同的进化参数,从而保证最终胜出的个体具备更优秀的搜索能力。此外,为防止遗传个体在搜索时陷入局部最优解,还引入了模拟退火算法中Metropolis准则。为了衡量改进后的算法性能(I-SGA),文中基于航空公司的实际航线和15个大中城市机场的实际规模等相关数据进行了仿真测试。仿真结果表明,I-SGA的目标函数最优收敛值为1.234 e+12,平均收敛值为1.100 e+12;而SGA的最优收敛值为1.201 e+12,平均收敛值为1.021 e+12,所提算法的效果和效率均有明显的提升。Aiming at the demand of reducing the distribution cost in the field of air logistics,this paper studies the optimization method of air logistics path.Through modeling analysis,the problem is abstracted as the hub location problem(HLP)in mathematics.Because of the complexity of the problem,this paper improves the traditional genetic algorithm,and expands the single population genetic algorithm to the dual population model.In addition,in order to prevent the genetic individuals from falling into the local optimal solution,the Metropolis criterion of simulated annealing algorithm is introduced.Finally,in order to measure the performance of the improved algorithm(I-SGA),the simulation is based on the actual routes of airlines and the actual scale of 15 airports in China’s large and medium-sized cities.The simulation results show that the optimal convergence value of the objective function of I-SGA is 1.234 e+12 and the average convergence value is 1.100 e+12.The effect and efficiency of the algorithm are obviously improved.

关 键 词：遗传算法 航空运输 物流路径 优化算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]