Documents de travail
Année
2005
Abstract
Nous étudions une variante du problème classique de localisation optimale d’entreprises avec capacités de livraison ou de production limitées, dans laquelle chaque centre de production se décompose en un nombre variable d’unités de production. Cette variante, NP-difficile également, a été récemment étudiée dans plusieurs articles, principalement dans le cas métrique. Dans ce document, nous traitons le problème général où les coûts de connexion des clients aux centres de livraison ne vérifient pas obligatoirement l’inégalité triangulaire. Nous proposons pour ce problème une heuristique adaptée de la méthode gloutonne pour le problème de Couverture d’Ensemble, où le sous-problème est traité par un schéma d’approximation utilisant une normalisation des coûts et la programmation dynamique. Nous montrons que cette heuristique permet d’approcher en temps polynomial le problème à rapport (1+ )H(n), où n est le nombre de clients devant être livrés et H est la série harmonique. Ce rapport améliore le précédent ratio de 2H(n) pour ce problème.
ALFANDARI, L. (2005). Improved Approximation of the General Soft-Capacitated Facility Location Problem. ESSEC Business School.
