时变公交网络的数学规划模型与算法  

Mathematical Programming Model and Algorithm for Time-Varying Transit Network

作　　者：徐勇[1] 李杰[2] 安利平[3] 王平[4] CHU Chao-Hsien 

机构地区：[1]河北工业大学理学院,天津300401 [2]北京大学软件与微电子学院无锡基地,江苏无锡214125 [3]南开大学商学院,天津300072 [4]北京大学软件与微电子学院,北京100260 [5]新加坡管理大学信息系统学院,新加坡178902

出　　处：《复杂系统与复杂性科学》2015年第3期1-6,共6页Complex Systems and Complexity Science

基　　金：国家自然科学基金(71071079);河北省自然科学基金(A2013202198)

摘　　要：大规模时变公交网络中最短路径精确查询的算法是公交网络寻径问题的研究难点之一,近似搜索算法的求解满意度不高,而精确搜索算法的效率又较低。针对公交网络的时变特性与不确定性,建立了时变公交网络模型。将公交最优路径选择问题分解为换乘次数与换乘线路的查询问题,给出了基于线路影射网络的换乘次数的查询算法和基于站点影射网络的换乘站点和乘车距离、乘车时间的计算方法,两种算法都是多项式算法,最后给出算例验证了该方法的有效性。The shortest path query problem in large scale time-varying transit network is NP- hard. Approximate search algorithm is not satisfactory, and the exact search algorithm is ineffi- cient. In this paper, a time-varying mathematical model for transit network is formulated accord- ing to the time-varying and uncertainty characteristic of public transport network. The choice of the optimal path for transit network is decomposed into transfer times and transfer line query problem. A query algorithm for transfer times is proposed based on the line mapping network and an algorithm for both transfer site and travel distance is proposed based on site mapping network. Both of them are polynomial. Finally we use a numerical example to illustrate the solution process of the proposed method.

关 键 词：公交网络 换乘次数 换乘线路 影射网络 

分 类 号：U491[交通运输工程—交通运输规划与管理] O121[交通运输工程—道路与铁道工程]