A number of parking segments is defined as a plurality of areas for street parking. A request for parking within the plurality of parking segments is received that defines parking constraints. The request is for optimize navigation to search for a free parking spot. Parking segments that comply with the parking constraints are determined. Current values for probabilities to park for the parking segments are determined based on evaluation of collected data for parking events. The data may include both traffic data and data related to defined features that are associated with determining of probability values. A route for traversing the parking segments is determined. The route defines an optimized order for traversing according to the determined current value for the probabilities to park. Navigation instructions are provided for the determined optimized route in response to the received request.