In this work, we propose a local search-based strategy to determine high-quality allocation of vaccines under restricted budgets and time periods. For this, disease spread is modeled as a SEAIR pandemic model. Subgroups are used to understand and evaluate movement restrictions and their effect on interactions between geographical divisions. A tabu search heuristic method is used to determine the number of vaccines and the groups to allocate them in each time period, minimizing the maximum number of infected people at the same time and the total infected population. Available data for COVID-19 daily cases was used to adjust the parameters of the SEAIR models in four study cases: Austria, Belgium, Denmark, and Chile. From these, we can analyze how different vaccination schemes are more beneficial for the population as a whole based on different reproduction numbers, interaction levels, and the availability of resources in each study case. Moreover, from these experiments, a strong relationship between the defined objectives is noticed.