Multiple Traveling Salesman Problem Model for Fleet Assignment

摘要

Fleet assignment is one of four main steps in airline planning The objective is to determine which type of aircraft should fly on each flight leg while considering the different features and costs with different fleet types The main purpose of the fleet assignment problem (FAP) is to maximize total profits or minimize total operating costs The problem is usually formulated as an integer linear programming problem The solving efficiency and quality of the massive programming problem will drop with complexity increasing Due to the size of the FAP various heuristic algorithms or methods for solving this problem have been studied The purpose of finding the heuristic solutions for the optimal feasible solution is to find the satistied results more efficient for less time This thesis proposes a multiple traveling salesman problem model(MTSP Model) to solve the FAP and determine which type of aircraft should fly on each flight arc and flights which has the optimal order It’s different to Time-Space Network model this model drawing the flight dots by the departure time departure airport arrival time and arrival airport and joining the flight dots to calculate the minimal costs by following the relative constraints The perpose is to obtain optimal flight order by considering constraints and minimal the costs of distance to get the maximum total profits after fleet assignment procedure In this thesis the MTSP Model is choosen because the MTSP is a well-known problem which is solved by many kinds of solver with good solving quality The MTSP not only has the roughly same problem size comparing to the FAP but also has well-developed technique to be solved This thesis proposes a two-phase approach to solving the FAP First genetic algorithm is applied to solve MTSP model for FAPs Cosidering more feasible time backward arcs are used to solve this problem By allowing backward time the optimal feasible solution with the minimum number of rescheduled flight is sought Some routes which have minimal costs of distance are found Finally the continuously adjustable flight schedule problem is solved using a integer linear programming model instead of using a time window to change flight schedules Our method has a similar level of flexibility as the fleet assignment model with time window (FAMTW) and solves the problem in shorter time than the FAMTW An approach for solving the aircraft routing problem is also proposed

獎項日期	2015 8月 21
原文	English
監督員	Ta-Chung Wang (Supervisor)