新能源货车充电站规划选址方法研究

四川中电启明星信息技术有限公司 徐小云 李欢欢 王红蕾

1 引言

当下充电站选址问题受到国内外学者的广泛关注，研究已涉及交通、能源、电力工程、计算机科学、管理科学等多个领域，从不同角度研究充电站选址的影响因素、选址方法、算法优化等。文献[1]以充电站投资运行成本最小为目标构建充电站选址两步法。文献[2]建立路径选择模型和交通满意度评价模型，考虑充电站定容选址对配电网了和交通网络的影响。文献[3]基于博弈论提出博弈优化模型和算法，对充电站选址方案进行评价。依据目前电动车司机的充电习惯来决定充电站的分布，以最大化满足现有用户的充电需求。分析认为用户充电习惯为在路途起点和终点充电，而非路途中间，并且使用遗传算法最大化充电桩数量，并在不同区域提供不同类型充电桩。

目前，大部分研究没有考虑到车辆使用属性和竞争因素对充电站选址的影响。因此本文针对新能源货车的特点，结合聚类算法对相关POI 数据进行聚类分析，并考虑已有充电站对选址建站的影响，对货车充电站展开规划选址。

2 方法概述

聚类算法目前在选址和区域划分中运用较多，比如常用K-means 算法具有快速高效、易于理解、理论可靠的优势，但也有一些问题，如聚类数目需预先确定、离群点影响大、容易形成局部最优解等。针对K-means 的缺陷，国内外学者从不同角度对传统聚类算法进行了改进。文献提出了初始k 值选取方法，比如基于图像分割的思想使用分水岭算法，或基于层次聚类的思想对传统算法改进等；文献提出了初始聚类中心点的选取方法，比如选取密度最大的对象，或首选距离最大的两点作为初始聚类中心等；文献提出了离群点的检测和去除方法，比如使用LOF 算法来筛出，或基于网格密度对传统算法改进等。

本文针对新能源货车充电站选址进行研究，根据实际选址需求，考虑充电需求与竞争选址，结合改进后的聚类算法，构建出新能源货车充电站规划选址方法，整体思路如图1所示。首先，将规划选址区域进行网格划分，分析配送点和竞争场站在网格中的空间分布；其次，根据网格中配送点的空间分布计算栅格充电需求指数，并根据网格中竞争场站的空间分布计算栅格充电供给指数；然后，优化传统聚类算法，避免离群点对聚类的影响与局部最优问题；最后，使用优化的聚类算法结合充电需求指数和充电供给指数对选址区域的栅格进行聚类，得到规划选址站址。

图1 货车充电站的规划选址方法

3 新能源货车建站需求的空间分析

充电需求一般分两类，一类是路途中需求，常存在于长途行程中途补充电量的情况；另一类是始末点需求，由于电动车充电时长较长，因此多选择在路途起点或终点休息时进行充电。本文主要针对新能源货车的选址，据调查显示，由于当前电池技术与配套设施的限制，目前新能源货车多用于城市配送服务。由于路程较短，因此较多考虑始末点需求，即在配送起点或终点进行充电。本文从城市配送相关POI 出发，结合竞争场站信息，分析区域内新能源货车的建站需求空间分布。

3.1 选址区域分析

整个选址规划区域Q 经度区间为[LOmin,LOmax]，纬度区间为[LAmin,LAmax]，按经纬度将区间划分为(M×N)个方格网格，假设至少在长宽三公里方形栅格范围内能找到合适的建站位置，因此满足式（1），网格空间，规划区域内任意一点qij有唯一对应的网格gmn，使得qij∈gmn。

3.2 城市配送POI 分析

表1为城市配送点POI 数据，配送点包含两大类，一类是配送起点，如下表中物流仓储等；一类是配送终点，如下表中超市、市场等。新能源货车在配送起点装载货物后，运送到一个或多个配送终点。

表1 城市配送POI

图2为配送点分布图，从配送点分布图可看出，存在一些配送点远离其他配送点，如果在这些离群配送点附近建站，则会降低建站效益。因此在聚类过程中，需考虑离群点对聚类规划选址的影响。

图2 配送点分布图

配送点集合W={w1,w2,…,wn}，集合中每个元素包含该配送点的经纬度wi=(loi,lai)。根据3.1划分的网格空间和配送点位置信息，可得配送点网格热度矩阵如式（2），元素aNM表示第n 行m 列的网格区域内的配送点的热力值，热力值越高的区域代表配送点越密集，相对充电需求越大，建站需求也就越大。

3.3 已有场站分析

