Discussion :

[Programmeur13]

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.

[dourouc05]

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.

[Programmeur13]

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.

[dourouc05]

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.)

[Programmeur13]

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

[dourouc05]

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/).