随着金融危机、生态环境恶化与能源短缺等问题的加剧，电动汽车的研究成为汽车行业竞争热点，各国纷纷抢占电动汽车市场的制高点^[1]。电动汽车的普及能够有效减少环境污染和对化石燃料的依赖，然而目前电动汽车很难实现大规模推广，主要的阻碍有充电站数量有限、续航里程较短、购买成本较高等^[2]。一些研究发现电动汽车的续航里程对于消费者的购买欲望^[3]和满意度^[4]起到消极作用，尤其是对于长距离出行者。本文提出在充电站有限情况下的双目标选址模型，使有限的充电站尽可能满足更多需求。

当前的研究大多针对单目标选址问题，追求成本最小化，这里的成本可以是充电站可及成本^[6]、建设成本^[7]、绕行成本^[8]等；还有一些研究考虑电网结构、可用容量的最优^[9]以及交通便利性^[10]等因素。不同于大多数研究的单目标选址问题，本文中的选址模型包含两个目标函数：绕行成本的最小化和出行频率的最大化。因为一般情况下影响选址的因素可能不止一个，多目标选址相比于单目标问题更具有普遍性和实际意义。而双目标选址被看作是具有代表性的、特殊的多目标问题。

此外，大多数选址问题的计算方法采用启发式算法，启发式算法只能计算出帕累托解的近似解，而本文的参数法能够计算出帕累托精确解，从而使解的分布更加准确。

本文采用参数法将双目标问题转化为一系列单目标问题，然后利用分支定界法和考虑中继的标号法分别解决单目标选址问题和这个选址问题的路径选择子问题。以长江三角洲高速路网为例，根据不同预算限制和里程限制，对比分析9种不同方案下的帕累托解的分布。

1 问题描述与模型构建

双目标优化选址模型基于如下出行行为假设：在给定的交通网络中，交通出行需求是给定的，如果在出行者驾驶电动汽车出行时，至少有一条可行路径，那么出行者一定会出行(中途充电是被允许的)。

充电站选址的影响因素和约束条件较多，例如充电站容量限制、充电站排队等候时间、交通区位因素和电网容量等，考虑所有影响因素会使问题过于复杂，因此本文重点关注里程限制对出行行为的影响。绕行成本和出行频率是重要的考虑因素：由于目前充电站不足，电动汽车的剩余电量可能无法直接到达目的地，则出行者需要绕行去寻找其他充电设施，增加了出行成本(时间)；同时，充电站的分布情况也会直接影响出行活动能否实现，进而影响电动汽车的使用和购买。这两个方面构成了我们的目标函数。

值得注意的是，充电站不足也会导致即使在允许中途充电的情况下，电动汽车仍无法到达目的地，采用惩罚成本的概念来定量表示这种出行需求不能被电动汽车满足的情况。

在问题设定中，绕行成本的最小化可以用出行总成本的最小化来实现，因为绕行成本可以表示为总成本减去最短路成本，而最短路成本对于确定的起讫点对而言是常量。

模型构建中使用的集合表示为：T备选充电站地点集合；W为起讫点对集合，W={(r, s)}；N为节点集合，N={i}, i=1，2，…，n；A路段集合，A={(i, j)}；K_rs为起讫点对(r, s)之间的路径k的集合；V_k^rs为连接起讫点对(r, s)的路径k上的充电站对集合，V_k^rs={(p, q)}。

参数为：p_rs为起讫点对(r, s)的单位未满足需求惩罚成本；c_{i, j}为路段(i, j)的通行成本；d_ij为路段(i, j)的实际长度；q_rs为起讫点对(r, s)之间的出行需求；M为一个充分大的常数；Z为网络中允许设置充电站的最大数量；D为电动汽车充满电后的最大行驶距离；d_k^{rs, pq}为连接起讫点对(r, s)的路径k上的充电站对(p, q)的子路径对应的实际长度；δ_{ij, k}^rs为通路指标，如果路段(i, j)是连接起讫点对(r, s)的路径k的一部分时，δ_{ij, k}^rs=1；否则，δ_{ij, k}^rs=0；δ_{ij, k}^{rs, pq}为通路指标，如果路段(i, j)是连接起讫点对(r, s)的路径k上的充电站对(p, q)的子路径的一部分时，δ_{ij, k}^{rs, pq}=1；否则，δ_{ij, k}^{rs, pq}=0。

