考虑非线性能耗的时间依赖型电动车辆路径模型及改进的鲸鱼优化算法

doi:10.16381/j.cnki.issn1003-207x.2023.1103

Abstract

Abstract:

In recent years， Electric Vehicles （EVs） have been widely spread and used in logistic distribution. Due to the fact that EV route planning is directed associated with time-varying properties of energy consumption and traffic conditions， the Time Dependent Electric Vehicle Routing Problem with Nonlinear Energy Consumption （TDEVRPNEC） deserves deeper study. The TDEVRPNEC discussed in this paper involves set constraints， including （1） distribution center locations，（2） a homogeneous EV fleet，（3） customers' number， locations， needs， time windows， and （4） time-varying speeds on several time sections. The optimal plan is expected to realize the goal of total cost minimization under the premise of satisfying customer' expectations， i.e.， needs and time windows， by means of reasonable departure time choice， optimal charging strategy and vehicle routing optimization. Specifically， the total cost includes energy consumption cost， charging time cost， usage-based time cost and fixed dispatch cost. In the design， a specific energy consumption rate function is firstly applied to calculate total rate of energy consumption during trips. And then， a partial charging strategy is proposed with special consideration of the influence of time-varying speed on charging capacity. Based on the fact of time-varying traffic conditions on different road sections， a road segment-based vehicle travel time calculation method is proposed. Finally， a TDEVRPNEC optimization model is constructed. In order to solve the TDEVRPNEC model， an Improved Whale Optimization Algorithm （IWOA） is designed. The basic idea of the algorithm can be described as follows. （1） The crossover techniques in genetic algorithm is introduced to derive a refined position updating formula in the whale optimization algorithm， with application to the solution of discrete problems. （2） The greedy algorithm is used to construct initial solution for shortening the computing time of optimization. （3） The scheduling of vehicle departure times is proposed to avoid traffic congestion. （4） A very important place for the design of operators， i.e. reversal operator， energy exchange operator and charging station insertion operator， is provided to expand the solution space， avoid local optima and improve global search capability. Experimental simulation results show the following. From a perspective of model， the TDEVRPNEC model is verified to achieve multi-objective balancing among logistics cost， energy consumption， and travel time. From a perspective of strategy， the partial charging strategy is tested effective to shorten charging time， save logistics cost and reduce the energy consumption； the scheduling of vehicle departure times can contribute to traffic congestion avoidance and high logistics efficiency. From a perspective of algorithm， the proposed IWOA is confirmed to achieve fast convergence， better generalizability and optimality-seeking ability.

Key words: EVRP, nonlinear energy consumption, time dependent, IWOA

CLC Number:

F252

Xiancheng Zhou,Songming Li,Li Wang, et al. Research on Time Dependent Electric Vehicle Routing Model with Nonlinear Energy Consumption and an Improved Whale Optimization Algorithm[J]. Chinese Journal of Management Science, 2026, 34(3): 214-225.

Figures/Tables 12

