基于预约模式的移动充电车实时需求响应策略研究

孙丽君, 李方方, 王新月, 胡祥培

(大连理工大学 经济管理学院,辽宁 大连 116024)

0 引言

移动充电车由于其灵活移动性[1]缓解了固定充电桩站点分布不均衡导致的电动汽车车主的续航焦虑问题，有效地补充了电动汽车充电网络。然而，目前移动充电车充电方式大多借助e充电等网上预约充电app，由电动汽车车主根据app中披露的移动充电车状态自主预约充电。这种预约充电模式对移动充电车运营商而言是一种被动的需求响应，没有从整体上高效智能地响应预约需求，导致物流成本高、客户满意度低。比如，当充电需求的位置偏僻且充电时段在需求高峰时段时，系统若响应该需求，则未来可能无法响应其它高盈利性的充电需求。因此，本文提出了新的预约模式：首先，电动汽车车主基于预约充电app披露充电需求，包含服务时间窗、充电的位置及电量；然后，移动充电车运营商综合考虑该需求属性、已接受订单、未来需求、移动充电车的当前位置及剩余电量等，实时评估该需求对整体收益的影响以实时判断是否响应该需求，即，如果该需求不能增加整体收益，则不响应；否则，响应该需求并将其转换为订单进行服务。本文基于该模式，从移动充电车运营商的角度，研究考虑整体收益的实时需求响应策略，这对于企业整体收益的提高及移动充电行业的发展意义重大。

本文所提实时需求响应策略需要主动、实时地判断是否响应动态到达的预约需求(Late Customers, LCs)，该过程会受到已经接受的预约需求(Early Customers, ECs)的影响，需要决策以下内容：1)考虑整体收益，实时决策是否响应LCs及响应LCs后如何服务；2)考虑充电时间窗，为ECs制定具有动态可调整性的充电服务方案。因此，与本研究密切相关的研究有两大类。一类是实时需求响应策略(Real-time Demand Response Strategy, RDRS)研究，其主要聚焦于需求被响应后，如何制定分配策略，如，Chen[2]等人在响应需求后使用基于规则的分配策略，首先将服务区域划分为子区域，其次将需求分配给其子区域内最近的空闲车辆，如果其子区域内没有空闲车辆，则寻找周围的子区域；Hyland[3]等人提出并比较了六种分配策略。一类是考虑未来随机需求信息的带时间窗约束的动态车辆路径问题(Dynamic vehicle routing problem with time windows and stochastic service requests, DVRPTWSSR)[4]。该类研究主要基于未来随机需求研究车辆的等待策略，比如，Mohamed[5]研究考虑未来客户需求的动态车辆问题，提出基于共同进化的等待策略生成方法以最大化可以服务的需求数量。该类研究的求解主要基于特定的需求概率分布，采用Sampling方法、随机规划方法等。Sampling[6]方法一般基于随机分布生成场景集；随机规划方法主要包括近似动态规划(Approximate Dynamic Programming, ADP)[7]与马尔可夫决策过程[8]等。由于本研究面临高维的决策变量与状态变量，基于状态空间搜索求解时会出现“维数灾”，且需要确定趋于收敛的决策后状态的未来价值。而ADP能有效避免“维数灾”，也能基于仿真不断迭代确定近似最优的决策后状态的未来价值，以在决策中考虑未来的随机信息。因此，本文采用ADP综合未来随机需求信息，以基于决策后状态的未来价值进行决策。

综上所述，现有两类研究可为本研究提供思路，但不能被直接应用于本研究，原因如下：1)实时需求响应策略的研究主要针对希望尽快被服务的即时需求，研究需求响应后的分配策略，这些需求往往没有时间窗约束；而本文针对具有充电服务时间窗的预约需求，且需要实时判断是否响应LCs。2)DVRPTWSSR的相关研究一般基于未来随机需求研究的等待策略；而本文在基于未来随机需求的同时，研究ECs的充电服务路径方案的动态更新与LCs的实时响应决策。3)在ADP的相关研究[9]中，动态需求的时间窗约束要求较松，可宽延至下一天被服务；而本文的充电需求不仅有明确的充电服务时间窗，而且LCs的实时响应决策与ECs的充电服务方案存在着动态交替影响。

