Localisation Optimale de Hubs et Taille Optimale d’une Flotte

QUELQUES NOTIONS GÉNÉRALES D’OPTIMISATION, DE HUB ET DE FLOTTE

 Introduction 

Dans ce chapitre, nous rappelons quelques notions générales d’optimisation utilisées dans cette thèse. Il s’agit plus précisément des notions de programmation linéaire et programmation linéaire en nombres entiers, de quelques éléments de la théorie des graphes et des problèmes de localisation. Le concept de Hub, de la flotte et de sa taille y sont aussi développés. 

Optimisation

 Le monde des industries, des entreprises est souvent confronté à des problèmes de décision. Une partie importante de ces problèmes que rencontrent les dirigeants dans la pratique sont sans aucun doute les problèmes d’optimisation linéaire ou programme linéaire. Avec la puissante avancée de la technologie informatique, on utilise des logiciels pour résoudre ces problèmes sans connaître la théorie qui se cache derrière. Les logiciels d’optimisation sont nombreux. On peut citer le cplex, Matlab, Lindo, Excel, Maple etc. Ces logiciels résolvent différents types de problèmes d’optimisation parmi lesquels ceux que nous traitons dans le cadre de la programmation linéaire  en nombres entiers(PLNE). Cette section a pour objet de présenter quelques notions utiles pour comprendre le mystère qui se trouve derrière ces logiciels. Il commence par une présentation de l’optimisation d’une manière générale. Nous introduisons ensuite la notion de programmation Linéaire (PL) car le Programme linéaire en nombres entiers n’est rien d’autre que le programme linéaire auquel on a ajouté des contraintes d’intégrité puis celle de programmation linéaire en nombres entiers(PLNE) proprement dite. Quelques notions de la théorie de graphe y sont présentées car pour la localisation d’un hub, on considère un graphe G = (N, A) où N représente l’ensemble des aéroports et A l’ensemble de lignes aériennes reliant les différents aéroports. Nous finissons cette section par une revue de littérature sur la localisation. Pour plus de détails sur ces notions, le lecteur peut consulter les ouvrages de références.

 Généralités sur l’optimisation 

Selon la nature du domaine réalisable, l’optimisation est continue ou discrète (optimisation combinatoire). La localisation d’un hub étant un problème combinatoire, dans cette thèse, nous approfondissons plus l’optimisation combinatoire. le problème général d’optimisation combinatoire Un problème d’optimisation combinatoire consiste à trouver la meilleure solution dans un ensemble discret, qu’on appelle ensemble de solutions réalisables. En général cet ensemble est fini mais compte un grand nombre d’éléments, d’où l’utilisation du terme « combinatoire ». La notion de meilleure solution est définie au sens d’une fonction, qu’on appelle fonction objectif (ou fonction coût). Mathématiquement cela peut se formuler de la façon suivante : On se donne : – une fonction J : R n → R appelée fonction-objectif ; – un ensemble U ⊂ R n appelé ensemble des contraintes. 

 OPTIMISATION 

 Le problème d’optimisation consiste à déterminer, lorsqu’il existe, un minimum ou un maximum de J sur U. Un problème d’optimisation peut se formuler comme suit : Minimisation Minimiser J sur U revient à chercher x ∗ ∈ U tel que J(x ∗ ) = min x∈U J(x) Ceci équivaut à : J(x ∗ ) ≤ J(x), ∀x ∈ U. x ∗ est la solution optimale du problème. Maximisation Maximiser J sur U revient à chercher x ∗ ∈ U tel que J(x ∗ ) = max x∈U J(x) Ceci équivaut à : J(x ∗ ) ≥ J(x), ∀x ∈ U Parmi les problèmes d’optimisation combinatoire classique, on peut citer le problème de couverture ou the set covering problem [54][51] qui consiste à déterminer un couplage de valeur maximale. On peut citer aussi le problème de plus court chemin dans un graphe qui, étant donnés un graphe et une valuation sur les arcs du graphe, consiste à trouver le chemin qui minimise la somme des valuations des arcs reliant deux sommets du graphe. Le problème de voyageur de commerce, parmi les plus connus, consiste à trouver, dans un graphe, un cycle Hamiltonien dont le coût est minimal. 

 La programmation linéaire 

