Solving Flight Conflict Problem with Network Flow Model

Flight-connecting schedule is the basis of making routine production plan of airline operation for airline companies. In this paper, according to the structural characteristics of single hub and spoke flight network, a bipartite graphic model and its optimization algorithm are developed for flight connecting in a hub and spoke network system to minimize the number of aircraft required. First, the flight-connecting problem is converted into the flight pairing connecting problem, and a bipartite graphic model describing the flight pairing connecting problem is built. Thus, an optimal flight-connecting problem is transformed to the maximum matching problem of the bipartite graphic model. Then, an assistant graph with single source and sink is created based on the bipartite graphic model. The maximum matching of the bipartite graph is obtained by calculating the maximum inflow with the Ford-Fulkerson algorithm, and a flight-connecting schedule with minimum craft number is accordingly produced. This provides a feasible method to computerize the work of making and optimizing a flight-connecting schedule. Moreover, through adjusting the upper limit of the time of passing depots, different flight-connecting schedules can be obtained. This brings flexibility to the making of production plans