在大型城市, 停车难问题和高昂的停车成本使得普通的上班族来讲拥有私家车不再具有吸引力. 汽车共享系统是私人车辆所有权的替代方案. 家庭或企业不必拥有一辆或多辆汽车, 而是共同使用一些车辆来满足需求, 这一类系统在20世纪70年代到80年代通过试点实施,近几年取得了相当大的发展.

汽车共享系统越来越多的采用环保型车辆, 不仅可以减少移动性对环境的负面影响, 也更加容易进入拥挤的城市地区. 其中在汽车共享系统中的环保型车辆首选是电动汽车. 现实中存在着一下几种类型的电动汽车, 主要有仅使用电池提供能量和电力的插入式电池电动车辆; 在行驶期间能够恢复能量的插电式混合动力电动车辆, 并且可以给电池充电, 但是仍然拥有内燃机^[1]. 在本文中, 汽车共享系统中使用的是仅使用电池提供能量和电力的插入式电池电动车辆.

根据用户是否应该将租借的车辆归还给他们的方式不同, 汽车的共享系统可分为灵活的“单向”和受到限制较多的“双向”两种类型. 根据停车位限制, “单向”的系统被分为“自由浮动的系统”和“非自由浮动的系统”. 前者是指用户可以在特定区域内的任意的停车点借还车辆; 后者定义为指定停车点来借还车辆. 在“自由浮动的系统”中, 不能采用预订的模式的. 而“非自由浮动的系统”模型为用户提供了预订能力和单程旅行的灵活性. 最近的一项研究表明采用预订模式可以提高汽车共享系统的服务质量^[2].

本文研究的问题是在单向共享电动车系统中车站的数量和位置以及每一个车站的初始化车辆数量, 目标为最大化利润, 这种方式考虑到可以服务的客户获得的收入、建设车站的成本以及购买电动汽车的成本. 本文将这个问题作为一个整数线性规划模型(Integer Linear Programming, ILP), 并利用这个模型, 决定所要服务的客户.

在第2节中, 将要回顾文献中的相关著作. 在第3节中, 定义了本文研究的问题之后, 提供了ILP公式的细节和模型所需的预处理程序. 最后, 进行了模拟仿真实验的结果, 对其进行分析.

1 相关研究

关于汽车共享系统的大多数现有研究都集中在战术和操作层面的决策问题上. 在这些研究中, 一方面研究的问题是汽车的重新安置, 以避免车站的汽车不平衡. 另一方面, 关于汽车共享系统中车站位置的研究.

文献[3]提出了一种用于单向汽车共享系统中站点最佳定位的混合整数规划模型. 文献[3]中通过考虑所有成本和收入因素来最大化公司的利润. 根据三种服务策略分析了该模型: (1)运营商可以自由选择客户的服务请求; (2)必须提供所有请求; (3)只有在起点时没有可用的汽车才能拒绝请求. 对来自葡萄牙里斯本市的实际数据的三种模型进行评估后发现, 满足所有客户要求可能会显着降低公司的利润. 这些模型基于这样的假设: 客户只能使用距离其原点和目的地最近的站点, 并且这种假设被认为是非常严格的. 文献[4]将这些模型扩展到更灵活的环境, 其中包括客户可以使用距离原点和目的地不是最近的车站. 对同一数据的案例研究表明, 引入这种用户灵活性和车辆库存信息增加了公司的利润.

除了上面提到的优化模型, 文献[5]提供了一个基于离散事件模拟的模型, 该模型评估了汽车共享系统中策略变化的影响, 例如创建新站, 增加车站容量, 合并或分离站. 作者通过对加拿大蒙特利尔汽车共享组织数据的几种策略评估了他们的模型.

