Robust covering problems : formulations, algorithms and an application
Problème de couverture robuste : formulations, algorithmes et une application
Résumé
Two robust optimization NP-Hard problems are studied in this thesis: the min-max regret Weighted Set Covering Problem (min-max regret WSCP) and the min-max regret Maximal Coverage Location Problem (min-max regret MCLP). The min-max regret WSCP and min-max regret MCLP are, respectively, the robust optimization counterparts of the Set Covering Problem and of the Maximal Coverage Location Problem. The uncertain data in these problems is modeled by intervals and only the minimum and maximum values for each interval are known. However, while the min-max regret WSCP is mainly studied theoretically, the min-max regret MCLP has an application in disaster logistics which is also investigated in this thesis. Two other robust optimization criteria were derived for the MCLP: the max-max MCLP and the min-max MCLP. In terms of methods, mathematical formulations, exact algorithms and heuristics were developed and applied to both problems. Computational experiments showed that the exact algorithms efficiently solved 14 out of 75 instances generated to the min-max regret WSCP and all realistic instances created to the min-max regret MCLP. For the simulated instances that was not solved to optimally in both problems, the heuristics developed in this thesis found solutions, as good as, or better than the exact algorithms in almost all instances. Concerning the application in disaster logistics, the robust models found similar solutions for realistic scenarios of the earthquakes that hit Kathmandu, Nepal in 2015. This indicates that we have got a robust solution, according to all optimization models
Deux problèmes robustes d'optimisation NP-difficiles sont étudiés dans cette thèse: le problème min-max regret de couverture pondérée (min-max regret WSCP) et le problème min-max regret de couverture et localisation maximale (min-max regret MCLP). Les données incertaines dans ces problèmes sont modélisées par des intervalles et seules les valeurs minimales et maximales pour chaque intervalle sont connues. Le min-max regret WSCP a été investigué notamment dans le cadre théorique, alors que le min-max regret MCLP a des applications en logistique des catastrophes étudiées dans cette thèse. Deux autres critères d'optimisation robuste ont été dérivés pour le MCLP: le max-max MCLP et le min-max MCLP. En matière de méthodes, formulations mathématiques, algorithmes exacts et heuristiques ont été développés et appliqués aux deux problèmes. Des expérimentations computationnelles ont montré que les algorithmes exacts ont permis de résoudre efficacement 14 des 75 instances générées par le min-max regret WSCP et toutes les instances réalistes pour le min-max regret MCLP. Pour les cas simulés qui n'ont pas été résolus de manière optimale dans les deux problèmes, les heuristiques développées dans cette thèse ont trouvé des solutions aussi bien ou mieux que le meilleur algorithme exact dans presque tous les cas. En ce qui concerne l'application en logistique des catastrophes, les modèles robustes ont trouvé des solutions similaires pour les scénarios réalistes des tremblements de terre qui a eu lieu à Katmandu au Népal en 2015. Cela indique que nous avons une solution robuste
Origine : Version validée par le jury (STAR)