Preventive health care is of utmost importance to governments since they can make massive savings on health care expenditure and promote the well-being of the society. Preventive care includes many services such as cancer screenings, vaccinations, hepatitis screenings, and smoking cessation programs. Despite the benefits of these services, their uptake is not satisfactory in many countries in the world. This can be attributed to financial barriers, social issues., and other factors. One of the most important barriers for preventive care is accessibility to proper services, which is a function of various qualitative and quantitative factors such as the distance to travel, waiting time, vicinity of facilities to other attractive facilities (such as shopping malls), and even the cleanliness of the facilities. Statistics show that even a small improvement in people's participation can save massive amounts of money for any government and improve the well-being of the people in a society. This paper addresses the problem of designing a preventive health care network considering impatient clients, and budget constraints. The objective is to maximize the accessibility of services to people. We model the problem as a mixed-integer programming problem with budget constraints, and congestion considerations. An efficient variable neighborhood search procedure is proposed and computational experiments are performed on a large set of instances.