文献[6]考虑了电动汽车共享系统中充电站位置的研究. 文献[6]提出了一种多目标混合整数线性规划模型, 该模型结合了单向共享电动汽车系统中的战略(站点位置)和战术(车辆重新定位)决策. 由于大量重定位变量而导致解决实际大小问题的模型难以处理, 因此使用了聚合需求结构. 该模型的第一个目标函数旨在最大化运营商的净利润, 而第二个目标最大化用户的净收益. 在文献[6]中, 假设充电周期明确地作为输入参数给出. 作者评估了他们的方法在法国尼斯的实际数据上的表现. 文献[7]提出了一种混合整数线性规划模型来解决单向共享电动汽车系统中充电站位置选择问题, 文献[7]中的目标函数为运营商的利润最大化, 其中每一个潜在站点的最大容量是已知的, 并没有考虑到充电站建造和电动汽车购买成本. 本文则需要确定每个潜在站点的最大容量, 并且有充电站建造和电动汽车购买成本有限制.

另一组相关研究是关于私人电动汽车充电站的位置, 文献[7–12]介绍了具体的方法. 文献[13,14]使用启发式算法解决了公共充电问题.

2 问题定义

该模型的动机是规划汽车共享系统中单向行驶, 并且时间不能自由浮动的, 其中共享使用的汽车用于为特定地理区域内的旅行提供服务. 在介绍问题制定之前, 我们从系统的需求和供给特征两个方面对系统进行了描述.

(1)车辆

整个系统中使用同一种类型的电动汽车, 任何类型的旅行请求都可以被任何可用的车辆所提供服务.

(2)车站

车辆在指定的车站出发和停靠. 车站有必要的基础设施来停车和为车辆充电; 每个车站提供特定数量的停车位, 这决定了车站的大小. 站的大小因站而异, 每个站的大小决定了它的容量.

(3)时间间隔

每个周期划分为不同的时间间隔(不一定一样长), 车辆出发的操作在时间间隔开始时开始, 车辆到达和充电完成操作在时间间隔结束时结束.

(4)运营操作

这个系统的运营涉及两项操作: 租赁; 充电.

① 该系统是在预定的基础上运行并允许单程租用车辆. 在预定时, 用户的出发地点、到达地点、出发时间、到达时间是可获得的. 在预定做出的时间段, 车辆在用户在出发地点可访问的车站获得车辆; 并在到达地点可访问的车站停放. 假定每一次租赁都是从一个时间间隔的开始时开始, 然后在一个时间间隔结束时结束.

② 本文所建立的模型采用了电动汽车. 为了对电动汽车充电时间进行建模, 假设车辆返回车站后, 必须在车站停留一段固定的时间, 这代表了车辆的充电时间.

(5)需求中心(潜在车站)

在该模型中, 需求中心表示可以由同一组(候选)站点服务的需求点. 为了说明中心是如何定义的, 图1描绘了需求的来源和目的地以及站点位置. 图2 示出了通过不同的起点和目的地位置可访问的站点. 请注意, 一个给定的起点/终点可以有多个对应的车站站点. 可以访问同一组车站的原点/目的点聚集在一起, 构成一个中心. 图3表示与这些中心相关联的两个中心(阴影区域)和旅程(需求). 将需求分组减少了变量的数量, 因为具有相同起源和目的地中心的旅行被组合在一起. 这种分组允许解决较大的问题实例.

(6)需求

需求有时间和空间两个维度. 需求表示拥有用户的起点和终点并具有出发时间和到达时间的订单的集合. 能够为一个订单提供服务需要满足以下两个条件:

① 在出发时间间隔开始时可从起始位置相应的车站获得车辆;

② 在到达时间时间间隔结束时到达位置相应的车站拥有停车位.

其中, “订单”不必分配给最邻近起点/终点的车站, 而是分配给可访问的车站.

(7)成本和收入

该模型的目标函数是最大化运营商的利润. 运营商的收入包括车辆租赁收入, 而成本包括车辆的维护, 运营以及车站开放后运营费用.

3 实验分析

