Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Real-timefastest path algorithm using bidirectional point-to-point search on a Fuzzy Time-Dependent transportation network

Abstract : Nowadays management of information systems within the transport industry for effective and efficient decision making requires the use of latest technological development such real-time monitoring and traffic simulation. This will lead to the development of methods and algorithms, for instance, of fleet management, routing within a specified time windows and risk assessment. In this paper we will focus on proposing a method for finding itineraries that has the fastest travel-time on a time-dependent transportation network. It is modelled as a weighted graph, whose weight are time duration that depends on the time at which the road segment is traversed. This problem can be solved in polynomial time with a Single-Source algorithm, by the definition of some restrictions on the edge weights. However, its application on a graph with several millions nodes and edges is highly memory and time consuming. Alternatively, a bidirectional Point-to-Point path search, using A-star, offers far better performance. The novelty of the proposed approach is based on the modelling of an appropriate degree of dynamics of a real-world network by considering the fuzzy nature of the travel-time using Zadeh's fuzzy concept. In addition, we speed-up search by integrating a pre-computation phase, which consists in network partitioning using network Voronoi diagrams with implicit calculation of the lower-bound travel-time label for each node-to-border, border-to-border and border-to-node. Those labels should never overestimate the travel-time at any moment, to ensure the reliability of the suggested heuristic cost function.
Document type :
Conference papers
Complete list of metadata
Contributor : Magalie Prudon Connect in order to contact the contributor
Submitted on : Wednesday, September 17, 2014 - 11:36:59 AM
Last modification on : Wednesday, November 17, 2021 - 12:31:19 PM



Mohamed Haitam Laarabi, Azedine Boulmakoul, Aziz Mabrouk, Roberto Sacile, Emmanuel Garbolino. Real-timefastest path algorithm using bidirectional point-to-point search on a Fuzzy Time-Dependent transportation network. 2014 International Conference on Advanced Logistics and Transport, ICALT 2014, May 2014, Hammamet, Tunisia. pp.78-84 - Article number 6864086, ⟨10.1109/ICAdLT.2014.6864086⟩. ⟨hal-01064823⟩



Record views