Multi-objective optimization of flight schedules considering Constraint Tolerance based on Local Search and Archives

This paper focuses on the flight schedule optimization that is required to minimize both the delay time and the altitude change from the desired altitudes of all aircrafts as the two objectives while maximizing the "constraint tolerance" which means the acceptable range of changing constraints as the third objective, and proposes Constrained Multi-objective Optimization Evolutionary Algorithm based on Dual Sets with Local Search and Archive (CMOEA/DS-LSA) for its optimization. CMOEA/DS-LSA is designed to find the feasible solutions (i.e., the flight schedules) from the infeasible ones while improving them by the local search and evolving them from the diverse solutions stored in an archive. In particular, the effectiveness of CMOEA/DS-LSA is investigated in not only the unimodal flight scheduling problems (which have the only one optimal solution) but also the multimodal problems (which have more than one optimal solution). The intensive simulations have revealed the following implications: (1) CMOEA/DS-LSA outperforms the conventional methods (i.e., Constrained NSGA-II (CNSGA-II) and Two-stage Non-dominated Sorting and Directed Mating (TNSDM)) in both the unimodal and multimodal problems from the viewpoint of AITDR, which evaluates both the two objectives (i.e., the delay time and altitude change) and the constraint tolerance simultaneously; and (2) CMOEA/DS-LSA can find the multiple solutions while the conventional methods can find only one solution in the multimodal problems.