变量为：f_k^rs为通过连接起讫点对(r, s)的路径k的电动汽车交通流量；x_ij为通过路段(i, j)的交通流量；Z_t为选址决策变量，表明充电站在哪个备选站点上设置，如果充电站设置在备选站点t，则Z_t=1；否则，Z_t=0；y_k^rs连接起讫点对(r, s)的路径k的激活指标，如果y_k^rs=1，则f_k^rs≥0；如果y_k^rs=0，则f_k^rs=0；y_k^{rs, pq}为连接起讫点对(r, s)的路径k上的充电站对(p, q)的子路径激活指标，如果y_k^rs=0，则y_k^{rs, pq}=0；如果y_k^rs=1，则y_k^{rs, pq}=0或1。

根据上述关于集合、参数和变量的注解，双目标优化选址问题的数学模型可表示为

$ \min \left[ \begin{array}{l} \sum\nolimits_{\left( {i,j} \right)} {{c_{ij}}{x_{ij}}} \\ \sum\nolimits_{rs} {{p_{rs}}{q_{rs}}} \left( {1 - \sum\nolimits_k {y_k^{rs}} } \right) \end{array} \right] $

(1)

服从于：

$ \begin{array}{*{20}{c}} {\sum\nolimits_t {{Z_t} \le Z} }&{\forall t \in T} \end{array} $

(2)

$ \begin{array}{*{20}{c}} {{Z_t} \in \left\{ {0,1} \right\}}&{\forall t \in T} \end{array} $

(3)

$ \begin{array}{*{20}{c}} {\sum\nolimits_k {f_k^{rs}} \le {q_{rs}}}&{\forall \left( {r,s} \right) \in W} \end{array} $

(4)

$ \begin{array}{*{20}{c}} {f_k^{rs} \ge 0}&{\forall \left( {r,s} \right) \in W,k \in {K_{rs}}} \end{array} $

(5)

$ \begin{array}{*{20}{c}} {f_k^{rs} \in \arg \max \sum\nolimits_k {f_k^{rs}} }&{\forall \left( {r,s} \right) \in W} \end{array} $

(6)

$ \begin{array}{*{20}{c}} {f_k^{rs} \le My_k^{rs}}&{\forall \left( {r,s} \right) \in W,k \in {K_{rs}}} \end{array} $

(7)

$ \begin{array}{*{20}{c}} {\sum\nolimits_k {y_k^{rs}} \le 1}&{\forall \left( {r,s} \right) \in W,k \in {K_{rs}}} \end{array} $

(8)

$ \begin{array}{*{20}{c}} {y_k^{rs,pq} \le {Z_{t = p,q}}}\\ {\forall \left( {r,s} \right) \in W,k \in {K_{rs}},\left( {p,q} \right) \in V_k^{rs}} \end{array} $

(9)

$ \begin{array}{*{20}{c}} {y_k^{rs}\delta _{ij,k}^{rs} \le \sum\nolimits_{\left( {p,q} \right) \in V_k^{rs}} {y_k^{rs,pq}\delta _{ij,k}^{rs,pq}} }\\ {\forall \left( {r,s} \right) \in W,k \in {K_{rs}},\left( {i,j} \right) \in A} \end{array} $

(10)

$ \begin{array}{*{20}{c}} {y_k^{rs,pq}\left( {D - d_k^{rs,pq}} \right) \ge 0}\\ {\forall \left( {r,s} \right) \in W,k \in {K_{rs}},\left( {p,q} \right) \in V_k^{rs}} \end{array} $

(11)

$ y_k^{rs} \in \left\{ {0,1} \right\}\forall \left( {r,s} \right) \in W,k \in {K_{rs}} $

(12)

$ y_k^{rs,pq} \in \left\{ {0,1} \right\}\forall \left( {r,s} \right) \in W,k \in {K_{rs}},\left( {p,q} \right) \in V_k^{rs} $

(13)

其中

$ \begin{array}{*{20}{c}} {{x_{ij}} = \sum\nolimits_{\left( {r,s} \right) \in W} {\sum\nolimits_k {f_k^{rs}\delta _{ij,k}^{rs}} } }&{\forall \left( {i,j} \right) \in A} \end{array} $

(14)

$ d_k^{rs,pq} = \sum\nolimits_{\left( {i,j} \right)} {{d_{ij}}\delta _{ij,k}^{rs,pq}k} \in {K_{rs}},\left( {p,q} \right) \in V_k^{rs} $

(15)

