In systems with interrelated alternatives, the benefits or costs of each alternative depend on which other alternatives are selected and when they are implemented. System interrelations and uncertainties in various elements of transportation systems such as future demand, make it difficult to evaluate project impacts with analytical methods. This study proposes a general and modular framework for planning and scheduling interrelated infrastructure projects under uncertainties. The method should be general enough to address the planning problem for any interrelated system in a wide range of applications. The goal is to determine which projects should be selected and when they should be implemented to minimize the present value of total system cost, subject to a cumulative budget flow constraint. For this purpose, the scheduling problem is formulated as a non-linear integer optimization problem that minimizes the present value of system cost over a planning horizon. The first part of this dissertation employs a simple traffic assignment model to evaluate improvement alternatives. The algorithm identifies potential locations within a network that needs improvements and considers multiple improvement alternatives at each location. Accordingly, a probabilistic procedure is introduced to select the optimal improvement type for the candidate locations. The traffic assignment model is used to evaluate the objective function and implicitly compute project interrelations, with a Genetic Algorithm (GA) developed to solve the optimization problem. In the second part of the dissertation, the traffic assignment model is replaced with a more detailed evaluation model, namely a Cell Transmission Model (CTM). The use of CTM significantly improves the model by tracking queues and predicating queue build-up and dissipation, as well as backward propagation of congestion waves. Finally, since GA does not guarantee global optimum, a statistical test is employed to test the optimality of the GA solution by estimating the probability of arriving at a better solution. In effect, it is shown that the probability of finding a better solution is negligible, thus demonstrating the soundness of the GA solution.