0000000000004036
AUTHOR
Theodoros Chondrogiannis
Relative Reachability Analysis as a Tool for Urban Mobility Planning
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 th…
Most Diverse Near-Shortest Paths
Computing the shortest path in a road network is a fundamental problem that has attracted lots of attention. However, in many real-world scenarios, determining solely the shortest path is not enough as users want to have additional, alternative ways of reaching their destination. In this paper, we investigate a novel variant of alternative routing, termed the k-Most Diverse Near-Shortest Paths (kMDNSP). In contrast to previous work, kMDNSP aims at maximizing the diversity of the recommended paths, while bounding their length based on a user-defined constraint. Our theoretical analysis proves the NP-hardness of the problem at hand. To compute an exact solution to kMDNSP, we present an algori…
Finding k -dissimilar paths with minimum collective length
Shortest path computation is a fundamental problem in road networks. However, in many real-world scenarios, determining solely the shortest path is not enough. In this paper, we study the problem of finding k-Dissimilar Paths with Minimum Collective Length (kDPwML), which aims at computing a set of paths from a source s to a target t such that all paths are pairwise dissimilar by at least \theta and the sum of the path lengths is minimal. We introduce an exact algorithm for the kDPwML problem, which iterates over all possible s-t paths while employing two pruning techniques to reduce the prohibitively expensive computational cost. To achieve scalability, we also define the much smaller set …
Simulation-based Evacuation Planning for Urban Areas
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 ar…