在当前大力推广使用压缩天然气汽车(Compressed　Natural　Gas简称CNG汽车)的形势下，CNG加气站的规划问题已凸现出来。本文在论述了CNG加气站选址的国内外研究状况之后，针对加气站选址问题进行了用户需求分析　，给出了服务小区划分和需求点确定的方法。比较了现有CNG加气站选址的几种方法以及它们不同的应用范围，从加气站的使用者和运营者两方面综合考虑，按照加气站运营者投资成本和加气站使用者加气成本最小的原则建立了CNG加气站选址模型。　对于CNG加气站的选址问题，其模型及算法复杂，具有NP难性质，传统的优化算法由于模型中变量和约束数目过多或者问题规模较大而被放弃使用，因此本文选择在解决优化方面问题具有很大优势的遗传算法进行CNG加气站选址模型的求解。然而，遗传算法无论是在其理论上还是实现方法上都有待完善，只有对其不断改进，才能更好地发挥遗传算法的性能和特点，使其更适用于CNG加气站的选址问题。本文在对遗传算法的特点、发展过程、应用领域以及其理论基础介绍之后，针对常数交叉率的遗传算法搜索能力不强的问题，设计了随遗传代数余弦下降的自适应交叉率公式，并通过标准的测试函数验证了改进的效果。结合CNG加气站选址问题的具体情况，本文还比较了其它几种自适应交叉率公式与本文设计的公式的优劣。经过比较，本文设计的自适应交叉率公式能够加快遗传搜索的速度，较容易的搜索出问题的最优解。为了使算法更贴近实际，针对不同的选址区域，在程序上作了一定的调整，使得算法不仅仅用于空白区域的加气站选址，还可以处理在选址区域内已有加气站和存在不能建站的点的情况。目前遗传算法在CNG加气站选址中的应用还很少，将改进遗传算法运用到CNG加气站选址问题，以得出CNG加气站优化的选址方案，这是本文的主要工作及努力的方向。论文研究工作及其结果力求对城市清洁汽车行动中制定CNG汽车加气站建设规划有所帮助，并对现代城市绿色（交通）物流发展研究能有所贡献。