In this paper we study a model to estimate the probability that a target group of an advertising campaign is reached by a commercial message a given number of times. This contact frequency distribution is known to be computationally difficult to calculate because of dependence between the viewing probabilities of advertisements. Our model calculates good estimates of contact frequencies in a very short time based on data that is often available. A media planning model that optimizes effective reach as a function of contact frequencies demonstrates the usefulness of the model. Several local search procedures such as taboo search, simulated annealing and genetic algorithms are applied to find a good media schedule. The results show that local search methods are flexible, fast and accurate in finding media schedules for media planning models based on contact frequencies. The contact frequency model is a potentially useful new tool for media planners.