Efficient Generation of Geographically Accurate Transit Maps
Hannah Bast, Patrick Brosi, Sabine Storandt · ACM Transactions on Spatial Algorithms and Systems · 2018
We present LOOM (Line-Ordering Optimized Maps), an automatic generator of geographically accurate transit maps. The input to LOOM is data about the lines of a transit network: for each line, its station sequence and geographical course. LOOM proceeds in three stages: (1) construct a line graph, where edges correspond to network segments with the same set of lines following the same course; (2) apply a set of local transformation rules that compute an optimal partial ordering of the lines and speed up the next stage; (3) construct an Integer Linear Program (ILP) that yields a line ordering for each edge and minimizes the total number of line crossings and line separations; and (4) based on the line graph and the computed line ordering, draw the map. As our maps respect the geography of the transit network, they can be used as overlays in typical map services. Previous research either did not take the network geography into account or was only concerned with schematic metro map layouting. We evaluate LOOM on six real-world transit networks, with line-ordering search-space sizes up to 2 × 10 267 . Using our transformation rules and an improved ILP formulation, we compute optimal line orderings in a fraction of a second for all networks. This enables interactive use of our method in map editors.