Modeling and Simulation
Vol. 09  No. 01 ( 2020 ), Article ID: 34368 , 12 pages
10.12677/MOS.2020.91008

Modeling and Simulation on Electric Vehicle Routing Problem with Improved Charging Strategy

Yongji Jia, Mei Chen, Jia Li

Glorious Sun School of Business and Management, Donghua University, Shanghai

Received: Feb. 6th, 2020; accepted: Feb. 21st, 2020; published: Feb. 28th, 2020

ABSTRACT

The charging strategy in the electric vehicle routing problem at present is usually full charge, which will bring about the problems that the charging time is too inflexibility and the customer’s time windows are hard to be met. Therefore, an improved charging strategy is proposed, in which, the vehicle charging time, the charging station and the charging power are taken as decision variables. With the objective of minimizing the total operation costs, a mixed integer linear programming model is established. Then, a hybrid heuristic algorithm based on the combination of self-adaptive genetic algorithm and simulated annealing algorithm is proposed. Finally, the validity and practicability of the model and the algorithm are proved by a large number of computational examples and sensitivity analyses.

Keywords:Charging Strategy, Partial Charging, Electric Vehicle Routing Problem, Genetic Algorithm, Simulated Annealing Algorithm

改进充电策略下电动车辆路径问题建模与仿真

贾永基,陈 媚,李 嘉

东华大学,旭日工商管理学院,上海

收稿日期:2020年2月6日;录用日期:2020年2月21日;发布日期:2020年2月28日

摘 要

目前电动车辆路径问题中的充电策略通常是完全充电策略,会带来充电时间不灵活,难以满足客户时间窗等问题。针对该问题,提出了改进充电策略,将车辆充电时间点、充电站点和充电电量作为决策变量,以电动车辆运营总成本最小为目标函数,建立了混合整数规划模型,并提出了自适应遗传算法融合模拟退火算法的混合启发式求解算法。最后,算例仿真测试和灵敏度分析结果验证了模型和算法的有效性和实用性。

关键词 :充电策略,部分充电,电动车辆路径问题,遗传算法,模拟退火算法

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

电动车辆具有能源利用效率高、零污染、低噪音等优点,是全球汽车产业的发展方向,更是我国国家战略框架下交通运输行业未来发展的重要选择。与传统燃油汽车相比,电动车辆具有续航里程短、充电时间长、且充电设施少等特点。为了提高电动车辆的推广效率,降低电动车辆运营成本,必须在路径规划时考虑充电策略。因此,针对电动车辆充电策略的研究,成为当前电动车辆运营领域的研究热点。

充电策略包括充电时间决策、充电站决策和充电电量决策三部分内容。现有的充电策略通常是完全充电策略,即在电池电量无法续航至下一客户点时才就近访问充电站,并充至满电状态。完全充电策略会导致车辆充电时间不灵活,难以满足客户时间窗等电动车辆用户比较关注的问题。

目前,考虑充电策略的电动车辆路径问题的研究还处于起步阶段,相关文献还较少。有些学者着重于设置决策变量进行了电动车充电策略研究,文献 [1] 运用节约算法对电动车辆充电策略进行研究,建立了以行驶距离最小为目标的数学模型。文献 [2] 在电动车辆路径问题中考虑客户服务时间窗,并提出了求解该问题的变邻域搜索和禁忌搜索相结合的混合启发式算法。文献 [3] 放松了完全充电限制而允许部分充电,使得车辆的充电时间更灵活,因而在实际问题中更实用。文献 [4] 研究了考虑部分充电的带时间窗电动车辆选址–路径规划问题,同时考虑电动车辆的路径规划和充电站的选址决策。此外,还有些学者对充电策略的算法进行创新,文献 [5] 将车辆在充电站的充电水平设置为变量,运用模拟退火算法对不同规模的算例测试,验证了其模型与算法的有效性。文献 [6] 提出了4种充电策略,并对各充电策略下的车辆路径进行了对比分析。文献 [7] 考虑充电策略与电池损耗对运营成本的影响,并提出了求解该模型的自适应大邻域搜素算法。

