This study is the first in the literature to examine the Braess paradox considering parking behavior in the autonomous vehicle (AV) environment, based on which the network design problem for the autonomous transportation system (NDP-ATS) is modeled. First, we introduce the AV commuting pattern considering the self-driving process for the parking purpose. We then illustrate the existence of two distinct Braess paradoxes that can occur in AV traffic networks with regards to parking space addition and network capacity expansion. They show that these two types of “improvement” measures might deteriorate the network system performance in an AV situation. Second, motivated to avoid the deterioration due to the introduced Braess paradoxes, we develop a bi-level programming model for NDP-ATS. The lower-level program addresses the network-equilibrium traffic assignment for AVs. The upper-level program aims to minimize the network-wide travel cost considering both occupied and empty AV trips by selecting the optimal design option accounting for road capacity enhancement and parking facility deployment simultaneously. To solve the developed bi-level model, the simplicial homology global optimization algorithm is employed along with the Frank–Wolfe algorithm and the CPLEX. Finally, the efficacy of the modeling framework is validated through case studies on the Sioux Falls city network and the Anaheim network. The results show that the developed methodology is capable of producing high-quality solutions with respect to savings in system-level travel costs for AV traffic. The results also highlight the impacts of parking fees on the system performance for the optimized network. Additionally, it is found that the two objectives, which minimize the total system travel cost and minimize that for empty AV trips only, are conflicting for certain scenarios. The methodological approach introduced in this work serves as a critical modeling device for infrastructure development and policy assessment for AV traffic.