Spatial Graphs Analysis

Quick links:

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. We also addressed the problem of finding k-Dissimilar Paths with Minimum Collective Length (kDPwML). 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. Recently, we introduced the problem k-Most Diverse Near-Shortest Paths (kMDNSP) where the goal is to maximize the diversity of the recommended paths, while bounding their length based on a user-defined constraint.

Publications

  • Christian Häcker, Panagiotis Bouros, Theodoros Chondrogiannis and Ernst Althaus:
    Most Diverse Near-Shortest Paths
    Proceedings of the 29th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), Beijing, China, November 2-5, 2021

  • Theodoros Chondrogiannis, Panagiotis Bouros, Johann Gamper, Ulf Leser and David B. Blumenthal:
    Finding k-Shortest Paths with Limited Overlap
    International Journal on Very Large Data Bases (VLDBJ), Vol 29, No 5, September 2020

  • Theodoros Chondrogiannis, Panagiotis Bouros, Johann Gamper, Ulf Leser and David B. Blumenthal:
    Finding k-Dissimilar Paths with Minimum Collective Length
    Proceedings of the 26th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL) Seattle, Washington, USA, November 6-9, 2018

  • Theodoros Chondrogiannis, Panagiotis Bouros, Johann Gamper and Ulf Leser:
    Exact and Approximate Algorithms for Finding k-Shortest Paths with Limited Overlap
    Proceeding of the 20th International Conference on Extending Database Technology (EDBT), Venice, Italy, March 21-24, 2017

  • Theodoros Chondrogiannis, Panagiotis Bouros, Johann Gamper and Ulf Leser:
    Alternative Routing: k-Shortest Paths with Limited Overlap
    Proceeding of the 23rd ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), Seattle, Washington, USA, November 3-6, 2015

Theses

  • Huu Duy Nguyen:
    Path Diversification for Evacuation Planning
    Bachelor thesis, Johannes Gutenberg University Mainz, Germany

  • Lisa-Patricia Barth:
    App-Based Specification and Visualization of User Preferences in Routing
    Master thesis, Johannes Gutenberg University Mainz, Germany, 2022

    • Primary supervisor: Prof. Dr. Stefan Kramer

  • Yannic Marcel Moog:
    Extending k-Shortest Paths with Limited Overlap
    Bachelor thesis, Johannes Gutenberg University Mainz, Germany, 2021

  • Christian Häcker:
    k-Most Diverse Near-Shortest Paths
    Bachelor thesis, Johannes Gutenberg University Mainz, Germany, 2021

  • Matthias Sawatzky:
    A Web Application for Analysis and Comparison of k-Shortest Paths with Limited Overlap Algorithms on Road Networks
    Bachelor thesis, Johannes Gutenberg University Mainz, Germany, 2019

  • Theodoros Chondrogiannis:
    Efficient Algorithms for Route Planning Problems on Road Networks
    Doctorate thesis, Free University of Bozen-Bolzano, Italy, 2017

Source code

 

Evacuation planning

Description

Evacuation planning is a critical task in disaster management. Especially in situations such as natural disasters or terrorist attacks, large crowds need to move away from danger and reach designated safe zones. For this purpose, various approaches that efficiently compute evacuation plans in urban areas have been proposed.

To evaluate the computed plans, previous works employ heuristics that can only roughly estimate the egress time of each plan. Intuitively, a much better approach is to estimate the egress time via simulation. However, designing a simulation model is usually a time-consuming task and, what is more, this model can only be used to evaluate evacuation plans for a specific area. We address these issues presenting the EURASIM interface, which enables the automated generation of simulation models for urban areas. Furthermore, EURASIM is designed in a way that algorithms for evacuation planning can be easily integrated, thus functioning as a testbed for the development of even better solutions.

Publication

  • Theodoros Chondrogiannis, Panagiotis Bouros, Winfried Emser:
    Simulation-based Evacuation Planning for Urban Areas
    Proceedings of the 29th International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), Virtual Event / Beijing, China, November 2-5, 2021

Theses

  • Huu Duy Nguyen:
    Path Diversification for Evacuation Planning
    Bachelor thesis, Johannes Gutenberg University Mainz, Germany

  • David Betz:
    Extending the EURASIM Interface for Evacuation Planning in Urban Areas
    Bachelor thesis, Johannes Gutenberg University Mainz, Germany, 2023

System

Source code

 

Relative reachability

Description

