Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport

5.6 Notre approche : un schéma de Branch & Price

La méthode de génération de colonnes couplée avec une méthode de séparation (Branch & Price) est, dans la plupart des cas, utilisée pour une résolution exacte des problèmes sur lesquels elle est appliquée. Pour le problème 2|RO|L-VRP, de par la complexité du problème de chargement en deux dimensions, ces contraintes ne pouvant être modélisées sous forme de ressources dans le sous-problème, le sous-problème n'est pas résolu de manière exacte. Dans cette section, nous décrivons un schéma de Branch & Price, tel qu'il faudrait l'appliquer dans le cas où l'on voudrait une résolution exacte (pour cela, le sous-problème doit être lui aussi résolu de manière exacte). Nous présentons dans les sections 5.7 et 5.8 notre approche, qui s'inscrit dans une recherche des moyens pour rendre heuristique une méthode a priori exacte.

Chapitre 5. Application au problème de Tournées de Véhicules avec Contraintes de Chargement

Cette section présente dans un premier temps les spécificités de notre algorithme pour la méthode de séparation, puis pour la résolution du problème esclave. Les heuristiques de chargement utilisées seront présentées par la suite et nous montrerons les différentes mises en oeuvre possibles de ces algorithmes dans notre schéma de résolution.

5.6.1 Méthode de séparation

Une fois que la génération de colonnes est terminée, c'est-à-dire que le problème esclave n'a pas réussi à trouver de chemins de coûts négatifs, nous obtenons une borne inférieure au problème. En effet, le problème considéré ne possède pas de contraintes d'intégralité sur les variables è_ù. Si toutes les variables sélectionnées sont entières (représentant ainsi des routes complètes), la solution est réalisable. Dans le cas contraire, afin de rendre cette solution réalisable, une méthode de séparation est appliquée. On est donc confronté au choix de politique de séparation. Une approche simple est de brancher sur la valeur des variables è_ù. On crée alors un noeud fils pour lequel on fixe une variable fractionnaire è_ù à 1 et un autre noeud pour lequel la variable est fixée à 0. On obtient donc un sous-problème dans lequel la route correspondant à la variable è_ù est obligatoire et un sous-problème où cette route est interdite.

Une telle stratégie est dans la plupart des cas mauvaise : en effet, elle a pour conséquence la création d'un arbre fortement déséquilibré. De plus, le fait d'interdire une route n'a que peu de répercussions dans le problème esclave et peut être difficile à intégrer.

Il est donc commun de brancher sur les variables de la formulation initiale. Si la solution est fractionnaire, alors il existe un arc _xij traversé par un flot fractionnaire.

xij = ? bk ijèk (5.34)

rk?Ù

On choisit le premier arc fractionnaire. On définit alors deux fils : un fils pour lequel xij = 0 et un fils pour lequel xij = 1. Dans le premier cas, cela implique de sup-primer toutes les routes empruntant cet arc dans le problème maître et de supprimer l'arc (vi, vj) dans le sous-problème. Dans le cas où l'arc est fixé à 1, on supprime dans le problème maître toutes les routes traversant un arc ayant pour extrémité initiale vi (autre que (vi, vj)) et toutes les routes traversant un arc ayant pour extrémité terminale vj (autre que (vi, vj)). Dans le sous-problème, on supprime alors tout arc (vi, vk) avec vk =6 vj et (vk, vj) avec vk =6 vi. Cette règle de branchement assure la convergence.

Une fois qu'un noeud est créé, on résout par génération de colonnes, la relaxation linéaire du problème correspondant aux branchements choisis.

Les noeuds sont traités dans l'ordre respectant la valeur croissante de leur borne inférieure (méthode connue sous le nom de Best Bound First). La borne inférieure est égale à la valeur de la relaxation linéaire.

Lorsqu'on obtient une solution entière, cette solution est réalisable et le coût de cette solution devient par conséquent une borne supérieure au problème. Cette borne est utilisée afin de ne pas explorer les noeuds dont la borne inférieure est supérieure à la plus petite borne supérieure.