Optimisation combinatoire multi-objectif : état de l’art

À la fin du dix-neuvième siècle, l’économiste Vilfredo Pareto (1896) a défini l’optimum dit de Pareto comme un état de société où l’on ne peut améliorer le bien-être d’un individu sans détériorer celui d’un autre. Par la suite, cette définition a amené les notions mathématiques de dominance de Pareto et de front de Pareto utilisées dans l’optimisation multi-objectif. Depuis lors, cette branche de l’optimisation combinatoire est de plus en plus étudiée puisqu’elle reflète de véritables enjeux industriels. En effet, les problèmes réels sont souvent représentés par un unique objectif, même s’ils possèdent de nombreuses caractéristiques qui seraient mieux représentées par l’utilisation de plusieurs fonctions objectif. Cependant, la présence de multiples objectifs entraîne une complexité accrue par rapport aux modèles mono-objectif.

Notions de base

Principe

En optimisation combinatoire mono-objectif, le problème consiste à déterminer l’élément optimisant un critère parmi un ensemble fini ordonnable d’éléments. Cet élément est la solution optimale et la valeur de son critère est l’optimum. Dans le domaine multiobjectif, les problèmes visent à optimiser p objectifs simultanément et ils sont définis comme suit :

(MOP)  ; min c(x) = (c1(x), c2(x), .., cp(x)) t.q. x ∈ X

Dans cette formulation, les critères sont représentés par un vecteur de fonctions objectif c de taille p qui doit être optimisé. L’ensemble X ⊆ Nn , où n est le nombre de variables, représente l’espace des solutions. Les contraintes et l’espace de définition du problème sont implicitement données par la définition de X . Tout élément x de X est une solution du problème.

L’image de X par c forme l’espace des objectifs Y ⊆ Np . Tout élément y de Y est l’image d’une solution x ∈ X telle que yi = ci (x), ∀i ∈ [[1; p]] et est un point dans l’espace des objectifs. Pour alléger les notations, les coûts des objectifs d’un point y ∈ Y, associé à la solution x ∈ X , peuvent être représentés avec les notations yi, i ∈ [[1; p]] au lieu des coûts de la solution ci(x), i ∈ [[1; p]].

L’ensemble des solutions réalisables d’un problème multi-objectif combinatoire est un ensemble fini ayant pour image un ensemble, potentiellement non convexe, de points dans l’espace des objectifs. L’optimum est donc un ensemble de points qui peuvent être caractérisés de plusieurs manières.

Bornes supérieures et inférieures

Les méthodes d’optimisation mono-objectif reposent sur l’obtention de bornes inférieures et supérieures qui sont des valeurs encadrant le coût de la solution optimale. Dans le cadre de l’optimisation multi-objectif, les bornes ne correspondent pas aux solutions primales et duales, mais à un ensemble de points. Si nous considérons la minimisation du vecteur objectif, une borne inférieure est une relaxation de YN , tandis qu’une borne supérieure est un ensemble de points correspondant à des solutions réalisables et qui ne se dominent pas entre eux.

Dans un problème bi-objectif avec le vecteur objectif c = (c1, c2), le point idéal local yˆI de deux points non dominés consécutifs selon l’ordre naturel y et y0 est tel que yˆI = (y1 , y02). De même, le nadir local yˆN est tel que yˆN = (y01 , y2). Ces points donnent une précision sur la zone de l’espace des objectifs où se situent des points non dominés. Cependant, ils présentent certains inconvénients comme leur éloignement de l’ensemble des points non dominés, le calcul du point idéal qui revient à résoudre p problèmes potentiellement N P-difficiles et la difficulté de trouver le nadir lorsque p > 2 (Ehrgott et Tenfelde-Podehl (2003)), même sur un problème P-difficile (Kirlik et Sayın (2014)).

Villarreal et Karwan (1981) ont défini les bornes comme des ensembles de points encadrant YN . Les points de la borne inférieure doivent être des points non dominés ou qui dominent au moins un point de YN . De plus, chaque point de YN doit être dans la borne inférieure ou dominé par au moins un point de la borne inférieure. La borne supérieure, quant à elle, est un ensemble de points appartenant à YN ou dominé par au moins un point de YN . Les points de la borne supérieure ne doivent pas se dominer entre eux. Par la suite, cette définition a été généralisée par Ehrgott et Gandibleux (2001; 2007). Ils ont introduit la notion d’enveloppe convexe de la borne inférieure. Elle contient les points supportés obtenus par résolution de la relaxation linéaire de la formulation où les objectifs sont transformés en une somme pondérée avec des poids variables . L’enveloppe convexe de la borne inférieure est donc l’ensemble de ces points reliés entre eux par des segments. Par la suite, Sourd et Spanjaard (2008) ont défini la borne inférieure comme une fonction séparant l’espace des objectifs en deux parties de telle sorte que tous les points non dominés soient réunis. Dans la suite de ce manuscrit, nous utiliserons la définition de Sourd et Spanjaard (2008) comme borne inférieure.

Évaluation des fronts

Dans ce manuscrit, nous allons comparer les qualités des bornes inférieures de deux méthodes pour un problème de minimisation à deux objectifs. Cette partie présente la mesure utilisée bien que d’autres indicateurs existent dans la littérature (Zitzler et al. (2002)). L’hypervolume ou S-métrique a été défini par Zitzler et Thiele (1998) pour comparer la qualité des bornes supérieures. Ainsi, nous introduisons une différence puisque nous comparons la qualité de la borne inférieure comprenant des segments et non uniquement des points.

