Transportation Science · 2003 · 60 citations · 9 references
ManagementIndustrial EngineeringOperations ManagementOperations PlanningOptimizationSchedulingCombinatorial OptimizationInteger ProgrammingMathematical ProgrammingNetwork OptimizationSchedule OptimizationSchedule Recovery PlanningAirline SchedulingFleet SchedulingLagrangian RelaxationMixed-integer OptimizationMixed-integer ProgrammingMixed-integer Programming For SchedulingMulticommodity FlowScheduling Problems
A bundle algorithm is presented to solve a multicommodity network model for determining a recoveryplanfor a single carrier with multiple fleets following a hub closure. The algorithm is shown to provide feasible near-optimal solutions much more quickly than can be obtained using a standard commercial mixed-integer programming code (CPLEX). In this application, a bundle method is used to solve a Lagrangian relaxation of the integer programming formulation. The full algorithm includes heuristic techniques for finding feasible solutions from the solutions to the relaxed problems. Extensive computations were performed using data from Continental Airlines. The results show that the proposed approach provides faster times to optimality in some cases and always obtains feasible, near-optimal solutions for larger problems much more quickly than can be found using CPLEX. In addition, while a standard commercial code will provide only one solution, this approach provides multiple high-quality solutions.
9