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

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

doi:10.1051/ro/2009001

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.

Résumé
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, \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.

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.

MR Zbl

DOI : 10.1051/ro/2009001

Classification : 90C09, 90C59
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro/2009001/

Bibliographie
Cité par

[1] D. Bauer, H.J. Broersma and H.J. Veldman, On smallest non-Hamiltonian regular tough graphs. Congressus Numerantium 70 (1990) 95-98. | MR | Zbl

[2] J. Blazewicz, R.E. Burkard, G. Finke and G.J. Woeginger, Vehicle scheduling in two-cycle flexible manufactoring systems. Math. Comput. Model. 20 (1994) 19-31. | Zbl

[3] G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, Solution of a large-scale traveling-salesman problem. Oper. Res. 2 (1954) 393-410. | MR

[4] J.B.J.M. De Kort, Lower bounds for symmetric $m$ -peripatetic salesman problems. Optimization 22 (1991) 113-122. | MR | Zbl

[5] J.B.J.M. De Kort, A branch-and-bound algorithm for symmetric 2-peripatetic salesman problems. Eur. J. Oper. Res. 70 229-243. | Zbl

[6] J.B.J.M. De Kort, Sensitivity analysis for symmetric 2-peripatetic salesman problems. Oper. Res. Lett. 13 (1993) 79-84. | MR | Zbl

[7] É. Duchenne, G. Laporte and F. Semet, Branch-and-cut algorithms for the undirected $m$ -peripatetic salesman problem. Eur. J. Oper. Res. 162 (2005) 700-712. | MR | Zbl

[8] É. Duchenne, G. Laporte and F. Semet, The undirected $m$ -peripatetic salesman problem: polyhedral results and new algorithms. Oper. Res. 55 (2007) 949-965. | MR | Zbl

[9] R. Gopalan, R. Batta and M.H. Karwan, The equity constrained shortest path problem. Comput. Oper. Res. 17 (1990) 297-307. | MR | Zbl

[10] K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106-130. | MR | Zbl

[11] J. Krarup, The peripatetic salesman and some related unsolved problems, in Combinatorial Programmin. Methods and Applications, edited by Roy B. D. Reidel Publ., Dordrecht (1975) 173-178. | MR | Zbl

[12] S. Lin, Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44 (1965) 2245-2269. | MR | Zbl

[13] L. Lindner-Dutton, R. Batta and M.H. Karwan, Equitable sequencing of a Given set of hazardous materials shipments. Transportation Science 25 (1991) 124-137.

[14] C. Quintero Araujo, R. Wolfler Calvo and M.A. Ould Louly, Développement de méthodes heuristiques pour le 2-voyageur de commerce péripatétique. 6e Conférence Francophone de MOdélisation et SIMulation - MOSIM 06, Rabat, Maroc.

[15] G. Reinelt, TSPLIB - A traveling salesman problem library. ORSA J. Comput. 3 (1991) 376-384. | Zbl

[16] M.A. Venkataramanan and K.A. Wilson, A branch-and-bound algorithm for flow-path design of automated guided vehicle systems. Nav. Res. Logist. 38 (1991) 431-445. | MR | Zbl

[17] R. Wolfler Calvo and R. Cordone, A heuristic approach to the overnight security service problem. Comput. Oper. Res. 30 (2003) 1269-1287. | Zbl

Cité par Sources :