电动汽车共享站点间车辆人工调度策略

王 宁， 张文剑， 刘 向， 左 静

(1. 同济大学 汽车学院，上 海 200092； 2. 同济大学 交通运输工程学院， 上海 200092)

城市道路资源和停车资源紧张、环境污染等问题使人们不得不关注机动车的使用.电动汽车共享是一种新兴交通模式，发展前景巨大，通过多人共享的使用方式能有效提高车辆使用率并有望改变人们的出行观念从而减少私家车的保有量，此外，电动汽车在节能减排和环保方面相对燃油车有较大的优势.但是，电动汽车共享作为一种新兴用车模型进入国内，尚处于用户推广阶段，加之用户用车需求的潮汐性和不均衡性导致站点间车辆失衡从而无法满足用车需求、降低了用户体验，这是电动汽车共享运营公司亟待解决的问题，也是电动汽车共享能否大规模推广的关键因素.

目前，电动汽车共享站点车辆、车位不平衡的主要原因是用户用车时间不确定且存在早晚高峰.部分站点车辆闲置，占用站点停车位导致用户无法还车；部分站点车辆不足导致用户无车可用.如何平衡供需，增加车辆的利用率，使得运营公司的收益最大化成为当前研究的热点.

目前国内针对电动汽车共享站点间的调度研究相对较少，主要是效果分析，可行性等宏观研究.国外汽车共享出现的时间较早，对于汽车共享车辆调度问题的主要研究如下： Dror Moshe[1]将拖车引入单程电动汽车共享调度模型中，将拉格朗日松弛方法应用到混合整数线性规划模型，计算单程电动汽车共享的车辆调度最优路径.Hafez Nevine[2]在Dror Moshe研究基础上，采用3种启发式算法计算调度耗时最少方案.LI Xiaopeng和MA Jiaqi[3]等根据电动汽车共享特点，基于连续逼近模型，优化了电动汽车共享调度系统，包括站点分布，站点车辆充电限制，减少综合系统成本(包括站点建设投资、车辆维修、交通运输和车辆平衡).WANG Hongman和LI Zhaohan[4]以葡萄牙里斯本市政府的电动汽车共享为研究对象，建立基于汽车共享运营公司利润最大的混合整数规划模型，分析比较3种不同的出行方式对公司收益的影响.Febbraro Angela Di[5]研究考虑了用户和工作人员对车辆的重新定位，用离散系统的复杂动态，模拟不同的方案，以减少所需的工作人员数量，并减少共享的车辆数量，以满足系统需求目标.Worley Owen[6]等研究电动汽车共享充电站站点布置和电动车辆调运的行车路径，构造以最少站点建设成本和调度成本的线性规划模型.

从文献来看，大多数研究都基于已知调度需求或假设的用车需求条件下求解和优化调度路径，较少对实际用车需求导致站点车辆不平衡进而产生的调度需求进行研究，缺乏完整的车辆人工调度策略.因此，本文根据电动汽车共享的特点设计电动汽车共享站点间的完整调度策略.首先，建立基于用户需求全满足的调度成本最低调度需求模型，采用遗传算法求解模型，针对模型特点提出染色体编码、交叉、变异等方面的具体设计思路，通过该模型求出调度需求.在此基础之上，提出在站点间采用调度员驾驶电动自行车通行的方式进行车辆调度，并建立调度员路径优化混合整数规划模型，采用分支定界法求解调度路径模型，生成基于收益最大化的调度路径方案.最后，以“EVCARD”位于上海市嘉定区5个站点的实际订单作为输入，进行人工调度策略优化分析，验证该模型的有效性.

1 研究模型和算法

国内电动汽车共享公司从小规模开始摸索试验并积累经验，在站点少、规模小的初期，随着用户数量的逐步增加，必然会出现站点间车数失衡的现象，这种情况会影响用户的预约成功率，从而损害用户体验，这对一种新兴交通模式的推广是极为不利的.因此，本文基于电动汽车共享站点间车辆失衡情况构建一套完整的调度方法，在有限运营车辆的前提下，如何通过站点间调度来最大满足用户需求，建立调度需求模型，求得最优的调度方案.再根据调度方案，建立调度路径优化模型，生成优化路径，以达到减少调度成本的目的.

1.1 电动汽车共享调度需求模型

对于电动汽车共享运营公司而言，满足用户需求前提下，运营成本也是公司需要考虑的重要因素.因此，调度需求模型是在已知周期内订单前提下，满足全部用车需求情况下指定的调度成本最低的调度方案.

