When there are a plurality of routes to one parking space, automatic parking cannot be performed on a route with short parking time. A route candidate generation unit 301 changes a reference vehicle speed and a route shape, and searches for a route from a parking start position to a parking target position. The route passage time calculation unit 302 calculates, for each route candidate, the time required to pass through the route based on the reference vehicle speed and the length of the route. A state switching time calculation unit 303 calculates, for each route candidate, the time required for switching between forward and backward movements of a vehicle, and the time required to change steering to a predetermined steering angle in a state where the vehicle is stopped. A route selection processing unit 305 selects a specific route, for example, a route with short parking time, from a generated routes based on route passage time.