刘晓胜，张 芮，朱宏林，王 娟

（哈尔滨工业大学 电气工程及自动化学院，黑龙江 哈尔滨 150001）

0 引言

电动汽车相对于传统汽车具有明显的节能减排的特点，成为21世纪最具有潜力的交通工具［1］。但续航里程是制约电动汽车发展的主要因素。动力电池作为电动汽车的动力来源，快速更换电池是解决这种问题的有效途径之一［2］。对动力电池配送车辆进行路径优化，不仅可以提高经济效益，还可以及时满足电动汽车的能量供给［3］。由此可见，合理选择满足约束条件的动力电池配送最优路径，进一步提升充换电站服务体系运行管理程度，具有非常重要的现实意义［4］。

物流配送中的路径选择优化问题是一个典型的NP-hard问题，国内外学者对其进行了深入的研究，并提出很多求解算法。这些算法可以分为精确求解算法和启发式算法两大类［5］。在精确求解算法中，计算量与问题的规模呈指数增加关系，求解耗费时间相当长，效率低［6］。启发式算法以及一些组合算法成为研究路径优化问题的主要算法［7］，但是为了保证可行解，导致遗传算法爬山能力差、禁忌搜索算法全局性差等问题。基本的启发式算法在求解大规模的路径优化问题时存在各种缺陷［8］。

蚁群算法是一种新的种群启发式算法，可以看作是一个分布式的多智能体系统。它可以在问题空间的多点同时独立进行解搜索，具有很强的鲁棒性［9］。本文根据路网的特点对蚁群算法进行改进，同时为了避免算法在搜索过程中陷入局部最优，在算法中引入惩罚因子，在保证全局最优的同时还可以提高算法的收敛速度。……