Transportation Routing in Urban Environments Using Updated Traffic Information Provided through Vehicular Communications

Abstract

Abstract:

Finding optimal routes for vehicles to reach their destinations is deemed to be a significant challenge and that is an objective in Intelligent Transportation Systems (ITS). In this paper, we propose a mechanism for vehicle routing based on the availability of updated traffic information. The proposed mechanism includes two phases. In the first phase, we propose a TIS (Traffic Information System) which collects the updated traffic status and stores it in the traffic information center. The proposed TIS approach consists of wired or wireless infrastructure and ad hoc inter-vehicle communications. This information will be used for vehicle navigation when a vehicle intends to run some errands. In the second phase, through exercising the available updated traffic information; we propose two different Dijkstra- based vehicle route suggestion algorithms named one-step vehicle path suggestion and step-by-step vehicle path suggestion. In the former, the algorithm is invoked only once at the beginning of the trip in order to obtain the best route towards the destination. The obtained route is then used by the vehicle throughout the journey. Nevertheless, in step-by-step path suggestion algorithm the suggested route toward the destination is being updated and refreshed at each intersection. The proposed step- by- step algorithm is further enhanced by two novel methods for avoiding loop creation. Results of the extensive simulation study using NCTUns 6.0 network simulator shows that both of the routing algorithms use the updated traffic information while the step-by-step algorithm outperforms the one-step path suggestion algorithm.

Key words: intelligent transportation systems (ITS), VANETs, WiMAX networks, road- side unit (RSU), directional antenna, dynamic vehicle routing, vehicles navigation, traffic information system

摘要：

为车辆出行规划最优路径是智能交通系统（ITS）的一个重要研究目标.本文根据有效的实时交通信息提出一种车辆路径选择机制，这种机制包括两个阶段.第一阶段，由有线或无线传输设备和车载通信设备组成的交通信息系统（TIS），收集用于车辆出行导航的实时交通信息数据，并将其存储至交通信息中心.第二阶段，利用有效的实时交通信息，提出两种基于Dijkstra 的路径选择算法，即一步路径选择和逐步路径选择.前者在整个车辆出行过程中，仅在其出行开始阶段单次计算通往目的地的最优路径.逐步路径选择在每个交叉口都实时更新并计算通往目的地的最优路径，并提出使用两种新优化方法以避免算法形成环路.利用NCTUns 6.0 进行路网仿真，结果表明两种算法都借助于实时交通信息，且逐步路径选择优于一步路径选择.

关键词: 智能交通系统（ITS）, VANETs, WiMAX 网络, 路侧单元(RSU), 定向天线, 动态车辆路径, 车辆导航, 交通信息系统

CLC Number:

U491