本文研究的电动车辆路径问题基于改进充电策略,即每次只充需要的电量,从而可以更加灵活地安排充电时间,更好地满足客户时间窗。将车辆充电时间点、充电站点和充电电量作为决策变量,以由车辆使用成本、电量消耗成本、充电时间成本和违背时间窗惩罚成本所组成的运营总成本最小为目标函数,建立了混合整数规划模型,并提出了求解该问题的自适应遗传算法融合模拟退火算法的混合算法。

2. 问题描述与数学模型

2.1. 问题描述与假设

改进充电策略下电动车辆路径问题可描述为:电动车辆从车库出发,满足装载容量、客户时间窗等基本约束的前提下,还需满足里程约束、电量约束等电动车辆特有的约束,确定电动车辆的行驶路径及服务客户的先后顺序,使运营总成本最小。电动车辆在服务客户过程中需要访问充电站以延长续驶里程,因此在对电动车辆路径规划时必须考虑充电策略问题。

改进充电策略的一个典型示例如图1所示,包括1个车库(点0)、9个待服务客户点(C1-C9),3辆电动车辆(EV1-EV3),每个客户有指定的货物需求量和服务时间窗。从图1中可以看出,由于电动车辆续航里程有限,因而在服务过程中需要充电才能完成服务任务并返回车库。制定合理的充电策略,即决策充电时间点、充电站点和充电量对于确定最优服务路径、降低运营成本和满足客户时间窗十分关键。

Figure 1. Typical example of electric vehicle routing problem

图1. 电动车辆路径问题典型示例

建立数学模型之前,做以下假设:

(1) 电动车辆为单一类型,具有相同的最大载荷量和电池容量;

(2) 车辆的耗电速率、充电速率以及行驶速度已知且保持不变;

(3) 电动车辆从车库出发时其电量为满电状态;

(4) 电动车辆在服务客户时不消耗电量,并且每个客户的服务时间相同;

(5) 充电站没有容量限制,不考虑排队情况。

2.2. 决策变量与参数

x i j k z i k 为0-1决策变量,车辆k经过弧(i,j)时 x i j k 为1,否则为0;车辆k在充电站i充电时 z i k 为1,否则为0。模型其余变量和参数说明如表1所示。

Table 1. Variables and parameters

表1. 变量与参数说明

2.3. 混合整数规划模型

电动车辆路径问题的基础模型如下:

min λ 1 j N F k K x o j k + λ 2 i V j V , i j k K t i j x i j k + λ 3 i F t i z i k + λ 4 i N max { e i τ i , τ i l i , 0 } (1)

s.t

k K j V , j i x i j k = 1 , i N (2)

i v , i j x i j k i v , i j x j i k = 0 , j N F , k K (3)

τ i + ( t i j + s i ) x i j k l 0 ( 1 x i j k ) τ j , i N { 0 } , j V , i j , k K (4)

u j u i q i x i j k + Q ( 1 x i j k ) , i V , j V , i j , k K (5)

0 u i Q , i { 0 } N (6)

y j y i h d i j x i j k + B ( 1 x i j k ) , i N , j V , i j , k K (7)

0 y i B , i { 0 } F (8)

x i j k { 0 , 1 } , i V , j V , i j , k K (9)

其中,式(1)为目标函数C,表示运营总成本最小,包括车辆使用成本、电量消耗成本、充电时间成本和违背时间窗惩罚成本;式(2)表示每个顾客由一辆车且仅由一辆车服务;式(3)为流量守恒条件;式(4)为访问完客户i后到达客户j点的时间关系;式(5)为车辆访问i点到达j点的车辆剩余货物量变化;式(6)保证车辆从车库出发时的货物量不超过装载容量限制;式(7)表示车辆从客户点i到达j点的电量变化;式(8)表示车辆从车库出发时电量不超过最大电量;式(9)表示 x i j k 为0~1变量。

在电动车辆路径问题基础模型的基础上,改进充电策略主要体现在充电时间点、充电站点和充电电量的决策方式上。首先,允许部分充电,即车辆根据实际情况充入所需电量,而不是充满;其次,在决策充电时间点的时候引入安全电量,当车辆k服务当前客户点i后,会判断服务下一个客户点时的剩余电量是否低于安全电量,如果低于安全电量,则车辆需要访问充电站;最后,在决策充电站点时,采用最小绕路距离原则。改进充电策略的约束条件如下:

