We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches. In particular, the entire alternative graph can be computed in less than 0.384sec for the road network of Germany, and in less than 1.24sec for that of Europe. Our approach provides also "quick-and-dirty" results of decent quality, in about 1/300 of the above mentioned query times for continental-size instances.

We aim at exploiting parallelism in shared-memory multiprocessing systems, in order to speed up the execution time with as small redundancy in work as possible, for an elementary task that comes up frequently as a subroutine in the daily maintenance of large-scale time-dependent graphs representing real-world relationships or technological networks: the many-to-all time-dependent shortest paths (MATDSP) problem. MATDSP requires the computation of one time-dependent shortest-path tree (TDSPT) per origin-vertex and departure-time, from an arbitrary collection of pairs of origins and departure-times, towards all reachable destinations in the graph. Our goal is to explore the potential and highlight the limitations of amorphous data parallelism, when dealing with MATDSP in multicore computing environments with a given amount of processing elements and a shared memory to exploit. Apart from speeding-up execution time, consumption of resources (and energy) is also critical. Therefore, we aim at limiting the work overhead for solving a MATDSP instance, as measured by the overall number of arc relaxations in shortest-path computations, while trying to minimize the overall execution time. Towards this direction, we provide several algorithmic engineering interventions for solving MATDSP concerning: (i) the compact representation of the instance; (ii) the choice and the improvement of the time-dependent single-source shortest path algorithm that is used as a subroutine; (iii) the way according to which the overall work is allocated to the processing elements; (iv) the adoption of the amorphous data parallelism rationale, in order to avoid costly synchronization among the processing elements while doing their own part of the work. Our experimental evaluations, both on real-world and on synthetic benchmark instances of time-dependent road networks, provide insight how one should organize heavy MATDSP computations, depending on the application scenario. This insight is in some cases rather unexpected. For instance, it is not always the case that pure data parallelism (among otherwise totally independent processors) is the best choice for minimizing execution times. In certain cases it may be worthwhile to limit the level of data parallelism in favor of algorithmic parallelism, in order to achieve more efficient MATDSP computations.

Providing efficient, sustainable and personalized mobility services in urban environments that combine a spectrum of transport modes (e.g., public transport, electric vehicles, vehicle sharing, low energy and/or emission routes) constitutes a great challenge. In this work, we present MOVESMART, a holistic approach (and integrated platform) for the provision of renewable personal mobility services, leveraging crowd-sourcing data, tools for collecting real-time information by multimodal travelers, and traffic prediction mechanisms. MOVESMART guarantees real-time responses to renewable (on-demand) mobility queries for efficient multi-modal route planning that are time-dependent as well as sensitive to aperiodic incidents and traffic prediction forecasts. This paper focuses on the cloudbased (backend) services of the MOVESMART platform.

In this paper, a new model, known as the multimodal dynamic timetable model (DTM), is presented for computing optimal multimodal journeys in schedule-based public transport systems. The new model constitutes an extension of the dynamic timetable model (DTM), which was developed originally for a different setting (unimodal journey-planning). Multimodal DTM demonstrates a very fast query algorithm that meets the requirement for real-time response to best journey queries, and an ultra-fast update algorithm for updating the timetable information in case of delays of scheduled-based vehicles. An experimental study on real-world metropolitan networks demonstrates that the query and update algorithms of Multimodal DTM compare favorably with other state-of-the-art approaches when public transport, including unrestricted—with respect to departing time—traveling (e.g., walking and electric vehicles) is considered.

A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden of landmark-based oracles (the large preprocessing requirements), CFLAT is extensively engineered. A thorough experimental evaluation on two real-world benchmark instances shows that CFLAT achieves a significant improvement on preprocessing, approximation guarantees and query-times, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.

We provide a cloud-based journey planner for public transport built upon an efficient core routing engine that updates efficiently timetable information in case of delays. We describe our mobile application along with a service that allows users to assess the suggested journeys offered by the application, built on top of an IoT/FIRE+ infrastructure. Our journey planner contributes to the establishment of a live community of travelers, equipped with an arsenal of inter-operable personalized renewable mobility services, for modern mobility in smart cities.

