(The following may well have occurred to you already, but for completeness ...)

When adding nodes to the open set (`openset` at [pseudocode](http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode)), you could ignore nodes that have a distance to $dest$ that are greater than the upper bound on $d(x, dest)$.  As in

    upperboundDistToDest = (Calculation of upper bound)

    (... then in the appropriate place ...)
    
    if neighbor not in openset and dist(neighbour, dest) < upperboundDistToDest 
        add neighbor to openset