考虑峰谷分时电价和电池损耗成本的纯电动公交车充电调度优化研究

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

Abstract

Abstract:

The problem of battery electric bus （BEB） charging scheduling is investigated in this study. The problem stems from the large-scale popularization and application of BEBs in especially Chinese urban areas， which bring unprecedented challenges to the current bus operation scheme. It is a very necessary and urgent task to accordingly solve the corresponding scheduling optimization problems emerged due to the application of BEBs. The charging scheduling of BEBs is taken as the research perspective， which aims to provide an efficient and minimum cost charging schedule to meet the electric power demand of BEBs in their daily operations. The BEB battery damage cost is described by analyzing the optimal fluctuation range of the battery state of charge （SoC）. The feature of peak-valley electricity price in the time horizon of a full day is furtker depicted. It is mainly observed that in the BEB charging activities， one battery actually needs not to be charged to 100%of SoC， while a minimum percent of SoC after charging is required so as to satisfy the power demand in the next day operation. Therefore， the amount of SoC being charged， which is called the task completion degree in this work， during one BEB charging activity becomes a critical variable in the considered problem. It differs from the classical scheduling problem in which tasks have to be fulfilled to 100% to be satisfied. It is assumed that all the BEB chargers in the charging field are identical in this work. Based on the above analysis and assumption， the considered problem is formulated as the identical parallel machine scheduling problem with controllable task completion degree. A mixed integer linear programming （MILP） model is established with the objective of minimizing the total operation cost， which consists of the cost of power consumed and the BEB battery damage cost. For small-scale instances of the considered problem， exact solutions can be obtained by solving the MILP model via commercial solvers such as CPLEX. For solving large-scale instances， an immune optimization algorithm based on random key coding and a greedy heuristic algorithm based on the idea of avoiding peaks and filling valleys are developed. The correctness of the MILP model is verified by solving small-scale instances in the numerical experiments. The effectiveness of the proposed algorithms is revealed by a case study based on a real public transport network in Shanghai and experimental results for large-scale instances. Numerical results show that the optimal charging scheduling scheme can save about 7.08% of operation costs for bus companies. Moreover， the random key immune algorithm proposed in this work has the potential to be applied in large-scale BEB charging scenarios.

Key words: scheduling optimization, battery damage cost, peak-valley electricity price, heuristic algorithm

CLC Number:

O224

Feifeng Zheng, Zhixin Wang, Ming Liu. Charging Scheduling Optimization of Battery Electric Buses Considering Peak-Valley Electricity Price and Battery Damage Cost[J]. Chinese Journal of Management Science, 2024, 32(11): 125-135.

Figures/Tables 10

季节	峰谷电价时段			峰谷分时电价
季节	峰时用电	平时用电	谷时用电			单位电价（元/(kW $∙$ h)）
夏季	08:00~11:00	06:00~08:00	24:00~06:00	用电分类		$≤ 1 k V$	10 $k V$	35 $k V$	$≥ 100 k V$
	13:00~15:00	11:00~13:00	-	工业用电	峰时	1.074	1.049	1.024	0.999
	18:00~22:00	15:00~18:00	-		平时	0.671	0.646	0.621	0.596
	-	22:00~24:00	-		谷时	0.316	0.310	0.304	0.298
其他	08:00~11:00	06:00~08:00	22:00~06:00	居民用电	峰时	-	0.730	-	-
	18:00~21:00	11:00~18:00	-		平时	-	0.448	-	-
	-	21:00~22:00	-		谷时	-	0.242	-	-

线路			Real	Cplex			RK-IA				GM
线路	N	M	$O b j$	$O b j C p$	T	$G R E C p$	$O b j I A$	T	$G R E I A$	$G I A C p$	$O b j G M$	T	$G R E G M$	$G G M C p$
111	9	2	1723.1	1576.5	23.07	8.51	1581.4	2.17	8.22	0.31	1664.2	0.15	3.42	5.56
	9	3	1677.4	1544.2	37.40	7.94	1558.2	2.14	7.11	0.91	1613.8	0.37	3.79	4.51
	9	4	1644.3	1541.3	55.12	6.26	1548.8	2.35	5.81	0.49	1594.2	0.29	3.05	3.43
69	11	3	2228.2	2038.8	143..21	8.50	2057.4	2.07	7.67	0.91	2167.4	0.59	2.73	6.31
	11	4	2136.9	1971.4	136.82	7.74	1986.9	3.56	7.02	0.79	2087.6	0.71	2.31	5.89
	11	5	2136.9	1998.4	225.41	6.48	2009.7	6.88	5.95	0.57	2074.3	1.03	2.93	3.80
224	14	3	2809.8	2574.1	297.45	8.39	2594.4	13.13	7.67	0.79	2675.3	0.95	4.79	3.93
	14	4	2745.6	2539.3	247.58	7.51	2560.8	19.76	6.73	0.85	2649.7	2.14	3.49	4.35
	14	5	2554.8	2405.5	331.95	5.84	2423.1	21.44	5.16	0.73	2491.9	1.27	2.46	3.59
830	14	3	2829.4	2583.9	357.02	8.68	2594.4	19.55	8.31	0.41	2689.4	4.51	4.95	4.08
	14	4	2749.6	2543.1	301.77	7.51	2572.3	24.41	6.45	1.15	2641.2	1.97	3.94	3.86
	14	5	2563.1	2421.5	399.54	5.52	2434.1	18.27	5.03	0.52	2503.1	2.21	2.34	3.37
836	16	4	3241.8	2982.5	655.9	8.00	3017.9	39.57	6.91	1.19	3105.3	5.67	4.21	4.12
	16	5	3166.2	2941.7	749.14	7.09	2984.5	37.12	5.74	1.45	3069.4	9.17	3.06	4.34
	16	6	3055.7	2856.4	898.69	6.52	2892.1	65.22	5.35	1.25	2978.5	8.42	2.53	4.27
71	22	5	4478.4	4188.7	1445.64	6.47	4256.2	101.5	4.96	1.61	4334.5	16.24	3.21	3.48
	22	6	4357.6	4130.5	2176.55	5.21	4196.5	77.85	3.70	1.60	4269.7	18.17	2.02	3.37
	22	7	4349.4	4119.4	2227.85	5.29	4207.9	99.21	3.25	2.15	4225.1	14.55	2.86	2.57
AVG						7.08			6.17	0.98			3.23	4.16

线路			Real	Cplex			RK-IA				GM
线路	N	M	$O b j$	$O b j C p$	T	$G R E C p$	$O b j I A$	T	$G R E I A$	$G I A C p$	$O b j G M$	T	$G R E G M$	$G G M C p$
111，69	20	4	4075.3	3720.5	1728.21	8.71	3769.9	94.54	7.49	1.33	3856.4	2.75	5.37	3.65
69，224	25	5	5114.7	4700.4	2854.17	8.10	4787.6	113.81	6.40	1.86	4874.1	4.48	4.70	3.70
224，830	28	6	5679.4	5211.8	3471.52	8.23	5347.5	213.44	5.84	2.60	5428.8	5.17	4.41	4.16
830，836	30	6	6198.2	—	—	—	5794.1	222.44	6.52	—	5900.5	11.75	4.80	—
836，71	38	8	7714.2	—	—	—	7212.4	358.52	6.50	1.93	7324.4	18.84	5.05	3.84
AVG						8.35			6.55				4.87	3.84

线路			Real	RK-IA			GM
线路	N	M	$O b j$	$O b j I A$	T	$G R E I A$	$O b j G M$	T	$G R E G M$
111，69，224	34	7	6897.4	6412.5	289.57	7.03	6641.8	12.54	3.71
69，224，830	39	8	7921.9	7311.2	366.14	7.71	7598.4	22.16	4.08
224，830，836	44	9	8955.3	8355.6	347.28	6.70	8628.9	39.45	3.64
111，69，224，830	48	10	9735.2	9052.1	407.92	7.02	9355.5	42.51	3.90
830，836，71	52	11	10533.1	9845.6	442.14	6.53	10196.3	49.58	3.20
69，224，830，836	55	11	11241.8	10544.9	465.38	6.20	10798.9	42.83	3.94
224，830，836，71	66	13	13388.9	12599.5	572.88	5.90	12863.4	64.21	3.92
整体网络	86	18	17390.6	16299.5	897.54	6.27	16770.8	99.76	3.56
AVG						6.67			3.75

References 17

1	Jansen K， Mastrolilli M. Approximation schemes for parallel machine scheduling problems with controllable processing times［J］. Computers & Operations Research， 2004， 31（10）： 1565-1581.
2	Alidaee B， Ahmadian A. Two parallel machine sequencing problems involving controllable job processing times ［J］. European Journal of Operational Research， 1993， 70（3）： 335-341.
3	郭苗苗，刘桓，王吉波，等.具有学习效应和加工时间可控的平行机排序问题［J］. 运筹与管理， 2018， 27（3）： 113-125.
	Guo M M， Liu H， Wang J B， et al. Parallel machine sequencing problem with learning effect and controllable processing time［J］. Operations and Management， 2018， 27（3）： 113-125.
4	Zou Y Q， Wang D J， Lin W， et al. Two-stage three-machine assembly scheduling problem with sum-of-processing-times- based learning effect［J］. Soft Computing， 2019，24（4）：1-18.
5	Kang Q， Wang J B， Zhou M C， et al. Centralized charging strategy and scheduling algorithm for electric vehicles undera battery swapping scenario［J］. IEEE Transactions on Intelligent Transportation Systems， 2016， 17（3）： 659-669.
6	Chen H M， Hu Z C， Xu Z W， et al. Coordinated charging strategies for electric bus fast charging stations ［C］// IEEE PES Asia-Pacific Power and Energy Engineering Conference， Xi’an， China，October 25-28， IEEE， 2016： 1174-1179.
7	Ke B R， Chung C Y， ChenYC. Minimizing the costs of constructing an allplug-in electric bus transportation system： A case study in Penghu［J］. Applied Energy， 2016， 177： 649-660.
8	Qin N， Gusrialdi A， Brooker R P， et al. Numerical analysis of electric bus fast charging strategies for demand charge reduction［J］. Transportation Research Part A：Policy and Practice， 2016， 94： 386-396.
9	Liu Z C， Song Z Q， He Y. Economic analysis of on-route fast charging for battery electric buses： Case study in Utah［J］. Transportation Research Record， 2019， 2673（5）： 119-130.
10	Wang Y S， Huang Y X， Xu J P， et al. Optimal recharging scheduling for urban electricbuses： A case study in Davis［J］. Transportation Research Part E：Logistics and Transportation Review，2017， 100： 115-132.
11	杨健维，杨鹤，张夏霖，等.基于换电规则优化与车辆-电池组匹配的电动公交车充换电站充电优化策略［J］. 中国电机工程学报， 2019， 39（8）： 2337-2347.
	Yang J W， Yang H， Zhang X S， et al. Charging optimization strategy of electric bus charging and swapping station based on power swap rule optimization and vehicle-battery pack matching［J］. Chinese Journal of Electrical Engineering， 2019， 39（8）： 2337-2347.
12	陈丽娟，秦萌，顾少平，等.计及电池损耗的电动公交车参与V2G的优化调度策略［J］.电力系统自动化， 2020， 44（11）： 52-60.
	Chen L J， Qin M， Gu S P， et al. The optimal dispatching strategy of electric buses taking into account battery loss participates in V2G［J］. Power System Automation， 2020， 44（11）： 52-60.
13	He Y， Song Z Q， Liu Z C. Fast-charging station deployment for battery electric bus systems considering electricity demand charges［J］. Sustainable Cities & Society， 2019， 48：10530.
14	Abdelwahed A， Berg P L V D， Brandt T， et al. Evaluating and optimizing opportunity fast-charging schedules in transit battery electric bus networks［J］. Transportation Science， 2020， 54（6）：1601-1615.
15	He Y， Liu Z C， Song Z Q.Optimal charging scheduling and management for a fast-charging battery electric bus system［J］. Transportation Research Part E：Logistics and Transportation Review， 2020， 142（23）：102056.
16	Ataka S， Kim B， Gen M. Optimal design of two‐stage logistics network considered inventory by boltzmann random key‐based GA［J］. Ieej Transactions on Electrical & Electronic Engineering， 2010， 5（2）， 195-202.
17	BrandãoJ S， NoronhaT F， ResendeM， et al. A biased random-key genetic algorithm for single-round divisible load scheduling［J］. International Transactions in Operational Research， 2015， 22（5）， 823-839.

文献	充电方式			考虑因素				求解方法
文献	夜间集中充电	白天机会充电	电池交换	电网负载	基础设施成本	电池损耗成本	峰谷分时电价	求解方法
Kang等			√		√		√	POS-GA
Chen等		√		√				Cplex HA
Ke等	√	√			√			Cplex GA
Qin等		√						Cplex
Wang等			√		√			Cplex
Liu等		√			√		√	Cplex
杨健维等			√					Gurobi
He等		√		√	√			Cplex
陈丽娟等		√		√		√		Cplex
Abdelwahed等		√		√				Cplex
本文	√			√		√	√	RK-IA HA

公交线	经停站	单程长度	公交车数量	班次间隔	运行时间窗
111路	51站	28.0km	9	20min	5:00-23:30
69路	40站	35.6km	11	20min	5:30-23:00
224路	43站	33.8km	14	12min	5:30-22:30
830路	69站	43.0km	14	20min	5:30-22:30
836路	51站	30.6km	16	10min	5:30-23:30
71路	48站	35.5km	22	10min	5:30-23:30

[1]	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.
[2]	Guohua Wu. Based on Hub-Spoke Network a Practice Heuristic Algorithm Applied to Airline Fleet Assignment [J]. Chinese Journal of Management Science, 2024, 32(1): 158-167.
[3]	GAO Hong-wei, LI Lu. Real-time Pricing Based on PMSC Management and Reward-Punishment Mechanism in Smart Grid [J]. Chinese Journal of Management Science, 2022, 30(7): 88-98.
[4]	XU Bao-guang, CHANG Jia-xin, GAO Min-gang. Research on Routing Problems about Road Information Collection Considering Mixed Mapping Method [J]. Chinese Journal of Management Science, 2022, 30(4): 218-227.
[5]	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.
[6]	LIU Wei-bo, ZHANG Hao-yue, ZHANG Jiang-hua. Research on Cross-region Patient Scheduling Problem Considering Travel Time and Machine Setup Time [J]. Chinese Journal of Management Science, 2021, 29(9): 180-187.
[7]	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.
[8]	ZHANG Bai-shang, FAN Gang-long, TAN Pang, JIA Yu-kui, YIN Ru-fa. Research on the Dynamic Collaborative Scheduling Optimization for Community Evacuation [J]. Chinese Journal of Management Science, 2019, 27(4): 190-197.
[9]	ZHANG Yang, DAN Bin, GAO Hua-Li. Stochastic Scheduling of Product Service System Orders with Due Date Assignment [J]. Chinese Journal of Management Science, 2019, 27(2): 93-106.
[10]	TANG Liang, HE Jie, JING Ke, JIN Zhi-hong. Collaborative Manufacturing Scheduling based on Improved Ant Colony Optimization Algorithm with Time Window Constraint [J]. Chinese Journal of Management Science, 2018, 26(4): 97-107.
[11]	YANG Jun, FENG Peng-xiang, SUN Hao, YANG Chao. Carbon Emission Reduction Cost-Sharing Model in Supply Chain Based on Improvingthe Demand for Low-Carbon Products [J]. Chinese Journal of Management Science, 2015, 23(9): 87-96.
[12]	XIAO Yi-yong, CHANG Wen-bing, ZHANG Ren-qian. A Research on Heuristic Production Planning with Dual Constraints of Capabilities and Resources [J]. Chinese Journal of Management Science, 2008, 20(6): 33-40.
[13]	LU Kui, YANG Chang-hui, Dai Dao-ming. A Heuristic Algorithm for Multi-Product Capacitated Lot Sizing with Subcontracting and Time-varying Transportation Costs [J]. Chinese Journal of Management Science, 2008, 16(1): 80-85.
[14]	QIAO Zhong, LI Ling-ying. A Bi-Level Programming Model for Location of Commodity Exchange Market Network Points [J]. Chinese Journal of Management Science, 2008, 16(1): 125-130.
[15]	LI Yan-hui, MA Shi-hua. An MINLP Model for the Single-Source and p-Median Distribution System Based on Time Constraints [J]. Chinese Journal of Management Science, 2004, (3): 86-90.

Charging Scheduling Optimization of Battery Electric Buses Considering Peak-Valley Electricity Price and Battery Damage Cost

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 17

Related Articles 15

Metrics

Comments

Recommended 0