Heuristiques pour le problème du vendeur $m$-péripatétique

Duchenne, Éric; Laporte, Gilbert; Semet, Frédéric

doi:10.1051/ro/2009001

Geodesic

Parcourir par

Heuristiques pour le problème du vendeur

m

-péripatétique

Duchenne, Éric ; Laporte, Gilbert ; Semet, Frédéric

RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 13-26

Voir la notice de l'article provenant de la source Numdam

Abstract (VO)
Résumé

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 \in V, i < j}$ is the edge set and (c $_{i j})$ 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.

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, \dots, n}$ est l’ensemble des sommets, $E = {(i, j) : i, j \in V, i < j}$ est l’ensemble des arêtes et $(c_{i j})$ 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.

MR Zbl

DOI : 10.1051/ro/2009001

Classification : 90C09, 90C59
Keywords: problème du vendeur $m$-péripatétique, problème du voyageur de commerce, heuristiques

@article{RO_2009__43_1_13_0,
     author = {Duchenne, \'Eric and Laporte, Gilbert and Semet, Fr\'ed\'eric},
     title = {Heuristiques pour le probl\`eme du vendeur $m$-p\'eripat\'etique},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {13--26},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {1},
     year = {2009},
     doi = {10.1051/ro/2009001},
     mrnumber = {2502322},
     zbl = {1158.90386},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2009001/}
}

TY  - JOUR
AU  - Duchenne, Éric
AU  - Laporte, Gilbert
AU  - Semet, Frédéric
TI  - Heuristiques pour le problème du vendeur $m$-péripatétique
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 13
EP  - 26
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2009001/
DO  - 10.1051/ro/2009001
LA  - en
ID  - RO_2009__43_1_13_0
ER  -

%0 Journal Article
%A Duchenne, Éric
%A Laporte, Gilbert
%A Semet, Frédéric
%T Heuristiques pour le problème du vendeur $m$-péripatétique
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 13-26
%V 43
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2009001/
%R 10.1051/ro/2009001
%G en
%F RO_2009__43_1_13_0

Duchenne, Éric; Laporte, Gilbert; Semet, Frédéric. Heuristiques pour le problème du vendeur $m$-péripatétique. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 13-26. doi: 10.1051/ro/2009001

Cité par Sources :