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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 9 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.