Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @PierreLaur,validated by @LeMasSon,@Rob-G and @Aldoggen.
If you have any issues, feel free to ping them.
For the early birds who played this puzzle “pre-release” : I allowed myself to make a small last-minute change, even though the puzzle was just approved : all distances should now be rounded to the nearest integer. I realized this is necessary to follow TSPLIB/CVRPLIB standards, the optimal values on the benchmark instances were incorrect otherwise 
.
This doesn’t really change much, but the true nerds can now use CVRPLIB to benchmark against the state of the art. Working with ints should also be a bit nicer, especially in some languages.
1 Like
I did some benchmarking ! Here are the scores these 8 solvers/algorithms would obtain on the leaderboard.
Please take this with a grain of salt as this is not a clean and principled benchmark, but it should give you some baselines to see how good your solvers are.
Solver | Score | Details
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Random Search | 261253 | 'Randomly insert customers in a route
Sweep Heuristic | 102345 | 'Try multiple random starting angles, optimize tours with Concorde
OR-Tools Routing | 91959 | 'Google's open-source optimization library for routing problems
LKH-3 | 90268 | 'Keld Helsgaun's solver for many academic TSP/VRP variants
Hexaly | 88632 | 'Commercial optimization solver. Can prove optimality/infeasibility
PyVRP | 88094 | 'Wouda, Lan & Kool's HGS-based solver for multiple VRP variants. Number 1 in the 2022 DIMACS VRPTW competition
HGS | 87934 | 'Thibault Vidal's state-of-the-art academic CVRP solver
MDM-HGS | 87905 | 'Maia, Plastino & Souza's improved HGS with Data Mining. Number 2 in the 2022 DIMACS CVRP competition (but number 1 on instances of size <= 200 like here)
All solvers were given 10 seconds of solving time and 10 submit attempts, I kept the best score. I fiddled a bit with the parameters when appropriate but didn’t do much tuning.
I tried some MIP/CP/SAT solvers (OR-Tools CP-SAT, Gurobi) but they time out during modeling and/or fail to find a feasible solution for larger instances. These have the benefit of being able to prove optimality and infeasibility and are very useful for smaller instances, but they do not scale very well on the VRP and typically require more time than metaheuristics.
By giving more time to the best solvers, I was able to reach a score of 87904. This could be the optimal score, but I was not yet able to prove it.
I am very impressed by some of the scores obtained already. @CodeVanguard’s solver does better than the best specialized CVRP solver I’ve been able to find! @trictrac and @cedricdd are doing amazing as well!
If you can reach the top of the leaderboard like these gentlemen, you are incredibly skilled! I have two requests for you:
- Share some of your secrets with the rest of us! What algorithms are you using? What do you think are the key components? Are there some creative implementation tricks?
- Try your solver on open instances from CVRPLIB! Improving on the best known values on some instances would be amazing!
3 Likes
I will start sharing ideas here, although my solution is not the best. I took inspiration from Hybrid Genetic Search, a very important innovation in VRP research, and used a memetic algorithm (genetic algorithm with local search to improve individuals).
Some key tips :
- There is a polynomial algorithm to optimally reconstruct feasible tours from a single permutation of the customers. This allows genetic algorithms to use permutations as the solution representation, as in the TSP.
- For local search, using multiple neighbourhoods is crucial ! Each new neighbourhood had a great impact on the performance of my solver.
2 Likes
Hi all codegamers,
I’m happy to discover it’s perhaps not possible to reach better than 87904. But champion scores are here to be outperformed.
I spent the 2 last weeks to study this optimization puzzle everyday and spent time to study a lot of new features, it’s fun to discover the path is more important than the result.
This experience in searching is really the most awarding part.
So I would say my secret is to learn a lot how to make a program as fast as possible and trying all possible solution. It’s not a big secret, but, computing optimization is really a very important part.
I’m also happy to discover all these solvers. But the more important skill to reach is fast computing to compute million of possibilities.
CVRP is really a new concept for me, I never heared before so thanks you so much for this puzzle.
For other who try to solve this puzzle, just learn a lot more about CVRP algorithm.
Learn everyday how to be fast and the rest will be easy.
Just one last advice point, Benchmark information points will perhaps gradually switch off the game.
In 6 months a lot of person will get top score (because it’s too easy, not to search by itself complexe solution).
If you want to keep it alive for a long time, make it a lot more complexe and without easy to find solutions.
Thanks again for this great game.
2 Likes
Thanks for the advice. About the benchmark : this is a well-known and studied computer science anyway. As with the TSP, if players want to copypaste some external solver instead of making their own, there is no way to prevent them from doing it. This is why I don’t care too much about showing good CVRP solvers, they will be found anyway. There are other optimization puzzles with more “honest” leaderboards !
I would rather have players know how these good solvers perform so that they can compare themselves (AFAIK, being able to do that is pretty much a unique feature of this puzzle !). They can also look into external code and learn from it !
2 Likes
How the capacity is managed in the HGS algorithm ? Thanks.
Maybe you figured it out, but basically it adds a penalty like lambda * excess_load to the objective. This is the usual way to handle additional constraints in simulated annealing, tabu search, etc. lambda is updated dynamically depending on the number of feasible/infeasible solutions generated.
there are a few more details, you can read about them in the paper
2 Likes
The Clarke and Wright Savings Heuristic effectively reduces the total distance traveled by iteratively merging routes that offer the greatest savings, all while respecting vehicle capacity constraints. By prioritizing the most significant savings first and ensuring that route continuity and capacity are maintained, the algorithm efficiently constructs optimized routes for the given set of customers.