Autosoft Journal

Online Manuscript Access


Simulation of Real-Time Path Planning for Large-Scale Transportation Network Using Parallel Computation



Abstract

To guarantee both the efficiency and accuracy of the transportation system, the real-time status should be analyzed to provide a reasonable plan for the near future. This paper proposes a model for simulating the real-world transportation networks by representing the irregular road networks with static and dynamic attributes, and the vehicles as moving agents constrained by the road networks. The all pairs shortest paths (APSP) for the networks are calculated in a real-time manner, and the ever-changing paths can be used for navigating the moving vehicles with real-time positioning devices. In addition, parallel computation is used to accelerate the shortest path searching and vehicle navigation. The testing results suggest that considerable time reduction can be realized in comparison with the non-real-time computations. This finding demonstrates that the proposed model is useful in improving the efficiency of a large-scale transportation system.


Keywords


Pages

Total Pages: 13

DOI
10.31209/2018.100000013


Manuscript ViewPdf Subscription required to access this document

Obtain access this manuscript in one of the following ways


Already subscribed?

Need information on obtaining a subscription? Personal and institutional subscriptions are available.

Already an author? Have access via email address?


Published

Online Article

Cite this document


References

L. B. Alexandre, and Gabriel, C., Teodor. (2005). A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Computers and Operations Research, 32(7), 1685-1708. https://doi.org/10.1016/j.cor.2003.11.023

T. Alfaro, and Riff, M.-C. (2008). An Evolutionary Navigator for Autonomous Agents on Unknown Large-Scale Environments. Intelligent Automation and Soft Computing, 14(1), 105-116. https://doi.org/10.1080/10798587.2008.10642986

L. An, Linderman, M., Qi, J., Shortridge, A., and Liu, J. (2005). Exploring complexity in a human-environment system: an agent-based spatial model for multidisciplinary and multiscale integration. Annals of the association of American Geographers, 95(1), 54-79. https://doi.org/10.1111/j.1467-8306.2005.00450.x

M. M. Artimy, Robertson, W., and Phillips, W. J. (2005). Assignment of dynamic transmission range based on estimation of vehicle density. Paper presented at the International Workshop on Vehicular Ad Hoc Networks, Vanet 2005, Cologne, Germany, September. https://doi.org/10.1145/1080754.1080761

M. Bakillah, Liang, S., Mobasheri, A., Jokar Arsanjani, J., and Zipf, A. (2014). Fine-resolution population mapping using OpenStreetMap points-of-interest. International Journal of Geographical Information Science, 28(9), 1940-1963. https://doi.org/10.1080/13658816.2014.909045

M. Batty, and Xie, Y. (1994). From cells to cities. Environment and Planning B: Planning and Design, 21(7), 31-48. https://doi.org/10.1068/b21S031

M. Batty, Xie, Y., and Sun, Z. (1999). Modeling urban dynamics through GIS-based cellular automata. Computers, environment and urban systems, 23(3), 205-233. https://doi.org/10.1016/S0198-9715(99)00015-0

R. Bellman, (1958). On a Routing Problem. Quarterly Appl Math, 16(1), 87-90. https://doi.org/10.1090/qam/102435

V. Bonifaci, (2013). Physarum can compute shortest paths: A short proof. Information Processing Letters, 113(1-2), 4-7. https://doi.org/10.1016/j.ipl.2012.09.005

C. J. Castle, and Crooks, A. T. (2006). Principles and concepts of agent-based modelling for developing geospatial simulations. Paper presented at the Ucl Centre for Advanced Spatial Analysis, University College London: London, UK.

G. L. Chang, Junchaya, T., and Zhuang, L. (1994). A user-optimum route navigation model with a massively parallel computing architecture. Transportation Planning and Technology, 18(2), 107-129. https://doi.org/10.1080/03081069408717537

B. Chen, and Cheng, H. H. (2010). A review of the applications of agent technology in traffic and transportation systems. Intelligent Transportation Systems, IEEE Transactions on, 11(2), 485-497. https://doi.org/10.1109/TITS.2010.2048313

