基于配送路径优化的换电网络一体化调度研究

董振斌，张　亮，高赐威

（1.国网电力需求侧管理指导中心，江苏南京210024；2.国网天津市电力公司，天津300201；3.东南大学电气工程学院，江苏南京 210096）

基于配送路径优化的换电网络一体化调度研究

董振斌1，张亮2，高赐威3

（1.国网电力需求侧管理指导中心，江苏南京210024；2.国网天津市电力公司，天津300201；3.东南大学电气工程学院，江苏南京 210096）

更换电池模式是电动汽车发展的重要模式之一，当前各地都开展了电动汽车更换电池网络的规划和建设。典型的换电网络应包含具有集中充电功能的集中型充电站和具有换电功能的配送站。文中首先在借鉴物流学物流配送内容的基础上建立了物流车队的配送路径优化模型，然后从配送站的更换电池需求出发，通过细致分析配送站、物流车队以及集中型充电站的输入输出得到基于配送路径优化的换电网络一体化调度模型。

换电网络；一体化调度；配送路径优化；充电策略；集中型充电站

随着各地电动汽车更换电池网络的大量建设，更换电池网络（简称换电网络）正成为电动汽车相关领域的另一个研究热点。文献［1］提出由V2G到V2B的必要性，进而探讨实现B2G面临的运营、管理和技术等方面的问题及解决方法；文献［2］从投资主体、投资运营关系以及盈利模式角度分析了更换电池模式/电池更换站的运营模式及优点；文献［3］研究了换电站的选址定容；文献［4］研究了换电站作为储能系统的优化问题；文献［5］研究了换电网络的机组组合问题；文献［6］研究了换电网络中集中型充电站的选址定容问题，该文指出“集中充电，统一配送”运营模式下至少有集中型充电站和配送站这2种类型工作站。本文以此为对象研究它们之间的一体化调度问题。

从电网运营角度而言，换电模式的核心问题依然是电池组充电问题，在插充模式下电动汽车的能源需求对于电网而言是直接的功率需求；而换电模式下电动汽车的能源需求实际上是电量需求，但是对于电网运营而言电力需求更为重要。换电模式下电量需求转化为电力需求取决于充电策略以及物流配送、充电站充电能力、可用满电池组数量等约束条件。集中型充电站的运行、电池组的调配以及物流车辆的调配是一个有机整体，彼此联系密切。

1　换电网络一体化调度相关概念

基于配送路径优化的换电网络一体化调度（以下简称一体化调度）主要研究换电模式下集中型充电站、物流配送（物流车队）、配送站以及电池组电量需求的优化运行调度问题。其中集中型充电站负责把电网电功率转换为电池电量，在此过程中涉及充电功率的优化；物流配送负责把满电池组配送到配送站并从配送站运回空电池组，在此过程中涉及配送路径和物流时间的优化；配送站负责为电动汽车更换电池组。一个集中型充电站能辐射一定数量的配送站，在正常运营中，一个集中型充电站仅为其所辖区的配送站提供服务，且以一个集中型充电站和数个配送站的系统为例进行研究。

一体化调度能正常运行的2个关键约束是：（1）配送站下一阶段所需的满电池组数量应该在该阶段开始之前已经由物流车队配送到该配送站；（2）集中型充电站必须在物流车队开始配送之前充满该物流车队将配送的满电池组数量。

1.1换电需求

换电需求即配送站的更换电池组需求。统计配送站各个时刻的更换电池组需求可以得到换电曲线，当统计的时间间隔较大时换电曲线则变为离散的点，某地区一天的换电曲线如图1所示。物流车辆安排、电池组调配以及电池组的充电都是根据换电需求进行的。

图1　某地区一天的换电曲线

1.2物流配送系统

物流配送系统负责从集中型充电站运满电池组到配送站并且从配送站运空电池组到集中型充电站。由于物流配送具有时间上的离散性，配送路径的多样性，因此物流系统与换电需求综合将体现以下2个方面的内容：

（1）配送路径优化。配送路径优化问题即为车辆路径问题，本文研究的车辆路径问题属于带回程运输的车辆路径问题。

（2）配送时间优化。配送曲线随配送开始时刻以及配送所需时间的不同而发生改变。例如当配送间隔分别为3 h，6 h时图1所示的配送曲线可变为如图2所示的配送曲线。

图2　不同配送时刻以及配送所需时间下的配送曲线

从图2（a）、图2（b）可以看出当配送时间间隔由3 h变化为6 h时，每次配送电池组数量显著增多；从图2 （b）、图2（c）可以看出配送时刻发生改变后每次配送电池组数量也将发生改变。且以定时配送作为主要研究内容，故未对配送时间进行优化建模。

