A method incrementally solves a current journey planning request from a user. The solving step performs a current search for at least one journey plan that satisfies the request by accessing a database storing journey planning information derived from results to a plurality of previous requests. The solving step stores, in the database, information discovered during the current search for responding to a subsequent request. The information discovered during the current search for responding to the request includes a reusable portion of a search graph, pairs of a state and a lower bound on a best arrival time and pairs of a state and an exact value for the arrival time. The lower bound is employed to increase an accuracy of a pre-computer heuristic function which guides the search based on state dominance in search spaces in which heuristic values are back propagated and stored in the database.