Supply Chain Management (SCM) describes the discipline of optimizing the delivery of goods, services and information from supplier to customer. Transportation network design is one of the most important fields of SCM. It offers great potential to reduce costs and to improve service quality. In this paper, we consider an extension version of two-stage transportation problem (tsTP) to minimize the total logistic cost including the opening costs of distribution centers (DCs) and shipping cost from plants to DCs and from DCs to customers. To solve the problem, we developed a priority-based Genetic Algorithm (pb-GA), in which new decoding and encoding procedures were used to adapt to the characteristic of tsTP, and proposed a new crossover operator called as Weight Mapping Crossover (WMX). An experimental study was carried out into two-stages. While the effect of WMX on the performance of pb-GA was investigated in the first stage, pb-GA and another GA approach based on different representation method were compared according to solution quality and solution time in the second stage.