Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-mines-paristech.archives-ouvertes.fr/hal-01064823
Contributeur : Magalie Prudon <>
Soumis le : mercredi 17 septembre 2014 - 11:36:59
Dernière modification le : jeudi 24 septembre 2020 - 17:20:28

Identifiants

Citation

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⟩

Partager

Métriques

Consultations de la notice

254