目前区域内存在已建充电站，如表2所示为充电站名称、地理位置、充电桩数等信息。对新建站的选址规划应考虑已有场站带来的影响。已有充电站主要有以下几种类型：在原露天停车场增配充电桩、路边停车位增配充电桩、地下停车场增配充电桩、新建专用充电站。对于在原有停车场和停车位上增配充电桩的方式，由于停车位大小有限，因此对充电车辆大小有所限制。由于本文是针对货车充电站的选址，货车所需停车位比普通车位大，因此主要依靠新修的货车充电站为其提供充电服务，在竞争选址上也主要考虑单独修建的可供货车充电的充电站对规划选址的影响。

表2 充电站信息

筛选出货车充电场站的集合V={v1,v2,…,vn}，集合中每个元素包含该配送点的经纬度和充电桩数量vi=(loi,lai,ci)。根据3.1划分的网格空间和充电站分布，得到已有场站网格热力矩阵如式（3），元素bnm表示第n 行m 列网格的已有场站热力值，热力值越高的区域表示已有场站越密集，对应充电供给也越充足，建站需求就越少。

4 基于改进的聚类规划选址方法

4.1 竞争选址下的建站需求

充电站市场是一个竞争市场，后进入市场的场站规划选址是在竞争环境下的选址问题。竞争选址问题上，影响的因素有很多，比如：竞争设施的位置距离越近影响越大；市场需求越大设施抢夺的市场份额也越大；竞争设施区域大小等原因造成的最大容量限制了抢夺的市场份额；由集群效应中造成设施之间既是竞争关系也是合作关系。

因此，本文考虑竞争选址，既可以考虑周边已有场站的距离因素对规划选址的影响，同时也可以考虑周边场站的容量对规划选址的影响。本文提出充电供给指数，结合周边充电站位置信息及其充电桩数量的信息，公式（4）计算出每个网格的充电供给指数ES，指数范围为[0,1]，指数越大表示该网格充电供给越多，建站需求越低。

d(·)是由公式（5）计算两点的曼哈顿距离；p为某网格中心点地理位置；(xi,yi)和(xj,yj)为两点坐标值；si为第i 个充电站地理位置；Ci为该充电站的充电桩数量；k 为充电站数量；R 为充电站服务距离。城市道路中汽车的平均时速为[20,50]km/h，汽车前往充电站的路程时长为半小时以内较合理，因此充电站服务距离R 设置为10km。根据公式（4）计算出所有栅格的充电供给指数后，考虑建站成本，若该网格充电供给大于0，则不考虑在该网格建站。根据充电供给指数，得到建站需求矩阵C 如式（6）所示，cnm 值为0或1，表示考虑竞争场站的影响下，是否可在该网格建站，1为可考虑建站，0为不考虑建站：

4.2 离群配送点

传统K-means 算法中，离群点会影响聚类的准确性。并且，考虑在离群配送点周边建站对建站效益的影响，本文在K-means 算法中结合密度聚类，分离远离其他簇的小簇，从而减少离群点对聚类选址的影响。具体操作步骤如下：

（1）对配送点集合W 中的任意两点x 和y，按照式(7)计算样本点两两间欧式距离d；

（2）设置距离阈值θ。为避免在离群点周边建站，考虑配送点车辆前往离群配送点周边行驶时间不超过半小时较合理，因此距离阈值为行驶时间半小时的路程，由于城市道路汽车的平均时速为[20,50]km/h，即曼哈顿距离10km 的路程，相对应的欧式距离为km，因此距离阈值θ 设置为10km；

（3）将步骤（2）获取的距离阈值θ 作为邻域阈值Eps，由于此处用密度聚类寻找离群点，因此minPts 为1，即一个点即可构成一个簇，使用DBSCAN 对样本进行密度聚类；

（4）根据步骤（3）得到的密度聚类结果，得到远离其他簇的小簇且簇中元素个数小于等于2，将这样的簇中的点视为离群点；

（5）从配送点集合W 中将离群点剔除得到新的集合W’。

4.3 改进的聚类算法

传统K-means 算法需要预先确定聚类个数k，k 值选取的不同会影响聚类中心的变化，得到的结果为局部最优。因此，本文在传统K-means 算法上作改进，引入核密度估计，优化局部最优问题，避免随机确定初始聚类中心引起的局部最优解。具体操作步骤如下：

（1）根据3.1所述，将选址规划区域划分为(m×n)个格点，每个格点中心为一样本点，所有样本点构成预选点集合G；

（2）考虑竞选址的因素，根据4.1中的建站需求矩阵，把预选点集合G 中cnm 值为0的网格从预选点合集中去除得到新的预选点集合G’。

