Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
952 connectés 

  FORUM HardWare.fr
  Discussions
  Sciences

  Modèle mathématique pour rentabiliser la distance d'un trajet

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Modèle mathématique pour rentabiliser la distance d'un trajet

n°12061307
cocorezo
Baaaaaaaaaaahhhh
Posté le 09-07-2007 à 13:01:26  profilanswer
 

Je me pose une question depuis un bout de temps, mais n'étant pas du tout matheux, je suis bien incapable d'y répondre...
 
J'essaye de poser le problème clairement...
 
Prenons l'exemple d'un VRP qui doit visiter un nombre N de villes pour finalement revenir au point de départ. On suppose qu'il connait la distance entre chacune des villes. Son but est de parcourir le chemin le plus court. Etant donné que le nombre de possibilité est vite très important (au delà de 4 villes, ce n'est plus facilement intelligible), existe-t-il un modèle mathématique, une équation permettant de faire un choix logique sans avoir à passer toutes les possibilités en revue ?
 
Voilà, c'est une question qui me dépasse et pourtant je trouve ce problème intéressant. Si qqun pouvait éclairer ma lanterne :)

mood
Publicité
Posté le 09-07-2007 à 13:01:26  profilanswer
 

n°12061338
vicmckay
Posté le 09-07-2007 à 13:06:20  profilanswer
 

c'est le problème dit du "voyageur de commerce" ou du "sac à dos", expliqué sur le lien plus bas  :D  
 
lien plus bas

n°12061430
Profil sup​primé
Posté le 09-07-2007 à 13:22:26  answer
 

cocorezo a écrit :

Je me pose une question depuis un bout de temps, mais n'étant pas du tout matheux, je suis bien incapable d'y répondre...
 
J'essaye de poser le problème clairement...
 
Prenons l'exemple d'un VRP qui doit visiter un nombre N de villes pour finalement revenir au point de départ. On suppose qu'il connait la distance entre chacune des villes. Son but est de parcourir le chemin le plus court. Etant donné que le nombre de possibilité est vite très important (au delà de 4 villes, ce n'est plus facilement intelligible), existe-t-il un modèle mathématique, une équation permettant de faire un choix logique sans avoir à passer toutes les possibilités en revue ?
 
Voilà, c'est une question qui me dépasse et pourtant je trouve ce problème intéressant. Si qqun pouvait éclairer ma lanterne :)


Les seules méthodes viables sont algorithmiques.
 
Les méthodes de minimisation déterministes donnant à coup sûr le trajet le plus court ont une complexité beaucoup trop grande, il faut recourir à des méthodes heuristiques qui donnent une solution approchée.
 
Si mes souvenirs sont bons l'algo du recuit simulé (méthode générique souvent rencontrée pour les pbs d'optimisation comme celui-là) donne des résultats assez satisafaisants pour peu qu'on choisisse les bons paramètres. Tu peux aussi chercher du côté de la méthode dite de la "colonie de fourmis". Il existe aussi des algos génétiques pour résoudre de manière approchée ce pb mais je ne me suis jamais renseigné dessus. :o


Message édité par Profil supprimé le 09-07-2007 à 13:26:20
n°12064243
cocorezo
Baaaaaaaaaaahhhh
Posté le 09-07-2007 à 17:42:06  profilanswer
 

Merci pour votre aide.
 
Ce qui me frappe c'est qu'il n'y a aucune solution exacte à ce type d'énoncé. On peut arriver à faire des modèles approchants, mais le grand nombre de variables rend impossible toute équation exacte...
 
C'est marrant comme truc :)  
 
 


Le nombre de chemins possibles passant par 69 villes est déjà un nombre de 100 chiffres. Pour comparaison, un nombre de 80 chiffres permettrait déjà de représenter le nombre d'atomes dans tout l'univers connu !


Message édité par cocorezo le 09-07-2007 à 17:43:49
n°12071674
Profil sup​primé
Posté le 10-07-2007 à 12:36:20  answer
 

Oui a priori il y en a N! (enfin, (N-1)! si on fixe la ville de départ)


Message édité par Profil supprimé le 10-07-2007 à 12:38:07

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Discussions
  Sciences

  Modèle mathématique pour rentabiliser la distance d'un trajet

 

Sujets relatifs
[CONSEIL] déménagement longue distanceduree d'un trajet en voiture puteaux --> Bobigny
Accéder à distance à sa musiqueY a quoi comme modele de voiture électrique/hydrogène sur le marché ?
Trajet autour de MarseilleConcours Hfr : Mathématiques, votre avis.
Une 20 de chercheurs perce l'un des plus grands secrets mathématiquetrajet à Paris en voiture
Trajet Nice - Savoie 
Plus de sujets relatifs à : Modèle mathématique pour rentabiliser la distance d'un trajet


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR