This paper proposes a detailed formulation to optimize transit road space priority at the network level and utilizes an efficient heuristic method to find the optimum solution. Previous approaches to transit priority have a localized focus in which only limited combinations of transit exclusive lanes could be assessed. The aim of this work is to reallocate the road space between private car and transit modes so that the system is optimized. A bilevel programming approach is adapted for this purpose. The upper level involves an objective function from the system managers' perspective, whereas at the lower level, a users' perspective is modeled. To take into account the major effects of a priority provision, three models are used: 1) a modal split; 2) a user equilibrium traffic assignment; and 3) a transit assignment. A genetic algorithm (GA) approach is used, which enables the method to be applied to large networks. Application of a parallel GA is also demonstrated in the solution method, which has a considerably shorter execution time. The methodology is applied to an example network, and results are discussed. It is found that the proposed methodology can successfully consider benefits of all stakeholders in the introduction of transit lanes. Furthermore, using parallel GA enables the methodology to be used for real-world-network scale in a shorter computer processing time.