1.1.1问题约定和假设

在建立模型前，对问题进行约定和假设：

(1) 车辆维度：所有电动汽车均为同一型号，一辆车在任何时刻只能服务一个任务需求；车辆在站点时，默认与充电桩连接充电；车辆任何时刻续航里程已知，并且充电时单位时间增加续航相同，不受外部因素如温度、湿度的影响；车辆循环使用，即在完成一个任务之后，如果续航满足要求，可以继续完成下一个任务.

(2) 站点维度：站点每个停车位均配备相同属性的充电桩.

(3) 服务周期：在一个周期内，用户的用车需求是随机的，不能确定用户用车需求时间，因此，为了简化模型，将服务时间段划分成若干周期.比如将1 d的24 h划分成24个时段，每个时段1h.将用户的取还车时刻都近似看作该时段开始时刻，比如用户12:10分取车，则近似看作12:00取车.

1.1.2模型建立

1.1.2.1 目标函数

目标函数为最大收益函数，可转换为最小调度需求的成本函数，即

式中：t表示服务周期，将一个运营周期等为M段，每段的开始为时间结点，时间结点t={1，2，3，4，…，M}；n表示网点个数；cij表示从i调运至j单位里程调运成本，不同站点之间道路交通状况不同，调运过程中单位距离调运成本相同；dij表示站点i到站点j距离；xtij表示站点空移车数，，∀i≠j,xtij为非负整数变量.

1.1.2.2 约束条件

(1) 在任何时刻车辆续驶里程均大于零：

lvk(t)≥0

式中:lvk(t)表示t时刻车辆k的续航里程.t时刻，车辆有两种状态：lvk0(t)停在站点充电；lvkij(t)从站点i行驶至站点j(包括用户用车和空车调配).

(2) 整个运营系统中，各时段各站点车辆总数守恒，即

∀i≠jj∈1,…,n

式中:Ati={ati1，ati2，ati3，…,atij，…,atin}，atij表示有载客需求从站点i到站点j并且在t时段起运的任务数；sit表示站点i在t时刻车辆集合,sit={v1,v2,…,vk}，且初始时刻站点i所停车辆已知.

(3) 在本系统中，车辆最大续航里程大于任意两站点之间的距离，即

L>dij∀i≠ji,j∈1,…,n

式中:L表示车辆最高续航里程.

(4) 各时段各站点车辆数目小于该站点停车位容量pi为

Card(sit)

式中：Card(sit)表示在t时刻停在站点i车辆数目.

(5) 车辆在站点之间通行的时间为

∀i≠ji,j∈1,…,n

(6) 车辆从站点i到达站点j时，保证站点j有足够的可用停车位ptj，即

∀i≠ji,j∈1,…,n

(7) 车辆在行驶时，车辆续航里程的表达式为

∀i≠ji,j∈1,…,n

lvk0(t)=lvk0(t-1)+e×Δt, 0≤lvk0(t)≤lmax

对于本模型而言，车辆的用车决策是无法约束的,为简化计算，做如下假设：用户用车时优先使用满电车辆，车辆被使用后，若站点车数目大于Δk，则车辆充电至满电后方可使用；若站点车辆数小于Δk，则需充电至车辆续航里程能够覆盖任意站点间距离且有一定余量后方可使用，保证站点有一定车辆，避免站点出现无车的情况.例如，当初始时刻，车辆k从站点1到站点2后，车辆k续航减少d12，站点2多一辆续航为L-d12的车辆，此时站点2满电车辆足够，则车辆k充电至满电后方可再次使用.若站点2无足够满电车辆，则充电至续航为L-Δl方可使用，并且优先使用满电车辆.该假设能够保证用户所驾驶车辆续航足够，减缓驾驶过程中驾驶员的续航焦虑，并且符合用户使用习惯.

因此，补充约束条件如下：

(1) 系统中车辆续航大于可用续航L-Δl方可成为可使用车辆，且可用续航需大于系统中任意两站点距离，即

lvk(t)≥L-Δl

L-Δl≥dij∀i≠ji,j∈1,…,n

(2) 车辆被使用后，再次成为可用车辆所需时间如下：

根据电动汽车共享用车模式以及车辆调配特点可知，在服务周期内各时段的车辆调配相互影响，调配方案需要从全局考虑，确定车辆调配方式，并且电动汽车续航有限，以及充电时间等因素，所以该模型是一个前后关联的多阶段决策问题.通过该模型求出最优化的调度方案，给出成本最低的调度需求.

1.2 遗传算法设计与实现