There is a plethora of user-oriented route planning applications and systems that enable the computation of the fastest journey between two locations using different transportation modes, e.g., car, public transport, walking, bicycle. While useful for individuals, they are of limited interest to a class of users that may be interested in a more global and comparative view of transportation systems in general. In this context, we adopt the view of an urban planner. Urban planners may be interested in queries such as “if a new transit stop was to be introduced in a given location, would that bring the travel time to a given point-of-interest (POI) or area-of-interest (AOI) by bus closer to the travel time by car, therefore improving air quality and/or overall traffic congestion?” To answer queries such as the above, as well as many other interesting ones, we propose the concept of relative reachability which aims at measuring how efficient a given transportation mode is (or may be) in comparison to other competing modes.

Publications

Thesis

  • Nina Röckelein:
    Measuring the Attractiveness of Transportation Modes using Relative Reachability and Mobility Patterns
    Bachelor thesis, University of Kostanz, Germany
    Primary supervisor: Dr. Theodoros Chondrogiannis

System

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' doctorate 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.

Publication

  • 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

Thesis

 

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

  • Claudia Perez Martinez, Panagiotis Bouros and Theodoros Chondrogiannis:
    RODGEN: An Interactive Interface for Road Network Generation
    Proceedings of the 30th ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), Seattle, WA, USA, November 1-4, 2022

  • 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

 

Logistics

Description

Pickup and delivery is a well-known problem in logistics and transportation scenarios. A transportation request is defined as picking up an object (e.g., package, person, etc.) from one location and delivering it at another. Given a set of customer requests, a company offering such services constructs a collection of trajectories that will be followed by its vehicle fleet to pickup and deliver the objects. However, during the service hours, new ad-hoc requests arrive at arbitrary timestamps and thus, the company needs to update the existing vehicle trajectories in order to satisfy the new customers. Under this setup, Prof. Bouros introduced dynamic Pickup and Delivery with Transfers, modeled as a dynamic shortest path problem with two optimization criteria that capture the company’s and the customers’ viewpoint.

Publication

  • Panagiotis Bouros, Dimitris Sacharidis, Theodore Dalamagas and Timos Sellis:
    Dynamic Pickup and Delivery with Transfers
    Proceedings of the 12th International Symposium on Spatial and Temporal Databases (SSTD), Minneapolis, Minnesota, USA, August 24-26, 2011

Thesis

 

Trajectories: retrieval tasks

Description

The Data Management group has targeted points-based search where trajectories are returned based on their proximity to a set of query points; i.e., given a collection of trajectories and a set query points, the goal is to retrieve the top-k trajectories that pass as close as possible to all query points. We advanced the nearest-neighbor based state-of-the-art by proposing a novel and more efficient, spatial range-based approach. In addition, a practical variant of this points-based search was proposed, which additionally takes into account other qualitative characteristics of the searched trajectories, e.g., the temporal span. Besides one-time or snapshot search. our recent work also introduced continuous points-based trajectory search where the query is long-standing and the result set must be maintained whenever updates to the query parameters and/or the data, i.e., the trajectories, occur.

Publications

  • Shuyao Qi, Dimitris Sacharidis, Panagiotis Bouros and Nikos Mamoulis:
    Snapshot and Continuous Points-based Trajectory Search
    International Journal on Advances of Computer Science for Geographic Information Systems (GeoInformatica), Vol 21, No 4, October 2017

  • Shuyao Qi, Panagiotis Bouros, Dimitris Sacharidis and Nikos Mamoulis:
    Efficient Point-based Trajectory Search
    Proceedings of the 14th International Symposium on Spatial and Temporal Databases (SSTD), Hong Kong, China, August 26-28, 2015
    Received the Best Paper Award

Thesis

 

Trajectories: path finding

Description

This line of work is captured by Prof. Bouros' doctorate studies. Prof. Bouros addressed new challenges that arise in path-finding problems, given the availability of trajectory collections; in prarticulal, whether path queries traditionally targeting graphs can be posed on trajectory collections, and even more importantly, if the evaluation of these queries can be enhanced by the special characteristics of the trajectories. For instance, a trajectory can be seen as a set of precomputed answers. Under this perspective, a novel framework was proposed for evaluating path queries on large disk resident collections that are frequently updated by adding and removing trajectories. The thesis introduced two evaluation paradigms that enjoy the benefits of search algorithms (i.e., fast index maintenance) while utilizing transitivity information to terminate the search sooner. In addition, efficient indexing schemes and appropriate updating procedures were also introduced.

Publications

Thesis