本研究同时具有DVRPTWSSR问题和RDRS问题的特征，且LCs和ECs要考虑未来的随机需求进行决策，以上三类问题特征的融合产生如下难点：1)LCs的动态到达性和实时响应性导致不能基于已知的需求信息确定需求响应策略；2)预约模式下，LCs的实时响应决策与ECs的充电服务方案L存在动态交替影响，即L将约束可响应的LCs，响应LCs后将触发L的更新；3)ECs和LCs都有严格的充电服务时间窗约束；4)未来需求的不确定性增强了系统的动态性，也增加了LCs和ECs联动决策的难度。

因此，为满足LCs和ECs的要求的同时考虑其动态交替影响，本文提出了考虑未来需求的两阶段实时需求响应策略：第一阶段为ECs滚动决策出可动态调整的服务路径方案，并输入到第二阶段；第二阶段则实时决策是否响应LCs，如果响应，则纳入到ECs序列；其中，决策的未来价值采用基于ADP思想的近似值迭代(AVI)算法求解，以衡量未来需求对决策的影响。最后，数值实验比较了本文策略与其他策略的整体收益，明确了本文策略的适用场景，并给出了管理启示。

1 两阶段移动充电车实时需求响应策略

1.1 问题描述与假设

结合实践调研结果及相关文献，本研究的前提如下：1)移动充电车的类型相同且数量固定不变；2)车辆匀速行驶，其行驶时间和行驶距离成正比；3)每个预约订单由且仅由一辆移动充电车服务；4)充电服务时长与充电量成正比；5)已响应的LCs必须服务；6)有可以满足ECs的充电服务路径方案；7)移动充电车基于订单的服务时间窗为其充电，若早到则须等待；8)移动充电车服务完某订单后若无后续任务，则在该点等待；9)不考虑未被响应的预约需求的惩罚，因为该预约模式是基于移动充电车运营商的视角，最大化运营商在一个工作周期内的整体收益，可以不响应不利于提高整体收益的预约需求，其不响应机制对于客户而言是不透明的，因此不会影响本次未被响应客户的下次下单；同时，不响应该需求不是拒绝其进入预约系统寻求服务，而是激发其改变预约属性[10]，如，充电的服务时间、地点等，以系统能接受的属性重新进入系统以获得响应。

1.2 移动充电车实时需求响应策略

由于ECs会随时间的推移不断更新，此时ECs的订单组的结构对后续LC的响应存在较大影响。因此，本研究将工作周期划分为K+1个时段，K为正整数，每个时段的时间长度t固定，在各时段滚动实现本文策略，如图1所示，包含以下方法和步骤：1)第一阶段是为ECs，滚动决策出可以动态更新的充电服务路径方案(1.2.1节)；2)第二阶段是针对LCs进行实时响应判定决策(1.2.2节)；3)采用基于ADP思想的近似值迭代(AVI)算法决策出趋于收敛的决策的未来价值，并将其融于两阶段响应策略中(1.2.3节)。

图1 实时需求响应策略流程图

1.2.1 第一阶段需求响应策略

本节为最大化ECs的充电服务路径方案的整体收益，提出多阶段随机动态决策模型。该模型在每个阶段初选择可以最大化当期收益和未来价值之和的决策X*(Sk)及其对应的服务路径方案L*。为保证ECs可以满足时间窗约束，每个决策点可采取的决策X(Sk)是基于VRPTW模型与禁忌搜索算法确定的。其中，多阶段随机动态决策模型、X(Sk)的确定流程的具体描述如下。

(1)多阶段随机动态决策模型

(2)确定每个决策点可采取决策的流程

每个决策点可采取决策的确定步骤如下：

Step1基于Sk构建静态VRPTW模型

本文构建以下静态VRPTW模型:

max∑m∈M∑(i,j)∈R(qj×qc-cij)xijm

(1)

∑m∈M∑j∈Nxijm=1,∀i∈N*,i≠j

(2)

∑j∈Nx0jm≤1,∀m∈M

(3)

ej≤sjm≤lj,∀j∈N*,∀m∈M

(4)

sim+tij-sjm≤(1-xijm)Fijm,∀(i,j)∈R,∀m∈M

(5)

xijm∈{0,1},∀(i,j)∈N,∀m∈M

(6)

