Le problème d'affectation quadratique généralisé (GQAP en anglais) ou non (QAP), est NP-difficile, et en pratique très difficile a résoudre exactement, meme pour des instances de petite taille. Les couts d'affectation sont quadratiques, car ils dépendent des affectations par paires. Plusieurs approches de résolution exacte ou approchée pour le QAP et le GQAP seront présentées, ainsi que les résultats de nombreuses expériences numériques:
La méthode RLT (reformulation and linearization technique) adaptée au (G)QAP ne permet pas de résoudre des instances de grande taille. Le passage a des niveaux superieurs (RLT-2 et RLT-3) permet d'améliorer les bornes inférieures et a fortiori le temps de résolution par branch-and-bound.
Les méthodes de convexification de type QCR (quadratic convex reformulation) permettent de convexifier en utilisant des méthodes SDP des problèmes quadratiques en variables 0-1 purs et d'utiliser ensuite des logiciels du commerce. Des améliorations récentes permettent de renforcer les bornes inférieures.
La méthode de l'enveloppe convexe (Convex Hull en anglais), adaptée de la méthode de décomposition simpliciale, permet dans le cas convexe d'obtenir une borne inférieure et dans tous les cas de bonnes solutions approchées. De nombreuses expériences numériques avec des instances non convexes de GQAP et des instances QAP de QAPLIB, montrent que l'erreur est très faible et les temps de calcul raisonnables.
L'utilisation combinée de QCR inversée et de la méthode CH pour des instances GQAP convexes produit des résultats sensiblement améliores compares à CH utilisé seul.
Le problème d'affectation des camions aux portes d'entrée et de sortie d'un crossdock est un problème important en logistique. Il peut être formulé comme un GQAP dans le sens ou le cout de traitement d' un objet provenant d'un camion et expédié dans un autre camion dépend de l'emplacement choisi pour ces deux camions. De nombreux résultats numériques montrent qu'il devrait être possible de résoudre ce problème en temps réel lors de l'arrivée de nouveaux camions à décharger.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Non-linear optimisation, bi-level optimisation and yield management |
| PDF version | : |  PDF version |
