Patent ID: 7191140

Claim:
An automated system for generating multiple solutions in near real time for n open pairings (where n is an integer) occurring in airline operations, which comprises: a memory system having stored therein first memory objects defining flight and crew data, legality rules and other data relating to pairings of an airline; an optimization server in electrical communication with said memory system and receiving user requests for updating said memory system and for generating solutions to cure said n open pairings; and a microprocessor in electrical communication with said memory system and said optimization server for identifying all deadhead paths occurring among said n open pairings, generating solution components based upon said deadhead paths, storing said deadhead paths and said solution components in said memory system as second memory objects, and upon receiving from said optimization server a user request for curing said n open pairings, extracting said first memory objects and said second memory objects to form an open pairing model, formulating said open pairing model into an integer program data structure to simplify said open pairing model for solution, and generating said multiple solutions based upon said integer program data structure to cure said n open pairings, wherein said integer program data structure is provided by an integer program represented by: ∑ j ⁢ ⁢ t ⁢ ⁢ x i ⁢ ⁢ j t = 1 ⁢ ∀ i , ( i ) ∑ i , j , t ⁢ x i ⁢ ⁢ j t ⁡ ( f ) ⁢ + y f - S f = 1 ⁢ ∀ f , ⁢ and ( ii ) Objective = min . ∑ i , j t ⁢ ⁢ C i , j t ⁢ x i , j t + ∑ f ⁢ ⁢ C f ⁢ y f + ∑ f ⁢ ⁢ B f ⁢ S f ( iii ) where “i” represents a first Pairing in a fix, whether broken or unbroken; where “j” represents a second Pairing in a fix, whether broken or unbroken; where “f” is an integer, indicating a flight identifier; where “C t ij ” and “x t ij ” represent a Cost to an airline in implementing a One-Way Fix “x t ij ” when i≠j and a SelfFix “x t ij ” when i=j; where “C f ” represents a Cost to an airline for flight f which is not covered by any fixes; where “y f ” is an integer, where y f =0 if a flight f is covered by a fix “x” and y f =1 if flight f is not covered by a fix “x”; where “B f ” represents a Cost of crew over-coverage for flight f; where “S f ” represents a slack factor referring to a over-coverage of crew to guarantee a feasibility of a solution; and where “min.” represents a minimum function, in which a smallest number in a data set is returned.