Calculating Multiple Optimal Routes Based on Link-to-link Transition Sampling

LI Jun; GUO Yuwei; YE Wei

doi:10.6054/j.jscnun.2022061

Journal of South China Normal University (Natural Science Edition) > 2022 > 54(4): 82-88. > DOI: 10.6054/j.jscnun.2022061

LI Jun, GUO Yuwei, YE Wei. Calculating Multiple Optimal Routes Based on Link-to-link Transition Sampling[J]. Journal of South China Normal University (Natural Science Edition), 2022, 54(4): 82-88. DOI: 10.6054/j.jscnun.2022061

Citation:

PDF (1546 KB)

Calculating Multiple Optimal Routes Based on Link-to-link Transition Sampling

School of Intelligent Systems Engineering/Guangdong Provincial Key Laboratory of Intelligent Transportation System, Sun Yat-sen University, Guangzhou 510006, China

More Information

Received Date: July 11, 2021
Available Online: September 21, 2022

Graphical Abstract

Abstract

Abstract

A link-to-link transition sampling method utilizing the historic data of link-to-link transition probability to obtain the multiple optimal routes between the given origin and destination in a road network (method of link-to-link transition probability for multiple optimal routes) was proposed to avoid the need of calculating the link travel times. Firstly, the link-to-link transition probabilities were calculated with travel data of time and region division. The impacts of traffic conditions were taken into account according to time division. And the problems of the large number of starting points and ending points and the insufficient data of specific point pairs in the road network were avoided by replacing the given starting point and ending point with the traffic zone. And multiple optimal routes were calculated with route sampling based on the link-to-link transition probability. The proposed method demonstrated the advantages of no need to calculate the link travel time, low requirement of data and easy implementation. A case study showed that the optimal routes obtained with the proposed method are much in accordance with the actual optimal routes. The size of traffic zones has minor impacts on the results, and the division of periods can effectively reflect the traffic conditions.
- traffic engineering,
- multiple optimal routes,
- link-to-link transition sampling,
- link-to-link transition probability

FullText(HTML)

References (15)

References

[1]	胡正华, 王尚媛. 基于多细节路网Voronoi层次模型的最优路径算法[J]. 华南师范大学学报(自然科学版), 2019, 51(3): 88-93. doi: 10.6054/j.jscnun.2019049 HU Z H, WANG S Y. An optimal routing algorithm based on the hierarchical model of Voronoi-graphs with level of detail[J]. Journal of South China Normal University(Na-tural Science Edition), 2019, 51(3): 88-93. doi: 10.6054/j.jscnun.2019049
[2]	CHEN M, YU X H, LIU Y. Mining moving patterns for predicting next location[J]. Information Systems, 2015, 54: 156-168. doi: 10.1016/j.is.2015.07.001
[3]	KRUMM J. A Markov model for driver turn prediction[J]. SAE World Congress, 2016, 22(1): 1-25.
[4]	WANG H J, YANG Z, SHI Y C. Next location prediction based on an Adaboost-Markov model of mobile users[J]. Sensors, 2019, 19(6): 1-19. doi: 10.1109/JSEN.2018.2885911
[5]	高法钦. 一种基于概率的路径预测与查询算法[J]. 计算机科学, 2016, 43(8): 207-211. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201608042.htm GAO F Q. Path prediction and query algorithm based on probability[J]. Computer Science, 2016, 43(8): 207-211. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201608042.htm
[6]	WANG X P, MA Y, DI J, et al. Building efficient probability transition matrix using machine learning from big data for personalized route prediction[J]. Procedia Computer Science, 2015, 53(1): 284-291.
[7]	ZHUANG Y, FONG S, YUAN M, et al. Predicting the next turn at road junction from big traffic data[J]. Journal of Supercomputing, 2017, 73(7): 3128-3148. doi: 10.1007/s11227-017-2013-y
[8]	李军, 郭育炜, 叶威. 基于路段间转移概率的最优路径预测方法[J]. 交通运输系统工程与信息, 2021, 21(1): 36-40;61. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT202101007.htm LI J, GUO Y W, YE W. Predicting optimal route based on link-to-link transition probability[J]. Journal of Transportaton Systems Engineering and Information Technology, 2021, 21(1): 36-40;61. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT202101007.htm
[9]	HE Y B, ZHANG F, LI Y, et al. Multiple routes recommendation system on massive taxi trajectories[J]. Tsinghua Science and Technology, 2016, 21(5): 510-520. doi: 10.1109/TST.2016.7590320
[10]	HUANG Z X, JIANG X J, HAO W. A proportional-switch adjustment model towards mixed equilibrium with multi-route choice behaviour criterion[J]. Journal of Advanced Transportation, 2020(11): 1-16.
[11]	王树西, 李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J]. 计算机科学, 2014, 41(6): 217-224. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201406043.htm WANG S X, LI A Y. Multi-adjacent-vertexes and multi-shortest paths problem of Dijkstra algorithm[J]. Computer Science, 2014, 41(6): 217-224. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201406043.htm
[12]	HU X B, CHIU Y C. A constrained time-dependent K shortest paths algorithm addressing overlap and travel time deviation[J]. International Journal of Transportation Science and Technology, 2015, 4(4): 371-394. doi: 10.1016/S2046-0430(16)30169-1
[13]	FLǑTTERǑD G, BIERLAIRE M. Metropolis-hastings sampling of paths[J]. Transportation Research Part B: Methodological, 2011, 48: 53-66.
[14]	MANLEY E. Estimating urban traffic patterns through probabilistic interconnectivity of road network junctions[J]. PLoS ONE, 2015, 10(5): 1-17.
[15]	LEE M, SOHN K. Inferring the route-use patterns of me-tro passengers based only on travel-time data within a Bayesian framework using a reversible-jump Markov chain Monte Carlo (MCMC) simulation[J]. Transportation Research Part B: Methodological, 2015, 81: 1-17.

Cited By

Cited by

Periodical cited type(1)

温雨柔，王浩洋，赵翔，温雅梅，纪利春，赵霜，杜玉英. 咔唑基化学传感器识别各种阴离子研究进展. 化学试剂. 2023(03): 74-84 .

Other cited types(0)

Get Citation

PDF

XML

Article views (322) PDF downloads (73) Cited by(1)

Turn off MathJax

Article Contents

Abstract

References

Calculating Multiple Optimal Routes Based on Link-to-link Transition Sampling

Abstract

References

Cited by

Periodical cited type(1)

Other cited types(0)

Catalog

Export File

Citation

Format

Content