What actually breaks when you try to scale vehicle routing to ~1M stops? [R]

I’ve been experimenting with scaling last-mile routing problems beyond typical sizes (tens of thousands of stops).

Something interesting I ran into:

At some point, the bottleneck stops being the routing algorithm itself and becomes how the system is structured around it.

A few things that seemed to matter more than expected:

- clustering that accounts for constraints, not just geometry

- limiting route optimization cost as a bounded step

- handling inconsistencies at cluster boundaries

- avoiding recomputing distances repeatedly

What surprised me is that the system started showing close to linear scaling in practice, which is not what I expected given how these problems usually behave.

Curious if others have seen similar behavior when pushing VRP-type problems to larger scales, or if there are known approaches that deal with this differently.