Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-28T01:58:12.629Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  28 January 2009

Éric Duchenne ,
Gilbert Laporte  and
Frédéric Semet
Éric Duchenne
Affiliation:
LAMIH-ROI, Université de Valenciennes, Le Mont Houy, 59313 Valenciennes, Cedex 9, France
Gilbert Laporte
Affiliation:
GERAD and Canada Research Chair in Distribution Management, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, H3T 2A7, Montréal, Canada
Frédéric Semet
Affiliation:
LAMIH-ROI, Université de Valenciennes, Le Mont Houy, 59313 Valenciennes, Cedex 9, France; [email protected]
Get access

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.

Keywords

Problème du Vendeur m-PéripatétiqueProblème du Voyageur de Commerceheuristiques.
Type
Research Article
Information
RAIRO - Operations Research , Volume 43 , Issue 1 , January 2009 , pp. 13 - 26
Copyright
© EDP Sciences, ROADEF, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bauer, D., Broersma, H.J. and Veldman, H.J., On smallest non-Hamiltonian regular tough graphs. Congressus Numerantium 70 (1990) 95–98.
Blazewicz, J., Burkard, R.E., Finke, G. and Woeginger, G.J., Vehicle scheduling in two-cycle flexible manufactoring systems. Math. Comput. Model. 20 (1994) 19–31. CrossRef
Dantzig, G.B., Fulkerson, D.R. and Johnson, S.M., Solution of a large-scale traveling-salesman problem. Oper. Res. 2 (1954) 393–410.
De Kort, J.B.J.M., Lower bounds for symmetric m-peripatetic salesman problems. Optimization 22 (1991) 113–122. CrossRef
J.B.J.M. De Kort, A branch-and-bound algorithm for symmetric 2-peripatetic salesman problems. Eur. J. Oper. Res. 70 229–243.
De Kort, J.B.J.M., Sensitivity analysis for symmetric 2-peripatetic salesman problems. Oper. Res. Lett. 13 (1993) 79–84. CrossRef
Duchenne, É., Laporte, G. and Semet, F., Branch-and-cut algorithms for the undirected m-peripatetic salesman problem. Eur. J. Oper. Res. 162 (2005) 700–712. CrossRef
Duchenne, É., Laporte, G. and Semet, F., The undirected m-peripatetic salesman problem: polyhedral results and new algorithms. Oper. Res. 55 (2007) 949–965. CrossRef
Gopalan, R., Batta, R. and Karwan, M.H., The equity constrained shortest path problem. Comput. Oper. Res. 17 (1990) 297–307. CrossRef
Helsgaun, K., An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106–130. CrossRef
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.
Lin, S., Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44 (1965) 2245–2269. CrossRef
Lindner-Dutton, L., Batta, R. and Karwan, M.H., Equitable sequencing of a Given set of hazardous materials shipments. Transportation Science 25 (1991) 124–137. CrossRef
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.
Reinelt, G., TSPLIB – A traveling salesman problem library. ORSA J. Comput. 3 (1991) 376–384. CrossRef
Venkataramanan, M.A. and Wilson, K.A., A branch-and-bound algorithm for flow-path design of automated guided vehicle systems. Nav. Res. Logist. 38 (1991) 431–445. 3.0.CO;2-C>CrossRef
Wolfler Calvo, R. and Cordone, R., A heuristic approach to the overnight security service problem. Comput. Oper. Res. 30 (2003) 1269–1287. CrossRef