在这一部分中, 首先定义了用于描述模型的集合和索引, 以及4.2节中的函数、变量和参数. 第4.2节给出混合整数规划模型, 并对其目标函数和约束条件进行了详细的描述.

3.1 输入

(1) 索引和集合:

① $p,j \in J$ : 潜在站点的索引;

② $h,k \in H$ : 需求订单索引.

(2) 参数定义:

① $V = \{ 1,\cdots,n\} $ : 为节点的集合;

② $J = \{ 1,\cdots,m\} $ : 潜在车站的集合, 其中 $J \in V$ ;

③ ${f_j}$ : 开放车站 $j$ 的成本, 它是关于充电站车位数量 ${C_j}$ 的线性函数;

④ ${F_j}$ : 建造车站 $j$ 的固定成本;

⑤ $g$ : 电动汽车运行成本;

⑥ $G$ : 电动汽车购买成本;

⑦ $T = \{ 0,\cdots,\tau \} $ : 时间节点;

⑧ $k = \{ {O_k},{D_k},{T_k},{T_k} + {d_k},{P_k},{\delta _{ij}}\} $ : ${O_k}$ 为请求 $k$ 的起点; c为请求 $k$ 的终点, ${T_k}$ 为请求 $k$ 的起始时间, ${T_k} + {d_k}$ 为请求 $k$ 的终止时间, ${P_k}$ 为请求 $k$ 的利润; ${\delta _{ij}}$ 为请求 $k$ 的电量.

(3) 辅助变量:

设计了一个预处理程序对辅助变量进行计算, 使用一个很小的例子对程序设计进行说明. 在这个例子中, 考虑了潜在站点的位置以及T时间内的需求K(如图1所示), 其中 ${i_1}$ 、 ${i_2}$ 、 ${i_3}$ 、 ${i_4}$ 为已建好的车站的位置, ${k_1}$ 、 ${k_2}$ 、 ${k_3}$ 为请求(包含了起始点O_k、终止点D_k、开始时间T_k、收入p_k), 模型中一个请求订单的完成有三部分组成(如图2所示), 连接任何起始点和起始站称为接入段(如O_k到 $i$ ); 连接任何终止点和终点站称为出口段(如D_k到 $j$ ); 连接始发站和终点站称为出租段(如 $i$ 到 $j$ ). 预处理程序主要将请求和车站进行连接, 形成接入段和出口段. 对于一个请求有可能被接入多个接入段和出口段, 形成集合 ${H_k}\left( {k \in K} \right)$ , 如果出租段满足电量和和接入段和出口段步行阈值满足要求, 则该请求 $h \in H = {U_{k \in K}}{H_k}$ 是可行的. 对于一个请求形成的结果(如图3所示). 由预处理程序进行实现.

预处理程序的伪代码, 伪代码如下:

算法1. 预处理程序

1) Π←Φ

2) for k←1 to K

3) H_k←Φ

4) for i←1 to m

d_Oki≤β

6) for j←1 to m

7) if d_Dki≤β

8) b[h][T_k]=1

9) u[j][T_k+d_k]=1

10) λ[h][j][T_k+d_k+d_k/ρ]=1

11) P_h={i, j, T_k+d_k}

12) H_k=H_k∪P_h

13) H=H∪Hk

14) return b, u, λ, H

① $u_{hj}^t = 1$ : 请求 $h$ 所使用的车辆在 $t$ 时刻已经在车站 $j$ 充电, 否则为0;

② $b_{hj}^t$ =1: 请求 $h$ 所要使用的车辆在 $t$ 时刻从车站 $j$ 出发, 否则为0;

③ $\lambda _{hj}^t$ =1: 请求 $h$ 所要使用的车辆在 $t$ 时刻已经在车站 $j$ 充电完成, 否则为0;

(4) 决策变量:

① ${u_h} = 1$ : 请求 $h$ 被服务;

② $L_j^t$ : 车站 $j$ 在 $t$ 时刻拥有的电动汽车的数量;

