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

doi:10.13306/j.1672-3813.2015.03.001

CORC > 北京大学 > 软件与微电子学院

	时变公交网络的数学规划模型与算法; Mathematical Programming Model and Algorithm for Time-Varying Transit Network
	徐勇 ; 李杰 ; 安利平 ; 王平 ; CHU Chao-Hsien
刊名	复杂系统与复杂性科学
	2015
关键词	公交网络换乘次数换乘线路影射网络 public transport network transfer time transfer lines mapping network
DOI	10.13306/j.1672-3813.2015.03.001
英文摘要	大规模时变公交网络中最短路径精确查询的算法是公交网络寻径问题的研究难点之一,近似搜索算法的求解满意度不高,而精确搜索算法的效率又较低.针对公交网络的时变特性与不确定性,建立了时变公交网络模型.将公交最优路径选择问题分解为换乘次数与换乘线路的查询问题,给出了基于线路影射网络的换乘次数的查询算法和基于站点影射网络的换乘站点和乘车距离、乘车时间的计算方法,两种算法都是多项式算法,最后给出算例验证了该方法的有效性.; 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 inefficient. In this paper, a time-varying mathematical model for transit network is formulated according 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. ?, 2015, The Journal Agency of Complex System and Complexity Science. All right reserved.; 国家自然科学基金; 河北省自然科学基金; EI; 中文核心期刊要目总览(PKU); 中国科技核心期刊(ISTIC); 中国科学引文数据库(CSCD); 3; 1-6; 12
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/420820]
专题	软件与微电子学院
推荐引用方式 GB/T 7714	徐勇,李杰,安利平,等. 时变公交网络的数学规划模型与算法, Mathematical Programming Model and Algorithm for Time-Varying Transit Network[J]. 复杂系统与复杂性科学,2015.
APA	徐勇,李杰,安利平,王平,&CHU Chao-Hsien.(2015).时变公交网络的数学规划模型与算法.复杂系统与复杂性科学.
MLA	徐勇,et al."时变公交网络的数学规划模型与算法".复杂系统与复杂性科学 (2015).