[1] Gu Cheng, Ren Gang,. Implementation and comparative testing of turn-based algorithmfor logit network loading [J]. Journal of Southeast University (English Edition), 2011, 27 (3): 316-321. [doi:10.3969/j.issn.1003-7985.2011.03.018]
Copy
Implementation and comparative testing of turn-based algorithmfor logit network loading(
)
基于转向的Logit网络分配算法实现与比较测试
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 27
- Issue:
- 2011 3
- Page:
- 316-321
- Research Field:
- Traffic and Transportation Engineering
- Publishing date:
- 2011-09-30
Info
- Title:
- Implementation and comparative testing of turn-based algorithmfor logit network loading
- 基于转向的Logit网络分配算法实现与比较测试
- Keywords:
- TALL algorithm; network expanding; deque structure; bidirectional star; arc-labeling shortest path searching
- PACS:
- U491.1
- DOI:
- 10.3969/j.issn.1003-7985.2011.03.018
- Abstract:
- In order to evaluate the practicality and effectiveness of the turn-based algorithm for logit loading(TALL), the TALL is implemented using C++, and it is compared with a combination of the network-expanding method and the Dial algorithm based on the analysis of algorithm procedures. The TALL uses the arc-labeling shortest path searching, bidirectional star and the deque structure to directly assign the traffic flow, while the Dial algorithm should be used in an expanded network. The test results over realistic networks of eight cities show the superior performance of the TALL algorithm over the combination of the network-expanding method and the Dial algorithm, and the average processing time is reduced by 55.4%. Furthermore, it is found that the operational efficiency of the TALL relates to the original densities of the cities. The average processing time is reduced by 65.1% when the original density is about 14%, but the advantage of the TALL is not obvious with the increase in the original density.
- 为了评价基于转向的Logit网络分配算法(TALL)的实用性和高效性, 在分析TALL算法过程的基础上, 运用C++实现了TALL算法, 并与传统的Dial算法+网络扩展法进行比较测试.TALL算法运用弧标号最短路径搜索、双向星形表和Deque结构, 直接对道路网络进行流量分配, 而不像Dial算法要在扩展后的路网上应用.在实际8个不同大小城市的路网比较测试结果表明:TALL算法在时间效率方面表现明显优于Dial算法+网络拓展法, 平均运行时间减少55.4%;TALL算法运算效率与城市路网起点密度有很大关系.当起点密度在14%左右时, 平均运算时间减少65.1%, 但随着起点密度的增加, TALL算法的优势变得不明显.
References:
[1] Yu N. A class of bush-based algorithms for the traffic assignment problem [J]. Transportation Research Part B, 2010, 44(1): 73-89.
[2] Dial R B. A probabilistic multipath traffic assignment algorithm which obviates path enumeration [J]. Transportation Research, 1971, 5(2): 83-111.
[3] Powell W B, Sheffi Y. The convergence of equilibrium algorithms with predetermined step sizes [J]. Transportation Science, 1982, 16(1): 45-55.
[4] Patriksson M. The traffic assignment problem: models and methods [M]. Utrecht, The Netherlands: V.S.P. Intl Science, 1994.
[5] Leurent F M. Curbing the computational difficulty of the logit equilibrium assignment model [J]. Transportation Research Part B, 1997, 31(4): 315-326.
[6] Bell M G H. Alternative to Dial’s logit assignment algorithm [J]. Transportation Research Part B, 1995, 29(4): 287-295.
[7] Akamatsu T. Cyclic flows, Marcov process and stochastic traffic assignment [J]. Transportation Research Part B, 1996, 30(5): 369-386.
[8] Bertsekas D P, Gafni E M, Gallager R G. Second derivative algorithms for minimum delay distributed routing in networks [J]. IEEE Transactions on Communications, 1984, 32(8): 911-919.
[9] Bar-Gera H. Origin-based algorithm for the traffic assignment problem [J]. Transportation Science, 2002, 36(4): 398-417.
[10] Damberg O, Lundgren J T, Patriksson M. An algorithm for the stochastic user equilibrium problem [J]. Transportation Research Part B, 1996, 30(2): 115-131.
[11] Liu H S, Fu Y. Stochastic user equilibrium assignment model based on travel trait [J]. China Journal of Highway and Transport, 2004, 17(4):93-118.(in Chinese)
[12] Meneguzzer C. An equilibrium route choice model with explicit treatment of the effect of intersections [J]. Transportation Research Part B, 1995, 29(5): 329-356.
[13] Wang F Y, Pan F Q, Zhang L X, et al. Optimal path algorithm of road network with traffic restriction [J]. Journal of Traffic and Transportation Engineering, 2005, 5(1): 92-95.(in Chinese)
[14] Ren Gang, Wang Wei, Deng Wei. Shortest path problem with turn penalties and prohibitions and its solutions [J]. Journal of Southeast University: Natural Science Edition, 2004, 34(1): 104-108.(in Chinese)
[15] Ren Gang, Wang Wei. A turn-based algorithm for solving the logit type network loading problem [C]//Proceedings of 2009 IEEE International Joint Conference on Computational Sciences and Optimization. Nanjing, China, 2009:89-94.
[16] Ren Gang. Traffic assignment models and algorithms with traffic management [M]. Nanjing: Southeast University Press, 2007.(in Chinese)
Memo
- Memo:
-
Biographies: Gu Cheng(1984—), male, graduate; Ren Gang(corresponding author), male, doctor, researcher, rengang@seu.edu.cn.
Foundation items: National Science and Technology Action Program for Road Traffic Safety(No.2009BAG13A05), the National Natural Science Foundation of China(No.51078086).
Citation: Gu Cheng, Ren Gang. Implementation and comparative testing of turn-based algorithm for logit network loading[J].Journal of Southeast University(English Edition), 2011, 27(3):316-321.[doi:10.3969/j.issn.1003-7985.2011.03.018]