Y.-L. Chen,, and Yang, H.-H. (2000). Shortest paths in traffic-light networks. Transportation Research Part B: Methodological, 34(4), 241-253. https://doi.org/10.1016/S0191-2615(99)00023-5

Y. Chen, Li, X., Wang, S., and Liu, X. (2012). Defining agents” behaviour based on urban economic theory to simulate complex urban residential dynamics. International Journal of Geographical Information Science, 26(7), 1155-1172. https://doi.org/10.1080/13658816.2011.626780

Clarke, Keith C. "Cellular Automata and Agent-Based Models." Handbook of Regional Science (2013): 1217-1233. Crossref. Web. https://doi.org/10.1007/978-3-642-23430-9_63

T. H. Cormen, Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Introduction to algorithms (Vol. 2): MIT press Cambridge. G. J. Katz, and Kider Jr, J. T. (2008). All-pairs shortest-paths for large graphs on the GPU. Paper presented at the Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. J. Liu, Xu, S., Zhang, F., and Wang, L. (2016). A hybrid genetic-ant colony optimization algorithm for the optimal path selection. Intelligent Automation and Soft Computing, 1-8.

K. R. Dahal, and Chow, T. E. (2014). An agent-integrated irregular automata model of urban land-use dynamics. International Journal of Geographical Information Science, 28(11), 2281-2303. https://doi.org/10.1080/13658816.2014.917646

E. W. Dijkstra, (1959). A Note on Two Problems in Connection with Graphs. Numerische Mathematics, 1(1), 269--271. https://doi.org/10.1007/BF01386390

R. W. Floyd, (1962). Algorithm 97: Shortest path. Communications of the Acm, 5(6), 345. https://doi.org/10.1145/367766.368168

D. R. Ford, and Fulkerson, D. R. (1963). Flows in networks. Physics Today, 16(7), 54-56. https://doi.org/10.1063/1.3051024

B. Huang, Wu, Q., and Zhan, F. B. (2007). A shortest path algorithm with novel heuristics for dynamic transportation networks. International Journal of Geographical Information Science, 21(6), 625-644. https://doi.org/10.1080/13658810601079759

D. B. Johnson, (1973). A Note on Dijkstra”s Shortest Path Algorithm. Journal of the Acm, 20(3), 385-388. https://doi.org/10.1145/321765.321768

D. B. Johnson, (1977). Efficient Algorithms for Shortest Paths in Sparse Networks. Journal of the Acm, 24(1), 1-13. https://doi.org/10.1145/321992.321993

X. Kang, (2015). Graph-based synchronous collaborative mapping. Geocarto International, 30(1), 28-47. https://doi.org/10.1080/10106049.2014.883437

J. Kim, Han, W.-S., Oh, J., Kim, S., and Yu, H. (2014). Processing time-dependent shortest path queries without pre-computed speed information on road networks. Information Sciences, 255, 135-154. https://doi.org/10.1016/j.ins.2013.07.009

D. Levinson, (2012). Network structure and city size. PloS one, 7(1), e29721. https://doi.org/10.1371/journal.pone.0029721

P. A. Longley, Goodchild, M. F., Maguire, D. J., and Rhind, D. W. (2005). Geographic information systems and science: John Wiley and Sons: New York, NY, USA.

M. Martijn, Matthieu, V. D. H., and Aart, V. H. (2007). Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems. European Journal of Operational Research, 181(1), 59-75. https://doi.org/10.1016/j.ejor.2006.02.051

B. Mi, and Liu, D. (2016). A fuzzy neural approach for vehicle guidance in real-time. Intelligent Automation and Soft Computing, 23(1), 13-19. https://doi.org/10.1080/10798587.2015.1118274

D. C. Parker, Manson, S. M., Janssen, M. A., Hoffmann, M. J., and Deadman, P. (2003). Multi-agent systems for the simulation of land-use and land-cover change: a review. Annals of the association of American Geographers, 93(2), 314-337. https://doi.org/10.1111/1467-8306.9302004

