یک مدل برنامه ریزی پرواز برای خطوط هوایی تایوان تحت رقابت های بازار

In this research, we develop a short-term flight scheduling model with variable market shares in order to help a Taiwan airline to solve for better fleet routes and flight schedules in today's competitive markets. The model is formulated as a non-linear mixed integer program, characterized as an NP-hard problem, which is more difficult to solve than the traditional fixed market share flight scheduling problems, often formulated as integer/mixed integer linear programs. We develop a heuristic method to efficiently solve the model. The test results, mainly using the data from a major Taiwan airline's operations, show the good performance of the model and the solution algorithm.

Fleet routing and flight scheduling are essential to a carrier's profitability, its level of service, its competitive capability, and its market share. There are many factors that need to be considered in past airline fleet routing and flight scheduling. These factors generally include the seasonal passenger trip demands, the passenger ticket price, the operating constraints (e.g. the aircraft type, the fleet size, the available slots, the airport quota), the operating costs, as well as the aircraft maintenance and crew scheduling [1]. Most past research has used fixed parameters, including the projected market share (and demand), for flight scheduling and for fleet routing. However, market share may vary, especially in competitive markets. It is dependent on the supply (e.g. the flight frequency, the trip travel time, the safety and equipment, the fare, the crew and staff service) of the carrier and its competitors, as well as the passenger characteristics. In practice, passenger choices of airline and flight are not only affected by the ticket price, but also the safety standards, and the level of service, the frequency of flights and the timetable. A carrier should not neglect the influence of its timetable on its market share. For example, the passenger demand could be lost or vary with respect to the projected demand if the timetable is inferior. On the other hand, a good timetable that takes into consideration passenger reactions to its services will attract more passengers and will improve the carrier's market share in actual operations. Therefore, to set a good flight schedule, not only does the fleet and related supply have to be considered, but also variable market shares in a competitive market have to be taken into account. Currently most airlines in Taiwan use a trial-and-error process for fleet routing and flight scheduling. The flight scheduling process typically consists of two separate phases: (a) the market share/demand projection phase and (b) the schedule construction and evaluation phase. There are only four airlines with domestic operations and each airline's services for the upcoming season are designed to resemble the preceding corresponding period. In practice, the target airline can usually estimate the competitors’ services for the next season. Therefore, in the first phase, planners from the marketing department estimate the market share and passenger demand for the next season based on the projected future market demand, as well as its and its competitors’ current and past operational data, including market share, passenger demand, timetable and other services. Note that in the first phase competitor timetables for the next season also can be projected to help to estimate the market share. The draft timetable is then sent to the scheduling department for the designing of fleet routes. In the second phase the timetable is finalized. In particular, the drafted timetable is adjusted according to fleet routes, fleet size, fleet availability, related costs/revenue, crew scheduling, and maintenance arrangements. This process is iterated manually until a desirable timetable and fleet routes are obtained. Since the flight scheduling and fleet routing in the second phase are neither efficient nor effective, Yan and Young [2] developed a set of network models to help carriers effectively solve for short term flight schedules and fleet routes based on a draft timetable and all the operating constraints. Their models should be more systematic and efficient than the traditional trial-and-error method. To improve Yan and Young's model, Yan and Tseng [1] incorporated the two phases into a single framework. They developed an integrated scheduling model for multi-fleet routing and flight scheduling, with the objective of maximizing the system profit, given a fixed projected market share (and demand) and all the operating constraints. In addition to Yan and Young's [2] and Yan and Tseng's [1] work, much other research has been devoted to fleet routing and flight scheduling problems, by the air industry as well as in academic fields. For example, Levin [3] used bi-partite graph, time-space network, and arc-chain techniques for modeling fleet routing problem. Abara [4] developed an integer linear programming model for fleet assignment with fixed flight departure times and formulated it as a multicommodity network flow problem. Hane et al. [5] modified Abara's model so they could solve daily aircraft routing and scheduling problems (DARSP) without departure time windows. Clarke et al. [6], based on Hane et al.'s basic model, tried to develop a fleet assignment model which would take maintenance and crew scheduling into considerations. Desaulniers et al. [7] proposed two integer programming models, a set partitioning type model and a time constrained multicommodity network flow model, for solving DARSPs according to a set of operational flight legs with known departure time windows. However, in all of the aforementioned models, including Yan and Tseng [1] and Yan and Young [2], to finalize the timetable and schedule, the assumed market shares are fixed, and the variation of market shares due to market competitions is neglected. As a result, the schedules and fleet routes offered may not reflect the actual market share, but be inclined to be inaccurate and inefficient in actual operations, and might possibly decrease the system performance. As mentioned above, in past airline scheduling models, the market share and the projected demand for a specific OD pair, for a given time interval for the target airline are assumed to be fixed. Passenger choice behaviors are neglected. Based on these fixed market share models, one might wonder if traditional sensitivity analysis techniques would actually be useful for understanding the influence of the variable demands on the solution. However, in this research, the evaluation of the target airline's market share, for each OD pair, for each time interval, is complicated, and is correlated with passenger choice behaviors, which are in turn related to such factors as the choice of airline, the fare, the flight frequency and the market characteristics. Moreover, when the related supply is changed, simultaneous changes in market share, for all OD pairs for all time intervals, become more complicated. Therefore, it becomes very difficult for an airline to forecast marker share by performing a sensitivity analysis based on an existing fixed market share model. That is, when developing a flight scheduling model with variable market shares, it is necessary to consider the passenger choice behavior. Apart from focusing on airline fleet routing and flight scheduling, there has been research applying multinomial logit models to formulate passenger choice behaviors in competitive market situations. These models usually take into account such factors, as the quality of service, the safety record, the flight frequency, the travel time, the fare and the passenger's attributes, to estimate the airline market share. For example, see [8], [9], [10], [11] and [12]. Proussaloglou and Koppelman [13] have discussed the effect of the Frequent Flyer program (FFP) and travel purpose on the passenger choice behavior. They found that these two factors had an influence on passenger choice. Proussaloglou and Koppelman [14] developed a joint choice model that took into account the aircraft's capacity constraint, to repeatedly estimate airline market share. Duann and Lu [15] discussed the joint choice decision problem (airline choice and flight choice) of Taiwan air passengers on non-stop flight operations to try to find the factors that had a significant effect on their choice decisions. The results showed that the variables which most significantly influenced the choice of Taiwan passengers as to airline flight selection, included such factors as safety and equipment, crew and staff services, early/late flight arrival times, flight delays, the fare, in-flight food and drink services, and passengers inertia. Yan [16] further modified Duann and Lu's model by incorporating the attribute of travel time into the model for the operations of non-stop and one-stop flights. From the above literature review we see that passenger choice behaviors vary with different market characteristics, meaning that when we incorporate passenger choice behaviors into a flight scheduling model, the passenger choice model and other related factors should reflect the carrier's own market condition. Due to the limitations of the past fixed market share models and the different market conditions/passenger characteristics as described above, the passenger choice models and the flight scheduling models, developed for the airlines in other areas, are not suitable for Taiwan domestic operations. Therefore, their models and solution algorithms are difficult to apply to Taiwan domestic airlines. Since no research on both airline fleet routing and flight scheduling under variable market shares for Taiwan domestic airlines was found, in this research we aim to develop both a model and a solution algorithm that will assist Taiwan domestic airlines in solving their fleet routing and flight scheduling problems under the variable market shares in today's competitive markets. The literature on Taiwan domestic passenger choice behaviors has mainly been focused on single-fleet operations. For simplicity, single-fleet routing and flight scheduling are primarily considered here, but the proposed model could be extended to multi-fleet operations, which will be described in Section 2.5. To solve such problems more practically, unlike the past flight scheduling process, the proposed model does not utilize fixed market share. Instead, passenger choice behaviors are considered. Such an approach, as opposed to the past fixed market share models, is expected to more accurately reflect real market shares, and thus be more practical for carrier operations in today's competitive markets. Therefore the development of an effective model, as well as an efficient solution algorithm, becomes the focus of this study. In this research, we employ the time-space network technique and a passenger choice model to develop a short-term flight scheduling model with variable market shares. It is assumed that projected competitor services will not change in response to the target airline's short term scheduling. This is normally true in current Taiwan domestic market conditions. The model is expected to be a useful planning tool for airlines to determine their short-term fleet routes and timetables in competitive markets. The model is formulated as a non-linear mixed integer program. It is characterized as NP-hard, so is more difficult to solve than traditional flight scheduling problems that are often formulated as integer/mixed integer linear programs. To efficiently solve the model with practical size problems, we develop a heuristic method. The heuristic method is constructed as an iterative solution method, where a series of fixed market share flight scheduling problems are repeatedly solved. It should be noted that the proposed model may be restricted for use by other airlines in markets, with market conditions different from Taiwan, meaning the target airline cannot easily predict its competitors’ services. For example, if every airline in the market is trying to estimate competitors’ services which change during the scheduling process, then these services may not be easy to project. That is, the other airline's services change in response to the target airline's services, making the scheduling practice more like a game. Thus the target airline cannot effectively estimate its market share using a passenger choice model, and therefore, the proposed model may not be directly applicable. As a result, it may be necessary to analyze competitors’ fleet routing and flight scheduling services by the incorporation of game theory. The model proposed in this research should be useful however, for such a market, as a basic tool. The incorporation of game theory to solve for services could be a direction of future research. Although the scheduling process, in practice, is closely related to the aircraft maintenance and the crew scheduling processes, these processes are usually separated to facilitate problem solving [17]. According to the studied Taiwan airline, in practice, maintenance and crew constraints are rather flexible, due to its use of stand-by crews and its progressive maintenance policy. These activities always performed after the fleet routes and flights schedules have been solved. Therefore, based on the current practices, as in Yan and Young [2] and Yan and Tseng [1], we exclude these constraints in the modeling. The rest of this paper is organized as follows: In Section 2, we introduce the model. In Section 3, a solution algorithm is developed to solve the proposed model. In Section 4, numerical tests are performed to evaluate the performance of the model and the solution algorithm. Finally, in Section 5 we conclude.

