Program > By author > Haddar Boukthir

Dans cet article nous nous intéressons à la résolution du problème de la distribution équitable qui est une extension du problème du sac-à-dos (SAD) dans laquelle un ensemble d'objets est soumis à une contrainte de ressource, comme dans le SAD. Cependant, les objets sont regroupés en différentes classes, et une fonction objective est associée à chaque classe. L'objectif du problème est de choisir un sous-ensemble d'objets permettant de maximiser la valeur minimale des coûts associés aux classes, en respectant la contrainte de capacité du sac. Ce problème NP-Difficile a été introduit par Brown en 1979 et a surtout été traité par des méthodes exactes dans la littérature (programmation dynamique, séparation et évaluation, etc). Nous proposons une méthode hybride, qui converge théoriquement vers une solution optimale du problème, en générant deux séquences de bornes supérieures et inférieures sur la valeur optimale, et en réduisant itérativement l'espace de recherche. Nous introduisons différents composants visant à accélérer la convergence de notre approche vers des solutions (presque) optimales en un temps de calcul restreint : recherche locale, contraintes additionnelles dans la formulation du problème, et nous développons une métaheuristique basée sur l'optimisation par essaim de particules. Notre méthode est évaluée sur un ensemble d'instances disponibles du problème. Les résultats montrent que notre approche permet d'obtenir un bon compromis entre la qualité de la solution finale et le temps nécessaire pour l'obtenir. En particulier, la version la plus efficace visite 63% des solutions optimales en moins de 30 secondes. Nous validons ensuite notre approche sur un ensemble de nouvelles instances plus difficiles à résoudre pour les méthodes exactes actuelles les plus performantes. Notre algorithme visite 53% des solutions optimales de ces instances en moins de 3 minutes, le logiciel CPLEX n'étant pas capable de toutes les résoudre en 1 heure.