Rego, César, and Catherine Roucairol. "A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem." Meta-Heuristics (1996): 661-675. Crossref. Web. https://doi.org/10.1007/978-1-4613-1361-8_40

R. W. Rothery, (2008). Car following models. Trac Flow Theory, 199(3), 287-291.

D. Sever, Dellaert, N., van Woensel, T., and de Kok, T. (2013). Dynamic shortest path problems: Hybrid routing policies considering network disruptions. Computers and Operations Research, 40(12), 2852-2863. https://doi.org/10.1016/j.cor.2013.06.014

T. Shirabe, (2014). A path that buys time to decide where to go. International Journal of Geographical Information Science, 28(2), 314-325. https://doi.org/10.1080/13658816.2013.838769

S. Skiena, (1990). Dijkstra”s algorithm: Reading, MA: Addison-Wesley.

N. Takashi, (2002). The physics of traffic jams. Reports on progress in physics, 65(9), 1331. https://doi.org/10.1088/0034-4885/65/9/203

E. G. Talbi, (2002). A Taxonomy of Hybrid Metaheuristics. Journal of Heuristics, 8(5), 541-564. https://doi.org/10.1023/A:1016540724870

W. R. Tobler, (1970). A computer movie simulating urban growth in the Detroit region. Economic geography, 234-240. https://doi.org/10.2307/143141

S. Warshall, (1962). A Theorem on Boolean Matrices. Journal of the Acm, 9(1), 11-12. https://doi.org/10.1145/321105.321107

M. Wegener, (1994). Operational urban models state of the art. Journal of the American Planning Association, 60(1), 17-29. https://doi.org/10.1080/01944369408975547

Q. Wu, Tong, C., Wang, Q., and Cheng, X. (2013). All-pairs Shortest Path Algorithm based on MPI+ CUDA Distributed Parallel Programming Model. Journal of Networks, 8(12), 2797-2803. https://doi.org/10.4304/jnw.8.12.2797-2803

T. Xing, and Zhou, X. (2011). Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach. Transportation Research Part B: Methodological, 45(10), 1660-1679. https://doi.org/10.1016/j.trb.2011.06.004

M. H. Xu, Liu, Y. Q., Huang, Q. L., Zhang, Y. X., and Luan, G. F. (2007). An improved Dijkstra”s shortest path algorithm for sparse network. Applied Mathematics and Computation, 185(1), 247-254. https://doi.org/10.1016/j.amc.2006.06.094

B. Yang, Zhang, Y., and Lu, F. (2014). Geometric-based approach for integrating VGI POIs and road networks. International Journal of Geographical Information Science, 28(1), 126-147. https://doi.org/10.1080/13658816.2013.830728

Z. Yang, Yu, B., and Cheng, C. (2007). A Parallel Ant Colony Algorithm for Bus Network Optimization. Computer-Aided Civil and Infrastructure Engineering, 22(1), 44-55. https://doi.org/10.1111/j.1467-8667.2006.00469.x

F. B. Zhan, (1997). Three fastest shortest path algorithms on real road networks: Data structures and procedures. Journal of geographic information and decision analysis, 1(1), 69-82.

T. Zhang, and Wu, L. (2011). A novel algorithm for APSP problem via a simplified delay pulse coupled neural network. Journal of Computational Information Systems, 7(3), 737-744.

JOURNAL INFORMATION


ISSN PRINT: 1079-8587
ISSN ONLINE: 2326-005X
DOI PREFIX: 10.31209
10.1080/10798587 with T&F
IMPACT FACTOR: 0.652 (2017/2018)
Journal: 1995-Present

SCImago Journal & Country Rank


CONTACT INFORMATION


TSI Press
18015 Bullis Hill
San Antonio, TX 78258 USA
PH: 210 479 1022
FAX: 210 479 1048
EMAIL: tsiepress@gmail.com
WEB: http://www.wacong.org/tsi/