With the increased emphasis on sustainability, several large logistics companies have purchased Alternative Fuel Vehicles (AFVs) to support their delivery operations. However, without effective deployment strategies for fueling stations it is not clear that these initiatives will result in net savings in emissions. Many of the local freight delivery operations are performed by independent truckers who are too small to manage their own fueling station. Thus, it becomes imperative to develop efficient deployment strategies for fueling stations for these carriers that will have minimal impact on their routing operations. This research will address the following questions regarding the impact on the location of the fueling stations on the deployment of AFVs for freight delivery. For a given set of origins and destinations, what would be the route efficiency losses? Could we end up with more net fuel consumption and GHG emissions? Under what circumstance would introduction of AFVs lead to the least efficiency losses?