GRASP-ELS pour la résolution du problème de tournées de véhicules avec profits et contraintes de capacité

Session : SS14 / SS14 : Logistique collaborative dans la distribution urbaine
Jeudi 11 février 15:00 - 16:40 Salle : Apollo
Asma Ben Said, Racha El Hajj et Aziz Moukrim

Le problème de tournées sélectives avec profits et contraintes de capacité (Capacitated Team Orienteering Problem - CTOP) dispose d'une flotte de véhicules et d’un ensemble de clients potentiels. Chaque client est caractérisé par une demande de service et un profit pouvant être collecté par un seul véhicule. La résolution du CTOP consiste à choisir les clients à servir et les organiser parmi les différents véhicules afin de maximiser la somme des profits collectés tout en respectant une longueur de trajet limite et la capacité maximale imposée pour chaque véhicule. Dans cet article, nous proposons une nouvelle heuristique basée sur la structure générale du Greedy Randomized Aadaptative Search Procedure (GRASP) améliorée par une recherche locale évolutionnaire (ELS). Les résultats expérimentaux montrent que notre algorithme atteint les meilleurs résultats de la littérature et détermine une nouvelle solution de profit strictement meilleur que toutes les solutions de la littérature.

Mots clés : tournées de véhicules, GRASP, construction/destruction, recherches locales