基于非线性混合充电策略的电动车物流配送路径规划模型

汪山颖; 靳文舟

doi:10.3963/j.jssn.1674-4861.2022.02.014

基于非线性混合充电策略的电动车物流配送路径规划模型

doi: 10.3963/j.jssn.1674-4861.2022.02.014

汪山颖,
靳文舟^,

华南理工大学土木与交通学院广州 510630

基金项目:

国家自然科学基金项目 52072128

详细信息

作者简介:
汪山颖（1998—），硕士研究生. 研究方向：交通规划与管理. E-mail：1005319695@qq.com

通讯作者:
靳文舟（1960—），博士，教授. 研究方向：交通规划与管理、需求响应公交调度等. E-mail：ctwzhjin@scut.edu.cn

中图分类号: TU4-9
计量
- 文章访问数: 1105
- HTML全文浏览量: 394
- PDF下载量: 88
- 被引次数: 0
出版历程
- 收稿日期: 2021-10-12
- 网络出版日期: 2022-05-18

Routing of Electronic Automobileswith Hybrid Nonlinear Charging Strategy for Logistics Distribution

WANG Shanying,
JIN Wenzhou^,

School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510630, Guangdong, China

摘要

摘要: 经典的车辆路径规划问题（VRP）通常只考虑载重约束和节点约束。随着电动物流车和充电站的增多，考虑充电时间与充电量成非线性关系的电动车路径规划问题（EVRP-NL）的研究在物流配送中也有着非常重要的意义。通过分段计算充电速率简化了以往对充电时间和充电量的非线性充电函数拟合方法，并对拟合函数进行了线性化处理。针对电动车物流配送的特性，构建了以最小化车辆固定成本、行驶成本、快充成本和换电成本之和为目标函数，考虑节点约束、载重约束、电量约束、时间窗约束及充电函数线性化约束的EVRP-NL模型，提出了由换电和非线性快充构成的非线性混合充电策略，其中非线性快充是考虑充电时间与充电量的非线性关系的快充方式。针对模拟算例的计算结果验证了模型的可行性和普适性。针对实际物流算例的计算结果表明，考虑充电时间和充电量非线性关系的混合充电模型可减少35%的充电时间和69%的充电成本，非线性混合充电策略具有显著优越性。对快充电价和换电电价进行控制变量的灵敏度分析后发现, 使用非线性混合充电策略时，随着电价升高，充电方式从电价升高的充电方式转变为电价稳定的充电方式，且电价升高至一定程度，充电方式和充电成本均不再变化。
- 交通规划与管理 /
- 混合充电策略 /
- 电动车路径规划 /
- 非线性充电模型 /
- 物流配送
Abstract: The classical vehicle routing problems (VRP) usually only consider load constraints and node constraints. As theshare of electric automobileswithin the road transportation fleet increases, the routing problem of suchelectric automobilesshowing anonlinear charging property (EVRP-NL) is of great implication to urban logistics distribution. The existing nonlinear charging functionsof charging time and charging amountarelinearized, and fitting methods are simplified by calculating charging rate sectionally.According to the characteristics of logistics distribution served by electric automobiles, an extended model of EVRP-NL with load, node, power and time window constraints and linearizedconditions of charging functionsisdeveloped, which aims to minimize the summation of fixed cost, operating cost, fast charging cost, and battery replacement cost.The extend modelachieves the nonlinear hybrid charging strategy consisting of power replacement and a fast charge method considering the nonlinear relationship between charging time and charging amount, named nonlinear fast charge.Theresults of simulationshow that the model is feasible and universal in different types of data.The results of actual logisticsdatashow that nonlinear hybrid charge can reduce 35% of charging time and 69% of charging cost, and therefore prove that nonlinear hybrid charge strategy has much more significant advantages than the othermethods.The sensitivity analysesagainstdifferent prices of fast charging and battery swapping show that the hybrid charging strategy is more inclined to the mode with a cheaper price.When the price of electricity rises to a certain level, neither charging mode nor its cost changes anymore.
- traffic planning and management /
- hybrid charging strategy /
- EVRP /
- nonlinear charging model /
- logistics distribution

HTML全文

