近年来,随着能源短缺和环境污染问题愈演愈烈,高效节能污染少的电动出租车作为一种新能源公共交通工具在应对能源和环境危机所起的作用得到了社会的普遍认可。由于电动汽车续航距离的增加和家庭充电桩的普及,使得私人电动汽车对换电站的需求有限,因此设计高效的电动出租车专用换电站部署方案是一个亟待解决的关键问题。本文在此背景下,以部署的换电站数量最小化和负载均衡为主要优化目标,考虑单个换电站的服务范围和服务负载等因素,制定科学合理的最优部署方案,以期为政府节能减排策略的进一步完善提供理论依据,同时推动电动出租车产业的发展。本文首先综合分析介绍了电动出租车和换电站的基本概念以及相关的部署理论和方法,为后文奠定基础;接着,给出了电动出租车换电站部署难题的相关定义和证明;然后,针对苏州市3997辆出租车的真实运行轨迹大数据进行挖掘,获得了基于城市交通流量的出租车电池更换需求,并在部署规则的约束下,构建网络覆盖部署模型,设计了一种基于计算几何学的交通驱动规划算法求解模型。此外,本文还对该算法在空洞区域存在失效的情况进行了分析研究,并给出了部署方案的改进机制,帮助提高换电站的利用率。最后,以苏州市路网为例,采用真实出租车的运行轨迹数据对本算法进行实验验证。实验结果表明,相对于统一部署方案,本文所述算法获得的负载均衡部署方案在换电站数量和单个换电站的服务负载上均有优化,且所述的算法时间复杂度较低,运行效率较高,大幅度降低了出租车的平均等待时间和换电站服务负载方差,能够满足实际的应用需求。