③ $L_j^0$ : 车站 $j$ 在0时刻拥有的电动汽车的数量;

④ ${C_j}$ : 站点 $j$ 的能力;

⑤ ${y_j}$ : 车站 $j$ 是否打开.

3.2 模型建立

$Max(z) = \sum\limits_{h \in H} {{P_h}{u_h}} - \sum\limits_{p \in P} {{f_p}} {C_p}{y_p} - g\sum\limits_{p \in P} {L_p^0} $

(1)

s.t.

$\sum\limits_{p \in P} {(\alpha + \beta {C_p}){y_p} + G\sum\limits_{p \in P} {L_p^0 \leqslant W} } $

(2)

$\sum\limits_{h \in H} {{u_h} \leqslant 1} $

(3)

${u_h} \leqslant {y_p},\begin{array}{*{20}{c}} {}&{\forall h \in H,p \in {P_h}} \end{array}$

(4)

$\sum\limits_{h \in H} {b_{hp}^t{u_h} \leqslant L_p^t}, \begin{array}{*{20}{c}} {}&{\forall p \in P,t \in T} \end{array}$

(5)

$L_p^t + \sum\limits_h {(u_{hp}^t - b_{hp}^t){u_h} \leqslant {C_p}{y_p},\begin{array}{*{20}{c}} {}&{\forall p \in P,t \in T} \end{array}} $

(6)

$L_p^t = L_p^{(t - 1)} + \sum\limits_{h \in H} {(\lambda _{hp}^t - b_{hp}^{(t - 1)}){u_h},\begin{array}{*{20}{c}} {}&{\forall p \in P,t \geqslant 1} \end{array}} $

(7)

$0 \leqslant L_p^t \leqslant {C_p}{y_p},\begin{array}{*{20}{c}} {}&{\forall p \in P,t \geqslant 1} \end{array}$

(8)

$L_p^0,{C_p} \in {{\rm Z}^ + }$

(9)

${u_h} \in \{ 0,1\}, \begin{array}{*{20}{c}} {}&{\forall h \in H} \end{array}$

(10)

${y_p} \in \{ 0,1\}, \begin{array}{*{20}{c}} {}&{\forall p \in P} \end{array}$

(11)

这是基于路径建立的模型(Path based Formulation, PF), 目标函数(1)为最大化利润, 第一部分所服务请求的总收入, 第二部分为车站建设后的运营成本, 第三部分为车辆的运营成本; 约束条件(2)是车站的建设费用和车辆的购买费用必须在预算范围内; 约束条件(3)是确保每一个请求接入一个接入段和出口段; 约束条件(4)确保一个请求若被服务则要求请求的起点和终点的车站都要打开; 约束条件(5)在t时刻每个车站的需求的车辆数量不能超过其能够提供的车辆数量; 约束条件(6)为在任意时刻j车站上的车辆数量不能超过车站的充电站的能力值; 约束条件(7)为在t时刻j车站上的车辆数量等于上一时刻该车站车辆数量加上充电完成的车辆数量减去出站的车辆数量; 约束条件(8)为车辆最大数量的限制; 约束条件(9)为初始车辆数量为正整数; 约束条件(10)为请求是否被满足; 约束条件(11)为车站是否进行打开.

4 仿真实验

这一部分通过创建一组实例测试了模型, 其中将街道网络建模为网格图, 其参数在一下部分中详细描述.

