Recent proposals for expanded intercity passenger rail service in the United States have included plans for incremental improvements to existing Amtrak service. Improvements to existing services aim to accommodate faster and more frequent passenger train operation, generally on track owned and operated by freight railways. Various projects and approaches can be considered when the running time of passenger trains is being decreased on a particular corridor. Raising the maximum operating speed can yield different benefits on different sections of the route, and conditions on adjacent sections can interact. For instance, the marginal travel time benefit of improving segments of a line from a maximum speed of 79 to 110 mph is less than the benefit of other improvements to eliminate segments currently restricted to lower speeds. Therefore, to maximize the potential of limited resources, project investments must be selected carefully to improve performance in a cost-effective manner. This paper presents a methodology for optimally selecting projects or establishing program budgets to reduce running time on a passenger rail corridor with consideration of capital, maintenance, and operating costs. The proposed project selection model is formulated with genetic algorithms. In the model, a route is divided into sections that can be independently upgraded, and the objective function is formulated as minimization of running time along the route. This model can aid in quickly and efficiently developing a strategic plan for improving running time on passenger rail corridors.