L’hypervolume est le pourcentage de la zone de l’espace des objectifs couverte par la borne inférieure, comparé à un point dominé par tous les points non dominés.  Dans cet exemple, le point yN est dominé par chaque point non dominé de YN et le point yI est le point idéal qui domine tous les points non dominés. Cela signifie que le front entier est contenu dans le rectangle formé par les points yI et yN . Les points y1, y2, y3 et y4 et les lignes entre chaque point successif représentent l’ensemble de la borne inférieure. L’hypervolume de cette borne est l’aire en gris divisée par l’aire du rectangle formé par les points yI et yN . Plus la mesure est faible et plus la borne inférieure est précise. Les points yI et yN doivent être les mêmes pour les méthodes comparées.

Méthodes exactes

Bien que la solution d’un problème multi-objectif soit un ensemble, une seule solution sera sélectionnée en pratique par un décideur. Les méthodes peuvent être classifiées selon la phase durant laquelle le décideur intervient :
— Préférence a priori où le décideur intervient seulement au début de la résolution pour définir ses préférences entre les objectifs. Ces préférences peuvent être définies indépendamment pour chaque objectif comme l’agrégation des objectifs en une somme pondérée, ou être interactives selon l’ordre des critères (Fouchal et al. (2011)). L’avantage de ces approches est qu’un unique problème mono-objectif est résolu, bien que définir ses attentes en amont de la résolution peut être difficile pour le décideur.
— Préférence interactive où le décideur définit ses préférences parmi les objectifs au début de la résolution et intervient également durant le processus de résolution pour la guider. Comme les approches a priori, une unique solution est retournée, mais qui est plus fidèle aux attentes du décideur. L’inconvénient majeur de cette approche est le besoin d’intervention du décideur au cours de la résolution qui peut être longue.
— Préférence a posteriori où le décideur n’intervient qu’en fin de résolution pour choisir la solution à garder dans l’ensemble proposé. Le décideur connaît alors les différents compromis possibles entre les objectifs avant de prendre une décision. Cependant, cette approche requiert plus de temps de calcul puisque de nombreuses solutions sont obtenues.

Table des matières

Introduction
1 Optimisation combinatoire multi-objectif : état de l’art
1.1 Introduction
1.2 Notions de base
1.2.1 Principe
1.2.2 Caractérisation des solutions
1.2.3 Bornes supérieures et inférieures
1.2.4 Évaluation des fronts
1.3 Méthodes exactes
1.3.1 Méthode basée la somme pondérée des objectifs
1.3.2 Méthode ε-contrainte
1.3.3 Méthode ε-contrainte avec changement de l’ordre d’exploration
1.3.4 Méthode de séparations et évaluations
1.3.5 Méthode basée sur la programmation dynamique
1.3.6 Conclusion
1.4 Conclusion du chapitre
2 Problèmes de tournées de véhicules : état de l’art
2.1 Introduction
2.2 Formulations mathématiques
2.2.1 Formulation de flux de véhicules à deux indices
2.2.2 Formulation de flux de marchandises à deux indices
2.2.3 Formulation de partitionnement
2.3 Génération de colonnes
2.3.1 Principe
2.3.2 Problème de plus court chemin élémentaire avec contraintes de ressources
2.3.3 Techniques de stabilisation
2.4 Méthodes exactes
2.4.1 Méthode de séparations et évaluations
2.4.2 Méthode de séparations et coupes
2.4.3 Méthode de séparations et génération de colonnes
2.4.4 Méthode de séparations et coupes et génération de colonnes
2.4.5 Énumération explicite des colonnes
2.5 Problèmes de tournées de véhicules multi-objectif
2.5.1 Réduction de la pollution
2.5.2 Équité entre les véhicules
2.5.3 Satisfaction des usagers
2.5.4 Réduction du risque
2.5.5 Collecte d’un profit
2.5.6 Conclusion
2.6 Conclusion du chapitre
3 Méthodes exactes pour les problèmes de tournées de véhicules bi-objectif
3.1 Introduction
3.2 Formulations mathématiques
3.2.1 Formulation bi-objectif
3.2.2 Formulation pour la méthode ε-contrainte
3.2.3 Formulation de la somme pondérée des objectifs
3.2.4 Conclusion
3.3 Résolution des problèmes mono-objectif avec la génération de colonnes
3.3.1 Étape 1 : Solution optimale de la relaxation linéaire
3.3.2 Étape 2 : Solution réalisable du problème entier
3.3.3 Étape 3 : Énumération de colonnes
3.3.4 Étape 4 : Solution optimale du problème entier
3.3.5 Conclusion
3.4 Méthodes pour le problème bi-objectif
3.4.1 Calcul des points extrêmes
3.4.2 Méthode 1 : basée sur l’approche ε-contrainte avec génération de toutes les colonnes
3.4.3 Méthode 2 : basée sur l’approche ε-contrainte par étapes
3.4.4 Méthode 3 : deux phases avec génération de toutes les colonnes pour les points supportés
3.4.5 Méthode 4 : deux phases par étapes
3.4.6 Conclusion
3.5 Résultats expérimentaux
3.5.1 Description des instances
3.5.2 Comparaison des méthodes
3.5.3 Conclusion
3.6 Conclusion du chapitre
4 Étude de la méthode ε-contrainte
Conclusion

Lire le rapport complet