Experts propose using an automated parcel locker (APL) for improving urban logistics operations. However, deciding the location of these APLs is not a trivial task, especially when considering a multi-period horizon under uncertainty. Based on a case study developed in Dortmund, Germany, we propose a simulation-optimization approach that integrates a system dynamics simulation model with a multi-period capacitated facility location problem (CFLP). First, we built the causal-loop and stock-flow diagrams to show the APL system's main components and interdependencies. Then, we formulated a multi-period CFLP model to provide the optimal number of APLs to be installed in each period. Finally, Monte Carlo simulation was used to estimate the cost and reliability level for different scenarios with random demands. In our experiments, only one solution reaches a 100% reliability level, with a total cost of 2.7 million euros. Nevertheless, if the budget is lower, our approach offers other good alternatives.