Fuel consumption is among the most important criteria in train operations. Considerable efforts have been made to identify optimal speed for enhanced fuel economy. The train speed control is achieved through switching the power notches, which sets constant level of fuel supply to the engine in a typical diesel-electric locomotive. A global optimal speed, however, cannot be considered appropriate due to the localized variations in the track gradient and curvature, apart from the variations in the load. An efficient train operation also requires the train completes its journey within a given travel time. This study aims at determining optimal train speeds to minimize the total fuel consumption in completing the journey, while considering the local variations in the track geometry and other properties. A nonlinear mixed integer programming model is formulated to solve the considered problem using an off-the-shelf optimization software package. A multiphase-steps improved method is proposed for solving the considered problem more effectively. Numerical examples are presented to illustrate the developed model and solution method.