1.3电网系统

集中型充电站根据不同的充电策略可以得到不同的充电曲线。集中型充电站可采取的充电策略有：基于峰谷差电价的充电费用最小、基于机组组合的发电费用最小。且以峰谷差电价为基础研究建立充电和配送总费用最小的一体化调度模型。

2　换电网络一体化调度模型

基于配送路径优化的换电网络一体化调度模型的主要研究对象有集中型充电站、物流车队、电池组以及配送站，根据配送站的换电需求安排电池组和物流车队的配送策略，进而研究集中型充电站的充电策略（即电池组充电时间和数量）。

2.1配送路径优化模型

物流车队配送路径直接影响着配送所需的时间，而配送费用与配送所需时间成正比，故在进行物流车队配送路径优化时以各物流车队配送所需时间的总和最小为目标。在此目标下为便于车队的管理以及集中型充电站的充电运行，需要尽可能使得各物流车队配送所需时间相等。通过该模型求解得到的方案不会因为研究周期以及配送站换电曲线的变化而发生改变。

配送路径优化问题属于混合整数规划问题，其模型可表达为：式（1）中：tdisk为第k个物流车队（考虑构成物流车队的物流车辆类型均相同）所需的配送时间，该配送时间不仅包括装卸电池组所需时间而且包括路上的行驶时间，min；n为示设定的物流车队数量；为n个物流车队配送所需时间的平均值，min。

第k个物流车队所需要的配送时间的计算表达式为：

式（2）中：tij为配送站ij间所需的时间（包括装卸时间和行驶时间）；yijk为车队路径安排，其为0，1变量，若车队k经由配送站i到配送站j，则yijk为1，否则为0；Lk为第k个物流车队所服务的配送站的集合。

其约束条件［7，8］为：

（1）保证每个配送站均被服务，而且每辆车都从集中型充电站出发：

（2）对任一由k服务的配送站j，必定有另一（而且只有一个）由k服务的配送站i（包括集中型充电站），物流车队k从配送站i到达配送站j，而对由k服务的配送站i同样存在由k服务的另一配送站，物流车队k是从该配送站到达配送站i的。

式（4）中：G0=G∪｛0｝，G=｛1，…，nds｝为配送站集合；｛0｝为集中型充电站。

在得到各物流车队的配送路径后即可根据各物流车队所负责的换电需求按比例得到各物流车队包含的物流车辆数：

式（5）中：nevi为第i个物流车队包含的物流车辆数；Ni为第i个物流车队所负责的换电总需求；Nall为区域总换电需求；nevall为总物流车辆数，该值为给定值。

2.2定时配送下的换电网络一体化调度模型

物流配送按照时间及配送商品数量可分为定时配送、定量配送、定时定量配送、定时定线路配送以及即时配送，且以定时配送为例研究一体化调度模型。

2.2.1换电网络一体化调度目标模型

一体化调度的目的是在满足配送站、物流车队以及集中型充电站等约束的基础上使得物流费用C物流和充电费用C充电的总和最小，一体化调度问题属于非线性整数规划问题，其模型可表示为：

该模型需同时满足配送站约束、物流车队约束和集中型充电站约束，且其中配送站、物流车队以及集中型充电站间的输入输出如图3所示。

图3配送站、物流车队以及集中型充电站间输入输出

图3中，Q'i空电池组（n-1）为第i个物流车队在n-1次配送中运往集中型充电站的空电池组数量；Qi满电池组（n）为第i个物流车队在n次配送中从集中型充电站运出的满电池组数量；Qi需求（n）为第i个物流车队负责的配送站在n次配送时段内所需的满电池组数量；Qi空电池组（n-1）为第i个物流车队所负责的配送站在n-1次配送时段内的空电池组数量 （包含该时段产生的空电池组以及站内原有的空电池组）；Qi供应（n）为第i个物流车队在n次配送中供应给配送站的满电池组数量。通过该图可知配送站缺电池组数量为Σ（Qi需求（n）-Qi供应（n））。

物流费用C物流和充电费用C充电分别为：

式（7，8）中：nreal_evi（j）为i个物流车队在第j次配送中实际需要的物流车辆数；cev为单个物流车辆每小时的运费，元/h；ηij为第i个物流车队第j次配送的车辆冗余系数，本文假设冗余系数为20%；tdisi为第i个物流车队所需的配送时间；ncb（t）为第t个时刻集中型充电站充电的电池组数量；为单块电池组的充电功率；pi（t）为第t个时刻的电价。

