Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Discussion :

Comment appliquer le problème du voyageur de commerce ?


Sujet :

Mathématiques

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2016
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2016
    Messages : 5
    Points : 3
    Points
    3
    Par défaut 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

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 684
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 684
    Points : 166 226
    Points
    166 226
    Par défaut


    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).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2016
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2016
    Messages : 5
    Points : 3
    Points
    3
    Par défaut
    Salut

    Citation Envoyé par dourouc05 Voir le message
    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..
    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


    Merci

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 684
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 684
    Points : 166 226
    Points
    166 226
    Par défaut
    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.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Rédacteur

    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    août 2013
    Messages
    366
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Administrateur de base de données
    Secteur : Finance

    Informations forums :
    Inscription : août 2013
    Messages : 366
    Points : 1 778
    Points
    1 778
    Par défaut
    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.
    N'hésitez pas à consulter mon mémento sur la programmation en VBA pour EXCEL tome 1.
    Ou le tome 2 qui aborde la programmation en mode graphique avec un exemple de programmation d'un jeu d'arcade en VBA
    Et pour les curieux, le tome 3 qui aborde le problème du voyageur de commerce.
    Le tome 4 est consacré à la cryptologie en VBA et satisfera ceux qui ont besoin de confidentialité.
    Vous découvrirez dans le tome 5 les fonctions SQL pour gérer les tableaux de données et l'application Sentinelle qui veille sur vos fichiers.
    Le tome 6, dernier de la série, vous apprendra à créer des fonctions pour simplifier la vie des utilisateurs.
    Le Crible Quadratique donne toutes les fonctions pour les opérations sur les grands nombres en VBA.
    N'oubliez pas de consulter les FAQ EXCEL et les cours et tutoriels comme par exemple celui de Jean-Marc RABILLOUD qui est très complet.

  6. #6
    Membre actif

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : mai 2013
    Messages : 22
    Points : 261
    Points
    261
    Par défaut Objectif
    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.
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

Discussions similaires

  1. Réponses: 4
    Dernier message: 03/02/2014, 09h55
  2. Problème du voyageur de commerce
    Par bleach1234 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 04/05/2009, 14h57
  3. Réponses: 2
    Dernier message: 03/02/2009, 20h21
  4. Problème du voyageur du commerce avec plusieurs voyageurs
    Par Treuze dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 21/12/2007, 11h46
  5. Réponses: 3
    Dernier message: 12/04/2007, 09h32

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo