The focus of this work is to determine the optimal storage capacity to be installed on transhipment nodes by shippers in a dynamic shipper carrier network under stochastic demand. A two stage linear program with recourse formulation is developed where in the first stage, the shipper decides the optimal capacity to be installed on transhipment nodes. In the second stage, the shipper chooses a routing strategy based on the realized demand. The performance of the following solution methods: Stochastic L Shaped Method, Regularized Decomposition and L ShapedMethod with preliminary cuts were compared for various network sizes and numerous demand scenarios. A novel capacity shifting heuristic was introduced to generate a feasible implementable solution which significantly improves the performance of Regularized Decomposition and provides the best performance in the cases tested. Various ways of generating analytical bounds on the objective function value was discussed. The new capacity shifting heuristic was found to be efficient in generating tight upper bounds. Even though the formulation considered in this paper is for a single commodity, the model can be easily extended to account for multiple commodities.