Airline networks are becoming increasingly complex, particularly at mega-hub airports characterized by high transit volumes. Effective schedule design and fleet assignment are critical for an airline, as they directly influence passenger connectivity and profitability. This study addresses the challenge of introducing a new route from a mega-hub to a new destination, while maintaining the existing flight network and leveraging arrivals from spoke airports to ensure connectivity. First, a mixed-integer nonlinear mathematical model was formulated to produce a global optimal solution at a lower time granularity, but it became computationally intractable at higher granularities due to the exponential growth in constraints and variables. Second, a genetic algorithm (GA) was employed to demonstrate scalability and flexibility, delivering near-optimal, high-granularity schedules with significantly reduced computational time. Empirical validation using real-world data from 37 spoke airports revealed that, while the exact model minimized waiting times and maximized profit at lower granularity, the GA provided nearly comparable profit at higher granularity. These findings guide airline managers seeking to optimize passenger connectivity and cost efficiency in competitive global markets.