以物流车队所辖配送站的换电总需求以及空电池组数量为研究对象，但是对于单个配送站可能其需要运回的空电池组需求要比其换电需求大，这时就需要额外的物流车辆（在式中加入的车辆冗余系数ηij来进行考虑）来装载需要运回的空电池组。通过设置车辆冗余系数还可以使得装载空电池组和卸下满电池组同时进行且操作方便。

2.2.2约束条件

（1）配送站的主要功能是为电动汽车提供满电池组而替换下空电池组，n-1次配送时段内站里空电池组数量 （包含该时段产生的空电池组以及站内原有的空电池组）为：

式（9）中：CiL为第i个物流车队的运力；Qi空电池组（n-2）为第i个物流车队所负责的配送站在n-2次配送时段内产生的空电池组数量；Qi供应（n-1）为第i个物流车队在n-1次配送中供应给配送站的满电池组数量。

（2）物流车队负责从集中型充电站运满电池组给配送站并且从配送站运回空电池组给集中型充电站，其中的关系可表示为：

式（10—13）中：nevi为第i个物流车队的物流车辆数；nev_pack为单辆物流车所能装载的电池组数量；nreal_evi（j）为i个物流车队在第j次配送中且实际需要的物流车辆数。

式（10）表示物流车队提供的满电池组数量与配送站的需求、集中型充电站的满电池组数量以及物流车队运力密切相关，为3者的最小值。式（11）表示物流车队运往集中型充电站空电池组数量取决于配送站的空电池组数量与物流车队运力的最小值。式（13）表示每次配送所需的实际物流车辆数由物流车队提供的满电池组数量Qi供应（n）与物流车队运往集中型充电站的空电池组数量Q'i空电池组（n-1）决定，ceil（）表示向上取整。

（3）集中型充电站负责把物流车队运回的空电池按照充电策略安排充电。

① 集中型充电站的空电池组数量约束。

式（14）中：Qall空电池组（n）为集中型充电站n（n＞1）次配送开始时总的空电池组数量；Qall空电池组（0）为集中型充电站在初始时刻总的空电池组数量。

② 假设t-1时刻对应于第n次开始配送时刻，t-1时刻之前（包含t-1时刻，t≥1）充电的电池组数量之和不大于集中型充电站t-1时刻之前（包含t-1时刻）空电池组数量之和：

③ t-1时刻之前（包含t-1时刻，t≥1）充电的电池组数量之和等于各物流车队在n次配送中从集中型充电站运出的满电池组数量之和：

④ 集中型充电站各时段充电的电池组数量应不大于集中型充电站的容量：

⑤ 从集中型充电站运出的满电池组数量应在物流车队运力允许的条件下，尽可能满足配送站的换电需求：

模型 （6）的已知量有Qi需求（n），CS，CiL，Qall空电池组（0），Ppack，pi（t），nev_pack，Pc，cev；其余变量均为待求解量。

3　求解步骤和方法

采用遗传算法对物流车队路径优化模型进行求解，具体的遗传操作见文献［8］。所建定时配送下换点网络一体化调度模型的求解步骤如图4所示。

图4　一体化调度模型求解步骤

根据图4即可求解出各物流车队的配送策略，即各个物流车队每次配送的满电池组数量、运回的空电池组数量、每次配送所需的物流车辆数等内容。图4中的各物流车队开始配送时间可根据实际运行情况用户自己输入。

集中型充电站的充电策略如图5所示。集中型充电站根据配送站的换电需求利用站内已有的空电池组数量以及物流车队每次运回的空电池组数量安排空电池组的充电，通过该充电策略可以得到集中型充电站各时刻充电的电池组数量。

4　算例分析

4.1参数说明

4.1.1物流配送

（1）上海市货运出租汽车运价管理办法中规定包车收费标准为0.9 t及以上车辆50元/h。且研究的配送车辆为0.9 t，单块电池组质量为30 kg，则一辆车可装载电池组数nev_pack为30块。

（2）一次配送结束后开始另一次配送，一个完整的配送过程包括：① 在集中型充电站装载满充满电的电池组，所需时间为10 min；② 把充满电的电池组从集中型充电站运往配送站；③ 在配送站卸下充满电的电池组，所需时间为5 min；④ 在配送站装上电动汽车更换下来的电池组，所需时间为5 min；⑤ 把更换下来的电池组运往集中型充电站；⑥ 把更换下来的电池组放到充电架上，所需时间为10 min。

图5　集中型充电站充电策略

