Optimizing flight connectivity through Graph, Machine Learning and Linear Programming Algorithms
Developed predictive model with 71.01% accuracy to forecast flight delays, clustered airports to enhance efficiency, and used Dijkstra’s algorithm for shortest flight paths, leading to fuel savings. Optimized intra-state connectivity with Kruskal's algorithm, reducing total delay by 93%, and created a linear programming model that minimized delay penalties by 20.15%.
Detailed Description for Each Method
Predict Delays
Technical Approach: We used a Gradient Boosting Classifier to predict flight delays. The dataset included variables like flight date, carrier ID, origin, destination, and delay times. Data preprocessing involved handling missing values and engineering features such as categorizing departure times and extracting month from flight dates.
Milestones and Impact: After building and optimizing the model with GridSearchCV, we achieved a 71.01% accuracy and a 76.85% ROC AUC score. The model's ability to accurately predict delays helps airlines reduce operational costs and improve passenger satisfaction by providing more reliable travel schedules.
Cluster Airports
Technical Approach: We utilized K-means clustering to group airports based on delay and cancellation metrics. Key features included departure and arrival delays, carrier-specific delays, and cancellation rates. The optimal number of clusters was determined using the elbow method.
Milestones and Impact: The analysis resulted in four clusters: High Efficiency, Low Impact; Moderate Delays, Controlled Impact; Average Performance; and High Delays and Cancellations. This clustering allows for targeted improvements, helping airports manage traffic volumes effectively and enhance overall operational efficiency.
Find Shortest Routes
Technical Approach: Dijkstra’s algorithm was implemented to find the shortest flight paths in terms of flight time between designated airports. The algorithm considered only valid flights with non-null elapsed times, creating a directed graph for analysis.
Milestones and Impact: The analysis provided the three shortest routes between JFK and LAX, quantifying differences in flight times. This information aids in efficient route planning, leading to significant fuel savings and reduced carbon emissions, thereby optimizing airline operations.
Optimize State Routes
Technical Approach: Kruskal's algorithm was applied to create a Minimum Spanning Tree (MST) for optimizing routes within a state. The graph was constructed with airports as nodes and flights as edges, weighted by carrier delays.
Milestones and Impact: The MST significantly reduced total delay from 562 minutes to 36 minutes, indicating a 93% reduction. This optimization improves intra-state connectivity, enhances local economic growth, and provides a strategic basis for route planning and operational efficiency.
Minimize Delay Penalty
Technical Approach: A linear programming model was developed using the pulp library to maximize the number of flights while reducing delay penalties. Decision variables represented flight selections, and constraints ensured a 20% reduction in total penalty costs.
Milestones and Impact: The optimized schedule resulted in a minimal reduction of 28 flights while achieving a 20.15% decrease in penalty costs. This demonstrates the model's effectiveness in managing delays and reducing operational costs, highlighting the strategic benefits of data-driven schedule optimization for airlines.