对于该车辆调度问题，求解复杂程度较高，求解存在不确定性，并且随着车辆规模的增加，求解难度程几何级增长，通常这类问题被认为是NP-Hard难解问题，而针对此类问题，目前尚无明确的求解算法.根据电动汽车调度问题的特征和对算法计算速度的高要求，本文采用遗传算法求解该问题.

遗传算法(Genetic Algorithm，GA)是起源于生物进化理论.最早由美国密西根大学的Holland教授的学生于1967年博士论文中提出，基本思想是模拟达尔文的遗传选择和自然界优胜劣汰的生存法则，在此基础上构建计算模型，是一种迭代搜索算法.遗传算法的搜索过程是基于群体的，GA搜索开始时，会首先产生一个随机群体，称为“种群(population)”.并且，遗传算法求解过程不依赖梯度信息，通过模拟自然界的进化过程来搜索最优解，是一种高效、并行、全局的搜索方法.遗传算法的运算过程如图1所示.

图1 遗传算法流程

1.2.1染色体编码与解码

根据车辆调度特点，本文中染色体编码包括被优化参数.染色体的基因序列g=(V,VC，D,DT,DN,DB,DE)，基因由7部分构成，其中，V表示车辆的平均行驶速度；VC表示车辆平均充电速度；D表示站点距离；DT表示空车调配启动时刻；DN表示空车调配启动数量；DB表示空车调配起始站点；DE表示空车调配的目的站点.

1.2.2初始化种群

在满足编码的前提下，随机产生n个个体，组成初始种群，记为

G={g0,g1,…,gn}

1.2.3约束处理与适度函数

常见约束处理方法有3种：① 直接处理约束条件，在编码过程中加入约束条件；② 计算过程中通过约束条件进行校验；③ 通过惩罚函数处理约束.根据模型特点，本文采用直接处理约束的方法，以目标函数作为适度函数.

1.2.4遗传操作

(1) 选择

(2) 交叉

采用启发式的交叉算子.设置交叉概率pc,在父代种群中随机产生两个个体，然后在区间(0,1)中生成随机数p.若p>pc，父代染色体不进行交叉，反之，染色体交叉.在交叉过程中，随机确定一个交叉点k，(1≤k≤n)，则在片段k之后，父代染色体进行交叉，k之前染色体保持不变.该交叉方法指只改变了染色体n-k的部分，保留了k片段，既能继承父代的优良基因，也体现了种群进化的思想.

(3) 变异

采用的是单片段变异方法.设种群的变异概率是pm，然后在区间(0,1)中生成随机数p′，若p′>pm，父代染色体不进行变异，不会产生新个体，反之，染色体变异.产生一个随机整数f(1≤f≤n)，表示染色体的第f个片段进行变异.将染色体的第f个片段重新进行编码，通过替换原来染色体片段而产生新染色体.

1.2.5终止准则

遗传算法计算前必须设计终止算法准则，遗传算法是一种随机并行搜索算法，需要设计终止准则来终止循环，停止迭代，常见的终止算法有3种：① 达到预先设定目标；② 种群中最优个体在迭代中没有改进；③ 达到预先设定的进化代数.预先设定进化代数能够很好地控制算法的求解精度和运行时间.综合考虑，本文采用预先设定进化点数，循环达到最大代数即停止迭代.

1.3 电动汽车共享调度优化模型

根据电汽车共享的特点，提出区域调度的模式，调度员采用折叠电动自行车在站点之间通行，在调度空车过程中将折叠电动自行车放置在后备箱中.建立以运营公司收益最大为目标函数的混合整数规划模型，优化模型，并采用分支定界法求解模型.

1.3.1问题约定和假设

(1) 调度员任何时刻只能服务一个调度需求任务需求.

(2) 调度员在驾驶电动汽车停车到站点后，取折叠电动自行车的时间忽略不计.

(3) 模型不考虑车辆和折叠电动自行车发生故障等意外情况.

1.3.2模型建立

1.3.2.1 目标函数

目标函数为运营公司最大收益函数，有

式中：i∈P表示某站点i在某时间需要调离电动汽车至别的站点；j∈D表示某站点j在某时间需要调配电动汽车到该站点；s为调度员编号，S表示调度人员数量；Rer表示每个调度任务的收益；xijs=1表示调度员s从取车点i取车前往送车点j，否则xijs=0；O表示调度中心；C表示每班每个调度人员的工时费.

1.3.2.2 约束条件

(1) 调度员s从集合点出发，一个调度员只能有一个调度路径，即

∀s=1,…,S