（3）参与配送的物流车辆在完成整个配送过程后随车队一起返回集中型充电站，中途即便空载也需完成这样的过程。

（4）物流车队的配送时刻是指物流车队从集中型充电站开始出发的时刻。

（5）本文不考虑交通拥堵导致的配送时间增加。

（6）物流车队每次配送电池组数量是指相邻两次到达配送站期间的换电总需求，由于物流车队到达每个配送站所需的时间不同，所以需要结合实际到达各配送站的时刻来进行统计（例如，物流车队1负责的配送站有2个，编号分别为2和3，假设物流车队1从集中型充电站出发时刻为08：00，到达配送站2和配送站3的时刻分别为08：30和09：00，第二次配送时刻为10：00，此时到达配送站2和配送站3的时刻分别为10：30 和11：00，配送站2在08：30-10：30期间的换电需求为200块，配送站3在09：00-11：00期间的换电需求为400块，故物流车队1配送的电池组数量为600块）。

4.1.2电池组

（1）电动汽车换下的电池组类型均相同，假设电池组恒功率充电，充电功率为2 kW，充电所需时间为2.5h；

（2）考虑到电池组配送多次配送的方便，研究锂离子电池组连续充电的情况，一天当中的可充电时段根据研究开始时刻以及配送开始时刻确定。例如图6中以研究开始时刻t0和配送开始时刻tD1，tD2，tD3为起点可划分得到8个可充电时段，分别为TC1，TC2，…，TC8，时段的长度即为电池组连续充电所需的时间。电池组选择在8个时段中的哪些时段进行充电是根据电池组需求以及各时段平均充电电价来确定的，优先选择充电电价低的时刻进行充电，其操作流程如图6所示。此时图5中“时间t按照充电电价由低到高进行排序”变为“各充电时段TC按照充电电价由低到高排序”。

图6　一天中可充电时段划分

4.1.3换电曲线

（1）配送站的换电曲线是指每个时刻配送站更换电池组的数量 （主要研究每30 min一个点的换电曲线，即每30 min总换电量得到的换电曲线），且以一个典型日的换电曲线为例进行研究；

（2）换电曲线每个时间点对应的更换电池组量是指从该时间点开始到下一个时间点前总的换电需求。

4.1.4初始状态

（1）典型日各配送站的换电曲线已知；

（2）各物流车队初始时刻可利用的集中型充电站满、空的电池组数按照各物流车队所负责的换电总需求进行比例分配，各物流车队根据自身的配送情况在集中型充电站安排充电，通过这样处理可方便集中型充电站充电任务的安排而且可以均等的为各配送站提供服务；

（3）把集中型充电站与其他用户同等看待时，峰、谷、平电价即为集中型充电站的充电电价。

4.2配送路径求解

研究算例如图7（配送站在图中用D表示，集中型充电站在图中用C表示）所示。假设预测的各配送站典型日换电曲线如表1所示。一天当中换电总需求为2405块。配送站对应的交通节点如表2所示。

图7　集中型充电站所辖区域交通网络结构

表1　各配送站换电需求

表2　配送站对应的交通节点

假设总的物流车辆数为100辆，通过求解配送路径优化模型（式（1））可以得到2物流车队情况下的物流车队设置（物流车队行驶路径见图中箭头所示）为：

（1）物流车队1负责的配送站有3，2；负责的总换电需求为1090块；包含45辆物流车辆；完成一次配送所需时间大约为2 h。

（2）物流车队2负责的配送站有5，4，1；负责的总换电需求为1315块，包含55辆物流车队；完成一次配送所需时间大约为2 h。

4.3定时配送下的换电网络一体化调度模型求解

4.3.1方案比较

根据初始状态（即集中型充电站初始时刻满、空电池组数以及区域所有配送站的初始满、空电池组数，分别简记为CF，CE，DF，DE）设置的不同，且设置4个方案来验证模型的有效性，如表3所示。初始时刻各配送站的满、空电池组数量按照各配送站的换电需求进行比例分配。典型日各时刻的电价如图8所示。其他参数如表4所示。

表3　方案介绍　块

图8　算例中典型日各时刻电价

表4　参数设置

根据各物流车辆单次配送所需时间 （单次配送所需时间为2 h）对物流车队配送时刻的设置如下：

物流车队 1的配送时刻为 06：00，10：00，14：00，16：00，20：00；

物流车队 2的配送时刻为 07：00，10：00，16：00，21：00。

通过对式（6）求解可以得到表5和图9。通过比较可以发现，总费用由低到高分别为方案3、方案1、方案2、方案4，初始状态不同对模型求解结果影响很大。各方案求解结果如表5所示。

