This paper formulates robust optimization models for the problem of finding near-optimal locations for new intermodal terminals and their capacities for a railroad company, which operates an intermodal network in a competitive environment with uncertain demands. To solve the robust models, a Simulated Annealing (SA) algorithm is developed. Experimental results indicate that the SA solutions (i.e. objective function values) were comparable to those obtained using GAMS, but the SA algorithm could obtain solutions faster and could solve much larger problems. In addition, the results verify that solutions obtained from the robust models were more effective in dealing with uncertain demand scenarios.