Une heuristique de génération de colonnes pour le problème de tournées de véhicules avec faisabilité boîte noire

Résumé : Nous proposons de reformuler le VRPBB comme un problème de partitionnement d'ensembles que nous optimisons à l'aide d'une approche (heuristique) de génération de colonnes. Des fourmis collectrices génèrent et collectionnent des colonnes (tournées) de façon heuristique, tout en étant guidées par des dépôts de phéromones provenant d'un oracle externe. Cet oracle calcule les dépôts de phéromones en fonction de la solution actuelle à la relaxation du problème. L'approche nous permet d'améliorer de manière itérative la borne inférieure du problème considéré. Une solution entière est trouvée en résolvant le problème de partitionnement d'ensembles avec solveur MIP. Cet article présente trois contributions. D'abord, nous proposons un nouveau problème générique, le problème de tournées de véhicules avec faisabilité boîte noire, qui permet de représenter des problèmes de tournées de véhicules exigeant la résolution d'un problème combinatoire par tournée. Deuxièmement, nous proposons un algorithme pour résoudre ce problème générique. Notre méthode est donc indépendante du problème combinatoire à résoudre pour chaque tournée. Elle peut facilement être appliquée à un nouveau problème en utilisant une autre fonction de faisabilité boîte noire. Enfin, nous démontrons l'applicabilité de la méthode proposée sur deux problèmes, le VRP avec chargement en trois dimensions (3L-CVRP) et le VRP à piles multiples (MP-VRP). Nous comparons nos résultats avec ceux des approches dédiées existantes pour montrer que notre approche générique est très compétitive.
Type de document :
Communication dans un congrès
Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00826544
Contributeur : Ist Inria Saclay <>
Soumis le : lundi 27 mai 2013 - 17:13:12
Dernière modification le : mardi 28 mai 2013 - 06:40:28
Document(s) archivé(s) le : mardi 3 septembre 2013 - 09:46:23

Fichier

paper_3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00826544, version 1

Collections

Citation

Florence Massen, Yves Deville, Pascal Van Hentenryck. Une heuristique de génération de colonnes pour le problème de tournées de véhicules avec faisabilité boîte noire. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. 〈hal-00826544〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

136