  Extensive research has been conducted, over recent years, on various ways of
enhancing heuristic search for combinatorial optimization problems with machine
learning algorithms. In this study, we investigate the use of predictions from
graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid
Genetic Search (HGS), a state-of-the-art algorithm for the Capacitated Vehicle
Routing Problem (CVRP). The crossover and local-search components of HGS are
instrumental in finding improved solutions, yet these components essentially
rely on simple greedy or random choices. It seems intuitive to attempt to
incorporate additional knowledge at these levels. Throughout a vast
experimental campaign on more than 10,000 problem instances, we show that
exploiting more sophisticated strategies using measures of node relatedness
(heatmaps, or simply distance) within these algorithmic components can
significantly enhance performance. However, contrary to initial expectations,
we also observed that heatmaps did not present significant advantages over
simpler distance measures for these purposes. Therefore, we faced a common --
though rarely documented -- situation of overkill: GNNs can indeed improve
performance on an important optimization task, but an ablation analysis
demonstrated that simpler alternatives perform equally well.
