Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints

REN Gang; WANG Wei

Volume 8 Issue 4

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2008 > 8(4): 84-89

Next Previous

REN Gang, WANG Wei. Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints[J]. Journal of Traffic and Transportation Engineering, 2008, 8(4): 84-89.

Citation:

REN Gang, WANG Wei. Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints[J]. Journal of Traffic and Transportation Engineering, 2008, 8(4): 84-89.

REN Gang, WANG Wei. Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints[J]. Journal of Traffic and Transportation Engineering, 2008, 8(4): 84-89.

Citation:

REN Gang, WANG Wei. Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints[J]. Journal of Traffic and Transportation Engineering, 2008, 8(4): 84-89.

PDF( 992 KB)

Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints

REN Gang,
WANG Wei

Jiangsu Provincial Key Laboratory of Transportation Planning and Management, Southeast University, Nanjing 210096, Jiangsu, China

More Information

Author Bio:
REN Gang(1976-), male, associate professor, PhD, +86-25-83795649, rengang@seu.edu.cn
Received Date: 2008-01-05
Publish Date: 2008-08-25

Abstract

Abstract

To analyze the difference and similarity between the shortest path characteristics and searching algorithms with and without turning constraints, dual graph theory was studied, the spanning tree of dual network was constructed with the shortest path set from a source node to all arcs in turning constraint network, the concept of dual shortest path tree(DSPT) was put forward and used for algorithm comparison.Analysis result shows that the present solution methods with turning constraints, including arc-labeling algorithm, node-labeling algorithm and dual-network method, can be unified into the same DSPT algorithmic frame, and have the same path searching strategies as the shortest path tree(SPT) algorithm without turning constraints; a prototype DSPT algorithm can be developed for the shortest path problem in networks with turning constraints, and more efficient algorithms can be designed according to different SPT labeling techniques.
- traffic network,
- dual shortest path tree,
- dual graph,
- turning constraint,
- prototype algorithm

FullText(HTML)

References(12)

References

[1]	MA Yong-feng, LU Jian, XI ANG Qiao-jun, et al. Optimalroute arithmetic with multigoalsin highway network based ontravel decision-making[J]. Journal of Traffic and Transportation Engineering, 2007, 7(3): 100-105. (in Chinese) http://transport.chd.edu.cn/article/id/200703021
[2]	XU Hong-mei, YANG Zhao-sheng, YAN Chang-wen, et al. Solving appoint order formjob problem based on ant colony system[J]. Journal of Chang an University: Natural Science Edition, 2007, 27(6): 84-86. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200706018.htm
[3]	LU Feng. Shortest path algorithms: taxonomy and advancein research[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(3): 269-275. (in Chinese) doi: 10.3321/j.issn:1001-1595.2001.03.016
[4]	LI Mao-sheng, WANG Wei. Traffic flow equilibrium analysis method based on road network sub-graph space[J]. China Journal of Highway and Transport, 2007, 20(2): 97-101. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200702018.htm
[5]	KIRBY R F, POTTS R B. The mini mumroute problem for networks with turn penalties and prohibitions[J]. Transportation Research, 1969, 3: 397-408. doi: 10.1016/S0041-1647(69)80022-5
[6]	ANEZ J, BARRA T, PEREZ B. Dual graph representation of transport networks[J]. Transportation Research Part B, 1996, 30(3): 209-216. doi: 10.1016/0191-2615(95)00024-0
[7]	ZILI ASKOPOULOS A K, MAHMASSANI HS. A note onleast time path computation considering delays and prohibitions for intersection movements[J]. Transportation Research Part B, 1996, 30(5): 359-367. doi: 10.1016/0191-2615(96)00001-X
[8]	WAN Xu-jun, HU An-zhou. Representation research ontransport networks[J]. China Journal of Highway and Transport, 1999, 12(4): 73-77. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL199904012.htm
[9]	WANG Feng-yuan, PAN Fu-quan, ZHANG Li-xia, 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) http://transport.chd.edu.cn/article/id/200501022
[10]	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) https://www.cnki.com.cn/Article/CJFDTOTAL-DNDX200401024.htm
[11]	REN Gang, WANG Wei. Turn-based algorithm for Logit traffic assignment[J]. Journal of Traffic and Transportation Engineering, 2005, 5(4): 101-105. (in Chinese) http://transport.chd.edu.cn/article/id/200504021
[12]	ZHENG Nian-bo, LI Qing-quan, XUJing-hai, et al. Abidi-rectional heuristic shortest path algorithm with turn prohibitions and delays[J]. Geomatics and Information Science of Wuhan University, 2006, 31(3): 256-259. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200603016.htm