Y i B , i F (10)

y i Y i , i F (11)

τ i + t i j x i j k + ( Y i y i ) / g l 0 ( 1 x i j k ) τ j , i V , j V , i j , k K (12)

y j Y i h d i j x i j k + B ( 1 x i j k ) , i F , j V , i j , k K (13)

r B y i , i N (14)

z i k { 0 , 1 } , i F , k K (15)

其中,式(10)表示充电后的电量不能超过电池容量;式(11)表示车辆k充电后的电量不小于当前电量;式(12)表示车辆k在充电站i充电后到客户j的时间变化;式(13)表示车辆k在充电站i充电后到客户j的电量变化;式(14)表示车辆k到达客户i时的电量须大于等于安全电量;式(15)表示 z i k 为0~1变量。

3. 自适应遗传算法融合模拟退火算法的设计

本文设计了以自适应遗传算法为基础,结合模拟退火的混合启发式求解算法。

根据模型的特点,编码方式采用自然数编码,包括1个车库,n个客户点,m个充电站,k辆电动车辆。

3.1. 构造初始解

利用贪心算法构建初始可行解,步骤如下:

步骤1:对于每个客户点根据时间窗的先后顺序以及与车库的距离确定初始解。构造成本函数

C 1 = λ 2 i V j V , i j k K t i j x i j k + λ 4 i N max { e i τ i , τ i l i , 0 } (16)

选择服务成本最小的点为当前服务点,然后再以该点为基点,依次插入客户点直至所有的客户点都被服务,从而生成客户服务序列,并在开始和结尾处插入车库0,表示车辆从车库出发,服务完所有客户后,最后又返回车库。一个典型的初始解(染色体)如图2所示。

Figure 2. Schematic diagram of the initial solution

图2. 初始解示意图

步骤2:按染色体客户顺序计算客户累计货物需求量 i = 1 n q i ,若 i = 1 e q i Q i = 1 e + 1 q i Q ,在客户e和e+1之间插入车库0;重复该步骤,直到所有车辆路径都满足容量约束;

步骤3:当车辆k服务客户点i后,判断服务下一个客户点i + 1时的剩余电量是否低于安全电量,即是否满足

y i h d i , i + 1 r B , i N (17)

若不满足,则需要插入充电站,通过计算所有充电站的插入成本,选择插入成本最低的充电站p,即

p = arg min h ( d i m + d m ( i + 1 ) ) , m F , i N (18)

步骤4:插入充电站p后,计算车辆服务所有剩余客户并返回车库所需电量 S p ,即车辆在充电站p的充电电量;如果 S p > B ,则将电池充至满电状态。

步骤5:重复步骤3和4,直至所有路径都满足电量约束。

3.2. 算法设计

本文选择适应度函数为目标函数的倒数,即目标函数值越小,染色体适应度函数值越大,被选的概率越大,即

