In recent years advanced car navigation systems have emerged as a key tool for commuters. For tourists and visitors, analogous mobile tour guides are equally important when exploring urban and outdoor spaces. During the development of a mobile tour guide designed specifically forhikers and cyclists the need for route planning based on individualized time estimates became evident. Despite progress in accurate time-of-arrival estimation for cars, relatively little research has focused on hiking and cycling. This paper therefore discusses a number of approaches to time estimation, introducing a nearest neighbour model which, based on a preliminary evaluation, is applicable in scenarios where limited learning data is available.