Optimized system and method for finding best fare

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 . In a communications network including a client and a query server computer, a method for finding at least one best fare for a trip, the method comprising:
 at the query server computer, in response to a fare query received from the client application:
 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, wherein said partial fare solutions are eliminated based on a threshold cost determined, at least in part, according to the travel time of said partial fare solutions; 
 determining whether a predetermined number of complete fare solutions have been found and repeatedly increasing the threshold cost and carrying out the above recited steps of determining, adding, and eliminating using the increased threshold cost until the predetermined number of complete fare solutions has been found; and 
 returning a subset of said complete fare solutions as the best fares for the trip.