Research on Shift Generation of Foreign Airlines Service Personnel Based on Tabu Search Algorithm
-
摘要: 针对机场外航服务人员班型生成面临的任务量大，约束条件复杂，人工生成班型方案困难等问题背景，考虑员工对任务具有层次资质，班型的各类劳动法规等约束条件，以最小化班型方案总工作时间为优化目标，研究构建了面向多任务层次资质场景下的班型生成优化模型，并设计禁忌搜索算法进行求解。在首都机场外航服务部实际排班数据集上进行实验，验证了模型和算法的实用性和有效性，实验结果表明，求得的班型方案相比较现有人工生成的班型方案，能满足所有约束条件且总工作时间更短，总服务人数更少，提高了机场资源利用率。Abstract: To solve the problem for the large amount of tasks, complex constraint conditions and manual which is hard to generation shifts of airport foreign airline service personnel. A shift generation model is studied and constructed for multi-task hierarchical qualification which including employees have hierarchical qualifications for tasks and shift needs to meet all kinds of labor laws and regulations and others constraints to minimize the total working time of shifts for optimum. Tabu search algorithm is designed to solve the model. Experiments, based on the actual scheduling data set of the foreign airlines service department of capital airport, verify the practicability and effectiveness of the model and the algorithm. The results show that compared to the existing manual shifts schemes, shifts obtained by using the model can fulfill all constraint conditions, shorten the total working time, reduce the number of employees and improve the utilization rate of airport resources.
-
表 2 复制以后的等价任务
星期 航班号 开始
时间结束
时间需组长
人数需控制人员
人数需普通人员
人数1 GA891 5:40 8:50 1 0 0 1 GA891 5:40 8:50 0 1 0 1 GA891 5:40 8:50 0 0 1 1 GA891 5:40 8:50 0 0 1 1 GA891 5:40 8:50 0 0 1 
下载: 导出CSV
表 3 排班任务信息数据表
星期 航班号 开始
时间结束
时间需组长
人数需控制人员
人数需普通人员
人数1 GA891 5:40 8:50 1 1 3 1 KE856 9:00 14:15 1 1 3 1 JS152 9:30 12:55 1 1 2 $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $
下载: 导出CSV
表 4 员工资质信息数据表示例
员工姓名 航空公司类型 AA KE SU GA PK J2 IR 7C VN JS 李晓敏 0 2 0 1 0 0 0 2 2 2 曹曦月 0 2 0 2 0 0 0 2 1 2 李艳香 2 0 0 3 0 0 0 0 3 1 $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $
下载: 导出CSV
表 5 班型方案示例表
星期 到岗时间 离岗时间 保障任务集合(航班号)及资质要求 1 7:50 11:45 KE880/1 SU2852/2 1 5:00 10:10 J2067/1 AA186/1 1 5:20 14:15 PK852/2 KE856/1 $ \vdots $ $ \vdots $ $ \vdots $ $ \vdots $
下载: 导出CSV
表 6 与人工班型对比结果
星期 总服务时间(h) 总服务人数(人) 人工方案 本文模型 人工方案 本文模型 1 462.13 444.41 63 62 2 338.71 318.33 54 44 3 415.36 361.50 54 50 4 315.47 299.41 52 45 5 424.67 395.00 60 47 6 375.49 345.16 47 44 7 352.31 313.08 51 45
下载: 导出CSV
表 7 班型服务时长统计(%)
算法 班型服务时长区间(h) [0,6) [6,9] (9,11] (11,13] 人工班型方案 25.56 39.06 26.55 3.14 本文模型生成的班型方案 35.60 49.55 14.84 0
下载: 导出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)
计量
- 文章访问数: 2756
- HTML全文浏览量: 900
- PDF下载量: 41
- 被引次数: 0