其中，式(1)表示最大化总收益(订单总收益减服务订单的总行驶成本)；式(2)表示每个已经接受的充电订单能且仅能被服务一次；式(3)表示移动充电车一天最多从充电站出发一次进行充电服务；式(4)表示移动充电车m开始服务客户j的时刻在[ej,lj]内；式(5)表示移动充电车基于预约订单充电时间窗的时间顺序进行充电；式(6)表示决策变量的取值约束，移动充电车m通过弧(i,j)并服务订单j时，xijm=1，否则xijm=0。

Step2基于禁忌搜索(Tabu Search, TS)算法求解静态VRPTW模型。

根据VRPTW求解算法文献[11]，TS算法搜索范围和产生可行解的空间广，已用于求解静态VRPTW、DVRPTWSSR问题等[12]，是目前较有效的VRPTW模型求解算法。因此，本文基于TS算法求解静态VRPTW模型：首先，基于插入式算法生成初始路径方案L0；其次，L0分别执行u次TS算法，得到u个服务路径方案Lr(r=1, 2, …,u)，其中每次算法执行时的最大迭代次数不同。

Step3基于Lr提取每个决策点可采取的行动。

1.2.2 第二阶段需求响应策略

(1)响应LCs的可行性判断

判断响应LCs是否可行，要判断该需求插入L*后能否同时满足移动充电车的载电量约束和需求的服务时间窗约束[13]。设L*中某条服务路线rm={m1,…,md,…,mp}。则如果rm的第d个订单之后能够插入需求h，需要同时满足如下约束：

(7)

(8)

(9)

(10)

(11)

Tmh+Wmh-(sdm+Tmd+Wmd+tmd,md+1)

=tmd,mh+Tmh+Wmh+tmh,md+1-tmd,md+1

(12)

(13)

(2)响应LCs的价值性判断

判断响应LCs是否有价值，主要判断不插入新需求的当前收益与决策后状态对应条目的价值之和是否比插入该需求时大；如果大，则不响应该需求；否则，响应该需求。

1.2.3 AVI算法

(14)

其中，α表示近似过程的步长。为了快速有效的近似，本研究利用动态查表算法(DLT)[9]设计近似值函数，将决策后状态的价值存储在表格中。该算法将状态空间分割为不同分区并用条目表示，并根据分区的重要程度进行不同粒度的划分。本研究中LCs的响应决策和ECs的最优服务路径决策受可用服务资源和待服务订单数影响，因此本文的状态空间由剩余工作时间、剩余载电量、剩余订单数组成。该状态空间涉及三维DLT，演化实例见图2，从左到右，状态空间的不同分区进行了不同程度的裂变，最终右上角区域未发生裂变，左下角区域高度分裂，是重点区域。

图2 DLT的动态演化示例图

2 实时需求响应策略生成的仿真流程设计

仿真流程包含两步：1)离线仿真过程，仿真本文策略，采用AVI算法求得趋于收敛的决策后状态的未来价值Vπ*；2)预约需求的在线响应过程，基于Vπ*确定期初ECs的最优充电服务路径方案L*，并实时决策是否响应LCs。

2.1 离线仿真过程

该过程的具体步骤如下：

步骤1初始化迭代次数：n←1。

步骤2初始化以下参数：时段k←0，累计收益R-1←0，基于系统当前状态S0与插入式算法确定车辆路径方案L0，条目的价值V(ω0)。

步骤3第k个时段初，根据每个决策点可采取决策的流程，获得L*、时段(k×t,(k+1)×t](Tk)内采取的具体行动SAk(*)、SAk(*)的当前收益R(SAk(*))、决策后状态及其对应的条目ωk，并更新累计收益Rk=Rk-1+R(SAk(*))。

步骤4基于L*以及LCs的可行性与价值性判断，实时判断时段Tk内是否要响应LCs(注：离线阶段还没有得到Vπ*，且，LCs的响应数量可在一定程度上反映状态价值，因此，LCs的价值判断环节只要能够响应新需求就响应)。

步骤5判断时刻是否到(k+1)×t，如果是，则令k=k+1、L0=L*，进入步骤6；否则，回到步骤4。

步骤6判断k是否等于K，如果是，进入步骤7；否则，回到步骤3。

步骤9令n=n+1，判断n是否大于Mn，如果是，则输出全部条目及其价值；否则，回到步骤2。

2.2 预约充电需求的在线仿真过程

ECs的充电服务路径方案按以下步骤生成：

