×

Rates of closed-bridge and crossing-collision oriented optimization model on aircraft-gate assignment and its heuristics. (Chinese. English summary) Zbl 1474.90150

Summary: Given a schedule of flights for an airport, the aircraft-gate assignment not only has to obey the technical constraints of airplanes and flights, but also needs to improve the resource utilization and economic efficiency, and facilitates passengers to enter and leave port in a timely, safe and convenient way. In this paper, we establish an optimization model of assigning gates for aircrafts with the objectives of aircraft allocating rate, closed-bridge rate and non-collision rate of crossings, as well as subject to the constraints of flight attributes such as aircraft types, affiliated companies, cargo/passenger tasks and domestic/international flights. For the real scenario of an airport in China, this assignment model becomes a large-scale mixed integer programming with the complexity of NP-COMPLETE. This paper then proposes a greedy-based heuristic algorithm, within which a priority queue is established to mediate the timetable conflicts of flights. The approximate optimal solutions are gradually explored according to aircraft allocating rate, closed-bridge rate and non-collision rate of crossings step by step. For each improvement of the algorithm, the effectiveness and performance are evaluated by comparing to the results of CPLEX. Finally, the experimental results show that the heuristic algorithm can save 90% of the solution time while the loss of near optimal solutions is less than 3%.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

CPLEX
PDFBibTeX XMLCite