Pull instead of push

This is joint work with Bjørn Petersen.

Almost every large routing or scheduling solver has the same shape. There is an outer loop that keeps track of the overall plan, and an inner loop that repeatedly answers one narrow question: given the current prices, what is the best single route I could add?

The inner question is a shortest path problem carrying baggage. The route has to respect a vehicle’s capacity, its shift length, delivery time windows, which stops can legally follow which. Formally it is the shortest path problem with resource constraints, and in a working solver it is where nearly all the time goes.

Which is good news, in a way. When one loop dominates the runtime, you know exactly where to stand, though it is worth checking which loop, because in other decompositions the bottleneck sits in the master problem instead.

How the loop normally works

The standard method builds partial routes and extends them one stop at a time. A partial route is called a label: where it is, what it cost, how much capacity is used, what time it is.

Two things happen constantly. Extension: take a label, add a legal next stop, make a new label. Dominance: if route X is at the same place as route Y, and is no worse on every single measure, cost and time and remaining capacity, then Y can never lead anywhere X can’t. Throw Y away.

Dominance is what keeps this from exploding. It is also the hot loop inside the hot loop: constant comparison of every new label against the ones already there.

Why parallelising it is awkward

The obvious move is to use more cores. The obvious approach fails in an interesting way.

Classical labelling pushes: take a label, generate its extensions, and write each one into wherever it lands. With many threads pushing at once, they write into the same places simultaneously. Now you need locks, or lock-free structures, and you spend your parallelism defending the data instead of doing work.

The problem is not the computation. It is the direction of the writes.

Turning it around

So don’t push. Pull.

Group the labels into buckets by location and by roughly how much resource is used. Then, instead of each label pushing its extensions outward, each bucket goes and gathers the labels that would reach it.

The arithmetic is identical. But now every bucket writes only to itself. A thread that owns a bucket owns it completely, so workers never have to coordinate access to a bucket at all: no collisions and no locks on the buckets themselves. What is left to synchronise is global rather than structural, the best bound found so far and the pool of finished paths, one lightweight lock each.

Two things stack on top. Bidirectional search builds routes from both ends and meets in the middle. That is much less work, because the search grows sharply with depth, and we let the meeting point move as the search learns where the real cost lies rather than fixing it up front. And because a bucket’s labels now sit together in memory, the dominance comparison can be vectorised: the CPU checks several labels against a candidate in one instruction instead of one at a time.

What it was worth

There are two numbers, and they answer two different questions.

The first is an ablation. The baseline is the same algorithm with none of the three ideas switched on: one thread, one direction, dominance checked one label at a time. Against that, on the same instances and on one 16-core desktop, the full version is around 18× faster on hard instances, and up to 274× on the instance that gains most. That figure includes the parallelism itself rather than isolating it, which is the honest way to read it: reorganising the loop is what made the parallelism available in the first place, so the two are not separable.

The spread matters more than the headline. The gain is largest exactly where the instances are worst: where labels pile up, where dominance is doing the most work, where the old approach was struggling most. That is the useful shape for a speed-up to have. A method that is fast on easy problems and slow on hard ones has not helped with anything; your easy problems were already fine.

The second is against a competitor. bucket-graph-spprc is our open implementation of the state-of-the-art bucket-graph algorithm of Sadykov, Uchoa and Pessoa. Being a push algorithm, it parallelises the two search directions and its internal sorting, but not the buckets, for exactly the reason above: extending one bucket writes into several successor buckets that other threads are also writing. Run on that same machine and those same instances, each solver in its own best parallel configuration, pull is 1.9 to 2.4 times faster, and faster on 164 of the 168 instances.

So the fair statement is not that pull uses more threads. It is that pull can put its threads somewhere push cannot.

What it costs

The ordering that makes this safe is not free, and it is worth being plain about where the bill lands.

A bucket can only be gathered once every bucket that feeds it is finished, so the buckets have to be sized small enough that those dependencies never form a cycle. That forces the bucket size down to the smallest resource consumption on any arc touching the vertex, which is the largest size for which acyclicity still holds. Sadykov and co-authors do not pay this, because a push algorithm can tolerate small cycles.

Finer buckets mean more of them, longer chains of dependency between them, and fewer labels sitting in each one for the vector unit to work on. And the amount of parallelism actually available is bounded by the longest chain of dependent work in the graph, however many cores you own. On the hardest instances, the ones with large neighbourhoods, that restriction bites: parallelism is limited and the worst case has a heavier tail. Allowing bounded cycles is the obvious next move and the one we would most like to make, but it threatens the immutability the whole scheme is built on.

The general shape

None of this is a new algorithm. It is the same computation, reorganised so that the machine underneath can actually do it in parallel, and modern machines punish you hard for getting that wrong. The number of cores has grown far faster than the speed of any one of them.

The move, stop handing work out and start letting workers come and take it, is not specific to routing. It shows up wherever many producers write into shared state. Whenever a parallel implementation is disappointing, it is worth asking whether the work is being pushed when it could be pulled.

The paper is arXiv:2511.01397.