Transportation network vulnerability envelope (TNVE), constituted by the upper and lower bounds of network performance among all possible disruption scenarios, has recently been proposed as a systematic tool to characterize the impact of simultaneous disruptions of multiple links in a transportation network. Both pessimistic and optimistic cases and the possible range of disruption consequences can be revealed by the TNVE, which can be modeled as a unified optimization problem without the need to enumerate and evaluate all possible disruption scenarios. Specifically, the TNVE problem can be formulated as a binary integer bi-level program (BLP), in which the upper-level problem maximizes/minimizes the remaining network performance under a given number of disrupted links, and the lower-level problem adopts the shortest path problem to check the post-disruption connectivity of each origin–destination (O-D) pair while circumventing the cumbersome path enumeration or path set pre-generation. However, the binary integer BLP is computationally intractable, which hinders the applications of TNVE in practice. This study aims to develop an efficient method based on the random key genetic algorithm (RKGA) for determining the TNVE under simultaneous multi-link disruptions. The main features and benefits of the proposed method include: (a) it simultaneously solves the upper- and lower-bound problems at the same time while guaranteeing the feasibility of all solutions in the solution procedure; (b) it improves the computational efficiency to ensure the applicability to real transportation networks; and (c) it can provide a variety of alternative solutions in addition to the single optimal one, which facilitates the derivation of TNVE buffer and identification of sub-important links. These benefits make the proposed method efficient and effective for solving the TNVE problem. The applicability of the proposed method is demonstrated with small and medium-sized networks, as well as a large-scale real road network. Numerical experiments are conducted to illustrate the usage of TNVE for vulnerability analysis of transportation networks.