A new heuristic for the traveling salesman problem

J. Carlier; P. Villon

RAIRO - Operations Research - Recherche Opérationnelle (1990)

  • Volume: 24, Issue: 3, page 245-253
  • ISSN: 0399-0559

How to cite


Carlier, J., and Villon, P.. "A new heuristic for the traveling salesman problem." RAIRO - Operations Research - Recherche Opérationnelle 24.3 (1990): 245-253. <http://eudml.org/doc/104984>.

author = {Carlier, J., Villon, P.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {heuristic; neighbouring relation; traveling salesman},
language = {eng},
number = {3},
pages = {245-253},
publisher = {EDP-Sciences},
title = {A new heuristic for the traveling salesman problem},
url = {http://eudml.org/doc/104984},
volume = {24},
year = {1990},

AU - Carlier, J.
AU - Villon, P.
TI - A new heuristic for the traveling salesman problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1990
PB - EDP-Sciences
VL - 24
IS - 3
SP - 245
EP - 253
LA - eng
KW - heuristic; neighbouring relation; traveling salesman
UR - http://eudml.org/doc/104984
ER -


  1. 1. R. BELLMAN, Dynamic Programming Treatment of The Traveling Salesman Problem, J.A.C.M., 1962, 9, pp. 61-63. Zbl0106.14102MR135702
  2. 2. R. BELLMAN, Dynamic Programming, Princeton University, New-Jersey, 1965. Zbl0077.13605MR90477
  3. 3. C. BERGE, Graphs and Hypergraphs, North Holland, Amsterdam, 1973. Zbl0254.05101MR357172
  4. 4. E. BONOMI and J. L. LUTTON, The N-city Traveling Salesman Problem: "Statistical Mechanics and Metropolis Algorithm", S.I.A.M. rev., 1984, 26, n° 4. Zbl0551.90095MR765672
  5. 5. J. CARLIER and P. VILLON, A Well Solved Case of the Traveling Salesman Problem, Research Report, Université de Technologie de Compiègne, 8, July 1987. 
  6. 6. J. EDMONDS and E. L. JOHNSON, Matching, Euler Tours and the Chinese Postman, Math. Program., 1973, 5, pp. 88-124. Zbl0281.90073MR321801
  7. 7. E. L. LAWLER, J. K. LENSTRA, A. H. G. RINNOOY KAN, and D. B. SHMOYS, The Traveling Salesman Problem, Wiley, Chichester, 1985. Zbl0562.00014MR811467
  8. 8. S. LIN and B. W. KERNINGHAN, An Effective Heuristic Algorithm for the Traveling Salesman Problem, Oper. Res., 1973, 21, pp. 498-516. Zbl0256.90038MR359742
  9. 9. M. W. PADBERG and S. HONG, On the Symmetric Traveling Salesman Problem: a Computational Study, Math. Program. Stud., 1980, 12, pp. 78-107. Zbl0435.90071MR571856
  10. 10. M. W. PADBERG and G. RINALDI, Optimization of a 532-city Symmetric Traveling Salesman Problem, A.F.C.E.T. Combinatorial group 20th anniversary, A.F.C.E.T. Publisher, 1986. Zbl0618.90082
  11. 11. H. D. RATLIFF and A. S. ROSENTHAL, Order Picking in a Rectangular Warehouse: a Solvable Case of the Traveling Salesman Problem, Oper. Res., 1983, 31, pp. 507-521. Zbl0523.90060
  12. 12. J. FONLUPT and A. NACHEF, Dynamic Programming and the Graphical Traveling Salesman Problem. Research report, ARTEMIS Laboratory, Grenoble, 1989. Zbl0795.68174

NotesEmbed ?


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.