This paper presents a bi-criteria binary linear programming model for locating alternative-fuel refueling stations on a directed transportation network with two conflicting objectives of maximizing the total vehicle-miles traveled (VMT) per year covered by the stations and minimizing the capital cost for constructing the refueling infrastructure. The proposed model is validated with an application to the Pennsylvania (PA) Turnpike System regarding the location of liquefied natural gas (LNG) refueling stations on existing service plazas. A regression model is developed to accurately estimate construction costs for LNG refueling stations on the turnpike. To solve the bi-objective model, the second objective (capital cost) is treated as an infrastructure budget constraint and the model is run considering a range of infrastructure budget values. Given that alternative fuels and fuel economy legislation dates back to the Clean Air Act Amendment of 1970, which created initiatives to reduce mobile sources of pollutants, further analysis is performed on the case study to estimate the potential reduction of pollutants on the PA Turnpike as a function of the LNG infrastructure cost.