式(1)中的第一个目标函数$ {\sum _{(i, j)}}{c_{ij}}{x_{ij}}$是最小化流量加权的出行成本，第二个目标函数${\sum _{rs}}{p_{rs}}{q_{rs}}(1 - {\sum _k}y_k^{rs}) $是最小化未出行需求的惩罚成本(等同于最大化需求)。约束(2)要求建设的充电站数量不超过给定的预算限制。约束(3)是整数性约束。约束(4)和(5)为流量守恒约束。式(6)说明了如果对于一个(r, s)存在可行路径，那么出行一定要被满足。约束(7)规定了f_k^rs和y_k^rs之间的数量关系，保证当y_k^rs=1，那么f_k^rs≥0；当y_k^rs=0，那么f_k^rs=0。在约束(8)中，规定对于任意一个起讫点对(r, s)，可行路径k的数量不能超过一个。约束(9)指出，如果在备选站点p、q上设置充电站，则该路径可能被激活。约束(10)将路径激活指标和子路径激活指标之间的关系具体化：对于路径k上的任意路段(i, j)，如果有一个或多于一个被激活的子路径，那么路径k就是被激活的；如果没有被激活的子路径，那么该路径k也不可能被激活。约束(11)保证如果充电站对(p, q)之间的实际距离小于充电汽车的续航里程，那么y_k^{rs, pq}可能为0，也可能为1；如果充电站对(p, q)之间的实际距离大于充电汽车的续航里程，那么y_k^{rs, pq}一定为0。约束(14)显示了路段交通流和路径交通流之间的关系，同时约束(15)则说明了路段长度和路径长度之间的关系。

2 双目标选址模型求解方法

最早将参数法应用于多目标线性规划问题。Xie等^[12]曾将参数法用于双目标网络规划问题。本文在解决参数法框架的子问题，即选址问题的过程中，采用分支定界法(branch and bound)。分支定界法通过不断“分枝”将解空间分解为更小、更容易处理的部分，再通过“剪枝”舍去不存在最优解的部分，从而提高算法效率。

综上，模型的求解算法总结如下：首先采用参数法，针对每一个可行的解空间构造单目标函数，再使用分支定界法解决选址问题并将最短路问题作为子问题，通过更新标签的方法计算出行成本和惩罚成本。关于子路径的相关定义参考文献[13]。具体算法过程如下。

2.1 参数法

参数法框架是一个不断迭代、“分而治之”的过程，在确定的解空间内搜索帕累托解集，当不再有新的帕累托解产生时，迭代结束。

给出双目标离散优化问题$ {\rm{mi}}{{\rm{n}}_x}\{ (f_n^1\left( \mathit{\boldsymbol{x}} \right), f_n^2\left( \mathit{\boldsymbol{x}} \right))|\mathit{\boldsymbol{x}} \in X\} $，其中(f_n¹, f_n²)是第n次迭代的目标函数向量，x和X是决策变量和决策变量区域，具体注释列表和迭代步骤如下所示：(f_a, f_b)为目标向量对，${\mathit{\boldsymbol{f}}_a} = (f_a^1, \mathit{\boldsymbol{f}}_a^2), {\mathit{\boldsymbol{f}}_b} = (f_b^1, f_b^2);\mathit{\boldsymbol{w}} $为目标系数集合，$ \mathit{\boldsymbol{w}} = \left( {\mathit{\boldsymbol{w}}_1^{\left( n \right)},w_2^{\left( n \right)}} \right);\mathit{\boldsymbol{w}}_1^{\left( n \right)}$是f_n¹在第n次迭代的系数；w₂⁽ⁿ⁾是f_n²在第n次迭代的系数。

1)(初始化)分别解决两个极值问题${\rm{mi}}{{\rm{n}}_x}\{ {f^1}\left( \mathit{\boldsymbol{x}} \right)|\mathit{\boldsymbol{x}} \in X\} $和${\rm{mi}}{{\rm{n}}_x}\{ {f^2}\left( \mathit{\boldsymbol{x}} \right)|\mathit{\boldsymbol{x}} \in \mathit{\boldsymbol{X}}\} $：解向量为X_a^*和X_b^*，对应目标函数向量为f_a^*和f_b^*，如果X_a^*=X_b^*，那么该双目标问题只有一个最优解且已经被找到；否则，将目标函数向量对(f_a^*, f_b^*)放入先进先出列表。设置第一次迭代的初始系数：$\mathit{\boldsymbol{w}}_1^{\left( 1 \right)} = 0.999, \mathit{\boldsymbol{w}}_2^{\left( 1 \right)} = 0.001, \mathit{\boldsymbol{w}}_1^{{{\left( 1 \right)}^\prime }} = 0.001{\rm{ }} $和$ \mathit{\boldsymbol{w}}_2^{{{\left( 1 \right)}^\prime }} = 0.999$。

