基于禁忌搜索算法的機場外航服務人員班型生成研究

馮霞; 唐菱; 盧敏

doi:10.11999/JEIT181196

基于禁忌搜索算法的機場外航服務人員班型生成研究

doi: 10.11999/JEIT181196

馮霞^{1, 2},
唐菱^{1, 2, ,},
盧敏^{1, 2, 3}

1.
中國民航大學計算機科學與技術學院天津 300300
2.
中國民航大學信息技術科研基地天津 300300
3.
中山大學機器智能與先進計算教育部重點實驗室 ??廣州 ??510275

基金項目: 國家自然科學基金(61502499)，中國民航科技創(chuàng)新引導基金項目重大專項(MHRD20140105)，中山大學機器智能與先進計算教育部重點實驗室開放基金(MSC-201704A)，中央高?；究蒲袠I(yè)務費科研專項(3122015D015)

詳細信息

作者簡介:
馮霞：女，1970年生，教授，研究方向為數(shù)據(jù)挖掘，民航信息智能處理

唐菱：女，1994年生，碩士生，研究方向為數(shù)據(jù)挖掘

盧敏：男，1985年生，講師，研究方向為機器學習、凸優(yōu)化

通訊作者:
唐菱　tacytang@163.com

中圖分類號: TP311
計量
- 文章訪問數(shù): 2822
- HTML全文瀏覽量: 954
- PDF下載量: 43
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-01-03
- 修回日期: 2019-04-17
- 網絡出版日期: 2019-05-21
- 刊出日期: 2019-11-01

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

Xia FENG^{1, 2},
Ling TANG^{1, 2
, ,},
Min LU^{1, 2, 3}

1.
College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China
2.
Information Technology Research Base of CAAC, Civil Aviation University of China, Tianjin 300300, China
3.
Key Laboratory of Machine Intelligence and Advanced Computing, Sun Yat-sen University, Guangzhou 510275, China

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)

摘要

摘要: 針對機場外航服務人員班型生成面臨的任務量大，約束條件復雜，人工生成班型方案困難等問題背景，考慮員工對任務具有層次資質，班型的各類勞動法規(guī)等約束條件，以最小化班型方案總工作時間為優(yōu)化目標，研究構建了面向多任務層次資質場景下的班型生成優(yōu)化模型，并設計禁忌搜索算法進行求解。在首都機場外航服務部實際排班數(shù)據(jù)集上進行實驗，驗證了模型和算法的實用性和有效性，實驗結果表明，求得的班型方案相比較現(xiàn)有人工生成的班型方案，能滿足所有約束條件且總工作時間更短，總服務人數(shù)更少，提高了機場資源利用率。
- 航空運輸 /
- 班型生成 /
- 禁忌搜索算法 /
- 人員排班 /
- 多任務層次資質
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.
- Air transportation /
- Shift generation /
- Tabu search algorithm /
- Staff scheduling /
- Multiple tasks and hierarchical qualifications

HTML全文

圖 1 插入移動

下載: 全尺寸圖片幻燈片

圖 2 交換移動

下載: 全尺寸圖片幻燈片

圖 3 禁忌搜索算法流程圖

下載: 全尺寸圖片幻燈片

圖 4 算法有效性分析

下載: 全尺寸圖片幻燈片

表 1 原始任務

星期	航班號	開始時間	結束時間	需組長人數(shù)	需控制人員人數(shù)	需普通人員人數(shù)
1	GA891	5:40	8:50	1	1	3

下載: 導出CSV

表 2 復制以后的等價任務

星期	航班號	開始時間	結束時間	需組長人數(shù)	需控制人員人數(shù)	需普通人員人數(shù)
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 排班任務信息數(shù)據(jù)表

星期	航班號	開始時間	結束時間	需組長人數(shù)	需控制人員人數(shù)	需普通人員人數(shù)
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 員工資質信息數(shù)據(jù)表示例

員工姓名	航空公司類型
員工姓名	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)		總服務人數(shù)(人)
星期	人工方案	本文模型	人工方案	本文模型
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 班型服務時長統(tǒng)計(%)

算法	班型服務時長區(qū)間(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

參考文獻(15)

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

施引文獻

資源附件(0)

訪問統(tǒng)計