Concorde TSP Solver
Encyclopedia
The Concorde TSP Solver is a program for solving the traveling salesman problem. It was written by David Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook, in ANSI C
, and is freely available for academic use.
Concorde has been applied to problems of gene mapping
, protein function prediction, vehicle routing
, conversion of bitmap images to continuous line drawings, scheduling ship movements for seismic surveys, and in studying the scaling properties of combinatorial optimization problems.
review both heuristic and exact solutions to the TSP; they call Concorde “a state of the art implementation” and state that it is “one of the best exact TSP solvers currently available.” add that Concorde “is widely regarded as the fastest TSP solver, for large instances, currently in existence.” In 2001, Concorde won a 5000 Guilder
prize from CMG
for solving a vehicle routing problem the company had posed in 1996.
ANSI C
ANSI C refers to the family of successive standards published by the American National Standards Institute for the C programming language. Software developers writing in C are encouraged to conform to the standards, as doing so aids portability between compilers.-History and outlook:The first...
, and is freely available for academic use.
Concorde has been applied to problems of gene mapping
Gene mapping
Gene mapping, also called genome mapping, is the creation of a genetic map assigning DNA fragments to chromosomes.When a genome is first investigated, this map is nonexistent. The map improves with the scientific progress and is perfect when the genomic DNA sequencing of the species has been...
, protein function prediction, vehicle routing
Vehicle routing problem
The vehicle routing problem is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics...
, conversion of bitmap images to continuous line drawings, scheduling ship movements for seismic surveys, and in studying the scaling properties of combinatorial optimization problems.
review both heuristic and exact solutions to the TSP; they call Concorde “a state of the art implementation” and state that it is “one of the best exact TSP solvers currently available.” add that Concorde “is widely regarded as the fastest TSP solver, for large instances, currently in existence.” In 2001, Concorde won a 5000 Guilder
Guilder
Guilder is the English translation of the Dutch gulden — from Old Dutch for 'golden'. The guilder originated as a gold coin but has been a common name for a silver or base metal coin for some centuries...
prize from CMG
CMG (company)
CMG was a consulting company focused on telecommunications and computing and based in London, United Kingdom. It was once a constituent of the FTSE 100 Index but was acquired by Logica in 2002.-History:...
for solving a vehicle routing problem the company had posed in 1996.
External links
- Concorde web site.
- Online access to Concorde solver at Argonne National Laboratories.