Crowd-shipping is an emergent solution to avoid the negative effects caused by the growing demand for last-mile delivery services. Previous research has studied crowd-shipping typically at an operational planning level. However, the study of support infrastructure within a city logistics framework has been neglected, especially from a strategic perspective. We investigate a crowd-sourced last-mile parcel delivery system supported by a network of strategically located mini-depots and present a two-stage stochastic network design problem with stochastic time-dependent arc capacity to fullfill stochastic express deliveries. The first-stage decision is the location of mini-depots used for decoupling flows allowing more flexibility for crowd-demand matchings. The second stage of the problem is the demand allocation of crowd carriers or professional couriers for a finite set of scenarios. We propose an exact Benders decomposition algorithm embedded in a branch-and-cut framework. To enhance the algorithm, we use partial Benders decomposition, warm-start, and non-dominated cuts. We perform computational experiments on networks that were inspired by the public transportation network of Munich. The proposed solution method outperforms an off-the-shelf solver by solving instances in between 3% to 39 % of its run time. The results show the potential to exploit the stochastic crowd flows to deliver packages with deadlines of 3 or 8 hours. The crowd can transport 8.3% to 32.5% of the total demand by using between 4% to 24% of the crowd capacity and we observe average daily savings of 2.1% to 7.6% of the total expected operational cost. The results show values of the stochastic solution of at least 1% and up to 10%.