图 1 电动车物流配送路径规划示意图

Figure 1. Schematic diagram of electric vehicle logistics distribution path planning

下载: 全尺寸图片幻灯片

图 2 电动车电池充电过程示意图

Figure 2. Charging process of electric vehicle battery

下载: 全尺寸图片幻灯片

图 3 分段函数拟合充电函数

Figure 3. Fitting charging function with piecewise function

下载: 全尺寸图片幻灯片

图 4 模拟算例配送路径示意图

Figure 4. Schematic diagram of distribution path of simulation example

下载: 全尺寸图片幻灯片

图 5 实际算例各点位置示意图

Figure 5. Location diagram of each point in the actual examples

下载: 全尺寸图片幻灯片

图 6 电价变化对充电电量的影响

Figure 6. Influence of electricity price change on charging power

下载: 全尺寸图片幻灯片

图 7 电价变化对充电成本的影响

Figure 7. Influence of electricity price change on charging cost

下载: 全尺寸图片幻灯片

图 8 不同充电策略的充电成本比较

Figure 8. Comparison of charging costs of different charging strategies

下载: 全尺寸图片幻灯片

图 9 不同充电策略的充电时间比较

Figure 9. Comparison of charging time of different charging strategies

下载: 全尺寸图片幻灯片

表 1 模型符号说明

Table 1. Model symbol description

集合	符号说明	参数	符号说明	参数	符号说明	变量	符号说明
V	客户点集合	d_ij /km	i点到j点的距离	c_f /元	单次使用车辆固定成本	x_ijk	当车辆k经过路段（i,j)时，x_ijk = 1，否则x_ijk = 0
F	充电站集合	t_ij/min	i点到j点的行驶时间	C_t /元	单位距离行驶成本	y_ik	当车辆k在充电站i选择换电时，y_ik = 1，否则y_ik = 0
S	配送中心	t_s /min	单次换电时间	p_τ /元	单位电量的快充成本	Z_ik	当车辆k在充电站i选择快充时，z_ik = 1，否则z_ik = 0
O	S ∪ F	r (kW · h/min)	电量消耗率	c_s /元	单次换电成本	ea_ik /(kW · h)	车辆k到达节点i时的电量，i ∈ P
D	F ∪ V	q_ik	车辆k在i点配送的货物量	[e_i,l_i/min	客户点i的时间窗	el_ik/(kW · h)	车辆k离开节点i时的电量，i ∈ P
E	s ∪ V	D_i/kg	客户点i的需求量	[e_s，l_s]/min	配送中心的时间窗	ta_ik/min	车辆k到达节点i时的时间，i ∈ P
P	S ∪ F ∪ V	v_s/(min/kg)	单位需求量服务速度	e(t)	电量随充电时间变化的分段函数	tl_ik/min	车辆k离开节点i时的时间，i ∈ P
K	电动汽车集合	C/kg	车辆的最大载重	M	e(t)端点编号的集合，M = {0, 1，…，n}	Z_in	0-1变量，辅助限定α_in的值
A_ij	路段（i，j)集合	Q/(kW · h)	车辆的最大电容	A_n	M中端点的横坐标，n ∈ M	W_in	0-1变量，辅助限定 λ_in 的值
				B_n	M中端点的纵坐标，n ∈ M	αⁱⁿ	分段函数e(t)线性化的系数，αⁱⁿ[0, 1]，n ∈ M
						λ_in	分段函数e(t)线性化的系数，λ_in ∈ [0, 1]，n ∈ M

下载: 导出CSV

表 2 相关参数设置

Table 2. Related parameter settings

参数	取值
d_ij /km	$\sqrt[2]{\left(y_{j}-y_{i}\right)^{2}-\left(x_{j}-x_{i}\right)^{2}}$
t_ij /min	$\frac{d_{i j}}{v}, \mathrm{v}=35 / \mathrm{km} / \mathrm{h}$
t_s /min	快充满充时间的10%
Q/ (r /km)	200
v_s/(kg/min)	1
Q/(kW · h)	80
ρ_τ /元	0.6
c_f /元	100
c_t元	0.75
C^s/元	快充的满充费用

下载: 导出CSV

