PythonGoogle OR-ToolsConstraint ProgrammingFolium / LeafletGIS Visualization

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，用约束条件把好司机的开车习惯写进模型。

2026-07-07 · updated 2026-08-08 · first published on boheastill.com最初发表于 boheastill.com

The problem

Naive shortest-path routing produces plans that look optimal on paper and make no sense behind the wheel. The route zig-zags between distant neighborhoods, doubles back late in the day, and the “return home” leg pulls afternoon stops in odd directions. Drivers ignore plans like that, and a plan drivers ignore is worthless.

The constraint

The optimizer had to respect three things standard VRP formulations don’t give you for free:

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, so the driver resumes where they stopped rather than from a fresh shuffle.

The solution

Open VRP modelling. The return-to-depot arc is weighted to zero, mathematically removing the “pull” that home exerts on late-day stops.
District contiguity. Constraint-programming indicator variables mean that entering a district commits the solver to completing it.
Cross-day carryover. Leftover stops persist, so Day 2 inherits yesterday’s active district before opening new zones.
Graceful degradation. Where hyper-dense areas make a hard constraint infeasible, the solver relaxes it into a soft penalty rather than failing.
An interactive Leaflet map with toggleable route layers and direction animations, so the client could see the difference instead of reading distance tables.

Proof: see it, don’t take my word for it

Baseline route: chaotic criss-crossing paths across the city — Baseline (shortest-path): criss-crossing, backtracking, neighborhood-hopping.

Optimized route: clean sequential sweeps through each district — Optimized: sequential district sweeps a real driver would actually follow.

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.

问题

简单的最短路径算法排出的计划，纸面上最优，开起来却很离谱：路线在相隔很远的街区之间来回跳，快收工了还要折返，“回仓库”这一段还把下午的配送点拉向奇怪的方向。司机不会照这种计划开，而司机不照着开的计划毫无用处。

约束

优化器必须满足三件标准 VRP 模型不会白送你的事：

**进了一个片区就跑完再走。**司机一旦进入某个片区，里面的点要全部送完，不能第二天再回来补一个漏掉的地址。
**回家的路不计成本。**开回仓库的通勤路程，不应该扭曲当天最后几单的走向。
**前后两天要衔接。**第一天剩下的点要作为第二天的起点，司机从昨天停下的地方接着跑，而不是重新排一遍。

方案

**Open VRP 建模。**把返回仓库那段路的权重设为零，从数学上去掉“回家”对傍晚配送点的拉扯。
**片区连续性。**用约束规划里的指示变量表达：一旦进入某个片区，求解器就必须把它跑完。
**跨天延续。**剩余的配送点会保留下来，第二天先接着跑昨天没完成的片区，再开新的。
**平滑降级。**遇到点位特别密集、硬约束无解的区域，求解器会把它放宽成软惩罚，而不是直接失败。
交互式 Leaflet 地图，路线图层可以切换，带方向动画，客户能直接看到差别，不用去读里程表。

证明：眼见为实，不用信我的话

还能用在哪

上门服务排班、最后一公里配送、销售片区规划、技师派单。凡是算法让你横穿全城两趟、白白浪费油钱和司机耐心的场景，都适用。