A passenger demand model for airline flight scheduling and fleet routing

Fleet routing and flight scheduling are essential to a carrier's profitability, its level of service and its competitive capability in the market. This research develops a model and a solution algorithm to help carriers simultaneously solve for better fleet routes and appropriate timetables. The model is formulated as an integer multiple commodity network flow problem. An algorithm based on Lagrangian relaxation, a sub-gradient method, the network simplex method, the least cost flow augmenting algorithm and the flow decomposition algorithm is developed to efficiently solve the problem. The results of a case study, regarding a major Taiwan airline's operations, show the model's good performance. Fleet routing and flight scheduling issues have been widely studied to enhance airline's operation efficiency. Normally, network flow techniques are adopted for modeling and solving such complex mathematical problems. However, traditional approaches, which employ draft timetable as an essential medium, not only involve too much subjective judgement and decision making in the process but also reveal an incapability of directly and systematically managing the interrelation between supply and demand. The purpose of this paper is to develop a network model together with a solution algorithm, that can directly manage the interrelationships between passenger trip demands and flight supplies, in order to effectively assist carriers' scheduling.