| dc.description.abstract | Fleet routing and flight scheduling are important in airline operations. They always affect the usage efficiency of facilities and crew scheduling. Furthermore, they are essential to carriers’ profitability, level of service and competitive capability in the market. Recently, besides passenger flights and cargo flights, some airlines introduced combi flights in their flight scheduling. The combi flights combine passengers and cargos in one flight and can supple passenger flights and cargo flights during a carrier’s regular operation. However, the carriers in Taiwan currently adopt a try-and-error method to determine the schedules of passenger flights, cargo flight and combi flights. The method starts by manually determining the passenger and combi flight schedules together. Based on the passenger and combi flight schedules and the projected cargo demand, the cargo flight schedule is then determined. Thereafter, the combi flight schedule is modified by considering the cargo flight schedule and the passenger flight schedule is revised in accordance with the combi flight schedule. The process is repeated until the final fleet routing and timetables are obtained. Since such a method without systemic analyses cannot effectively manage the interrelationship among the passenger, cargo and combi flight schedules, the performance of the obtained schedules would easily decrease as the system scale is enlarged. As a result, the operating performance could possibly be inferior.
Therefore, given the operating data, including fleet size, airport flight quota and available time slots, related flight cost, on the basis of the carrier’s perspective, this research tries to develop a scheduling model by integrating passenger, cargo and combi flight schedules, with the objective of maximizing the operating profit, subject to the related operating constraints. The model is a useful planning tool for airlines to determine a suitable fleet routing and timetables in their short-term operations. We employ network flow techniques to construct the model, which include passenger-flow, cargo-flow and fleet-flow networks in order to formulate the flows of passengers, cargos and fleet in the dimensions of time and space. The model is formulated as an integer multiple commodity network flow problem that is characterized as an NP-hard problem. Since the real problem size is huge, this model is harder to solve than the conventional passenger flight scheduling problems in the past. A Lagrangian relaxation-based algorithm, coupled with a subgradient method, the network simplex method and a heuristic for upper bound solution, is suggested to solve the problem. Finally, to evaluate the model and the solution algorithm, we perform a case study by using the real operating data from a major Taiwan airline. | en_US |