Définition 1.2.1. Un problème d’optimisation linéaire est un probème d’optimisation où la fonction objectif et les contraintes sont linéaires. 1.2. OPTIMISATION 11 Il peut s’écrire : min Z(x) = c.x Sous contraintes Ax ≥ b x ≥ 0 où A est une matrice n × m à coefficients réels, b ∈ R m, c ∈ R n et x ∈ R n Cette forme est appelée forme canonique. Définition 1.2.2. La forme standard du PL s’écrit sous la forme min Z(x) = c.x Sous contraintes Ax = b x ≥ 0 Définition 1.2.3. Le domaine Ω = {x ∈ R n/Ax ≥ b; x ≥ 0} est appelé domaine réalisable (ou admissible). Remarque 1. – Ω = ∅ : le problème n’a pas de solution réalisable. – Ω 6= ∅ : le problème est dit réalisable. – Le problème est dit borné s’il existe une constante réelle k ∈ R vérifiant l’inégalité suivante : c.x ≥ k pour toute solution réalisable x ∈ Ω Définition 1.2.4. Pour un problème de « minimisation », nous disons que la solution x ∗ est solution optimale si les deux conditions suivantes sont vérifiées : – x ∗ ∈ Ω (la solution x ∗ est admissible) – x ∈ Ω ⇒ c.x ≥ c.x∗ (la solution x ∗ donne la plus petite valeur). Théorème 1.2.1. Un programme linéaire est réalisable et borné si et seulement si il possède une solution optimale .

OPTIMISATION 

