Graphe chemin, avec arrête minimale

Bonjour, Voici mon problème : - on a M villes de coordonnées (x, y) - on a N stations services de coordonnées (x’, y’)

Avec ma voiture j’aimerais passer par toutes les villes M, mais j’aimerais aussi minimiser la taille de mon réservoir à essence. Je veux donc que le volume d mon réservoir à essence soit le plus petit possible. L’essence dépensé entre deux stations services est égale à la distance entre ces stations (dans le plan euclidien orthonormé). Étant donner que je peux passer autant de fois que je veux dans les stations services afin de remplir mon réservoir, quel est le chemin passant par toutes les villes (rien ne m’empêche de passer plusieurs fois dans les mêmes villes ou dans les mêmes stations à essences) qui me permet d’avoir une contenance minimale pour mon réservoir ?

En faite j’aimerais bien créer un code en javascript/python qui réponde à ce problème, mon problème c’est que je ne connais aucun algorithme qui permette de résoudre ce problème, j’ai regardé sur internet avec les algorithmes de Kruskal… mais cela ne semble pas m’aider.

Ainsi quelqu’un connaîtrait-il une méthode, un algorithme efficace qui me permettrait de résoudre ce problème ?

Merci d’avance.

P.S : Veuillez-m’excuser pour mon français qui peut-être maladroit (je suis anglais).

Je crois que ça ressemble pas mal au dernier problème des qualifications de cette année pour prologin : https://prologin.org/train/2017/qualification/taxi_des_neiges Si je me souviens bien, c’était la distance au carré qui était comptée, mais je pense que c’était juste pour simplifier les calculs.

Du coup j’ai pas trop envie de donner un indice avant la clôture le 4 janvier (si quelqu’un pense que c’est pas grave…). Si tu peux attendre jusque là, des solutions seront sûrement publiées et tu pourras t’en inspirer.

Oui bien sûr j’ai jusqu’au 15 janvier, j’ai le temps