考虑电池损耗的电动物流汽车充电设施选址与充电策略协同优化研究

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

摘要/Abstract

摘要：

由于政府的大力支持和社会公众环保意识的增强，电动汽车在物流领域的应用得到了广泛的关注。不同于传统物流车辆，电动汽车运营成本受到电池损耗等因素的影响。本文以电池损耗模型为基础，建立了电动汽车充电设施选址与充电策略协同优化问题的整数规划模型。针对上述问题，本文提出了基于自适应大邻域搜索的混合启发式算法（SIGALNS），改进算子提升算法求解效率。随后，通过算例分析验证了模型的准确性和算法的有效性。研究结果表明，考虑电池损耗成本的电动汽车网络优化策略有利于降低物流企业运营成本，与其实际需要更为契合。

关键词: 设施选址, 电动物流汽车, 充电策略, 电池损耗, 混合启发式算法

Abstract:

Electric vehicles （EVs） have attracted increasing attention in the field of logistics owing to the strong support received from the government and the continuous increase in social environmental awareness. Compared to traditional logistics vehicles， EVs have additional charging costs such as charging time cost and battery wear cost. In this study， the routing problem of EVs is formulated as an integer programming model based on a nonlinear charging model and a practical battery wear model. Subsequently， a three-phase algorithm called SIGALNS is proposed for solving it. Based on the proposed model， a series of instances are generated showing the benefits of combining charging time， battery wear and distribution. Finally， sensitivity analyses are systematically conducted on wearing cost and charging time under a realistic background. The results show that the optimal planning of an EV network considering time and wear costs is in line with the practical needs of EV logistics enterprises； this can help reduce operating costs. The results of this paper demonstrate the impact of charging strategy on the cost of electric logistics vehicle logistics service network from a practical perspective， and propose a collaborative optimization scheme of distribution scheduling and charging plan to reduce the comprehensive operating cost of enterprises. The models and algorithms proposed in this study can provide a decision-making basis for logistics enterprises that use electric logistics vehicles as delivery vehicles to make operational decisions.

Key words: facility location, electric freight vehicle, charging strategy, battery wear, hybrid heuristic algorithm

中图分类号:

U116.2

黄志红,黄卫来,郭放. 考虑电池损耗的电动物流汽车充电设施选址与充电策略协同优化研究[J]. 中国管理科学, 2024, 32(6): 68-78.

Zhihong Huang,Weilai Huang,Fang Guo. Collaborative Optimization of Charging Network and Charging Strategy with Practical Battery Wear Model[J]. Chinese Journal of Management Science, 2024, 32(6): 68-78.

图/表 14

表1

参数与变量"

参数与变量
参数
$I$	配送点集合
$J$	充电站点集合
$V$	节点集合 $V = I ? J ? o ? o'$
$D$	SOC区间集合
$o$	配送中心
$o'$	虚拟配送中心
$K$	配送车辆集合
$f i$	在 $i$ 点建立充电站点的成本
$M$	一个极大值
$C k$	车辆 $k$ 的最大载重
$S ˉ d$	SOC 区间 $d$ 的上限
$α$	电池损耗成本系数
$γ$	车辆行驶单位距离产生的运输成本
$σ 2$	路径成本权重
$Q$	满电量状态下车辆最大行驶里程，考虑到对电池寿命的影响，假设SOC须在最小值 $Q m i n$ 和最大值 $Q m a x$ 之间
变量
$d g h$	节点 $i$ 和 $j$ 之间的距离
$L$	SOC区间的长度
$q i$	节点 $i$ 的货物需求量
$S ? d$	SOC 区间 $d$ 的下限
$W d$	SOC 区间 $d$ 内充、放单位电量损耗成本
$σ 1$	建站成本权重
$σ 3$	电池损耗成本权重
$y i$	0-1变量，当在 $i$ 点设立服务设施时， $y i = 1$ ，否则为0
$x i j k$	0-1 变量，当车辆 $k$ 经过弧 $i, ? j$ 时， $x i j k = 1$ ，否则为0
$u j k d$	0-1 变量，若车辆 $k$ 在充电站点 $j$ 将电量充入SOC区间 $d ∈ D$ ，则 $u j k d = 1$ ，否则取0
$g j k ?$	车辆 $k$ 在站点 $j$ 处的充电总量
$c i k$	车辆 $k$ 离开点 $i$ 时剩余车载货物量
$S j k d$	车辆 $k$ 在站点 $j$ 充电过程中充入SOC区间 $d ∈ D$ 的电量
$p i k 1$	车辆 $k$ 到达点 $i$ 的电量
$p i k 2$	车辆 $k$ 离开点 $i$ 的电量

表1

表2

模型参数赋值"

变量	$ρ 3$	$ρ 4$	$N b e s t$	$α 1$	$α 2$	$λ 1$	$λ 2$	$λ 3$	$λ 4$	$I T E R a l n s$	$I T E R i g a l n s$
取值	10	10	30	0.6	0.4	0.9	0.1	0.9	0.1	30	200

表2

表3

表4

表5

表6

表7

表8

图1

图2

表9

图3

图4

图5

参考文献 22

1	Guo F， Huang Z H， Huang W L. Heuristic approaches for a vehicle routing problem with an incompatible loading constraint and splitting deliveries by order［J］. Computers & Operations Research， 2021，134： 105379.
2	徐小峰，林姿汝，周鹏. 多油品供给受限下多油库被动配送车辆路径问题研究［J］. 中国管理科学， 2021， 29 （5）： 157-165.
	Xu X F， Lin Z R， Zhou P. Research on vehicle routing problem of multiple oil depot passive distribution under multi oil supply constraints［J］. Chinese Journal of Management Science， 2021， 29 （5）： 157-165.
3	邱晗光，周继祥，龙跃. 顾客可选末端交付方式和时间窗的城市配送动态订单接受优化研究［J］. 中国管理科学， 2020， 28 （8）： 114-126.
	Qiu H G， Zhou J X， Long Y. Research on the dynamic order acceptance in urban delivery considering customer choice of the last-mile delivery modes and time slots［J］. Chinese Journal of Management Science， 2020， 28 （8）： 114-126.
4	Koc C， Jabali O， Mendoza J E， et al. The electric vehicle routing problem with shared charging stations［J］. International Transactions in Operational Research， 2019， 26（4）： 1211-1243.
5	Li Y， Zhang P， Wu Y. Public recharging infrastructure location strategy for promoting electric vehicles： A bi-level programming approach［J］. Journal of Cleaner Production， 2018， 172： 2720-2734.
6	Farham M S， Sural H， Iyigun C. A column generation approach for the location-routing problem with time windows［J］. Computers & Operations Research， 2018， 90： 249-263.
7	Darvish M， Archetti C， Coelho L C， et al. Flexible two-echelon location routing problem［J］. European Journal of Operational Research， 2019， 277（3）： 1124-1136.
8	Huang Z， Huang W， Guo F. Integrated sustainable planning of self-pickup and door-to-door delivery service with multi-type stations［J］. Computers & Industrial Engineering， 2019， 135： 412-425.
9	Huang Z， Huang W， Guo F. Integrated sustainable planning of micro-hub network with mixed routing strategy［J］. Computers & Industrial Engineering， 2020， 149： 106872.
10	郭放，杨珺，杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究［J］. 中国管理科学， 2019， 27（8）： 118-128.
	Guo F， Yang J， Yang C. Study on heterogeneous electric vehicle routing and battery charging problem with the consideration of differentiated service cost［J］. Chinese Journal of Management Science， 2019， 27（8）： 118-128.
11	Jafari M， Khan K， Gauchia L. Deterministic models of li-ion battery aging： It is a matter of scale［J］. Journal of Energy Storage， 2018， 20： 67-77.
12	Zhang S， Gajpal Y， Appadoo S S， et al. Electric vehicle routing problem with recharging stations for minimizing energy consumption［J］. International Journal of Production Economics， 2018， 203： 404-413.
13	Schoch J， Gaerttner J， Schuller A， et al. Enhancing electric vehicle sustainability through battery life optimal charging［J］. Transportation Research Part B： Methodological， 2018， 112： 1-18.
14	Pelletier S， Jabali O， Laporte G. 50th anniversary invited article—goods distribution with electric vehicles： Review and research perspectives［J］. Transportation Science， 2016， 50（1）： 3-22.
15	Pelletier S， Jabali O， Laporte G， et al. Battery degradation and behaviour for electric vehicles： Review and numerical analyses of several models［J］. Transportation Research Part B： Methodological， 2017， 103： 158-187.
16	Pelletier S， Jabali O， Laporte G. Charge scheduling for electric freight vehicles［J］. Transportation Research Part B： Methodological， 2018， 115： 246-269.
17	Yue M， Jemei S， Gouriveau R， et al. Review on health-conscious energy management strategies for fuel cell hybrid electric vehicles： Degradation models and strategies［J］. International Journal of Hydrogen Energy， 2019，44（13）：6844-6861.
18	郭放，杨珺，杨超. 考虑充电策略与电池损耗的电动汽车路径优化问题研究［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.
19	Han S， Han S， Aki H. A practical battery wear model for electric vehicle charging applications［J］. Applied Energy， 2014， 113： 1100-1108.
20	Adulyasak Y， Cordeau J F， Jans R. Optimization-based adaptive large neighborhood search for the production routing problem［J］.Transportation Science， 2012， 48（1）：20-45.
21	Montoya A， Gueret C， Mendoza J E， et al. The electric vehicle routing problem with nonlinear charging function［J］. Transportation Research Part B： Methodological， 2017， 103： 87-110.
22	Augerat P， Belenguer J M， Benavent E， et al. Computational results with a branch and cut code for the capacitated vehicle routing problem［J］. Rapport De Recherché-IMAG， 1995， 495： 1-33.

测试参数	算例	SPR^*	BWR	AWR	RAR^*	SBR	BIR^*	RGR^*	RER^*	TPR	平均值
调用次数	P-n16-k8	2017	1670	1573	2004	1656	2075	1961	2020	1673	1850
	P-n19-k2	1976	1764	1872	1825	1626	1940	1888	2028	1700	1847
	P-n21-k2	1999	1799	1636	1961	1587	1953	1956	1845	1942	1853
	P-n23-k8	1980	1864	1389	1979	1640	2002	1940	1920	1903	1846
	P-n40-k5	2077	1712	1672	1837	1733	1973	2111	1792	1779	1854
权重	P-n16-k8	13.51	10.36	7.58	10.49	7.26	9.74	10.71	8.60	6.16	9.38
	P-n19-k2	9.63	7.06	8.74	8.12	9.34	9.67	12.77	9.77	9.24	9.37
	P-n21-k2	11.37	7.69	9.99	13.47	7.28	12.07	9.60	8.72	8.36	9.84
	P-n23-k8	10.28	10.35	8.65	11.48	8.09	8.92	11.72	11.44	6.11	9.67
	P-n40-k5	9.49	8.03	6.03	9.76	6.07	8.08	10.39	12.84	6.84	8.62

测试参数	算例	BGI	AGI^*	BR2I	BR3I*	AR2I^*	AR3I^*	平均值
调用次数	P-n16-k8	2059	2767	2530	3073	2889	2884	2700
	P-n19-k2	2559	2934	2121	2645	2923	3016	2700
	P-n21-k2	2224	3040	1919	3205	2759	3054	2700
	P-n23-k8	2545	3071	2092	2804	2836	2851	2700
	P-n40-k5	2175	2735	2854	3130	2652	2654	2700
权重	P-n16-k8	8.50	11.65	11.09	12.53	12.88	10.35	11.17
	P-n19-k2	9.70	10.68	8.89	8.40	14.81	11.84	10.72
	P-n21-k2	9.89	12.59	9.61	14.27	11.63	12.41	11.74
	P-n23-k8	10.87	9.05	8.03	11.92	10.50	8.82	9.87
	P-n40-k5	7.61	10.18	7.68	10.61	9.90	11.36	9.56

输入			CPLEX					SIGALNS				GAP
算例	N	Q	满意解		L	k	计算时间(s)	满意解	L	k	计算时间(s)	(%)
P-n5-k2	5	87.92	478.55		2	2	772.31	478.55	2	2	1.42	0.00
P-n6-k2	6	87.92	547.34		3	2	4251.68	547.34	3	2	1.83	0.00
P-n7-k3	7	87.92	549.78^*		3	2	10800.00	549.78	3	2	2.53	0.00
P-n8-k3	8	89.48	748.43^*		3	3	10800.00	745.39	3	3	2.99	-0.41
P-n9-k4	9	89.48	726.11^*		2	3	10800.00	712.64	2	3	3.52	-1.86
P-n10-k4	10	89.48	#		#	#	#	711.43	2	4	3.66	#
平均值	7.50	88.70		610.04	2.60	2.40	7484.80	624.19	2.50	2.67	2.66	-0.45

				CPLEX			SIGALNS
算例	N	Q	C	站点成本	距离成本	损耗成本	站点成本	距离成本	损耗成本
P-n5-k2	5	87.92	43.96	87.92	325.84	64.79	87.92	325.84	64.79
P-n6-k2	6	87.92	43.96	131.88	345.08	70.38	131.88	345.08	70.38
P-n7-k3	7	87.92	43.96	131.88	346.82	71.08	131.88	346.82	71.08
P-n8-k3	8	89.48	44.74	134.22	510.05	104.16	134.22	508.41	102.76
P-n9-k4	9	89.48	44.74	89.48	525.87	110.76	89.48	517.72	105.44
P-n10-k4	10	89.48	44.74	#	#	#	89.48	539.13	82.82
平均值	7.50	88.70	44.35	115.08	410.73	84.23	110.81	430.50	82.88

输入		实验组				对照组
编号	算例	当前最优解	20次运行结果			当前最优解	20次运行结果
编号	算例	当前最优解	平均解	Gap%	标准差	当前最优解	平均解	Gap%	标准差
1	P-n16-k8	1483.77	1487.52	0.25	3.91	1273.09	1273.09	0.00	0.00
2	P-n19-k2	632.71	633.95	0.20	0.96	527.92	527.92	0.00	0.00
3	P-n21-k2	651.82	654.48	0.41	2.79	542.06	544.67	0.48	2.67
4	P-n23-k8	1858.57	1869.78	0.60	10.67	1607.07	1614.10	0.44	7.11
5	P-n40-k5	1203.39	1210.70	0.61	7.38	1013.65	1021.37	0.76	8.76
6	P-n45-k5	1272.38	1278.70	0.50	6.67	1073.90	1075.34	0.13	1.45
7	P-n50-k7	1481.82	1489.75	0.54	8.57	1255.57	1263.31	0.62	8.35
8	P-n55-k8	1671.75	1681.48	0.58	10.34	1404.38	1416.14	0.84	9.86
9	P-n60-k10	2164.54	2185.37	0.96	21.84	1815.35	1823.25	0.44	7.15
10	P-n70-k10	2173.56	2190.64	0.79	16.72	1851.29	1864.08	0.69	11.17
平均值		1459.43	1468.24	0.54	8.99	1236.43	1242.33	0.44	5.65