2)(参数产生)从先进先出列表中选择第一个目标函数向量对(f_a, f_b)，其中f_a=(f_a¹, f_a²)，f_b=(f_b¹, f_b²)，产生新的参数集w=(w₁⁽ⁿ⁾, w₂⁽ⁿ⁾)并构造单目标函数，添加额外的约束条件保证解的非劣性。

3)(问题求解)寻求单目标函数f⁽ⁿ⁾=w₁⁽ⁿ⁾f_n¹+w₂⁽ⁿ⁾f_n²达到最小值时所对应解，如果存在可行解，则原问题有帕累托解，将得到的目标函数向量f^*与f_a和f_b结合构造两个新的目标函数向量对(f_a, f^*)和(f^*, f_b)，并把它们放入先进先出列表；如果不存在可行解，那么在(f_a, f_b)所构成的限制区域内，帕累托解不存在。

4)(终止条件)如果先进先出列表是空的，那么停止搜索，所有的帕累托解已经得到；否则，转入步骤1)。

2.2 双约束目标加权问题的构造

参数法的关键是合理的构造单目标函数。在每一次构造的过程中，使用先进先出列表中给定的目标向量(f_a, f_b)所产生的系数进行目标函数的线性组合，其中f_a=(f_a¹, f_a²)，f_b=(f_b¹, f_b²)。具体公式如下

$ {\min _\mathit{\boldsymbol{x}}}f = w_1^{\left( n \right)}f_n^1 + w_2^{\left( n \right)}f_n^2 $

(16)

服从于约束(2)~(15)

$ f_n^1 \le f_{\max }^1 - \varepsilon \;和\;f_n^2 \le f_{\max }^2 - \varepsilon $

(17)

其中

