Bonjour !

J'aimerais développer un outil pour optimiser l'achat de pièces détachées de Lego. En entrée, je devrais avoir la liste et les quantités de pièces à acheter, ainsi que la liste des vendeurs avec les prix de vente, quantités disponibles, poids des pièces et frais de port (variant selon le poids et le pays d'expédition). Le but étant d'avoir en sortie les "paniers" par vendeur, avec le coût global le plus faible possible.

Est-ce que vous avez une idée du type d'algorithme employable ?

Merci d'avance  

Edit : si le problème est trop complexe ainsi, il serait possible de considérer un montant de frais de port forfaitaire.

Tu peux regarder du côté de la RO (recherche opérationnelle) avec l'algo du Simplex.
Après, ça va dépendre de la taille des données en entrées. En effet, avec une vingtaine de types de pièces et 3-4 vendeurs, le nb de combinaisons va très vite augmenter.
Du coup, un algo génétique pourrait être une bonne solution
 
Ton pb de rapproche d'un que j'ai traité il y a qq années : j'ai une liste de fichiers à graver sur un nb de CDs, le but étant de perdre le moins de place sur les CDs mais je ne suis pas obliger de prendre tous les fichiers. Les fichiers, ce sont tes pièces, les CDs, ce sont tes vendeurs. La taille des fichiers ce sont les prix des vendeurs (ça varie donc).
 
http://forum.hardware.fr/hfr/Windo [...] 3648_1.htm
http://chrisjav.olympe.in/projects_optcd.php

J'avais pensé au simplexe (cette nuit à 3h du mat' ), mais je peux avoir plusieurs centaines d'articles, idem pour les vendeurs Donc effectivement je me demandais si un algo génétique ou type colonie de fourmis pouvait faire l'affaire
 
Mais entre temps j'ai vu une autre approche : définir combien on veut de fournisseurs au maximum (les fdp représentent facilement 25% des commandes optimisées, donc il faut minimiser le nombre de fournisseur) et procéder par combinaisons à partir des quelques magasins qui disposent des articles les plus rares, et enfin finir d'optimiser (ce qui la peut se faire avec un simplexe) à partir des combinaisons réalisables.

Tu peux aussi la tenter avec un algo de big data style MapReduce. Ce genre de calcul est tout à faire parallélisable sur un outil tel que Hadoop
Tu fais calculer des paquets de vecteurs "solution" et pour chaque paquet, tu gardes la meilleure solution. Tu te retrouves donc avec un ensemble de vecteurs "bonne solution". Tu réitères le processus : après qq itérations, tu devrais converger vers une bonne solution voire la meilleure. C'est un peu un mix entre algo génétique et big data...