Jan‐Henrik Haunert

Daniel Faber, Jan-Henrik Haunert, Petra Mutzel

Regionalization is a fundamental task in spatial analysis that seeks to partition a larger area - such as a country - into smaller regions that are homogeneous with respect to a given attribute. A popular model for regionalization is the p-regions problem, in which regions are formed by grouping the areas of an input planar subdivision. Given the subdivision's adjacency graph G and pairwise dissimilarities between vertices, the goal is to partition G into a fixed number p of connected subgraphs, such as to minimize the sum of dissimilarities over all vertex pairs in the same subgraph. The problem is NP-hard and even small instances are difficult to solve to provable optimality. In this paper, we present the new ILP model ER-S for the p-regions problem, exploiting a connection between the p-regions objective and the k-partitioning problem. Furthermore, we strengthen the known ILP model Tree with a new type of subtour elimination inequality specific to the p-regions problem. Combining ER-S and the strengthened version of Tree yields the model ER-S-Tree, which dominates the state-of-the-art models in polyhedral strength. This theoretical advantage is reflected in its superior performance in our experimental evaluation. In particular, the new models ER-S and ER-S-Tree enable the solution of problem instances for major European countries that were previously intractable.

J. Oehrlein, A. Förster, D. Schunck et al.

Understanding the criteria that bicyclists apply when they choose their routes is crucial for planning new bicycle paths or recommending routes to bicyclists. This is becoming more and more important as city councils are becoming increasingly aware of limitations of the transport infrastructure and problems related to automobile traffic. Since different groups of cyclists have different preferences, however, searching for a single set of criteria is prone to failure. Therefore, in this paper, we present a new approach to classify trajectories recorded and shared by bicyclists into different groups and, for each group, to identify favored and unfavored road types. Based on these results we show how to assign weights to the edges of a graph representing the road network such that minimum-weight paths in the graph, which can be computed with standard shortest-path algorithms, correspond to adequate routes. Our method combines known algorithms for machine learning and the analysis of trajectories in an innovative way and, thereby, constitutes a new comprehensive solution for the problem of deriving routing preferences from initially unclassified trajectories. An important property of our method is that it yields reasonable results even if the given set of trajectories is sparse in the sense that it does not cover all segments of the cycle network.