(2) 每个调度任务只能执行一次，即

∀i∈P∪D

(3) 站点的访问时间是由其上一站点的访问时间加上调度时间的总和，即

tis+cijxijs≤tjs+W(1-xijs) ∀i∈P,

∀j∈D, ∀s=1,…,S

式中：W表示每班调度人员的工作时长.

(4) 调度员取送车时间约束为

tis≥τi∀i∈P, ∀s=1,…,S

tjs≥τj∀j∈D, ∀s=1,…,S

式中：tis为连续时间变量；τi表示取车任务站点i的服务时间；τj表示送车任务点j的服务时间.

(5) 电动汽车在行驶过程中，行驶距离与所耗电量呈线性关系：

dijxijs≤L(ρi+e(tis-τi))

∀i∈P, ∀j∈D, ∀s=1,…,S

ρi+e(tis-τi)≤1

式中：ρr表示调度任务r所需电量；e表示电动汽车充电时单位时间增加的电量.

(6) 调度员在调度过程中电动汽车电量满足续航要求，有

ρj-e(tjs-τj)-(ρj+1)(1-xijs)

∀i∈P, ∀j∈D, ∀s=1,…,S

1.4 调度路径模型优化和求解

1.4.1模型优化

该模型是一个混合整数线性规划模型，根据调度需求可以求解调度人员调度路径.但是，在该模型中每个调度员的路线可以与其他调度员的路线交换，因此，该混合整数线性规划模型在可行域中包含多个最优解，对应不同xijs和tis的值，不易求解，并且CPU会耗费更多的时间来求最优解.为了防止出现这种情况，对目标函数增加约束条件：

(1) 指定路线分配给调度人员，不允许调度员之间交换路线，则

∀s′,s″∈1,…,S;s′

(2) 显示最大满足需求的上限，则

1.4.2分支定界法求解模型

通过分析，关于调度人员的调度路径优化问题是一个混合整数规划模型，通常采用分支定界法(Branch and Bound)求解该模型.分支定界法最早由Dakin于1964年提出，经过50多年的发展，目前分支定界法多被用于求解整数规划和混合整数规划问题.

分支定界法的核心思想是将求解问题分解成若干子问题，再将子问题分解，直到无法对子问题进行分解，分解子问题的过程称为分支.分支的过程是估算目标值的界限，这个过程称为定界，定界可以预测解的趋势，判定分支的有效性和求出不能判定的分支.将超出已知可行解集目标值的子问题删除，这个过程称为剪支，剪支可提高计算效率，加速收敛速度.分支定界法的步骤包含分支、定界、再到剪支，将该过程循环进行，就是分支定界法的基本步骤.

分支定界法的计算前提是以深度优先为目标，估算目标函数在分支结点的上、下界.再将该估算的解与已求得的最优解进行比较，删除超过最优解的决策，从而提高最优解的求解速度.对于分支定界法而言，决策变量的先后顺序和对目标函数的估值精度决定了计算效率和精度.

分支定界法能够在计算过程中保证精度的前提下加快计算速度，减少计算量，通过剪支舍去没有希望的解从而求得问题的最优解，方便计算求解.

2 案例应用与分析

2.1 案例概况

采用“EVCARD”位于上海市嘉定区的5个站点的实际运营数据作为案例进行研究分析，以实际订单作为输入，进行人工调度策略优化分析，同时对比采用人工调度方案和扩大车辆、车位规模的成本投入.表1为选取的5个站点之间的距离.

表1 各共享站点间距离

由于用户出行的目的各不相同，各站点间的距离不能直接作为实际行驶距离.根据这5个站点在一个月内的运营数据进行筛选出的3 289条有效运营数据计算出各站点间的平均行驶时间，再通过高德地图统计1 d内站点所在区域道路平均行驶速度为30 km·h-1，则可换算出各站点间的实际行驶距离，见表2.站点初始时刻车辆和车位数如表3所示.

通过上一年同期的运营数据可知，5个站点平均51单·d-1，平均每辆车1.5单·d-1，通过增加车辆和车位数， 5个站点订单数增加至平均104单·d-1，平均每辆车2.1单·d-1，虽然订单数量增加一倍，但车辆利用率显然没有明显的提高.

表2 各共享站点间实际行驶距离

表3 初始时刻车辆、车位数量

2.2 调度需求模型实例模拟

取车辆最高续航里程L=120 km；车辆充电速度e=18 km·h-1；站点之间单位里程调度成本cij=1元·km-1；用户用车时，每公里收益wij=1元·km-1；取L-Δl=30 km；站点车辆数目限制Δk=2.

