Algorithme pour chercher un chemin optimal VBA

Messages postés
1
Date d'inscription
jeudi 14 novembre 2019
Statut
Membre
Dernière intervention
23 novembre 2019
-
Bonjour à tous,

Je suis un étudiant au niveau debutant en informatique et j'ai besoin de votre aide.

Dans un fichier excel, j'ai des feuilles avec:
Une matrice de temps qui indique le temps nécessaire pour se déplacer d'une borne électrique X à Y. Ceci pour chacune des bornes en ville, soit 150 au total.
Une matrice de distances qui indique la distance d'une borne X à Y.

L'algorithme prend en paramètre : Une borne de départ, une d'arrivée et l'autonomie du véhicule électrique

1- Il calcule s'il est possible de se déplacer du point A à C directement sans s'arrêter pour recharger la batterie.
2- S'il n'est pas possible d'aller directement, il choisira un arrêt (point B) optimal ou autant d'arrêts optimaux qu'il faudra pour se rendre à destination.
3- Il affiche l'itinéraire du chemin à prendre le plus court et qui prends le moins de temps.

Le problème est que nous avons déjà un algorithme qui est efficace, mais pas optimal. Voici ce qu'il fait rapidement:

1- Il se rends compte qu'il faudra faire des arrêts pour se rendre à destination et nous donne un ensemble d'arrêts soit dits "optimaux".
Par exemple:
On part de la borne 5 pour se rendre à la borne 144; Il calcule que la borne la plus proche à 144 est la borne 33, la deuxième la plus proche est la 55 et ainsi de suite jusqu'à qu'il reconstitue un chemin qui nous mène à destination. Toutefois, bien que la borne 33 soit celle qui est la plus proche à 144 au debut, à la fin on se rends compte qu'un autre algorithme (qu'on n'a pas et qu'il faut chercher) prends une borne non optimale au debut, mais qui donne à la fin, un chemin plus court que s'il avait pris la borne 33.

Question: Connaissez vous un algorithme qui peut remplacer l'ancien algorithme que bien qu'il soit efficace, n'est pas tout à fait optimal.

Merci de votre collaboration et excusez-moi de la longueur du message. J'ai essayé d'être le plus concis possible.
Afficher la suite