In case of a threat in a public space, the crowd in it should be evacuated fast. A working evacuation plan should account for different uncertainties. One way to decrease the uncertainties is to make use of safety staff, or guides, that lead the crowd out of the building according to an evacuation plan. Nevertheless, solving the minimum time evacuation plan is a computationally demanding problem. In this paper, we model the evacuating crowd and guides as a multi-agent system with the social force model. To represent the uncertainty, we construct probabilistic scenarios. The evacuation plan should work well both on average, and also for the worst-case scenarios. Thus, we formulate the problem as a bi-objective scenario optimization problem, where the mean and conditional value-at-risk (CVaR) of the evacuation time are objectives. A solution procedure combining numerical simulation and genetic algorithm is presented. We apply it on the evacuation of a fictional passenger terminal. In the mean-optimal solutions, guides are assigned to lead the crowd to the nearest exits, whereas in the CVaR-optimal solutions the focus is on solving the worst-case physical jam. With enough guides, a plan that minimizes both objectives is obtained. We show that the evacuation times can vary a lot between scenarios, and the mean-optimal evacuation plan can be qualitatively very different to the CVaR-optimal evacuation plan.