A route-planning device (200;302), comprising: a storage section (230;306) storing map information, wherein the map information comprises data representative of roads and/or sub-roads of a road network, each road and/or sub-road having a length and at least one parking space associated therewith, and wherein the map information further comprises probability information for each road and/or sub-road corresponding to the likelihood of finding a vacant parking space on the road and/or sub-road; and a search route module arranged to: receive a request to provide a search route for a vacant parking space; set a current position of a navigation device associated with a vehicle as a start position of the search route; determine a route from the start position that visits a plurality of the parking spaces using the map information, wherein said determining comprises evaluating a predetermined cost function for each of a plurality of possible routes from the start position of up to a maximum length, the cost function being based at least on the probability information for the roads and/or sub-roads of the possible route, and selecting the best route from the plurality of possible routes as the determined route based on maximising or minimising the result of the cost function; and output the determined route as the search route, the route-planning device further comprising a goal identification section for identifying a goal position, and wherein the cost function is further based on a predetermined metric relating to the goal position and a position of the road or sub-road, wherein a parameter is used in the cost function to weight the importance of the predetermined metric relating to the goal position and the position of the road or sub-road, and wherein the search route module is further arranged to receive a value of the parameter from a user of the navigation device. a storage section (230;306) storing map information, wherein the map information comprises data representative of roads and/or sub-roads of a road network, each road and/or sub-road having a length and at least one parking space associated therewith, and wherein the map information further comprises probability information for each road and/or sub-road corresponding to the likelihood of finding a vacant parking space on the road and/or sub-road; and a search route module arranged to: receive a request to provide a search route for a vacant parking space; set a current position of a navigation device associated with a vehicle as a start position of the search route; determine a route from the start position that visits a plurality of the parking spaces using the map information, wherein said determining comprises evaluating a predetermined cost function for each of a plurality of possible routes from the start position of up to a maximum length, the cost function being based at least on the probability information for the roads and/or sub-roads of the possible route, and selecting the best route from the plurality of possible routes as the determined route based on maximising or minimising the result of the cost function; and output the determined route as the search route, the route-planning device further comprising a goal identification section for identifying a goal position, and wherein the cost function is further based on a predetermined metric relating to the goal position and a position of the road or sub-road, wherein a parameter is used in the cost function to weight the importance of the predetermined metric relating to the goal position and the position of the road or sub-road, and wherein the search route module is further arranged to receive a value of the parameter from a user of the navigation device. receive a request to provide a search route for a vacant parking space; set a current position of a navigation device associated with a vehicle as a start position of the search route; determine a route from the start position that visits a plurality of the parking spaces using the map information, wherein said determining comprises evaluating a predetermined cost function for each of a plurality of possible routes from the start position of up to a maximum length, the cost function being based at least on the probability information for the roads and/or sub-roads of the possible route, and selecting the best route from the plurality of possible routes as the determined route based on maximising or minimising the result of the cost function; and output the determined route as the search route, the route-planning device further comprising a goal identification section for identifying a goal position, and wherein the cost function is further based on a predetermined metric relating to the goal position and a position of the road or sub-road, wherein a parameter is used in the cost function to weight the importance of the predetermined metric relating to the goal position and the position of the road or sub-road, and wherein the search route module is further arranged to receive a value of the parameter from a user of the navigation device.