步骤1令决策点k=-1，生成初始方案L0。

步骤2判断k是否小于K，若是，转入步骤3；否则，结束。

步骤3令k=k+1，基于X(Sk)的确定流程与Vπ*，确定L*、Tk内的行动集合SAk(*)。

步骤1基于LCs的可行性判断，判断LCs能否插入到L*，若不能，则不响应该需求；否则，转到步骤2。

步骤2基于响应LCs的价值判断与Vπ*，判断不插入LCs的整体收益是否比插入时大，如果是，则不响应该需求；否则，响应该需求并将其纳入ECs订单集合中，更新L*。

步骤3判断是否到(k+1)×t，如果是，则执行针对ECs的步骤2～3；否则，回到步骤1。

3 数值实验

3.1 算例设计与算法参数

本文参数根据调研实际设置为：仿真时长为8h，移动充电车行驶速率为25km/h，条目初始价值为1000。本算法基于python3.6实现，测试环境为Intel Core i7，16GB内存的Windows平台。

3.2 策略比较

本文为验证所提策略的有效性，将其与经典响应策略[3]进行对比实验。为保证策略的一致性，本文对经典策略进行以下改造：①构造符合本研究充电需求特点的需求；②基于静态局部优化算法确定车辆服务路径方案后，判断能不能响应LCs。两种策略的区别为：针对ECs，比较策略是基于即时收益确定最优车辆路径方案L1*，本文策略则基于即时收益与决策未来价值确定；针对LCs，比较策略是只要需求能插入L1*就响应它，本文策略还要判定响应该需求的未来价值。

本文以表示研究目标的期望整体收益AR和反映动态需求响应质量的期望响应时间AT为评价指标，进行了100次对比实验。其中，AR和AT的单位分别为元和秒。针对ECs和LCs的特点，本文比较两种策略在动态度dd和客户规模nd不同取值下的效果，并得出管理启示。同时更新时段长度Δt、移动充电车车辆规模nc也会影响实验结果，为确定其取值，本文以RC101为例，进行不同Δt、nc的对比实验，结果分别如表1、表2所示：1)Δt=20min时，两种策略的AR最大且更新频次适中，因此，后续实验中Δt取为20min；2)nc=5时，本文策略的AR增加百分比(PIAR=(本策略AR-对比策略AR)/对比策略AR×100%)最高，但是本文策略及对比策略的AR最低；nc=15时，两种策略的AR、PIAR表现均不错，因此，后续实验中nc取为15。

表1 不同Δt下的整体收益期望值实验结果

表2 不同车辆规模下的整体收益期望值实验结果

(1)动态度

为验证dd对策略效果的影响，令dd取不同值进行策略对比实验，AT的比较结果如表3。为清楚地展示三种算例在不同dd、不同响应策略下的AR及本文策略的PIAR变化情况，本文绘制图3。

表3 各策略不同动态度的实验结果

图3显示，本文策略及对比策略的AR随dd的变大而下降。这是由于两种策略是按时段滚动更新ECs的服务方案，dd越高，可响应的LCs的数量可能越少，AR就越低。图3中本文策略PIAR的变化趋势图显示，dd越高，本文策略的PIAR也越高，这说明相同条件下，LCs占比较多时，本文策略具有更好的实时决策能力。同时表3显示，两种策略的AT随dd的增加却下降。这是由于对LCs的实时响应需要判断其能否插入期初生成的L*，而dd越高，ECs数量占比越小，L*的规模越小、复杂度越低，遍历L*耗费的时间越短，因此AT呈明显下降趋势。同时，本文策略的AT均在0.01s内，可以满足需求响应的实时性要求。

(2)客户规模

为分析客户规模nd对策略目标的影响，本节将算例RC101、R101、C101的nd增加一倍，分别命名为RC1_2_1、R1_2_1、C1_2_1，并维持其他实验条件不变。三种算例在不同响应策略、不同dd下的AR、AT的结果见表4，在不同dd下PIAR的表现见图4。为了直观地反映不同nd对本文策略PIAR的影响，本文绘制本策略在不同nd中PIAR的绝对差值随dd变化的趋势图，见图5。

图3 动态度对本策略与对比策略期望收益大小的影响

表4 各策略不同动态度下的实验结果(nc=15)

图4 动态度对本策略整体期望收益增加百分比的影响