表5　各方案求解结果

图9　配送站1满电池组数量变化趋势

根据表5和图9，且从表5可以得到以下几点：

（1）方案1即便集中型充电站的满电池组数量可满足全天的换电需求，但各物流车队配送到达之前无法满足各配送站的换电需求，所以最终导致缺120块电池组；方案3由于配送站在初始时刻有满电池组储备，其可满足物流车队第一次配送到达之前的换电需求，所以不会缺电池组。

（2）方案4虽然初始时刻集中型充电站的满电池组数量不能满足全天的换电需求，但通过对更换下来的电池组进行充电，然后用于以后的配送当中，这样可达到方案一的效果（即缺满电池组数量为120块）。

（3）结合图9可知，虽然方案4充电的电池组数量少，但是充电费用较方案2高，这主要是因为方案2利用夜间廉价电能进行了的充电，而方案4利用白天的负荷高峰电价进行充电。

4.3.2配送站满电池组变化分析

以方案4情况下配送站1为例研究配送站满电池组数量变化，通过求解可得方案4中物流车队二到达配送站1的时刻及配送的满电池组数量，如表6所示。

根据表6以及换电曲线可得到配送站1的满电池组数量变化趋势，如图10所示。

表6　到达配送站1的时刻以及配送的满电池组数量

图10　配送站1满电池组数量变化趋势

5　结束语

本文利用物流学相关理论得到物流车队的配送路径优化模型，在此基础上得到基于配送路径优化的换电网络一体化调度模型。通过对不同方案的分析可知集中型充电站和配送站的初始状态、配送时间的选择等都对模型的求解具有重要影响。

［1］薛 飞，雷宪章，张野飚，等.电动汽车与智能电网从V2G到B2G的全新结合模式［J］.电网技术，2012，36（2）：29-34.

［2］杨永标，黄 莉，徐石明，等.电动汽车换电商业模式探讨［J］.江苏电机工程，2015，34（3）：19-24.

［3］WANG C N，YANG J Y，LIU N，et al.Study on Siting and Sizing of Battery-Switch Station［C］//4th Conference on Electric Utility Deregulation and Restructuring and Power Technologies （DRPT），2011：657-662.

［4］薛钟兵，彭 程.新能源发电与电动汽车充换储站协调运行研究［J］.江苏电机工程，2014，33（5）：36-38.

［5］张 舒，胡泽春，宋永华，等.考虑电动汽车换电站与电网互动的机组组合问题研究［J］.中国电机工程学报，2012，32（10）：49-55.

［6］高赐威，张 亮，薛 飞，等.考虑集中型充电站定址分容的电网规划研究［J］.中国电机工程学报，2012，32（7）：40-46.

［7］陈火根，丁红钢，程耀东.物流配送中心车辆调度模型与遗传算法设计［J］.浙江大学学报（工学版），2003，27（5）：512-516.

［8］宋伟刚，张宏霞，佟 玲.有时间窗约束非满载车辆调度问题的遗传算法［J］.系统仿真学报，2005，17（11）：2593-2597.

董振斌（1967），男，江苏淮阴人，高级工程师，从事电力工程和电力需求侧管理工作；

张亮（1987），男，山西太谷人，工程师，研究方向为配电网规划及运行、电动汽车接入电网；

高赐威（1977），男，浙江淳安人，博士生导师，研究方向为电力需求侧管理与需求响应、电力规划、电动汽车接入电网。

centralized charging stations

The Integration Optimal Scheduling Model of Battery Switching Network Considering Distribution Routing Problem

DONG Zhenbin1，ZHANG Liang2，GAO Ciwei3
（1.State Grid Demand Side Management Supervision Centre，Nanjing 210024，China；2.State Grid Tianjin Power Company，Tianjin 300201，China；3.Electrical Engineering School of Southeast University，Nanjing 210096，China）

Battery switching is one of the most important developing modes of electric vehicle.Currently the planning and construction of battery switching network have been carried out in most of the provinces of China.Typical battery switching network should include centralized charging stations for centralized charging and distribution stations for battery switching.In the reference of logistics'relevant contents，the routing problem of logistics team is solved，then according to the needs of distribution stations，on the basis of detailed analysis input and output of distribution stations，logistics teams and large-scale centralized charging station，the integration optimal scheduling model is built.

battery switching network；integration scheduling；distribution routing problem；charging strategy；large-scale

TM714.1

A

1009-0665（2016）04-0044-07

2016-02-23；修回日期：2016-03-31

国家自然科学基金项目：51207022