The research that has made the most valuable contribution to fleet routing and flight scheduling is the development of a new scheduling model capable of incorporating passenger choice behavior in competitive markets. In order to solve the proposed model, which is formulated as a non-linear mixed integer program and is more difficult to solve than the conventional flight scheduling problems, we develop anefficient solution algorithm. The new modeling approach and solution algorithm are expected to help airlines more efficiently determine their flight schedules and fleet routes in competitive markets. Numerical tests, including four cases utilizing data from a major Taiwan airline’s operations with reasonable sim- plifications, are performed to evaluate the adequacy of the model and the solution algorithm. The test results show that the heuristic solutions obtained in this research were very close to the optimal solution for VMSFSM. In addition, a comparison of the VMSFSM and FMSFSM results indicated that VMSFSM was a significant improvement over FMS- FSM, and could be useful for carriers in real operations. In the testing process, several sensitivity analyses demon- strated the flexibility of the model, showing that it could be useful in actual operations. Although the preliminary test results show that the model and the solution algorithm are potentially useful for solving medium scale problems, especially for the domestic Taiwan market, more testing and case studies should be conducted, so that the effectiveness of the model and its limitations may be better grasped. The model and the solution algorithm can be suitably modified to solve larger-scale problems, or for multi-fleet routing and multi-stop flight scheduling. If the proposed solution algorithm cannot efficiently solve large- scale problems, then modern meta-heuristic techniques (e.g. the tabu search method, threshold accepting method, or ge- netic algorithm), column generation or lagrangian relax- ation, may be incorporated or employed to develop a more efficient algorithm. This could be a direction of future re- search. Moreover, for other markets different from current Taiwan market conditions, where the target airline cannot predict competitor services, the proposed model should be useful as a basic tool. The incorporation of game theory to solve for services could be a direction of future research. The passenger choice model and its related factors and pa- rameters may be suitably modified, for according to their own market characteristics. Modification and testing of the model could also be directions for future research