Optimized system and method for finding best fares

Abstract

The present invention provides a method, apparatus and system for processing fare queries to find the best fares. In one embodiment of this invention a query server utilizes a branching and bounding based technique to implicitly enumerate possible solutions to arrive at best fare solutions.

1 . A method for finding at least one best fare for a trip, the method comprising 
 determining a set of partial fare solutions for the trip;    adding trip information to the partial fare solutions in order to define a set of complete fare solutions for the trip;    as trip information is added to the partial fare solutions, eliminating partial fare solutions that are non-optimal partial solutions; and    returning a subset of said complete fare solutions as the best fares for the trip.    
     
     
         2 . The method of  claim 1 , wherein adding trip information comprises: 
 supplying a fare query to a root node in a solution tree;    assigning fare components corresponding to said root node to a plurality of first nodes;    assigning at least one carrier corresponding to said first nodes to a plurality of second nodes;    assigning at least one flight corresponding to said second nodes to a plurality of third nodes;    assigning at least one priceable unit corresponding to said third nodes to a plurality of fourth nodes; and    assigning at least one fare corresponding to said fourth nodes to a plurality of leaf nodes.    
     
     
         3 . The method of  claim 1 , wherein said subset of complete fare solutions is a predetermined number of lowest cost fare solutions.  
     
     
         4 . The method of  claim 1 , wherein said subset of complete fare solutions is an exhaustive set of said complete fare solutions.  
     
     
         5 . The method of  claim 1 , wherein adding trip information and eliminating partial fare solutions are performed in a recursive manner.  
     
     
         6 . The method of  claim 1 , wherein adding trip information and eliminating partial fare solutions are performed in an iterative manner.  
     
     
         7 . The method of  claim 1 , wherein said partial fare solutions are eliminated based on a threshold cost.  
     
     
         8 . The method of  claim 1 , wherein said partial fare solutions are eliminated based on a refined lower bound.  
     
     
         9 . The method of  claim 1 , wherein said partial fare solutions are stored in a priority queue.  
     
     
         10 . The method of  claim 1 , wherein said complete fare solutions are retrieved from a priority queue.  
     
     
         11 . The method of  claim 1 , wherein adding trip information and eliminating partial fare solutions are performed as part of a branch-and-bound best fare search routine.  
     
     
         12 . The method of  claim 1 , wherein adding trip information and eliminating partial fare solutions are performed both backward and forward from a destination and origin.  
     
     
         13 . A computer readable medium containing computer executable instructions for finding at least one best fare for a trip, comprising determining a set of partial fare solutions for the trip; 
 adding trip information to the partial fare solutions in order to define a set of complete fare solutions for the trip;    as trip information is added to the partial fare solutions, eliminating partial fare solutions that are non-optimal partial solutions; and    returning a subset of said complete fare solutions as the best fares for the trip.    
     
     
         14 . The computer readable medium of  claim 13 , wherein adding trip information comprises: 
 supplying a fare query to a root node in a solution tree;    assigning fare components corresponding to said root node to a plurality of first nodes;    assigning at least one carrier corresponding to said first nodes to a plurality of second nodes;    assigning at least one flight corresponding to said second nodes to a plurality of third nodes;    assigning at least one priceable unit corresponding to said third nodes to a plurality of fourth nodes; and    assigning at least one fare corresponding to said fourth nodes to a plurality of leaf nodes.    
     
     
         15 . The computer readable medium of  claim 13 , wherein said subset of complete fare solutions is a predetermined number of lowest cost fare solutions.  
     
     
         16 . The computer readable medium of  claim 13 , wherein said subset of complete fare solutions is an exhaustive set of said complete fare solutions.  
     
     
         17 . The computer readable medium of  claim 13 , wherein adding trip information and eliminating partial fare solutions are performed in a recursive manner.  
     
     
         18 . The computer readable medium of  claim 13 , wherein adding trip information and eliminating partial fare solutions are performed in an iterative manner.  
     
     
         19 . The computer readable medium of  claim 13 , wherein said partial fare solutions are eliminated based on a threshold cost.  
     
     
         20 . The computer readable medium of  claim 13 , wherein said partial fare solutions are eliminated based on a refined lower bound.  
     
     
         21 . The computer readable medium of  claim 13 , wherein said partial fare solutions are stored in a priority queue.  
     
     
         22 . The computer readable medium of  claim 13 , wherein said complete fare solutions are retrieved from a priority queue.  
     
     
         23 . The computer readable medium of  claim 13 , wherein adding trip information and eliminating partial fare solutions are performed as part of a branch-and-bound best fare search routine.  
     
     
         24 . The computer readable medium of  claim 13 , wherein adding trip information and eliminating partial fare solutions are performed both backward and forward from a destination and origin.  
     
     
         25 . An apparatus for finding at least one best fare for a trip, the apparatus operative to: 
 determine a set of partial fare solutions for the trip;    add trip information to the partial fare solutions in order to define a set of complete fare solutions for the trip;    as trip information is added to the partial fare solutions, eliminate partial fare solutions that are non-optimal partial solutions; and    return a subset of said complete fare solutions as the best fares for the trip.    
     
     
         26 . The apparatus of  claim 25 , wherein adding trip information comprises: 
 supplying a fare query to a root node in a solution tree;    assigning fare components corresponding to said root node to a plurality of first nodes;    assigning at least one carrier corresponding to said first nodes to a plurality of second nodes;    assigning at least one flight corresponding to said second nodes to a plurality of third nodes;    assigning at least one priceable unit corresponding to said third nodes to a plurality of fourth nodes; and    assigning at least one fare corresponding to said fourth nodes to a plurality of leaf nodes.    
     
     
         27 . The apparatus of  claim 25 , wherein said subset of complete fare solutions is a predetermined number of lowest cost fare solutions.  
     
     
         28 . The apparatus of  claim 25 , wherein said subset of complete fare solutions is an exhaustive set of said complete fare solutions.  
     
     
         29 . The apparatus of  claim 25 , wherein adding trip information and eliminating partial fare solutions are performed in a recursive manner.  
     
     
         30 . The apparatus of  claim 25 , wherein adding trip information and eliminating partial fare solutions are performed in an iterative manner.  
     
     
         31 . The apparatus of  claim 25 , wherein said partial fare solutions are eliminated based on a threshold cost.  
     
     
         32 . The apparatus of  claim 25 , wherein said partial fare solutions are eliminated based on a refined lower bound.  
     
     
         33 . The apparatus of  claim 25 , wherein said partial fare solutions are stored in a priority queue.  
     
     
         34 . The apparatus of  claim 25 , wherein said complete fare solutions are retrieved from a priority queue.  
     
     
         35 . The apparatus of  claim 25 , wherein adding trip information and eliminating partial fare solutions are performed as part of a branch-and-bound best fare search routine.  
     
     
         36 . The apparatus of  claim 25 , wherein adding trip information and eliminating partial fare solutions are performed both backward and forward from a destination and origin.