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

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

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