机场任务指派问题的优化方案研究

doi:10.12005/orms.2019.0241

运筹与管理 ›› 2019, Vol. 28 ›› Issue (11): 1-8.DOI: 10.12005/orms.2019.0241

• 理论分析与方法探讨 • 下一篇

机场任务指派问题的优化方案研究

田倩南¹, 李昆鹏¹, 李文莉¹, 徐东洋²

1.华中科技大学管理学院,湖北武汉 430074;
2.河南大学商学院,河南开封 475004

收稿日期:2018-01-19 出版日期:2019-11-25
作者简介:田倩南(1989-),女,河南驻马店人,博士研究生,研究方向:航线优化问题、车辆路径问题;李昆鹏(1978-),男,湖北武汉人,教授,博士,研究方向:物流与供应链与管理、生产运作管理; 李文莉(1992-),女,河南周口人,博士研究生,研究方向:物流路径优化;徐东洋(1988-),男,河南驻马店人,讲师,博士,研究方向:物流与供应链管理、生产运作管理。
基金资助:
国家自然科学基金面上项目(71372133)

Research on Optimization of Airport Task Assignment Problem

TIAN Qian-nan¹, LI Kun-peng¹, LI Wen-li¹, XU Dong-yang²

1. School of Management, Huazhong University of Science & Technology, Wuhan 430074, China;
2. School of Business, Henan University, Kaifeng 475004, China

Received:2018-01-19 Online:2019-11-25

摘要/Abstract

摘要： 本文研究了机场任务指派问题,该问题是指将具有特殊属性的任务指派给有限数量的班次。由于机场任务和班次属性的多样性,机场任务指派问题是一个复杂的组合优化问题,属于NP-完全问题。本文以任务完成产生的效益总和最大化为目标建立数学优化模型,提出有效不等式,应用CPLEX软件对实际数据进行求解,结果表明,CPLEX可以在较短时间内对一定规模的算例求得最优解。同时对影响目标函数的四个因素:任务数量、班次数量、班次工作时长和任务属性分别进行分析,通过实际算例测试对比,得出具有指导意义的结论,即根据机场特征分别调整四个因素不仅能够提高机场资源的有效利用率,而且能够提高机场的运行效率和服务水平。

关键词: 机场任务指派, NP-完全问题, 地勤服务, 有效不等式

Abstract: Airports are one of the biggest complexes we humans operate on the earth. For aircraft to land and take off safely and yet on schedule, there are so many tasks to perform by ground staffs. Luckily, most of the tasks can be pre-defined ahead of times, according to the flight schedules and aircraft types. Airport ground staffs work in shifts to perform the tasks. In this paper, an airport task assignment problem is explored, which comes from a domestic airline. The problem is to assign tasks with special properties to a limited number of shifts. Due to the diversity of the properties of airport tasks and shifts, the problem of airport task assignment is a very complicated combinatorial optimization problem, which belongs to NP-complete problem. A mathematical optimization model is established and the objective is to maximize the total benefit by completing tasks, put forward effective inequality and apply software CPLEX to solve the actual data. The results show that the optimal solution of given size instances can be obtained in a short of time by CPLEX. Moreover, the impacts of various properties of tasks and shifts are explored via computational experiment as well. Through the practical data test comparison, we gain the conclusion that, according to the characteristics of the problem, adjusting appropriately different factors can not only improve the effective utilization rate of airport resources, but also the efficiency and service level of the airport.

Key words: airporttask assignment, optimization model, ground service, valid inequalities

中图分类号:

V351.17

田倩南, 李昆鹏, 李文莉, 徐东洋. 机场任务指派问题的优化方案研究[J]. 运筹与管理, 2019, 28(11): 1-8.

TIAN Qian-nan, LI Kun-peng, LI Wen-li, XU Dong-yang. Research on Optimization of Airport Task Assignment Problem[J]. Operations Research and Management Science, 2019, 28(11): 1-8.

参考文献

[1] Berrittella M, Franca L L, Zito P. An analytic hierarchy process for ranking operating costs of low cost and full service airlines[J]. Journal of Air Transport Management, 2009, 15(5): 249-255.
[2] Cheung A, Ip W H, Lu D. Expert system for aircraft maintenance services industry[J]. Journal of Quality in Maintenance Engineering, 2005,9(4): 348-358.
[3] Baker K R. Workforce allocation in cyclical scheduling problems[J]. Journal of the Operational Research Society, 1976, 27(1): 155-167.
[4] Nagraj B, Richard T W. A network model for the rotating workforce scheduling problem[J]. Networks, 1990, 20(1): 25-42.
[5] Chu C K, Chan C H. Crew scheduling of flight rail transit in Hong Kong: from modeling to implementation[J]. Computer & Operations Research, 1998, 25(11): 887-894.
[6] Luca D G, Johannes G, Guy K. The minimum shift design problem[J]. Annals of Operations Research, 2003, 155(1): 79-105.
[7] Detienne B, Péridy L, Éric P, Rivreau D. Cut generation for an employee timetabling problem[J]. European Journal of Operational Research, 2009,197(3): 1178-1184.
[8] Tommy C. A Rule-based local search algorithm for general shift design problems in airport ground handling[J]. Transportation Engineering Journal, 2010, 35(6): 189-199.
[9] Soukour A A, Devendeville L, Lucet C, Moukrim A. A memetic algorithm for staff scheduling problem in airport security service[J]. Expert Systems with Applications, 2013, 40(18): 7504-7512.
[10] Ip W H, Wang D, Cho V. Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme[J]. IEEE Systems Journal, 2013, 7(4): 649-657.
[11] Jiang Y, Xu X, Zhang H, Luo Y. Taxiing route scheduling between taxiway and runway in hub airport[J]. Mathematical Problems in Engineering, 2015(1): 1-14.
[12] Ascó A, Atkin J A D, Burke E K. An analysis of constructive algorithms for the airport baggage sorting station assignment problem[J]. Journal of Scheduling, 2014, 17(6): 601-619.
[13] Zou X, Liu L, Li K, Li W. A coordinated algorithm for integrated production scheduling and vehicle routing problem[J]. International Journal of Production Research, 2017(1): 1-20.
[14] 吕虹,秦永彬,罗聪.基于Memetic算法的飞机地面作业调度问题研究[J].广西师范大学学报(自然科学版),2011,29(2):145-150.
[15] 樊琳.大型机场地勤服务中的车辆调度问题的初步研究[D].东北大学,2009年.
[16] 樊玮,吴建波,衡红军.基于多Agent的机场地面服务车辆调度方法研究[J].计算机应用与软件,2015(10):256-259.
[17] 王来军,史忠科.航班离场排序问题的遗传算法设计[J].系统工程理论与实践,2005,25(9):119-125.
[18] 张建同,杨文娟.基于优先级的进离港飞机排序优化问题研究[J].运筹与管理,2018,27(6):115-121.
[19] 付晓薇,郭强,马芹芹.一类非确定型多目标指派问题及其算法研究[J].运筹与管理,2013(6):34-38.
[20] 唐非,刘树安,董昕禹.多阶段启发式算法求解机场地勤服务优化问题[J].沈阳工业大学学报,2017,39(6):664-669.

机场任务指派问题的优化方案研究

Research on Optimization of Airport Task Assignment Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics