For a service that is only restricted to 15 cities across 9 states, when is it feasible to introduce location search?

The service is only offered in 15 cities, the number of disappointment search results (0 results) is much greater than actually getting results.

What other factors should I consider to make this decision?

Would you recommend no location search and a simple browsing by city to start? and only introduce search after more cities are incorporated?

How many cities warrant a location search?