高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

冯霞 唐菱 卢敏

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

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

doi: 10.11999/JEIT181196
基金项目: 国家自然科学基金(61502499),中国民航科技创新引导基金项目重大专项(MHRD20140105),中山大学机器智能与先进计算教育部重点实验室开放基金(MSC-201704A),中央高校基本科研业务费科研专项(3122015D015)
详细信息
    作者简介:

    冯霞:女,1970年生,教授,研究方向为数据挖掘,民航信息智能处理

    唐菱:女,1994年生,硕士生,研究方向为数据挖掘

    卢敏:男,1985年生,讲师,研究方向为机器学习、凸优化

    通讯作者:

    唐菱 tacytang@163.com

  • 中图分类号: TP311

Research on Shift Generation of Foreign Airlines Service Personnel Based on Tabu Search Algorithm

Funds: The National Natural Science Foundation of China (61502499), The Civil Aviation Key Technologies R&D Program of China (MHRD20140105), The Open Project in Key Laboratory of Machine Intelligence and Advanced Computing of the Ministry of Education (Sun Yat-sen University) (MSC-201704A), The Fundamental Research Funds for the Central Universities of China (3122015D015)
  • 摘要: 针对机场外航服务人员班型生成面临的任务量大,约束条件复杂,人工生成班型方案困难等问题背景,考虑员工对任务具有层次资质,班型的各类劳动法规等约束条件,以最小化班型方案总工作时间为优化目标,研究构建了面向多任务层次资质场景下的班型生成优化模型,并设计禁忌搜索算法进行求解。在首都机场外航服务部实际排班数据集上进行实验,验证了模型和算法的实用性和有效性,实验结果表明,求得的班型方案相比较现有人工生成的班型方案,能满足所有约束条件且总工作时间更短,总服务人数更少,提高了机场资源利用率。
  • 图  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
  • 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.
    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
    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.
    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
    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
    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
    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.
    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
    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
    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
    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
    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
    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
    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
    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
  • 加载中
图(4) / 表(7)
计量
  • 文章访问数:  2806
  • HTML全文浏览量:  945
  • PDF下载量:  43
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-01-03
  • 修回日期:  2019-04-17
  • 网络出版日期:  2019-05-21
  • 刊出日期:  2019-11-01

目录

    /

    返回文章
    返回