In airline industry scheduling problems, the aircraft routing and the aircrew pairing problems are highly related to fueling and personnel costs. When performing aircraft routing and aircrew pairing, several objectives, such as the ground-turn around time, flow balance, transition time, number of deadheads, number of layovers, flying time, and flight duty period should be considered. It is difficult to optimize these conflicting objectives simultaneously. Many issues are yet to be solved as follows.
1. Most researches related to the aircraft routing and aircrew pairing problems use set partitioning or set covering models. Planners must (1) enumerate several possible subsets of flights, (2) assign costs, and (3) check feasibilities simultaneously. This is time-consuming since the numbers of whole subsets are exponential values to the problem size.
2. The number of enumerated subsets is usually too small to cover the whole solution space. Therefore, even if the optimal solution is found, it is just a local optimal solution of the enumerated subsets.
3. When using traditional optimization algorithms to find a combination of these subsets with minimal cost, it should be ensured that all flights should be covered exactly once. This causes the overheads of checking the number of coverage.
4. In traditional solution methods, the number of required aircrafts and crewmembers cannot be pre-specified since these numbers can only be obtained when the optimization algorithm is completed.
5. All enumerated subsets should be assigned cost values according to various objectives, such as transition time, number of deadheads, number of layovers, flying time, and flight duty period. The cost values are difficult to assign since it is highly dependent on domain knowledge, and usually nonlinear. Also, inappropriate cost values will cause bias in optimization, and ambiguity among all factors due to single objective formulation.
Hence, to overcome these problems, we propose several enhancements in both formulation and the solution stages. In the formulation stage, we propose a novel permutation-based model with multiple objectives, which has the following features.
1. The proposed permutation-based model can save the overheads of pre-enumerating possible sub-solutions
2. The permutation-based model can cover the whole solution space. Hence, it has more chance to find out the global optimal solution.
3. The proposed permutation-based model can ensure that each flight can be covered exactly once to save the overheads of checking the number of coverage.
4. The proposed permutation-based model can provide a new way to pre-specify the number of aircrafts or group number of crewmembers.
5. Taking the advantage of multiobjective formulation, various objectives are considered separatively instead of assigning cost values. All objective can be considered individually even if they have different definitions of optimality or scales.
In the solution stage, we apply the MOI-based MGA (MMGA) to solve the problems of aircraft routing and crew pairing. MMGA is originally proposed to solve numerical controller design problem. By using MMGA, designers can configure the ranges of solutions via adjusting an auxiliary vector of performance indices. To make MMGA more suitable for solving the aircraft routing and aircrew pairing problems, some enhancements are added, such as chromosome encoding scheme, repairing strategy, crossover, and mutation operations. This approach has following features.
1. In both aircraft routing and aircrew pairing problems, the permutation-based encoding scheme, which is the same as the formulation model, can ensure all flights be covered once.
2. Moreover, in the crew pairing problem, the sectional permutation-based encoding scheme, which divides the flights into three sections, such as earlier flights, later flights, and floating flights, can enhance MMGA to find out optimal solutions which satisfy the flight duty period objective.
3. Also, to overcome the large violations caused by random generation of candidate solutions, we use a repairing strategy, which repairs all generated solutions by reordering the sequences of flights according to departure times.
4. The sectional order-based crossover can have a more stable evolution than the widely-used partial mapped crossover. Also, it can make the newborn offspring keep the features of three sections defined in the encoding scheme.
5. Also, the sectional mutation can inherit the advantages of the widely-used reciprocal mutation and keep the features of three sections defined in the encoding scheme.
In the aircraft routing problem, experiments show that MMGA can find out optimal flight schedules under the condition of sufficient aircrafts. On the other aspect, when the number of aircrafts is insufficient, planners can modify the obtained solutions by a little retiming process when the number of violations is small.
In the aircrew pairing problem, experiments indicate the proposed approach can solve the aircrew pairing problem with minimal group number of crewmembers which is verified by a branch-and-bound approach.
By using MMGA, the problems of aircraft routing and aircrew pairing can be solved efficiently and effectively. In other words, planners can solve these problems in a short time period instead of enumeration and feasibility checking by traditional methods. Via the proposed approach, planners can further consider more important issues, such as to suggest better schedules with lower cost and higher benefit.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0214108-174718 |
| Date | 14 February 2008 |
| Creators | Chou, Ta-Yuan |
| Contributors | Tung-Kuan Liu, Pau-Choo Chung, Jan-Ming Ho, Chung-Nan Lee, Shie-Jue Lee, Tzung-Pei Hong |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0214108-174718 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0021 seconds