We implement and experimentally evaluate landmark-based oracles for min-cost paths in two different types of road networks with time-dependent arc-cost functions, based on distinct real-world historic traffic data: the road network for the metropolitan area of Berlin, and the national road network of Germany. Our first contribution is a significant improvement on the implementation of the FLAT oracle, which was proposed and experimentally tested in previous works. Regarding the implementation, we exploit parallelism to reduce preprocessing time and real-time responsiveness to live-traffic reports. We also adopt a lossless compression scheme that severely reduces preprocessing space and time requirements. As for the experimentation, apart from employing the new data set of Germany, we also construct several refinements and hybrids of the most prominent landmark sets for the city of Berlin. A significant improvement to the speedup of FLAT is observed: For Berlin, the average query time can now be as small as 83μsec, achieving a speedup (against the time-dependent variant of Dijkstra's algorithm) of more than 1, 119 in absolute running times and more than 1, 570 in Dijkstra-ranks, with worst-case observed stretch less than 0.781%. For Germany, our experimental findings are analogous: The average query-response time can be 1.269msec, achieving a speedup of more than 902 in absolute running times, and 1, 531 in Dijkstra-ranks, with worst-case stretch less than 1.534%. Our second contribution is the implementation and experimental evaluation of a novel hierarchical oracle (HORN). It is based on a hierarchy of landmarks, with a few “global” landmarks at the top level possessing travel-time information for all possible destinations, and many more “local” landmarks at lower levels possessing travel-time information only for a small neighborhood of destinations around them. As it was previously proved, the advantage of HORN over FLAT is that it achieves query times sublinear, not just in the size of the network, but in the Dijkstra-rank of the query at hand, while requiring asymptotically similar preprocessing space and time. Our experimentation of HORN in Berlin indeed demonstrates improvements in query times (more than 30.37%), Dijkstra-ranks (more than 39.66%), and also worst-case error (more than 35.89%), at the expense of a small blow-up in space. Finally, we implement and experimentally test a dynamic scheme to provide responsiveness to live-traffic reports of incidents with a small timelife (e.g., a temporary blockage of a road segment due to an accident). Our experiments also indicate that the traffic-related information can be updated in seconds.

Urban road networks are represented as directed graphs, accompanied by a metric which assigns cost functions (rather than scalars) to the arcs, e.g. representing time-dependent arc-traversal-times. In this work, we present oracles for providing time-dependent min-cost route plans, and conduct their experimental evaluation on a real-world data set (city of Berlin). Our oracles are based on precomputing all landmark-to-vertex shortest travel-time functions, for properly selected landmark sets. The core of this preprocessing phase is based on a novel, quite efficient and simple one-to-all approximation method for creating approximations of shortest travel-time functions. We then propose three query algorithms, including a PTAS, to efficiently provide min-cost route plan responses to arbitrary queries. Apart from the purely algorithmic challenges, we deal also with several implementation details concerning the digestion of raw traffic data, and we provide heuristic improvements of both the preprocessing phase and the query algorithms. We conduct an extensive, comparative experimental study with all query algorithms and six landmark sets. Our results are quite encouraging, achieving remarkable speedups (at least by two orders of magnitude) and quite small approximation guarantees, over the time-dependent variant of Dijkstra's algorithm.

Many efforts have been done in the last years to model public transport timetables in order to find optimal routes. The proposed models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. The array-based models have been shown to be very effective in terms of query time, while the graph-based models usually answer queries by computing shortest paths, and hence they are suitable to be used in combination with speed-up techniques developed for road networks. In this paper, we focus on the dynamic behavior of graph-based models considering the case where transportation systems are subject to delays with respect to the given timetable. We make three contributions: (i) we give a simplified and optimized update routine for the well-known time-expanded model along with an engineered query algorithm; (ii) we propose a new graph-based model tailored for handling dynamic updates; (iii) we assess the effectiveness of the proposed models and algorithms by an experimental study, which shows that both models require negligible update time and a query time which is comparable to that required by some array-based models.

We present improved methods for computing a set of alternative source-to-destination routes in road networks in the form of an alternative graph. The resulting alternative graphs are characterized by minimum path overlap, small stretch factor, as well as low size and complexity. Our approach improves upon a previous one by introducing a new pruning stage preceding any other heuristic method and by introducing a new filtering and fine-tuning of two existing methods. Our accompanying experimental study shows that the entire alternative graph can be computed pretty fast even in continental size networks.