Querying spatial graphs

Alternative routing

Description

The majority of existing routing approaches return a single path; providing alternative ways to reach the destination which are sufficiently different from each other, has received very limited attention. Although, modern navigation systems may recommend more than one paths, e.g., the shortest (w.r.t. the covered distance), the fastest and the cheapest (w.r.t. the fuel consumption), in practice, an independent search is performed for each criterion. As a result, the computed paths may in fact be very similar and thus, cannot be considered as alternatives.

To fill this gap, we introduced the notion of alternative routing where the goal is to recommend a set of paths which qualify the given quality constraints/criteria while being sufficiently dissimilar to each other. As our first case study, the task of identifying the k-Shortest Paths with Limited Overlap (kSPwLO) was defined. In brief, the goal of this task is to recommend k dissimilar to each other paths which are as short as possible. For this purpose, we devised a number of both exact and approximate routing algorithms in an effort to efficient handle real-world road networks even on a continental scale. Recently, we also addressed the problem of finding k-Dissimilar Paths with Minimum Collective Length (k-DPwML). In this case, the goal is again to recommend a set of k sufficiently dissimilar to each other paths, which however exhibit the lowest collective length among all sets of k sufficiently dissimilar paths.

Publications

Source code

 

Most preferred path

Description

Car navigation and route planning systems recommend the shortest/fastest path as the most preferable way of moving on top of a road network. However, in practice, the shortest/fastest path is not always the ideal way of routing as it fails to capture the actual way people tend to move. Specifically, people usually follow roads already familiar to them and highly used in their every day life. Further, when they want to reach a location for the first time, they might ask their friends to recommend a good and safe way based on their experience. In both cases, routing involves the wisdom stemming from experience and moving habits which give preference to specific parts of a city or its road network while avoiding other parts; for example, areas with increased traffic, included in high crime areas, or more likely to become dangerous in case of bad weather conditions.

To capture this routing problem, we study the idea of the Most Preferred Path. This task was first introduced in Prof. Bouros' PhD studies. A collection of historical paths or moving patterns is employed to define a preferred subgraph of the road network. A driver consults this collection seeking for a path to travel as less as possible outside this preferred part of the network without significantly increasing, at the same time, the total length of the trip compared to the shortest path.

Publications

  • Dimitris Sacharidis, Panagiotis Bouros and Theodoros Chondrogiannis:
    Finding the Most Preferred Path
    Proceedings of the 25th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), Redondo Beach, California, USA, November 7-10, 2017
  • Panagiotis Bouros:
    Evaluating Queries over Route Collections
    Ph.D. Dissertation, School of Electrical and Computer Engineering, National Technical University of Athens, Greece, 2011

 

Routing directions

Description

The problem of providing meaningful routing directions in written or spoken text is of great importance; in this context, the fastest path may not be the ideal choice. Consider an emergency situation, e.g., a natural disaster or a terrorist attack, which requires an evacuation plan to be communicated to people on the site. Under such circumstances of distress and disorganization, it is often desirable to provide concise, easy to memorize, and clear to follow “simple” instructions; hence, a simple path is more preferable and appropriate than the fastest path. However, the simplest path may often be considerably longer than the fastest. Hence, we introduced and investigated the efficient computation of near-simplest paths which are as fast as possible and near-fastest paths which are as simple as possible. As per the most common interpretation, turns (road changes) are assigned costs, and the simplest path is the one that has the lowest total turn cost, termed complexity.

Publications

  • Dimitris Sacharidis and Panagiotis Bouros:
    Routing Directions: Keeping it Fast and Simple
    Proceedings of the 21st ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS), Orlando, Florida, USA, November 5-8, 2013