（3）根据分离离群点后的配送点集合W’的空间分布，利用高斯核密度估计计算每个栅格样本点的核密度估计值，如式（8）。其中k(·)是核函数；h 是带宽，表示在x 的邻域[x-h,x+h]计算x 的密度函数；n 是带宽范围内观测点的数量，i=1,…,n。本文采用的核平滑函数是高斯核函数，如式（9），其中σ 是带宽，控制高斯核函数的局部作用范围。

（4）根据每个栅格的核密度估计值，根据公式（10）计算出每个栅格的充电需求指数。

（5）选择预选点G’中充电需求指数最高的点，作为一个聚类中心点p，将其放入集合P，并根据该点创建一个新类簇c，将其放入集合C；

（6）根据步骤（5）中选出的聚类中心点p，设置建站距离R 代表场站之间最短距离，将p 和其服务半径R 内的点从预选点集合G’中去除，得到新的预选点集合G’；

（7）重复步骤（5）（6），直到所有配送点到最近充电站的行驶路程最多半小时即曼哈顿距离10km，得到聚类分析的结果。

4.4 充电站规划选址方法实现

本文以成都为例，运用改进的聚类算法构建的选址方法，进行成都市货车充电站规划选址，确保成都市内新能源货车充电便利性的同时，最小化建站成本，最大化充电站潜在效益。新能源货车充电站规划选址方法，是考虑充电需求与竞争选址，使用改进的聚类算法进行规划选址，该改进后的算法能减少离群点对聚类效果的影响，并避免聚类局部最优问题。方法实现流程如下：

（1）数据收集及预处理。本文以成都为例，爬取成都市区域内各配送点信息，以及已有充电站信息，并对数据进行特征值筛选、数据去重、空值处理等预处理操作。如表3、表4为数据预处理后的数据，表3为物流商圈位置信息，表4为已有货车充电站位置信息和充电桩数量。

表3 成都市物流商圈位置信息

表4 成都市货车充电站位置及充电桩数量

（2）竞争选址。根据收集到的已有货车充电站的位置和充电桩数量信息，计算每个栅格的充电供给指数，画出充电供给热力图如图3，颜色越深代表充电供给越充足。本文4.1中设定，若该网格充电供给大于0，则不考虑在该网格建站，因此只考虑在白色区域建站。

图3 充电供给热力图

（3）利用密度聚类分离离群点。由文中4.2，设定邻域阈值为10km，点数阈值为1，利用DBSCAN寻找出离群点并剔除。如图4所示，一个点代表一个配送点，通过密度聚类为10个簇，相同颜色的点属于同一簇。如图5所示，为簇的元素数量柱状图，将元素个数少于10的簇中的点视为离群配送点，将其剔除。

图4 DBSCAN 聚类寻找离群点

图5 DBSCAN 密度聚类分布图

（4）根据改进后的聚类算法计算出聚类中心。将成都区域划分为3km 长度的正方形小网格，即41×26个格点，根据物流商圈分布，计算出每个格点样本的充电需求指数，得到充电需求指数热力图如图6所示。此示例假设建站距离为9km，使用改进后的聚类算法算出多个聚类中心，该聚类中心所在网格即为场站选址推荐点，如图7所示，红点所在网格即代表规划选址推荐点。

图6 成都市充电需求指数热力图

图7 改进后的聚类规划选址结果

5 结果评估

5.1 评估模型建立

5.1.1 平均充电路程

充电站选址的目标之一为考虑货车充电的便利性。本文通过货车前往充电站的距离为评估模型，在构建评估模型前，明确如下假设：物流商圈中的货车的优先考虑距离最近的五个充电站，并且路程距离假设为两点间的曼哈顿距离。

式中：d(·)是由公式（11）计算的曼哈顿距离；p 为某配送点；si为距离该配送点最近的五个充电站之一。

5.1.2 平均周边配送点的数量

充电站选址的另一目标是充电站效益。本文通过充电站周边商圈数量为评估模型，在构建评估模型前，明确如下假设：充电站的主要充电车辆来源于周边半小时路程内即十公里范围内的物流商圈，并且物流车数量与物流园区数量呈正相关。

5.2 结果评估

设置建站距离分别为3km 至10km，当建站距离大于10km，配送点到最近充电站路程大于10km，因此最大考虑建站距离10km。建站个数、平均充电路程和平均周边商圈个数的结果如下表5所示，走势图如图7所示。通过对比可看出，随着建站距离的增加，建站个数先大幅降低，7km 后逐渐趋于平滑；平均充电路程缓慢增加；平均周边商圈的数量先增加，9km 后小幅降低。因此，考虑建站成本则距离越大越有利，考虑建站平均收益则距离越大越有利，考虑充电便利性则距离越小越有利，综合考虑以上三点因素，可选择建站距离7km 至8km，此时可较好的平衡建站成本、充电便利性与建站收益。

表5 选址结果对比

图8 选址结果趋势图