Source-linked AI summary
CLIPPER: Replayable Shortlisted Optimization for Repeated Spatial Coverage Planning
Julian Teusch, Jörg Philipp Müller, Monika Sester
TL;DR
Municipal micromobility policy edits require new feasible plans, but full-set greedy can take tens of seconds per city-scale alternative. CLIPPER uses bounded pools with exact current-gain recomputation, hard-constraint checks, conservative screening, and replay records; across three cities, it stays close to same-policy full-set controls while substantially reducing rollout time. Its scope is limited by controlled benchmark chains, a simplified coverage model, static rankings, and incomplete, non-redistributable trip feeds.
Problem
Municipal micromobility planning must compare feasible alternatives after policy edits, while full-set greedy takes tens of seconds per city-scale alternative.
Method
CLIPPER builds bounded candidate pools, recomputes exact current gains, checks every active constraint, audits omitted gains, and records deterministic executions for replay.
Results
Across Braunschweig, Munich, and Berlin, CLIPPER-F stays within 0.245 percentage points of same-policy full-set greedy, while CLIPPER-A uses 9–15% of relaxed-cap control rollout time with city-specific gaps.
Takeaways & Limitations
CLIPPER enables rapid, replayable comparison of recorded city-scale planning states while enforcing every encoded model constraint.
Takeaways & Limitations
The evaluation uses controlled edit chains rather than user interaction or deployment, omits several operational factors, and tests one static-ranking operating point per mode.
Abstract
from arXiv · showhide
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.
1 Motivation and contribution
CLIPPER targets rapid, replayable comparison of feasible municipal micromobility plans after policy edits. Its execution contract combines bounded candidate evaluation with exact feasibility checks and inspectable full-set controls.
- Motivation and contribution: Each policy edit requires reoptimization under exclusions, retained sites, spacing rules, and area-level allocations.Full-set greedy takes tens of seconds per city-scale alternative, motivating seconds-level feedback.
- Motivation and contribution: CLIPPER is designed for what-if exploration that supports deliberation while retaining explicit constraints, replay records, and missed-gain auditing.The system compares feasible alternatives under revised municipal policies rather than treating speed as a substitute for constraint enforcement.
- Motivation and contribution: CLIPPER constructs a bounded pool, computes exact current gains, checks every active constraint, and records results for replay.Candidate generation is replaceable, while matched full-set controls and separate screening and audit paths make restriction effects inspectable.
- Motivation and contribution: Unlike dynamic methods that update solutions across edits, CLIPPER recomputes each recorded state.This supports comparisons over common demand and candidate data after changing policy constraints.
2 CLIPPER
CLIPPER optimizes weighted coverage by selecting from bounded, singleton-ranked pools while recomputing exact current gains and checking all encoded feasibility constraints. Conservative bounds can trigger expansion or audit, and deterministic records support replay.
- Planning model: CLIPPER maximizes weighted demand coverage over scenario-filtered candidates while retaining locks, exclusions, budgets, caps, conflict rules, and minimum spacing.The full-set greedy control uses the same policy, and reported gaps compare the resulting greedy trajectories.
- Restricted selection: Proposal groups are singleton-ranked once; each round filters and backfills a bounded pool, then selects using exact current marginals and hard-constraint checks.The incumbent starts with all mandatory locks, and demand already covered is accounted for when marginals are recomputed.
- Pool policies: CLIPPER-F assigns fixed per-group width K, whereas CLIPPER-A distributes one shared candidate budget and uses coverage-prioritized accounting caps.CLIPPER-A’s coverage-prioritized policy sets λ = 1.5 without changing the global facility budget.
- Complexity: Exact marginal work scales with the sum of pool widths, O(c Σ_t W_t), versus O(cT|V_Ω|) for full-set greedy or an exact trajectory audit.These expressions describe gain calculations rather than measured end-to-end wall time.
- Screening and audit: 0 ≤ δ_t ≤ ˆδ_t bounds the exact gain omitted by the pool; CLIPPER uses the bound to trigger pool expansion or an offline audit.Full-set exact-marginal scans are reserved for offline or high-stakes checkpoints and excluded from reported rollout times.
- Replay: Identical inputs and fixed ranking and tie-breaking rules reproduce the selected-set fingerprint and aggregate replay counters.Replay records include scenario and policy settings, termination status, and can include configured missed-gain values.
3 Evaluation
The evaluation recomputes each edited scenario across three cities and compares CLIPPER with full-set greedy under controlled cap policies. CLIPPER-F preserves coverage closely while reducing rollout time, whereas CLIPPER-A prioritizes coverage with a shared candidate budget.
- Scenario construction: The stress chain increases high-contribution baseline sites with 75 m exclusions from 0 to 17.5% and locked baseline sites from 0 to 35%.Later states ramp network spacing from 25 m to 60 m and add hotspot exclusions.
- Aggregate evaluation: At K = 1024, CLIPPER-F stays within 0.245 percentage points of full-set control coverage and reduces rollout time to 1.49–1.83 seconds from 22.9–52.7.Means cover all 11 states across the evaluated cities.
- Aggregate evaluation: CLIPPER-A with 8192 slots uses 9–15% of relaxed-cap control time, with gaps of 1.82 (BS), 0.12 (MUC), and 0.27 (BER) percentage points.CLIPPER-A and CLIPPER-F answer different policy questions because their cap policies differ.
- Chain sensitivity: Across complete chains, CLIPPER-F speedup ranges from 7.4–40.7× in Braunschweig, 8.4–49.1× in Munich, and 15.7–84.3× in Berlin.Speedups remain at least 7.4× after spacing and hotspot edits are combined.
- Determinism and audit: Three full-data reruns of every state and city produced identical coverage, counts, termination reasons, and terminal flags for CLIPPER-F with K = 1024.All runs exhausted feasible positive gains, and none stopped because its pool was too narrow.
4 Limitations and scope
The evaluation uses controlled scenario chains rather than deployment studies, and the coverage model omits several operational factors. Transfer, refreshed rankings, public reconstruction, and planner utility remain outside the demonstrated scope.
- Evaluation scope: The controlled E0–E10 chains evaluate optimizer behavior, not user interaction, deployment, edit frequency, response thresholds, or planner utility.The collaboration with Braunschweig informed requirements, but the benchmark does not measure operational adoption.
- Model scope: The coverage model omits congestion, compliance, equity, rebalancing, and curb capacity.These factors are therefore outside the reported objective and constraints.
- Method scope: Only one operating point per mode is evaluated with a static ranking; refreshed rankings and transfer remain open.The limitation concerns both parameter coverage and generalization beyond the evaluated settings.
- Data and reproducibility: The trip feeds are incomplete and cannot be redistributed, while public reconstruction requires processed candidates, scenario records, and fixed OSM snapshots.Reproducibility depends on project-provided artifacts and fixed network data.
- Operational interpretation: Planners can test several K values on stored states against the same planning data before interactive use.This operational workflow is presented as a preparatory use of recorded scenarios.
5 Conclusion
CLIPPER makes repeated city-scale planning runs inspectable by combining bounded candidate pools, exact feasibility checks, replay records, and matched full-set comparisons. The practical comparison unit is a versioned policy state with its feasible plan and rerunnable record.
- Conclusion: Bounded pools reduce alternatives from tens of seconds to seconds while exact checks enforce every encoded constraint.Each pool policy is compared with full-set greedy under the same policy.
- Conclusion: Replay records preserve scenario context, and offline scans reveal gains omitted by restricted candidate pools.The execution contract allows proposal rules to change without altering feasibility or comparison semantics.
- Conclusion: The practical unit of comparison is a versioned policy state, its feasible plan, and the record needed to rerun it.This extends evaluation beyond a score alone to include constraints, selected sites, and execution context.