$ \left\{ \begin{array}{l} f_{\max }^1 = \max \left( {f_{n - 1}^1,f_n^1} \right),\\ f_{\max }^2 = \max \left( {f_{n - 1}^2,f_n^2} \right) \end{array} \right. $

(18)

$ \left\{ \begin{array}{l} w_1^{\left( {n + 1} \right)} = \frac{{f_n^2 - f_{n - 1}^2}}{{\left( {f_{n - 1}^1 - f_n^1} \right) + \left( {f_n^2 - f_{n - 1}^2} \right)}},\\ w_2^{\left( {n + 1} \right)} = \frac{{f_{n - 1}^1 - f_n^1}}{{\left( {f_{n - 1}^1 - f_n^1} \right) + \left( {f_n^2 - f_{n - 1}^2} \right)}} \end{array} \right. $

(19)

产生参数集w=(w₁⁽ⁿ⁾, w₂⁽ⁿ⁾)的方法称为正交法，由Cohon^[11]针对于双目标线性规划问题提出。由于本文研究的是离散问题，可行目标区域是非连续的，因此需要对每个目标函数引入额外约束：$ f_n^1 \le f_{{\rm{max}}}^1 - \varepsilon $和$f_n^2 \le f_{{\rm{max}}}^2 - \varepsilon $，从而保证解的非劣性。

2.3 解决双约束目标加权问题的分支定界法

对于小网络的选址计算可以直接进行排列组合，而对于大网络，需要采用分支定界法来提高算法效率。分支定界法被广泛应用于解决混合整数线性规划问题，利用分支定界法求解极小值的关键是找到问题的“下界”，从而通过“剪枝”有效减少运算时间。

2.4 需要中继的最短路问题

最短路径，是在里程限制情况下，出行成本最小的路径。在以往文献中，关于需要中继的最短路问题涉及不多，Laporte等^[14]提出了通过添加辅助矩阵进行标签更新的方法。Smith等^[15]认为标签法远比网络扩张法更有效，尤其是在解决最小出行成本的问题上。本文所采用的方法是来自Laporte等^[14]提出的基于出行成本最小的顺序进行标签更新的方法。该方法的特点在于：在动态规划过程中，同时包含成本标签和距离标签，通过对每个节点的候选标签进行对比来确定主导的标签。

3 长三角高速路网实例分析

采用长江三角洲高速路网(图 1)来验证模型和算法的有效性。该网络由30个节点和110条线段组成，每一条线段代表两条双向流量的路段，每条路段的出行成本(时间)和距离数据来自百度地图。根据人口统计和社会经济数据，确定了不同起讫点之间的需求量和15个备选充电站点：T={4, 5, 8, 12, 15, 16, 17, 18, 20, 21, 22, 24, 25, 29, 30}。同时选定了11个节点城市{1, 2, 7, 9, 14, 15, 17, 23, 25, 26, 30}既作为供给点，又作为需求点，对应110个起讫点对(O-D对)。惩罚成本的组成比较复杂，其设定需要考虑的因素有很多，除采用其他替代交通工具的出行成本外，还包括出行活动的经济效益和社会效益等，在本问题中，将其简化为驾驶燃油车出行的费用。设定百公里油耗为10 L，基本油价为6元/L。

设定了9个方案：对于方案a、b、c，预算限制为6，里程限制分别为90、120、150 km；对于方案d、e、f和方案g、h、i，预算限制分别为8、10，里程限制也分别是90、120、150 km。通过Matlab程序运算，这9个方案的帕累托解个数分别为：116、117、77、117、120、93、113、127和91。将预算限制相同的方案合并，图 2所示。

图 2(a)中的极值点1、极值点2和极值点3是在预算为0的情况下产生的，有趣的是，有些帕累托解虽然里程限制不同，却显示出相似的特性，例如不设置充电站的极值点3，和充电站点为{5, 18, 24, 25, 29, 30}的点4，两者的里程限制虽分别为150和120 km，在图中的位置却非常接近，可以互为替代。

值得注意的是，对于预算较小的情况，即Z为0或接近0，也就是当大部分路径是不可行时，里程限制的增加会极大的提高路径可行性，从而使出行成本增加；而当预算较大的时候，即大部分路径都是可行的，增加里程限制反而会减少绕行，从而减少出行成本。从图中容易看出，里程限制对于帕累托解的分布影响很大，尤其是当出行成本较大、惩罚成本较小时，因此提高电动汽车的续航里程非常必要。需要注意的是，在确定惩罚成本的过程中，没有考虑出行活动的经济效益和社会效益，因此会导致出行成本偏小，但这并不会影响帕累托解的总体分布形态。

参数法可以保证所有的帕累托解被找到，而分支定界法能够提高算法的有效性。决策者可以根据帕累托解的分布特征和分布形态，通过“斜率法”进一步选择最优解，具体方法如图 3所示。

图 3是方案(c)中部分帕累托解的分布情况，总体而言，这些点可以被看作斜率不同的3条直线:线段1、线段2和线段3。线段1近似由点A: (3.498 4×10⁷, 1.122 2×10⁷)和点B: (3.553 9×10⁷, 1.088 6×10⁷)确定，斜率为-0.606 1，意味着出行成本增加要比惩罚成本减少要多，因此这种趋势的变化是不合理的，即点A比点B合理。相反，对于近似由点B: (3.553 9×10⁷, 1.088 6×10⁷)和点C: (3.575 2×10⁷, 1.039 7×10⁷)确定的线段2来说，斜率为-2.295 7，即惩罚成本的减少大于出行成本的增加，这样的变化是合理的，即点C比点B合理。因此，点A和点C可以进一步被确定为最优解。

4 结论

1) 参数法能够保证帕累托解集的完整性和精确性，并优先搜索具有代表性的解；

2) 具有不同充电站点数和不同里程限制的方案可能具有相似的特性，应努力提高电动汽车的续航里程；

3) 当出行较多时，里程限制对于帕累托解的分布影响较大；

4) 斜率法能够在得到的帕累托解中进一步找到最优解，决策者可以根据目标函数不同的优先权，从选出的最优解中制定最终决策方案。

本研究存在着一些局限性，也为今后的研究提供了方向。对于参数法框架下单目标构造方法的选择，采用了双约束目标加权的构造方法，此外，还有单约束双曲线目标的构造方法、切比雪夫构造方法等，这些方法可能对于求解双目标帕累托选址问题更简单或更有效。另外一个值得改进的方面就是惩罚成本的确定方法，惩罚成本的确定方法复杂，除了油耗和汽油价格，还有许多经济学方面的因素值得考虑，例如出行的经济效益、社会效益、电池折旧费等，科学合理定义惩罚成本有利于使帕累托解的分布更加准确和更贴合实际。