Comment appliquer le problème du voyageur de commerce ?

Bonjour à vous,
Je suis actuellement étudiant, je vous passe le détails mais j'ai étudié entre autres la recherche opérationnelle, l'optimisation logistique et l’ordonnancement.
Ça fait en tout beaucoup de théorie plus ou moins mathématique et plus ou moins applicable.

Aujourd'hui je m’intéresse à développer des compétences informatique un peu plus sérieuses pour mettre en application les outils que j'ai pu étudier. j'ai un projet en tête, qui me permettrait d'utiliser certaines de mes connaissances et surtout de comprendre comment les utiliser à l'aide d'outils informatique.
Mon but est d'être capable de mettre en place tout ce qui se trouve autour du 'cœur' théorique de mon projet, comment traiter les données etc.

Simplement, après avoir vu en quoi consiste mon projet, j'aimerais, que vous me disiez quels sont les outils dont j'aurai besoin et quelles seront mes option pour mettre en place chaque aspect de mon projet et de le faire aboutir.

Le projet (très simple):

- Imaginez une entreprise familiale de livraison. Disons que cette entreprise est spécialisée dans le livraison de matériel médical, elle livre les professionnels du domaines de la santé au niveau local.
1- Chaque jour l'entreprise reçoit des appels de clients, pour des commandes. La personne qui prend la commande renseigne les détails sur une fiche excel
(formulaire) puis la valide.
2- Les informations de toutes les fiches excel (lieu, jour de livraison) sont ensuite regroupées et traitées de façon à établir un itinéraire journalier optimisé pour chaque
véhicule de livraison.
3- la personne en bout de chaîne reçoit ensuite, selon son identité, son itinéraire pour la journée ou pour les jours sur lesquels l'itinéraire de livraison a été fixé (disons
3 jours).


La description est assez vague, je ne veux pas trop contraindre la chose et j'attends surtout de lire vos idées.
Voici ma vision des choses et les question que je me pose (pour vous donner une idée de ce que j'attends):

1- Une fois le document 'formulaire' validé, une copie est crée, portant le nom de la commande, et est envoyée vers un répertoire commun ou sont stockées toutes les
commandes. ==>Excel VBA requis, niveau basique?

- Grace à l'adresse renseignée sur la fiche excel, comment créer une cartographie de tous les points à livrer pour un jour donné (utiliser google map avec python? on
veut les coordonnées x,y de chaque point en sortie)

2- Lire tous les documents excel depuis un autre logiciel afin de résoudre le problème typique mTSP (problème de voyageur de commerce). Faisable avec python
(librairie docplex), Cplex IBM, Xpress et autre logiciel.
- ici on utilise les coordonnées de chaque point à livrer, le volume de chaque commande et le jour ou elles doivent être livrées comme entrée de notre algorithme
(simplifié).


3- On prend le résultat de l'algorithme (disons que le résultat correspond à 1 itinéraire pour chaque véhicule, à une date donnée, sous forme d'une liste de
coordonnées) et on le transforme de façon à avoir un feuille de route d'un véhicule pour jour donné.
On doit ensuite envoyé chaque feuille à la personne concernée. Fiche excel+Excel VBA?Comment commander l'envoi



Je suis ouvert à tous vos conseils et suggestions, et si il existe une sorte de 'base' qui regroupe ce genre de projet assez basique et très utile, je suis preneur.

infos supplémentaires (pas utile):
- Toutes les commandes sont livrées par un même type de véhicule, avec une capacité donnée. Le volume de chaque commande est renseigné et la commande est expédiée en une fois.

J'attends vos réponses avec impatience, merci.

Kada

:salut:

Après avoir lu ton message, je ne suis pas sûr de bien saisir ta question. Tu souhaites que l'on t'aide sur la partie recherche opérationnelle (plus proche de la théorie) ou vraiment sur le développement de ton application ?

Dans le premier cas : tu n'as pas vraiment un problème de voyageur de commerce (je suppose que c'est que tu indiques avec mTSP ?). Je ne connais pas vraiment cette variante, je ne sais pas à quel point il faudra chipoter pour arriver à résoudre tes instances suffisamment rapidement…

Dans le second cas : mieux vaut avoir une solution intégrée, un seul programme qui fait tout (avis personnel), au moins toute la partie calcul et importation-exportation de données (la visualisation et l'interaction avec l'utilisateur, pas forcément). Dans ce cas, tu as un seul langage du début à la fin, tu peux facilement passer des informations d'un bout à l'autre de ton programme.
Si tu veux impérativement utiliser Excel, tu peux l'interfacer en COM (c'est ce qui est fait dans https://stackoverflow.com/a/1860269/1066843, par exemple) — Python donne accès aux bibliothèques COM, avec un peu de colle : https://pbpython.com/windows-com.html — ; sinon, tu peux aussi imaginer que l'utilisateur entre toutes les informations dans un site Web, informations que tu peux stocker/exporter comme tu préfères (des fichiers CSV, c'est parfait à petite échelle).
Ensuite, pour résoudre ton problème d'optimisation, tu peux y aller avec Python (docplex, mais tu te limites à CPLEX ; Pyomo, c'est pas trop mal), Julia (JuMP)… ou alors tu restes dans Excel (https://solverstudio.org/languages/ampl/, https://www.ibm.com/support/knowledg..._manual_1.html) ou juste côté CPLEX (qui peut accéder à des fichiers Excel en OPL, apparemment : https://www.ibm.com/support/knowledg...heetWrite.html).

Salut:D

Citation:

---

Envoyé par dourouc05

Après avoir lu ton message, je ne suis pas sûr de bien saisir ta question. Tu souhaites que l'on t'aide sur la partie recherche opérationnelle (plus proche de la théorie) ou vraiment sur le développement de ton application ?

Dans le premier cas : tu n'as pas vraiment un problème de voyageur de commerce (je suppose que c'est que tu indiques avec mTSP ?). Je ne connais pas vraiment cette variante, je ne sais pas à quel point il faudra chipoter pour arriver à résoudre tes instances suffisamment rapidement…

