The objective of this paper is to investigate the importance of introducing stochastic elements into service network design formulations. To offer insights into this issue, we take a basic version of the problem in which periodic schedules are built for a number of vehicles and where only the demand may vary stochastically. We study how solutions based on uncertain demand differ from solutions based on deterministic demand and provide qualitative descriptions of the structural differences. Some of these structural differences provide a hedge against uncertainty by using consolidation. This way we get consolidation as output from the model rather than as an a priori required property. Service networks with such properties are robust, as seen by the customers, by providing operational flexibility.