Column Generation for the Micro-Transit Zoning Problem

In municipal planning workshops, planners and other stakeholders compare shared-micromobility parking policies by varying no-parking zones, retained sites, spacing, or area allocations. Each edit changes feasible sites and how much demand they cover, so the alternative must be reoptimized on the same spatial data. Full-set greedy, the transparent reference for this task, takes tens of seconds per alternative at city scale. We present Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay (CLIPPER), an optimizer with audit functions developed for requirements elicited with the City of Braunschweig. In each greedy round, it forms a deterministic candidate pool of bounded size, computes how much still-uncovered demand each candidate would add, and rejects candidates that violate an active constraint. An optional offline audit scans every remaining feasible candidate and records what the restricted pool omitted. We evaluate these functions on complete eleven-state edit chains ($E_0,\ldots,E_{10}$) in Braunschweig, Munich, and Berlin. With $K=1024$ candidates per group, the fixed-width mode CLIPPER-F has mean coverage gaps to full-set greedy under the same policy of 0.245, 0.003, and 0.001 percentage points in Braunschweig, Munich, and Berlin, respectively, while mean rollout time falls by factors of 13.6--28.9; no audited run terminates while a candidate outside the pool could still increase coverage. Plans computed from two checksummed versions of Braunschweig's official no-parking-zone data differ in 30 of about 540 selected sites although coverage moves by only about 0.1 percentage points. These changes still require municipal assessment and implementation. The findings inform a proposed municipal process that versions policy inputs, reports site changes beside coverage, and scans the full candidate set before a final decision.

Designing a transit network requires many sequential route extension decisions, but their quality is often visible only after the full network is assembled. This delayed-feedback challenge lies at the heart of the Transit Route Network Design Problem (TRNDP), where route interactions can be deceptive: an extension that appears useful locally can create transfer bottlenecks, produce redundant overlap, or reduce overall throughput. To guide route construction under delayed simulator feedback, we introduce AlphaTransit, a search-based planning framework for cityscale bus network design. AlphaTransit couples Monte Carlo Tree Search (MCTS) with a neural policy-value network: the policy proposes route extensions, the value estimates downstream design quality, and search uses these predictions to refine each decision. This provides decision-time lookahead during route construction without running simulator rollouts inside the search tree. We evaluate AlphaTransit on a new Bloomington TRNDP benchmark with realistic road topology and censusderived demand, under mixed and full transit demand settings. In the Bloomington network, AlphaTransit attains the highest service rate in both demand settings, reaching 54.6% and 82.1%, respectively. Relative to reinforcement learning without search, these correspond to 9.9% and 11.4% service rate gains; relative to MCTS without learned guidance, they correspond to 2.5% and 11.2% gains. These results suggest that coupling learned guidance with MCTS is more effective than using either approach alone for transit network design. Our code and data are publicly available in https://github.com/poudel-bibek/AlphaTransit.

Operational requirements developed with the City of Braunschweig frame municipal micromobility planning under geofenced exclusions, mandatory retained sites, spacing rules, and area-level caps. Each policy edit requires a new feasible plan; full-set greedy takes tens of seconds per alternative at city scale. We present CLIPPER (Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay). It forms bounded candidate pools but recomputes exact current gains and checks every active constraint before selection. Coverage from each candidate alone sets the initial order. Offline full-set scans measure gains omitted by the pool; online, a conservative bound triggers expansion or audit. CLIPPER-F gives each proposal group the same number of candidate slots. Across Braunschweig, Munich, and Berlin, its mean coverage over complete chains stays within 0.245 percentage points of full-set greedy under the same policy, with 13.6--28.9 times lower mean rollout time. CLIPPER-A instead distributes one shared candidate budget across the groups. Under its coverage-prioritized policy, it uses 9--15% of full-set greedy's rollout time under the same policy, with mean gaps of 1.82 percentage points in Braunschweig, 0.12 in Munich, and 0.27 in Berlin. Together, CLIPPER enables rapid, replayable comparison of recorded city-scale planning states while enforcing every encoded model constraint.