Le problème de voyageur de commerce avec les classes de priorité (VDCp) est un cas particulier du problème de voyageur de commerce clusterisé (VDCc) où l'ensemble de villes à visiter est divisé en sous-ensembles avec une contrainte de précédence : le véhicule ne peut pas sortir d'un cluster sans visiter toutes les villes de ce cluster et il ne peut aller à un cluster dont la priorité est inférieure à celui qu'il vient de quitter.

Une des applications possibles de ce problème est observée dans la logistique humanitaire. Après une catastrophe naturelle ou industrielle, la situation est évaluée et les zones sont triées selon l'importance de l'impact. Les zones les plus touchées doivent naturellement être secourues prioritairement.

Jongens et Volgenant [1] ont proposé une relaxation lagrangienne pour le VDCc mais leur modèle ne permet pas de résoudre le cas où il y a un ordre prédéfini de visite des clusters.

Nous proposons un modèle de programmation linéaire en nombres entiers et sa relaxation lagrangienne inspirée de celle de Jongens et Volgenant. Nous démontrons que, lorsque la relaxation trouve une solution réalisable, cette dernière est optimale, sans aucune autre condition. Afin de juger la qualité et l'efficacité de cette méthode, elle est testée sur les instances de la littérature et générées aléatoirement contenant jusqu'à 200 sommets.

[1] Jongens K. Volgenant T. The symmetric clustered traveling salesman problem . European Journal of Operational Research 1985: 19 (1) : 68-75