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

Algorithmes et structures de données Discussion :

Variante du problème du sac à dos


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    47
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 47
    Points : 12
    Points
    12
    Par défaut Variante du problème du sac à dos
    Bonjour,
    je viens vers vous pour vous demander de l'aide concernant un projet. Je voudrais réaliser une variante du Knapsack Problem modélisant une priorisation de conteneurs maritimes (les objets) pour remplir un porte-conteneur (le sac). Le chargement total ne doit pas dépasser une certaine masse et il doit y avoir une limite sur le nombre d'objets retenus. On cherche à maximiser la valeur totale du chargement. Pour l'instant, il s'agit d'un problème assez classique dont j'ai pu trouvé et implémenté plusieurs solutions qui fonctionnent. Je souhaiterai toutefois rajouter un paramètre contraignant fortement mon problème et dont je trouve pas de documentation. Chaque objet a maintenant une destination, qui n'est pas a priori la destination finale du porte-conteneur, et le porte-conteneur effectue plusieurs escales où il peut charger/décharger des conteneurs tant qu'ils satisfassent les limites imposées. Le but est maintenant d'optimiser sur le trajet total la valeur du chargement. Je voudrais savoir si vous avez des idées de résolution ainsi que des ressources vers lesquelles me diriger. Savez-vous s'il s'agît d'un problème portant un nom spécifique ?
    Merci beaucoup d'avance.

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 928
    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 928
    Points : 170 586
    Points
    170 586
    Par défaut


    Ton problème commence à ressembler à un VRP (vehicle routing problem), bien plus compliqué que le sac à dos. C'est un mélange entre le sac à dos et le voyageur de commerce.
    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
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    47
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 47
    Points : 12
    Points
    12
    Par défaut
    Bonsoir,
    Merci pour ta réponse. J'ai bien conscience que mon problème s'éloigne du sac à dos mais j'ai du mal à voir quelle stratégie utiliser. La programmation dynamique, l'algorithme génétique ou glouton reste-t-ils possibles ? Le voyageur du commerce recherche un plus court chemin alors que cet aspect n'est pas pris en compte dans mon problème. Par quelle caractéristique tu trouves qu'il s'y rapproche ?
    J'avoue être un peu perdu avec ce nouveau paramètre, peut-être un peu trop dur à prendre en compte ?
    Merci beaucoup pour votre aide.

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 928
    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 928
    Points : 170 586
    Points
    170 586
    Par défaut
    Tu fais face à un problème vraiment plus compliqué que le sac à dos, mets-toi bien ça en tête. La programmation dynamique ne marchera pas, tu n'as pas la propriété de sous-structure optimale. Tu peux toujours implémenter des heuristiques gloutones ou des métaheuristiques genre programmation dynamique, vol d'abeilles, reproduction d'oursins en Alaska ou autre. As-tu besoin d'une solution optimale ou tu seras déjà heureux avec une solution réalisable ?

    (Sinon, le voyageur de commerce n'a aucun rapport avec un plus court chemin entre deux points : tu dois choisir le plus court chemin qui passe par toutes les villes ou, dans ton cas, tous les ports où tu dois déposer des objets.)
    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
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    47
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 47
    Points : 12
    Points
    12
    Par défaut
    L'idée était de comparer plusieurs algorithmes donnant des solutions approchées de la solution optimale. J'ai cependant sûrement sous-estimé la difficulté de cette variante. Je peux et je vais sûrement revenir sur ma version précédente. Toutefois, je la trouve un peu simpliste par rapport à la réalité et c'est pour cela que j'avais pensé à ce paramètre. T'aurais pas une idée pour rajouter une contrainte sans trop complexifié le problème ?
    Merci beaucoup

  6. #6
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 928
    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 928
    Points : 170 586
    Points
    170 586
    Par défaut
    Tout dépend du niveau visé . Si tu veux une contrainte pas trop complexe mais qui donne vite lieu à des problèmes importants, tu peux considérer des sacs à dos multidimensionnels. C'est un problème vraiment utile en pratique, par exemple pour remplir des serveurs de machines virtuelles (chaque serveur a du CPU et de la RAM, chaque VM a des besoins différents en CPU et en RAM). Si tu veux complexifier encore un peu, amuse-toi avec des contraintes plus particulières (http://www.roadef.org/challenge/2012...inition_v1.pdf est une belle source, avec énormément de données de test : http://www.roadef.org/challenge/2012/en/).
    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 !

Discussions similaires

  1. Réponses: 2
    Dernier message: 25/02/2010, 00h08
  2. Compréhension d'un algorithme sur le problème du sac à dos
    Par Treuze dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 18/12/2006, 16h26

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