提出CLIPPER算法,实现城市级共享出行规划的快速重播与优化。
CLIPPER: Replayable Shortlisted Optimization for Repeated Spatial Coverage Planning
- 构建候选池并动态验证约束,精确计算每步收益。
- 在柏林、慕尼黑等地平均覆盖率误差小于0.25个百分点,提速13.6至28.9倍。
- 支持政策反复测试,适合市政交通规划人员使用。
基于德国布伦瑞克市的实际运营需求,本研究针对地理围栏排除区、必留点位、间距规则和区域容量限制等约束,设计城市级微出行设施布局规划。每次策略调整需生成新可行方案,传统全集贪心法在城市尺度上耗时数十秒。本文提出CLIPPER(Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay),通过构建有界候选池,在选择前精确计算当前收益并校验所有活跃约束。每个候选单独覆盖贡献决定初始排序。离线扫描获取候选池遗漏增益;在线时,保守边界触发扩展或审计。CLIPPER-F为每组提案分配相同候选名额,在布伦瑞克、慕尼黑、柏林三地平均覆盖率与全集贪心相差不超过0.245个百分点,平均推演时间降低13.6至28.9倍。CLIPPER-A则将总候选预算按需分配,采用覆盖优先策略下,推演时间仅为全集贪心的9%至15%,布伦瑞克、慕尼黑、柏林的平均覆盖率差距分别为1.82、0.12、0.27个百分点。CLIPPER实现了城市级规划状态的快速重播与约束严格满足。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。