This paper addresses a novel liner shipping fleet deployment problem characterized by cargo transshipment, multiple container routing options and uncertain demand, with the objective of maximizing the expected profit. This problem is formulated as a stochastic program and solved by the sample average approximation method. In this technique the objective function of the stochastic program is approximated by a sample average estimate derived from a random sample, and then the resulting deterministic program is solved. This process is repeated with different samples to obtain a good candidate solution along with the statistical estimate of its optimality gap. We apply the proposed model to a case study inspired from real-world problems faced by a major liner shipping company. Results show that the case is efficiently solved to 1% of relative optimality gap at 95% confidence level.