Le Problème du Vendeur -Péripatétique (-PVP) est défini sur un graphe non orienté où est l’ensemble des sommets, est l’ensemble des arêtes et est une matrice de coûts définie sur . Le -PVP consiste à déterminer cycles hamiltoniens sur n’ayant aucune arête en commun et dont le coût total est minimal. Cet article décrit sept nouvelles heuristiques pour le -PVP et les compare à celle qui a été proposée par Krarup en 1975.
The -Peripatetic Salesman Problem (-PSP) is defined on a undirected graph where is the vertex set, is the edge set and (c is a cost matrix defined on . The -PSP consists of determining edge-disjoint hamiltonian cycles of least total cost on . This article describes seven new heuristics for the -PSP and compares them with the heuristic proposed by Krarup in 1975.
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] On smallest non-Hamiltonian regular tough graphs. Congressus Numerantium 70 (1990) 95-98. | MR | Zbl
, and ,[2] Vehicle scheduling in two-cycle flexible manufactoring systems. Math. Comput. Model. 20 (1994) 19-31. | Zbl
, , and ,[3] Solution of a large-scale traveling-salesman problem. Oper. Res. 2 (1954) 393-410. | MR
, and ,[4] Lower bounds for symmetric -peripatetic salesman problems. Optimization 22 (1991) 113-122. | MR | Zbl
,[5] A branch-and-bound algorithm for symmetric 2-peripatetic salesman problems. Eur. J. Oper. Res. 70 229-243. | Zbl
,[6] Sensitivity analysis for symmetric 2-peripatetic salesman problems. Oper. Res. Lett. 13 (1993) 79-84. | MR | Zbl
,[7] Branch-and-cut algorithms for the undirected -peripatetic salesman problem. Eur. J. Oper. Res. 162 (2005) 700-712. | MR | Zbl
, and ,[8] The undirected -peripatetic salesman problem: polyhedral results and new algorithms. Oper. Res. 55 (2007) 949-965. | MR | Zbl
, and ,[9] The equity constrained shortest path problem. Comput. Oper. Res. 17 (1990) 297-307. | MR | Zbl
, and ,[10] An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106-130. | MR | Zbl
,[11] 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] Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44 (1965) 2245-2269. | MR | Zbl
,[13] Equitable sequencing of a Given set of hazardous materials shipments. Transportation Science 25 (1991) 124-137.
, and ,[14] 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.
, and ,[15] TSPLIB - A traveling salesman problem library. ORSA J. Comput. 3 (1991) 376-384. | Zbl
,[16] A branch-and-bound algorithm for flow-path design of automated guided vehicle systems. Nav. Res. Logist. 38 (1991) 431-445. | MR | Zbl
and ,[17] A heuristic approach to the overnight security service problem. Comput. Oper. Res. 30 (2003) 1269-1287. | Zbl
and ,Cité par Sources :