Heuristiques pour le Problème du Vendeur m-Péripatétique

¹ LAMIH-ROI, Université de Valenciennes, Le Mont Houy, 59313 Valenciennes, Cedex 9, France
² GERAD and Canada Research Chair in Distribution Management, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, H3T 2A7, Montréal, Canada
³ LAMIH-ROI, Université de Valenciennes, Le Mont Houy, 59313 Valenciennes, Cedex 9, France; frederic.semet@univ-valenciennes.fr

Reçu : 19 Février 2006
Accepté : 17 Juillet 2008

Résumé

Le Problème du Vendeur m-Péripatétique (m-PVP) est défini sur un graphe non orienté G=(V,E) où V = {1,...,n} est l'ensemble des sommets, E = {(i,j) : i,j ∈ V,i < j} est l'ensemble des arêtes et (c_ij) est une matrice de coûts définie sur E. Le m-PVP consiste à déterminer m cycles hamiltoniens sur G n'ayant aucune arête en commun et dont le coût total est minimal. Cet article décrit sept nouvelles heuristiques pour le m-PVP et les compare à celle qui a été proposée par Krarup en 1975.

Abstract

The m-Peripatetic Salesman Problem (m-PSP) is defined on a undirected graph G = (V, E) where V = {1,...,n} is the vertex set, E = {(i,j) : i,j ∈ V,i < j} is the edge set and ((c_ij) is a cost matrix defined on E. The m-PSP consists of determining m edge-disjoint Hamiltonian cycles of least total cost on G. This article describes seven new heuristics for the m-PSP and compares them with the heuristic proposed by Krarup in 1975.