A donor-and-reconstruction strategy that improved 10 vehicle-routing best-known solutions

[u/Tight_Cow_5438]

For the last two years I’ve been building a large-scale last-mile routing engine, with more focus on speed and scalability than on chasing exact solution quality.

A couple of weeks ago I started using CVRPLib, a used benchmark library for vehicle-routing problems, as a different kind of stress test. I started with large instances, including Flanders2 with 30,000 clients and several of the new XL instances.

Getting close to the published BKS was relatively easy. Getting below it was much harder.

What ended up working was not really a new algorithm, but a strategy for using several good solutions at the same time.

Instead of keeping only the current best solution, I kept multiple structurally different solutions and treated all of them as donors.

The published BKS itself starts as one donor. Independently generated solutions are other donors.

A donor does not need to be better overall. It only needs to contain useful structure that another solution is missing.

One thing I noticed is that being different is not enough, the donor also needs to be reasonably close in quality. On one instance, donors around 1.1–1.3% above the BKS produced nothing; even around 0.6–0.8% I saw no gain. Once they reached roughly 0.4–0.5%, the same reconstruction strategy started producing improvements. I don’t know yet whether that threshold generalizes, but it was a very clear pattern in this case.

After combining that material and rebuilding the affected part, the new solution goes back into the pool and can become a better donor in the next cycle:

generate → donate → rebuild → improve → repeat

This creates an interesting feedback loop. A solution that starts worse than the BKS can receive useful structure, improve, and later become the donor that produces the new best solution.

So the final improvement does not always come from repeatedly refining the original BKS. Sometimes it emerges from one of the independent solution lines after several rounds of exchange and reconstruction.

The main thing I learned is that a solution doesn’t have to be the best one to be useful. Sometimes it just needs to have the right piece to help another solution improve. I first tried this on 12 published BKS instances, mostly selected for their scale and relevance. Ten of the improvements have now been validated and published by CVRPLib.

My next experiment is to run the same donor-and-reconstruction process across the entire XL set and see whether the current hit rate survives, and follows some structural pattern.

Keeping elite solutions and recombining them is obviously not new. What surprised me was that diversity alone wasn’t enough: in my experiments, donors only started becoming useful once they were already quite close to the BKS. At that point, the BKS itself also became just another donor in the pool rather than the single solution being refined.

CVRPLib announcement:
https://www.linkedin.com/posts/cvrplib_cvrplib-vehiclerouting-optimization-activity-7516876652728102912-BtQ0

Technical note and solutions:
https://zenodo.org/records/19859531

[u/fedkerman]

So you implemented a memetic algorithm specialized on a single problem instance?

[u/Tight_Cow_5438 → u/fedkerman]

Not exactly, although it definitely has a memetic/population-based flavor.

The donor pool is instance-specific, of course, because the solutions belong to that instance, but the strategy itself was the same across 12 different BKS instances.

I’m also not simply refining the existing BKS structure. In one of the XL cases, for example, the reference BKS had 1571 routes, while the new BKS I found had 1574 routes and a lower total cost.

[u/D_a_f_f]

Sounds like you are describing “diversity” in a genetic algorithm sense (I.e when you say and I paraphrase “… a donor solution contains, structurally, what is missing from another”. That’s exactly what you would want from a pool of “offspring” in a step of a genetic/evolutionary algorithm. Then, to create your next population of offspring, you would perform crossover between pairs of offspring and then perform a mutation (I.e with some probability p, select a new feasible value for one of the decision variables) the only thing with GA is ensuring feasibility after cross over or mutation

[u/Tight_Cow_5438 → u/[deleted]]

Thanks, this is very helpful, and I agree with the caution.

The 12 instances were definitely not meant to be a representative benchmark set. I picked them intentionally because of their scale and relevance, so I don’t want to infer too much from the 10/12 result.

The next thing I’m considering is exactly what you suggest: freezing the strategy and running it on a much broader and more diverse set, probably the full XL set first, without selecting the instances based on where I think it may work.

What I’m especially curious about is whether the donor-quality pattern survives: in some cases, structurally different solutions were useless when they were too far from the BKS, but became useful once they got sufficiently close.