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

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

Abstract

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

CLC Number:

U116.2

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.

Figures/Tables 14

参数与变量
参数
$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$ 的电量

变量	$ρ 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

References 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

Collaborative Optimization of Charging Network and Charging Strategy with Practical Battery Wear Model

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 22

Related Articles 15

Metrics

Comments

Recommended 0

输入		实验组				对照组
编号	算例	车数K	BEST1	best1	时间(s)	车数K	BEST2	best2	时间(s)
1	P-n16-k8	8.00	1483.77	1292.17	3.57	8.00	1492.23	1273.09	3.62
2	P-n19-k2	2.00	632.71	533.21	4.51	2.00	638.56	527.92	4.55
3	P-n21-k2	2.00	651.82	549.36	4.77	2.00	670.53	542.06	4.68
4	P-n23-k8	9.00	1858.57	1617.49	5.19	9.00	1898.48	1607.07	5.01
5	P-n40-k5	5.00	1203.39	1023.94	11.82	5.00	1219.88	1013.65	11.18
6	P-n45-k5	5.00	1272.38	1088.02	12.49	5.00	1292.87	1073.90	11.72
7	P-n50-k7	7.00	1481.82	1275.09	14.01	7.00	1513.84	1255.57	13.34
8	P-n55-k8	7.00	1671.75	1419.47	22.97	7.00	1712.74	1404.38	21.96
9	P-n60-k10	10.00	2164.54	1849.28	27.37	10.00	2197.05	1815.35	27.16
10	P-n70-k10	10.00	2173.56	1886.70	30.16	10.00	2216.84	1851.29	30.61
平均值		6.50	1459.43	1253.47	13.69	6.50	1485.30	1236.43	13.38

[1]	Yin Xiang. Dynamic Emergency Medical Facilities Location for Epidemics under Uncertain Demand [J]. Chinese Journal of Management Science, 2024, 32(6): 129-139.
[2]	XIANG Yin. Hydrogenation Infrastructure Network Optimization Considering Industrial Layout and Customer Satisfaction [J]. Chinese Journal of Management Science, 2023, 31(5): 164-175.
[3]	GUO Fang, HUANG Zhi-hong, HUANG Wei-lai, YANG Chao. Optimal Planning of the Electric Vehicle Routing and Battery Charging Problem with Self-pickup and Door-to-door Delivery Service [J]. Chinese Journal of Management Science, 2022, 30(2): 264-275.
[4]	CHEN Gang, FU Jiang-yue. Emergency Medical Mobile Hospital Robust Location Problem in Post-disaster under Demand Uncertainty [J]. Chinese Journal of Management Science, 2021, 29(9): 213-223.
[5]	GUO Fang, YANG Jun, YANG Chao. Study on Heterogeneous Electric Vehicle Routing and Batterycharging Problem with the Consideration of Differentiated Service Cost [J]. Chinese Journal of Management Science, 2019, 27(8): 118-128.
[6]	XIANG Yin. A Bi-level Programming Model for Locating Terror Response Facilities [J]. Chinese Journal of Management Science, 2019, 27(7): 147-157.
[7]	ZHOU Yu-feng, LI Zhi, LIU Si-feng. Location-inventory Model of National Blood Strategic Reserves based on p-robust Stochastic Optimization Method [J]. Chinese Journal of Management Science, 2018, 26(10): 52-63.
[8]	CHEN Yi-you, ZHANG Jin, LUO Jian-qiang. The Impact of Customers' Choice Behavior on Pickup Point Location [J]. Chinese Journal of Management Science, 2017, 25(5): 135-144.
[9]	ZHANG Min, ZHANG Ling. System of Evaluation Indices of Emergency Facility Location and Model Based on Facility Failure Scenarios [J]. Chinese Journal of Management Science, 2016, 24(11): 129-136.
[10]	YU Peng, JUAN Zhi-cai. Service Level Guaranteed Emergency Repair Station Location Model and Solution [J]. Chinese Journal of Management Science, 2014, 22(3): 34-41.
[11]	ZHAO Pei-xin, ZHANG Cun-Quan, ZHAO Bing-xin. Multi-facility Location Policy based on New Graph Theory Clustering Approach [J]. Chinese Journal of Management Science, 2012, 20(6): 149-153.
[12]	WANG Zheng, LIAO Bei-yu, SUI Wen-juan. Hierarchical Emergency Facility Location Model and Its Application [J]. Chinese Journal of Management Science, 2011, 19(6): 88-91.
[13]	YANG Jun, LIU Shu-ji, WANG Ling. A Bi-Level Programming Model and Heuristics for P-Median Location Problem with R-Interdiction Worst Loss [J]. Chinese Journal of Management Science, 2011, 19(4): 120-129.
[14]	HUANG Song, YANG Chao, YANG Jun. Distribution Network Design Model for Deteriorating Items Based on Stackelberg Game [J]. Chinese Journal of Management Science, 2009, 17(6): 122-129.
[15]	HUANG Song, YANG Chao. Study on Joint Location-Inventory Model under Stochastic Demand [J]. Chinese Journal of Management Science, 2009, 17(5): 96-103.

输入		P-n40-k5			P-n45-k5			P-n50-k7
编号	Q_d	实验组	对照组	Gap(%)	实验组	对照组	Gap(%)	实验组	对照组	Gap(%)
1	1.00	1374.61	1390.92	-1.17	1516.04	1540.47	-1.59	1798.31	1858.36	-3.23
2	1.10	1191.88	1206.47	-1.21	1259.19	1277.80	-1.46	1480.90	1510.86	-1.98
3	1.20	1144.82	1153.10	-0.72	1248.16	1262.66	-1.15	1419.72	1443.53	-1.65
4	1.30	1100.96	1112.74	-1.06	1177.05	1189.75	-1.07	1371.11	1388.89	-1.28
5	1.40	998.91	1007.00	-0.80	1078.38	1088.02	-0.89	1292.16	1308.12	-1.22
6	1.50	967.45	972.02	-0.47	1041.96	1049.85	-0.75	1273.56	1291.13	-1.36
7	1.60	950.07	954.85	-0.50	981.44	988.38	-0.70	1197.42	1212.83	-1.27
8	1.70	929.06	930.65	-0.17	969.01	974.10	-0.52	1177.24	1190.82	-1.14
平均值		1082.22	1090.97	-0.80	1158.91	1171.38	-1.06	1376.30	1400.57	-1.73