4 Aug 2026 ==========================================
CVRP benchmark from size 100 to 1,000,000
==========================================
Hans Mittelmann
<mittelmann@asu.edu>
Logfiles are at: plato.asu.edu/ftp/hex_hgs_logs/
Platform: AMD Ryzen 9 5900X (12 cores, 128GB). Hexaly 15.0, HGS-CVRP-2.0.0, PyVRP-0.13.4, AILSII 2023.0106, filo2
Hexaly frequently compares their hybrid heuristic code to exact solvers such as Gurobi and OR-Tools, see here.
One may rather compare to other heuristics as listed here
This benchmark is showing how well problems from the X/XL/AGS-sets of CVRPLIB can be approximately solved with Hexaly, HGS-CVRP, PyVRP and AILSII
Results for additional very large problems are given below.
Hexaly runs on 12 threads while the others are serial; they are executed in a single run with default parameters and random seed 1. Further improvements can be obtained by running with 12 random seeds.
We list the gap percentages to the best known solution BKS and the scaled and shifted (by 10) geometric mean of the gaps. The max compute times were chosen to show obtainable accuracy. The geomeans are similar for a fraction of the times.
============================================================================ geom mean 1 2.57 2.52 ---------------------------------------------------------------------------- problem HGS gap Hexaly gap PyVRP gap BKS Time ---------------------------------------------------------------------------- X-n101-k25 27591 0 27591 0 27591 0 27591 300 X-n106-k14 26376 0.05 26362 0 26378 0.06 26362 300 X-n110-k13 14971 0 14971 0 14971 0 14971 300 X-n115-k10 12747 0 12747 0 12747 0 12747 300 X-n120-k6 13332 0 13332 0 13332 0 13332 300 X-n125-k30 55539 0 55700 0.29 55546 0.01 55539 300 X-n129-k18 28940 0 28940 0 28995 0.19 28940 300 X-n298-k31 34231 0 34239 0.02 34242 0.03 34231 600 X-n303-k21 21738 0.009 21802 0.30 21826 0.41 21736 600 X-n308-k13 25862 0.01 26009 0.58 25899 0.15 25859 600 X-n313-k71 94051 0.009 94444 0.43 94265 0.24 94043 600 X-n317-k53 78368 0.02 78355 0 78368 0.02 78355 600 X-n322-k28 29855 0.07 29932 0.33 29943 0.37 29834 600 X-n327-k20 27557 0.09 27649 0.42 27602 0.25 27532 600 X-n459-k26 24160 0.09 24252 0.47 24239 0.41 24139 1200 X-n469-k138 222074 0.11 223705 0.85 222589 0.34 221824 1200 X-n480-k70 89468 0.02 89781 0.37 89574 0.14 89449 1200 X-n491-k59 66531 0.07 66762 0.42 66750 0.40 66483 1200 X-n502-k39 69265 0.06 69242 0.02 69425 0.29 69226 1200 X-n513-k21 24201 0 24255 0.22 24255 0.22 24201 1200 X-n524-k153 154755 0.10 154839 0.16 155449 0.55 154593 1200 X-n613-k62 59601 0.11 59882 0.58 59738 0.34 59535 1800 X-n627-k43 62362 0.32 62450 0.46 62449 0.46 62164 1800 X-n641-k35 63867 0.29 64006 0.51 63939 0.40 63682 1800 X-n655-k131 106815 0.03 106808 0.03 106850 0.07 106780 1800 X-n670-k130 146783 0.31 147078 0.51 148547 1.51 146332 1800 X-n685-k75 68344 0.20 68532 0.48 68492 0.42 68205 1800 X-n701-k44 82277 0.43 82411 0.60 82172 0.30 81923 1800 X-n876-k59 99687 0.39 99877 0.58 99628 0.33 99299 2400 X-n895-k37 54098 0.44 54256 0.74 54143 0.53 53860 2400 X-n916-k207 329909 0.22 330945 0.54 329582 0.12 329179 2400 X-n936-k151 133193 0.36 133864 0.87 134754 1.54 132715 2400 X-n957-k87 85581 0.14 85632 0.20 85694 0.27 85465 2400 X-n979-k58 119270 0.25 119396 0.36 119347 0.31 118973 2400 X-n1001-k43 72590 0.34 73039 0.96 72829 0.67 72346 2400 ============================================================================ ============================================================================ geom mean 7.76 3.89 ` 1 ---------------------------------------------------------------------------- problem Hexaly gap PyVRP gap AILSII gap BKS ---------------------------------------------------------------------------- XL-n1234-k55 97624 1.06 97351 0.77 96791 0.19 96603 XL-n1701-k562 529791 1.72 524198 0.64 521360 0.10 520843 XL-n2028-k617 551687 1.38 547809 0.67 544618 0.08 544166 XL-n2354-k631 949985 0.99 941979 0.14 941020 0.04 940634 XL-n3007-k658 524766 0.51 523742 0.31 522567 0.08 522126 XL-n3054-k461 790357 1.04 786369 0.53 783044 0.11 782194 XL-n3287-k30 41077 2.21 40518 0.82 40278 0.22 40190 XL-n4063-k347 552915 0.84 551561 0.59 549402 0.20 548330 XL-n4738-k487 766572 0.91 763558 0.51 761159 0.20 759649 XL-n5061-k184 163251 1.10 163004 0.94 161777 0.18 161480 XL-n5174-k55 63987 4.46 62567 2.14 61650 0.65 61254 XL-n6034-k61 66788 3.95 65538 2.00 64941 1.07 64251 XL-n6168-k1922 1548460 1.38 1542299 0.98 1531614 0.28 1527390 XL-n7037-k38 73401 3.73 72253 2.11 70948 0.27 70760 XL-n7193-k1683 2991390 1.12 2961847 0.12 2959384 0.04 2958205 XL-n8028-k294 270708 1.66 269270 1.12 267237 0.35 266295 XL-n8389-k2028 3403790 1.51 3393935 1.21 3361958 0.26 3353305 XL-n9160-k379 329600 1.86 327655 1.25 324594 0.31 323596 XL-n9571-k55 112329 5.63 109602 3.06 107768 1.34 106344 XL-n10001-k1570 2362700 1.37 2350459 0.85 2334541 0.17 2330666 ============================================================================ compute time 3600s ============================================================================= geom mean 8.33 7.97 1.29 1 ----------------------------------------------------------------------------- problem Hex-1 gap Hex-2 gap AIL-1 gap AIL-2 gap BKS ----------------------------------------------------------------------------- Antwerp1 480254 0.63 480071 0.59 477761 .10 477735 .01 477261 Antwerp2 297423 2.11 296945 1.95 291835 .20 291836 .20 291265 Brussels1 507761 1.26 507138 1.14 503014 .32 502232 .16 501434 Brussels2 355991 3.24 358558 3.98 346266 .42 345781 .28 344822 Flanders1 7300240 0.85 7296740 0.81 7254096 .21 7250167 .16 7238697 Flanders2 4515300 3.43 4507090 3.24 4404155 .88 4387244 .49 4365762 Ghent1 473007 0.75 472712 0.69 470052 .12 469924 .009 469482 Ghent2 264845 2.80 264414 2.63 258169 .21 258075 .17 257637 Leuven1 193912 0.55 193868 0.53 193010 .008 193014 .009 192848 Leuven2 113805 2.20 113578 2.00 111656 .27 111631 .25 111355 ============================================================================= Hexaly and AILSII run for 1,2 hours The following computations are done on instances from the filo2 github. The platform is an AMD EPYC 7763, 64 Cores, 2TB, 3.25GHz; 2 hours. ================================================================================ geom mean 1 35 -------------------------------------------------------------------------------- problem BKS size filo2 gap Hexaly gap -------------------------------------------------------------------------------- Abruzzo 311712556 250000 312611292 0.29 332335000 6.62 Basilicata 175623919 150000 176188247 0.32 184348000 4.97 Calabria 1964651530 380000 1966156843 0.08 2025420000 3.09 Campania 391859276 500000 393303129 0.37 1646130000 320 Emilia-Romagna 5405446715 900000 5410581864 0.10 5606280000 3.72 Friuli-Venezia-Giulia 415805616 300000 417116727 0.32 439558000 5.71 Lazio 3145381332 1000000 3149396224 0.13 3328910000 5.83 Liguria 1426389867 320000 1427961138 0.11 1454490000 1.97 Lombardia 1339900081 950000 1344374005 0.33 1513680000 13.0 Marche 420484426 420000 421910854 0.34 462411000 9.97 Molise 111184982 50000 111401631 0.19 112944000 1.58 Piemonte 2627446164 600000 2631885098 0.17 2755270000 4.86 Puglia 1464797603 750000 1468314124 0.24 1560030000 6.50 Sardegna 827934149 470000 830308302 0.29 899752000 8.67 Sicilia 1774262462 800000 1779515900 0.30 1897460000 6.94 Toscana 1084417188 700000 1087382228 0.27 1183730000 9.16 Trentino-Alto-Adige 102063181 100000 102450385 0.38 195075000 91.1 Umbria 545507981 200000 546593385 0.20 923430000 69.3 Valle-D-Aosta 21679514 20000 21756229 0.35 21806200 0.58 Veneto 1050488613 850000 1053594936 0.30 1179940000 12.3 ================================================================================
