一种电瓶换电柜布局城市的选址模型

梁会军， 沈 兵

（1. 湖北民族大学，湖北恩施 445000；2. 中国核工业第二二建设有限公司，湖北武汉 430050）

0 引言

随着外卖行业蓬勃发展，续航里程为50 km 左右的电瓶车已满足不了外卖骑手日工作需求，而让骑手中止工作并花费1 h～2 h为电瓶充电将严重影响他们的工作效率[1-2]。因此，外卖平台近年已联合各换电服务公司在城市的街头巷尾陆续安装有不同品牌的换电柜[3]。这些换电柜能有效解决外卖骑手即时性用电问题，也能避免电瓶车用户自行充电诱发的各种安全隐患[4-6]。但很多换电柜在建设时没有得到充分考究和规划，导致换电柜建设后出现扰民、占用人行横道、影响市容和资源错配等现象[7-8]。为了均衡配置换电柜资源，让换电柜更好地融入城市，为电瓶车用户提供便利性的换电服务，从外卖骑手的工作特性进行分析，结合地区外卖行业发展现状和城区道路规划以及城市整体布局，构建换电柜选址模型。该模型通过模拟外卖员接单送餐行为计算其欲换电地点。在欲换电地点的基础上，融合遗传算法思想，应用改进的K-means聚类算法优化种群并应用Pareto优化排序算法择取优质的选址方案，为换电柜规划建设提供优质的选址方案集。

1 选址模型影响因素及前提假设

1.1 选址模型影响因素

构建换电柜选址模型应从换电柜用户需求、换电服务公司运营成本以及城市整体规划等方面分析影响因素。为了方便骑手进行换电，换电柜安置点应在骑手经常工作的路径附近。根据当地外卖行业发展情况及骑手数确定换电柜配置数量。应与地区内各行政部门做好沟通，采纳有效建议，考虑城市5～10年发展规划后择取选址方案。换电柜选址充分考虑到城区道路规划和商城、医院、产业园区等公共场所的分布情况。配置换电柜应与生活区和人群密集地区保持一定距离，在保证用电安全和质量安全的前提下不影响市容市貌。

1.2 选址模型前提假设

经过查阅相关文献和走访调查后，对建立换电柜选址模型提出以下假设：安装于城市中每台换电柜多数拥有12个充电箱；为在换电高峰期满足用户的换电需求，保证城区所有换电箱拥有充电箱的总数应为城区骑手总数；满格电瓶续航里程为50 km，在里程焦虑的作用下续航里程下降至5 km 时，骑手会送完手头订单后选择就近换电。分析城区的道路结构并选取重要道路节点，在二维坐标系形成平面节点图。模拟外卖骑手接单送餐行为并计算其欲换电地点，需要考察每个道路节点附近商铺数量和社会公共场所配套情况定义该节点的商铺接单概率η1和外卖用户需要送餐概率η2。通过走访发现1 号节点附近有两所机关单位和较少商铺，经对比分析定义1 号节点的接单概率为0.4，送餐概率为0.6；节点2 附近有大型商城、宾馆及社区，因此定义其接单概率和送餐概率分别为0.8和0.7。

在模拟骑手接单送餐过程中，将与城区骑手数相同的目标随机分配到每个道路节点上。假设每个目标拥有50 km 的续航里程，即d=50 000，应用所有节点接单概率和送餐概率，通过轮盘赌机制计算各个节点商家需要骑手接单和外卖用户需要骑手送餐状态。然后确定距离目标点所在节点i 最近的需要骑手接单节点a和需要骑手送餐节点b，计算剩余续航里程d=d-dia-dab，并设定该目标点此时所在节点为b 节点。循环上述操作直至d＜5000 时，得到该目标点所在节点是此骑手欲换电地点。收集所有欲换电地点形成最终的目标点集合作为基础数据参与换电柜选址模型的迭代运算。

2 换电柜选址模型的求解

图1为换电柜安置点选址模型的整体框图。选址模型选用改进的Dijkstra 算法分析城区道路间的关联性，形成城区道路最优路径表和距离表。Dijkstra 算法采用的贪心策略求解起点到终点的最优路径和最近距离。但由于Dijkstra 算法采用的是全局搜索机制，其计算量将随着道路节点的增多而剧增[6]。在多次试验后发现，每次求解得到点对点的最优路径中各点间最优路径也是沿此路经，因此模型将每次应用Dijkstra 算法求到的最优路径信息尽可能地提取出来，归纳入最优路径表和距离表，以减轻模型整体计算量。

图1 换电柜安置点选址模型整体框图

