  This work aims to apply the Facility Location Problem in the Emergency
Medical Service (EMS) of Belo Horizonte, Brazil. The objective is to improve
two previous optimization models from literature to handle base locations and
ambulances allocation/relocation problems. The proposed multi-period models
introduce the concept of relocation to the local EMS, which allows ambulances
to move among bases in different periods to raise the system coverage. This
paper also proposes a bi-objective approach aiming to minimize the number of
bases and maximize the coverage of demands, which is solved using the
epsilon-constraint method. Results show that coverage levels increase by up to
31% for the deterministic approach and up to 24% for the probabilistic
approach. Ambulances' relocation optimization might improve coverage levels by
up to 21% for the deterministic approach and up to 15% for the probabilistic
approach when change scenarios from static to multi-period. Also, since the
multi-period model solutions result in installing a larger number of bases, the
bi-objective approach is a powerful tool for the decision-maker. Bi-objective
results suggest modest increments in the objective function when the stations'
number exceeds 28 for the deterministic approach. The probabilistic approach
increments in the objective function start to narrow above 30 installed
stations.
