Alternative fuel vehicles (AFVs) have seen increased attention as a way to reduce reliance on petroleum for transportation, but adoption rates lag behind conventional vehicles. One crucial barrier to their proliferation is the lack of a convenient refueling infrastructure, and there is not a consensus on how to locate initial stations. Some approaches recommend placing stations near where early adopters live. An alternate group of methods places stations along busy travel routes that drivers from across the metropolitan area traverse each day. To assess which theoretical approach is most appropriate, drivers of compressed natural gas (CNG) vehicles in Southern California were surveyed at stations while they refueled. Through GIS analysis, results demonstrate that respondents refueled on the way between their origins and destinations ten times more often than they refueled near their home, when no station satisfied both criteria. Freeway interchanges, which carry high daily passing traffic volumes in metropolitan areas, can be appropriate locations for initial stations based on these results. Stations cannot actually be built directly at these interchange sites, so suitable locations on nearby street networks must be chosen. A network GIS method is developed to assess street network locations' ability to capture all traffic passing through 72 interchanges in greater Los Angeles, using deviation from a driver's shortest path as the metric to assess a candidate site's suitability. There is variation in the ability of these locations to capture passing traffic both within and across interchanges, but only 7% of sites near interchanges can conveniently capture all travel directions passing through the interchange, indicating that an ad hoc station location strategy is unlikely to succeed. Surveys were then conducted at CNG stations near freeway interchanges to assess how drivers perceive and access refueling stations in these environments. Through comparative analysis of drivers' perceptions of stations, consideration of their choice sets, and the observed frequency of the use of a freeway to both access and leave these stations, results indicate that initial AFV stations near freeway interchanges can play an important role in regional AFV infrastructure.