高级搜索

基于禁忌搜索算法的机场外航服务人员班型生成研究

冯霞 唐菱 卢敏

引用本文: 冯霞, 唐菱, 卢敏. 基于禁忌搜索算法的机场外航服务人员班型生成研究[J]. 电子与信息学报, 2019, 41(11): 2715-2721. doi: 10.11999/JEIT181196 shu
Citation:  Xia FENG, Ling TANG, Min LU. Research on Shift Generation of Foreign Airlines Service Personnel Based on Tabu Search Algorithm[J]. Journal of Electronics and Information Technology, 2019, 41(11): 2715-2721. doi: 10.11999/JEIT181196 shu

基于禁忌搜索算法的机场外航服务人员班型生成研究

    作者简介: 冯霞: 女,1970年生,教授,研究方向为数据挖掘,民航信息智能处理;
    唐菱: 女,1994年生,硕士生,研究方向为数据挖掘;
    卢敏: 男,1985年生,讲师,研究方向为机器学习、凸优化
    通讯作者: 唐菱,tacytang@163.com
  • 基金项目: 国家自然科学基金(61502499),中国民航科技创新引导基金项目重大专项(MHRD20140105),中山大学机器智能与先进计算教育部重点实验室开放基金(MSC-201704A),中央高校基本科研业务费科研专项(3122015D015)

摘要: 针对机场外航服务人员班型生成面临的任务量大,约束条件复杂,人工生成班型方案困难等问题背景,考虑员工对任务具有层次资质,班型的各类劳动法规等约束条件,以最小化班型方案总工作时间为优化目标,研究构建了面向多任务层次资质场景下的班型生成优化模型,并设计禁忌搜索算法进行求解。在首都机场外航服务部实际排班数据集上进行实验,验证了模型和算法的实用性和有效性,实验结果表明,求得的班型方案相比较现有人工生成的班型方案,能满足所有约束条件且总工作时间更短,总服务人数更少,提高了机场资源利用率。

