With the rapid development of the courier industry, customers are placing higher demands on the cost and delivery time of courier services. Therefore, this paper focuses on the bi-objective express transportation network design problem (BO-ETNDP) to minimize the operation cost and maximum arrival time. A multi-structure parallel design methodology (MS-PDM) is proposed to solve the BO-ETNDP. In this methodology, all topological structures commonly used in designing transportation networks are sorted out. For each topological structure, a novel bi-objective nonlinear mixed-integer optimization model for BO-ETNDP is developed considering the impact of the hub’s sorting efficiency on the operation cost and arrival time. To solve these models, a preference-based multi-objective algorithm (PB-MOA) is devised, which embeds the branch-and-cut algorithm and Pareto dominance theory in the framework of this ranking algorithm. In the case study, the applicability of the proposed methodology is verified in a real-world leading express company. The results show that our methodology can effectively avoid the limitation of solving the BO-ETNDP with a specific structure. Besides, the suitable topology for designing express transportation networks in different scenarios are explored through the sensitivity analysis.