Un algorithme de branch-and-cut pour la résolution du Problème de Tournées SélectivesReportar como inadecuado




Un algorithme de branch-and-cut pour la résolution du Problème de Tournées Sélectives - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 Université Libanaise 2 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes Compiègne

Résumé : Cet article décrit un algorithme de branch-and-cut pour résoudre le problème de tournées sélectives Team Orienteering Problem - TOP. Il s-agit d-une variante du problème de tournées de véhicules dont le but est de maximiser la somme des profits collectés tout en respectant un temps de trajet limite pour chaque véhicule. Notre algorithme est basé sur une formulation linéaire avec un nombre polynomial de variables. Un ensemble de propriétés de dominance et d-inégalités valides est proposé pour renforcer cette formulation. Elles sont basées sur l-élimination de la symétrie et des sous-tours ainsi que l-introduction de bornes sur le profit-nombre de clients et de coupes exploitant des graphes d-incompatibilité. Les expérimentations réalisées sur le benchmark du TOP montrent l-efficacité de notre méthode. L-algorithme proposé est capable de traiter un grand nombre d-instances et permet de résoudre à l-optimalité plusieurs instances ouvertes.

Mots-clés : branch-and-cut graphe d-incompatibilité inégalités valides





Autor: Racha El-Hajj - Duc-Cuong Dang - Aziz Moukrim -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados