关键词: 调度优化, 电池损耗成本, 峰谷分时电价, 启发式算法

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