How do we reason about incomplete spatio-temporal descriptions? How might a map influence formerly constructed preferred mental models? Little research so far focused on a combination of two central fields important for successful route planning: the way humans deal with constraint based reasoning (especially with some sort of spatio-temporal constraints) and the way in which humans plan with a given map (especially with problems inspired by typical Traveling Salesman Problems). This, however, becomes even more interesting in cases in which the spatio-temporal constraints allow for several solutions. Do the predictions of the preferred mental model theory still hold true in such situations? This article investigates the influence of maps on the generation of preferred models. The goal is to bring together the theory of (preferred) mental models and route planning.