根据城区规模大小输入换电柜安置点数量后，选址模型以遗传算法为框架，采用改进的K-means聚类算法求解换电柜安置点选址及配置方案。遗传算法是以优胜劣汰的自适应机制为主导思想，应用交叉、变异和选择等操作，将优良的基因遗传给后代，通过迭代计算求解出优质解[10]。K-means 聚类算法是种无监督学习的聚类算法，算法首先将K个聚类中心随机分配至目标区域内，以目标点到聚类中心的欧式距离最小为目标函数将目标点聚合成K类[11]。然后目标点以类为单位确定新的聚类中心，使该类中的目标点到聚类中心的平均距离最小，如此往复更新聚类中心得到最优解。在换电柜安置点选址模型中，将会应用城区道路距离代替节点间的欧式距离求解选址方案。为克服K-means聚类算法存在局部收敛性的缺陷，选址模型应用枚举法在种群迭代稳定后重新初始化种群参与迭代求解和对历史结果进行验算。

应用K-means聚类算法迭代求解选址方案时将应用dav、num、ddis_av三个指标对选址结果进行评价。其中dav表示所有目标点到最近聚类中心的平均值；num 表示离群点数，离群点是到最近聚类中心的距离超过离群点阈值的目标点；ddis_av指离群点到最近聚类中心平均距离。同时模型将记录下dav、num、ddis_min历史最小值分别为dav_min、nummin、ddis_av_min，在此基础上乘以扩展倍数或加上扩展个数形成对选址方案的评价指标limit。通过评价指标筛选后的选址方案再应用Pareto多目标优化算法择取出最前沿的优质方案形成选址方案集，为换电柜服务公司在规划城区换电柜建设过程中提供参考方案。

3 换电柜选址模型测试

为检验换电柜选址模型的可行性，本次测试以某市的道路规划、城市布局以及外卖业发展情况为例进行分析。首先根据该市的发展概况和道路间的关联性，在城区中择取了150个重要节点，绘制出如图2 所示的城区道路规划及重要节点分布简图。换电柜选址模型通过改进的Dijkstra 算法对重要节点分布简图进行分析，获得城区节点间的路径表path和距离表distance。

图2 某市城区道路规划及重要节点分布简图

依据该市外卖骑手的数量设定目标点数为600，每台换电柜拥有充电箱的数量为12，定义各个节点的商铺接单概率η1和外卖用户需要送餐概率η2形成节点需求概率表η。经过市场调查欲充电地点距离最近的换电柜安置点超过1000 m 时将会给骑手带来焦虑情绪，因此设定离群点阈值为1000。与此同时，设定所有目标点距离最近聚类中心平均距离的扩展倍数为1.2；离群点到最近聚类中心平均距离的扩展倍数为1.2；最少离群点数的扩展个数为10。评价指标limit 的初始值将被设定为[inf inf inf]，随着选址方案的不断优化，扩展个数和扩展倍数与历史最优值进行加/乘后对评价指标limit 进行持续更新。最后设定遗传算法迭代过程中的种群大小为1000，种群在迭代7 代且趋于收敛后将被重新初始化，模型迭代总次数超过3000且收敛后结束计算并输出结果。表1 是输入聚类中心为5 h～8 h时的相关参数。选址模型结果输出多个优质解及其相关参数，评价指标在迭代运算过程中每次更新至limit =[dav_limitnumlimitddis_av_limit]，三项评价指标和目标点到最近聚类中心的平均距离随着安置点数的增多而下降，离群点到最近聚类中心的平均距离都在1250 m以下。

表1 换电柜安置点数为5-8的各项参数

为进一步验证选址结果的有效性，此次选取每组中dav_min值最小的选址结果进行展示。图3 是在平面坐标系中，聚类中心为5 h～8 h 换电柜安置点分布情况。表2是4个选址方案的相关参数。

表2 四个优质解的相关参数

由表2 可以看出，增加换电柜配置点能有效降低外卖骑手前往换电的距离，避免骑手远距离换电，但配置点增多也将增加投资和运营成本，最终还需根据实际情况择取最适应的选址方案。以上4个优质选址方案仅是选址模型输出方案集中的一种，换电柜投资商可对比多个优质选址方案，再结合当地各路段土地性价比等实际情况选择换电柜最终的选址与配置方案。

4 结论

应用改进的Dijkstra 算法分析城区道路规划，在当地外卖业发展现状的基础上通过改进的Kmeans 聚类算法优化换电柜安置点选址方案，最后设定评价指标并应用Pareto多目标优化算法择取优质解形成换电柜选址方案集合。投资商依据实际情况对比后选择合适方案建设换电柜，既能避免电瓶车换电柜在街头乱建现象，又能促进换电柜资源随用户需求而配置，降低换电柜的运营成本。