A navigation device comprising: a processor; a display controllable by the processor to display a screen with a plurality of selectable options, each selectable option being associated with at least one reference location; an input interface (220,240) controllable by the processor, the input interface being configured to enable a user to select at least one reference location by selecting one of the plurality of selectable options; and an over the air search module for generating a server call message comprising the at least one reference location and a search text for transmission to a remote map search server and for receiving a search results reply message comprising one or more search results from such a remote map search server based on the at least one reference location and the search text, and the processor being responsive to the OTA search module to control said display to display the search results to the user, wherein the processor is further configured to implement route planning functionality to calculate a route from a start position to a destination position characterised in that: the input interface is additionally configured to enable a user to input the search text; and wherein the route is associated with one of the plurality of selectable options, the route comprising a plurality of reference locations, and the processor is further configured, upon selection of the selectable option associated with the route, to control said display to display an indication, for each search result, whether the search result is on the route, near the route or off the route. a processor; a display controllable by the processor to display a screen with a plurality of selectable options, each selectable option being associated with at least one reference location; an input interface (220,240) controllable by the processor, the input interface being configured to enable a user to select at least one reference location by selecting one of the plurality of selectable options; and an over the air search module for generating a server call message comprising the at least one reference location and a search text for transmission to a remote map search server and for receiving a search results reply message comprising one or more search results from such a remote map search server based on the at least one reference location and the search text, and the processor being responsive to the OTA search module to control said display to display the search results to the user, wherein the processor is further configured to implement route planning functionality to calculate a route from a start position to a destination position characterised in that: the input interface is additionally configured to enable a user to input the search text; and wherein the route is associated with one of the plurality of selectable options, the route comprising a plurality of reference locations, and the processor is further configured, upon selection of the selectable option associated with the route, to control said display to display an indication, for each search result, whether the search result is on the route, near the route or off the route. the input interface is additionally configured to enable a user to input the search text; and wherein the route is associated with one of the plurality of selectable options, the route comprising a plurality of reference locations, and the processor is further configured, upon selection of the selectable option associated with the route, to control said display to display an indication, for each search result, whether the search result is on the route, near the route or off the route.