---

L'approche est peut-être différente sur un projet de ce type, ce n'est peut-être pas réellement un problème de TS effectivement.

Ce qui m’intéresse n'est pas la théorie mais plutôt tout ce qu'il y a autour, et je pense que ta réponse répond parfaitement à ma question!
Pour l'instant j'ai des bases en Python et en VBA, mais je suis prêt à investir du temps et apprendre quelque chose de nouveau, à condition que ça me soit utile pour d'autres choses..

Citation:

---

mieux vaut avoir une solution intégrée, un seul programme qui fait tout (avis personnel), au moins toute la partie calcul et importation-exportation de données (la visualisation et l'interaction avec l'utilisateur, pas forcément)

---

A quelle langage pense-tu?

Le truc étant qu'on résout des problèmes d'optimisation à l'école avec Python ou autre mais sans vraiment en voir plus. C'est un peu comme avoir un bon balai mais pas de manche (j'ai pas mieux comme analogie désolé).

Je suis curieux de savoir comment c'est mis en place dans un cas réel. Tu pense que je peux trouver une genre de site qui regroupe des projets entiers de ce type?
Encore une fois je n'en suis qu'au début de la démarche et reste ouvert aux suggestions
:mrgreen:

Merci

Tout dépend ce que tu souhaites faire… Si tu souhaites implémenter des algos "poussés" (génération de colonnes, de contraintes, utilisation d'heuristiques pendant le processus de résolution et j'en passe), Python, Julia ou C++ sont d'assez bons choix (personnellement, je suis très orienté Julia) ; si la partie algorithmique est moins avancée, mais que tu souhaites plus t'intégrer à de "gros" systèmes informatiques, Java est plus ou moins le meilleur choix (les solveurs sont entièrement accessibles en Java, énormément de code de systèmes de gestion est en Java).

Sinon, "en pratique", de ce que j'ai pu voir dans plusieurs sociétés, tu as une vraie séparation entre ceux qui font la partie algorithmique et ceux qui font la partie interfaçage avec l'utilisateur : d'un côté, les gens qui ne font que des maths et un peu de codage (ta formation, j'ai l'impression) ; de l'autre, des gens qui ont peut dès qu'ils voient un symbole mathématique ésotérique, mais passent leur journée à coder.

Bonjour.
Je trouve que ce qui est dommage dans le projet de "Muchacho_masqué" est qu'il confie la partie la plus intéressante, à savoir la résolution du problème du voyageur de commerce (pour les tournées des chauffeurs de son entreprise familiale), à un langage de programmation qui va lui donner la solution sur un plateau.
Dommage car une solution approximative pour organiser une tournée peut être trouvée facilement et est programmable tout aussi facilement.
Ce serait, à mon avis, un excellent exercice pour apprendre un langage de programmation.

Pour information j'ai rédigé une documentation sur ce sujet, avec un code source en VBA : http://laurent-ott.developpez.com/tu...el-vba-tome-3/
On voit ici que la technique de "l'insertion de moindre coût" (puis 2-opt pour supprimer les croisements) est très facile à programmer, donne un résultat très rapide, et est finalement assez efficace.
On peut, à mon avis, se contenter de ce niveau d'approximation pour une livraison de chauffeurs qui seront de toute façon coincés dans les embouteillages.

Quant au langage de programmation à utiliser, je pense que Python a plus la côte que VBA.
Ou dans l'idéal Java ou le C.

Bonne continuation.

Bonjour,

Je passe sur l'application de gestion qui, à mon avis, n'est pas du ressort de ce forum.

Le problème de distribution me paraît très limité (planification à trois jours avec des camionnettes). Une solution exhaustive sous contrainte est donc vraisemblablement possible. Mais est-ce vraiment intéressant ?

S'il y a beaucoup de points de livraison en 3 jours cela implique des déplacements essentiellement urbains dans une ville importante et ses alentours. Dans ce cas, l'incertitude de la qualité de circulation l'emporte sur un parcours optimisé.

S'il n'y en a pas beaucoup (par exemple, de l'ordre d'une dizaine de livraisons par véhicule sur 3 jours). il n'est vraisemblablement pas utile de sortir des algorithmes sophistiqués et lourds pour gagner quelques mètre ou minutes.

Mais peut être que la résolution du problème n'est pas l'objectif premier et que ce n'est que l'opportunité de tester des concepts et d'apprendre un langage. Ça me parait faire beaucoup d’œufs dans un même panier.

Je ne cherche pas à dissuader mais inciter à pondérer les objectifs, c'est à dire à faire un cahier des charges.

Bon courage.