Cruising for parking is one of the most important issues affecting the air quality and traffic congestion in large- and medium-sized cities. This may emanate from insufficient parking spaces, which can itself cause illegal parking. This paper proposes a bi-level model to optimise parking facility location and size, as its upper-level problem, considering drivers’ parking search behaviour to determine demand allocation, as its lower-level problem. The model determines parking capacities such that the dynamic demand is met legally at a pre-specified satisfaction level. Results show that, for the entire study area, the legal satisfaction ratio is 92% for 20-year planning horizon, while an optimal addition of 2100 parking spaces can increase it to 98.7%. Also, the ratio has a significant increase from 62% to 92% for the most critical zone. Moreover, the establishment cost incurred by the proposed model is 28% less than the commonly used parking accumulation method.