Source-linked AI summary
CLIPPER Beyond Shortlisting: Auditable Decision Support for Changing Municipal Micromobility Policies
Julian Teusch, Jörg Philipp Müller, Monika Sester
TL;DR
Municipal planners need to compare micromobility parking-policy edits because each edit can change feasible sites and coverage, while full-set greedy takes tens of seconds per alternative. CLIPPER forms a bounded candidate pool, selects with exact gains subject to active constraints, and can audit omitted gains. Across three cities, its fixed-width mode is much faster with small mean coverage gaps; Braunschweig policy versions also show changed sites despite similar coverage.
Problem
Policy edits can change feasible sites and coverage, so municipalities need to reoptimize alternatives on common spatial data and compare site changes as well as aggregate coverage.
Source: §1 · p. 1Method
Results
CLIPPER-F(1024)’s mean coverage gap to same-policy full-set greedy is 0.245, 0.003, and 0.001 percentage points in Braunschweig, Munich, and Berlin, while mean rollout is 13.6–28.9× faster.
Source: §8 · p. 10Takeaways & Limitations
The proposed municipal process versions policy inputs, reports changed sites beside coverage, calibrates score updates locally, and scans the full candidate set before a final decision.
Source: §8 · p. 10The weighted point-coverage model omits curb capacity, congestion, compliance, equity, temporal rebalancing, operator behavior, and institutional approval; the trip feeds are non-public, incomplete market samples.
Source: §7 · p. 9
Abstract
from arXiv · showhide
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.
1 Introduction
Municipal micromobility policy edits change feasible sites and demand coverage, requiring repeated comparison of newly optimized alternatives. CLIPPER combines constrained pooled selection with audits and evidence about how policy-input changes affect selected sites.
1 Introduction
- Policy edits can make a previous plan infeasible or reduce its coverage, so alternatives must be reoptimized on common spatial data.The scenario model reflects requirements to revise restrictions, retain mandatory sites, enforce spacing and area allocations, and compare feasible alternatives.Source: §1 · p. 1
- Two checksummed versions of Braunschweig’s official no-parking-zone data change 30 of about 540 selected sites while aggregate coverage shifts by only about 0.1 percentage points.The municipality must still assess, implement, and communicate each change, so the proposed decision support reports site changes alongside coverage.Source: §1 · p. 1
- Full-set greedy is the transparent same-constraint reference, but takes 23–53 seconds per state in the benchmarks, or 4.2–9.7 minutes for eleven states.CLIPPER solves each recorded state from the beginning, using a replaceable pool rule while calculating exact gains and checking active constraints within the pool.Source: §1 · p. 2
- CLIPPER’s contributions include exact enforcement of recorded constraints, fixed-width and adaptive-budget pool modes, and an offline audit of coverage omitted by the restricted pool.A fixed ordering resolves ties; the audit scans every remaining feasible candidate and records omitted coverage gain in each round.Source: §1 · p. 2
- This article extends the earlier four-page report with audits at three K values, affected-candidate score updates, evaluation of two official policy geometries, and a proposed implementation process.The evaluation covers all eleven states of controlled three-city scenario chains.Source: §1 · p. 2
- 0.245, 0.003, and 0.001 percentage points are CLIPPER-F(1024)’s mean coverage gaps to same-policy full-set greedy in Braunschweig, Munich, and Berlin; rollout is 13.6–28.9× faster.These are means over the eleven scenario states.Source: §1 · p. 2
2 Related work
Prior work reduces greedy optimization effort through bounds, sampling, thresholds, or maintaining solutions across updates. CLIPPER instead restricts the candidate set and recomputes each recorded policy state under its explicit constraints.
Reducing work in greedy submodular optimization
- Lazy, stochastic, and thresholded greedy reduce gain calculations through bounds, sampling, or gain thresholds, while CLIPPER restricts the selector’s candidate set.The approaches operate under their stated feasibility models.Source: §2 · pp. 2–3
- CLIPPER limits the candidates passed to the selector, computes exact current gains within that pool, and checks combined scenario constraints before insertion.Its primary comparisons use full-set greedy under the same policy as the corresponding CLIPPER mode.Source: §2 · p. 3
Optimization under changing inputs
- Unlike dynamic or learning-augmented methods that maintain solutions across updates, CLIPPER discards the previous plan and solves each recorded policy state from the beginning.The benchmark scenarios combine locks, area caps, conflict classes, exclusions, and network-distance spacing.Source: §2 · p. 3
Facility location for micromobility
- Micromobility facility research includes GIS station siting, geofenced parking, time-varying curb allocation, and reinforcement-learning approaches; CLIPPER focuses on deterministic recomputation under explicit policy states.Source: §2 · p. 3
Learning for combinatorial optimization
- CLIPPER accepts a replaceable candidate-pool source, while its experiments use a deterministic score based on demand each candidate would cover on its own.Source: §2 · p. 3
3 Problem formulation
The problem formulation represents parking locations as candidates and demand as weighted points, with the objective of maximizing weighted union coverage. Each recorded scenario defines which plans are feasible, and each policy edit creates a new state to solve and audit.
3 Problem formulation
- The objective f(S) is the weighted union coverage of demand covered by the selected plan S; a candidate’s marginal contribution is still-uncovered demand in its coverage set.The marginal contribution is nonnegative and can only shrink as the incumbent set grows.Source: §3 · p. 3
- Proposal groups form the candidate pool, while each candidate belongs to exactly one accounting group for cap counting; proposal groups may overlap.Source: §3 · p. 3
- A scenario records active proposal groups, exclusions, locked facilities, global and accounting-group caps, conflict classes, and minimum network spacing.In the benchmark, conflict classes are disjoint and the distance rule handles arbitrary pairwise spacing conflicts separately.Source: §3 · p. 3
- Locked facilities remain in every feasible plan, even inside exclusion zones, while exclusions apply only to new placements; the locks are assumed feasible.Source: §3 · p. 3
- Each recorded policy edit produces a new instance solved from the beginning, and the resulting state can be audited.The audit scans all remaining candidates and calculates coverage gain omitted from the restricted pool.Source: §3 · p. 3, Figure 1 · p. 4
- The objective uses temporally aggregated trip records as weighted demand points; temporal utilization and rebalancing are analyzed after spatial selection.Source: §3 · p. 3
4 CLIPPER: optimization over a restricted candidate pool
CLIPPER forms bounded candidate pools, selects the feasible candidate with the greatest exact current gain, and can audit the pool against all remaining feasible candidates. Its modes differ in how they allocate candidate slots and accounting caps.
4 CLIPPER: optimization over a restricted candidate pool
- Each round, proposal groups offer bounded lists ranked by singleton coverage; CLIPPER evaluates exact current gains for pooled candidates and selects the largest feasible gain.The scan continues past selected or infeasible candidates until the requested group-list width is filled.Source: §4 · p. 4
- CLIPPER-F offers up to K candidates per active group with balanced caps; CLIPPER-A distributes a total Bprop-slot budget using coverage-prioritized caps.The two modes share the objective, selector, and constraint checks.Source: §4 · pp. 4–5
- Mandatory locks remain, while selected sites must satisfy budgets, exclusions, spacing, and conflict checks; deterministic ordering resolves exact ties.The fixed order is based on recorded proposal-group order and stable within-group ranks.Source: §4 · pp. 4–5
- The offline audit compares the best feasible gain in the full remaining set with the best pooled gain; their difference is the gain omitted in that round.Because the full-set maximum requires exact gains for every remaining candidate, the audit is intended after a run or at selected checkpoints; a full scan can confirm termination.Source: §4 · pp. 4–5
- CLIPPER-F requires O(T G_eff K c) gain-calculation work versus O(T|V_L(Ω)|c) for full-set greedy; if every feasible candidate is pooled each round, both return the same greedy sequence.Here, G_eff is the number of active groups and c is the largest demand support of one candidate.Source: §4 · p. 5
5 Empirical evaluation
Across complete eleven-state edit chains in three cities, the evaluation compares CLIPPER with same-policy full-set greedy, audits restricted candidate pools, and tests score updates and official policy inputs.
5.1 Setup
- The benchmark demand comes from three non-public operator trip feeds, with origins and destinations snapped to feasible support points and counted as endpoint demand.Individual trip records and coordinates are not released.Source: §5.1 · p. 6
- The spatial objective uses weighted point coverage within a 200 m walk-network radius, with shared demand, candidates, policy constraints, and facility budget within each state.The three-city benchmark uses complete candidate and demand data without downsampling.Source: §5.1 · p. 6
- The controlled E0–E10 chains progressively add exclusions, mandatory locks, spacing, and dense-endpoint halos, and methods are rerun on every state.Each state uses full-set greedy under the same cap policy as its corresponding CLIPPER mode.Source: §5 · p. 5, §5.1 · p. 6
5.2.1 Full-city comparison under the same policy (Q1).
- Across 11 states, CLIPPER-F(1024) trails same-policy full-set greedy by 0.245/0.003/0.001 percentage points and is 13.63×/15.37×/28.87× faster in Braunschweig/Munich/Berlin.Mean rollout times fall from 24.029 to 1.762 seconds in Braunschweig, 22.943 to 1.493 in Munich, and 52.685 to 1.825 in Berlin.Source: §5.2.1 · p. 7, Table 3 · p. 8
5.2.2 A fixed candidate order and scores updated during selection
- At K=1024, the pool omitted no larger feasible gain in 51.0%, 100.0%, and 100.0% of audited rounds in Braunschweig, Munich, and Berlin, yet no audited run stopped with outside-pool gain available.The exact audit scans all remaining feasible candidates after each selection and performs a terminal check.Source: Table 4 · p. 8, §5.2.2 · p. 8
- Updating affected scores changed mean coverage by +0.2037, +0.0049, and −0.0006 percentage points in Braunschweig, Munich, and Berlin, while requiring more time in all three cities.Median paired wall-time ratios were 2.75×, 1.76×, and 2.32×, respectively.Source: §5.2.2 · p. 8, Table 4 · p. 8
5.2.3 Documented policy-input case (Q3).
- Two official Braunschweig policy versions produced plans differing in 30 of about 540 sites, while coverage changed by −0.094 and −0.106 percentage points under fixed and updated scores.The newer resource geometry added 3,218 forbidden candidates; both runs stopped below the 600-site budget after finding no positive feasible gain.Source: §5.2.3 · pp. 8–9
5.2.4 Recorded audit and repeatability checks.
- Three reruns of every state and city—99 runs total—reproduced coverage, step counts, gain calculations, termination reasons, and terminal flags; none stopped because its pool was too narrow.Every run ended with no feasible candidate that could add coverage.Source: §5.2.4 · p. 9
6 Municipal implementation pathway
The proposed municipal process pairs coverage with changed-site reporting, calibrates score updates locally, and scans the full candidate set before a final decision. A pilot assigns policy and acceptance checks to the municipality and supplies plans, comparisons, and audit records through CLIPPER.
6 Municipal implementation pathway
- At K=1024, the pool omits no larger feasible gain in every audited Munich and Berlin round, but in 51% of Braunschweig rounds.The proposed process scans every remaining candidate and records what the pool omitted before the final decision.Source: §6 · p. 9
- Two official Braunschweig no-parking-zone versions yielded 30 removed sites, 22 newly forbidden and eight still feasible.Both runs used identical demand, a 600-site budget, and no locks or spacing.Source: Table 5 · p. 9
- In the proposed pilot, a municipal policy owner defines constraints and acceptance checks, while a data steward validates demand, candidates, and the network.Each edit creates a fresh scenario; the interface shows coverage and retained, removed, or added sites, and the chosen state receives a final scan and archive package.Source: §6 · p. 9
7 Limitations
The evaluation measures optimizer behavior, not planning use or deployment outcomes, and its model, data, and runtime comparisons have stated boundaries. Learned candidate rules also require validation on unseen data and bias checks.
7 Limitations
- Optimizer experiments do not estimate edit frequency, acceptable response times, alternatives considered, or planner utility without recorded planning sessions or edit logs.Reported speedups cover optimization rather than end-to-end deliberation.Source: §7 · p. 9
- The weighted point-coverage model omits curb capacity, congestion, compliance, equity, temporal rebalancing, operator behavior, and institutional approval.The three trip feeds are non-public, incomplete market samples, and a held-out city–provider pair is needed to assess transfer beyond them.Source: §7 · p. 9
- Runtime speedups do not separate pool restriction from execution technique, and comparison with classical lazy greedy under matched conditions remains open.The reported speedups compare implementations within the stated timing boundary.Source: §7 · p. 9
- The proposed pilot leaves policy and acceptance thresholds with the municipality; CLIPPER supplies plans, comparisons, and audit records.This defines the pilot’s institutional boundary rather than evidence of deployment outcomes.Source: Table 6 · p. 9
- Learned candidate rules require validation on unseen data and checks for bias.The paper also notes that operator trip feeds cannot be released, distinguishing deterministic replay from public reproduction.Source: §7 · pp. 9–10
8 Conclusion
Across three cities, CLIPPER-F approaches full-set greedy coverage while substantially reducing rollout time, and the audited runs satisfy the stated pool-limit stopping condition. The proposed process uses optimization, audits, and policy-version comparisons to support municipal review.
8 Conclusion
- CLIPPER-F’s mean coverage gap over the complete chain is at most 0.245 percentage points, while its mean rollout is 13.6–28.9× faster than full-set greedy under the same policy.At K=1024, none of the 11 audited runs per city ends because of the pool limit.Source: §8 · p. 10
- Both CLIPPER modes enforce every encoded hard constraint and replay recorded states deterministically.The optimizer computes feasible alternatives, the audit measures omitted gains, and policy-version comparisons identify changed sites.Source: §8 · p. 10
- Braunschweig plans differ in 30 sites despite similar coverage, so aggregate coverage alone cannot describe what a municipality would implement.The proposed process compares alternatives, calibrates score updates locally, scans the full candidate set before a final decision, and archives policy inputs and selected sites.Source: §8 · p. 10