将30 min划分为一个周期，1 d共计48个周期，根据这5个站点的运营数据，订单主要集中在7:00 am～10:00 pm之间，占总订单数的95.9%，为简化计算，忽略10:00 pm～7:00 am之间的订单.因此，1 d共计30个周期，M=30.

根据数据规模，取群体个数为20，最大遗传代数100，设置不同的交叉概率值和变异概率值，运行结果显示，交叉概率Pc=0.8，变异概率Pm=0.01计算结果最优.根据模型求出空车调度需求方案如表4所示，该模型是基于在周期内全部满足用户104个订单的求解结果，共调度25次.若不采用调度方案，从M=5时刻开始站点B就会出现用户无法还车的情况.

表4 空车调度需求方案

2.3 调度路径优化模型实例模拟

调度路径优化模型采用Lingo 11编写程序，计算机为64位操作系统，处理器为Intel (R), Pentium (R), CPU, G2030 @ 3.00 GHz，安装内存为9.00GB.模型输入参数：

假设调度员驾驶折叠电动自行车的行驶速度为v″=20 km·h-1；车辆最高续航里程L=120 km；调度员月工资为8 000元，故每个调度员1 d的工时费C=267元；折叠电动自行车成本C′=1 000元；每个调度任务的收益Rer=15.6元.

根据表4所示调度需求方案，通过计算，采用2个调度员可以完成调度任务的88%，同时满足收益最大化要求.两个调度员的具体调度路径分别为：

(1) O-A-C-C-A-D-A-E-A-C-A-B-A-B-C-C-A-D-A-C-A-O

(2) O-B-D-A-D-B-A-D-A-D-A-D-A-B-A-C-B-C-A-B-C-O

2.4 收益分析

通过对比采用调度策略和扩大车辆、车位规模这两种方式，分析成本投入，以及各自带来的收益变化，均以年作为计算投入与收益的时间范围.相关参数说明及取值见表5.

表5 相关参数说明

通过计算，得到了增设车辆和车位、采用调度策略以及保持原状3种策略下的成本支出与订单收益，如图2所示.

图2 3种策略下的支出与收益对比

在用户用车需求增长的情况下，不增设停车位和车辆数目而采用人工调度优化策略，同比可以提升60%的订单服务量，订单收入增加89.4%，虽然订单收入较增设停车位和车辆数目后的实际情况略有减少12%，但是相比增设停车位和车辆数目可以节约62.4%的成本投入.由此可见，运营公司采取人工调度策略的方式，而非增设停车位和车辆数目的方式可为运营公司节约成本，增加公司收益.

3 结论与展望

目前，国内外出现了多家电动汽车共享运营公司，但因为用户用车时间、空间的不均衡性，在运营之中仍不可避免的出现某些时间站点车辆和车位的供需不平衡状况，车辆的利用率不能达到理想的水平，影响运营公司收益.本文通过对电动汽车共享中车辆调度问题的研究，不同于以往研究基于已知调度需求或基于相对稳定的用车需求条件下求解和优化调度路径，对实际用车需求导致站点车辆不平衡进而产生的调度需求进行研究，从而得到一整套完整的车辆人工调度策略，主要得出以下成果：

(1) 建立了需求全满足前提下的调度成本最小目标函数，构建调度需求模型，并通过遗传算法求解该NP-hard难解问题，设计算法流程和思路.

(2) 在求出调度需求的基础上，提出了调度员采用折叠电动自行车在站点间通行的方法，构建基于收益最大化的调度路径优化模型，采用分支定界法求解模型，生成调度路径方案.

(3) 以“EVCARD”电动汽车共享运营公司5个站点的实际运营数据为例，进行人工调度策略优化分析，通过收益分析发现，相比增设车辆和车位数量，采用人工调度策略能明显提高运营公司收益及车辆利用率，节省车辆、车位的投入成本.

研究结论说明了车辆人工调度策略的有效性，对当前汽车共享行业在运营过程中面临的车辆失衡问题的解决和改善是有益的.但不足之处在于建立的调度路径模型是基于收益最大化的调度方案，因此在一些情况下并不能完全满足出现的调度需求，即无法满足所有的订单的用车需求.在未来的研究中可以考虑采用激励用户的方法进行基于用户激励的自适应调度策略，作为对调度员人工调度的补充，进一步提高车辆利用效率和降低调度成本.此外，未来研究可基于运营数据，建立电动汽车用车需求预测模型，根据预测数据，提前规划共享站点位置、配置车辆和车位数.