TSP Software

Andrea Lodi
D.E.I.S, University of Bologna
Viale Risorgimento 2, 40136 Bologna, Italy
andrea.lodi@unibo.it

Abraham Punnen
Department of Mathematics
Simon Fraser University, Canada
apunnen@sfu.ca

Chapter 16 of the book:
The Traveling Salesman Problems and its Variations G. Gutin, A. Punnen, Eds., Kluwer Academic Publishers, 2002

Page maintained by:

Matteo Boccafoli
Ph.D. student
Department of Mathematics, University of Ferrara
matteo.boccafoli@unife.it

Last Update: 29/11/2010

1  Introduction

For most of the software that is available through the web there is a high probability that the current URL may become obsolete over a period of time and some times it may become difficult trace new URL's, if any, for the information. In order to minimize such difficulties we maintain this web page which is mirrored at

http://v5o5jotqkgfu3btr91t7w5fhzedjaoaz8igl.unbsj.ca/~punnen/tspsoft.html

where latest information on software discussed in this chapter can be accessed in addition to information on updates and on new software.

Problem Transformations: The Asymmetric Traveling Salesman Problem (ATSP), i.e., a TSP in which the cost matrix is not necessarily symmetric, is clearly more general than the Symmetric Traveling Salesman Problem (STSP) where the cost matrix is always assumed to be symmetric. Often these two versions of the TSP are investigated independently.

On one hand, a code for the ATSP can in principle handle symmetric instances, but the effectiveness of many of the solution procedures for the ATSP depends on the asymmetric structure of the cost matrix (e.g., methods based on the Assignment Problem (AP) relaxation) and these procedures become less powerful in the symmetric case. On the other hand, substantial effort has been invested in developing efficient algorithms for solving the STSP. As a result very effective solution procedures and computer codes are available to solve the STSP. Chapter 1 and the computational section of Chapter 4 discuss transformations that reduce an ATSP into a STSP by doubling the number of nodes. Thus, any code for the STSP can be used to solve the ATSP using these transformations. Further, Chapter 1 contains transformations that reduce several variations of TSP to the TSP. Thus, under these transformations, the TSP software discussed here can also be used to solve these variations. Our discussion also includes information on some general-purpose codes that can be used in developing software for TSP and other combinatorial optimization problems.

2  Exact algorithms for TSP

In this section we consider various software to compute an optimal solution to the TSP.