Résolution de programmes linéaires

 Dans cette sous section, nous présentons quelques définitions et propriétés puis une description de la méthode du Simplexe, méthode développée par G. Dantzig en 1947, et qui reste jusqu’à présent l’algorithme connu le plus performant pour les tailles classiques. a) Résolution graphique Définition 1.2.5. 1. Un ensemble P défini par P = {x ∈ R n/Ax ≤ b} est un polyèdre. A ∈ R n×m et b ∈ R m. 2. Un ensemble E est dit convexe, si ∀x, y ∈ E, λx + (1 − λ)y ∈ E pour 0 ≤ λ ≤ 1. Proposition 1.2.1. Soit DR = {x ∈ R n/Ax = b} l’ensemble des solutions réalisables d’un programme linéaire sous forme standard. DR est un polyèdre convexe, fermé. Définition 1.2.6. Un point x ∈ DR est un sommet (ou point extrême) si et seulement s’il n’existe pas y, z ∈ DR, y 6= z tels que x = λy + (1 − λ)z avec 0 ≤ λ ≤ 1. Théorème 1.2.2. ➀ x est une solution de base réalisable si et seulement si x est une solution réalisable de DR ; ➁ L’optimum de la fonction objectif f, s’il existe, est atteint en au moins un sommet de DR. b) Algorithme du Simplexe Nous donnons ici une synthèse de l’algorithme du Simplexe. Le lecteur intéressé par cette notion peut consulter [36] [37]. On considère un PL écrit sous forme standard c’est-à-dire si on a par exemple une contrainte de la forme Xn j=1 aijxi ≤ bi  . On peut écrire Xn j=1 aijxi + xn+i = bi en ajoutant une variable supplémentaire indexée n+i où i est le numéro de la contrainte. Cette variable n’apparaît pas dans la fonction objectif et prend des valeurs positives. Base réalisable et solutions associées On appelle variables de base, m variables parmi les n + m d’une forme standard ; qui peuvent être écrites en fonction des n autres variables. Ces variables forment alors une base du PL, les autres variables sont dites horsbases. On associe à une base une solution du PL en fixant les variables hors-bases à 0. Une base est dite réalisable si la solution associée est réalisable pour le PL. On peut facilement vérifier qu’une telle solution est réalisable : il suffit de vérifier que toutes les valeurs sont positives ou nulles. Il est très facile de savoir si la solution associée à une base admissible est optimale pour le PL. Pour cela, il suffit de réécrire la fonction objectif en fonctions des variables hors-bases. Cas de maximisation : si les coefficients obtenus sont tous négatifs alors la solution associée est optimale. Cas de minimisation : si les coefficients obtenus sont tous positifs alors la solution associée est optimale. Description de l’algorithme du Simplexe On suppose que l’on dispose d’une base réalisable de départ B0 . Les différentes étapes de l’algorithme sont les suivantes : (a) B0 base réalisable de départ. Itération k=0. (b) k ← k + 1. (c) à l’itération k, soit B la base courante, x = [xB, xN ] la solution de base correspondante. Calculer : ¯b = B−1 .b, (les valeurs des variables de base) 1.2. OPTIMISATION 14 π = cB.B−1 , (les multiplicateurs du simplexe) c¯N = cN − π.N (les coûts réduits) (d) si c¯N ≥ 0, STOP : l’optimum est atteint. Si ∃ s tel que : c¯s < 0 alors : (e) Soit As la colonne s de A. Calculer A¯ s = B−1 .As. Si a¯is ≤ 0, ∀i = 1, …, m, STOP : optimum non borné(−∞). sinon, calculer : xˆs = ¯br a¯rs = min i/a¯is>0 { ¯bi a¯is } . – Soit xt la variable correspondante à la r-ième ligne de la base c’està-dire telle que B−1 .A = er (m-vecteur à composantes toutes nulles sauf la composante r égale à +1) ; alors la variable s prend la valeur x¯r > 0 (« rentre en base » ) ; la variable t s’annule ( ˆxt = 0) (« sort de la base ») ; la nouvelle solution courante xˆ correspond à la nouvelle base réalisable : Bˆ = B+{As}−{At}. Calculer l’inverse de la nouvelle base Bˆ−1 et retourner en (b). Géométriquement, la procédure s’interprète comme un cheminement de point extrême en point extrême adjacent le long de la frontière de X (ensemble des solutions du problème). Algébriquement, elle s’interprète comme la détermination d’une suite de bases adjacentes B0 , B1 , …, Bq , … et de solution de bases x 0 , x1 , …, xq , … telles que z(x 0 ) > z(x 1 ) > … > z(x q ) > … 1.2.3 Programmation linéaire en nombres entiers La programmation linéaire en nombres entiers(PLNE) étudie des programmes linéaires dans lesquels les variables sont astreintes à être entières. En particulier les variables peuvent être booléennes c’est-à-dire ne prendre que les valeurs 0 ou 1. On parle de PL en 0-1. La contrainte d’intégrité sur la variable est nécessaire pour modéliser certains problèmes tels la localisation des hubs étudiée dans cette thèse, en particulier des problèmes algorithmiques. Cette contrainte complémentaire rend le problème plus complexe et demande des techniques particulières. c’est donc un problème NP-difficile. Elle est un domaine très riche de la programmation mathématique. Les recherches dans ce domaine sont nombreuses et ont vraiment commencé avec GOMORY en 1958. Pour plus de détails sur la PLNE, le lecteur intéressé peut consulter [48][26][52]. Modélisation mathématique Considérons la forme matricielle de la programmation linéaire ci-dessus. Si on introduit de nouvelles contraintes (appelées contraintes d’intégrité), on obtient la formulation de la programmation linéaire en nombres entiers. min Z(x) = c.x Sous contraintes Ax ≥ b x ≥ 0 xi entiers(i = 1, 2, …, n). où x = (x1, x2, …, xn). Lorsque les variables sont astreintes à prendre que les valeurs 0 ou 1, on parle de programmation linéaire en 0-1 ou programme binaire. Méthode de résolution Pour résoudre un PLNE, une des premières idées que l’on pourrait avoir serait d’abord de résoudre le PL continu, puis de prendre la valeur entière la plus proche, un arrondi de la solution optimale non entière que l’on aurait trouvé. Malheureusement, cette méthode est complètement fausse. Il existe des méthodes propres aux PLNE pour les résoudre. Pour résoudre les problèmes de PLNE, il existe aussi de nombreux solveurs commerciaux : par exemple Cplex, Xpress ou Gurobi et des solveurs livres : Glpk ou Scip. Dans cette thèse nous ne présentons que les méthodes de recherches arborescentes par séparation et évaluation. Méthode qu’ utilise le logiciel Cplex que nous avons utilisé pour nos simulations. Le lecteur intéressé par ces différentes méthodes peut consulter [52][43]. N’dogotar Nélio La méthode séparation et évaluation (Branch and Bound) L’algorithme de séparation et évaluation, plus connu sous son appellation anglaise Branch and Bound (B & B) [32] repose sur une méthode arborescente de recherche d’une solution optimale par séparations et évaluations, en représentant les états solutions par un arbre d’états, avec des nœuds, et des feuilles. Le branch-and-bound est basé sur trois axes principaux : – L’évaluation ; – La séparation, – la stratégie de parcours. L’évaluation L’évaluation permet de réduire l’espace de recherche en éliminant quelques sous-ensembles qui ne contiennent pas la solution optimale. L’objectif est d’essayer d’évaluer l’intérêt de l’exploration d’un sous-ensemble de l’arborescence. Le branch-and-bound utilise une élimination de branches dans l’arborescence de recherche de la manière suivante : la recherche d’une solution de coût minimal, consiste à mémoriser la solution de plus bas coût rencontré pendant l’exploration, et à comparer le coût de chaque nœud parcouru à celui de la meilleure solution. Si le coût du nœud considéré est supérieur au meilleur coût, on arrête l’exploration de la branche et toutes les solutions de cette branche seront nécessairement de coût plus élevé que la meilleure solution déjà trouvée. La séparation La séparation consiste à diviser le problème en sous-problèmes. Ainsi, en résolvant tous les sous-problèmes et en gardant la meilleure solution trouvée, on est assuré d’avoir résolu le problème initial. Cela revient à construire un arbre permettant d’énumérer toutes les solutions. L’ensemble de noeuds de l’arbre qu’il reste encore à parcourir comme étant susceptibles de contenir une solution optimale, c’est-à-dire encore à diviser, est appelé ensemble des noeuds actifs. – La largeur d’abord : Cette stratégie favorise les sommets les plus proches de la racine en faisant moins de séparations du problème initial. Elle est moins efficace que les deux autres stratégies présentées. – La profondeur d’abord : Cette stratégie avantage les sommets les plus éloignés de la racine (de profondeur la plus élevée) en appliquant plus de séparations au problème initial. Cette voie mène rapidement à une solution optimale en économisant la mémoire. – Le meilleur d’abord : Cette stratégie consiste à explorer des sousproblèmes possédant la meilleure borne. Elle permet aussi d’éviter l’exploration de tous les sous-problèmes qui possèdent une mauvaise évaluation par rapport à la valeur optimale. La méthode de Branch and Bound permet de résoudre le problème de localisation de façon optimale. Toutefois elle n’est efficace que pour les problèmes de petites tailles (problèmes avec au plus 50 noeuds)

 Quelques éléments de la théorie des graphes 

