From chaotic backtracking to clean neighborhood sweeps 从混乱折返,到整齐的逐街区扫街
A vehicle-routing optimizer for multi-day delivery across Montreal — built on Google OR-Tools, with constraints that encode how good drivers actually work. 覆盖蒙特利尔的多日配送路径优化器——基于 Google OR-Tools,用约束把"好司机的开法"写进了数学。
The problem问题
Naive shortest-path routing produces plans that look optimal on paper and feel insane behind the wheel: the route zig-zags between distant neighborhoods, doubles back late in the day, and lets the "return home" leg drag afternoon stops in random directions. Drivers ignore plans like that — which means the plan is worthless. 朴素的最短路径算法排出来的计划,纸面上最优,方向盘后面看简直是疯的:路线在相距很远的街区之间来回横跳,临近收工还要折返,"回家"这一段还会把下午的配送点拽向莫名其妙的方向。司机根本不会照着开——而司机不执行的计划,一文不值。
The constraint约束
The optimizer had to respect three things standard VRP formulations don't give you for free: 优化器必须满足三件标准 VRP 模型不会白送你的事:
- Finish a neighborhood before leaving it. Once a driver enters a district, all stops there get done — no coming back tomorrow for one missed address. 进了街区就干完再走。司机一旦进入某个片区,里面的点必须全部跑完——不能明天再回来补一个漏掉的地址。
- The commute home doesn't count. The drive back to the depot shouldn't distort where the last deliveries of the day go. 回家的路不计成本。开回仓库的通勤路程,不应该扭曲当天最后几单的走向。
- Days connect. Whatever is left over from Day 1 must anchor the start of Day 2 — the driver resumes where they stopped, not from a fresh shuffle. 今天连着明天。第一天剩下的点必须锚定第二天的起点——司机从昨天停下的地方继续,而不是重新洗牌。
The solution方案
- Open VRP modeling — the return-to-depot arc is weighted to zero, mathematically removing the "pull" that home exerts on late-day stops. Open VRP 建模——把返回仓库的边权重置零,从数学上消除"家"对傍晚配送点的引力。
- District contiguity constraints — formulated with constraint-programming indicator variables, so entering a district commits the solver to completing it. 街区连续性约束——用约束规划的指示变量表达:一旦进入某片区,求解器就被绑定必须把它跑完。
- Cross-day state carryover — leftover stops persist and force Day 2 to inherit yesterday's active district before opening new zones. 跨天状态延续——剩余配送点会持久化,并强制第二天先继承昨天未完成的片区,再开新区。
- Graceful degradation — when hyper-dense areas make hard constraints infeasible, the solver automatically relaxes them into soft penalties instead of failing. 优雅降级——当超高密度区域让硬约束无解时,求解器自动把它们放宽为软惩罚,而不是直接失败。
- An interactive Leaflet map — toggleable route layers with direction-marking animations, so the client could see the difference instead of reading distance tables. 交互式 Leaflet 地图——可切换的路线图层加方向指示动画,让客户亲眼看到差别,而不是去读里程表格。
Proof: see it, don't take my word for it证明:眼见为实,不用信我的话
Delivered as a runnable repository — solver, mock-data generator, baseline-vs-optimized comparison script, interactive GIS map, and a print-ready PDF report. Anyone can reproduce every figure with two commands. 以可运行的代码仓库交付——求解器、模拟数据生成器、基线对比脚本、交互式 GIS 地图、可打印的 PDF 报告。任何人两条命令就能复现每一张图。
Where else this applies还能用在哪
Field-service scheduling, last-mile delivery, sales-territory planning, technician dispatch — any operation where "the math says drive across town twice" costs you real fuel and real morale. 上门服务排班、最后一公里配送、销售片区规划、技师派单——任何"数学说要横穿全城两趟"会烧掉真实油钱和士气的场景。
← All case studies← 全部案例