考虑服务半径的电动汽车充电设施选址问题

刘 慧，张 迪，冷凯君

(1.湖北经济学院 湖北物流发展研究中心，湖北 武汉 430205；2.华中科技大学 管理学院，湖北 武汉 430074)

0 引言

电动汽车因其清洁、节能的显著优势，正逐步成为汽车市场的主流发展方向。在巨大的环境压力和未来市场空间预期的双重作用下，各国政府纷纷介入电动汽车市场，并将发展电动汽车作为应对能源和环境问题的重要举措。然而，电动汽车市场的推广却相对缓慢，其中一个重要原因是电动汽车续航里程短，使其一问世就遭遇了里程焦虑症(指驾驶电动汽车时由担心突然没电引起的精神痛苦和忧虑)。传统燃油汽车也有续航里程问题，只是目前加油站星罗棋布，已使这个问题得到解决。电动汽车相对传统汽车来说还是新生事物，在实际使用环节中的充电设施配套体系尚不完善，充电难成为影响消费者购买电动汽车的最大障碍[1]。同时，已建成的部分充电设施却呈现出使用效率低甚至闲置的状况，形成了当前电动汽车发展的“充电怪圈”[2]，即充电难与充电设施闲置现象并存。如何根据电动汽车发展初期用户的充电特点，在国内城市交通拥挤、停车位紧张的大环境下合理布局充电设施，解决消费者“里程焦虑”问题，对电动汽车的发展具有重要意义[3]。

目前，已经有学者在经典选址模型基础上，根据充电设施特点，对充电设施选址问题做了相关研究。Kuby等[4]提出基于路径流的新能源补充设施选址模型(Flow Refueling Location Model, FRLM)，在建立P个设施约束下，考虑如何选址使覆盖的过路需求最多；Wang等[5]研究多等级充电设施选址问题，使建立充电设施的成本和充电成本之和最小；MirHassani等[6]通过添加节点和边的方式构建扩张网络，提出充电设施选址的截流模型和最大覆盖模型；Zhang等[7]将单阶段容量限制FRLM扩展为多阶段模型，并以最大化用户需求为目标；Yang等[8]基于顾客满意度提出充电服务网络设计模型，并设计禁忌搜索算法求解模型；He等[9]对北京充电设施选址布局问题进行案例研究，将当地的供应限制和对充电设施的需求纳入3种经典选址模型；Lin等[10]提出P-中心截流选址模型，该模型在建立P个设施的约束下，最小化出行者的最大偏移距离；Zhu等[11]以成本最小化为目标，提出考虑不同用户类型的充电设施选址模型，决策充电站位置和站内充电桩数量；褚玉婧等[12]从需求点效用最大化的角度出发，提出基于时间满意的逐渐覆盖充电站选址模型；陆坚毅等[13]从充电站运营商的角度出发，考虑实时电价和充电时间，提出充电成本最小的数学模型；郭放等[14]将电动汽车在配送货物途中的充电时间和电池损耗成本纳入目标函数，建立线性规划数学模型统筹安排车辆行驶路径，并采用充电策略最小化运营成本。

现有文献研究表明，充电设施选址问题大多在经典选址模型上加入续航里程约束，而且考虑用户需求产生于日常行走路线，例如从家到工作地的上下班路线上接受充电站的服务，忽略了需求的多样性。在现实生活中，住在充电设施附近的小区居民也会前往充电站接受充电服务。在传统设施选址问题中，如银行、便利店等设施，已有学者同时考虑两类需求，即产生于日常路线上的过路需求和产生于节点(社区)的固定需求。Hodgson等[15]在经典截流选址模型基础上，研究了截流选址和P-中位问题混合模型；杨珺等[16]研究基于设施服务半径的截流选址模型；李珍萍等[17]在自提点选址问题中考虑了用户的多种需求。关于充电设施的需求问题，Melaina[18]指出充电设施选址应遵循的标准与其他能源补充设施一样，既可以为行驶在网络路径上的用户流充电，也能为设施附近的用户充电；Wang等[19]同时考虑两类需求，提出集覆盖和截流选址的综合模型，目标是最小化充电设施建站成本和最大化覆盖节点用户，然而其用一系列不等式表示电动汽车在行驶中始终有电的假设，使模型因约束条件和决策变量较多而不易求解。