表 3 每种算例的时间参数

Table 3. Time parameters of each example

算例分类	时间比	换电时间/min	最大电容/(kW · h)	耗电率/(kW · h/min)	服务速度/(kg/min)	行驶速度/(km/h)
RC₁₀₁	3.50:1	3	24	0.12	0.3	123
R₁₀₁	3.652:1	3	24	0.12	0.3	128
C₁₀₁	0.680:1	15	120	0.6	1.5	24
R₂₀₁	0.840: 1	12	96	0.48	1.2	29
C₂₀₁	0.248: 1	40	320	1.6	4	7
RC₂₀₁	0.875: 1	11	88	0.44	1.1	31

下载: 导出CSV

表 4 模拟算例求解结果

Table 4. The solution results of simulation examples

算例名称	成本/元	运算时间/h	Gap/%	充电总量/(kW · h)	充电时间/min	快充次数	换电次数
RC₁₀₁	717	0.44	0	8.01	15.88	1	0
R₁₀₁	680	0.009	0	0.95	1.89	1	0
C₁₀₁	876	8	3.64	138.61	108	2	1
R₂₀₁	748	8	1.45	3.51	7.02	1	0
C₂₀₁	814	8	7.26	328.05	56.11	2	1
RC₂₀₁	902	8	5.18	11.2	56.02	2	0

下载: 导出CSV

表 5 模拟算例配送路径

Table 5. Distribution path of simulation examples

路径序号	节点序号
R₁	25-9-25
R₂	25-16-25
R₃	25-13-19-0-20-5-8-17-4-18-11-6-3-7-25
R₄	25-14-1-2-12-10-15-25

下载: 导出CSV

表 6 实际算例基础数据

Table 6. The basic data of actual examples

