Integrated aircraft tail assignment and cargo routing problem with through cargo consideration

Traditionally, freight airlines assign individual aircraft to each flight and sequentially determine the cargo itineraries for each order. This may limit the option of cargo itineraries, and lead to mismatches between cargo demands and freighter capacities. To overcome this limitation, we introduce the concepts of through cargo connection and short through cargo connection. A through cargo connection requires cargoes to stay on the same aircraft between two connected flights, and a short through cargo connection is a through connection that needs less time than the standard cargo transshipment time. By considering the through cargo connections and short through cargo connections, we can generate the complete set of all possible cargo itineraries, so as to improve the overall schedule efficiency and robustness, and reduce the cargo ground handling cost. In this paper, two mathematical models (the connection- and string-based models) are proposed to solve the aircraft tail assignment problem (TAP) and cargo routing problem (CRP) simultaneously with through cargo considerations. We developed a column generation framework to solve the LP relaxation of the string-based model, and a diving heuristic with reoptimization strategy to find a good IP solution in a reasonable time. The proposed solution methods are tested using industrial cases from the largest freight airline in China. The computational experiments revealed that the integrated models could bring up to 5.04%∼10.31% profit growth, and the through cargo savings are tripled compared with the baseline solutions. By analyzing the computational performance of two models, we recommend that airlines can apply connection-based model only if the problems are not very large and the computational time is sufficient; otherwise, the string-based model is more robust in terms of problem scales and computational time.