Heuristiques pour le Problème du Vendeur m-Péripatétique

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

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 1, page 13-26
  • ISSN: 0399-0559

Abstract

top
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. 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.

How to cite

top

Duchenne, Éric, Laporte, Gilbert, and Semet, Frédéric. "Heuristiques pour le Problème du Vendeur m-Péripatétique." RAIRO - Operations Research 43.1 (2009): 13-26. <http://eudml.org/doc/250642>.

@article{Duchenne2009,
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 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. },
author = {Duchenne, Éric, Laporte, Gilbert, Semet, Frédéric},
journal = {RAIRO - Operations Research},
keywords = {Problème du Vendeur m-Péripatétique; Problème du Voyageur de Commerce; heuristiques.; problème du vendeur -péripatétique; problème du voyageur de commerce; heuristiques},
language = {eng},
month = {1},
number = {1},
pages = {13-26},
publisher = {EDP Sciences},
title = {Heuristiques pour le Problème du Vendeur m-Péripatétique},
url = {http://eudml.org/doc/250642},
volume = {43},
year = {2009},
}

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
DA - 2009/1//
PB - EDP Sciences
VL - 43
IS - 1
SP - 13
EP - 26
AB - 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.
LA - eng
KW - Problème du Vendeur m-Péripatétique; Problème du Voyageur de Commerce; heuristiques.; problème du vendeur -péripatétique; problème du voyageur de commerce; heuristiques
UR - http://eudml.org/doc/250642
ER -

References

top
  1. D. Bauer, H.J. Broersma and H.J. Veldman, On smallest non-Hamiltonian regular tough graphs. Congressus Numerantium70 (1990) 95–98.  
  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.  
  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.  
  4. J.B.J.M. De Kort, Lower bounds for symmetric m-peripatetic salesman problems. Optimization22 (1991) 113–122.  
  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.  
  6. J.B.J.M. De Kort, Sensitivity analysis for symmetric 2-peripatetic salesman problems. Oper. Res. Lett.13 (1993) 79–84.  
  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.  
  8. É. Duchenne, G. Laporte and F. Semet, The undirected m-peripatetic salesman problem: polyhedral results and new algorithms. Oper. Res.55 (2007) 949–965.  
  9. R. Gopalan, R. Batta and M.H. Karwan, The equity constrained shortest path problem. Comput. Oper. Res.17 (1990) 297–307.  
  10. K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res.126 (2000) 106–130.  
  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.  
  12. S. Lin, Computer solutions of the traveling salesman problem. Bell Syst. Tech. J.44 (1965) 2245–2269.  
  13. L. Lindner-Dutton, R. Batta and M.H. Karwan, Equitable sequencing of a Given set of hazardous materials shipments. Transportation Science25 (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.  
  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.  
  17. R. Wolfler Calvo and R. Cordone, A heuristic approach to the overnight security service problem. Comput. Oper. Res.30 (2003) 1269–1287.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.