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

Azeddine Cheref (1) , Christian Artigues (1) , Emmanuel Hébrard (1) , Pierre Lopez (1) , Vincent Charvillat (2, 3) , Yves Régent , Sandra Ulrich Ngueveu (3, 1)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 IRIT-REVA - Real Expression Artificial Life
3 Toulouse INP - Institut National Polytechnique (Toulouse)

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

Mots clés: Problème de localisation; Arrondi en programmation linéaire.; Approximation

Domaines: Optimisation et contrôle [math.OC]; Informatique et théorie des jeux [cs.GT]; Complexité [cs.CC]; Recherche opérationnelle [math.OC]

Azeddine Cheref, Christian Artigues, Emmanuel Hébrard, Pierre Lopez, Vincent Charvillat, et al.. Algorithme d’approximation pour un problème d’affectation d’une commande multiproduit multifournisseur. 12ème Conférence Internationale de MOdélisation, Optimisation et SIMulation (MOSIM 2018), Jun 2018, Toulouse, France. 7p. ⟨hal-01880425⟩