节点编号	需求量/kg	时间窗/min	节点编号	需求量/kg	时间窗/min
0	159	[30, 180]	15	153	[150, 420]
1	140	[90, 180]	16	172	[120, 390]
2	142	[60, 21]	17	178	[120, 390]
3	146	[0, 240]	18	148	[45，330
4	142	[30, 330]	19	163	[30, 330]
5	153	[30, 150]	20	170	[120, 390]
6	151	[90, 360]	21	161	[90, 330]
7	166	[30, 300]	22	151	[90, 330]
8	147	[150, 390]	23	140	[150, 330]
9	140	[60, 330]	24	143	[120, 390]
10	158	[60, 330]	25	0	[0, 840]
11	151	[60, 240]	26	0	[0, 840]
12	166	[90, 390]	27	0	[0, 840]
13	170	[60, 330]	28	0	[0, 840]
14	161	[150, 420]

下载: 导出CSV

表 7 电价组别

Table 7. electricity price group

电价组号	c_s /元	ρ_τ /元	电价组号	c_s /元	ρ_τ /元
1		0.2	10	10
2		0.3	11	15
3		0.4	12	20
4		0.5	13	25
5	35	0.6	14	30	0.6
6		0.7	15	35
7		0.8	16	40
8		0.9	17	45
9		1.0	18	50

下载: 导出CSV

参考文献(21)

[1]	CAZZOLA P, GORNER M, SCHUITMAKER R, et al. Global EV outlook 2018: Towards cross modal electrification[M]. Paris: International Energy Agency, 2018.
[2]	QIN H, SU X X, REN T, et al. A review on the electric vehi-cle routing problems: Variants and algorithms[J]. Frontiers of Engineering Management, 2021, 8(3): 370-389 doi: 10.1007/s42524-021-0157-1
[3]	SCHNEIDER M, STENGER A, GOEKE D, et al. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520 doi: 10.1287/trsc.2013.0490
[4]	蔡银怡. 考虑充电策略和非线性能量消耗的电动车配送路径规划研究[D]. 广州: 华南理工大学, 2020. CAI Y Y. Research on electric vehicle routing problem with charging strategy and nonlinear energy consumption[D]. Guangzhou: South China University of Technology, 2020. (in Chinese)
[5]	VERMA A. Electric vehicle routing problem with time windows, recharging stations and battery swapping stations[J]. EURO Journal on Transportation and Logistics, 2018, 7(4): 415-451. doi: 10.1007/s13676-018-0136-9
[6]	KESKIN M, ÇATAY B. Partial recharge strategies for the elec-tric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65(4): 111-127
[7]	李军, 唐晓宇, 赵长相. 基于充电策略的纯电动公交车辆调度优化[J]. 重庆交通大学学报(自然科学版), 2015, 34(4): 107-112. https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201504021.htm LI J, TANG X Y, ZHAO C X. Dispatch optimization of pure electric buses based on charging strategy[J]. Journal of Chongqing Jiaotong University(Natural Science), 2015, 34(4): 107-112. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201504021.htm
[8]	UGUR B, MEHMET E. Optimization of electric vehicle recharge schedule and routing problem with time windows and partial recharge: A comparative study for an urban logistics fleet[J]. Sustainable Cities and Society, 2021, 70(7): 102883.
[9]	PENNA P, AFSAR H, PRINS C, et al. A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations[J]. IFAC Papers OnLine, 2016, 49(12): 955-960. doi: 10.1016/j.ifacol.2016.07.899
[10]	MACRINA G, DI P P L, GUERRIERO F, et al. The green mixed fleet vehicle routing problem with partial battery recharging and time windows[J]. Computers & Operations Research, 2019, 101(1): 183-199.
[11]	揭婉晨, 杨珺, 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践, 2016, 36(7): 1795-1805. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201607017.htm JIE W C, YANG J, YANG C. Research on branch pricing algorithm for multi model electric vehicle routing problem[J]. System engineering theory and practice, 2016, 36(7): 1795-1805. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201607017.htm
[12]	AMIN C, JULIO M, MUSTAPHA O, et al. Vehicle routing problem for reverse logistics of End-of-Life Vehicles (ELVs)[J]. Waste Management, 2020, 120(1): 209-220
[13]	蒋珊珊. 考虑路段限行时间窗与灵活子路径的车辆径程优化问题研究[D]. 北京: 北京交通大学, 2020. JIANG S S. Research on vehicle routing optimization considering section restriction time window and flexible sub path[D]. Beijing: Beijing Jiaotong University, 2020. (in Chinese)
[14]	MONTOYA A, GUERET C, MENDOZA J et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B: Methodological, 2017, 103(9): 87-110
[15]	FROGER A, MENDOZA J, JABALI O, et al. Improved for-mulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[J]. Computers & Operations Research, 2019, 104(10): 256-294
[16]	ZUO X R, XIAO Y Y, YOU M, et al. A new formulation of the electric vehicle routing problem with time windows con-sidering concave nonlinear charging function[J]. Journal of Cleaner Production, 2019, 236(1): 1-18.
[17]	王美芹. 考虑非线性电池折旧的电动车路径规划问题[D]. 北京: 清华大学, 2018. WANG M Q. The electric vehicle routing problem considering nonlinear battery depreciation[D]. Beijing: Tsinghua University, 2018. (in Chinese)
[18]	UHRING M, WEI L, SURIYAH M, et al. E-mobility in car parks-guidelines for charging infrastructure expansion planning and operation based on stochastic simulations[C]. 28^th International Electric Vehicle Symposium and Exhibition, Goyang, Korea: KINTEX, 2015.
[19]	WANG H F, CHEN Y Y. A genetic algorithm for the simulta-neous delivery and pickup problems with time window[J]. Computers & Industrial Engineering, 2011, 62(1): 122-149
[20]	宋稚雅. 基于纯电动物流车的城市配送车辆路径问题研究[D]. 北京: 北京交通大学, 2019. SONG Z Y. Research on urban distribution vehicle routing problem based on pure electric logistics vehicle[D]. Beijing: Beijing Jiaotong University, 2019. (in Chinese)
[21]	郭放, 杨珺, 杨超. 考虑充电策略与电池损耗的电动汽车路径优化问题研究[J]. 中国管理科学, 2018, 26(9): 106-118. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK201809011.htm GUO F, YANG J, YANG C. Study on the electric vehicle routing problem in the present of charging strategy and battery consumption[J]. Chinese Journal of Management Science, 2018, 26(9): 106-118. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK201809011.htm