To build a cooperative logistics network covering multiple enterprises, a planning method that can build a long-distance transportation network is required. Many strict constraints are imposed on this type of problem. To solve these strict-constraint problems, a selfish-constraint-satisfaction type genetic algorithm (GA) is proposed. Moreover, a constraint pre-checking method is also applied. Our experimental result shows that the proposed method can obtain an accurate solution in a practical response time.