Optimizing onboard catering loading locations and plans for airlines

Airlines serve complimentary or for-purchase in-flight meals that vary depending on the length of the flight. These meals are prepared by airline catering companies and are ideally loaded just before the flight. However, as the loading process takes time and effort and it is costly to have required amount of meal at the departure airport just before each flight, airline companies carry out catering loading at predetermined airports. In general, the catering loading sites, i.e., airports, can be classified into two types as normal or cross loading sites. At the normal loading sites, the catering can be loaded directly to the aircraft with a fixed loading cost and a variable handling cost that depend on the loaded amount and personnel cost at the corresponding location. At the cross loading sites, the catering should be transported from a catering facility before the loading operation, incurring an additional transportation cost. During a flight, an aircraft may carry the catering demand of 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 change dynamically, 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 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 life time for each catering type should be considered. We first develop a mixed integer programming formulation for the problem. As the planning horizon gets larger, it is not possible to obtain good solutions by the mathematical formulation in 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.