符号	表示含义
0	作为起点的配送中心
$n + 1$	作为终点的虚拟配送中心
$N$	顾客点的集合， $N = {1,2, ⋯, n}$
$S$	充电站集合， $S = {1,2, ⋯, s}$
$A$	起点、顾客点、充电站与终点集合， $A = 0 ⋃ N ⋃ S ⋃ {n + 1}$
$A 1$	起点、顾客点与充电站集合， $A 1 = 0 ⋃ N ⋃ S$
$A 2$	顾客点、充电站与终点集合， $A 2 = N ⋃ S ⋃ n + 1$
$A 3$	顾客点与充电站集合, $A 3 = N ⋃ S$
$K$	配送车辆的集合， $K = {1,2, ⋯, K'}$
$Q$	电动车最大载重
$C$	电动车电池容量
$q i$	顾客点 $i$ 的需求量
$[b i, e i]$	顾客点 $i$ 的服务时间窗
$H$	时间段 $h$ 的集合, $H = 1, 2, ⋯, u$
$v i j h$	车辆在时间段 $h$ 行驶在路段 $(i, j)$ 上的速度
$t i k 1$	车辆 $k$ 到达节点 $i$ 的时刻， $i ∈ A 2$
$t i k 2$	车辆 $k$ 离开节点 $i$ 的时刻， $i ∈ A 1$
$q i k 1$	车辆 $k$ 到达顾客点 $i$ 时的载重
$q i k 2$	车辆 $k$ 离开顾客点 $i$ 时的载重
$Q i j k$	车辆 $k$ 行驶在道路 $(i, j)$ 上的载重
$c i k 1$	车辆 $k$ 到达节点 $i$ 时的剩余电量
$c i k 2$	车辆 $k$ 离开节点 $i$ 时的剩余电量
$d i j k h$	车辆 $k$ 在时间段 $h$ 以速度 $v i j h$ 在道路 $(i, j)$ 上行驶的距离
$d i j$	从节点 $i$ 到节点 $j$ 的距离
$t i j k h$	车辆 $k$ 在时间段 $h$ 以速度 $v i j h$ 在道路 $(i, j)$ 上行驶的时间
$ξ i j k h$	车辆 $k$ 在时间段 $h$ 以速度 $v i j h$ 在道路 $(i, j)$ 上行驶单位距离的能耗
$ζ i j k$	车辆 $k$ 从节点 $i$ 行驶到节点 $j$ 的能耗
$σ i k$	车辆 $k$ 提前到达顾客点 $i$ 的等待时间
$τ i$	顾客点 $i$ 的服务时间
$P i k$	车辆 $k$ 在充电站 $i$ 充电后完成后续配送服务需消耗的总电量
$R i k$	车辆 $k$ 在充电站 $i$ 进行充电时的充电量
$t i k$	车辆 $k$ 在充电站 $i$ 的充电时间
$ε$	车辆的充电速率
$λ 1$	单位能耗成本
$λ 2$	车辆使用单位时间成本
$λ 3$	车辆使用单位时间人力成本
$λ 4$	车辆的固定发车费用
$x i j k$	0-1决策变量，当车辆 $k$ 从节点 $i$ 行驶至节点 $j$ 时值为1，否则为0
$y i j k h$	0-1决策变量，当车辆 $k$ 在时间段 $h$ 行驶在道路 $(i, j)$ 上时值为1，否则为0
$z i k$	0-1决策变量，当车辆 $k$ 在充电站 $i$ 充电时值为1，否则为0

符号	参数值	符号	参数值
$Q$	3000千克	$f 0$	3169千克
$ε$	60千瓦/小时	$C$	38千瓦时
$λ 1$	1.4元/千瓦时	$λ 2$	70元/小时
$λ 3$	50元/小时	$λ 4$	200元/辆

References 20

[1]	揭婉晨，杨珺，杨超. 多车型电动汽车车辆路径问题的分支定价算法研究［J］. 系统工程理论与实践， 2016， 36（7）： 1795-1805.
	Jie W C， Yang J， Yang C. Branch-and-price algorithm for heterogeneous electric vehicle routing problem［J］. Systems Engineering-Theory & Practice， 2016， 36（7）： 1795-1805.
[2]	郭放，杨珺，杨超. 考虑充电策略与电池损耗的电动汽车路径优化问题研究［J］. 中国管理科学， 2018， 26（9）： 106-118.
	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.
[3]	Conrad R G， Figliozzi M A. The recharing vehicle routing problem ［C］//Proceedings of the 2011 Reno Industrial Engineering Research Conference，Reno，NV，USA，May 21-25， IISE， 2011：111-118.
[4]	Kancharla S R， Ramadurai G. An adaptive large neighborhood search approach for electric vehicle routing with load-dependent energy consumption［J］. Transportation in Developing Economies， 2018， 4（2）： 1-9.
[5]	黄建华，刘方翔. 动态负载下电动汽车充电策略及路径优化问题［J］. 计算机集成制造系统， 2023， 29（11）： 3909-3921.
	Huang J H， Liu F X. Charging strategy and routing optimization of electric vehicles under dynamic load［J］. Computer Integrated Manufacturing Systems， 2023， 29（11）： 3909-3921.
[6]	Bektaş T， Laporte G. The pollution-routing problem［J］. Transportation Research Part B： Methodological， 2011， 45（8）： 1232-1250.
[7]	Xiao Y， Zhang Y， Kaku I， et al. Electric vehicle routing problem： A systematic review and a new comprehensive model with nonlinear energy recharging and consumption［J］. Renewable and Sustainable Energy Reviews， 2021， 151： 111567.
[8]	Desaulniers G， Errico F， Irnich S， et al. Exact algorithms for electric vehicle-routing problems with time windows［J］. Operations Research， 2016， 64（6）： 1388-1405.
[9]	葛显龙，李祖伟，葛小波. 考虑灵活充电策略的带时间窗物流配送路径优化研究［J］. 控制理论与应用， 2020， 37（6）： 1293-1301.
	Ge X L， Li Z W， Ge X B. Research on logistics distribution route optimization with time window considering flexible charging strategy［J］. Control Theory & Applications， 2020， 37（6）： 1293-1301.
[10]	Meng M， Ma Y. Route optimization of electric vehicle considering soft time windows and two ways of power replenishment［J］. Advances in Operations Research， 2020， 2020（1）： 5612872.
[11]	Lu J， Chen Y， Hao J K， et al. The time-dependent electric vehicle routing problem： Model and solution［J］. Expert Systems with Applications， 2020， 161： 113593.
[12]	Zhang R， Guo J， Wang J. A time-dependent electric vehicle routing problem with congestion tolls［J］. IEEE Transactions on Engineering Management， 2022， 69（4）： 861-873.
[13]	Wang L， Gao S， Wang K， et al. Time-dependent electric vehicle routing problem with time windows and path flexibility［J］. Journal of Advanced Transportation， 2020， 2020： 3030197.
[14]	Zulvia F E， Kuo R J， Nugroho D Y. A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products［J］. Journal of Cleaner Production， 2020， 242： 118428.
[15]	Mirjalili S， Lewis A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016， 95： 51-67.
[16]	张金良，李超. 碳排放影响下的动态配送车辆路径优化研究［J］. 中国管理科学， 2022， 30（9）： 184-194.
	Zhang J L， Li C. Research on dynamic distribution vehicle route optimization under the influence of carbon emission［J］. Chinese Journal of Management Science， 2022， 30（9）： 184-194.
[17]	Keskin M， Çatay B. Partial recharge strategies for the electric vehicle routing problem with time windows［J］. Transportation Research Part C： Emerging Technologies， 2016， 65： 111-127.
[18]	Schneider M， Stenger A， Goeke D. The electric vehicle-routing problem with time windows and recharging stations［J］. Transportation Science， 2014， 48（4）： 500-520.
[19]	Yu V F， Jodiawan P， Gunawan A. An Adaptive Large Neighborhood Search for the green mixed fleet vehicle routing problem with realistic energy consumption and partial recharges［J］. Applied Soft Computing， 2021， 105： 107251.
[20]	高佳静，镇璐. 多卡车多机器人联合配送系统路径问题研究［J］. 中国管理科学， 2023， 31（3）： 48-57.
	Gao J J， Zhen L. Research on routing problem for joint delivery system based on multiple trucks and robots［J］. Chinese Journal of Management Science， 2023， 31（3）： 48-57.

算例	5个顾客点					10个顾客点
	CPLEX		IWOA		Dev%	CPLEX		IWOA		Dev%
	TC	t/秒	TC	t/秒	Dev%	TC	t/秒	TC	t/秒	Dev%
R202	1102.6	1.8	1032.1	13.8	6.4	2025.1	998.7	1652.6	23.5	18.3
R204	1315.2	1.1	1185.8	14.9	9.8	1577.1	3600	1544.3	23.9	2.1
R206	1111.2	1.7	849.7	23.1	23.5	1937.3	3600	1764.1	21.1	8.9
R208	1269.1	1.6	995.7	18.3	21.5	1866.5	3600	1473.9	22.4	21
RC202	1646.2	0.7	1483.8	19.5	9.9	2521.7	79.97	2190.8	26.1	13.1
RC204	1801.4	0.9	1682.3	16.7	6.6	2782.8	396.02	2686.2	31.2	3.5
RC206	1757.8	0.6	1878.5	21.1	-6.9	3668.4	1390.1	2934.4	35.1	20
RC208	1067.9	2.1	996.3	25.8	6.7	2380.8	3600	2602.3	27.9	-9.3
平均值	1383.9	1.3	1263.0	19.2	9.7	2345.0	2158.1	2106.1	26.4	9.7

优化目标	TC	TE	TT	TD	TV
总配送成本最小	8028.91	300.22	3105.30	1450.52	7
总能耗最小	9927.86	239.81	4096.06	1417.73	7
总行程时间最小	8167.21	311.36	3065.65	1459.76	8

充电策略	SN	CT	CR	TC	TE	TT
部分充电	1	5.68	14.95	7941.46	268.76	3082.59
	2	11.49	30.24
	3	14.71	38.71
	4	11.29	29.71
	5	11.35	29.87
	6	18.01	47.39
	7	9.56	25.16
完全充电	1	31.01	100	8358.59	338.29	3242.49
	2	16.75	100
	3	23.59	100
	4	21.58	100
	5	17.26	100
	6	31.65	100
	7	25.75	100

算例	IWOA			ALNS			VNS			Dev%
算例	Best	Ave	t/秒	Best	Ave	t/秒	Best	Ave	t/秒	ALNS	VNS
R202	10005.29	10648.11	759.25	11108.66	12512.61	812.02	11955.85	15257.33	535.08	9.93	16.31
R204	8126.87	8698.04	675.98	9364.66	9818.10	1050.65	9955.31	10901.74	400.69	13.22	18.37
R206	8962.29	9493.38	738.08	9999.56	10815.16	918.39	12137.11	13373.41	595.08	10.37	26.16
R208	7679.24	7908.48	557.43	7964.93	8524.67	1047.78	8925.59	9368.73	250.94	3.59	13.96
RC202	11725.66	12208.99	777.82	13317.4	14551.05	872.50	13232.28	14932.33	638.41	11.95	11.39
RC204	9139.32	9693.25	678.24	10491.1	10725.19	1050.24	10492.64	11471.3	305.73	12.89	12.90
RC206	10341.55	11254.04	714.79	12105.25	12719.18	904.00	11994.68	12957.88	602.4	14.57	13.78
RC208	7941.46	8028.91	841.76	8046.58	8303.18	1010.87	9987.2	10596.13	443.09	1.31	20.48
平均值	9240.21	9741.65	717.92	10299.77	10996.14	958.31	11085.08	12357.36	471.43	9.73	16.67

算例	TC/TC1	Increase%	TE/TE1	Increase%	TT/TT1	Increase%
R202	10005.29/11201.64	11.96	375.84 /389.82	3.72	4139.56 /4627.95	11.80
R204	8126.87/9253.27	13.86	299.40 /337.25	12.64	3253.86 /3690.56	13.42
R206	8962.29/10631.78	18.63	319.94 /345.12	7.87	3557.19 /4474.31	25.78
R208	7679.24/9190.56	19.68	255.27 /276.34	8.25	2960.93 /3701.85	25.02
RC202	11725.66/13815.46	17.82	466.59 /479.15	2.69	4836.22 /5772.33	19.36
RC204	9139.32/10435.55	14.18	323.75 /383.40	18.42	3743.04 /4249.40	13.53
RC206	10341.55/12127.85	17.27	397.51 /456.26	14.78	4192.52 /5044.54	20.32
RC208	7941.46/8945.49	12.64	264.78 /328.39	24.03	3085.39 /3542.87	14.83
平均值	9240.21/10700.20	15.76	337.89/374.47	11.55	3721.09/4387.98	18.01

Research on Time Dependent Electric Vehicle Routing Model with Nonlinear Energy Consumption and an Improved Whale Optimization Algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 20

Related Articles 1

Metrics

Comments

Recommended 0