Electric Vehicle Scheduling in Public Transit with Capacitated Charging Stations
研究了充电站容量有限且允许部分充电的公共交通电动车辆调度问题，用列生成和两种启发式算法求解，在荷兰某公交线路数据上测试，潜水启发式算法在7小时内达到3%以内的最优性差距。
This paper considers the scheduling of electric vehicles in a public transit system. Our main innovation is that we take into account that charging stations have limited capacity, while also considering partial charging. To solve the problem, we expand a connection-based network in order to track the state of charge of vehicles and model recharging actions. We then formulate the electric vehicle scheduling problem as a path-based binary program, whose linear relaxation we solve using column generation. We find integer feasible solutions using two heuristics: price-and-branch and a diving heuristic, including acceleration strategies. We test the approach using data from the concession Gooi en Vechtstreek in the Netherlands, containing up to 816 trips. The diving heuristic outperforms the other heuristic and solves the entire concession within seven hours of computation time with an optimality gap of less than 3%. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0253 .