Heuristiques pour le problème du vendeur ...
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Heuristiques pour le problème du vendeur m-péripatétique
Author(s) :
Duchenne, Éric [Auteur]
Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201 [LAMIH]
Laporte, Gilbert [Auteur]
Laboratoire CIRRELT Université Laval Quebec [CIRRELT]
Semet, Frédéric [Auteur]
LAGIS-OSL
Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201 [LAMIH]
Laporte, Gilbert [Auteur]
Laboratoire CIRRELT Université Laval Quebec [CIRRELT]
Semet, Frédéric [Auteur]

LAGIS-OSL
Journal title :
RAIRO - Operations Research
Pages :
13-26
Publisher :
EDP Sciences
Publication date :
2009-01-01
ISSN :
0399-0559
Keyword(s) :
Problème du Vendeur m-Péripatétique
Problème du Voyageur de Commerce
heuristiques
Problème du Voyageur de Commerce
heuristiques
HAL domain(s) :
Computer Science [cs]/Operations Research [math.OC]
French abstract :
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 (cij) est une matrice de ...
Show more >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 (cij) 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.Show less >
Show more >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 (cij) 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.Show less >
English abstract : [en]
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 ((cij) is a cost matrix defined on E. The m-PSP ...
Show more >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 ((cij) 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.Show less >
Show more >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 ((cij) 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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- http://www.numdam.org/item/10.1051/ro/2009001.pdf
- Open access
- Access the document
- 2009001.pdf
- Open access
- Access the document