Comme promis voici l'indication numérique du minimum:
Spoiler : [Afficher le message] 48 hexagones de route + les villes

@nicolas647: Bravo, tu es le seul à avoir remarqué que sur le pavage hexagonal la "norme" et donc la métrique se comporte étrangement, cependant j'ai choisi le placement des villes pour que la solution semble naturelle et que cette dernière soit unique!

Merci à tout les participants!

NB: Certains auront vu un lien avec les arbres de Steiner, qui concerne le même problème mais sur R², ici le pavage hexagonal n'a pas le même comportement au niveau de la métrique (tentez voir de trouver le chemin le plus court entre deux points vous verrez que parfois il n'est pas unique) mais j'ai placé les villes pour que le comportement soit intuitif et le minimum a priori unique.