Nöllenburg and Wolff – DRAWING AND LABELING HIGH QUALITY METRO MAPS BY MIXED-INTEGER PROGRAMMING 2010

Description

The paper proposes a mixed-integer programming (MIP) method that jointly solves schematic metro layout and station labeling. Starting from seven common design rules, the authors distinguish hard constraints (H1–H4: mandatory octilinearity, preserved circular vertex order/topology, minimum edge lengths, inter-edge spacing/planarity) from soft objectives (S1–S3: minimize bends, preserve relative directions, minimize total edge length). Octilinear directions are modeled via an extended coordinate system and the L∞ metric; binary and integer variables encode choices while bend/position/length costs are expressed linearly. To reduce model size and runtime they collapse degree-2 paths, limit spacing checks to face-related pairs, and add spacing constraints lazily via solver callbacks. Labeling is integrated by reserving parallelogram regions attached to edges. Implemented in CPLEX and tested on Sydney, Vienna and London, the approach produces high-quality, globally consistent layouts comparable to official maps and judged best among automated methods by experts, but suffers long solve times, scalability limits, difficulty with thick multi-line edges, and intractability for very large labeled networks.