Algorithme d’approximation pour un problème d’affectation d’une commande multiproduit multifournisseur

International audienceDans le contexte de la vente en ligne, étant donné une commande constituée d'un ensemble de produits et un ensemble de magasins, leprobì eme que nous présentons dans ce papier consistè a répartir la commande sur un ensemble de magasins de sortè a minimiser le coût de la commande. Ceprobì eme se retrouve dans plusieurs contextes et comporte beaucoup de similitudes avec leprobì eme de localisation d'entrepôts. Nous traitons dans ce papier deux cas particuliers et pour chacun d'eux un algorithme de résolution est proposé. Dans le premier cas, nous considérons que les produits sont disponibles dans les magasins en quantité illimitée. Dans ledeuxì eme cas, les quantités sont considérées limitées. Leprobì emé etant une généralisation du probì eme couverture par ensembles, il est par conséquent NP-difficile. Ainsi, une heuristique avec garantie de performance basée sur l'approche d'arrondi en programmation linéaire est proposée pour chacun des cas traités