tournée de véhicules

[kaderben]

Bonjour
En naviguant sur internet, j'ai vu que le problème de l'optimisation de tournée de véhicules est l'un des problèmes NP-difficiles. Mais ils expliquent les algorithmes d'une façon savante et je ne comprends pas; ils ne donnent pas un exemple concrêt c'est à dire un exemple à faire à la main.
Y'a t-il quelqu'un qui peut m'expliquer comment on fait à la main pour optimiser les distances et le nombre de véhicules sur un exemple de ce genre:

A,B,C,D,E,F,G,...sont les centres à livrer, chaque centre tant de palettes, le nombre de camions entre 4 et 8 par exemple, capacité d'un camion de tant de palettes, distances entre centres connues; je vous laisse le choix des données
( si ce n'est pas clair je peux fournir des données)
Merci pour votre aide.
-----

[apzo11]

Bonjour,
Cela me fait penser à des problèmes de "recherche opérationnelle".
ce sont des méthodes pour optimiser des tournées, pour dimensioner des tuyaux (débit fluides ou électrique...).
apzo11

[JPL]

Par définition un problème NP est inextricable si on cherche un algorithme exact (enfin dès qu'on dépasse un tout petit nombre de centres de livraisons, ce qu'on pourrait résoudre avec un papier et un crayon). Par contre il peut exister des approches empiriques qui donnent des résultats pas trop mauvais dans la plupart des cas. Fais une recherche Google sur problème du voyageur de commerce.

[Jack]

Ca me rappelle mes projet d'info. J'étais tombé sur le voyageur de commerce et à l'époque, pas d'internet pour trouver des algo tout faits.

Comme le problème se complique très rapidement en fonction du nombre d'étapes et que la force brute ne suffira pas, il faut plutôt se diriger vers des euristiques qui ne donneront pas forcément la solution optimale mais des solutions viables dans un temps raisonnable, ce que vient précisément d'évoquer JPL.

A+

[A voir en vidéo sur Futura]

[kaderben]

Je vous remercie tous pour les réponses. J'ai déjà navigué sur internet, je sais que le problème du voyageur de commerce, le problème du sac à dos etc... sont difficiles; ce que je voulais exactement, c'est un exemple pour voir commment on fait à la main à titre pédagogique,pour optimiser une tournée de véhicules sur quelques centres. Les explications qu'ils donnent sur internet c'est vraiment pour les étudiants qui préparent des thèses d'ingénieur et de docteur; personnellement je ne suis pas étudiant, je n'ai pas de projet à préparer, je n'ai pas d'examen à passer, je suis autodidacte et je m'interesse à ce problème.
Merci

[JPL]

Je comprends mais justement tu t'intéresses à un des problèmes les plus difficiles qui existent dans le domaine des algorithmes. Ne sois donc pas étonné que les approches, bien qu'empiriques, soient particulièrement complexes.

[kaderben]

JPL, peut être je ne me suis pas bien fait comprendre. Comment font les professeurs pour expliquer ce genre d'algorithme à leurs élèves ? Je pense qu'ils doivent prendre un petit exemple avec quelques centres, quelques véhicules et ils le font à la main comme qu'on fait pour l'algorithme de Dijkstra (chemin le plus court entre 2 points)en terminale ES.
C'est ce que je pense réellement à moins que je me trompe
Merci.

[apzo11]

http://www.iecn.u-nancy.fr/.../Reche...e/polyRo-I.pdf

Connais-tu ce pdf
J'ai eu des cours il ya quelques années:
Discipline difficile à apprendre tout seul
Bravo et bon courage
apzo11