Solving the flight frequency programming problem with particle swarm optimization

摘要

This paper proposes a PSO-FFPP algorithm based on the particle swarm optimization (PSO) framework to solve the flight frequency programming problem (FFPP). The FFPP is to determine the flight frequency for each type of aircraft on each flight route. This problem is fundamental to an airline's operational planning because it affects the airline's profit and market share greatly. The FFPP can be formulated as an integer programming problem with constraints that is very suitable to be solved by the PSO algorithm. The proposed PSO-FFPP algorithm codes the decision variables of the FFPP with real number to represent the potential solutions and defines the optimization objective as a maximization problem for the airlines profit. A constraints handling method that combines the ideas of feasible solution preserving and infeasible solution rejection is developed. This method avoids the expense of infeasibility repair or penalty, making the algorithm simple to use and easy to extend. An integer handing process is also devised to round the real number to the nearest valid integer before feasibility check and function evaluation. This process maintains the search tendency of the PSO algorithm and can help to search in a promising region for the global optimum. The feasibility of the proposed algorithm is demonstrated and compared with the Monte Carlo method and the enumeration method on a simulation case with promising results. Experiments are also conducted to investigate the factors that affect the solution quality and computational time.