在当前城市土地资源紧张、充电设施建设成本高的大环境下，只有充分考虑两类需求，才能最大程度地利用充电设施来推进电动汽车的发展。基于此，本文同时考虑过路需求和节点需求，通过构建扩张网络，提出考虑服务半径的充电设施选址模型。该模型相比当前研究能够更准确地描述用户充电需求，更全面地考虑充电需求的多样性。相比Wang等[19]的模型，本文所提模型在约束条件和变量方面均有所减少，因此更容易求解。另外，Wang等[19]针对台湾部分城市的充电设施选址问题展开案例分析，并未提出模型的求解算法。本文根据模型的特点，通过松弛两组约束，设计拉格朗日松弛算法求解数学规划问题，并通过随机生成的数值算例验证了模型和求解的有效性，高效的求解算法使得本文模型能够应用于现实生活中规模较大、较复杂的交通网络。最后，利用25个节点的网络作为数值算例，研究了充电设施建站成本与节点需求覆盖量之间的权衡关系，分析了电动汽车的续航里程与充电设施服务半径对模型结果的影响。

1 模型的建立与分析

1.1 模型假设与问题描述

本文模型作如下假设：①电动汽车用户从起点出发行驶至目的地，行驶路径为最短路径；②电动汽车在起点的电量至少为续航里程R的50%；③电动汽车在终点的电量不低于续航里程R的50%；④节点需求量的服务半径为r，当节点与充电设施的距离小于r时，用户会去该站点充电，即用户被充电设施覆盖，否则不被覆盖。

假设①～③最初由Kuby等[20]提出，后被广泛应用到其他文献[6,21]，假设②和③保证电动汽车能够往返于同一条路径。

步骤2若电动汽车能够以50%的电量从源节点s出发到达节点i(i是路径q上的任意节点)，则连接s和i，即

步骤3若电动汽车能够以50%的电量从节点i(i是路径q上的任意节点)出发到达终节点t，则连接节点i和t，即

步骤4对于路径q上任意两个节点i和j，若电动汽车完全充电时能够从节点i到达节点j，则连接i和j，即

假设充电设施不仅为产生于交通网络路径的车流量提供服务，还为充电设施附近的用户提供充电服务。如图1所示，若在C点建立充电设施，则该设施不仅为行驶在路径q上的用户提供充电服务，C点附近的用户(用户离C点的距离小于服务半径r)也会前往C点寻求充电服务。本文研究的问题是：交通网络上电动汽车用户行驶路径和节点的固定需求量已知，如何建立充电设施，在满足过路充电需求的前提下使充电设施建立成本最小，同时尽可能多地为节点需求提供充电服务。

1.2 模型的建立

模型中用到的集合、参数和变量说明如下：

(1)集合

Q为路径的集合，q∈Q；

N为路径包含的节点集合，N=∪q∈QNq；

Qi为经过节点i的路径集合，i∈N。

(2)参数

ci为在节点i处建立充电设施的固定成本，i∈N；

pi为节点i处的固定充电需求量，i∈N；

r为充电设施的服务半径；

M为大常数。

(3)变量

令r表示节点需求量的服务半径[16]，则考虑服务半径的充电设施选址模型可表示为以下数学规划：

S-LP：

minWz1+(1-W)z2。

(1)

s.t.

(2)

(3)

(4)

(5)

yi∈{0,1},∀i∈N；

(6)

Hi∈{0,1},∀i∈N。

(7)

该模型扩展了单目标充电设施截流选址模型，更能充分有效地利用充电设施。图3所示为图1路径q的两种最优充电设施选址方案{B，D}和{B，C}，节点下方的数字表示每个节点的固定需求量(可视为附近的社区居民人数)。假设每个备选点的建站成本相同，若仅考虑充电设施建站成本，则两种方案无差别，然而在实际运营中，充电设施附近(服务半径内)的社区居民也会前往设施充电，即充电设施也为节点需求服务。充电设施{B，D}覆盖的节点需求为300，充电设施{B，C}覆盖的节点需求为1 100，显然选择{B，C}建立充电设施更优。可见，本文模型为相关决策部门提供了一个能够更加充分利用充电设施的决策方案。

考虑两种极端情形，当W=0时，问题S-LP表示最大化充电设施覆盖的节点需求，此时约束(4)中的Hi=1，即每个节点需求至少被一个充电设施覆盖，该模型退化为覆盖问题，会产生较高的充电设施建站成本；当W=1时，问题S-LP在满足交通网络过路需求的前提下最小化充电设施建站成本，该模型仅考虑过路需求完全覆盖下的最小成本，忽略了节点充电需求，退化为充电设施截流选址问题。显然，高建站成本会覆盖更多节点需求，目标函数中的权重W使得相关决策部门能够在建站成本和覆盖的节点需求之间进行权衡。

