Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport

2.3 Classe des problèmes considérés : Problèmes de Tournées avec Couverture Partielle

Le Problème du Voyageur de Commerce, ou Traveling Salesman Problem (TSP), est un problème qui est largement étudié depuis le 20ème siècle. L'objectif de ce problème est de visiter un ensemble donné de villes, en minimisant la distance totale parcourue. La première publication sur la résolution du TSP est attribuée à Menger (1932), dans laquelle il considère une variation appelée das Botenproblem ou the Messenger Problem. La résolution de ce problème sous sa forme originale est aujourd'hui encore un challenge très concurrentiel en optimisation combinatoire. David Applegate, Robert Bixby, Vasek Chvátal et William Cook ont développé dans les années 1990 la méthode Concorde 1, basée sur une méthode de séparation et de coupes (séparation et génération de coupes) qui permet de résoudre optimalement des instances de très grande taille (plusieurs milliers de villes). Cet intérêt pour ce problème a poussé la communauté scientifique à proposer un grand nombre d'extensions ou de variantes du TSP. Un ouvrage récent est consacré au problème du Voyageur de Commerce et à ses variations (Gutin et Punnen, 2002).

Les premières extensions du TSP portent sur la considération de transport de marchandises récoltées durant la tournée, puis ramenées à un dépôt. À ce problème initial furent ajoutées des contraintes de temps durant lesquels la récupération des marchandises pouvait avoir lieu (Problème du Voyageur de Commerce avec Fenêtre de Temps ou Traveling Salesman with Time Windows), des contraintes de capacités (Problème du

1. http :// www-neos.mcs.anl.gov

Voyageur de Commerce avec Contraintes de Capacité ou Capacitated Traveling Salesman Problem). À tous ces problèmes fut ajoutée la possibilité d'utiliser plusieurs véhicules. Ces problèmes sont connus sous le nom de problèmes de calcul de tournées de véhicules ou Vehicle Routing Problem (VRP). Pour plus de détails sur les problèmes de tournées de véhicules, nous conseillons au lecteur le livre de Toth et Vigo (2002).

Le voisinage que nous présentons à travers deux exemples dans les chapitres suivants peut s'appliquer à des variantes du TSP pour lesquelles la visite de l'ensemble des sommets du graphe n'est pas obligatoire. La classe de problèmes la plus étudiée parmi les problèmes présentant cette caractéristique est la classe des Problèmes de Tournées avec Gains (voir (Feillet et al., 2005) pour plus de détails sur cette classe de problèmes). Nous nommons par souci de simplicité cette classe de problèmes les Problèmes de Tournées avec Couverture Partielle (Partial Covering Routing Problems). Ces problèmes sont définis comme des problèmes dont les solutions ne visitent pas nécessairement l'ensemble des noeuds.

L'ensemble de ces problèmes présente une particularité dans sa structure : l'ensemble des noeuds du graphe ne doit pas être nécessairement visité. Cette différence avec un certain nombre d'extensions du problème du Voyageur de Commerce implique d'avoir des solutions de taille variable. De plus, on peut remarquer une difficulté supplémentaire dans la résolution du problème : une fois que les villes à visiter sont choisies, il reste à déterminer l'ordre dans lequel elles seront visitées, ce qui se ramène dans la plupart des cas à un TSP de taille réduite.

2.3.1 Problèmes de Tournées avec Gains

La classe des problèmes de Tournées avec Gains est une extension bien connue du problème du Voyageur de Commerce. Ces problèmes sont généralement définis de la façon suivante. Soit G = (V, A) un graphe orienté avec V = {v1, . . . , v_n} un ensemble de sommets pour lequel v1 est le dépôt. On note _cij le coût de l'arc (vi, vj). On associe à chaque sommet vi un gain supposé positif.

On peut voir cette classe de problèmes comme un Problème de Voyageur de Commerce bicritère avec deux objectifs contraires : d'une part, minimiser la distance parcourue (avec le droit de ne pas visiter l'ensemble des sommets) et d'autre part, maximiser la somme des gains collectés auprès des sommets desservis.

Dans le cas du problème du Voyageur de Commerce avec Gains, on trouve trois variantes dont l'objectif ne comporte qu'un critère :

- Orienteering Problem (Golden et al., 1987) : l'objectif consiste à maximiser le gain

sous la contrainte que la distance soit inférieure à une longueur maximale,

- Prize-collecting Traveling Salesman Problem (Balas, 1989) : l'objectif consiste à mini-

miser la distance parcourue sous la contrainte que le gain récolté soit supérieur à

un montant minimal,

- Profitable Tour Problem (Dell'Amico et al., 1995) : l'objectif est de minimiser la différence entre la somme des distances parcourues et la somme des gains récoltés.

Le problème du Voyageur de Commerce avec Gains a été étudié dans quelques cas sous sa forme bicritère : Keller (1985) , Bérubé et al. (2008).

On retrouve ces problèmes sous d'autres noms :

- Selective TSP (Laporte et Martello, 1990; Gendreau et al., 1998),

- Maximum Collection Problem (Kataoka et Morito, 1988),

- Traveling Salesman Subtour Problem (Gensch, 1978),

- Traveling Salesman Subset-Tour Problem with One additional Constraint (Mittenthal et Noon, 1992),

- Cardinality Constrained Circuit Problem (Bauer et al., 1998),

- Score Orienteering Problem (Kataoka et al., 1998),

- Multiobjective Vending Vroblem (Keller et Goodchild, 1988),

- Resource Constrained Traveling Salesman Problem (Pekny et Miller, 1990), - . . .

Dans le cas où l'utilisation de plusieurs véhicules est autorisée, on trouve aussi trois variantes mono-critères:

- Team Orienteering Problem (Chao et al., 1996) : l'objectif est de maximiser les gains collectés sous contrainte de ne pas dépasser une longueur maximale de distance pour chaque route,

- Prize-collecting VRP (Tang et Wang, 2006) : l'objectif est de minimiser la distance totale parcourue sous contrainte que le gain total récolté soit supérieur à un montant minimum et en respectant des contraintes de capacités sur les véhicules,

- Profitable VRP (Archetti et al., 2007) : l'objectif est de minimiser la différence entre la somme des distances parcourues et la somme des gains récoltés sous contrainte de capacité des véhicules.