YOUSEFI Saleh, ABBASI Tofigh, ANVARI Zahra. Transportation Routing in Urban Environments Using Updated Traffic Information Provided through Vehicular Communications[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(5): 23-36.

YOUSEFI Saleh,ABBASI Tofigh, ANVARI Zahra. 基于车载通信实时交通信息的城市道路路径选择方法[J]. 交通运输系统工程与信息, 2014, 14(5): 23-36.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/abstract/abstract18848.shtml

http://www.tseit.org.cn/EN/Y2014/V14/I5/23

References

[1] Schrank D, Lomax T, Eisele B. TTI’s 2011 Urban Mobility report powered by Inrix traffic data[J]. Texas Transportation Institute Research Report, The Texas A&M University System, 2011.

[2] Nadi S, Delavar M R. Location- based service for invehicle route guidance with real time traffic information [C]//The 12th World Conference on Transport Research (WSTR to WCTR) Proceedings, 2010:1-10.

[3] Mimbela L E Y, Klein L Y. A summary of vehicle detection and surveillance technologies used in intelligent transportation systems[R]. Federal Highway Administrations (FHWA) Intelligent Transportation Systems Joint Program Office, Research Report, 2000 to 2007.

[4] Dhingral S L, Gull I. Traffic flow theory historical research perspectives[C]//75 Years of the Fundamental Diagram for Traffic Flow Theory: Greenshields Symposium Proceedings, 2008:45-62.

[5] Skordyli A, Trigoni N. Delay- bounded routing in vehicular Ad- Hoc networks[C]// In 9th ACM International Symposium on Mobile Ad- Hoc Networking and Computing (MobiHoc’08) Proceedings, 2008: 341-350.

[6] Kitani T, Shinkawa T, Shibata N, et al. Efficient VANET- based traffic information sharing using buses on regular routes[C]//Vehicular Technology Conference (VTC Spring 2008) Proceedings, 2008: 3031-3036.

[7] Khosroshahi A H, Keshavarzi P, KoozehKanani Z D, et al. Acquiring real time traffic information using VANET and dynamic route guidance, [C]//2nd International Conference on Computing, Control and Industrial Engineering (CCIE) Proceedings, 2011:3-13.

[8] Fan Y Y, Kalaba R E, Moore J E. Shortest paths in stochastic networks with correlated link costs[J]. Computers & Mathematics with Applications, 2005, 49 (9-10): 1549-1564.

[9] Delling D, Wagner D. Time-dependent route planning, robust and online large- scale optimization[J]. Lecture Note in Computer Science. 2009, 5868: 207-230.

[10] Boutilier C, Dearden R, Goldszmidt M. Stochastic dynamic programming with factored representations[J]. Artificial Intelligence, Elsevier, 2000, 121 (1- 2):49- 107.

[11] Feldman R M, Valdez-Flores C. Applied probability and stochastic processes[M]. Springer, 2010.

[12] Bander J L, White C C. A heuristic search approach for a non- stationary stochastic shortest path problem with terminal cost[J]. Transportation Science, 2002, 36 (2): 218–230. [13] Hashemi S M, Mokarami S, Nasrabadi E. Dynamic shortest path problems with time - varying costs[J]. Optimization Letters, 2010, 4:147-156.

[14] Lim S, Balakrishnan H, Gifford D, et al. Stochastic motion planning and applications to traffic[J]. Algorithmic Foundation of Robotics VIII, Springer Berlin Heidelberg, 2009, 57: 483-500.

[15] Kim S, Lewis M E, White C C. State space reduction for non- stationary stochastic shortest path problems with real- time traffic information[J]. IEEE Transactions on Intelligent Transportation Systems, 2005, 6 (3) :273- 284.

[16] Psaraftis H N, Tsitsiklis J N. Dynamic shortest paths in acyclic networks with markovian arc costs[J]. OperationsResearch, 1993, 41 (1):91-101.

[17] Ramalingam G, Reps T. An incremental algorithm for a generalization of the shortest- path problem[J]. Journal of Algorithms, 1996, 21(2): 267–305.

[18] Buriol LS, Resende M G C, Ribeiro C C, et al. A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing[J]. Networks, 2005, 46 (1): 36–56.

[19] Frigioni D, Marchetti-Spaccamela A, Nanni U. Semidynamic algorithms for maintaining single source shortest path trees[J]. Algorithmics, 1998, 22:250–274.

[20] Fortz B, Thorup M. Increasing internet capacity using local search[J]. Computational Optimization and Applications. 2004, 29:13-48.

[21] Goel A, Ramakrishnan K G, Kataria D, et al. Efficient computation of delay-sensitive routes from one source to all destinations [C]// Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies ( INFOCOM 2001) Proceedings, 2001:854- 858.

[22] http://www.navman.com acc[OL]. 2014.

[23] http://www.papago.com.tw acc[OL]. 2014.

[24] Chen P Y, Guo Y M, Chen W T. Fuel-saving navigation system in vehicular Ad-Hoc networks. [C]//IEEE 72nd Vehicular Technology Conference (VTC 2010 - Fall) Proceedings, 2010: 1-5.

[25] Lin B Y, Chen C H, Lo C C. A traffic information estimation model using periodic location update events from cellular network[J]. Communications in Computer and Information Science (CCIS), 2011, 135:72-77.

[26] Diao X, Mou K M, Li J J, et al. Inter- vehicle communication for the next generation of intelligent transport systems: Trends in geographic Ad Hoc routing techniques[C]//Beylot A-L, Labiod H (Eds.), Vehicular Networks-Models and Algorithms, John Wiley & Sons, 2013,47-51.

[27] http://www.kurzweilai.net/driverless-vehicles-to-zip-atfull- speed-through-intersections acc[OL]. 2014.

[28] Ramanathan R, Redi J, Santivanez C, et al. Ad Hoc networking with directional sntennas : A complete system solution[J]. IEEE Journal on Selected Areas in Communications, 2005, 23(3):254-255.

[29] Wang S P, Ledley R S. Computer architecture and security: Fundamentals of designing secure computer systems[M]. John Wiley & Sons. 2013.

[30] Medhi D, Ramasamy K. Network routing: algorithms, protocols, and architectures[M]. Morgan Kaufmann Publishers, 2010.

[31] Blue V J, Adler J L, List G F. Real-time multipleobjective path search for in- vehicle route guidance systems[J]. Transportation Research Record, 1997, 1588: 159-167.