2 模型求解

2.1 问题的下界

本节设计拉格朗日松弛算法求解问题S-LP。分析模型，若去掉约束(3)和(4)，则问题化为扩张网络上的多OD对最短路径问题，而该问题存在多项式时间算法。引入拉格朗日乘子αi(αi>0,∀i∈N)和βi(βi>0,∀i∈N)松弛约束(3)和(4)，整理后得到如下拉格朗日问题：

s.t.

yi∈{0,1},∀i∈N；

Hi∈{0,1},∀i∈N。

可将问题S-LPR分成如下3个子问题：

s.t.

问题S-LPR1是多OD对最短路问题，可以用多项式时间算法求解。

S-LPR2:

ZR2(α,β)

s.t.

yi∈{0,1},∀i∈N。

S-LPR3:

ZR3(α,β)=

s.t.

Hi∈{0,1},∀i∈N。

2.2 问题的上界

2.3 拉格朗日乘子

第k次迭代，步长

tk=

式中：UB是问题S-LP的最小上界；LBk是第k次迭代拉格朗日问题S-LPR的目标函数值；μk∈[0,2]，本节将μk的初始值设为2，若连续两次迭代，问题S-LPR的最优值不减小，则将μk减半。

给定拉格朗日乘子αk和βk的初始值，每次迭代的拉格朗日乘子如下：

2.4 拉格朗日松弛算法的步骤

利用拉格朗日松弛算法求解问题S-LP的具体步骤如下：

步骤1求初始上界。令yi=1(∀i∈N)，求解问题S-LP，得到初始上界UB0，令UB=UB0。

步骤3通过求解3个子问题S-LPR1，S-LPR2，S-LPR3，得到拉格朗日松弛问题S-LPR的最优解。

步骤4若拉格朗日问题的解满足约束条件(3)和(4)，则为原问题的可行解，也为最优解，算法终止，否则转步骤5。

步骤5更新上下界。若LBk>LB，则更新LB。利用问题S-LPR的解求出原问题的上界UBk，若UBk

步骤7更新拉格朗日乘子，返回步骤3。

3 数值算例与分析

本章首先通过随机生成交通网络和节点需求，在8个交通网络上测试拉格朗日松弛算法求解问题S-LP的有效性；然后，利用25个节点的网络图作为数值算例来分析目标函数权重对最优解的影响，权衡电动汽车充电设施建站成本和节点需求覆盖量之间的关系。

3.1 算法的性能测试

本节按照上述构造网络的方法随机生成8个交通网络图。令t(i,j)表示边(i,j)上增加的节点，所增加的节点

式中：length(i,j)为边(i,j)的长度；l是一个输入参数。

假设电动汽车的续航里程R=300 km。由于建立充电设施的位置不同，建站成本也会不同，假设每个备选节点充电设施建站成本在区间[1 000,10 000]上随机生成。令l=100 km，节点的权重即节点充电需求在区间[500,5 000]上随机生成，与Hodgson[15]相同，OD对之间的流量(每条路径的过路需求)由重力模型求得，即

式中：wi，wj分别表示节点i和j的充电需求；dij表示从起点i到讫点j的最短距离。

表1 拉格朗日松弛算法的性能测试

续表1

3.2 数值结果与分析

电动汽车续航里程d=300，500，充电设施的服务半径r=10，20，目标权重值W=0，0.3，0.7，1时，问题S-LP的最优解如表2所示。由表2可知，d=300，r=10，当权重W=0时即覆盖问题，在满足过路充电需求的前提下，决策者将关注覆盖所有节点用户需求，而不考虑建站成本，其所建立的充电设施数为92，充电设施的节点占总节点的比例高达59.35%，节点需求覆盖量为158 365；当W=1时即充电设施建站成本最小问题，决策者只关注建站成本，不考虑节点用户需求，其所建立的充电设施数大幅度下降为11，节点建站比例仅为9.03%；当W从0增加到1(0→0.3→0.7→1)，即决策者对建站成本的重视程度增加时，其所建立的充电设施数大幅度减少(92→36→19→11)，节点需求覆盖量也相应减少，节点建站比例变化为59.35%→23.22%→12.25%→7.09%。这是由于随着权重W的增加，决策者更加重视建站成本，忽略节点需求覆盖量，导致充电设施数大幅度减少，节点需求覆盖量也急剧下降。

