Résolution par des algorithmes exacts et approchés de problèmes intégrés d’ordonnancement de la production et de tournées de véhicules

 Modélisation d’un problème d’optimisation

Chaque problème d’optimisation peut se modéliser à l’aide des quatre types de composantes suivantes. Les paramètres sont les données fournies par l’environnement du problème. Ils ne peuvent être modifiés. Un ensemble de paramètres décrit une instance du problème. Les variables permettent de modéliser les décisions à prendre afin de définir une solution. Les variables peuvent être continues (comprises entre moins l’infini et plus l’infini), entières ou bien binaires. Les contraintes imposent des relations entre (et sur) les variables. Ces relations doivent être respectées pour que la solution obtenue soit réalisable, c’est-à-dire acceptable comme solution du problème. On note S l’ensemble des solutions réalisables de l’instance d’un problème. La fonction objectif définit la qualité d’une solution, que l’on cherche à minimiser (ou maximiser) lors de la résolution d’un problème d’optimisation. En d’autres termes, si l’on considère f une fonction objectif qui associe à une solution s sa valeur objectif f(s), résoudre un problème d’optimisation revient à trouver s∗ ∈ S tel que : f(s∗) = mins∈S f(s)

Prenons l’exemple du problème de sac à dos [Toth, 1990] dans sa version la plus simple : Vous êtes Arsène Lupin et vous vous êtes introduit chez un riche négociant. La maison dort, vous venez de forcer le coffre avec succès, les richesses s’étalent devant vous. Cependant, votre sac est encore vide et le temps presse. Vous ne pourrez pas tout emporter car vous charger audelà d’un poids W risquerait de compromettre votre agilité, votre discrétion et donc votre fuite. Soit J l’ensemble des objets présents dans le coffre, chaque objet j ∈ J peut se résumer à deux caractéristiques : son poids wj et son prix de vente au marché noir cj . W et les ensembles wj et cj sont les paramètres de votre problème. Vous avez ces éléments en tête, vous êtes un professionnel. Pour chaque objet j, un choix s’offre à vous, modélisé par une variable xj . Choisissez de dérober l’objet j, xj vaudra 1, sinon elle vaudra 0. Vous devez également respecter la contrainte suivante : la somme des poids wj des objets j dans votre sac ne doit pas dépasser sa capacité W. Votre objectif est de maximiser la valeur de l’ensemble des objets que vous emportez.

Complexité des problèmes de décision

La théorie de la complexité se base sur le temps (ou l’espace mémoire) nécessaire à un algorithme pour effectuer une opération sur un problème, comme par exemple prouver l’existence d’une solution. De telles valeurs s’évaluent en fonction de la taille de l’instance et de ses données. Très souvent, seule la taille de l’instance, communément notée n, est utilisée (un choix de n objets, n sites à visiter, n tâches à planifier). La complexité est exprimée par une fonction mathématique dépendante de n et considérant le pire des cas. Par exemple, trouver l’index d’un élément dans un tableau à n entiers demande, dans le pire des cas, de parcourir les n éléments du tableau (si l’élément est à la fin ou s’il est absent) soit n opérations. De même, trier un tableau à l’aide d’un algorithme nommé tri à bulle demande dans le pire cas n² opérations (le pire des cas étant si le tableau est trié dans l’ordre inverse de celui recherché). Ce nombre d’opérations tombe à n log(n) avec l’usage d’un autre algorithme comme le tri par fusion par exemple.

Les problèmes de décision peuvent être associés à différentes classes de complexité dont voici les deux principales :

– La classe de complexité notée P regroupe tous les problèmes de décision résolvables en temps polynomial. C’est-à-dire qu’il existe un algorithme polynomial pour définir si la réponse à la question posée est “oui” ou “non” .

– La classe de complexité N P regroupe tous les problèmes de décision dont une solution peut être vérifiée en temps polynomial (P est donc inclu dans N P). Dans le cas du problème de sac à dos, dans sa variante décisionnelle, évaluer une solution demande d’évaluer si la somme des poids dans le sac est inférieure à W et si la somme des coûts est supérieure à K. Ces opérations peuvent être réalisées en temps polynomial donc le problème de sac à dos appartient à la classe N P.

Méthode de résolution

Une méthode de résolution est un algorithme visant à apporter une solution à un problème donné pour n’importe laquelle de ses instances. Dans le cadre de cette section nous nous limiterons à la description des méthodes pour les problèmes d’optimisation. On peut distinguer deux grandes familles de méthodes de résolution : les méthodes approchées et les méthodes exactes.

Méthode approchée

Les méthodes approchées sont généralement utilisées pour obtenir des solutions dans des délais raisonnables. Elles ne sont pas assurées de trouver la solution optimale (contrairement aux méthodes exactes), mais fournissent généralement de bonnes solutions, voire des solutions optimales et peuvent parfois donner des garanties sur la qualité des solutions trouvées (solution au pire à 50% de l’optimal par exemple). Dans la suite de cette section, plusieurs méthodes approchées (appelées aussi heuristiques et métaheuristiques) seront brièvement présentées. Ces méthodes seront d’ailleurs réutilisées dans cette thèse.

