Optimizing onboard catering loading locations and plans for airlines

Airlines serve complimentary or for-purchase in-flight meals that vary depending on flight duration. These meals are prepared by airline catering companies and are ideally loaded immediately before the flight. However, as the loading process takes time and effort and it is costly to have the required amount of meals at the departure airport immediately before each flight, airline companies conduct catering loading at predetermined airports. In general, the catering loading sites, i.e. airports, can be classified into two types: normal or cross-loading sites. At the normal loading sites, the catering can be directly loaded to the aircraft with a fixed loading cost and a variable handling cost that depends on the loaded amount and personnel cost at the corresponding location. At the cross-loading sites, the catering is transported from a catering facility before the loading operation, incurring an additional transportation cost. During a flight, an aircraft may carry the catering demand for the next flights. The total amount of catering carried during a flight depends on the shelf life of the catering and the aircraft capacity and affects the fuel consumption during the flight. Although the flight plan might dynamically change, airlines determine catering loading sites before each flight season based on the established flight plan and estimated amount of catering consumed during each flight. In this study, given the flight plan of an airline for a specified planning horizon with the estimated demand for each catering type at each flight, we address the problem of determining the locations of normal and cross-loading sites. The objective is to minimize total operational costs that include the fixed costs of opening normal or cross-loading sites, fixed and variable costs of loading, transportation costs for cross-loading, and additional aircraft fuel costs that depend on the catering load of the aircraft such that the estimated catering demand for each flight is fully met. The aircraft catering capacity limits and lifetime for each catering type should be considered. We first develop a mixed integer programming formulation for the problem. As the planning horizon increases, it is not possible to obtain good solutions via the mathematical formulation over a reasonable time. Therefore, we propose a hybrid solution approach based on a tabu search algorithm and dynamic programming approach for realistic planning horizons. We analyze the performance of the proposed approaches on realistic problem instances obtained from an airline company based in Turkey.