f = 1 / C (19

为了克服遗传算法的“早熟”问题,引入自适应调整机制对遗传算法的交叉和变异算子进行改进,自适应机制通过调整交叉概率( P c )和变异概率( P m )来避免算法的早熟。对于适应度值高于平均值的个体,对应较低的 P c P m ,使其优秀基因得以进入下一代;对于适应度值低于平均值的个体,对应较高的 P c P m ,使其被淘汰或者在交叉变异的过程中对该个体进行基因重组。

本文交叉算子为双点交叉,即在两个父代染色体上,随机选择两个位置,通过交换两个位置之间的基因串,得到新的染色体。变异算子为对换变异,即随机选择染色体中两个非0的基因位,将其进行对换得到新的染色体。交叉概率和变异概率的自适应调整公式分别为:

P c = { α 1 ( f max f ) f max f avg , f f avg α 2 f < f avg (20)

P m = { α 3 ( f max f ) f max f avg , f f avg α 4 f < f avg (21)

其中 f max 是最大适应度值, f avg 是平均适应度值,f为个体适应度值, α 1 , α 2 , α 3 , α 4 在(0, 1)之间取值。

对于新的种群,使用模拟退火中的Metropolis准则对解进行选择和更新。若在温度T时的能量函数为 f ( x ) ,则Metropolis准则表示为:

P = { 1 , f ( x new ) < f ( x now ) exp ( f ( x new ) f ( x now ) T ) , f ( x new ) f ( x now ) (22)

3.3. 算法流程

本文设计的自适应遗传算法融合模拟退火算法(Adaptive genetic algorithm and Simulated annealing algorithm,以下简称AGA/SA),一方面利用AGA的多样性和较强的局部搜索能力弥补了SA搜索方式单一、搜索精度差的不足;另一方面利用SA较强的全局搜索能力弥补了AGA易陷入局部最优的不足,增强了算法的全局搜索能力。

AGA/SA算法流程图如图3所示,步骤如下:

步骤1:参数初始化,设置当前温度下的种群最大迭代次数Gmax、初始温度T0和结束温度Tend

步骤2:采用贪心算法生成初始种群s,设置当前种群S = s;

步骤3:计算当前种群S的适应度值 f ( s ) ,根据公式(20)和(21)进行自适应的交叉运算和变异运算,得到新的种群v,并计算其适应度值 f ( v )

步骤4:计算 Δ f = f ( v ) f ( s ) ,并且判断其是否小于0,若小于0,则接受当前解,并进行更新;若大于等于0,则根据Metropolis准则以一定概率接受当前解;

步骤5:如果当前温度下的种群迭代次数 ,则迭代次数加1,返回步骤3;

步骤6:判断当前温度T是否小于Tend,如果否,则以 T = β T 降温,重置当前温度下的迭代次数G,返回步骤3;如果是,则输出群体中最优个体,算法终止。

Figure 3. Algorithm flow chart

图3. 算法流程图

4. 算例仿真测试

本文构建了一个包括1个车库(编码0)、20个客户点(编码1-20)、5个充电站(编码21-25)的测试算例,所有点的坐标及客户时间窗和货物需求量如表2所示。设每个客户点的服务时间为10 min。电动汽车的相关参数为:最大载重量Q = 2400 kg,电池最大容量B = 50 kw·h,电池剩余电量安全系数r = 0.2,电池的充电速率g = 1 kw·h/min。单位车辆使用成本 = 200元/辆,单位耗电量成本 = 0.6元/kw·h,单位充电时间成本 = 0.3/min,单位时间窗惩罚成本 = 0.1/min。算法中的相关参数为:种群规模P = 100,当前温度下的最大迭代次数 = 100,初始温度 = 1000,温度衰减因子 = 0.975,最低温度为 = 0.1。程序采用Matlab R2016a编写,在Intel i7 8500U,8 G内存的笔记本电脑上运行。

Table 2. Test data

表2. 测试实例数据

4.1. 改进充电策略与完全充电策略仿真对比分析

利用AGA/SA分别对完全充电策略和改进充电策略下的电动车辆路径问题进行求解。完全充电策略下的车辆最优行驶路径如图4所示,其车辆路径、访问客户点和充电站的顺序、访问时间及电池电量变化等,如表3所示。在同样的客户需求和电动车辆条件下,改进充电策略下的电动车辆最优行驶路径如图5所示,其车辆路径、访问客户点和充电站的顺序、访问时间及电池电量变化等,如表4所示。

Figure 4. Vehicle optimal path under full charge strategy

图4. 完全充电策略下的车辆最优路径

Figure 5. Vehicle optimal path under improved charging strategy

图5. 改进充电策略下的车辆最优路径

Table 3. Distribution path and power change table for each vehicle

表3. 每一车辆配送路径以及电量变化表

Table 4. Distribution path and power change table for each vehicle

表4. 每一车辆配送路径及电量变化表

完全充电策略和改进充电策略下的电动车辆路径问题的AGA/SA算法的仿真测试结果如图6所示。两种充电策略从配送时间、惩罚时间、消耗电量、使用车辆数、行驶距离以及总成本的对比分析,如表5所示。从中可以看出,改进充电策略是优于完全充电策略的。

Figure 6. Comparison of Improved charging strategy and full charging strategy test results

图6. 改进充电策略和完全充电策略仿真测试对比

Table 5. Comparison of improved charging strategy and full charging strategy test results

表5. 改进充电策略和完全充电策略仿真测试结果对比

4.2. AGA/SA与遗传算法仿真对比分析

分别使用AGA/SA和遗传算法求解改进充电策略下的电动车辆路径问题,仿真测试结果如图7所示。从中可以看出,AGA/SA的求解结果更优。

4.3. 灵敏度分析

在改进充电策略中,安全电量的选择尤为重要,若设置过低,会增加电动车辆无法抵达充电站的风险,若设置过高,会导致电动车辆频繁访问充电站,增加不必要的充电成本。对安全电量的灵敏度分析结果如图8所示,随着电量警戒系数r的增大,总成本随之增大,但当r ≤ 0.2时,总成本受r的影响不大。因此,本文选择0.2作为安全电量警戒系数。

Figure 7. Comparison of AGA/SA and genetic algorithm test result

图7. AGA/SA与遗传算法仿真测试对比

Figure 8. Sensitivity analysis of electric vehicle safety

图8. 电动车辆安全电量灵敏度分析

5. 总结

本文将包括充电时间决策、充电站决策和充电电量决策的改进充电策略加入电动车辆路径问题的基础模型,允许部分充电并引入安全电量,以包括车辆使用成本、电量消耗成本、充电时间成本和违背时间窗惩罚成本所组成的总成本最小为优化目标,建立了混合整数规划模型,并设计了以自适应遗传算法为基础,结合模拟退火算法的混合启发式求解算法。首先,对改进充电策略和完全充电策略进行了对比分析,测试结果表明改进充电策略下的运营总成本降低了7.2%,验证了改进充电策略的优势。然后设计了算例对AGA/SA和GA进行了对比测试,验证了AGA/SA的求解结果优于GA,虽然求解速度相对较慢,但在可接受的范围内。

改进充电策略可以应用于电动车辆的物流配送、公共交通和共享租赁等领域,能有效解决电动车辆充电时间不灵活、难以满足客户时间窗和电动车辆用户“充电焦虑”等完全充电策略所无法解决的现实问题。

基金项目

上海市哲学社会科学规划基金项目(2018BGL018)。

文章引用

贾永基,陈 媚,李 嘉. 改进充电策略下电动车辆路径问题建模与仿真
Modeling and Simulation on Electric Vehicle Routing Problem with Improved Charging Strategy[J]. 建模与仿真, 2020, 09(01): 65-76. https://doi.org/10.12677/MOS.2020.91008

参考文献

  1. 1. Erdoğan, S. and Miller-Hooks, E. (2011) A Green Vehicle Routing Problem. Transportation Research Part E, 48, 100-114. https://doi.org/10.1016/j.tre.2011.08.001

  2. 2. Chneider, M., Stenger, A. and Goeke, D. (2014) The Electric Vehicle Routing Problem with Time Windows and Recharging Stations. Transportation Science, 48, 500-520. https://doi.org/10.1287/trsc.2013.0490

  3. 3. Keskin, M. and Çatay, B. (2016) Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows. Transportation Research Part C: Emerging Technologies, 65, 111-127. https://doi.org/10.1016/j.trc.2016.01.013

  4. 4. Schiffer, M. and Walther, G. (2017) The Electric Location Routing Problem with Time Windows and Partial Recharging. European Journal of Operational Research, 260, 995-1013. https://doi.org/10.1016/j.ejor.2017.01.011

  5. 5. Felipe, Á., Ortuno, M.T., Righini, G., et al. (2014) A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges. Transportation Research Part E: Logistics and Transportation Review, 71, 111-128. https://doi.org/10.1016/j.tre.2014.09.003

  6. 6. Desaulniers, G., Errico, F., Irnich, S., et al. (2016) Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows. Operations Research, 64, 1388-1405. https://doi.org/10.1287/opre.2016.1535

  7. 7. 郭放, 杨珺, 杨超. 考虑充电策略与电池损耗的电动汽车路径优化问题研究[J]. 中国管理科学, 2018, 26(9): 106-118.

期刊菜单