Heuristique gloutonne 

Les heuristiques gloutonnes sont des méthodes de résolution très rapides, souvent des algorithmes polynomiaux, généralement utilisées pour fournir des solutions initiales à des méthodes plus complexes. Ces méthodes construisent une solution par un processus itératif et ne reviennent jamais sur une décision prise. une heuristique de construction gloutonne pourrait être la suivante : Chaque objet j dans l’ensemble J se voit attribuer une utilité uj égale au quotient du coût cj de l’objet sur son poids wj . Les objets sont ensuite triés par ordre décroisant d’utilité et sont placés dans le sac dans cet ordre. Si un objet ne peut pas être placé dans le sac, on passe à l’objet suivant. L’heuristique prend fin lorsqu’aucun objet ne peut plus être placé dans de sac.

Recherche locale

Les recherches locales sont des méthodes plus élaborées visant à améliorer itérativement une solution avec des opérateurs simples. L’algorithme général d’une recherche locale est le suivant. Une recherche locale démarre avec une solution initiale (généralement aléatoire ou générée par une heuristique gloutonne). Tant que la condition d’arrêt de la recherche locale n’est pas atteinte, elle tente d’améliorer itérativement la solution courante. À chaque itération, un ensemble de nouvelles solutions est généré à partir de la solution courante et d’un opérateur de voisinage. Cet ensemble est d’ailleurs appelé le voisinage de la solution courante. Une nouvelle solution de ce voisinage, généralement la meilleure, remplace la solution courante si elle l’améliore. Si elle ne l’améliore pas, alors on dit qu’un minimum local est atteint. La recherche locale procède alors à une phase de diversification qui modifie fortement la solution courante qui sera de nouveau améliorée jusqu’à atteindre un nouveau minimum local ou le critère d’arrêt de la recherche locale. Une procédure de diversification peut, par exemple, donner lieu à un certain nombre de modifications aléatoires de la solution courante. Un critère d’arrêt classique se base sur le temps utilisé par la méthode.

Table des matières

Introduction
1 Présentation des champs d’étude
1.1 Introduction à la recherche opérationnelle
1.1.1 Modélisation d’un problème d’optimisation
1.1.2 Complexité
1.2 Méthode de résolution
1.2.1 Méthode approchée
1.2.2 Méthode exacte
1.3 Problèmes abordés dans cette thèse
1.4 Les problèmes d’ordonnancement d’atelier
1.4.1 Notation de Graham
1.4.2 Exemples de notations et de résultats de complexité
1.4.3 Positionnement du sujet de thèse en termes d’ordonnancement
1.4.4 Les coûts d’inventaire dans les problèmes d’ordonnancement
1.5 Les problèmes de tournées
1.5.1 Description du problème de voyageur de commerce
1.5.2 Un résultat et quelques algorithmes
1.5.3 Positionnement du sujet de thèse en termes de tournées de véhicules
1.6 Problème de gestion de la chaîne d’approvisionnement dans les grandes surfaces
1.6.1 Trois types d’agents
1.6.2 Quelques cas concrets
1.7 Plan de thèse
2 État de l’art
2.1 État de l’art sur les problèmes intégrés
2.1.1 Historique des problèmes intégrés
2.1.2 Littérature des problèmes intégrés
2.2 Littérature spécifique aux sous-problèmes de production et de distribution
2.2.1 Le problème de flow shop avec coût d’inventaire
2.2.2 Le problème de livraison avec pénalité de retard
2.3 Études connexes
2.3.1 À propos de la chaîne d’approvisionnement
2.3.2 À propos de la collaboration
2.4 Conclusion
3 Problème général : un producteur, un distributeur et plusieurs clients
3.1 Présentation du problème
3.2 Formulation mathématique
3.3 Résultats préliminaires
3.4 Conclusion
4 Approche où le producteur domine
4.1 Contexte
4.2 Adaptation de la modélisation
4.2.1 Problème de production
4.2.2 Problème de distribution
4.2.3 Synchronisation et résumé
4.3 Méthodes de résolution
4.3.1 Représentation et évaluation d’une solution
4.3.2 Algorithme GRASP
4.3.3 Algorithme génétique (AG)
4.3.4 Gestion de la population
4.3.5 Paramétrage de l’algorithme génétique
4.4 Expérimentations et résultats
4.4.1 Génération des instances
4.4.2 Évaluation des heuristiques
4.4.3 Comparaison du GRASP et de l’algorithme génétique
4.4.4 Répartition des coûts de la fonction objectif
4.4.5 Comparaison des méthodes sur des instances de petites tailles
4.5 Conclusion
Conclusion

Télécharger le rapport complet