With the increased emphasis on sustainability, several logistics companies have purchased alternative fuel vehicles, like Compressed Natural Gas (CNG) trucks, to support their delivery operations. However, CNG trucks face several challenges on their way to replacing traditional diesel trucks such as limited mile range and small load capacity. 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, while the public fueling stations are limited. This research develops efficient deployment strategies for these carriers.