La théorie des graphes est, avec la combinatoire, une des pierres angulaires de ce qu’il convient de désigner par mathématiques discrètes . Les graphes sont utilisés pour modéliser de nombreuses situations et leurs applications sont par conséquent aussi nombreuses que variées : dans d’autres branches des mathématiques (algèbre, combinatoire,…), en informatique, en Recherche Opérationnelle (tournées de distribution, ordonnancement de tâches, construction de réseaux en transport,…), en télécommunication, en cartographie (coloriage de cartes), en chimie, etc. Quelques définitions Dans notre étude, les lignes aériennes qui seront considérées vont dans les deux sens donc les graphes des réseaux utilisés sont non orientés. Par conséquent nous donnons ici quelques définitions sur le graphe non orienté. Pour plus de détails sur la théorie des graphes, consulter les ouvrages de Berge [13] [14] et aussi par exemples [34][31]. Définition  Un graphe (non orienté) est constitué d’un ensemble G = {g1, g2, …, gn} de points appelés sommets et d’un ensemble A = {a1, a2, …, ak} d’arêtes tels qu’à chaque ai sont associés deux éléments de G, appelés extrêmités. Si les deux extrêmités sont confondues, l’arête est appelée boucle. S’il y a plusieurs arêtes entre deux sommets, on parle d’arêtes multiples. Un graphe ne présentant ni arête multiple, ni boucle est appelé graphe simple. Définition 1.2.8. 1. Une chaîne est une suite quelconque d’arêtes consécutives. 2. Sa longueur est le nombre d’arêtes qu’elle comporte. 3. Un cycle est une chaîne composée d’arêtes distinctes dont les deux extrémités sont confondues. 4. Un graphe est dit connexe si quels que soient les sommets gi et gj , il existe toujours une chaîne reliant gi à gj . Remarque 2. – Un graphe est orienté si les arêtes ont un sens de parcours. Chaque arête a alors une origine et une extrémité. Elle est représentée par une flèche et est appelé arc ; – On peut préciser la correspondance entre le vocabulaire utilisé pour les deux graphes : Graphe orienté graphe non orienté arête arc chaîne chemin cycle circuit Définition 1.2.9. Un graphe valué est un graphe pour lequel chaque arête est associée à un nombre réel appelé poids. Si le nombre réel est positif, on parle de graphe pondéré. Exemple Le graphe de la figure (1.1) représente les aéroports internationaux des capitales des pays de l’UEMOA connectés par un réseau aérien. Le graphe est connexe et est pondéré par les distances.