Mathematical Programming Model and Algorithm for Time-Varying Transit Network
XU Yong1, LI Jie2, AN Liping3, WANG Ping4, CHU Chao-Hsien5
1. School of Science, Hebei University of Technology, Tianjin 300401, China; 2. School of Software and Microelectronics at Wuxi, Peking University, Wuxi 214125, China; 3. School of Business, Nankai University, Tianjin 300072, China; 4. School of Software and Microelectronics, Peking University, Beijing 100260, China; 5. School of Information Systems, Singapore Management University, Singapore 178902
Abstract：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.
徐勇, 李杰, 安利平, 王平, CHU Chao-Hsien. 时变公交网络的数学规划模型与算法[J]. 复杂系统与复杂性科学, 2015, 12(3): 1-6.
XU Yong, LI Jie, AN Liping, WANG Ping, CHU Chao-Hsien. Mathematical Programming Model and Algorithm for Time-Varying Transit Network[J]. Complex Systems and Complexity Science, 2015, 12(3): 1-6.
[1] Ernesto C, Stefano G, Marco P. Transit network design: a procedure and an application to a large urban area[J]. Transportation Research Part C, 2012, 20(1): 3-14. [2] Antonio M, María E U. A route set construction algorithm for the transit network design problem[J]. Computers & Operations Research, 2009, 36(8): 2440-2449. [3] Ceder A, Wilson N. Bus network design[J]. Transportation Research Part B, 1986, 20 (4): 331-344. [4] Baaj M H, Mahmassani H. An AI-based approach for transit route system planning and design[J]. Journal of Advanced Transportation, 1991, 25 (2): 187-210. [5] Tong C O, Wong S C. A stochastic transit assignment model using a dynamic schedule-based network[J]. Transportation Research Part B, 1998, 33(2): 107-121. [6] Zhao F, Ubaka I. Optimization of transit network to minimize transfers and optimize route directness[J]. Journal of Public Transportation. 2004, 7(1): 63-82. [7] 邸振.基于最少换乘的公交系统网络配流模型及算法[J].系统科学学报,2011, 19(3): 78-81. Di Zhen. An assignment model for transit network based on the least transfer[J]. Journal of Systems Science. 2011, 9 (3): 78-81. [8] 四兵锋,高自友.城市公交网络均衡配流模型及算法的研究[J].公路交通科技,1998,9(3): 41-44. Si Bingfeng, Gao Ziyou. A study on the equilibrium assignment model and algorithm for urban transit network[J]. Journal of Highway and Transportation Research and Development, 1998, 9(3): 41-44. [9] 宋一凡,高自友.拥挤条件下的公交平衡配流[J].中国公路学报,1999,12(4): 88-95. Song Yifan, Gao Ziyou. Transit equilibrium assignment for congested public transport systems[J]. China Journal of Highway and Transport, 1999, 12(4): 88-95. [10] 高自友,宋一凡,四兵锋,等.公交网络中基于弹性需求和能力限制条件下的SUE配流模型及算法(Ⅰ)[J].北方交通大学学报,2000,24(6): 1-7. Gao Ziyou, Song Yifan, Si Binfeng, et al. A SUE Assignment model and solution algorithm with elastic transit demand and bottlenecks for public transport networks (I)[J].Journal of Northern Jiaotong University, 2000, 24(6): 1-7. [11] 高自友,宋一凡,四兵锋,等.公交网络中基于弹性需求和能力限制条件下的SUE配流模型及算法(Ⅱ)[J].北方交通大学学报,2000,24(6):8-13. Gao Ziyou, Song Yifan, Si Binfeng, et al. a SUE assignment model and solution algorithm with elastic transit demand and bottlenecks for public transport networks (II)[J].Journal of Northern Jiaotong University, 2000, 24(6): 8-13. [12] 钱臻,陆化普.一种公交网络客流分配方法及其实用性研究[J].清华大学学报(自然科学版), 2005, 45(9): 1170-1174. Qian Zhen, Lu Huapu. An assignment method for transit network and its practical application[J].Journal of Tsinghua University (Science and Technology), 2005, 45(9):1170-1174. [13] 伍雁鹏,彭小奇,黄同成.基于路径集合运算的公交网络寻径算法研究[J].计算机科学,2009,36(6):239-272. Wu Yanpeng, Peng Xiaoqi, Huang Tongcheng. Research on path set operation based algorithm for path searching in public transit network[J]. Computer Science, 2009, 36(6): 239-272. [14] 苏爱华,施法中.公交网络换乘问题的一种实现[J].工程图学学报,2005, (4): 55-59. Su Aihua, Shi Fazhong. Optimal route choice of public traffic network based on shortest path searching[J]. Journal of Engineering Graphics, 2005, (4): 55-59. [15] 姚春龙, 李旭, 沈岚. 公交出行最优路径搜索的有向赋权图模型[J]. 计算机应用研究, 2013, 30(4): 1058-1063. Yao Chunlong, Li Xu, Shen Lan. Weighted directed graph model for searching optimal travel routes by public transport[J]. Application Research of Computers, 2013, 30(4):1058-1063. [16] 徐勇,李杰,张军芳,等.新型公交网络模型与最优线路选择算法[J].系统工程理论与实践,2011,31(11):2234-2240. Xu Yong, Li Jie, Zhang Junfang, et al. New urban transit network models and optimal path searching algorithm[J]. Systems Engineering-Theory and Practice, 2011, 31(11): 2234-2240. [17] 温金辉,刘伟铭.用于最短路算法的公交网络模型构建[J].交通标准化,2011,8(243):177-178. Wen Jinhui, Liu Weiming. Public transit network modeling for shortest path algorithm[J]. Transport Standardization, 2011, 8(243): 177-178. [18] 周媛,邓卫,胡启洲.基于遗传禁忌算法的城市公交线网优化研究[J].武汉理工大学学报(交通科学与工程版),2011,35(01):42-45. Zhou Yuan, Deng Wei, Hu Qizhou. Study on the optimization of public transit network based on genetic algorithm and tabu search algorithm[J]. Journal o f Wuhan University of Technology (Transportation Science & Engineering), 2011, 35(1): 42-45. [19] 许伦辉,林泉.基于GBAS的公交出行最优路径选择算法[J].公路交通科技,2010,27(3):154-158. Xu Lunhui, Lin Quan. Transit trip optimal route choice algorithm based on GBAS[J]. Journal of Highway and Transportation Research and Development, 2010, 27(3): 154-158. [20] 周文峰,李珍萍,刘洪伟,等.最优公交线路选择问题的数学模型及算法[J].运筹与管理,2008,17(5): 80-84. Zhou Wenfeng, Li Zhenping, Liu Hongwei, et al. Mathematical models and algorithms of optimal public transportation line choice problem[J]. Operations Research and Management Science, 2008, 17(5): 80-84. [21] 伍雁鹏,彭小奇,杨恒伏.改进的基于关系数据库技术的公交查询算法[J].中南大学学报(自然科学版), 2009,4(3):763-766. Wu Yanpeng, Peng Xiaoqi, Yang Hengfu. Improved algorithm based on relational database technology for querying transit network[J].Journal of Central South University (Science and Technology). 2009,4(3): 763-766. [22] 张淑娟,浮寸萍,金淑英.最短路径算法用于城市公交出行路径最优化[J].现代测绘,2006,4:37-44. Zhang Shujuan, Fu Cunping, Jin Shuying. The application of the shortest path algorithm in the research of the best way of city bus[J]. Mo-dern Surveying and Mapping, 2006, 4: 37-44. [23] 乔梁,黄加翼,李云霄.基于A*算法城市急救救援最有路径决策[J].国防科技,2011,3:8-10. Qiao Liang, Huang Jiayi, Li Yunxiao. The path decision based on A* for city emergency rescue[J]. Journal of National Defense Science and Technology, 2011, 3: 8-10. [24] Li S G, Su Y M. Optimal transit path finding algorithm based on geographic information system[C].2003 IEEE Proceedings of Intelligent Transportation Systems, 2003, 2: 1670-1673.
