5.8 Branch & Price heuristique
Nous avons présenté dans la section
précédente un schéma classique de résolution par
Branch & Price. De par la complexité des contraintes de chargement,
le sousproblème n'est pas résolu de manière exacte. Notre
travail s'est donc porté sur les méthodes
d'accélération de résolution. Dans cette section, nous
montrons tous les moyens dont nous disposons pour rendre la méthode
heuristique, que ce soit au niveau du problème esclave, de la
méthode de séparation, ou de la résolution du
problème maître restreint. La plupart des changements que nous
proposons présentent l'intérêt de dépendre de
paramètres. Ainsi, nous pouvons rendre à nouveau la
méthode exacte (du moins pour la méthode de séparation et
la gestion des colonnes) en ne modifiant que certains paramètres.
5.8.1 Problème esclave heuristique
On peut rendre heuristique le problème esclave de
plusieurs manières différentes.
Gestion de la taille de la liste des chemins
partiels
La première technique, et l'une des plus
intéressantes afin d'accélérer la résolution du
problème esclave, est de limiter le nombre de chemins partiels pour
chaque sommet. On l'a vu précédemment, le nombre de chemins
partiels pour chaque sommet peut rapidement exploser. Afin de limiter ce
nombre, on peut ne garder en mémoire que les nblabels premiers
chemins partiels de la liste triée de chemins partiels qui nous semblent
les plus prometteurs. Le tri de cette liste est effectué selon le
coût du chemin partiel. On peut aussi par ailleurs renforcer les
règles de dominances entre deux chemins partiels en créant des
règles de dominances « trop fortes >>. Ces règles
risquent de supprimer des chemins partiels non dominés, mais permettent
d'accélerer la résolution du sousproblème.
Gestion des successeurs
Cette technique est proche de la technique de Recherche
à Limitation d'Écarts. En limitant le nombre de successeurs pour
chaque sommet, on oblige les chemins partiels à être
étendus uniquement vers de « bons>> voisins. On peut donc
modifier le nombre de sommets considérés comme « bons
>>. Cette méthode est plus restrictive que la méthode de
Recherche à Limitation d'Écarts puisqu'elle n'autorise aucun
écart.
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
5.8.2 Gestion des colonnes
Lors de la résolution de la relaxation linéaire
du problème maître restreint par le solveur, celui-ci va fixer au
bout d'un certain nombre d'itérations des colonnes. Les variables seront
alors égales à 1. Afin d'accélérer la
résolution, il peut être intéressant de fixer de telles
variables pour toute la suite de la résolution. Il faut cependant
attendre qu'un nombre suffisant de colonnes ait été
générées, afin de ne pas fixer à 1 une colonne
inintéressante. Lorsque l'on choisit de fixer une colonne 0k
à 1, cela revient à ajouter dans le noeud courant les
contraintes qui fixent à 1 l'ensemble des arcs empruntés par la
colonne considérée. On peut remarquer que le fait d'imposer une
route interdit toutes les routes partageant les mêmes sommets (les
sommets étant déjà visités). Cela revient donc
à travailler sur un problème de taille réduite, pour
lequel on retire les sommets appartenant à la route 0k. Cette
méthode est différente d'une méthode de séparation
car la colonne est fixée à 1 pour toute la suite de la
résolution.
| 
