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.

Le Problème du Vendeur m-Péripatétique (m-PVP) est défini sur un graphe non orienté G=(V,E)V={1,,n} est l’ensemble des sommets, E={(i,j):i,jV,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.

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,jV,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.

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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2009001/

[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 :