Agent-based models (ABMs) / multi-agent systems (MASs) are today one of the most widely used modeling-simulation-analysis approaches for understanding the dynamical behavior of complex systems. These models are often characterized by several parameters with nonlinear interactions which together determine the global system dynamics, usually measured by different conflicting criteria. The problem that emerges is that of tuning the controllable system parameters at the local level, in order to reach some desirable global behavior. In this research paper, we cast the tuning of an ABM for emergency response planning as a multi-objective optimization problem (MOOP). We then propose the use of multi-objective evolutionary algorithms (MOEAs) for exploration and optimization of the resultant search space. We employ two well-known MOEAs, the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Pareto Archived Evolution Strategy (PAES), and test their performance for different pairs of objectives for plan evaluation. In the experimental results, the approximate Pareto front of the non-dominated solutions is effectively obtained. Further, a conflict between the proposed objectives is patent. Additional robustness analysis is performed to help policymakers select a plan according to higher-level information or criteria not present in the original problem description.