Freight distribution within a city has to face a wide variety of requirements and difficulties with time uncertainty amongst them. Especially, when looking at a complex distribution scheme with numerous synchronizations between different types of vehicles, the delay of one vehicle may cause delays of other vehicles as well. Therefore, we investigate the influence of time uncertainties on such a distribution scheme by a Monte Carlo Simulation approach. We first solve the Vehicle Routing Problem with synchronization constraints under deterministic assumptions. Then we iteratively evaluate the robustness of the solution using Monte Carlo Simulation, and we use a relocation operator to increase the robustness of the solution. Our algorithm generates a Pareto frontier of solutions based on cost and robustness, and can therefore be used to obtain solutions that are executable in practice. Therefore, the result of our algorithm can give planners an additional decision support.