TSP-VRP-PROFITS

Responsable Scientifique :

Feillet Dominique

Chercheurs Permanents :

Feillet Dominique

Problematique :

Les problèmes de voyageurs de commerce et de tournées de véhicules avec gains (TSP with profits, VRP with profits) sont des problèmes de tournées dans lesquels deux objectifs concurrentiels doivent être pris en compte : minimiser la distance parcourue et maximiser le gain collecé par la visite des sommets du graphe. Contrairement aux versions classiques du TSP et du VRP, il n'est pas imposé de visiter l'ensemble des sommets.
Ce type de problèmes a du sens dans de nombreuses situations réelles, par exemple lorsque des contraintes logistiques empèchent d'envisager la visite de tous les sommets.

Objectifs :

Un premier objectif réalisé au cours de ce projet a été définir cette classe de problèmes.
Nous nous intéressons maintenat à voir comment le niveau de décision supplémentaire induit par la notion de gains (sélection des sommets) influe sur la structure des problèmes, la difficulté de leur résolution et peut être intégré dans les méthodes de résolution.
Nous élargissons notre étude à des problèmes de structure proche, où la sélection des sommets existe aussi, tel que le problème de l'acheteur itinérant (Traveling Purchaser Problem) ou le problème de voyageur de commerce généralisé (Generalized Travling Salesman Problem).

Methodologie :

  • Génération de colonnes
  • Méthodes à grand voisinages

Collaborations :

Michel Gendreau (CRT, Montréal)
A. Hertz (GERAD, Montréal)
P. Dejax (Ecole des Mines de Nantes)
C. Artigues (LAAS, Toulouse)
C. Archetti (Université de Brescia)
M.G. Speranza (Université de Brescia)

Soutien :

Page Web :



Laboratoire Informatique d'Avignon

Université d'Avignon et des Pays de Vaucluse
339 chemin des Meinajaries, Agroparc BP 91228, 84911 Avignon cedex 9
+33 (0)4 90 84 35 00