Analyzing Airline Alliances through Multi-Attribute Graph Partitioning to Maximize Competition and Market Penetration Capability

The air transportation market is highly competitive and dynamic. Airlines often form alliances to expand their network reach, improve operational efficiency, and enhance customer experience. However, the impact of these alliances on market competition and operational efficiency is not fully understood. In this paper, we propose a novel approach to analyze airline alliances using multi\mfabian{-}attribute graph partitioning. We develop metrics to quantify the competitiveness of flight segments and the market penetration capability of airlines based on their alliance memberships. We formulate a bi\mfabian{-}objective optimization problem to maximize both competition and market penetration simultaneously. We also propose algorithms to solve this optimization problem and demonstrate their effectiveness using real-world flight schedule data. Our results provide insights into the structure of airline alliances and their implications for market competition and operational efficiency.