图5 动态度对本策略在不同客户规模下整体期望收益增加百分比绝对差值的影响

首先，观察同一客户规模下两种策略的表现。表4、图4显示，两种客户规模下的结果类似：1)两种策略的AT和AR均随着dd的增大而减少，且本文策略的AT均在0.01s内，因此本文策略符合决策的实时性要求；2)本文策略的PIAR随着dd的增大而增大。然后，观察各算例在不同规模中本策略相较于对比策略的PIAR的趋势。图5显示，PIAR的绝对差值(大规模算例下PIAR-小规模算例下PIAR)均大于0，且随dd的提高逐渐增高，说明本策略在大规模、动态度较高的需求响应问题中更有优势。且图4显示，本文策略在动态度为0.95的C1_2_1中，PIAR最大。为进一步验证本文策略在动态度为0.95的C1_2_1中的效果，本文做了不同nc下的对比实验，结果见表5：1)本文策略相较于对比策略的PIAR在不同nc下的提升幅度均较明显，进一步验证了前文所述nc对本文策略的影响；2)nc为30时，本文策略具有最高的AR与PIAR。为进一步探讨nc为30时，表4中三个算例在不同dd下AR、AT的效果，本文做了对比实验，结果如表6所示，进一步验证了本文策略的AR均高于对比策略，且在C1_2_1中有较高的提升幅度。

表5 不同车辆规模下的整体收益期望值实验结果

表6 各策略不同动态度下的实验结果(nc=30)

(3)管理启示

上述对比实验可得出以下结论：1)在不同的更新时段长度、车辆规模、动态度以及客户规模下，本文策略的系统整体收益相对于经典策略都有了提升；同时，本文策略在大规模算例C1_2_1中，在高动态度0.95、不同车辆规模下，期望总收益相较于经典策略增加的百分比提升幅度均较明显；2)虽然本文策略在某些情况下的整体收益较经典策略提升的绝对值幅度不是很大，但是该提升收益仅是一天期望总收益的提升，实践中任何一点收益的每日提升，在长期上都有很大的价值，这是企业孜孜不倦追求的目标。特别地，企业规模越大，长期累计的价值将越高。因此，基于本文策略的长期累积价值是不可估量的。

数值实验结果可以得出以下管理启示：(1)与经典响应策略相比，本文所提策略随着动态度的增大对整体收益增加的优势越来越突出，且在客户规模较大时对整体收益的优化空间更大；(2)本文提出的预约模式下考虑未来需求的实时需求响应策略，既可以动态更新已接收未服务的订单的服务方案，也可以实时响应动态的需求，且与对比策略的响应时间差较小。因此，本文所提策略更适用于随机到达的客户规模较大、资源较短缺的场景，如，供小于求的繁忙时段、应急情景。

4 结论

考虑整体收益的实时需求响应策略是移动充电行业发展过程中面临的新问题，有新的特点和难点。本文定义了预约模式下的实时需求响应问题并为此提出了联动的两阶段实时需求响应策略，使得预约模式下的实时需求响应决策更加智能，为类似具有静、动态相结合特征，且考虑未来需求的实时需求响应问题提供了新思路，拓展了DVRPTWSSR的问题域，丰富了DVRPTWSSR和实时需求响应策略交叉领域的应用研究，具体的贡献在于：

(1)提出了以最大化整体收益为目标的两阶段实时需求响应策略，满足了ECs和LCs的要求的同时考虑了两者的动态交替影响关系：第一阶段基于多阶段随机动态决策模型与禁忌搜索算法生成了可以动态调整的充电服务方案，既满足了ECs的充电服务时间窗要求，也考虑了决策的未来价值；第二阶段基于第一阶段，提出了LCs的实时响应决策流程，保证了LCs的响应可以提高企业的整体收益。(2)采用基于ADP思想的AVI算法确定决策的未来价值，并应用于需求响应决策的两个阶段，提高了企业的整体收益。(3)数值实验结果验证了本文策略在不同客户规模和不同动态度下的有效性，本文策略适用于客户规模较大、动态度较高的实时需求响应问题，对提高服务运营商收益的效果更明显。

后续研究将根据移动充电车的运营实际，修正决策后状态未来价值的近似模型，增强响应决策的科学性。另外，实时需求响应策略优化研究可以同时考虑企业收益和客户满意度，以促进移动充电行业的持续稳定发展。