Transportation Science · 2008 · 40 citations · 8 references
Natural SciencesIndustrial EngineeringOperations ManagementOptimizationParallel AlgorithmsSchedulingAviation TransportationCombinatorial OptimizationDiscrete OptimizationInteger ProgrammingLarge-scale OptimizationNetwork OptimizationAir Transportation NetworksAirline SchedulingAsynchronous Parallel AlgorithmsAsynchronous SchedulingConstraintsInteger FlowLocal SearchMulticommodity Flow
The availability of relatively cheap small jet aircrafts suggests a new air transportation business: dial-a-flight, an on-demand service in which travelers call a few days in advance to schedule transportation. A successful on-demand air transportation service requires an effective scheduling system to construct minimum-cost pilot and jet itineraries for a set of accepted transportation requests. In Part I, we introduced an integer multicommodity network flow model with side constraints for the dial-a-flight problem and showed that small instances can be solved effectively. Here, we demonstrate that high-quality solutions for large-scale real-life instances can be produced efficiently by embedding the core optimization technology in a local search scheme. To achieve the desired level of performance, metrics were devised to select neighborhoods intelligently, a variety of search diversification techniques were included, and an asynchronous parallel implementation was developed.
8