高级搜索

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

冯霞 唐菱 卢敏

引用本文: 冯霞, 唐菱, 卢敏. 基于禁忌搜索算法的机场外航服务人员班型生成研究[J]. 电子与信息学报, 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, 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]. Proceedings of 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]. Proceedings of 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]

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

    2. [2]

      杨善超田康生刘仁争郑玉军. 基于价值优化的相控阵雷达任务调度算法. 电子与信息学报, doi: 10.11999/JEIT190147

    3. [3]

      钱亚冠卢红波纪守领周武杰吴淑慧云本胜陶祥兴雷景生. 基于粒子群优化的对抗样本生成算法. 电子与信息学报, doi: 10.11999/JEIT180777

    4. [4]

      徐金甫吴缙李军伟曲彤洲董永兴. 基于敏感度混淆机制的控制型物理不可克隆函数研究. 电子与信息学报, doi: 10.11999/JEIT180775

    5. [5]

      张国雯高军曹祥玉杨欢欢李思佳. 基于三种反射型单元共享孔径的新型宽带低RCS反射屏设计. 电子与信息学报, doi: 10.11999/JEIT181049

    6. [6]

      牛淑芬王金风王伯彬贾向东杜小妮. 区块链上基于B+树索引结构的密文排序搜索方案. 电子与信息学报, doi: 10.11999/JEIT190038

    7. [7]

      张玉磊刘文静刘祥震张永洁王彩芬. 基于授权的多服务器可搜索密文策略属性基加密方案. 电子与信息学报, doi: 10.11999/JEIT180944

    8. [8]

      任炯炯李航陈少真. 减轮Simeck算法的积分攻击. 电子与信息学报, doi: 10.11999/JEIT180849

    9. [9]

      李云唐英刘涵霄. 基于Q-Learning算法的毫微微小区功率控制算法. 电子与信息学报, doi: 10.11999/JEIT181191

    10. [10]

      梁春燕袁文浩李艳玲夏斌孙文珠. 基于判别邻域嵌入算法的说话人识别. 电子与信息学报, doi: 10.11999/JEIT180761

    11. [11]

      陈鸿昶谢天高超李邵梅黄瑞阳. 候选标记信息感知的偏标记学习算法. 电子与信息学报, doi: 10.11999/JEIT181059

    12. [12]

      李林王林韩红霞姬红兵江莉. 自适应时频同步压缩算法研究. 电子与信息学报, doi: 10.11999/JEIT190146

    13. [13]

      王琼罗亚洁李思舫. 基于分段循环冗余校验的极化码自适应连续取消列表译码算法. 电子与信息学报, doi: 10.11999/JEIT180716

    14. [14]

      韦永壮史佳利李灵琛. LiCi分组密码算法的不可能差分分析. 电子与信息学报, doi: 10.11999/JEIT180729

    15. [15]

      于洪涛丁悦航刘树新黄瑞阳谷允捷. 一种基于超节点理论的本体关系消冗算法. 电子与信息学报, doi: 10.11999/JEIT180793

    16. [16]

      张小恒李勇明王品曾孝平颜芳张艳玲承欧梅. 基于语音卷积稀疏迁移学习和并行优选的帕金森病分类算法研究. 电子与信息学报, doi: 10.11999/JEIT180792

    17. [17]

      蒲磊冯新喜侯志强余旺盛. 基于空间可靠性约束的鲁棒视觉跟踪算法. 电子与信息学报, doi: 10.11999/JEIT180780

    18. [18]

      丛雯珊余岚沃江海. 基于粒子群算法的宽带真延时方向图栅瓣抑制方法. 电子与信息学报, doi: 10.11999/JEIT180719

    19. [19]

      徐保庆赵永波庞晓娇. 基于实值处理的联合波束域双基地MIMO雷达测角算法. 电子与信息学报, doi: 10.11999/JEIT180766

    20. [20]

      刘小龙. 改进多元宇宙算法求解大规模实值优化问题. 电子与信息学报, doi: 10.11999/JEIT180751

  • 图 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下载量:  6
  • 文章访问数:  211
  • HTML全文浏览量:  120
  • 引证文献数: 0
文章相关
  • 通讯作者:  唐菱, tacytang@163.com
  • 收稿日期:  2019-01-03
  • 录用日期:  2019-04-17
  • 网络出版日期:  2019-05-21
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章