Constrained <i>K</i>-shortest Paths Algorithm to Prevent the Congestion Shifting Problem

WANG Yuan; YANG Zhao-sheng; GAO Peng

doi:10.3969/j.issn.0254-0037.2009.03.010

Journal of Beijing University of Technology > 2009 > 35(3): 345-349. > DOI: 10.3969/j.issn.0254-0037.2009.03.010

WANG Yuan, YANG Zhao-sheng, GAO Peng. Constrained K-shortest Paths Algorithm to Prevent the Congestion Shifting Problem[J]. Journal of Beijing University of Technology, 2009, 35(3): 345-349. DOI: 10.3969/j.issn.0254-0037.2009.03.010

Citation:

PDF (321 KB)

Constrained K-shortest Paths Algorithm to Prevent the Congestion Shifting Problem

College of Transportation, Jilin University, Changchun 130022, China

More Information

Received Date: July 20, 2008
Available Online: December 06, 2022

Graphical Abstract

Abstract

Abstract

For a better solution of the congestion shifting problem in Urban Traffic Flow Guidance System (UTFGS),this paper analyzes the root causes of the congestion shifting problem and develops a constrained K-shortest paths algorithm suitable for the travelers.With the realization in the basis of MapX Control,the actual effect of this algorithm is tested with the micro simulation tool VISSIM. Conclusions could be drawn as follows,the constrained K-shortest paths algorithm can efficiently prevent the congestion shifting problem,so that both the travelers and the whole system could benefit a lot from this.

FullText(HTML)

References (11)

References

[1]	杨兆升.城市交通流诱导系统[M].北京:中国铁道出版社,2004:169-170.
[2]	姜桂艳,郑祖舵,白竹,等.交通拥挤漂移的形成机理与预防技术[J].交通运输工程学报,2007,7(4):93-97. JIANG Gui-yan,ZHENG Zu-duo,BAI Zhu,et al.Causes and preventive technologies of traffic congestion shift[J].Journal of Traffic and Transportation Engineering,2007,7(4):93-97.(in Chinese)
[3]	张国强,晏克非.车辆动态导航中Braess悖论的解决方法及其算法设计[J].西安公路交通大学学报,2001,21(4): 29-32. ZHANG Guo-qiang,YAN Ke-fei.Solution of braess' paradox in dynamic vehicle navigation and its design algorithms[J]. Journal of Xi'an Highway University,2001,21(4):29-32.(in Chinese)
[4]	HOFFMAN W,PAVLEY R.A method for the solution of the Nth best path problem[J].Journal of the Association for Computing Machinery,1959,6:506-514.
[5]	BELLMAN R,KABALA R.On Kth best policies[J].Journal of SIAM,1996,8:582-585.
[6]	SHIER R D.On algorithms for finding the K shortest paths in a network[J].Networks,1979,7(3):341-352.
[7]	EPPSTEIN D.Finding the K shortest paths[C]//Proceeding of the 35th An-nual Symposium on Foundations of Computer Science.USA:IEEE,1994:154-165.
[8]	YEN J Y.Finding the K shortest loopless paths in a network[J].Management Science,1971,17(11):716-721.
[9]	LAWLER.Combinatorial Optimization:Networks and Matroids[M].New York:Courier Dover Publications,1976: 92-104.
[10]	Microsoft Corporation.Visual basic 6.0 programmer's guide[M].USA:Microsoft Press,1999:1172-1205.
[11]	李连营,李清泉.基于MapX的GIS应用开发[M].武汉:武汉大学出版社,2003:111-154.

Cited By

Get Citation

PDF

XML

Article views (18) PDF downloads (8)

Turn off MathJax

Article Contents

Abstract

References

Constrained K-shortest Paths Algorithm to Prevent the Congestion Shifting Problem

Abstract

References

Catalog

Export File

Citation

Format

Content