网格实例: 利用一定的规则产生随机矩阵, 进行模拟. 其中街道网络 $G = (V,A)$ 由尺寸30×30的网格图表示, 其中相邻节点的最大距离为5, 潜在站点的服务半径为 ${\rm{\{ 3}},{\rm{6}},{\rm{10\} }}$ . 每个潜在充电站点 $p \in J$ 的容量 ${C_p}$ 是未知的, 而车站的建造成本 ${F_p}$ 被设置为 $\alpha + \beta {C_p}$ , 其中 $\alpha = 100$ 和 $\beta = 10$ , 车辆的购买成本为 $G = 50$ , 车站的运营成本为 ${f_p} = (0.2\alpha + 0.05\beta {C_p}){y_p}$ , 车辆的运营成本为 $g = 0.01G$ . 潜在充电站的数量 $J{\rm{ = 50}}$ , 请求的数量 $K \in \{ 100{\rm{0}},{\rm{3}}00{\rm{0}},{\rm{5}}000\} $ , 时间的集合 $T\max {\rm{ = 24}}$ . 每个行程 $k \in K$ 的参数被选择如下: 原点 ${O_k}$ 和目的地 ${D_k}$ 被随机选择, 开始时间 ${T_k}$ 从随机选择, 结束时间 ${T_k} + {d_k}$ 从 $\{ {T_k},\cdots,{T_{\max }}\} $ 里面选择, 利润为 ${p_k} = 2{d_k}$ , 充电站的充电率为 $\rho = 10/3$ , 也就是说一个请求运行完毕后, 需要 $0.3{d_k}$ 的时间进行再次充电.

在Intel Core i3-6300处理器上使用IBM ILOG CPLEX 12.8进行了实验, 该处理器CPU为3.80 GHz, 内存为8 GB. 为了考虑到不同资金约束下模型的可行性, 在仿真实验中, 使用了资金约束在 $factor\_\cos t = $ $\{ {\rm{2500}},{\rm{5000}},{\rm{7500}}\} $ 的选择.

在表1中, 总结了每个解决问题实例的预处理结果. 在该表中, 列 $|K|$ 给出了从模拟数据中获取的请求数量, $|J|$ 为潜在站点的数量, $|\mathop K\limits^\_ |$ 为可能被服务请求的数量, $|H|$ 为预处理期间可能服务的潜在的路径数量, $p\_t$ 显示预处理期间可能服务的潜在的路径数量(以秒为单位).

在表2、3、4中详细测试了模型PF opt、RPF opt(使用 $0 \leqslant {u_h} \leqslant 1,\forall h \in H$ 替代 ${u_h} \in \{ 0,1\} $ )和LP(完全放开整数约束)分别从, 其中 $LP\_GAP$ 和 $LP\_GAP$ 的值分别使用公式(100*(LP opt – PF opt)/ PF opt)和(100*(RPF opt – PF opt)/ PF opt),被服务的请求数量 $|{K_a}|$ 、建设的车站 $|{J_a}|$ .

表2、3、4中看到, RPF和PF在每个实例中的值都是一致的; RPF中的解 在某些情况下不是整数. 随着充电站服务半径的增加, 能够服务的请求和利润都获得了增加. 但是求解时间和预处理过程花费时间也增加了.

当资金比较缺乏时, 该模型更倾向于建设更多的充电点为更多的客户提供服务; 资金由5000变为10 000时更加明显. 从以上求解结果可以看到, 每种求解结果PF和LP之间的Gap小于2%. 除了表2中的PF和LP之间的Gap比较大; 说明给模型能够得到一个比较好的求解结果. 当资金足够充足时, 该模型能够服务到充电站覆盖范围内的所有请求.

表5、6、7中的求解时间, 在半小时内解决了每个实例, 除了表6中资金约束需求量为5000, 服务半径为10的实例. 此外, 解决LP所需时间通常小于PF的求解时间, RPF的求解时间大于PF的求解时间.

5 结论和展望

将电动汽车引入共享汽车的系统, 为这些系统的运营带来了新的挑战. 在本文中, 我们介绍了资金约束下单向电动汽车共享系统中充电站的潜在站点的选择和车辆数量的配置的问题.

该整数规划模型可以很容易的将共享模式进行扩展, 应用到大规模. 通过模拟仿真实验表明, 我们的模型能够在合理时间内解决规模相当大的问题, 下一步主要进行潜在站点的选择方法的研究和启发式算法求解问题的创新.