A route-planning device (200;302), comprising: a storage section (230;306) storing map information, the map information including information identifying positions of a plurality of parking spaces, the map information further including time dependent probability information for each parking space, the probability information corresponding to the likelihood of the parking space being found vacant at a plurality of different time intervals; and a search route module arranged to determine a search route from a start position at a current or future departure time visiting at least one of the parking spaces, the determination of the search route comprising maximising or minimising a predetermined cost function based at least on the probability information for the estimated time of arrival at each parking space to determine a search route that has a better chance of finding a vacant parking space in the shortest time or with the least distance travelled, characterised by further comprising: an updating section arranged to receive temporary probability information for at least one parking space from a server, the temporary probability information to be used in place of the probability information in the map information for a predetermined time before stepwise or gradually reverting to the probability information in the map information, wherein the temporary probability information for a parking space is set at the server based on information received from another device indicating that the parking space was found or not found to be vacant. a storage section (230;306) storing map information, the map information including information identifying positions of a plurality of parking spaces, the map information further including time dependent probability information for each parking space, the probability information corresponding to the likelihood of the parking space being found vacant at a plurality of different time intervals; and a search route module arranged to determine a search route from a start position at a current or future departure time visiting at least one of the parking spaces, the determination of the search route comprising maximising or minimising a predetermined cost function based at least on the probability information for the estimated time of arrival at each parking space to determine a search route that has a better chance of finding a vacant parking space in the shortest time or with the least distance travelled, characterised by further comprising: an updating section arranged to receive temporary probability information for at least one parking space from a server, the temporary probability information to be used in place of the probability information in the map information for a predetermined time before stepwise or gradually reverting to the probability information in the map information, wherein the temporary probability information for a parking space is set at the server based on information received from another device indicating that the parking space was found or not found to be vacant. an updating section arranged to receive temporary probability information for at least one parking space from a server, the temporary probability information to be used in place of the probability information in the map information for a predetermined time before stepwise or gradually reverting to the probability information in the map information, wherein the temporary probability information for a parking space is set at the server based on information received from another device indicating that the parking space was found or not found to be vacant.