1. Concorde: This is an ANSI C code for the exact solution of STSP and is available free of charge for academic research use. The code implements a branch-and-cut algorithm for the STSP developed by Applegate, Bixby, Chvátal and Cook [1] (see Chapter 2). It also provides a number of additional interesting features such as implementations of (i) heuristic algorithms (see Section 3 and Chapter 9), (ii) general algorithms for network optimization (e.g., algorithms for Minimum Cut computation, see Section 6), and (iii) a solver for the TSP variant called multiple TSP.

   The current release 12/15/1999 is well documented and can be obtained in tar.gz format (``co991215.tgz") from the web site:
   

   http://www.tsp.gatech.edu/concorde.html

2. CDT: This is a FORTRAN 77 code to compute an exact solution to the ATSP. It is published as code 750 in ACM Transactions on Mathematical Software. The code implements the branch-and-bound AP-based algorithm by Carpaneto, Dell'Amico and Toth [4] (see Chapter 4 for details and computational results). The release also includes an implementation of the well-known patching heuristic by Karp (see again Chapter 4 for details).

   The code can be obtained in gz format (``750.gz") from the web site:
   

   http://calgo.acm.org/750.gz

3. TSP1 (TSP2): These are Turbo Pascal codes for solving the STSP as developed by Volgenant and van den Hout in the ORSEP context [28]. Code TSP2 is menu driven with graphical options and implements a modified version of TSP1. The codes implement the `1-tree'-based branch-and-bound algorithm by Jonker and Volgenant [15]. (The release includes an implementation of Christofides heuristic [5] improved with some restricted 3-opt moves.)

   The code can be obtained in zip format (``volgenan.zip") from the web site:
   

   http://optimierung.mathematik.uni-kl.de/old/ORSEP/contents.html

4. tsp_solve: This is a C++ code for the exact solution of both ATSP and STSP. The release incorporates a number of algorithms: exact branch-and-bound algorithms based on the AP, 1-tree, and arborescence relaxations, and heuristic algorithms (see Section 3). Developed by Hurwitz and Craig, the package comes with good documentation and is available free of charge.

   The release 1.3.6 can be obtained in tar.gz format (``tsp_solve-1.3.6.tar.gz") from the web site:
   

   http://www.cs.sunysb.edu/~algorith/implement/tsp/implement.shtml
   A new release 1.3.7 is also available. For details contact the authors (e-mail: churitz@cts.com).

5. SYMPHONY: This is a general-purpose parallel branch-and-cut code for integer and mixed-integer programming (mainly over networks), written in ANSI C programming language by Ralphs. Developed for solving vehicle routing problems, the recent release 2.8 contains a (parallel) STSP solver which exploits some of the separation routines of Concorde.

   The code can be obtained, free of charge, by filling an appropriate form at the web site:
   

   http://www.branchandcut.org/

6. tsp*: This is an AMPL code to compute an exact solution of the STSP, as developed by Lee. This code is part of a didactic web site containing computational tools for combinatorial optimization problems including an AMPL implementation of the Christofides heuristic [5], and some codes for related problems such as minimum cut computation. (The package includes codes for finding: the minimum weight Euclidean spanning tree T, the minimum weight perfect matching M of odd degree nodes of T, and an Eulerian tour in T ÈM). Finally, the package also includes some utilities for viewing the solutions of Euclidean (2-D) problems with Mathematica.

   The code can be obtained from the web site:
   

   http://web.archive.org/web/20080302022600/http://www.ms.uky.edu/~jlee/jlsup/jlsup.html

7. Combinatorica: This is an add-on to the package Mathematica developed by Skiena [30]. It includes the capability of solving the STSP and the Hamiltonian cycle problem. For the STSP, Combinatorica can be used to compute upper and lower bounds, and the optimal solution.

   The package is included in the standard distribution of Mathematica (directory Packages/DiscreteMath/Combinatorica). It can also be obtained from the ftp site:
   

   http://www.cs.uiowa.edu/~sriram/Combinatorica/NewCombinatorica.m

8. rank: This is a software for ranking the solutions of the assignment problem by non-increasing values of the objective function. (Thus, this software could be used for solving the ATSP by testing feasibility of each assignment.) It is an executable file for DOS platform, developed by Metrick and Maybee in the ORSEP context [28] and implements the algorithm by Murty [25].

   The software can be obtained in zip format (``murty.zip") from the web site:
   

   http://optimierung.mathematik.uni-kl.de/old/ORSEP/contents.html

9. babtsp: This is a Pascal code implementing the branch-and-bound algorithm by Little, Murty, Sweeney, and Karel [20], and developed by Syslo for the book by Syslo, Deo and Kowalik [31].

   The code can be obtained in zip format (``syslo.zip") from the web site:
   

   http://optimierung.mathematik.uni-kl.de/old/ORSEP/contents.html

3  Approximation Algorithms for TSP

In this section we consider various software for the heuristic solution of STSP and ATSP.

1. LKH: This is an ANSI C code to compute an approximate solution of STSP. It implements a variation of the well known Lin-Kernighan heuristic [19] developed by Helsgaun [14] (see Chapter 9). The code is available free of cost for academic research.

   The current release 1.0 accepts input data in any of the TSPLIB [29] formats, and the output format can be controlled by appropriate parameter settings. The code can be obtained either in tar.gz format (``LKH-1.0.tgz") or in a

   stuffit archive format (``LKH-1.0.sit") from the web site:
   

   http://www.akira.ruc.dk/~keld/

2. SaCEC: This is a software package for the approximate solution of the STSP. It implements the ``Stem-and-Cycle Ejection Chain Algorithm" by Rego, Glover and Gamboa developed in the context of the 8^th DIMACS Implementation Challenge devoted to the TSP, the results of which are summarized in Chapter 9.

   The software is available for Microsoft Windows, Linux and Unix platforms at the web site:
   

   http://faculty.bus.olemiss.edu/crego/

3. Concorde: As mentioned in the previous section, the Concorde package includes effective ANSI C implementations of the following approximation algorithms for the STSP:
   1. Chained Lin-Kernighan heuristic [24],
   2. k-opt heuristic with k = 2, 2.5, 3,
   3. Greedy, Nearest Neighbor, Boruvka, and Farthest addition.

   An ANSI C implementation of the 1-tree relaxation algorithm by Held and Karp [12,] is also included to compute a lower bound on the optimal objective function value (see Chapter 9 for experimental results).

4. DynOpt: This is an ANSI C implementation a dynamic programming based algorithm developed by Balas and Simonetti [2]. It computes approximate solutions of both STSP and ATSP. Some flexibility in the input format is guaranteed by allowing the user to implement a macro (``theName(a,b)" in the code) which determines how to calculate the distances among cities.

   The code can be obtained in ascii format from the web site:
   

   http://www.andrew.cmu.edu/userneils/tsp/

5. LK: This is an ANSI C code for computing an approximate solution of the STSP. The code implements another effective variation [26] of the Lin-Kernighan heuristic [19], and it is available free of cost under the GNU Library General Public License. The code is developed using the ``Cweb" tool set [17], and to read it ``Cweb" and ``LaTeX" [11] are required. In addition, the (non-standard) BSD resource usage functions (``getrusage") are required to run the program. The code uses the TSPLIB [29] input formats allowing various output options.

   The current release 0.5.0 can be obtained in tar.gz format (``lk-0.5.0.tar.gz") from the web site:
   

   http://www.cs.utoronto.ca/~neto/research/lk/

6. TSP: This is a FORTRAN code for computing an approximate solution of the STSP. The code implements the well known Christofides heuristic [5], and is published in the book by Lau [18].
7. Routing: This is a FORTRAN code for computing an approximate solution of the ATSP and published as code 456 on Communications of the ACM. The code implements the node-insertion plus 3-opt heuristic by Fencl [7].

   The code, to the best of our knowledge, is not available on-line but can be obtained in pdf format (inside the article); go to http://portal.acm.org/ and enter a search string like "algorithm 456"
   

   http://portal.acm.org/

8. twoopt, threeopt, fitsp: These are Pascal codes for computing a heuristic solution of the symmetric TSP and published in the book by Syslo, Deo and Kowalik [31]. These codes implement the two-opt, three-opt and farthest insertion heuristics, respectively.

   The codes can be obtained in zip format (``syslo.zip") at the web site:
   

   http://optimierung.mathematik.uni-kl.de/old/ORSEP/contents.html

9. GATSS: This is a GNU C++ code for computing a heuristic solution of the STSP and is linked to a user interface in HTML via CGI-script. The code implements a standard genetic algorithm, and is suitable for didactic purposes.

   The code can be obtained in ascii format at the web site:
   

   http://www.acc.umu.se/~top/travel_information.html

10. Tours: This is a software package for computing approximate solutions of both STSP and ATSP. The software is able to compute several upper and lower bounds for the problems using various algorithms from the literature. In addition, a branch-and-bound code can be used to solve small instances to optimality. The software has graphical facilities, and has options of reading/saving both ascii and binary files. User's manual and on-line help are also included.

    The software is commercially available for Microsoft Windows platforms, and information on how to buy it can be found from the web site:
    

    http://www2.isye.gatech.edu/people/faculty/Marc_Goetschalckx/

11. RAI: This is an ANSI C code for the approximate solution of an ATSP and uses the ``flex/lex" tool. The code implements the algorithm by Brest and Zerovnik [3] based on a sequence of randomized insertions.

    The code can be obtained (directly as a source code) at the web site:
    

    http://marcel.uni-mb.si/~janez/rai/

12. ECTSP: This is a software package containing two different heuristics for solving the STSP. The first heuristic is based on a genetic algorithm while the second is an evolutionary programming heuristic. The package contains two executable files for the Windows 9x platforms, can be used free of charge, and comes with graphical interfaces.

    The software has been developed by Ozdemir and Embrechts, and can be obtained from the authors (using the two e-mail addresses {ozdemm,embrem}@rpi.edu).

13. GlsTsp: This is a C++ code for the heuristic solution of the STSP. The code implements the guided local search approach by Voudouris and Tsang [32]. The current release 2.0 includes an executable file for Microsoft Windows platforms, and the source code in C++ for Unix/Linux platforms.

    The release can be obtained free of charge in zip format (from ``glstsp.zip") from the web site:
    

    http://cswww.essex.ac.uk/CSP/glsdemo.html after a correction of link http:/demos/gls_tsp.zip in http://cswww.essex.ac.uk/CSP/demos/gls_tsp.zip

14. TSPGA: This is an ANSI C code for the approximate solution of the STSP using the ``pgapack" package. The code implements the approach of Frick [10] which combines evolutionary computation and local search.

    The code can be obtained from the author (using the e-mail address afr@aifd.uni-karlsruhe.de), and additional information can be found at the web site:
    

    http://www.rz.uni-karlsruhe.de/~lh71/

15. Operations_Research_3.0: This is a Mathematica-based software for solving operations research problems. It contains heuristic algorithms for the TSP, based on simulated annealing and ant colony systems. It also contains a specialized branch-and-bound algorithm. Mathematica version 3 or up is required to use this software.

    The software can be purchased from SoftAS GmbH and information on how to buy it can be found at the web site:
    

    http://web.archive.org/web/20080527080625/http://www.softas.de/op_researchframe.htm

4  Java Applets

1. http://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/java/TSP/

2. http://home.kpn.nl/waalewyn/tspx.html

3. http://pageperso.lif.univ-mrs.fr/~michel.vancaneghem/mait/demo/touropt.html

4. http://itp.nat.uni-magdeburg.de/~mertens/TSP/index.html

5   Variations of the TSP

1. concorde: As mentioned in Section 2, a linear programming based code for the TSP variant called Multiple TSP is provided within the concorde distribution.
2. RA-TSP: A variant of the ATSP called Arc Replenishment Traveling Salesman Problem has been studied by Mak and Boland [21], and their ANSI C codes for this problem and its variations are available for research purposes. In particular, the codes consist of a simulated annealing to obtain heuristic solutions, a Lagrangian relaxation for computing lower bounds, and a branch-and-bound algorithm. Both Lagrangian relaxation and branch-and-bound codes use CPLEX 6.0.

   Information on problems and codes can be obtained from the web site:
   

   http://www.deakin.edu.au/~vicky/

3. Salazar's_codes: Many interesting variants of the TSP has been considered by Salazar and co-authors. These include the Capacitated Vehicle Routing Problem, the Symmetric Generalized TSP, the Orienteering Problem, the Traveling Purchaser Problem, and the Pickup-and-Delivery TSP (see details on some of these problems in Chapter 13). For all these variations Salazar developed ANSI C codes which can be shared for research purposes.

   Information on problems and codes can be obtained from the web site:
   

   http://webpages.ull.es/users/jjsalaza/

4. HC: This is a FORTRAN 77 code to compute one or more Hamiltonian circuits in a directed graph and published as code 595 on ACM Transactions on Mathematical Software. It implements the algorithm by Martello [23].

   The code can be obtained in gz format (``595.gz") from the web site:
   

   http://calgo.acm.org/

5. hamcycle: This is a computer code which implements several algorithms to compute a Hamiltonian cycle in a graph, also including random graph generators. The codes, developed by Vandegriend and Culberson, are written in ANSI C programming language. The release includes a user's manual, and it is available free of charge.

   The code can be obtained in tar.gz format (``prog.tar.gz") at the web site:
   

   http://webdocs.cs.ualberta.ca/~joe/Theses/HCarchive/main.html

6. Groups&Graphs: This package contains computer codes to solve several graph theoretical problems including the Hamiltonian cycle problem. The codes, developed by Kocay, has two different releases: 3.0 for Macintosh platforms and 0.9 for Microsoft Windows platforms. Both are available free of charge.

   These releases can be obtained from the web site:
   

   http://www.combinatorialmath.ca/G&G/

7. Ariadne100: This is a software package for computing Hamiltonian cycles in a graph. Various experimental modes are also available with random graph generators. The software package is developed for Microsoft Windows platforms and is available free of charge.

   The current release 8.23.2000 can be obtained in exe format (``SetupAriadne.exe") at the web site:
   

   http://www.aya.or.jp/~nasukun/babalab/download.html

8. hamcrc: This is a FORTRAN code for finding the k^th vertex in a Hamiltonian cycle. By repeatedly calling this subroutine, a Hamiltonian cycle in a graph can be identified. The code is included in the book by Nijenhuis and Wilf [27].

   The code ``hamcrc.f" is available as part of the distribution file ``other.tar.gz" (which contains all the codes of the book) at the web site:
   

   http://www.cs.sunysb.edu/~algorith/implement/wilf/distrib/

9. LEP-CR: This is a LEDA-Extension Package to solve the Curve Reconstruction Problem. This problem is not exactly a variation of the TSP, but is closely related to the TSP. A specific TSP-based code to solve the Curve Reconstruction has been developed by Althaus.

   The package in tgz format (``LEP_curve_reconstruction_1.0.tgz") can be obtained at the web site:
   

   "http://www.mpi-inf.mpg.de/~althaus/LEP:Curve-Reconstruction/"

6  Other Related Problems and General-Purpose Codes

1. LP: Efficiently solving linear programming relaxations is crucial for state of the art exact TSP solvers. Since a review of (commercial) software for LP is out of the scope of this chapter, we refer to the Software Survey by Fourer published in OR/MS Today in 1999 [9].

   This survey is available on line at the web site:
   

   http://lionhrtpub.com/orms/orms-8-99/survey.html
   Almost all the presented packages are still available, often in more recent releases, thus the survey is still useful for giving the related pointers to the interested reader. (We are also confident that the survey will be updated soon.)

2. AP: As mentioned in the introduction, algorithms for the ATSP often require to solve the Assignment Problem as a relaxation. Several algorithms and codes for AP have been developed in the literature and are available on the web. We refer to the recent survey by Dell'Amico and Toth [6] for a thorough treatment of the subject.
3. mincut: Many of the LP-based methods for TSP need to compute a Minimum Cut in a graph in order to separate Subtour Elimination Constraints (see Chapter 2 for details). In recent years, several studies have been devoted to efficient algorithms and codes to solve this problem. We refer to the paper by Jünger, Rinaldi and Thienel [16] and to their library of codes which can be obtained at the web site:
   

   http://www.informatik.uni-koeln.de/old-ls_juenger/projects/mincut.html

Let us now consider some general-purpose software and libraries for developing TSP applications.

1. COIN-OR: The name COIN-OR stands for ``Common Optimization INterface for Operations Research". According the COIN-OR web page: ``Our goal is to create for mathematical software what the open literature is for mathematical theory".

   Detailed information can be found at the web site:
   

   http://www.coin-or.org

2. BOB (BOB++): This is a general-purpose software library to implement enumerative algorithms which exploit parallelism. TSP is used, among other combinatorial problems, to illustrate the use of the library.

   The current release 1.0 is available free of cost at the web site:
   

   https://software.prism.uvsq.fr/bobpp/

3. ABACUS: This is a callable C++ library designed to provide a general framework for the implementation of enumerative algorithms. It supports cutting plane generation and/or column generation, and the linear programming solvers CPLEX and XPRESS.

   The package can be purchased from OREAS, and information can be found at the web site:
   

   http://www.oreas.de

4. MINTO: This is a general-purpose software to solve mixed integer programs by using linear programming relaxations and branch-and-cut. The system allows the user to consider specific problems e.g. by adding problem-specific cutting planes and defining appropriate branching strategies. The current version supports CPLEX and OSL.

   Detailed information can be found at the web site:
   

   http://www2.isye.gatech.edu/faculty/Martin_Savelsbergh/software/

5. CP: In the last decade, Constraint Programming (CP) [22] has shown its effectiveness in modeling and solving real-world combinatorial optimization problems. CP is a programming paradigm exploiting Constraint Satisfaction techniques, and many CP tools have been developed to tackle discrete (optimization) problems. Although CP is currently far from being competitive for solving ``pure" problems like TSP, many TSP-like applications involving side constraints have been successfully solved through CP algorithms (such as the TSP with Time Windows, see, e.g., Focacci, Lodi, Milano [8]).

   An exhaustive list of CP tools would be too long and is obviously outside the scope of this chapter. However, useful pointers along with the C++ source code of the TSP constraint (in zip format, ``cost-based.zip") used in [8] are available at the web site:
   

   http://www.or.deis.unibo.it/research_pages/ORcodes/CP.html

6. parSA-Lib: This is a general-purpose software library providing a general framework for implementing simulated annealing algorithms in parallel. The library is written in C++ programming language.

   Available by filling up a request form at the web site:
   

   http://www2.cs.uni-paderborn.de/cs/ag-monien/SOFTWARE/PARSA/

7. PPBB-Lib: This is a general-purpose software library that can be used to parallelize sequential branch-and-bound algorithms. The library is written in ANSI C programming language.

   Detailed information can be found at the web site:
   

   http://www2.cs.uni-paderborn.de/cs/ag-monien/SOFTWARE/PPBB/ppbblib.html

7  New and Lost URLs

  Missing URLs

1. Ascheuer's_codes: Interesting variations of the ATSP called ATSP with Precedence Constraints and the ATSP with Time Windows have been studied by Ascheuer and co-authors. Ascheuer developed ANSI C codes for solving these problems.

  New URLs

2. Another list of general-purpose software and libraries for developing TSP applications.

   http://www.adaptivebox.net/CILib/code/tspcodes_link.html

References

[1]

D. Applegate, R.E. Bixby, V. Chvátal, and W. Cook. On the solution of traveling salesman problems. Documenta Mathematica, Extra Volume ICM III:645-656, 1998.

[2]

E. Balas and N. Simonetti. Linear time dynamic programming algorithms for new classes of restricted TSPs: A computational study. INFORMS Journal on Computing, 13:56-75, 2001.

[3]

J. Brest and J. Zerovnik. An approximation algorithm for the asymmetric traveling salesman problem. Ricerca Operativa, 28:59-67, 1998.

[4]

G. Carpaneto, M. Dell'Amico, and P. Toth. Exact solution of large-scale asymmetric traveling salesman problems. ACM Transactions on Mathematical Software, 21:394-409, 1995.

[5]

N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.

[6]

M. Dell'Amico and P. Toth. Algorithms and codes for dense assignment problems: the state of the art. Discrete Applied Mathematics, 100:17-48, 2000.

[7]

Z. Fencl. Algorithm 456 - routing problem [H]. Communications of ACM, 16:572-574, 1973.

[8]

F. Focacci, A. Lodi, and M. Milano. A hybrid exact algorithm for the TSPTW. Technical Report OR/01/2, D.E.I.S., University of Bologna, 2001. INFORMS Journal on Computing (to appear).

[9]

R. Fourer. Software survey: Linear programming. OR/MS Today, 26:64-71, 1999.

[10]

A. Frick. TSPGA - an evolution program for the symmetric traveling salesman problem. In H.J. Zimmermann, editor, EUFIT'98 - 6th European Congress on Intelligent Techniques and Soft Computing, pages 513-517. Mainz Verlag, Aachen, 1998.

[11]

M. Goossens, F. Mittelbach, and A. Samarin. The LATEX Companion. Addison-Wesley, Reading, Massachusetts, 1998. http://www.latex-project.org/.

[12]

M. Held and R.M. Karp. The traveling-salesman problem and minimum spanning trees. Operations Research, 18:1138-1162, 1970.

[13]

M. Held and R.M. Karp. The traveling-salesman problem and minimum spanning trees: part II. Mathematical Programmin, Ser. A, 1:6-25, 1971.

[14]

K. Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 126:106-130, 2000.

[15]

R. Jonker and T. Volgenant. A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation. European Journal of Operational Research, 9:83-89, 1982.

[16]

M. Jünger, G. Rinaldi, and S. Thienel. Practical performance of efficient minimum cut algorithms. Algorithmica, 26:172-195, 2000.

[17]

D.E. Knuth and S. Levy. The CWEB System of Structured Documentation. Addison-Wesley, Reading, Massachusetts, 1993. http://www-cs-faculty.stanford.edu/ ~ knuth/cweb.html.

[18]

H.T. Lau. Combinatorial heuristic algorithms with FORTRAN, volume 280 of Lecture notes in Economics and Mathematical Systems. Springer Verlag, Berlin-New York, 1986.

[19]

S. Lin and B.W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21:498-516, 1973.

[20]

J.D.C Little, K.G. Murty, D.W. Sweeney, and C. Karel. An algorithm for traveling salesman problem. Operations Research, 11:972-989, 1963.

[21]

V. Mak and N. Boland. Heuristic approaches to asymmetric travelling salesman problems with replenishment arcs. International Transactions in Operational Research, 7:431-447, 2000.

[22]

K. Marriott and P.J. Stuckey. Programming with Constraints. The MIT Press, 1998.

[23]

S. Martello. An enumerative algorithm for finding hamiltonian circuits in a directed graph. ACM Transactions on Mathematical Software, 9:131-138, 1983.

[24]

O. Martin, S.W. Otto, and E.W. Felten. Large-step markov chains for the tsp incorporating local search heuristics. Operations Research Letters, 11:219-224, 1992.

[25]

K.G. Maurty. An algorithm for ranking all the assignments in increasing order of cost. Operations Research, 16:682-687, 1968.

[26]

D.M. Neto. Efficient Cluster Compensation For Lin-Kernighan Heuristics. PhD thesis, University of Toronto, Canada, 1999.

[27]

A. Nijenhuis and H.S. Wilf. Combinatorial Algorithms. Academic Press, Inc., 1978.

[28]

ORSEP. Operations research software exchange program. European Journal of Operational Research, 38:118-122, 1989.

[29]

G. Reinelt. TSPLIB - a traveling salesman problem library. ORSA Journal on Computing, 3:376-384, 1991. http://www.crpc.rice.edu/softlib/tsplib/.

[30]

S.S. Skiena. Implementing Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Addison-Wesley, Redwood City, CA, 1990.

[31]

M.M. Syslo, N. Deo, and J.S. Kowalik. Discrete Optimization Algorithms with Pascal Programs. Prentice-Hall, Englewood Cliffs, 1983.

[32]

C. Voudouris and E. Tsang. Guided local search and its application to the travelling salesman problem. European Journal of Operational Research, 113:469-499, 1999.