需求响应型公交车辆调度及路径优化

Dispatch and Route Optimization of Demand-responsive Bus

针对高度分散和随机的客流状况,为尽可能降低运营成本、提高乘客满意度,研究了需求响应型公交车辆调度及路径优化。首先通过分析历史乘车站点需求频次,分时段提取了具有高频需求量的出行点作为高概率出行点,在此基础上建立了公交车辆调度及路径优化模型。其次,以历史公交运营数据为依据,运用大规模邻域搜索(LNS)遗传算法,在乘客需求出行时间和车容量限制的约束条件下,以公交系统运行里程最小为目标进行了静态车辆调度。最后,基于初始静态线路和后期实时出行需求,运用精确动态规划算法,以系统运行里程变化最小为目标进行了动态路径优化,实现需求及时响应。选取某区部分区域进行了分析应用。结果表明:采取提取高概率点策略的系统平均总成本为1.04×10^(4)元,而未采取该策略的系统平均总成本为4.38×10^(6)元,高概率点提取策略对系统成本节省影响明显;通过LNS遗传算法进行最短路径求解时,3次求解结果偏差为3.1%,较为稳定;在路径优化阶段,车辆满载率提升17.92%,乘客需求响应率保持较高水平;运营成本变动合理,人均成本减少1.08元,提高了车辆利用率和乘客满意度。基于站点提取策略的2阶段调度优化模型能提供合理的车辆实时调度和路径优化方案,为实际公交调度提供理论基础和应用指导。

In view of the highly dispersed and random passenger flow,in order to reduce operation cost as much as possible and improve passenger satisfaction,the dispatch and route optimization of demand-responsive bus are studied.First,by analyzing the demand frequency of historical bus stations,the travel points with high frequency demand in different periods are extracted as high probability travel points,and the model of bus scheduling and route optimization is established on this basis.Second,based on historical bus operation data,constraints of passenger demand travel time and vehicle capacity by using large-scale neighborhood search(LNS)genetic algorithm.Finally,based on the initial static line and the later real-time travel demand,with the goal of minimizing the mileage change of the bus system,the static vehicle scheduling is carried out by using the accurate dynamic programming algorithm to achieve timely response to the demand.The analysis and application of selected areas in a certain area are conducted.The result shows that(1)the average total cost of the system that adopts the strategy of extracting high probability points is 1.04×10^(4) RMB,while the average total cost of the system without this strategy is 4.38×10^(6) RMB,indicating that the high probability point extraction strategy has a significant influence on system cost saving;(2)when the shortest path is solved by LNS genetic algorithm,the deviation of 3 solution results is 3.1%,which is relatively stable;(3)at the route optimization stage,the vehicle full load rate is increased by 17.92%,and the passenger demand response rate remains at a high level;(4)the operation cost changes reasonably,the per capita cost reduced by 1.08 RMB,which improved vehicle utilization and passenger satisfaction.The 2-stage dispatching optimization model based on the station extraction strategy can provide reasonable real-time vehicle dispatching and route optimization scheme,and provide theoretical basis and application guidance for actual bus scheduling.