Expanding on our preliminary work [1], we present a novel method to heuristically adapt the Earth Mover's Distance to relevance feedback. Moreover, we detail an optimization-based method that takes feedback from the current and past Relevance Feedback iterations into account in order to improve the degree to which the Earth Mover's Distance reflects the preference information given by the user. As shown by our experiments, the adaptation of the Earth Mover's Distance results in a larger number of relevant objects in fewer feedback iterations compared to existing query movement techniques for the Earth Mover's Distance.