基于优先级拓扑排序的可变线路式公交调度

Flex-route buses scheduling based on priority topological sorting

为提高可变线路式公交的服务水平,提出基于站点优先级拓扑排序的公交调度方法,依据出行需求确定有向无环图,综合到站便捷性、节点度以及乘车和落客需求等因素进行站点优先级标定,得到唯一的站点需求处理拓扑次序;建立以公交行驶成本和乘客广义出行成本最少为目标的调度模型,采用基于拓扑排序的遗传算法优化求解.以中国天津市385路公交为例进行验证分析,结果表明,与传统的调度方法或者按需求进行拓扑排序但不考虑优先级的调度方法相比,当出行需求水平高于预期时,本调度方法的公交人均行驶成本分别降低11.87%和6.85%,人均广义出行成本分别降低9.06%和3.28%,请求拒绝率降至7.68%.本研究方法具有更高的出行需求接运比例,可有效提高可变线路式公交服务质量和盈利水平,为出行者提供更好的公共交通运输服务.

In order to improve the service level of flex-route buses,a scheduling method based on station priority topology sequencing is proposed.According to the travel needs,the directed acyclic graph(DAG)is determined,and the station priority is calibrated based on the convenience of arrival,node degree,demand for boarding,and alighting,etc.The only topological order of station demand processing is obtained finally.A scheduling model aiming at minimizing travel costs of buses and generalized travel costs of passengers is established,which is optimized by genetic algorithm based on topological sorting.Using No.385 bus in Tianjin city as an example,the results show that compared with the traditional scheduling method and the method with topological sequencing of demand but without considering priority.The travel cost of buses per passenger of our scheduling method is reduced by 11.87%and 6.85%respectively,and the generalized travel cost per passenger is reduced by 9.06%and 3.28%respectively when the travel demand level is higher than expected.This method can effectively improve the service quality and profitability of flex-route buses,and has lower per capita driving cost and per capita generalized travel cost,as well as lower reservation rejection rate.