基于改进K最短路算法的公交线网优化研究  

Study on public transit network optimization based on improved K-shortest path algorithm

作　　者：丁建勋 钟业文 李棒 张实 DING Jianxun;ZHONG Yewen;LI Bang;ZHANG Shi(School of Automobile and Traffic Engineering, Hefei University of Technology, Hefei 230009, China;Key Laboratory of Process Optimization and Intelligent Decision Making of Ministry of Education, Hefei 230009, China;Hefei Public Transport Group Co., Ltd., Hefei 230011, China)

机构地区：[1]合肥工业大学汽车与交通工程学院,安徽合肥230009 [2]过程优化与智能决策教育部重点实验室,安徽合肥230009 [3]合肥公交集团有限公司,安徽合肥230011

出　　处：《合肥工业大学学报（自然科学版）》2019年第10期1388-1393,1423,共7页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金青年科学基金资助项目(71704046);安徽省自然科学基金资助项目(1808085QG225)

摘　　要：文章研究了公交场站选址和线网设计组合优化问题,建立以站间直达为关键约束的线网优化模型并给出求解算法。在所构建的公交网络中,利用改进的 K最短路算法和相应的路径筛选条件获得从节点出发的K最短路径树,找出符合条件的单个K最短路径树作为初始解;通过不同节点的K最短路径树的叠加、删除、替代的优化过程,获得最优的K最短路径树组合,得到最优的公交线路集、场站位置。算例结果表明:公交网络规模越大,所需场站越多;K值越大,所需场站越少;不同场站可相互配合进行布局,实现公交线网性能的提升。A combinatorial optimization problem of bus depot location and public transit network design is studied, and its optimization model requiring station-to-station line is proposed. The algorithm to solve the model is also designed. The K -shortest path tree based on any node is obtained by the improved K -shortest path algorithm and the corresponding conditions for filtering paths. And then a single K -shortest path tree meeting the criteria is set as the initial solution. Through the superposition, deletion and substitution of multiple K -shortest path trees of different nodes, the combination of K -shortest path trees with the optimal bus line set, locations of bus stations and depot number is obtained. The numerical example shows that the depot number increases with bus network sizes but decreases with K -values, and multiple depots could cooperate with each other to work out the layout, so as to improve the performance of the public transit network.

关 键 词：城市交通 公交线网优化模型 改进K最短路算法 公交网络 公交场站选址 

分 类 号：U491.17[交通运输工程—交通运输规划与管理]