表2 充电设施数和节点需求覆盖量

续表2

固定权重W，即决策者对建站成本和节点需求覆盖量重视程度一定，当续航里程d增加时，充电设施数和节点需求覆盖量均减少；当充电设施服务半径r增加时，充电设施数减少，节点需求覆盖量增加。另外，当目标函数权重W=1时，决策者仅关注建站成本，能够为所有路径提供充电服务的最小设施数主要取决于续航里程d，例如当续航里程d和服务半径r的组合分别为(300，10)，(500，10)，(300，20)，(500，20)时，最小充电设施数分别为11，8，11，8;相反,当目标函数权重W=0时，决策者仅关注节点需求覆盖量，能够覆盖所有节点需求的设施数主要取决于充电设施的服务半径r，例如当续航里程d和服务半径r的组合分别为(300，10)，(500，10)，(300，20)，(500，20)时，最小充电设施数分别为92，92，85，85。

图5和图6所示分别为续航里程d=300和设施服务半径r=10时，不同权重下建立的充电设施数和节点需求覆盖量。由图5可知，随着权重W的增加，决策者更加重视建站成本，充电设施建站数减少。当权重较小时(W∈[0,0.1])，随着权重W的增加，充电设施建站数急剧减少；当权重较大时，随着权重W的增加，充电设施建站数减少较缓慢。当充电设施建站成本成为决策者的主要考量因素时，充电设施数会逐渐减少。观察图6可见，随着权重W的增加，节点需求覆盖量减少，这是因为随着权重

W的增加，决策者忽视节点需求，充电设施只满足过路需求即可，所以充电设施建站数减少，节点需求覆盖量降低。

充电设施数和节点需求覆盖量之间的权衡关系如图7所示。从图7可见，充电设施数较少时，决策者比较关注建站成本，节点需求覆盖量较少；当充电设施数较少时，曲线较陡峭，随着充电设施数的增加，曲线渐渐平缓。这表明，当充电设施较少时，决策者比较重视建站成本，可以通过少量增加充电设施建站数来大幅度提高节点需求覆盖量；当充电设施较多时，即使增加充电设施建站数，也很难再提高节点需求覆盖量。

综合以上分析，可以得到如下结论：

(1)最优选址方案因决策者对建站成本和节点需求重视程度的不同而不同。若决策者只以建站成本作为考量因素，而忽略节点需求，则充电设施数较少，相应的节点需求覆盖量较低。在满足过路需求的前提下，若决策者重视节点需求，要求所有节点需求均被覆盖，则充电设施数将大幅度增加，节点需求覆盖量显著提高。

(2)若决策者只关注充电设施建站成本，则最优方案取决于电动汽车的续航里程；若决策者只关注节点需求覆盖量，则在满足过路需求的前提下，最优方案取决于充电设施的服务半径。

(3)由充电设施数与节点需求覆盖量的权衡关系可知，在电动汽车推广初期，充电设施数量较少时，可以通过增加充电设施的方法来大幅提高节点需求覆盖量；而当电动汽车的保有量达到一定程度，充电设施数较多时，增加充电设施仅能小幅度提高节点需求量。

4 结束语

如何根据用户需求特点进行充电设施选址布局，从而破解电动汽车市场发展的困局，成为亟待研究和解决的关键问题。本文在现有研究基础上，充分考虑过路需求和节点需求两类需求，提出基于服务半径的充电设施选址模型，并设计拉格朗日松弛算法求解该模型。本文模型更加准确、全面地描述了用户充电需求，且模型规模较小，易于求解。同时，针对当前模型难以应用于现实复杂交通网络的问题，设计了拉格朗日松弛算法求解模型，该算法求解速度快、准确率高。通过随机生成的数值算例实验验证了模型和算法的有效性，结果表明充电设施建站成本与节点用户覆盖量存在权衡关系。随着决策者对建站成本重视程度的加大，设施数量减少，节点用户覆盖量降低。本文研究可以为政府部门和电动汽车充电服务商决策充电设施位置和数量提供科学依据。

考虑到电动汽车选址问题受到用户路径不确定性与需求多样性等诸多因素影响，本文后续研究可以从以下方面展开：①产生于路径的用户可能偏离原定的最短路径来寻求最大效用的充电模式，即用户路径偏离与充电偏好问题；②用户路径选择与充电设施的交互影响作用，即充电设施的最优位置选择会受用户路径的影响，用户路径选择也会受充电设施位置的影响。