English

    1. [1]

      KYNGÄS N, NURMI K, KYNGÄS J, et al. Solving the person-based multitask shift generation problem with breaks[C]. The 5th International Conference on Modeling, Simulation and Applied Optimization, Hammamet, Tunisia, 2013: 1–8.

    2. [2]

      BRUCKER P, QU Rong, and BURKE E. Personnel scheduling: Models and complexity[J]. European Journal of Operational Research, 2011, 210(3): 463–473. doi: 10.1016/j.ejor.2010.11.017

    3. [3]

      REID K N, LI Jingpeng, SWAN J, et al. Variable neighbourhood search: A case study for a highly-constrained workforce scheduling problem[C]. 2016 IEEE Symposium Series on Computational Intelligence, Athens, Greece, 2016: 1–6.

    4. [4]

      ERNST AT, JIANG H, KRISHNAMOORTHY M, et al. Staff scheduling and rostering: A review of applications, methods and models[J]. European Journal of Operational Research, 2002, 153(1): 3–27. doi: 10.1016/s0377-2217(03)00095-x

    5. [5]

      MA Jinghua, CHEN H H, SONG Lingyang, et al. Residential load scheduling in smart grid: A cost efficiency perspective[J]. IEEE Transactions on Smart Grid, 2016, 7(2): 771–784. doi: 10.1109/TSG.2015.2419818

    6. [6]

      PENG Kunkun and SHEN Yindong. Hybrid variable neighbourhood search for multi-objective bus driver rostering[J]. Journal of Computational and Theoretical Nanoscience, 2016, 13(6): 3989–3996. doi: 10.1166/jctn.2016.5238

    7. [7]

      PENG Kunkun and SHEN Yindong. An evolutionary algorithm based on grey relational analysis for crew scheduling[J]. Journal of Grey System, 2016, 28(3): 75–88.

    8. [8]

      YAGHINI M, KARIMI M, and RAHBAR M. A set covering approach for multi-depot train driver scheduling[J]. Journal of Combinatorial Optimization, 2015, 29(3): 636–654. doi: 10.1007/s10878-013-9612-1

    9. [9]

      RAHIMIAN E, AKARTUNALI K, and LEVINE J. A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems[J]. European Journal of Operational Research, 2016, 258(2): 411–423. doi: 10.1016/j.ejor.2016.09.030

    10. [10]

      ZAMORANO E, BECKER A, and STOLLETZ R. Task assignment with start time-dependent processing times for personnel at check-in counters[J]. Journal of Scheduling, 2018, 21(1): 93–109. doi: 10.1007/s10951-017-0523-3

    11. [11]

      ZEREN B and ÖZKOL I. A novel column generation strategy for large scale airline crew pairing problems[J]. Expert Systems with Applications, 2016, 55: 133–144. doi: 10.1016/j.eswa.2016.01.045

    12. [12]

      CHURCH R L and REVELLE C S. Theoretical and computational links between the p-median, location set-covering, and the maximal covering location problem[J]. Geographical Analysis, 1976, 8(4): 406–415. doi: 10.1111/j.1538-4632.1976.tb00547.x

    13. [13]

      XIA Yangkun, FU Zhuo, PAN Lijun, et al. Tabu search algorithm for the distance-constrained vehicle routing problem with split deliveries by order[J]. PLoS One, 2018, 13(5): e0195457. doi: 10.1371/journal.pone.0195457

    14. [14]

      BU Henan, YAN Zhuwen, ZHANG Dianhua, et al. Application of case-based reasoning-Tabu search hybrid algorithm for rolling schedule optimization in tandem cold rolling[J]. Engineering Computations, 2018, 35(1): 187–201. doi: 10.1108/EC-02-2017-0054

    15. [15]

      MONTANÉ F A T and GALVÃO R D. A Tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computers & Operations Research, 2006, 33(3): 595–619. doi: 10.1016/j.cor.2004.07.009

    1. [1]

      卢敏, 王莉, 唐菱. 基于Block Gibbs的航空公司外航服务人员排班算法. 电子与信息学报, 2018, 40(10): 2513-2520.

    2. [2]

      陆阳, 骆立俊, 邹采荣, 何振亚. 一种运动估计的快速预测搜索算法. 电子与信息学报, 1998, 20(5): 591-596.

    3. [3]

      田菁, 陈岩, 沈林成. 不确定环境中多无人机协同搜索算法. 电子与信息学报, 2007, 29(10): 2325-2328.

    4. [4]

      苏志刚, 彭应宁, 王秀坛. 三维目标曲线SAR成像的降维搜索算法. 电子与信息学报, 2006, 28(6): 965-968.

    5. [5]

      梁淮宁, 王建国, 黄顺吉. 快速搜索算法与极化合成孔径雷达三维成像. 电子与信息学报, 2002, 24(5): 584-590.

    6. [6]

      徐润生, 张卫东, 许晓鸣, 陆哲明. 一种改进的矢量量化码字搜索算法. 电子与信息学报, 2002, 24(5): 604-609.

    7. [7]

      于勇, 郭雷. 噪声图像中提取边缘的蚁群搜索算法. 电子与信息学报, 2008, 30(6): 1271-1275.

    8. [8]

      邹卫霞, 杜光龙, 李斌, 崔志芳, 胡玉聪, 张芳. 60 GHz毫米波通信中一种新的波束搜索算法. 电子与信息学报, 2012, 34(3): 683-688.

    9. [9]

      唐宏, 王惠珠. 基于无线信号不规则性的无线传感网层次型拓扑控制算法. 电子与信息学报, 2015, 37(9): 2246-2253.

    10. [10]

      许宁, 尤红建, 耿修瑞, 曹银贵. 基于光谱相似度量的高光谱图像多任务联合稀疏光谱解混方法. 电子与信息学报, 2016, 38(11): 2701-2708.

    11. [11]

      张水平, 林平平, 巫光福, 江林伟. 基于可变拟阵搜索算法构造码率为1/p的二进制系统准循环码. 电子与信息学报, 2016, 38(11): 2916-2921.

    12. [12]

      贾艳艳, 胡予濮, 高军涛. 对比特搜索生成器的猜测确定攻击. 电子与信息学报, 2010, 32(12): 2925-2929.

    13. [13]

      和华, 杜兰, 徐丹蕾, 刘宏伟. 基于多任务复数因子分析模型的雷达高分辨距离像识别方法. 电子与信息学报, 2015, 37(10): 2307-2313.

    14. [14]

      赵文波, 柳健, 李小文. 一种支持多星多任务遥感卫星地面系统综合处理的运行控制技术. 电子与信息学报, 2005, 27(6): 919-923.

    15. [15]

      袁亚洲, 孙小芹, 李岳峰, 关新平. 基于先验特征的矿下人员定位校准方法. 电子与信息学报, 2018, 40(6): 1323-1329.

    16. [16]

      涂开辉, 黄志洪, 侯峥嵘, 杨海钢. 基于配置模式匹配和层次化映射结构的高效FPGA码流生成系统研究. 电子与信息学报, 2019, 41(11): 2585-2591.

    17. [17]

      陈东, 沈振康, 李飚, 刘文华, 王炜华, 李吉成. 一个基于神经网络的航空照片自动目标识别算法. 电子与信息学报, 2001, 23(7): 722-725.

    18. [18]

      谷阳, 宋千, 李杨寰, 马明, 周智敏. 基于惯性鞋载传感器的人员自主定位粒子滤波方法. 电子与信息学报, 2015, 37(2): 484-488.

    19. [19]

      胡光岷, 李乐民, 安红岩. 动态多播最小生成树算法. 电子与信息学报, 2003, 25(1): 88-93.

    20. [20]

      周映虹, 马争鸣. 基于层次模型的重要性编码算法. 电子与信息学报, 2009, 31(6): 1497-1500.

  • 图 1  插入移动

    图 2  交换移动

    图 3  禁忌搜索算法流程图

    图 4  算法有效性分析

    表 1  原始任务

    星期航班号开始
    时间
    结束
    时间
    需组长
    人数
    需控制人员
    人数
    需普通人员
    人数
    1GA8915:408:50113
    下载: 导出CSV

    表 2  复制以后的等价任务

    星期航班号开始
    时间
    结束
    时间
    需组长
    人数
    需控制人员
    人数
    需普通人员
    人数
    1GA8915:408:50100
    1GA8915:408:50010
    1GA8915:408:50001
    1GA8915:408:50001
    1GA8915:408:50001
    下载: 导出CSV

    表 3  排班任务信息数据表

    星期航班号开始
    时间
    结束
    时间
    需组长
    人数
    需控制人员
    人数
    需普通人员
    人数
    1GA8915:408:50113
    1KE8569:0014:15113
    1JS1529:3012:55112
    $ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $
    下载: 导出CSV

    表 4  员工资质信息数据表示例

    员工姓名航空公司类型
    AAKESUGAPKJ2IR7CVNJS
    李晓敏0201000222
    曹曦月0202000212
    李艳香2003000031
    $ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $
    下载: 导出CSV

    表 5  班型方案示例表

    星期到岗时间离岗时间保障任务集合(航班号)及资质要求
    17:5011:45KE880/1 SU2852/2
    15:0010:10J2067/1 AA186/1
    15:2014:15PK852/2 KE856/1
    $ \vdots $$ \vdots $$ \vdots $$ \vdots $
    下载: 导出CSV

    表 6  与人工班型对比结果

    星期总服务时间(h)总服务人数(人)
    人工方案本文模型人工方案本文模型
    1462.13444.416362
    2338.71318.335444
    3415.36361.505450
    4315.47299.415245
    5424.67395.006047
    6375.49345.164744
    7352.31313.085145
    下载: 导出CSV

    表 7  班型服务时长统计(%)

    算法班型服务时长区间(h)
    [0,6)[6,9](9,11](11,13]
    人工班型方案25.5639.0626.553.14
    本文模型生成的班型方案35.6049.5514.840
    下载: 导出CSV
  • 加载中
图(4)表(7)
计量
  • PDF下载量:  14
  • 文章访问数:  712
  • HTML全文浏览量:  434
文章相关
  • 通讯作者:  唐菱, tacytang@163.com
  • 收稿日期:  2019-01-03
  • 录用日期:  2019-04-17
  • 网络出版日期:  2019-05-21
  • 刊出日期:  2019-11-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章