Transportation models play an important role in logistics and supply chain management for reducing cost and improving service. This paper studies the fixed-charged transportation problem with random variables, and the mathematical model for the problem under uncertain condition is established. According to theory of uncertainty, an approach to conversion of the stochastic constraints to their respective deterministic equivalents is formulated. Applying the property that a transportation network is a spanning tree, a genetic algorithm based on tree is adopted to solve our problem. A numerical example is provided to illustrate the effectiveness of the algorithm.