A multiobjective hub-airport location problem for an airline network design

This paper presents a biobjective multiple allocation p-hub median problem, discusses the properties of the Pareto frontier and proposes exact and heuristic algorithms for finding the Pareto frontier. Our motivation emanates from airline networks and their new hub investment strategies. The first objective minimizes the total transportation cost of the network, while the second one minimizes 2-stop journeys in order to improve customer satisfaction, which is negatively affected by the multiple-transit routes of airlines. Although using hubs reduces operating costs in networks, a cost-effective hub network may not imply minimum individual travel times for passengers, or happy passengers. It is well-known that airline customers prefer flights with fewer stops. However, reducing 2-stop routes increases the number of arcs, non-stop and 1-stop routes, and thus the total cost in the network. We analyzed the tradeoff between these objective functions. We performed experiments on well-known data sets from the literature. We were able to find the Pareto frontier exactly for small/medium size instances. A variable neighborhood search (VNS) heuristic is presented to approximate the Pareto frontier of large size instances. We also performed an application on the current Turkish aeronautics network. The results are presented and discussed.