基于列生成算法的电动公交车辆调度计划优化研究

在公交运营规划过程中，公交车辆计划问题是编制时刻表和调度驾驶员的连接纽带，是公交运营规划过程中的关键问题.相对于传统公交车，电动公交车具有绿色环保，运营里程短，充电资源少等特点.在运营规划方面，电动公交车车辆计划模型约束多，计算难度大.本文应用整数规划，网络流等基本理论，将车次任务，公交场站，充电站作为节点，将车次间的空驶作为边，把电动公交车的车辆计划问题转化为网络模型.在网络模型的基础上应用列生成方法，对电动公交的车辆计划问题进行求解.在实验部分，将列生成算法分别应用于随机生成数据和实际数据.实验结果中，列生成算法结果相比现在使用方案最多节省了1 辆电动车，成本优化最高为8.3%，表明列生成算法在求解电动公交车辆计划问题时效率高，优化结果较好.

Battery Electric Transit Bus Scheduling Problem Based on Column Generation Approach

As the key problem in the process of public transit planning, bus scheduling is the connection of timetabling and driver rostering. Compared with traditional bus, the battery electric (BE) transit bus is environmental and short mileage. From the planning point of view, the new characteristics of BE bus brings challenges to the traditional planning method. In this paper, the depot, recharge station and trips are regarded as points, the deadheading between points are regarded as arcs, we formulate the BE bus schedule as a directed network. A tailed column generation approach is employed to solve the BE scheduling problem. Both random and actual data sets are used to test our approach, the results show that the tailed column generation approach performs well in solving the BE scheduling problem.